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.
Thurs. 14 Jan.
First day of class
Overview, intro Lecture 1
Readings/references: Chapter 1 of Culler and Singh as well as Tanenbaum and van Steen (on reserve at Carlson)
Tues. 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)
Thurs. 21 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)
Modeling speedup: Readings/references: Gustafson, Karp & Flatt;
Amdahl's Law in the Multicore Era
Additional reading relevant to analysis of your project results: Crowl
Parallel language constructs: Readings/references: PLP Section 12.2;
Pthreads tutorial Lecture 4
Tues. 26 Jan.
Basics of Parallelization (continued): patterns of parallelism: task 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)
Modeling speedup: Readings/references: Gustafson, Karp & Flatt;
Amdahl's Law in the Multicore Era
Additional reading relevant to analysis of your project results: Crowl
Parallel language constructs: Readings/references: PLP Section 12.2;
Pthreads tutorial Lecture 4
Thurs. 28 Jan.
Pthreads; Shared Memory Synchronization: mutual exclusion, events;
Slides from Lectures
Reading: Section 5.5 of Culler and Singh
Tues. 2 Feb.
Shared Memory: Synchronization, Coherence, and Consistency: hardware support for synchronization, symmetric multiprocessors, basic write-back snoop-based protocol for coherence.
Slides from Lectures
Reading: Chapter 5 of Culler and Singh
Thurs. 4 Feb.
Shared Memory: Synchronization, Coherence, and Consistency: snoop-based coherence: implementation issues
Slides from Lectures
Reading: Sections 6.1-6.2 of Culler and Singh
An Introduction to Interconnection Networks Reading: Sections 8.1-8.3 of Culler and Singh
Tues. 9 Feb.
Scalable software-based synchronization algorithms (spinlocks and barriers) - student presentation: Georgiy and Amin; Professor Michael L. Scott will be present to facilitate the discussion Class slides (by Matthew Graichen and Charles Lehner)
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).
Thurs. 11 Feb.
Memory Consistency Models (Guest lecture: Professor Chen Ding)
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.
Tues. 16 Feb.
Memory Consistency Models (continued) 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
Thurs. 18 Feb.
Transactional memory (TM), TM on Intel's Haswell machines; Class slides
Tues. 23 Feb.
Shared Memory: Synchronization, Coherence, and Consistency: directory-based coherence: implementation issues
Slides from Lectures
Reading: Sections 6.1-6.2 of Culler and Singh
An Introduction to Interconnection Networks Reading: Sections 8.1-8.3 of Culler and Singh
Thurs. 25 Feb.
Languages and libraries for parallelism, thread implementation
Readings/references: PLP Chapter 12;
Cilk Plus Tutorial
Intel's pages for Cilk Plus: Additional material
OpenMP
Class Slides
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.
Tues. 1 Mar.
Message passing (MPI), MPI Tutorial
Thurs. 3 Mar.
Consistency models from a programmer's perspective (Colin and Feroz)
Threads Cannot be Implemented as a Library, Hans-J. Boehm, in Proceedings of the Conference on Programming Language Design and Implementation (PLDI), June 2005.
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
C/C++ 11 Memory order and atomic operations

Tues. 8 Mar.
Spring break;
Thurs. 10 Mar.
Spring break;

Tues. 15 Mar.
More on Message Passing;
Distributed systems: Synchronization using 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.
Thurs. 17 Mar.
Distributed systems: Synchronization using logical clocks
Reading: Sections 5.1 and 5.2 of Tanenbaum and van Steen
Distributed systems: mutual exclusion, election algorithms
Reading: Sections 5.3-5.5 of Tanenbaum and van Steen
Lecture slides
Tues. 22 Mar.
Term project discussions;
Distributed systems: leader election, global state
Reading: Sections 5.3 and 5.4 of Tanenbaum and van Steen
Thurs. 24 Mar.
MapReduce and Its Implementation;
Reading material: MapReduce: Simplified Data Processing on Large Clusters, Jeffrey Dean and Sanjay Ghemawat, OSDI 2004
Hadoop (please browse these pages to get a sense of the Hadoop programming model)
Tues. 29 Mar.
Using logical clocks: 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.
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.
Thurs. 31 Mar.
Distributed transactions, distributed commit, distribution protocols, consistency
Reading: Section 5.6, Section 7.5, Sections 6.4-6.5.2, and 6.6.2 of Tanenbaum and van Steen
Tues. 5 Apr.
Distributed commit, fault tolerance
Reading: Sections 7.1 - 7.6 of Tanenbaum and van Steen
Knowledge and Common Knowledge in a Distributed Environment(Halpern and Moses, 2009 Dijkstra award)
Thurs. 7 Apr.
Group Communication (Yuncheng Li)
Background reading: Section 7.4, reliable group communication (virtual synchrony), Tanenbaum and van Steen, Section 6.4.3, epidemic protocols, Tanenbaum and van Steen
Spinglass: Secure and Scalable Communications Tools for Mission-Critical Computing , Kenneth P. Birman, Robbert van Renesse and Werner Vogels, International Survivability Conference and Exposition, DARPA DISCEX-2001, Anaheim, California, June 2001.
Tues. 12 Apr.
Fault tolerance, recovery in distributed systems
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.
Thurs. 14 Apr.
Guest lecture by Professor Chen Ding: Behavior-Oriented Parallelization
Reading material: Software behavior oriented parallelization, Chen Ding, Xipeng Shen, Kirk Kelsey, Chris Tice, Ruke Huang, and Chengliang Zhang, PLDI 2007.
Tues. 19 Apr.
Guest lecture by Professor Michael L. Scott: Nonblocking Algorithms
Reading: Chapter 8 of Shared-Memory Synchronization
Thurs. 21 Apr.
In-Class Exam
Tues. 26 Apr.
In-class quiz on last two lectures; Wrap-up and Overview
Saturday, May 7
8.30 --- 11.30 a.m. Project presentations

Last Change: 26 April 2016 / by Sandhya Dwarkadas