CSC375

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

• [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

• 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.

• 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

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:

• 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

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