CSC375 (original) (raw)

Instructor: Doug Lea
Class: T-Th 9:35
Office/Lab hours. T-W-Th 11-12:30am (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

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.

Outcomes

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 operation.
[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 parallel applications.

Readings

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

Herlihy, Maurice, Nir Shavit,Victor Luchangco, Michael Spear. The Art of Multiprocessor Programming, Elsevier, 2020. See also book companion site.
Goetz, Brian, et al. Java Concurrency in Practice., Addison-Wesley 2006. ISBN-13: 978-0321349606. See also Book supplement site. Other recommended online readings include:
ACM Curriculum
Using JDK 9 Memory Order Modes
Intro to High Performance Scientific Computation Vol 1,Vol 2 online text by Victor Eijkhout
SIMD design
sample code
Java Vector tutorial and guide, Another

Requirements

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.

Campus references

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

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, titleix@oswego.edu. 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 prohibited.

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.

Overview and terminology: declarative parallelism, 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; monotonicity, ABA problems
Locks: before/after idioms, deadlock; reentrance
Barriers, latches, and phasers
Semaphores and related blocking resource control
Condition Variables, Monitors, and their application
Blocking queues and reactive alternatives.
[mid-term approximately here]
Non-blocking stacks and queues; wait/lock/obstruction freedom; linearizability
Concurrent data stores and collections; optimistic locking
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

Doug Lea