CS 606, Foundations of Parallel Computation

Basic questions that will be explored The approach is theoretical:


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.

Lecture notes: