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