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