CSC 2/458
Parallel and Distributed Systems
Spring 2009.
Course Schedule
Please note that some readings (those with ur_only in their URL) are only accessible from a UR domain.
- Wed. 14 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);
- Wed. 21 Jan.
-
Basics of Parallelization: dependences, synchronization Lecture 2
Readings/references: Chapters 2 and 3 of Culler and Singh;
- Mon. 26 Jan.
-
Basics of Parallelization: patterns of parallelism Lecture 3
- Wed. 28 Jan.
-
Modeling speedup: Readings/references:
Gustafson,
Karp &
Flatt;
Additional reading relevant to analysis of your project results:
Crowl
Parallel language constructs: Readings/references: PLP Section
12.2;
Pthreads tutorial Lecture 4
- Mon. 2 Feb.
-
Scalable Software-based synchronization algorithms (spinlocks and barriers): Class slides (by Greg Wilbur)
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
- Wed. 4 Feb.
-
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.
- Mon. 9 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
- Wed. 11 Feb.
-
Coherence protocols: snoop-based and directory-based coherence
Slides from Lectures
An Introduction to Interconnection Networks
Reading: Sections 6.1, 6,2, 8.1-8.3 of Culler and Singh
- Mon. 16 Feb.
-
Memory Consistency Models (Satyaki Mahalanabis):
Shared Memory Consistency Models: A Tutorial,
Sarita Adve and Kourosh Gharachorloo, Rice TR 9512, also appeared in
IEEE Computer, December 1996.
- Wed. 18 Feb.
-
More on consistency models
- Mon. 23 Feb.
-
More on memory consistency models (Chetan Bhole)
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
- Wed. 25 Feb.
-
Message passing (and other models)
MPI tutorial Lecture 5
- Mon. 2 Mar.
-
Comparison of Sun Fireplane and IBM Power4 Architectures (Rajkumar Parihar):
POWER4 System Microarchitecture , white paper, IBM Server Group,
October 2001.
The Sun Fireplane System Interconnect ,
Alan Charlesworth, Supercomputing Conference, November 2001.
Class slides
- Wed. 4 Mar.
-
Guest lecture by Professor Chen Ding: Speculative parallelization
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.
- Mon.-Wed. 9-11 Mar.
-
Spring break
- Mon. 16 Mar.
-
Term project introductions, MPI/OpenMP/Cilk discussion,
continuation of multiprocessor implementation discussion
Cilk
OpenMP
- Wed. 18 Mar.
-
Distributed systems: Logical and physical clocks
Lecture slides
Reading: Sections 5.1 and 5.2 of Tanenbaum and van Steen
- Mon. 23 Mar.
-
BlueGene/L and other HPC machines (Ravi Patel)
Top 500 Supercomputer Sites
Overview of the Blue Gene/L System Architecture,
A. Gara, M. A. Blumrich, D. Chen, G. L.-T. Chiu, P. Coteus,
M. E. Giampapa, R. A. Haring, P. Heidelberger,
D. Hoenicke, G. V. Kopcsay, T. A. Liebsch, M. Ohmacht,
B. D. Steinmacher-Burow, T. Takken, and P. Vranas,
IBM Journal of Research and Development, Vol. 49, No. 2/3, March/May 2005.
Entering the Petaflop Era: The Architecture and Performance of Roadrunner
Kevin J. Barker , Kei Davis , Adolfy Hoisie , Darren J. Kerbyson ,
Mike Lang , Scott Pakin , and Jose C. Sancho, Proceedings of the
2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008,
Austin, Texas
Class slides
- Wed. 25 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
- Mon. 30 Mar.
-
Software distributed shared memory (Peter Andrews and Justin Steinberg)
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
- Wed. 1 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. 6 Apr.
-
Transactional Memory (Alain Leblanc)
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.
Additional readings:
Tapping into Parallelism with Transactional Memory, A. Shriraman, S. Dwarkadas, and M. L. Scott. ;login: (the USENIX Magazine), Apr. 2009.
Conflict Detection and Validation Strategies for Software Transactional Memory,
M. F. Spear, V. J. Marathe, W. N. Scherer III, and M. L. Scott,
20th International Symposium on Distributed Computing (DISC), Stockholm,
Sweden, Sept. 2006.
Class Slides
- Wed. 8 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. 13 Apr.
-
GPGPU (Kostas Menychtas)
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
- Wed. 15 Apr.
-
AlphaServer GS320 (Yanwei Song)
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. 20 Apr.
-
Recovery in distributed systems (Bryan Jacobs)
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
- Wed. 22 Apr.
-
Parallel Languages: Partitioned Global Address Space (PGAS) models (Bin Bao)
Unified Parallel C (UPC)
Scaling Communication-Intensive Applications on BlueGene/P Using One-Sided Communication and Overlap,
R. Nishtala, P. Hargrove, D. Bonachea, K. Yelick,
23rd International Parallel & Distributed Processing Symposium (IPDPS), 2009.
Class Slides
- Mon. 27 Apr.
-
Group Communication (Rongrong Zhong)
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
- Wed. 29 Apr.
-
Overview/Wrap-Up
------------------------------------------------------
Last Change:
01 May 2009 /
by Sandhya Dwarkadas