COSC 273: Parallel and Distributed Computing
course materials for Spring 2023
Welcome to the Spring 2023 edition of COSC 273: Parallel and Distributed Computing. Course materials and assignments will be posted to this website. Please start by reading the course syllabus:
Coordinates
- Lecture: MWF 10:00–10:50 Science Center, A131
- Drop-in Office Hours (Science Center C216)
- MWF 11:00–11:30
- Will’s Office Hours by Appointment: sign up here
- Thursday 1:00–2:30
- TA Office Hours with Mary Kate (Science Center C109)
- Wednesday 7:00–9:00pm
Resources
Primary Text: The Art of Multiprocessor Programming (AMP) by Herlihy et al. (required reading)
Other Resources
- Java Concurrency in Practice by Goetz et al. (occasional suggested reading)
- Java 19 API Documentation (exhaustive documentation for Java)
- Amherst College HPC Cluster Documentation (requires VPN if you’re off campus)
Lecture Materials
In readings below, AMP refers to The Art of Multiprocessor Programming.
Week 01 (01/30 - 02/03)
- Lecture 01 (Monday, 01/30)
- Topics: course introduction; introduction to parallelism
- Readings: course syllabus
- lecture 01 slides (annotated pdf)
- Lecture 02 (Wednesday, 02/01)
- Topics: multithreading in Java
- Readings: multithreading notes
- Examples: lec02-shared-counter.zip
- lecture 02 slides ((annotated pdf))
- Lecture 03 (Friday, 02/03)
- Topics: RAM and PRAM models, reasoning about multithreaded programs
- Activity:
- what are possible outcomes?
- lecture 03 slides ((annotated pdf))
Week 02 (02/06 - 02/10)
- Lecture 04 (Wednesday, 02/08)
- Topics: Embarrassingly parallel tasks and limitations
- Readings:
- AMP Section 1.5 The Harsh Realities of Parallelization
- AMP Section 1.6 Parallel Programming
- Monte Carlo Simulation
- Activity:
- Lecture 03 Activity (complete before class)
- lecture 04 slides (annotated pdf)
- Lecture 05 (Friday, 02/10)
- Topics: Amdahl’s Law and Locks
- Readings:
- none!
- Activity:
- lecture 05 slides (annotated pdf)
- Programming Assignment 01 (Due Friday, 02/10)
Week 03 (02/13 - 02/17)
- Lecture 06 (Monday 02/13)
- Topics: mutual exclusion and locks
- Readings:
- AMP Section 1.1 Shared Objects and Synchronization
- AMP Section 1.2 A Fable
- Activity:
- lecture 06 slides (annotated pdf)
Lecture 07 (Wednesday 02/15)Lecture Canceled :/- Topics: more mutual exclusion
- Readings:
- AMP Sections 2.1 through 2.3 (mutual exclusion)
- Activity:
- Lecture 07 (Friday 02/17)
- Topics: locality of reference
- Readings:
- Locality of Reference (from Wikipedia)
- The Locality Principle by Denning (optional)
- Activity (laptop required):
- lecture 07 slides (annotated pdf)
- Homework 01 (pdf), .tex source
Week 04 (02/20 - 02/24)
- Lecture 08 (Monday 02/20)
- Topics:
- locality of reference
- computing shortcuts
- using the HPC cluster
- Readings: Lab 02: Computing Shortcuts description
- Lecture 08 Slides (annotated pdf)
- Topics:
- Lecture 09 (Wednesday 02/22)
- Topics:
- Mutual Exclusion and Peterson Locks
- Lecture 09 Slides (annotated pdf)
- Topics:
- Lecture 10 (Friday 02/24)
- Topics:
- Lamport’s Bakery Algorithm
- Lecture 10 Slides (annotated pdf)
- Topics:
- Lab 02: Computing Shortcuts (Due Friday, 02/24)
Week 05 (02/27 - 03/03)
- Lecture 11 (Monday 02/27)
- Topics: Finishing Mutual Exclusion
- Readings: AMP 2.8 Lower Bounds on the Number of Locations
- Lecture 11 Slides (annotated pdf)
- Lecture 12 (Wednesday 03/01)
- Topics: SIMD Parallelism and Vector Operations
- Lecture 12 Slides (annotated pdf)
- Lecture 13 (Friday, 03/03)
- Topics: More
Vectors in Java, Masking - Readings:
- Demo:
hamming-weight.zip - Lecture 13 Slides (annotated pdf)
- Topics: More
- Homework 02 (pdf), .tex source (Due
Friday, 03/03Friday, 03/10)
Week 06 (03/06 - 03/10)
- Lecture 14 (Monday, 03/06)
- Topic: The Mandelbrot Set
- Activity: Points in the Mandelbrot Set
- Lecture 14 Slides (annotated pdf)
- Lecture 15 (Monday, 03/08)
- Topics: More Mandelbrot Set and Thread Pools
- Reading: Mandelbrot Set from Complex Analysis by Juan Carlos Ponce Campuzano
- Demos:
- Lecture 15 Slides (annotated pdf)
- Lecture 16 (Friday, 03/10)
- Topics: Thread Pools
- Readings:
- Demo:
- Lecture 16 Slides (annotated pdf)
Week 07 (03/20 - 03/24)
- Lecture 17 (Monday, 03/20)
- Topic: Introduction to Concurrent Objects
- Readings: None!
- Lecture 17 Slides (annotated pdf)
- Lecture 18 (Wednesday, 03/22)
- Topic: Sequential Consistency
- Readings: AMP 3.1–2, Concurrency and Correctness and Sequential Objects
- Lecture 18 Slides (annotated pdf)
- Lecture 19 (Friday, 03/24)
- Topic: Mandelbrot and Sequential Consistency
- Readings AMP 3.3 Sequential Consistency
- Lecture 19 Slides (annotated pdf)
- Lab 03: Mandelbrot Set (Due
Friday, 03/24Monday, 03/27)
Week 08 (03/27 - 03/31)
- Lecture 20 (Monday, 03/27)
- Topic: Linearizability
- Lecture 20 Slides (annotated pdf)
- Lecture 21 (Wednesday, 03/29)
- Topic: More Linearizability
- Lecture 21 Slides (annotated pdf)
- Lecture 22: (Friday, 03/31)
- Topic: A Linearizable Queue with Locks
- Lecture 22 Slides (annotated pdf)
Week 09 (04/03 - 04/07)
- Lecture 23 (Monday, 04/03)
- Topic: A Lock-free Queue, Blocking and Non-blocking Progress
- Demo:
concurrent-queues.zip - Lecture 23 Slides (annotated pdf)
- Lecture 24 (Wednesday, 04/05)
- Topic: Lock Implementations I
- Demo:
peterson-lock.zip - Readings: AMP Sections 7.1–3
- Lecture 24 Slides (annotated pdf)
- Lecture 25 (Friday, 04/07)
- Topic: Lock Implementations II
- Readings: AMP Sections 7.4–5
- Quiz 02: Predict the performance!
- Demo:
tas-locks.zip - Lecture 25 Slides (annotated pdf)
Week 10 (04/10 - 04/14)
- Lecture 26 (Monday, 04/10)
- Topic: Finishing Lock Implementations
- Demo:
clh-lock.zip - Lecture 26 Slides (annotated pdf)
- Lecture 27 (Wednesday, 04/12)
- Topic: Computing Primes
- Activity:
prime-activity.pdf - Lecture 27 Slides (annotated pdf)
- Lecture 28 (Friday, 04/14)
- Topic: Parallel Sorting
- Lecture 28 Slides (annotated pdf)
Week 11 (04/17 - 04/21)
- Lecture 29 (Wednesday, 04/19)
- Topic: Fork-join Pools
- Optional reading: AMP Chapter 16, Scheduling and work distribution
- Documentation:
- Activity
- Lecture 29 Slides (annotated pdf)
- Lecture 30 (Friday, 04/21)
- Topic: Sorting Networks
- Reading: AMP Sections 12.7–8, Parallel Sorting and Sorting Networks
- Further Reading and Documentation:
- Demo:
sorting-networks.zip - Lecture 30 Slides (annotated pdf)
Week 12 (04/24 - 04/28)
- Lecture 31 (Monday, 04/24)
- Topic: concurrent linked lists; optimistic synchronization
- Relevant readings: AMP Section 9.1–9.6
- Demo:
linked-lists.zip - Lecture 31 Slides (annotated pdf)
- Lecture 32 (Wednesday, 04/26)
- Topic: lazy list synchronization
- Relevant readings: AMP Section 9.7
- Demo:
linked-lists.zip(annotated pdf) - Lecture 32 Slides
- Quiz on Linked Lists Released (take-home)
- Lecture 33 (Friday, 04/28)
- Topic: nonblocking list synchronization
- Relevant readings: AMP Section 9.8
- Demo:
linked-lists.zip - Quiz on Linked Lists due (submission on Gradescope)
- Lecture 33 Slides (annotated pdf)
Week 13 (05/01 - 05/09)
- Lecture 34 (Monday, 05/01)
- Topic: Thread Pools and Future, Introduction to Consensus
- Readings:
- Activity:
lec34-futures.zip- edited solution:
lec34-futures-edited.zip
- edited solution:
- Lecture 34 Slides
- Lecture 35 (Wednesday, 05/03)
- Topic: Consensus
- Lecture 35 Slides
- Lecture 36 (Friday, 05/05)
- Topic: More on Consensus
- Lecture 36 Slides
- Lecture 37 (Monday, 05/08)
- Topic: Closing Thoughts
- Lecture 37 Slides
Assignments
Programming Assignments
- 01: Estimating Pi (Due Friday, 02/10)
- 02: Computing Shortcuts (Due Friday, 02/24)
- 03: Mandelbrot Set (Due
Friday, 03/24Monday, 03/27)
Written Assignments
- Homework 01 (pdf), .tex source (Due Friday, 02/17)
- Homework 02 (pdf), .tex source (Due
Friday, 03/03Friday, 03/10) - Homework 03 (pdf) (Due Friday, 04/14)
Quizzes
- Quiz 01 (Friday, 03/31)
- Quiz 02 (Friday, 04/07)
- Quiz 03 (Friday, 04/21)
- Quiz 04 (Friday, 04/28)
- Quiz 05 (Friday, 05/05)
Final Project
- Final Project Description
- Group Selection (due Friday, 04/14)
- Leaderboard Submissions
- Friday 04/21
- Friday 04/28
- Friday 05/05
- Final Submission (due Tuesday, 05/09 by 5:00pm)