CS 390: Principles of Concurrency and Parallelism

Handout 1:                                                                       January 9, 2012



Prof. Suresh Jagannathan
Room 3154J
Lawson Computer Science Building
Ph: x4-0971


Office Hours:

Tu, Th. 11- 12


This course will examine the design and implementation of programming languages and computing systems that support concurrency and parallelism with a focus on foundations and principles. It will be broadly partitioned into four units. First, we will investigate techniques used to describe concurrency such as threads, events, coroutines, etc., as well as mechanisms that enforce a specific interaction and coordination model among concurrently executing tasks. Here, concurrency is viewed primarily as a program structuring device. We will also introduce concepts and mechanisms for describing and reasoning about correctness such as data races, linearizability, deadlocks, livelocks, and serializability. While concurrency is introduced as a program structuring device, parallelism is motivated as a mechanism to improve performance. In this context, there will be discussion on cost models, notions of speedup and efficiency, and tradeoffs between concurrency, latency and throughput.

Second, abstractions used in modern concurrent and parallel languages are introduced, and broadly classified as either message- or shared-memory based. For the former, we introduce the basic concepts in languages like Erlang and libraries like MPI. In this process, we examine differences between synchronous (asynchronous) and (un)buffered communication. For the latter, thread programming using libraries like Posix, Cilk, and OpenMP will be introduced. You will also given the opportunity to program simple MapReduce applications to understand data parallelism, and will get some exposue to OpenCL and Cuda for GPU programming.

The third part of the course introduces various parallel data structures and algorithms. We consider a number of basic parallel algorithms over concurrent variants of representative data structures such as stacks, queues, matrices, trees, lists, hash tables, and graphs. Parallel sorting and searching algorithms over these structures are presented as representative examples, along with a detailed examination of their run-time complexity.

Finally, there will be a short introduction to processor architectures as it relates to foundational concerns related to parallelism. This includes a lecture devoted to weak memory models (e.g., relaxed consistency, Total Store Order), and emerging trends in parallel hardware, with specific emphasis on GPGPUs.


Each lecture will be assigned a scribe responsible for taking detailed lecture notes available the following week. A series of small programming projects will be assigned, and there will be a midterm and a cumulative final.


Scribe                20%
Programming Assignments     30%
Midterm             20%
Final                   30%


Lecture 1:   Introduction and Course Overview. Scribe.
Lecture 2:   Coroutines. Scribe.
Lecture 3:   Threads and Events. Scribe.
Lecture 4:   Message-Passing and CSP.Scribe.
Lecture 5:   Erlang.Scribe 1. Scribe 2.
Lecture 6:   Posix Threads. Scribe 1. Scribe 2. Scribe 3.
Lecture 7:   Mutual Exclusion. Scribe 1. Scribe 2.
Lecture 8:   Spin Locks and Low-Level Atomics. Scribe 1. Scribe 2.
Lecture 9:   Lock-free Data Structures. Scribe 1. Scribe 2.
Lecture 10:   Tasks and Work-Stealing. Scribe.
Lecture 11:   Data Races. Scribe.


Programming with Coroutines. Due Date: January 31, 2012. Solution

Erlang . Due Date: February 16, 2012. Solution

Posix threads . Due Date: March 1, 2012.

Lock-free data structures . Due Date: April 10, 2012.

Data race detection . Due Date: April 26, 2012.


  1. Essentials of Programming Languages, Frideman and Wand, (2008)
  2. Continuation-based Multiprocessing, Wand, (1980)
  3. Continuations and Threads: Expressing Machine Concurrency Directly in Advanced Languages, Shivers (1997)
  4. Continuations and Concurrency, Hieb and Dybig (1990)
Threads and Events
  1. Why Threads are a Bad Idea (for most purposes), Ousterhout (1996)
  2. Cooperative Task Management without Manual Stack Management, Adya, Howell, Theimer, Bolosky and Douceur (2002)
  3. Why Events are a Bad Idea (for high-concurrency servers), von Behren, Condit, and Brewer (2003)
Message-Passing and Erlang
  1. Communicating Sequential Processes, Hoare (1978)
  2. Concurrent Programming in Erlang Armstrong et. al (1996)
Shared-Memory Programming and Posix
  1. Posix Threads Tutorial
  2. Amdhal's Law in the Multicore Erra Hill and Marty (2008)
  3. Monitors: An Operating Systems Structuring Concept Hoare (1974)
Mutual Exclusion and Locking
  1. Art of Multiprocessor Programming (slides) (2009)
Scheduling and Work-Stealing
  1. Cilk 5.4.6 Reference Manual
  2. Implementation of the Cilk-5 Multithreaded Language
  3. Intel TBB
Data Races
  1. Eraser: A Dynamic Data Race Detector for Multithreaded Programsl
  2. FastTrack: Efficient and Precise Dynamic Race Detectione
  3. Learning from Mistakes - A Comprehensive Study on Real-World Concurrency Bugs