Instructor: Doug Lea
Class: T-Th 8:00
Office/Lab hours. T-W-Th 11-12am (or send mail to set up another time)
Prereqs: CSC241 (365 strongly encouraged) and CSC322 (or 222)


The design, implementation, and analysis of concurrent algorithms, protocols, data structures, software components, and systems, on computer architectures supporting parallelism and synchronization.



Upon completion of this course, students will demonstrate ability to:


The course does not follow these books in sequence, but they provide additional background and coverage that will be assigned as needed. Other recommended online readings include:


Subject to minor change:
Two exams (35%)
Exam questions cover the design and theory of operation of concurrent components and algorithms, as well as analysis in terms of safety, liveness, efficiency, and appropriateness for a given problem.
3-4 programming assignments (if 3, the third has multiple parts) (65%)
Projects entail specialized versions of covered techniques and components in support of concurrent applications. At least one project entails systematic performance evaluation, and at least one requires modeling a concurrent system. Programs may not be submitted unless they successfully run according to specification. You must demo your program to me within 2 days of submitting it. Five percent credit is taken off per day late.

As a substitute for live demos, you may alternatively send e-mail a zip/tar including your program source with screenshots or remote screenshare of successful operation with a brief (approx one-page) design and experience account of your approach and how it changed over time. (This may be embedded as main program documentation.) If you maintain commit logs or time logs every time you work on project, a lightly edited collection of these should suffice. I may send follow-up questions before accepting.

  1. Assignment 1
  2. Assignment 2
  3. Choose: Game Search or Heat propagation.

Campus references

The CS and College policies and resources pages provide more information about:


Here are the targeted topics for lectures, not including classes for review, exams, or coverage of project-specific applications. Topics don't always fit exactly into class times, so these don't always exactly correspond to dates.
  1. Overview and terminology: safety, liveness, latency, throughput.
  2. Creating and running activities: Threads, Executors, Event handlers
  3. Shared Memory consistency: atomicity, happens-before
  4. Avoiding Data races: isolation, safe publication, ordered access modes
  5. Consensus: CompareAndSet, etc; ABA problems
  6. Locks: before/after idioms, deadlock; reentrance
  7. Barriers, latches, and phasers
  8. Semaphores and related blocking resource control
  9. Condition Variables, Monitors, and their application
  10. Non-blocking stacks and queues; wait/lock/obstruction freedom; linearizability
  11. Concurrent data stores and collections; optimistic locking
  12. [mid-term approximately here]
  13. Performance measurement; read-mostly designs
  14. Other scalable data structures, transactions, and counters
  15. Parallel decomposition; data parallelism
  16. Bulk parallelism for data store operations
  17. Nested parallelism; parallel scan, sorting
  18. Parallel search, graph and tree problems and algorithms
  19. Iterative parallelism; grids; relaxation
  20. Parallel linear algebra; data analysis and learning
  21. Cluster and cloud computing; data distribution and coordination
  22. Cluster-based parallel execution frameworks
  23. GPGPU and special-purpose hardware parallelism
  24. Asynchronous messaging, IO and completions
  25. Language support; synchronous messaging, HPC languages
Doug Lea