Revised May 27, 2014
CS 343: Concurrent and Parallel Programming
Watch a video introduction to this course on YouTube.
This course introduces advanced control-structures with an emphasis on concurrency and writing concurrent programs at the programming-language level. Programming techniques and styles are examined to express complex forms of control flow, such as multi-level loop exit, exceptions, coroutines, and concurrency.
Logistics
Audience
- CS major students planning to do advanced programming
- Required for SE majors
Normally available
- Fall and Winter
Related courses
- Pre-requisites: CS 350 or SE 350
For official details, see the UW calendar.
Software
- UNIX, C++
Typical reference(s)
- Course notes
Required preparation
At the start of the course, students should be able to
- Recognize programs written using iteration and recursion
- Write advanced imperative programs using arrays and lists for a mutable memory model
- Use advanced object-oriented programming features in C++ including inheritance, templates, and separate compilation
Learning objectives
At the end of the course, students should be able to
- Explain complex forms of control flow at a fundamental level
- Select appropriate forms of control flow for a given problem
- Synthesize algorithms and use patterns involving multiple threads
- Compose and debug medium-sized programs involving exceptions, coroutines, and concurrency
Typical syllabus
Advanced control flow (3 hours)
- Multi-exit loops, multi-level exits, exceptions (termination/resumption)
Coroutines (4 hours)
- Multiple stacks, context switching
- Semi and full coroutines
Concurrency (3 hours)
- Threading models, concurrent systems, speedup
- Ready queue, thread states, interrupts
- Start, synchronize, and communicate among threads
Mutual exclusion (4 hours)
- Software and hardware solutions for critical sections
- Atomic data structures
Locks (4 hours)
- Spinning and blocking locks and implementations
- Basic lock, binary and counting semaphore, barrier
- Lock programming: baton passing and split binary semaphores
- Bounded buffer and readers/writer problems
Concurrency errors (3 hours)
- Race condition, starvation, live-lock, synchronization and mutual exclusion deadlock
- Examine deadlock prevention, avoidance and recovery
High-level concurrency (8 hours)
- Conditional critical regions, monitors, tasks
- Internal and external synchronization in mutex objects
- Rendezvous, futures and client/server
Other concurrency approaches (3 hours)
- Concurrent programming languages: Ada, Java, Go, Actors, Linda, OpenMP, pthreads, C++11
Optimization (2 hours)
- Sequential and concurrent execution models
- Corruption: memory, cache, registers, execution order
Distributed environments (2 hours)
- Distributed communication: sockets
- Message-passing, MPI
- Remote procedure/method call