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)
The design, implementation, and analysis of concurrent algorithms,
protocols, data structures, software components, and systems, on
computer architectures supporting parallelism and synchronization.
- Architectural support: Processor-level, multicore, and
cluster parallelism, shared memory and message passing;
associated programming constructs.
- Atomicity: Synchronization, locks, atomic operations, transactions.
- Asynchrony: Threads, processes, tasks.
- Coordination: Monitors, barriers, futures, messaging, scheduling.
- Data structures: Shared data stores and queues.
- Algorithmic strategies: Actors, parallel divide and conquer,
completions and streams.
- Analysis: safety, liveness, invariants, graph-based performance
models, empirical evaluation.
Upon completion of this course, students will demonstrate ability to:
- [Design] Choose among relevant design strategies to approach
problems; construct and use components that apply atomicity,
asynchrony, and coordination techniques for correct and efficient
- [Analysis] Determine safety, liveness, and parallel speedup
properties; recognize sequential vs parallel constructions;
empirically evaluate multiple solutions to a given problem.
- [Development] Incorporate covered techniques in concurrent and
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:
- Herlihy, Maurice, Nir Shavit,Victor Luchangco, Michael Spear. The Art of Multiprocessor
Programming, Elsevier, 2020.
book companion site.
- Goetz, Brian, et al. Java Concurrency in Practice.,
Addison-Wesley 2006. ISBN-13: 978-0321349606.
See also Book supplement site.
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
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.
- Assignment 1
- Assignment 2
- Choose: Game Search or
CS and College policies and resources pages provide more
- If you have a disabling condition, which may interfere with
your ability to successfully complete this course, please contact
the Office of Accessibility Services.
- SUNY Oswego is committed to enhancing the safety and security
of the campus for all its members. In support of this, faculty may
be required to report their knowledge of certain crimes or
harassment. Reportable incidents include harassment on the basis
of sex or gender prohibited by Title IX and crimes covered by the
Clery Act. For more information about Title IX protections contact
the Title IX Coordinator, 405 Culkin Hall, 315-312-5604,
email@example.com. For more information about the Clery Act and
campus reporting, see the University Police annual report.
- SUNY Oswego is committed to Intellectual Integrity. Any form
of intellectual dishonesty is a serious concern and therefore
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.
- Overview and terminology: safety, liveness, latency, throughput.
- Creating and running activities: Threads, Executors, Event handlers
- Shared Memory consistency: atomicity, happens-before
- Avoiding Data races: isolation, safe publication, ordered access modes
- Consensus: CompareAndSet, etc; ABA problems
- Locks: before/after idioms, deadlock; reentrance
- Count-based synchronization: semaphores, latches, barriers, phasers
- Condition Variables and their application
- Non-blocking stacks and queues; wait/lock/obstruction freedom; linearizability
- Concurrent data stores and collections; optimistic locking
- [mid-term approximately here]
- Performance measurement; read-mostly designs
- Other scalable data structures, transactions, and counters
- Parallel decomposition; data parallelism
- Bulk parallelism for data store operations
- Nested parallelism; parallel scan, sorting
- Parallel search, graph and tree problems and algorithms
- Iterative parallelism; grids; relaxation
- Parallel linear algebra; data analysis and learning
- Cluster and cloud computing; data distribution and coordination
- Cluster-based parallel execution frameworks
- GPGPU and special-purpose hardware parallelism
- Asynchronous messaging, IO and completions
- Language support; synchronous messaging, HPC languages