Course Description
How do we make parallel programming mainstream? This is one of the most important problems facing computer systems researchers today, and solving it is the key to unlocking the performance potential of multicore processors. This seminar course focuses on recent breakthroughs in this area that attempt to address this problem by exploiting the deep structure of parallelism and locality in algorithms. These ideas are useful not only for computational science applications but also for complex applications from other domains such as data-mining, network science, artificial intelligence, and games.

Topics include the following:
  1. Structure of parallelism and locality in important algorithms
  2. Algorithm abstractions: dependence graphs, halographs
  3. Multicore architectures: interconnection networks, cache coherence, locks, lock-free synchronization
  4. Memory consistency models
  5. Optimistic parallel execution of programs
  6. Scheduling and load-balancing
  7. Parallel data structures: linearizability, lock-free data structures, transactional memory, array/graph partitioning
  8. Memory hierarchies and locality
  9. Cache-oblivious algorithms
  10. Compiler analysis and transformations for regular and irregular programs
  11. Performance models: PRAM, BPRAM, logP
  12. Self-optimizing software, machine-learning techniques for program optimization
  13. GPUs and GPU programming
  14. Case studies: Cilk, PGAS languages, TBBs, Map-reduce
  15. Approximate computing for power and energy optimization

Students will present papers, participate in discussions, and do a substantial final project. The readings will include some of the classic papers in the field of parallel programming.

Prerequisites: programming maturity, knowledge of C/C++, basic courses on modern computer architecture and compilers


For basic material on computer architecture, read "Computer Architecture: A Quantitative Approach"
by Hennessy & Patterson, Morgan Kaufmann Publishers. For basic material on compilers, read "Optimizing Compilers for Modern Architectures" by Allen and Kennedy.

Lecture schedule and notes

Assignments

Announcements

Presentation Schedule and Readings