CSC 2/458

Parallel and Distributed Systems

Spring 2007.

Course Schedule (evolving)

Wed. 17 Jan.
First day of class
Overview, intro Lecture 1
Readings/references: Chapter 1 of Culler and Singh as well Tanenbaum and van Steen (on reserve at Carlson);
Mon. 22 Jan.
Basics of Parallelization: dependences, synchronization Lecture 2
Readings/references: "Parallel Programming Patterns" in preparation by Willy Zwaenepoel; Chapters 2 and 3 of Culler and Singh;
Wed. 24 Jan.
Basics of Parallelization: patterns of parallelism Lecture 3
Mon. 29 Jan.
Pthreads tutorial Lecture 4
Wed. 31 Jan.
Parallel language constructs; MPI tutorial Lecture 5
Mon. 5 Feb.
MPI continued; Thread implementation;
Readings/references: PLP sections 8.6 and 12.2; 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.
Wed. 7 Feb.
Shared Memory: Synchronization, Coherence, and Consistency: hardware support for synchronization, symmetric multiprocessors, basic write-through snoop-based protocol for coherence.
Slides from Lectures
Reading: Chapter 5 of Culler and Singh
Mon. 12 Feb.
Scalable Software-based synchronization algorithms (spinlocks and barriers): Max Abernethy and Brian Sherwin
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.
Section 5.5 of Culler and Singh
Class slides
Wed. 14 Feb.
Shared Memory: Synchronization, Coherence, and Consistency (continued): hardware support for synchronization, symmetric multiprocessors, basic write-through snoop-based protocol for coherence.
Slides from Lectures
Reading: Chapter 5 of Culler and Singh
Mon. 19 Feb.
Comparison of Sun Fireplane and IBM Power4 Architectures (Daniel Mollowney and Thomas Thomas):
POWER4 System Microarchitecture , white paper, IBM Server Group, October 2001.
Class slides
The Sun Fireplane System Interconnect , Alan Charlesworth, Supercomputing Conference, November 2001.
Class slides
Wed. 21 Feb.
Coherence protocols: snoop-based and directory-based coherence
Reading: Chapter 5 of Culler and Singh, Sections 6.1 and 6.2, and Section 8.2 of Culler and Singh
Slides from Lectures
An Introduction to Interconnection Networks
Mon. 26 Feb.
Memory Consistency Models (Nitin Bhardwaj):
Shared Memory Consistency Models: A Tutorial, Sarita Adve and Kourosh Gharachorloo, Rice TR 9512, also appeared in IEEE Computer, December 1996.
Class slides
Wed. 28 Feb.
More on memory consistency models (Matt Post)
The Java Memory Model, J. Manson, W. Pugh, and S. V. Adve, in Proceedings of the Symposium on Principles of Programming Languages (PoPL), January 2005.
Threads Cannot be Implemented as a Library , Hans-J. Boehm, in Proceedings of the Conference on Programming Language Design and Implementation (PLDI), June 2005.
Class slides
Mon. 5 Mar.
Guest lecture by Professor Kai Shen Class slides
Wed. 7 Mar.
Scalable concurrent Internet services (Saurabh and Vinod)
SEDA: An Architecture for Well-Conditioned, Scalable Internet Services, M. Welsh, D. Culler, and E. Brewer, Symposium on Operating Systems Principles , October 2001.
Class slides
Capriccio: Scalable Threads for Internet Services , R. Behren, J. Condit, F. Zhou, G. C. Necula, and E. Brewer, Symposium on Operating Systems Principles , October 2003.
Class slides
Mon.-Wed. 12-14 Mar.
Spring break
Mon. 19 Mar.
Distributed systems: Logical and physical clocks
Lecture slides
Reading: Sections 5.1 and 5.2 of Tanenbaum and van Steen
Wed. 21 Mar.
Software distributed shared memory (Hongzhou and Jiasheng)
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.
Class slides
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.
Class slides
Mon. 26 Mar.
Cashmere (continued)
Distributed systems: mutual exclusion (continued), distributed snapshots
Reading: Sections 5.3-5.5, Tanenbaum and van Steen
Wed. 28 Mar.
BlueGene/L and other HPC machines (Aaron Carpenter)
Overview of the Blue Gene/L System Architecture, Gara et al. , IBM Journal of Research and Development, Vol. 49, No. 2/3, March/May 2005.
Cray
Performance Evaluation of the Cray X1 Distributed Shared Memory Architecture, T.H. Dunigan, Jr., J.S. Vetter et al., IEEE Micro, 25(1):30-40, 2005.
Early Evaluation of the Cray XT3, 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2006.
Class slides
Mon. 2 Apr.
Speculative parallelization (Chris Tice) Tradeoffs in Buffering Memory State for Thread-Level Speculation in Multiprocessors, M. J. Garzaran, M. Prvulovic, J. Llaberia, V. Vinals, L. Rauchwerger, and J. Torrellas, International Conference on High Performance Computer Architecture, February 2003.
Class slides
Wed. 4 Apr.
Distributed systems: mutual exclusion (continued), distributed snapshots
Reading: Sections 5.3-5.5, Tanenbaum and van Steen
Distributed Transactions
Reading: Section 5.6, Sections 7.1 - 7.5 of Tanenbaum and van Steen
Mon. 9 Apr.
Recovery in distributed systems (Jonathan and Hai)
A Survery 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.
Class Slides - Checkpointing
Class Slides - Log-based recovery
Background reading: Section 7.6 of Tanenbaum and van Steen
Wed. 11 Apr.
Group Communication (Shaojun Zhao)
Background reading: Section 7.4, 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.
Class Slides
Mon. 16 Apr.
Distributed transactions (continued), distribution protocols, consistency
Reading: Section 5.6, Sections 7.1 - 7.5, Sections 6.4-6.5.2, and 6.6.2 of Tanenbaum and van Steen,
Mon. 18 Apr.
AlphaServer GS320 (Hemayet): 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.
Class slides
Mon. 23 Apr.
More on parallel programming models (Bin Wei)
Cilk
Unified Parallel C (UPC)
OpenMP
Wed. 25 Apr.
Guest lecture by Professor Michael L. Scott
Professor Scott's High-Performance Synchronization Webpage
Reading: Capabilities and Limitations of Library-Based Software Transactional Memory in C++ , (in submission), authors: L. Dalessandro, V. J. Marathe, M. F. Spear, and M. L. Scott.
Mon. 30 Apr.
Project presentations
Wed. 2 May
Project presentations

Last Change: 05 May 2007 / by Sandhya Dwarkadas