CS 606, Foundations of Parallel Computation
Fundamental theoretical issues in designing parallel algorithms and
architectures.
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.
Prerequisites:
CS 301 Design and Analysis of Algorithms, or equivalent.
Textbooks:
1. Introduction to Parallel Algorithms and Architectures: Arrays, Trees,
Hypercubes. F.T.Leighton. Morgan Kaufmann Publishers, San Mateo,
California. 1991.
2. An Introduction to Parallel Algorithms. Joseph JaJa. Addison
Wesley. 1992.
3. Introduction to Parallel Processing. B. Codenotti, M. Leoncini.
Addison Wesley. 1992.
4. Computational aspects of VLSI. J. D. Ullman. Computer Science
Press, Rockville, Md., 1984.
These will be supplemented by lecture notes.
Evaluation:
Quizzes, midterm and final examinations.