Principles and practice of multiprocessor prgramming. Illustration of multiprocessor programming principles through the classical multual exclusion problem, correctness properties of concurrency (e.g., linearizability), shared memory properties (e.g., register constructions), and synchronization primities for implementing concurrent data structures (e.g., consensus protocols). Illustration of multiprocessor programming practice through programming patterns such as spin locks, monitor locks, the work-stealing paradigm, and barriers. Discussion of concurrent data structures (e.g., concurrent linked lists, queues, stacks, hash maps, skiplists) through synchronization patterns ranging from coarse-grained locking to fine-grained locking to lock-free structures, atomic synchronization primities, elimination, and transactional memory.
The computer industry is undergoing a paradigm shift, as chip manufactures are increasingly investing in, and manufacturing a new generation of multi-processor ships called multicores, as it is becoming increasingly difficult to enhance clock speeds by packing more transistors in the same chip without increasing power consumption and overheating. Consequently, application software performance can no longer be improved by simply relying on increased clock speeds of single processors; software must explicity be written to exploit the hardware parallelism of multiprocessors. Programming multi-processors is fundamentally different from programming single-processors, due to the need to understand how concurrent computations on separate processors coordinate with one another, in contrast with understanding how concurrent computations on the same processor coordinate with one another. This is a complex and intricate problem, and requries new abstractions, algorithms, and programming tools, which are precisely the focus of the course.
Percentage of Course
|Introduction to shared objects and synchronization, and the mutual exclusion problem||5%|
|Correctness properties of concurrent programs (consistency, linearizability, progress, fairness, deadlock-freedom)||10%|
|Foundations of shared memory (register constructions, atomic snapshots)||10%|
|Synchronization operations for concurrent data structures (atomic registers, consensus protocols, FIFO queues, universality of consensus)||15%|
|Programming patterns: Spin locks and contention, monitor locks and waiting, work-stealing and parallelism, barriers||10%|
|Concurrent data structures (concurrent linked lists, concurrent queues, concurrent stacks, concurrent hash maps, concurrent skiplists)||20%|
|Synchronization patterns: coarse-grained locking, fine-grained locking, optimistic locking, lazy synchronization, non-blocking synchronization||15%|
|Atomic synchronization primities, elimination, parallel search||10%|