Introduction to Parallel Computer Architecture

CS 15-840(A), Fall 1994

MWF 2:30-3:20 WeH 5304

Professors:

Adam Beguelin
Office: Wean 8021
Phone: 268-5295

Bruce Maggs
Office: Wean 4123
Phone: 268-7654

Course Description

This course covers both theoretical and pragmatic issues related to parallel computer architecture. We will study existing parallel architectures such as the Cray T3D, C90, and Intel Paragon and iWarp. Low level mechanisms for programming these systems will be discussed as well. Students will have some hands on experience with existing parallel computers, both to gain experience with the low level programming mechanisms provided by the hardware and to evaluate the architectures. We will also cover theoretical issues of computer architecture and relate that theory to existing machines.

Grading

Grading will be based on class participation and homework assignments.

Tentative list of lectures

Sept 19: Overview of course. Motivation for building parallel computers. Current uses of parallel computers.
Sept 23: Fixed-connection network model Linear arrays. Algorithms for sorting. Word model vs. bit model. (Maggs)
Sept 26: Arithmetic Parallel prefix computations; carry-lookahead addition; carry-save addition. (Maggs)
Sept 28: Systolic algorithms. Retiming. Conversion of semisystolic algorithms to systolic algorithms. (Maggs)
Sept 30: Odd-even transposition sort. The zero-one principle. (Maggs)
Oct 3: Meshes. Greedy routing. Routing by sorting. Row-column-row routing. (Maggs)
Oct 5: The architecture of the CMU/Intel iWarp. Guest Lecturer: Dave O'Hallaron
Oct 7: More on the iWarp. Guest Lecturer: Dave O'Hallaron
Oct 10: The architecture of the Intel Paragon. Guest Lecturer: Susan Hinrichs
Oct 12: More on the Paragon. Guest Lecturer: Susan Hinrichs
Oct 14: Hypercubes. Subgraphs of the hypercube: linear arrays, meshes, double-rooted complete binary trees. Bounded-degree hypercubic networks: butterfly networks; shuffle-exchange graphs. (Maggs)
Oct 19: Computing Fast Fourier Transforms on butterfly networks. Odd-even merge sort. (Maggs)
Oct 21: A model of the Connection Machine CM-2: Scans, arithmetic, cube-swap, route. Sorting on the CM-2. (Maggs)
Oct 24: Benes networks. Circuit switching on Bene\v{s} networks. Packing, unpacking, and greedy circuit switching on butterfly networks. (Maggs)
Oct 26: The architecture of the Cray T3D (Beguelin) Homework
Oct 28: More on the T3D. Message passing protocols and interfaces: PVM. (Beguelin)
Oct 31: More on PVM (Beguelin)
Nov 2: Proposed message passing standard MPI (Beguelin) MPI Postscript
Nov 4: Multibutterfly networks. Deterministic packet routing. Fault tolerance. (Maggs)
Nov 7: Circuit switching on multibutterfly networks. Construction of nonblocking networks. (Maggs)
Nov 9: Parallel Random-Access Machines (PRAMs). Work-efficient algorithms. Prefix computations. Brent's Theorem. The Scan model. (Maggs)
Nov 11: Randomized routing on leveled networks. Valiant's Algorithm. Ranade's algorithm. (Maggs)
Nov 14: Valiant's algorithm for routing on butterfly networks. (Maggs)
Nov 16: VLSI layout theory. Layouts of trees, meshes, butterflies, hypercubes. (Maggs)
Nov 18: The architecture of the Cray Y-MP and C90 Guest lecturer: Guy Blelloch.
Nov 21: More on the Y-MP and C90. Guest lecturer: Guy Blelloch.
Nov 28: Area and volume universal networks. Fat trees. (Maggs)
Nov 30: CM-5 (Maggs)
Dec 2: CM-5 (Maggs)
Dec 5: LogP, BSP (Maggs)
Dec 7: The architecture of the Kendall Square Research KSR-1. (Beguelin) Homework
Dec 9: The architecture of the Kendall Square Research KSR-1. (Beguelin) T3D Programming Assignment