CSC 2/458

Parallel and Distributed Systems

Spring 2013.

Course Schedule

Please note that some readings (those with ur_only in their URL) are only accessible from a UR domain.
Thurs. 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)
Tues. 22 Jan.
Basics of Parallelization: dependences, synchronization Lecture 2
Readings/references: Chapters 2 and 3 of Culler and Singh; Chapter 3 of Grama, Karypis, Kumar, and Gupta
Thurs. 24 Jan.
Basics of Parallelization: patterns of parallelism Lecture 3
Readings/references: Chapters 2 and 3 of Culler and Singh; Chapter 3 of Grama, Karypis, Kumar, and Gupta
Tues. 29 Jan.
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. 31 Jan.
Scalable Software-based synchronization algorithms (spinlocks and barriers): Class slides (by Tim Kopp and Joe Izraelevitz)
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
Tues. 5 Feb.
Barrier algorithms (Tim Kopp: continued);
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. 7 Feb.
Coherence protocols: snoop-based coherence: implementation issues
Slides from Lectures
Reading: Sections 6.1-6.2 of Culler and Singh
Tues. 12 Feb.
Coherence protocols: directory-based coherence
Slides from Lectures
An Introduction to Interconnection Networks Reading: Sections 8.1-8.3 of Culler and Singh
Thurs. 14 Feb.
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.
Tues. 19 Feb.
More on consistency models
Thread implementation;
Readings/references: PLP section 8.6; 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.
Thurs. 21 Feb.
The Java Memory Model (Brian Gernhardt)
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
Tues. 26 Feb.
Parallel programming models (Andrew Abumoussa)
Cilk
Unified Parallel C (UPC)
OpenMP
Class slides
Thurs. 28 Feb
MapReduce (and other models) (Iftekhar Naim)
Class slides
Message passing (MPI), MPI Tutorial
Tues. 5 Mar
Comparison of Sun Fireplane, IBM Power4, and Blue Gene/Q Architectures (Hao Luo):
POWER4 System Microarchitecture , white paper, IBM Server Group, October 2001.
The Sun Fireplane System Interconnect , Alan Charlesworth, Supercomputing Conference, November 2001.
Class slides
Thurs. 7 Mar
AlphaServer GS320 (and a peek at Intel's Xeon Phi Coprocessor) (Ananya Parekh)
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
Tues.-Thurs. 12-14 Mar.
Spring break
Tues. 19 Mar.
BlueGene/Q and other HPC machines (Sushant Kondguli)
Top 500 Supercomputer Sites
The IBM Blue Gene/Q Compute Chip, IEEE Micro, March-April 2012
Evaluation of Blue Gene/Q Hardware Support for Transactional Memories, International Conference on Parallel Architectures and Compilation Techniques (PACT), 2012
Class slides
Thurs. 21 Mar.
Term project introductions, MPI/OpenMP/Cilk discussion, continuation of multiprocessor implementation discussion
Cilk
OpenMP
Message passing (MPI), MPI Tutorial
Tues. 26 Mar.
Distributed systems: Logical and physical clocks
Lecture slides
Reading: Sections 5.1 and 5.2 of Tanenbaum and van Steen
Thurs. 28 Mar.
Distributed systems: Logical and physical clocks (continued), mutual exclusion, distributed snapshots
Lecture slides
Reading: Sections 5.1-5.5 of Tanenbaum and van Steen Distributed Transactions
Reading: Section 5.6, Sections 7.1 - 7.5 of Tanenbaum and van Steen
Tues. 2 Apr.
Software distributed shared memory (Leon Weingard and Andrew Hoskins)
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
Thurs. 4 Apr.
Guest lecture by Professor Chen Ding: Safe parallel programming
Suggested reading: BOP: Software Behavior Oriented Parallelization, C. Ding, X. Shen, K. Kelsey, C. Tice. R. Huang, and C. Zhang, ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2007.
Tues. 9 Apr.
Transactional Memory (Shule Li)
Required background reading: Section 5.6 of Tanenbaum and van Steen
Required paper reading (summary due in class):
Lowering the Overhead of Nonblocking Software Transactional Memory, V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. Scherer III, and M. L. Scott, First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT), held in conjunction with PLDI, Ottawa, Ontario, Canada, June 2006
Additional readings:
Transactional Memory: architectural support for lock-free data structures., M. P. Herlihy and J. E. B. Moss, International Symposium on Computer Architecture (ISCA), May 1993, San Diego, CA.
Class Slides
Thurs. 11 Apr.
Guest lecture by Professor Michael Scott: Nonblocking algorithms
Tues. 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,
Thurs. 18 Apr.
GPGPU (Andrew, Sean, Thomas)
GPU Computing, J. D. Owens, M. Houston, D. Luebke, S. Green, J. E. Stone, and J. C. Phillips, Proceedings of the IEEE, Vol. 96, Issue: 5, May 2008.
A Closer Look at GPUs, K. Fatahalian and M. Houston, Communications of the ACM, Vol. 51, Issue: 10, October 2008.
Class slides
Tues. 23 Apr.
Recovery in distributed systems (Wei Liu and Chao Li)
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
Background reading: Section 7.6 of Tanenbaum and van Steen
Thurs. 25 Apr.
Group Communication (Quanzeng and Haoliang)
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.
Class Slides
Tues. 30 Apr.
Overview/Wrap-Up

------------------------------------------------------

Last Change: 05 May 2013 / by Sandhya Dwarkadas