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

Parallel Computing


Administrative details

Instructor: Pavel Tvrdik
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 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 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

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 – 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

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 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.LeightonIntroduction 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



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Virtual Fashion Technology

Virtual Fashion Education


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


News About Tech, Money and Innovation


Modern art using the GPU

Theme Showcase

Find the perfect theme for your blog.


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


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

The Blog

The latest news on and the WordPress community.

%d bloggers like this: