CS 606, Foundations of Parallel Computation

Basic questions that will be explored

How do you get many processors to cooperatively solve a computational problem? How do you distribute work and data among them? If you have P processors, will you finish in 1/P time?
How do you build a parallel computer? What network do you use? Are certain networks better for certain computational problems? How do you estimate the cost of different networks?

The approach is theoretical:

Abstract models + proofs + analysis
Spirit of the course: similar to "Design and analysis of Algorithms", "Discrete mathematics".
No programming.

Prerequisites:

For PGs: UG course on Design and analysis of algorithms.

For UGs: CS 218.

Quiz for testing aptitude: This quiz gives a flavour of the kind of arguments that get used all the time in this course. If you cannot solve this quiz in half an hour, then perhaps you should not take this course. See the notes below and the problem sets in them to get a further sense of whether you will like the course.

Solution and grading scheme for final exam of last year

Possible Topics:

Parallel computers based on interconnection networks such as hypercubes, shuffle-exchanges, trees, meshes and butterfly networks. Parallel algorithms for arithmetic, linear algebra, sorting, Fourier Transform, recurrence evaluation, and dense graph problems. Use of graph embedding techniques to compare different networks.

Shared memory based parallel computers. Algorithms for list ranking, maximal independent set, arithmetic expression evaluation, convex hull problems and others.

Message routing on multidimensional meshes, Butterfly networks, Hypercubes, Shuffle Exchange networks, Fat-trees and others. Simulation of shared memory on networks. Routing on expander-based networks.

Limits to parallelizability and P-completeness.

Thompson grid model for VLSI. Layouts for standard interconnection networks. Lower bound techniques for area and area time-squared tradeoffs. Area-Universal networks.