6.892 Course Outline
- Introduction. Overview of the course;
data-parallel computing, prefix computations, segmented operations,
work and critical path, Brent's theorem.
- The data-parallel abstraction. Implementation
of data-parallel model on fixed-connection networks, EREW vs. CRCW,
randomized routing on hypercubic networks, provably good routing.
- Sorting. Bitonic sort, radix sort, sample
sort.
- NESL. The NESL data-parallel language,
nested parallelism, matrix multiplication, parallel quicksort.
- List ranking. Pointer jumping,
work-efficient parallel prefix.
- Tree and graph algorithms. Euler tour, tree
contraction, connected components.
- String matching. Finding a pattern in a
string, Breslauer-Galil algorithm.
- Multithreaded programming. The Cilk language,
work and critical path, Brent's theorem, busy leaves scheduling,
randomized work-stealing.
- Analysis of multithreaded algorithms.
Algorithms for sorting, matrix multiplication, LU-decomposition;
analysis of time.
- Race conditions. Detecting and localizing
determinacy races; the SP-bags algorithm.
- Provably good scheduling I.
Blumofe-Leiserson scheduling algorithm; recycling game.
- Provably good scheduling II.
Blumofe-Leiserson scheduling algorithm.
- Space bounds. Space for algorithms scheduled
with busy-leaves. Blelloch-Gibbons-Matias scheduling algorithm.
- Shared-memory models. Sequential
consistency, Dijkstra's and Dekker's mutual-exclusion algorithms,
Cypher's lower bound.
- Wait-free synchronization. Universality of
compare-and-swap (Herlihy), etc.
- Message passing. Message-passing libraries,
protocols, avoiding deadlock. Term project proposal due.
- Active-message programming. Consumption
assumption, overproduction, protocol safety, termination detection.
- Distributed shared memory I.
Dag-consistency, the Backer algorithm, analysis of page faults.
- Distributed shared memory II. Semantics of
dag-consistency; relation to location consistency.
- Workstation scheduling. Awerbuch-Leighton
algorithm.
- Macroscheduling. Scheduling adaptively
parallel jobs.
- I/O. Permuting and sorting data on disks.
- Advanced topics.
- Advanced topics.
- Term project presentations.
- Term project presentations.