Clusters of commodity PCs and workstations are fast becoming a
viable alternative to custom parallel machines: high-performance
processing nodes and fast networks combine to provide performance
levels comparable to massively-parallel architectures, while
offering significant cost and scaling advantages.
In this course, we will examine the architecture and software of
high-performance scalable clusters, emphasizing differences in how
various issues are addressed in a cluster environment as compared to
in custom parallel machines.
Topics to be covered include the architectures of clusters (processing
nodes, networks, processor-network interfaces), middleware (messaging
layers, distributed shared memory systems, models for group
communication and fault-tolerant computing, and various models of
resource coordination), and specific case studies of clusters and
large-scale applications that have demonstrated good performance.
Introductory graduate level courses in computer architecture and
operating systems recommended.
The course will be conducted as a combination of lectures (providing
general background) and discussions of papers representing the state
of the art. Students will be expected to present papers, participate
in discussion, and do a project which explores the research issues in
greater detail. There will be no exams.
The following is an approximate schedule of topics to be covered. All
the referenced papers are available on the web. Everyone is expected
to have read the papers before the corresponding lecture.
|Lecture 1 (1/20)
||Course Introduction and Administrivia
|Lecture 2 (1/27)
A Case for NOW (Networks of Workstations),
T. Anderson, D. Culler, D. Patterson, and
the NOW team, IEEE Micro, February 1995.
Myrinet -- A Gigabit-per-second Local-Area Network,
N. Boden, D. Cohen, R. Felderman, A. Kulawik, C. Seitz,
J. Seizovic, and W. Su, IEEE Micro, February 1995,
|Lecture 3 (2/3)
||Full-custom Parallel Machines
PRESENTER(S): Arash Baratloo, Holger Karl, Fangzhe Chang
*T: A Multithreaded Massively Parallel Architecture,
R. S. Nikhil, G. M. Papadopoulos, and Arvind, Proceedings of
the 19th ISCA.
iWarp: An Integrated Solution to High-Speed Parallel Computing
S. Borkar et al., Proceedings of Supercomputing'88.
The Message-Driven Processor: A Multicomputer Processing Node with
W. Dally et. al, IEEE Micro, April 1992, pp.23-39.
The MIT Alewife Machine: Architecture and Performance,
A. Agarwal et al., Proceedings of the 22nd ISCA, pp. 2-13.
|Lecture 4 (2/10)
||Parallel Machines with Commodity Processor Cores
PRESENTER(S): Perrin Meyer
Synchronization and Communication in the T3E Multiprocessor,
S. Scott, Proceedings of ASPLOS-VII, pp. 26-36.
Performance Optimizations, implementation, and verification of
the SGI Challenge Multiprocessor,
M. Galles and E. Williams, Proceedings of HICSS'94-1, pp. 134-143.
The SGI Origin: A ccNUMA highly scalable server,
J. Laudon and D. Lenoski, Computer Architecture News,
vol. 25, no. 2, pp. 241-251, 1997.
|Lecture 5 (2/17)
PRESENTER(S): Yuanyuan Zhao, Jian Zheng
An implementation of the Hamlyn sender-managed interface architecture,
G. Buzzard, D. Jacobson, M. Mackey, S. Marovich, and J. Wilkes,
Proceedings of the 2nd OSDI, pp. 245-259.
Virtual Memory Mapped Network Interface for the SHRIMP Multicomputer,
M. A. Blumrich, K. Li, R. Alpert, C. Dubnicki, E. Felten,
and J. Sandberg, Proceedings of the 21st ISCA, 1994.
Memory Channel Network for PCI,
R. Gillett, IEEE Micro, vol. 16, no. 1, pp. 12-18, 1996.
|Lecture 6 (2/23)
||Low-level Messaging Protocols
PRESENTER(S): Linda Steinberg, Leonid Zheleznyak
Active Messages: A mechanism for integrated communication and
T. von Eicken, D. Culler, S. Goldstein, and K. Schauser,
Proceedings of ISCA'92.
Fast Messages: Efficient Portable Communication for Workstation
Clusters and MPPs,
S. Pakin, V. Karamcheti, and A. Chien,
IEEE Concurrency, v. 5, n. 2, 1997, pp. 60-73.
Effects of Communication Latency, Overhead, and Bandwidth in a
Cluster Architecture, R. Martin, A. Vahdat, D. Culler, and
T. Anderson, Proceedings of the 24th ISCA, June 1997.
|Lecture 7 (3/3)
||Higher-level Messaging Protocols
PRESENTER(S): Amit Nene, Niranjan Nilakantan
VMMC-2: Efficient Support for Reliable, Connection-Oriented
C. Dubnicki, A. Bilas, Y. Chen, S. Damianakis, and K. Li,
Proceedings of Hot Interconnects V, August 1997.
Incorporating Memory Management into User-Level Network
A. Basu, M. Welsh, and T. von Eicken, Proceedings of Hot
Interconnects V, August 1997.
Virtual Interface Architecture Specification, Version 1.0,
December 16, 1997, Read only pages 11-35.
You will need to register online at http://www.viarch.org to
get a copy of the specification.
|Lecture 8 (3/10)
||Shared Virtual Memory
PRESENTER(S): Yuanyuan Zhao, Fangzhe Chang
Performance Evaluation of Memory Consistency Models for Shared
K. Gharachorloo, A. Gupta, and J. Hennessy, Proceedings of
ASPLOS-IV, pp. 245-257.
TreadMarks: Shared Memory Computing on Networks of Workstations,
C. Amza, A. Cox, S. Dwarkadas, P. Keleher, H. Lu, R. Rajamony,
W. Yu, and W. Zwaenepoel, IEEE Computer, vol. 29,
no. 2, pp. 18-28, February 1996.
Improving Release-Consistent Shared Virtual Memory using
Automatic Update, L. Iftode, C. Dubnicki, E. W. Felten,
and K. Li, Proceedings of 2nd HPCA, Feb. 1996.
The Effects of Latency, Occupancy, and Bandwidth in Distributed
C. Holt, M. Heinrich, J. Singh, E. Rothberg, and J. Hennessy,
Tech Report CSL-TR-95-660, Computer Science, Stanford
University, January 1995.
|Lecture 9 (3/24)
||Shared Object Memory and Custom Protocols
PRESENTER(S): Amit Nene, Niranjan Nilakantan
CRL: High-Performance All-Software Distributed Shared Memory
K. Johnson, M. Kaashoek, and D. Wallach, Proceedings of
15th SOSP, 1995.
Towards Transparent and Efficient Software Distributed Shared
Memory, D. Scales and K. Gharachorloo, Proceedings of
16th SOSP, 1997.
Implementation and Performance of Munin,
J. Carter, J. Bennett, and W. Zwaenepoel, Proceedings of
13th SOSP, pp. 152-164, 1991.
|Lecture 10 (3/31)
||Fault-tolerance and Availability
PRESENTER(S): Arash Baratloo, Jian Zheng
Horus: A Flexible Group Communication System,
R. van Renesse, K. Birman, and S. Maffeis, Communications
of the ACM, April 1996.
Calypso: An environment for reliable parallel computing,
A. Baratloo, P. Dasgupta, and Z. Kedem, Old version appears in
Proceedings of HPDC'95.
Windows NT Clusters for Availability and Scalability,
R. Short, R. Gamache, J. Vert, and M. Massa, Proceedings of
This is a Microsoft Word document.
|Lecture 11 (4/7)
PRESENTER(S): Harris Morgenstern, Holger Karl
Effective Distributed Scheduling of Parallel Workloads,
A. Dusseau, R. Arpaci, and D. Culler, Proceedings of
Dynamic Coscheduling on Workstation Clusters,
P. Sobalvarro, S. Pakin, W. Weihl, and A. Chien,
Technical Note 1997-017, Digital Equipment Corporation Systems
Research Center, Palo Alto, July 1997.
The Performance of Work Stealing in Multiprogrammed
Environments, R. Blumofe and D. Papadopoulos, Submitted for
|Lecture 12 (4/14)
PRESENTER(S): Perrin Meyer, Linda Steinberg
Beowulf: A Parallel Workstation for Scientific Computation,
D. Becker, T. Sterling, D. Savarese, J. Dorband, U. Ranawak,
C. Parker, Proceedings of ICPP'95.
Parallel Computing on the Berkeley NOW, D. Culler et al.,
Proceedings of the 9th Joint Symposium on Parallel Processing,
The Inktomi Experience, E. Brewer, Collection of white
papers on the web.
|Lecture 13 (4/21)
|Lecture 14 (4/28)
You can do projects in groups of 2-3. You are free to choose any
topic which explores the research issues associated with using a
cluster of commodity workstations as a viable high-performance
parallel platform. I am trying to arrange for access to both a
scalable parallel machine and a cluster of workstations which can be
used for running experiments.
A one-page writeup describing the project idea and completion plan is
due by 9:00pm, March 3, 1998 (Lecture 7). Project presentations are
scheduled for Lectures 13 and 14. The final report is due by 6:00pm,
May 5, 1998 and should be 15-20 pages long in conference style (e.g.,
consisting of an abstract, intro/motivation, background,
approach/solution, analysis/discussion, related work, and