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