This course will examine the design and implementation of programming
languages and computing systems that support concurrency and
parallelism. We will focus on foundations. 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, we will discuss shared memory, message passing,
memory models, blocking and non-blocking forms of communication.
We will also spend a significant amount of time discussing concurrency
control models, and will introduce formal notions of serializability
and atomicity and how these notions manifest in real
languages. Quantifying overheads and performance
characteristics of parallel programs is also a subject we will
study. Some fraction of the course will be devoted to
implementation studies of threading systems and schedulers.
The second part of the course will apply these foundational principles
to derive concurrent data structures, non-blocking algorithms and
restructuring techniques from sequential programs to parallel ones, and
detailed case studies of language proposals and system designs.
Time permitting, we will discuss formal methods in concurrency
including process calculi, abstractions such as continuations,
dataflow, selective communication, and dependence analysis.
Requirements
Each lecture will
be assigned a scribe responsible for taking detailed lecture notes
available the following week. A series of small programming
projects, implementation of one large project (devised in consultation
with the instructors), and a final.