CSC 2/458

Parallel and Distributed Systems

Spring 2019.

Course Schedule (evolving)

Note:  assigned reading must be completed before class. 
Also: most of the links to readings work only from UR IP addresses; if you’re off campus, you’ll need to extablish a VPN connection before you can follow them. 

Wed. 16 Jan.
First day of class.
Overview, intro (notes).
Mon. 21 Jan.
Martin Luther King, Jr. day; no class.
Wed. 23 Jan.
More overview; the multicore revolution.
To be read before class today:  (1) article by Sutter & Larus; (2) chapter 1 of Shared Memory Synchronization.*
Due before class today: assignment 0
Mon. 28 Jan.
Threads in C and C++. 
To be read before class today:  (1) C++11 threading tutorial (e.g., this one—read it carefully) and (2) Lawrence Livermore pthreads tutorial (skim this). 
Also, if you haven’t taken CSC 2/454 at Rochester, read (3) PLP sections 9.5 & 13.1–13.2.*  (If you have taken the course, you might still want to review the material :-) 
Wed. 30 Jan.
Snooping cache coherence (notes, diagrams).
To be read before class today:  (1) chapter 2 of Shared Memory Synchronization* and (2) Section 5.4* of Parallel Computer Organization and Design, by Dubois, Annavaram, and Stenström. 
Mon. 4 Feb.
Memory consistency models.
To be read before class today:  Adve & Gharachorloo.* 
Due last night: assignment 1
Wed. 6 Feb.
Memory consistency models (continued).
You may want to skim Section 3.4 of Shared Memory Synchronization,* but be warned that it oversimplifies.  Specifically:  it fails to introduce the “sequenced with” relation described in the lecture notes.  It then erroneously defines happens-before as the transitive closure of program order and synchronized-with; it should define happens-before as the (non-transitive) union of program order and the transitive closure of sequenced-with and synchronized-with.  (I will be fixing this in a subsequent revision.) 
Mon. 11 Feb.
Spin locks (notes).
To be read before class today:  chapter 4 of Shared Memory Synchronization.* 
Wed. 13 Feb.
Busy-wait condition synchronization.
To be read before class today:  chapter 5 of Shared Memory Synchronization.*  and Lock Cohorting, by Dice, Marathe, and Shavit.  (For more details, see the longer journal version of this paper.)
Mon. 18 Feb.
Prof. Scott out of town; guest lecture by Prof. Yuhao Zhu:  “Beyond Parallelism: Architectural Specialization and Customization.”
To be read before class today:  Understanding Sources of Inefficiency in General-Purpose Chips, by Hameed et al.
and Dark Silicon and the End of Multicore Scaling, by Esmaeilzadeh et al. 
Due last night: assignment 2
Wed. 20 Feb.
Prof. Scott out of town; guest lecture by Prof. Chen Ding:  “Compilation for Data Parallelism.”
To be read before class today:  Section 2.2 and Chapter 14 of Optimizing Compilers for Modern Architectures,* by Allen and Kennedy. 
Please also see Kennedy's lecture notes for Chapter 14, as well as the on-line errata for the text. 
Mon. 25 Feb.
Finish coverage of barriers.
New material: speedup (notes).
To be read before class today:  (1) Gustafson* (scaled speedup) and (2) Karp & Flatt* (serial fraction).
Wed. 27 Feb.
Read-mostly synchronization (notes).
To be read before class today:  (1) chapter 6 of Shared Memory Synchronization* and (2) McKenney's Structured Deferral
Mon. 4 Mar.
MPI (notes) and (if time permits) Map-Reduce (notes).
To be read before class today:  (1) Victor Eijkhout’s on-line MPI book: read chapter 1 and skim chapters 2–14 to get a sense of scope. 
Wed. 6 Mar.
Concurrency theory (notes).
To be read before class today:  chapter 3 of Shared Memory Synchronization.* 
(Fri. 8 Mar.)
Due by 5pm: assignment 3
 
(Mon. 11 Mar. and Wed. 13 Mar.)
Spring break; no class.
 
Mon. 18 Mar.
Guest lecture (remote) by Brad Chamberlain, Principal Engineer at Cray, Inc., and Technical Lead for the Chapel programming language.
Wed. 20 Mar.
Nonblocking data structures (notes).
To be read before class today:  (1) chapter 8 of Shared Memory Synchronization.* 
Due by end of day Saturday: semester project/presentation proposals
Mon. 25 Mar.
In-class presentation of proposals. 
Wed. 27 Mar.
(continued)
Mon. 1 Apr.
Presentation of final 2 project proposals; continued coverage of concurrency theory and nonblocking data structures.
Wed. 3 Apr.
Finish coverage of nonblocking data structures.
To be read before class today:  (1) Hendler et al. (flat combining) and (2) Morrison & Afek (LCRQs). 
Due by end of day Sunday: assignment 4
Mon. 8 Apr.
Time (notes).
To be read before class today:  Tanenbaum & van Steen, Sections 6.1–6.2.* 
Optional: Lamport’s classic “Time, Clocks, and the Ordering of Events in a Distributed System.” 
Wed. 10 Apr.
Software Distributed Shared Memory (notes).
To be read before class today:  Treadmarks and Cashmere.  In the latter, focus your attention on Sections 1, 2, 4.1, 5, and 6. 
Mon. 15 Apr.
Distributed Consensus (notes, slides).
To be read before class today: Coulouris et al. Sec. 15.5* and Henry Robinson’s blog on FLP impossibility
Wed. 17 Apr.
Paxos and Raft (notes).
To be read before class today: Henry Robinson’s blog on Paxos and the Raft paper
If you’re curious, take a peek at the original Paxos paper and/or Lamport’s Paxos Made Simple.
Mon. 22 Apr.
Transactions (notes).
To be read before class today: Coulouris et al. Chap. 16.* 
Wed. 24 Apr.
Transactional Memory (notes).
To be read before class today: chapter 9 of Shared Memory Synchronization.* 
Mon. 29 Apr.
Persistence (slides).
To be read before class today: Steve Swanson’s first and second blog posts on persistence.  Please also skim the Durable Linearizability paper. 
Please be sure to fill out your on-line course evaluation.
Wed. 1 May
Miscellaneous topics (notes).
No reading assignment.
Final projects due Sunday by end-of-day.

* Available from UR IP addresses only. 


Back to the course home page

Last Change:  01 May 2019 / Michael Scott's email address