
CITIDEL >
Syllabus Collection >
Syllabus >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10117/7087

Title:  opics in Parallel Computing 
Authors:  Computer Sciences Department  University of Wisconsin Madison 
Issue Date:  
Publisher:  Computer Sciences Department  University of Wisconsin Madison 
Citation:  http://www.cs.wisc.edu/~tvrdik/cs838.html 
Abstract:  CS 838: Topics in Parallel Computing
Spring 1999
UNIVERSITY OF WISCONSINMADISON
Computer Sciences Department
Administrative details
Instructor: Pavel Tvrdik
email: tvrdik@cs.wisc.edu
Office: CS 6376
Phone: 2655907
Office hours: Tuesday/Thursday 9:3011:00 a.m. or by appointment
Lecture times: Tuesday/Thursday 08:0009:15 a.m.
Classroom: 1221 Computer Sciences
The contents
1. Syllabus
2. Schedule and materials
3. Optional books
4. Course requirements
5. Term projects.
6. Grading policy
The syllabus of the lectures
The aim of the course is to introduce you into the art of designing efficient and analyzing parallel algorithms for both sharedmemory and distributed memory machines. It is structured into four major parts.
The first part of the course is a theoretical introduction into the field of design and analysis of parallel algorithms. We will explain the metrics for measuring the quality and performance of parallel algorithms with the emphasis on scalability and isoefficiency. To prepare the framework for parallel complexity theory, we will introduce a fundamental model, the PRAM model. Then we will introduce the basics of parallel complexity theory to provide a formal framework for explaining why some problems are easier to parallelize then some others. More specifically, we will study NCalgorithms and Pcompleteness.
The second part of the course will deal with communication issues of distributed memory machines. Processors in a distributed memory machine need to communicate to overcome the fact that there is no global common shared storage and that all the information is scattered among processors' local memories. First we survey interconnection topologies and communication technologies, their structural and computational properties, embeddings and simulations among them. All this will form a framework for studying interprocessor communication algorithms, both pointtopoint and collective communication operations. We will concentrate mainly on orthogonal topologies, such as hypercubes, meshes, and tori, and will study basic routing algorithms, permutation routing, and onetoall as well as alltoall communication operation algorithms. We conclude with some more realistic abstract models for distributed memory parallel computations.
The third and fourth parts are devoted to the case studies of parallel algorithms. In the third part, we will study three families of distributed memory parallel algorithms, in which the communication algorithms explained above are heavily used. First we explain basic oblivious sorting algorithms. Parallel branchandbound algorithms are given to learn more about load balancing and program termination protocols for irregular parallel algorithms. Finally, we discuss important instances of efficient parallel algorithms on dense matrix, namely basic matrix operations and algorithms for solving systems of linear equations.
Finally, in the fourth part, we will get back to the PRAM model to enjoy the elegance of several wellknown sharedmemory parallel algorithms. We start with fundamental parallel PRAM NCalgorithms, such as parallel prefix sum, pointer jumping, and Euler tour construction. Based upon that, we will explain more complicated algorithms, such as parallel list ranking, tree contraction, and connected components algorithm.
Back to the beginning of the page
Class schedule and course materials
The following schedule is tentative and can change. I will prepare handout materials on the web for each lecture. The primary materials are lecture notes in condensed form prepared in latex using small fonts and placed on web in Postscript (ps), no later than at the end of the preceding week. Besides taking handout materials to the class, make sure to take papers or notebooks, you might need them to take notes of what we will be writing on the blackboard. Then two other kinds of materials will be generated semiautomatically from the lecture notes. The slides which you will see during lectures will appear on web also in Postscript form. Slides are prepared from lecture notes by ommiting less important parts, but using larger fonts. Finally, I will try to place on web html versions of (at least some) lecture notes.
Also specifications of homeworks will appear in the last column of the schedule table simultaneously with the corresponding course materials. For a list of books you might find useful for this course, see the list bellow.
Week Day Topic Lecture Notes Homeworks
1 Jan 19 Performance and scalability of parallel algorithms Section 1 (ps)
1 Jan 21 PRAM models Section 2 (ps) (slides) (html)
2 Jan 26 Parallel complexity theory  NC algorithms Section 3 (ps) (slides) (html)
2 Jan 28 Parallel complexity theory  Pcompleteness Section 4 (ps) (slides) (html) Homework 1 (ps) (html)
3 Feb 2 Interconnection networks  survey of topologies Section 5 (ps) (slides) (html)
3 Feb 4 Interconnection networks  properties Section 5 (ps) (slides) (html) Homework 2 (ps) (html)
4 Feb 9 Embeddings and simulations among INs I. Section 6 (ps) (slides) (html)
4 Feb 11 Embeddings and simulations among INs II. Section 6 (ps) (slides) (html) Homework 3 (ps) (html)
5 Feb 16 Routing and switching technologies Section 7 (ps) (slides) (html)
5 Feb 18 Virtual channels and deadlocks Section 8 (ps) (slides) (html)
6 Feb 23 Permutation routing in meshbased networks Section 9 (ps) (slides) (html)
6 Feb 25 Permutation routing in hypercubic networks Section 10 (ps) (slides) (html) Homework 4 (ps)
7 Mar 2 Onetoall broadcast algorithms Section 11 (ps) (slides) (html)
7 Mar 4 Multicast, IRC, and onetoall scatter algorithms Section 12 (ps) (slides) (html) Homework 5 (ps) (html)
8 Mar 16 Alltoall broadcast algorithms in SF networks Section 13 (ps) (slides) (html)
8 Mar 18 Alltoall scatter algorithms Section 14 (ps) (slides) (html) Homework 6 (ps) (html)
9 Mar 23 Introduction to parallel sorting on meshes Section 15 (ps) (slides) (html)
9 Mar 25 Asymptotically optimal mesh sorting algorithm Section 16 (ps) (slides) (html) Homework 7 (ps) (html)
10 Mar 30 Parallel sorting on hypercubic machines Section 17 (ps) (slides) (html)
10 Apr 1 Optimal EREW PRAM sorting Section 18 (ps) (slides) (html)
11 Apr 6 Parallel matrix operations Section 19 (ps) (slides)
11 Apr 8 Solving systems of equations in parallel I Section 20 (ps) (slides) Homework 8 (ps)
12 Apr 13 Solving systems of equations in parallel II Section 20 (ps) (slides)
12 Apr 15 Parallel scan  introduction Section 21 (ps) (slides) Homework 9 (ps)
13 Apr 20 Advanced applications of parallel scan Section 22 (ps) (slides)
13 Apr 22 Parallel scan on linked lists Section 23 (ps) (slides)
14 Apr 27 Deterministic coin tossing Section 24 (ps) (slides)
14 Apr 29 Euler tour technique and its applications Section 25 (ps) (slides) Homework 10 (ps)
15 May 4 Parallel tree contraction Section 26 (ps) (slides)
15 May 6 Parallel connected component algorithms Section 27 (ps) (slides)
Finals May 11 Final Exam (Tuesday, 8:00)
Back to the beginning of the page
List of optional books for this course
There is a couple of books on parallel algorithms and parallel computing you might find useful as a supplementary source of information, but in no case you have to read them to get through this course. They can serve as a source of additional information if you wish to understand more about problems discussed in the course. An incomplete list of such useful books follows:
* Vipin Kumar, et al.: Introduction to parallel computing, The Benjamin/Cummings Publ. Co., 1994, ISBN 080533170
* R. Greenlaw, et al.: Limits to parallel computation, Oxford University Press, 1995, ISBN 0195085914
* J. Ja'Ja': An introduction to parallel algorithms , AddisonWesley, 1992, ISBN 0201548569
* J. H. Reif, ed. : Synthesis of parallel algorithms , Morgan Kaufmann Publ., 1993, ISBN 155860135X
* T.Leighton: Introduction to parallel algorithms and architectures, Morgan Kaufmann Publ., 1992, ISBN 1558601171
* J.Duato et al.: Interconnection networks: An engineering approach, IEEE CS Press, 1997, ISBN 0818678003
Back to the beginning of the page
Course requirements
Administrative requirements
Each student registrated for this course is required either to provide me a reference to his personal home page with a photo and information on professional background or to provide me a passport photo and send me by email the following information:
1. first and family name,
2. thesis topic,
3. supervisor's name,
4. experience with parallel computing and/or machines in general.
Programming skills
You are expected to have some programming experience with either C or C++. PVM and MPI2 are C/C++ parallel programming libraries.
Prerequisites
Background in graph theory, programming techniques, data structures, computer architecture, and complexity theory will be of great help.
Computer facilities and accounts
We will be using UNIX workstations (running the Sun Solaris operating systems and X windows) and SP2 machine for the programming term project. You need an account on the SP2 machine and on at least one of local UNIX workstation clusters.
Homeworks
There will be 10 small homeworks. At the end of selected Thursday lectures (for specific dates, check always the class schedule on this page), you will be asked to do a small problem solving homework, which will be tightly related to the topics covered by that week's two lectures. The due for emailing me the the solutions and/or answers will be always Wed noon next week. Every homework will be marked by 2 points so that the total contribution of all homeworks to the course grading is 20% (see bellow).
Written final exam
The final written exam is mandatory. It will be a problem solving exam. You will be given a collection of problems, similar or related to those discussed and solved (often as homeworks) during the course. Tentatively, the written exam should take two hours or more.
Back to the beginning of the page
Grading Policy
This course will be graded on an AF scale. The major part of the grading will be based on the results of your programming project and the written exam. More detailed criteria on how the term project will be evaluated will appear here soon, but basically, correctness of your parallel algorithm, your performance and scalability figures, and quality of the report will be the main criteria.
Term project: 40%
Homeworks: 40%
Final exam: 20%
Back to the beginning of the page 
URI:  http://www.citidel.org/handle/10117/7087 
Appears in Collections:  Syllabus

Files in This Item:
File 
Size  Format 
73cs838.html  19Kb  HTML  View/Open 

All items in DSpace are protected by copyright, with all rights reserved.
