Instructor | Pavol Cerny |
Lectures | TTh 5.00-6.15 in DUAN G2B47 |
Office hours | Wed 4-5pm in ECEE 120, and by appointment |
TA | Aniruddha Phatak email: aniruddha.phatak at colorado.edu |
Course Moodle site
Course schedule, slides, homework assignments, and project suggestions are on the Moodle site.Course description
This course focuses on the theory and practice of multicore programming. Our ability to effectively harness the computational power of the current and the next generation of multicore architectures is based on advances in programming languages and tools for developing concurrent software. The first part of the course presents foundations of concurrent programming: mutual exclusion, wait-free and lock-free synchronization, spin locks, monitors, memory consistency models. In the second part, we will see a sequence of concurrent data structures, and techniques used in their implementations (coarse-grained, fine-grained, optimistic, and lock-free synchronization).Course Topics
- Introduction: Mutual Exclusion, Concurrency in Java.
- Mutual Exclusion: Peterson's algorithm, Bakery Algorithm
- Reasoning about concurrency, Lower Bound for Mutual Exclusion
- Concurrency in Java: Java memory model; thread local variables.
- Foundations of Shared Memory Concurrent Programming
- Case Study: Concurrent Lists
- Correctness of Concurrent Objects; Linearizabillity
- Power of Synchronization Operations
- Concurrent Registers
- Practical Synchronization Algorithms.
- Spin Locks.
- Monitors and Blocking Synchronization.
- Concurrent Data Structures.
- Concurrent Queues and the ABA problem
- Concurrent Stacks and Elimination
- Concurrent Hashing and Natural Parallelism
- Advanced Topics.
- Futures, Scheduling, and Work Distribution.
- Transactional Memory.
Note: Slides are available on Moodle.
Course project
The goal of your project is to write a larger concurrent program, and test its performance. Performance study will be an integral part of the project: if applicable, compare the performance of different versions of your program (sequential, naive concurrent data structures, optimized concurrent data structures). Perhaps a different version will work best for different various inputs, workloads, and environments. Work on your own or in pairs.Note: Project suggestions are available on Moodle.
Preliminary project deadlines:
- February 24: project proposal (2 pages)
- March 24: checkpoint (project works on motivating examples, performance testing can begin (4 pages))
- May 1: project submission deadline (submit source code, examples, project report (6 pages))
- week of May 1: project presentations, demos
Tests
Preliminary test dates.- February 16: Test 1
- March 21: Test 2
- April 27: Test 3
Textbook
- The Art of Multiprocessor Programming by Maurice Herlihy and Nir Shavit. Required.