Instructor: |
Pavel Tvrdik |

email: |
tvrdik@cs.wisc.edu |

Office: |
CS 6376 |

Phone: |
265-5907 |

Office hours: |
Tuesday/Thursday 9:30-11:00 a.m. or by appointment |

Lecture times: |
Tuesday/Thursday 08:00-09:15 a.m. |

Classroom: |
1221 Computer Sciences |

The aim of the course is to introduce you into the art of designing efficient and analyzing parallel algorithms for both shared-memory 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 NC-algorithms and P-completeness.

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 point-to-point 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 one-to-all as well as all-to-all 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 branch-and-bound 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 well-known shared-memory parallel algorithms. We start with fundamental parallel PRAM NC-algorithms, 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 |

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 – P-completeness | 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 mesh-based 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 | One-to-all broadcast algorithms | Section 11 (ps) (slides)(html) | |

7 | Mar 4 | Multicast, IRC, and one-to-all scatter algorithms | Section 12 (ps) (slides)(html) | Homework 5 (ps) (html) |

8 | Mar 16 | All-to-all broadcast algorithms in SF networks | Section 13 (ps) (slides)(html) | |

8 | Mar 18 | All-to-all 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 |

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 0-8053-3170*R. Greenlaw, et al.*:**Limits to parallel computation**, Oxford University Press, 1995, ISBN 0-19-508591-4*J. Ja’Ja’*:**An introduction to parallel algorithms**, Addison-Wesley, 1992, ISBN 0-201-54856-9*J. H. Reif, ed.*:**Synthesis of parallel algorithms**, Morgan Kaufmann Publ., 1993, ISBN 1-55860-135-X*T.Leighton*:**Introduction to parallel algorithms and architectures**, Morgan Kaufmann Publ., 1992, ISBN 1-55860-117-1*J.Duato et al.*:**Interconnection networks: An engineering approach**, IEEE CS Press, 1997, ISBN 0-8186-78003

**Source:**

http://pages.cs.wisc.edu/~tvrdik/cs838.html#schedule

Virtual Fashion Technology

Virtual Fashion Education

toitocuaanhem

"chúng tôi chỉ là tôi tớ của anh em, vì Đức Kitô" (2Cr 4,5b)

Cùng Viết Hiến Pháp

hienphap.net

VentureBeat

News About Tech, Money and Innovation

digitalerr0r

Modern art using the GPU

Theme Showcase

Find the perfect theme for your blog.

lsuvietnam

Learn to Learn

Gocomay's Blog

Con tằm đến thác vẫn còn vương tơ

Toán cho Vật lý

Khoa Vật lý, Đại học Sư phạm Tp.HCM - ĐT :(08)-38352020 - 109

Maths 4 Physics & more...

Blog Toán Cao Cấp (M4Ps)

Bucket List Publications

Indulge- Travel, Adventure, & New Experiences

Lib4U

"Behind every stack of books there is a flood of knowledge."

The WordPress.com Blog

The latest news on WordPress.com and the WordPress community.

%d bloggers like this: