Readings
CMSC 714:  High Performance Computing

Note: for each class (after the intro material), 4 students will be responsible for emailing me (als@cs.umd.edu) with ~4 discussion question on the reading(s) for that day at least 24 hours before class starts, and be prepared to ask those questions and help explain the paper to the rest of the class.

Introduction - What and Why? 

1/26 Parallel Computing and Parallel Computers

• from Lecture Notes

1/28 Applications of Parallel Computing

• from Lecture Notes

Programming Models

2/2  Expressing Parallelism (Explicit Control)

• V.S. Sunderam, G.A. Geist, J. Dongarra, and R. Manchek, "The PVM Concurrent Computing System: Evolution, Experiences, and Trends", Parallel Computing, 20(4), 1994. [PDF]

• J. J. Dongarra, S. W. Otto, M. Snir, and D. Walker, "A message passing standard for MPP and workstations," Communications of the ACM, 39(7), 1996, pp. 84-90. [PDF]

2/4-16 Introduction to Debugging Parallel Programs

• from Taiga Nakamura's lecture notes

2/18 Expressing Parallelism (Implicit Control) - N. Crowell, M. Badamo, C. Cui, D. Wood

• William W. Carlson et al, "Introduction to UPC and Language Specification," CCS-TR-99-157. [PDF]

• L. Dagum and R. Menon, "OpenMP: An Industry-Standard API for Shared-Memory Programming," IEEE Computational Science & Engineering, 5(1), 1998. [PDF]

2/23 Expressing Parallelism (Data Layout and Functional) - C. Gavini, A. Crowell, C. Hayden, R. Jain

• Siegfried Benkner and Hans Zima, "Compiling High Performance Fortran for distributed-memory architectures", Parallel Computing, 25(13-14), 1999. [PDF]
  You can skip, or at most skim, Section 6.

• Jean-Luc Gaudiot, Tom DeBoni, John Feo, Wim Bohm, Walid Najjar, and Patrick Miller, "The Sisal Model of Functional Programming and its Implementation," Proceedings of the 2nd AIZU International Symposium on Parallel Algorithms / Architecture Synthesis (pAs '97).  [PDF]

2/25 Expressing Parallelism (Hybrids) - J. Gruen, B. Robbins, Y. Kim, G. Zaki

• Kathy Yelick et. al., "Titanium: A High Performance Java Dialect", Concurrency: Practice & Experience, 10(11-13), 1998. [PDF]

• Steve W. Bova et. al., "Parallel Programming with Message Passing and Directives", Computing in Science & Engineering, 3(5), 2001. [PDF]

Architectures

3/2  Shared Memory - I. Chukhman, J. Locke, P. Roos, W. Zheng

• J. Laudon and D. Lenoski, "The SGI Origin: a ccNUMA highly scalable server," Proceedings of 1997 International Symposium on Computer Architecture (ISCA '97), May 1997 [PDF]

• Alan E Charlesworth, "The Sun Fireplane Interconnect", IEEE Micro, 22(1), Jan.-Feb. 2002. [PDF]

3/4  Message Passing and Communication - J. Wu, B. Wilson, B. Liu, M. Scharrenbroich

• Robert M. Metcalfe and David R. Boggs, "Ethernet: distributed packet switching for local computer networks," Communications of the ACM, (19)7, 1976. [PDF]

• Fabrizio Petrini. Wu-chun Feng,  Adolfy Hoisie, Salvador Coll, Eitan Frachtenberg, "The Quadrics Network: High-Performance Clustering Technology," IEEE Micro, 22(1), Jan-Feb 2002. [PDF]

3/9 Vectors and Threading - P. Sharma, A. Balasubramanian, C. Kang, M. McCutchen

• Gail Alverson, Preston Briggs, Susan Coatney, Simon Kahan, Richard Korry, "Tera hardware-software cooperation", Proceedings of SC'97, November 1997. [PDF]

• T. H. Dunigan, Jr, J.S. Vetter, J.B. White III, P. H. Worley, "Performance Evaluation of the Cray X1 Distributed Shared-Memory Architecture", IEEE Micro, 25(1), Jan. 2005. [PDF]

3/11 Not Vector, Not Commodity - S. Srivastava, U. Ikram, M. McCutchen, G. Zaki

• A. Gara, et. al, "Overview of the Blue Gene/L system architecture", IBM Journal of Research and Development, 49(2/3), Fall 2005, [PDF]

•  A. E. Eichenberger , et. al, "Using advanced compiler technology to exploit the performance of the Cell Broadband Engine architecture", IBM Systems Journal, 45(1), Jan. 2006. [PDF]

3/16, 3/18 Spring break

3/23 Computational Grids - T. Long, C. Gavini, J. Wu, U. Ikram

• I. Foster and C. Kesselman, "Computational Grids", Chapter 2 of The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann, 1999. [PDF]

• A. Chervenak, I. Foster, C. Kesselman, C. Salisbury, S. Tuecke, "The Data Grid: Towards an Architecture for the Distributed Management and Analysis of Large Scientific Datasets",  Journal of Network and Computer Applications, 23:187-200, 2001. [PDF]

3/25 Clouds - S. Srivastava, B. Robbins, W. Zheng, P. Sharma

• Jeffrey Dean and Sanjay Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters", Proceedings of OSDI'04, pp. 137-150  [PDF]

• Michael Stonebraker, Daniel Abadi, David J. DeWitt, Sam Madden, Erik Paulson, Andrew Pavlo, Alexander Rasin, "MapReduce and Parallel DBMSs: Friends or Foes?", Communications of the ACM, 53(1), Jan. 2010, pp. 64-71. [PDF]

Tools

3/30 Event Ordering and Race Detection - Y. Kim, R. Jain, B. Wilson, S. Srivastava

• L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System", Communications of the ACM, 21(7), 1978, pp. 558-564. [PDF]

• S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson, "Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs", In Proceedings of the 16th Symposium on Operating Systems Principles, ACM Press, Oct. 1997. [PDF]

4/1 Performance Metrics - B. Liu, C. Hayden, A. Balasubramanian, P. Roos

• A. J. Goldberg and J. L. Hennessy, "Mtool: An Integrated System for Performance Debugging Shared Memory Multiprocessor Applications", IEEE Transactions on Parallel and Distributed Computing, 4(1), 1993. [PDF]

• J. K. Hollingsworth, "Critical Path Profiling of Message Passing and Shared-memory Programs", IEEE Transactions on Parallel and Distributed Computing, 9(10), 1998, pp. 1029-1040. [PDF]

4/6 Data Collection and Instrumentation - J. Gruen, C. Kang, D. Wood, G. Zaki

• Nicholas Nethercote and Julian Seward, "Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation",  In Proceedings of  the 2007 ACM/SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2007. [PDF]

• B. R. Buck and J.K. Hollingsworth , "An API for Runtime Code Patching," International Journal of High Performance Computing Applications, 14 (4), Winter 2000, pp. 317-329. [PDF]

4/8 Scheduling - Short Term - Y. Kim, J. Locke, W. Zheng, J. Wu

• Y. Zhang, A. Sivasubramaniam, J. Moreira, and H. Franke, "Impact of Workload and System Parameters on Next Generation Cluster Scheduling Mechanisms", IEEE Transactions on Parallel and Distributed Systems, 12(9), Sept. 2001, pp. 967-985. [PDF]

• A.C. Dusseau, R.H. Arpaci, D.E. Culler, "Effective Distributed Scheduling of Parallel Workloads", In Proceedings of ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, ACM Press, May 1996. [PDF]

4/13 Cache Tools - I. Chukhman, T. Long, N. Crowell, M. Badamo

• J. Mellor-Crummey, D. Whalley, and K. Kennedy,  "Improving Memory Hierarchy Performance for Irregular Applications Using Data and Computation Reorderings", International Journal of Parallel Programming, 29(3), June 2001. [PDF]

• Margaret Martonosi, Anoop Gupta, Thomas Anderson, "MemSpy: analyzing memory system bottlenecks in programs", ACM SIGMETRICS Performance Evaluation Review, 20(1), 1992. [PDF]

4/15 Midterm Exam

4/20 No class

4/22 Runtime Parallelization - A. Crowell, C. Kang, C. Hayden, M. Scharrenbroich

• S.J. Fink, S.R. Kohn, and S.B. Baden, "Efficient Run-time Support for Irregular Block-Structured Applications", Journal of Parallel and Distributed Computing, 50(1), 1998. [PDF]

• G. Agrawal, A. Sussman, and J. Saltz, "An Integrated Runtime and Compile-time Approach for Parallelizing Structured and Block Structured Applications", IEEE Transactions on Parallel and Distributed Computing, 6(7), 1995. [PDF]

Systems Issues

4/27 Scheduling - Batch Queues - N. Crowell, D. Wood, J. Locke, I. Chukhman

• D. G. Feitelson and A. M. a. Weil, "Utilization and Predictability in Scheduling the IBM SP2 with Backfilling", 12th International. Parallel Processing Symposium, April 1998. Use this extended form [PDF]

• J. Weinberg and A. Snavely, "Symbiotic Space-Sharing on SDSC's DataStar System",  12th Workshop on Job Scheduling Strategies for Parallel Processing, 2006. [PDF]

4/29 Finding Idle Cycles - R. Jain, C. Gavini, P. Roos, T. Long

• M. Litzkow, M. Livny, and M. Mutka, "Condor - A Hunter of Idle Workstations", In Proceedings of  International Conference on Distributed Computing Systems, June 1988, pp. 104-111. [PDF]

• David P. Anderson, Carl Christensen and Bruce Allen, "Designing a Runtime System for Volunteer Computing", In Proceedings of SC'06, November 2006. [PDF]

5/4 Parallel I/O - B. Wilson, J. Gruen, M. Badamo, B. Robbins, M. McCutchen

• Terry Jones, Alice Koniges, and R. Kim Yates, "Performance of the IBM General Parallel File System", In Proceedings of 14th International Parallel and Distributed Processing Symposium (IPDPS'00), April 2000. [PDF]

• A. Acharya, M. Uysal, and J. Saltz, "Active Disks: Programming Model, Algorithms and Evaluation", In Proceedings of Eighth International Conference on Architectural Support for Programming Languages and Operating Systems, October1998. [PDF]

5/6 Project Demos

5/7 Project Demos - class meets at 1:30PM in CSIC 2118

5/11 Applications - A. Balasubramanian, B. Liu, M. Scharrenbroich, U. Ikram, A. Crowell, P. Sharma

• U. Catalyurek, M. Beynon, C. Chang, T. Kurc, A. Sussman, and J. Saltz, "The Virtual Microscope",  IEEE Transactions on Information Technology in Biomedicine, Vol. 7, No. 4, 2003. [PDF]

• David E. Shaw et. al., "Millisecond-scale molecular dynamics simulations on Anton", Proceedings of SC'09, November 2009. [PDF]