CMPSCI 691W - Parallel and Concurrent Programming

Professor Emery Berger
Meeting Time MW, 10:35am-11:50am
Course Number CMPSCI 691W
unique number: 58200
Room Number CS 142

For years, parallel programming advocates have been saying that someday we'd all have computers with multiple processors.
That day has finally arrived. Faced with the end of the Moore's Law ride of the last two decades, all of the major chip manufacturer have started producing CPUs with at least two cores, and some have announced plans for eight-core CPUs. Taking advantage of this processing power will be a major challenge in coming years.

In this course, we will examine parallel languages and libraries that let programmers take advantage of multiple processors or computers. We will also study concurrent programming techniques especially suitable for high-performance computing. Topics to be discussed include both explicitly and implicitly parallel programming languages, threads, message-passing, events, non-blocking synchronization, and transactions. Students will gain experience programming using these systems and will also do a research-oriented project.

Parallel languages to be examined will likely include Linda, NESL, and Cilk, as well as newer languages like X10 and Fortress. We will explore POSIX threads, MPI (message-passing), software transactional memory, SEDA (event-driven programming), and non-blocking synchronization in C and Java, among other topics. We will also discuss how to debug and reason about these programs.

 
Lecture   Slides / Notes   Scribed notes  Papers / Resources 
1 Introduction  Journal notes (PDF) Scribed by Jacob Sorber: PDF, source tarball
2 Processes & Threads  Slides (PDF) Scribed by Richard Chang: PDF, source tarball An Introduction to Programming with Threads (by Birrel)
LLNL pthreads tutorial
3 Advanced Synchronization  Slides (PDF) Scribed by Kevin Grimaldi: PDF Experience with Processes and Monitors in Mesa, Lampson and Redell
On the Duality of Operating Systems Structures, Lauer and Needham
4 Concurrency in Java  Slides (PDF) Scribed by Matt Marzilli: PDF, LaTeX source
Homework 1 - due February 27 (submit by e-mail)
5 Advanced Java Concurrency  Slides (PDF) Scribed by Dennis Gove: PDF, LaTeX source Sun's documentation for Java 1.5's concurrency utilities and the NIO libraries.
6 Server Architectures  Slides (PDF) Flash: An Efficient and Portable Web Server, Pai et al.
SEDA: An Architecture for Well-Conditioned, Scalable Internet Services, Welsh et al.
7 Alternative Server Architectures  Slides (PDF) Scribed by Shangzhu Wang: PDF Capriccio: Scalable Threads for Internet Services, von Behren et al.
Flux: A Language for Programming High-Performance Servers, Burns et al.
8 Dynamic Race Detection  Slides (PDF) Scribed by Vitaliy Lvin: PDF Eraser: A Dynamic Data Race Detector for Multithreaded Programs (by Savage et al.)
9 Atomicity  Slides (PDF) Scribed by Heather Conboy: PDF, source tarball Atomizer: A Dynamic Atomicity Checker for Multithreaded Programs (by Flanagan and Freund)
Homework 2 - due March 29 (submit by e-mail)
interposition example
intro to C++
10 Cilk  Slides (PDF) Scribed by John Burgess: PDF, LaTeX The Implementation of the Cilk-5 Multithreaded Language (by Frigo, Lesierson, and Randall)
Cilk reference manual
11 Multiprogramming  Slides (PDF) Scribed by Ed Walters: PDF The Performance of Work Stealing in Multiprogrammed Environments (Blumofe and Papadopoulos)
Thread Scheduling for Multiprogrammed Multiprocessors (Arora, Blumofe and Plaxton)
Homework 3 - due April 17 (submit by e-mail)
12 MPI I Slides (PDF) Scribed by Alex Epshteyn: PDF MPICH2 User's Guide
13 MPI II: Collective Communication Slides (PDF) Scribed by Ting Yang: PDF
14 OpenMP Slides (PDF) OpenMP Spec
15 ZPL Slides (PDF) ZPL programming guide
ZPL Improves Productivity and Performance (by Chamberlain et al.)
ZPL Overview (Chamberlain's thesis, Chapter 2)
The ZPL Approach
Parallel Languages
Atomos Slides (PPT) Presented by Dennis Gove and Matt Marzilli
Erlang Slides (PPT) Presented by Heather Conboy and Shangzhu Wang
occam Slides (PPT) Presented by Vitaliy Lvin and Alex Epshteyn occam reference manual
MultiLisp Slides (PPT) Presented by Ed Walters and Tim Richards
pH Slides (PPT) Presented by Jim Cipar and Jacob Sorber
X10 Slides (PPT) Presented by Paul Kohler and Kevin Grimaldi
Fortress Slides (PPT) Presented by Richard Chang and John Burgess
Chapel Slides (PPT) Presented by Ting Yang

 

Papers:

Shared Memory Consistency Models (by Adve and Gharachorloo)
Type-based race detection for Java (by Flanagan and Freund)
NesC
Object race detection (by von Praun and Gross)

 

Resources:

scribe notes template (LaTeX)
SEDA source code
ZPL source code
NesC source code

This course material is Copyright (C) 2006 by Emery Berger and may not be used without prior written permission.