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