Multiprocessor Programming

Principle and practice of multiprocessor programming. Illustration of multiprocessor programming principles through the classical mutual exclusion problem, correctness properties of concurrency (e.g., linearizability), shared memory properties (e.g. register constructions), and synchronization primitives 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 primitives, elimination, and transactional memory. Pre-requisite: Graduate Standing required