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.
Requirements
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.
Grading
Scribe 20%
Programming Assignments 30%
Midterm 20%
Final 30%