6.892 Course Outline

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