CSC 2/458

Parallel and Distributed Systems

Course Schedule

Please note that some readings (those with ur_only in their URL) are only accessible from a UR domain. Also, the schedule below will evolve through the semester. The schedule from a prior instantiation of the course is left in place to give you a sense of what is to come.
Wed. 12 Jan.
First day of class
Overview, intro Lecture 1
Readings/references: Chapter 1 of Culler and Singh as well as van Steen and Tanenbaum (both available online --- see the links on blackboard or the course main web page)
Wed. 19 Jan.
Basics of Parallelization: dependences Lecture 2
Readings/references: Chapter 3 of Grama, Karypis, Kumar, and Gupta (Chapters 2 and 3 of Culler and Singh may also be helpful)
Mon. 24 Jan.
Basics of Parallelization (continued): patterns of parallelism: data parallelism Lecture 3
Readings/references: Chapter 3 of Grama, Karypis, Kumar, and Gupta (Chapters 2 and 3 of Culler and Singh may also be helpful)
Wed. 26 Jan.
Basics of Parallelization (continued): patterns of parallelism: task parallelism, performance metrics, performance and practical considerations Lecture 4
Readings/references: Chapter 3 of Grama, Karypis, Kumar, and Gupta (Chapters 2 and 3 of Culler and Singh may also be helpful)
Mon. 31 Jan.
Practical considerations for performance; performance metrics; pthreads:thread creation and synchronization (mutual exclusion, events)
Slides from Lectures
Modeling speedup: Readings/references: Gustafson, Karp & Flatt;
Amdahl's Law in the Multicore Era
Additional reading relevant to analysis of your project results: Crowl
pthreads Tutorial
Wed. 2 Feb.
Thread creation; Thread implementation
Slides from Lectures
Parallel language constructs: Readings/references: PLP Section 12.2;
Language/library tutorials: Cilk Plus Tutorial
Intel's Threaded Building Blocks (TBB)
OpenMP
The Performance Implications of Thread Management Alternatives for Shared-Memory Multiprocessors, T. J. Anderson, E. D. Lazowska, and H. M. Levy, IEEE Transactions on Computers, 38 (12), December 1989.
Mon. 7 Feb.
Shared Memory: coherence: symmetric multiprocessors, basic write-back snoop-based protocol for coherence.
Reading: Chapter 5, Sections 6.1-6.2 of Culler and Singh
Slides from Lectures
Shared Memory: Synchronization: hardware support for synchronization
Slides from Lectures
Reading: Section 5.5 of Culler and Singh
Wed. 9 Feb.
Message passing (MPI), MPI Tutorial
Mon. 14 Feb.
Scalable software-based synchronization algorithms (spinlocks and barriers) - student presentation: Henry Moncure and Pavlo Pastaryev
Algorithms for Scalable Synchronization on Shared Memory Multiprocessors, John Mellor-Crummey and Michael L. Scott, ACM Transactions on Computer Systems, 9(1):21-65, February 1991 (2006 Dijkstra award).
Chapters 4 and 5 of Shared-Memory Synchronization
Wed. 16 Feb.
Shared Memory: hardware support for synchronization, synchronization algorithms, coherence protocols continued; implementation complexity, scale issues
Slides from Lectures
Reading: Chapter 5, Sections 6.1-6.2 of Culler and Singh
Reading: Sections 8.1-8.3 of Culler and Singh
Chapters 4 and 5 of Shared-Memory Synchronization
Slides from Lectures
Mon. 21 Feb.
Shared Memory: directory-based coherence protocols; interconnect topologies
Slides from Lectures
An Introduction to Interconnection Networks
Reading: Chapter 5, Sections 6.1-6.2 of Culler and Singh
Reading: Sections 8.1-8.3 of Culler and Singh
Wed. 23 Feb.
Shared Memory: Consistency Models
Shared Memory Consistency Models: A Tutorial, Sarita Adve and Kourosh Gharachorloo, Rice TR 9512, Compaq-DEC TR WRL-97-7, also appeared in IEEE Computer, December 1996.
Slides from Lectures

---------------------------------------
Mon. 28 Feb.
Consistency models (continued); Distributed systems: Physical clocks
Lecture slides
Reading: Sections 5.1 and 5.2 of Tanenbaum and van Steen
Efficient at-most-once messages based on synchronized clocks, Liskov, Shrira, and Wroclawski, ACM TOCS, May 1991.
Wed. 2 Mar.
Distributed systems: Physical and logical clocks
Reading: Sections 5.1 and 5.2 of Tanenbaum and van Steen
------------------------------------
Mon. 14 Mar.
Term project discussions

Wed. 16 Mar.
Distributed systems: global state, mutual exclusion, election algorithms
Reading: Sections 5.3-5.5 of Tanenbaum and van Steen
Lecture slides
"Distributed Systems: Concepts and Design", third edition, George Coulouris, Jean Dollimore, and Tim Kindberg, Chapters 10 and 11
Replication and Consistency in Distributed Systems
Background reading: Chapter 7, Distributed Systems by van Steen and Tanenbaum

Mon. 21 Mar.
Consistency models from a programmer's perspective (student presentation: Beakal Lemeneh and Zeyu Xu)
Class Slides
Readings/references: Threads Cannot be Implemented as a Library, Hans-J. Boehm, in Proceedings of the Conference on Programming Language Design and Implementation (PLDI), June 2005.
Memory Model for Multithreaded C++ Alexander Alexandrescu, Hans Boehm, Kevlin Henney, Doug Lea, and Bill Pugh, 2004.
C++11 atomics and memory order
Additional readings: Position Paper: Nondeterminism is unavoidable, but data races are pure evil, Hans-J. Boehm, RACES 2012, HP Tech. Report Version
How to miscompile programs with benign data races
Wed. 23 Mar.
Using logical clocks (student presentation: Shreyan Goswami): Implementing shared memory in software on distributed systems
TreadMarks: Shared Memory Computing on Networks of Workstations, A. Amza, A. L. Cox, S. Dwarkadas, P. Keleher, H. Lu, R. Rajamony, W. Yu, and W. Zwaenepoel, IEEE Computer, February 1996.
TreadMarks: Distributed Shared Memory on Standard Workstations and Operating Systems, with A.L. Cox, P. Keleher, and W. Zwaenepoel, Proceedings of the Winter 94 Usenix Conference, pp. 115-131, January 1994.
Cashmere-2L: Software Coherent Shared Memory on a Clustered Remote-Write Network, R. Stets, S. Dwarkadas, N. Hardavellas, G. Hunt, L. Kontothanassis, S. Parthasarathy, and M. L. Scott, Symposium on Operating Systems Principles, October 1997.
Mon. 28 Mar.
Coherence implementation issues (student presentation: Alex Bowman and Andrew Hahn)
Class Slides
Architecture and Design of AlphaServer GS320 , Kourosh Gharachorloo, Madhu Sharma, Simon Steely, and Stephen Van Doren, International Conference on Architectural Support for Programming Languages and Operating Systems, 2000.
Wed. 30 Mar.
Replication and consistency (continued)
Fault tolerance, recovery in distributed systems
Background reading: Sections 8.1 and 8.6, Distributed Systems by van Steen and Tanenbaum
A Survey of Rollback-Recovery Protocols in Message-Passing Systems, E. N. Elnozahy, L. Alvisi, Y. Wang, and D. B. Johnson, ACM Computing Surveys, 34:3, pp. 375-408, September 2002.
Mon. 4 Apr.
GPUs (led by Jiamin Gan and Bokai Zhang) (Class Slides)
Reading: The GPU Computing Era, IEEE Micro, John Nickolls and William J. Dally, April 2010
References: General-Purpose Graphics Processor Architectures, Morgan and Claypool Synthesis Lectures on Computer Architecture, Tor Aamodt, Wilson Fung, and Timothy Rogers; Chapter 1 and Sections 2.1, 3.1, and 4.1 might be useful background reading.
Wed. 6 Apr.
Fault tolerance, distributed consensus (Paxos), replication, group communication
Class slides
Reading: Section 8.2 of van Steen and Tanenbaum
References:
The Part-Time Parliament, Leslie Lamport, ACM Transactions on Computer Systems 16, 2 (May 1998), 133-169
Paxos Made Simple ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58
Mon. 11 Apr.
Group communication, Distributed transactions, distributed commit
Reading: Section 5.6, Section 7.5 of Tanenbaum and van Steen
Class slides

Wed. 13 Apr.
Distributed file systems: Google File System, General Parallel File System (GPFS, IBM), Azure (Microsoft) (led by Jinshu Liu and Pranay Mundra)
Class Slides
The Google File System, Ghemawat et al., SOSP 2003
GPFS: A Shared-Disk File System for Large Computing Clusters, Frank Schmuck and Roger Haskin, FAST 2002
Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency, Calder et al., SOSP 2011

Mon. 18 Apr.
Nonblocking algorithms (led by Abdul Moid Munawar, William Leyman, and Jacob Lovell)
Class Slides
Readings: Sections 3.1, 3.2, 8.1, 8.2 of Shared Memory Synchronization
Reference: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms, Maged Michael and Michael L. Scott, PODC 1996.
Reference: A Lock-Free B+ tree, Anastasia Braginsky and Erez Petrank, SPAA 2012.
Wed. 20 Apr.
Guest lecture by Professor Sreepathi Pai: Parallelizing Irregular Applications on GPUs
Class Slides
Why GPUs are Slow at Executing NFAs and How to Make them Faster
Mon. 25 Apr.
Transactional memory (TM); TM on Intel's Haswell machines
Class slides (TM)
Class slides (Intel TSX)
Wed. 27 Apr.
Wrap-up and Overview

Mon. May 2
8.30 --- 11.30 a.m. Project presentations

Last Change: 27 April 2022 / by Sandhya Dwarkadas