CSC375

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

Overview

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

Topics

Outcomes

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

Readings

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:

Requirements

Subject to minor change:
Two exams (final exam is take-home-style) (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:

Lectures

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. Count-based synchronization: semaphores, latches, barriers, phasers
  8. Condition Variables and their application
  9. Non-blocking stacks and queues; wait/lock/obstruction freedom; linearizability
  10. Concurrent data stores and collections; optimistic locking
  11. [mid-term approximately here]
  12. Performance measurement; read-mostly designs
  13. Other scalable data structures, transactions, and counters
  14. Parallel decomposition; data parallelism
  15. Bulk parallelism for data store operations
  16. Nested parallelism; parallel scan, sorting
  17. Parallel search, graph and tree problems and algorithms
  18. Iterative parallelism; grids; relaxation
  19. Parallel linear algebra; data analysis and learning
  20. Cluster and cloud computing; data distribution and coordination
  21. Cluster-based parallel execution frameworks
  22. GPGPU and special-purpose hardware parallelism
  23. Asynchronous messaging, IO and completions
  24. Language support; synchronous messaging, HPC languages
Doug Lea