CDA5125 Parallel and Distributed Systems

Syllabus, Example Programs

Lecture 1 (Aug. 24)

• Syllabus, Introduction

• Basics of Parallelism (1), Basics of Parallelism (2)

• Parallel Programming Models
• Software and the Concurrency Revolution, by Herb Sutter and James Larus (Microsoft), ACM Queue Special Issue on Multiprocessor 3(7) Sept. 2005.
• Homework 1: Write a critic for the above paper. The critic should follow this format. Due Sept. 7 before class.
• Prepare for an in class discussion section in Sept. 7. Focus topic: "What is the most useful software feature to support the concurrency revolution?"

• Pthread
• You can find a more thorough introduction to pthread and more programming examples in this pthread tutorial

• Programming assignment No. 1, Programming assignment No. 1 presentation, Driver and sample code

• OpenMP
• More information about OpenMP

• Message Passing Interface(MPI)
• MPI forum home page

Your assignment 1 program must be able to product exactly the same output file (tmp333) as the driver program for any small AND large matrices (check with the UNIX diff command) to be considered correct and to receive a non-zero grade.

Lecture 8 (Sept. 21)

• Parallel Computer Architecture Overview
• From a few cores to Many: A Tera-scale Computing Research Over view , An Intel white paper about tera-scale (parallel) computing, 2006.
• Homework 2: Write a critic for the above paper. Due Sept.28 before class.
• Prepare for an in-class discussion section in Sept.28. Focus topic: "What will the future multi-core processors be like?"

• Shared Memory Architecture: Cache Coherence Protocols
• Reading: Culler's book, Chapters 6 and 8.

• Shared Memory Architectures 2: Shard memory consistency models,
• Reading: Shared Memory Consistency Models: A Tutorial.
• Homework 3, due Oct. 5 before the class.
• Programming assingment 2: OpenMP and MPI sparse matrix multiplication, Due: Oct. 14(11:00am). This is a hard deadline.

• Scalable Multiprocessor,
• Reading: Culler's book Chapter 10.

• Interconnection Networks: topology,
• Reading: Culler's book Chapter 9.
• Homework 4, formally describe k-ary n-cube (either mesh or torus case), give the diameter, nodal degree, and bisection bandwidth of this topology. due before the next class.

• Interconnection Networks 2: Switching, Routing, and Flow Control

• Interconnection Networks 3: Fat-tree and Its Performance Issues
• Reading: T. Hoefler, T. Schneider, and A. Lumsdaine, "Multistage Interconnection Networks are not Crossbars: Effects of static routing in high performance networks", IEEE Cluster, 2008.
• Reading: G. Rodriguez, et. al., "Exploring Pattern-aware Routing in Generalized Fat Tree Networks," ACM International Conference on Supercomputing 2009.
• Homework 5: Write critics for the above two papers. Due next Monday.

• Interconnection Networks 4: Hardware/Software Interaction
• Reading: V. Karamcheti and A. A. Chien, "Software Overhead in Messaging Layers: Where Does the Time Go?" ASPLOS-VI, 1994.

• IBM Blue Gene/L Architecture
• Reading: Overview of the Blue Gene/L system architecture, by A. Gara, et. al., IBM Journal of Research and Development, 49(2/3):195-212, March/May 2005. Here is a free version

Lecture 17 (Oct. 21)

• The InfiniBand architecture

Information for the term project, important dates when you must turn in some documents or do the presentation: 10/26 (topic selection), 11/11 (progress report), (11/25, 11/30, 12/2) (project presentation), 12/8 (final report/software due).

Schedule for the rest of the semester. The topics are fixed, pick your course presentation topic as soon as possible.

Lecture 18 (Oct. 26)

• Loop optimization and parallelizing compilers
• Programming assignment 3: Loop optimizations, due date: Nov. 4, the naive matrix multiply routine.

Lecture 19 (Nov. 2)

• PRAM and LogP

Course Presentation Schedule, Presentation Grading Sheet Lecture 20 (Nov. 4)

• Transactional Memory (Akil Merchant/Vineet Sahu)
  • Reading: M. Herlihy, J.E. B. Moss, "Transactional Memory: Architectural support for lock-free data structures," ACM ISCA 1993.
  • Reading: U. Drepper, "Parallel Programming with Transactional Memory," ACM Queue 6(5)38-45, Dec. 2008.

• New parallel programming models (Vanessa Cedeno/Anuja Jain)
  • Reading: Michael D. Linderman, J. D. Collins, H. Wang, t. H. Meng, "Merge: A Programming Model for Heterogeneous Multi-core Systems," ACM ASPLOS 2008.
  • Reading: J. Dean, and S. Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters," OSDI 2004.
• Compiler and OS support for Multi-core (Tony Howard/Jaime Mahaffey)
  • Reading: Marek Olszewski, Jason Ansel, Saman Amarasinghe, "Kendo: Efficient Determistic Multithreading in Software," ACM ASPLOS 2009.
  • Reading: Z. Anderson, D. Gay, R. Ennals, and E. Brewer, "SharC: Checking Data Sharing Strategies for Multithreaded C," ACM PLDI 2008.

• Future direction of parallel computing research & Autotuner (Fernando Torres/Peter Chau)
  • Reading: K. Asanovic, et. al., "A View of the Parallel Computing Landscape," Communications of ACM , 52(10): 56-67, Oct. 2009.
  • Reading: C. Whaley, et. al, "Automated Empirical Optimization of Software and the ATLAS Project," Parallel Computing, 27(1-2):3-35, 2001.
• Accelerator based computing (Charles Mcclendon/Matthew Guidry)
  • Reading: Michael Kistler, John Gunnels, Daniel Brokenshire, Brad Benton, "Petascale Computing with Accelerators," ACM PPoPP 2009.
  • Reading: S. Ryoo, C. I. Rodrigues, S.S. Baghsorkhi, S. S. Stone, "Optimization Principles and Application performance Evaluation of a Multithreaded GPU Using CUDE," ACM PPoPP 2008.

• Networks-on-chip (Surjyendy Ray/Yourej Pawar) /
  • Reading: L. P. Carloni, P. Pande, and Y. Xie, "Networks-on-Chip in Emerging Interconnect Paradigms," IEEE/ACM Symp. on Networks on Chip, 2009.
  • Reading: H. Matsutani, et. al., "Fat H-Tree: A Cost-Efficient Tree Based on-Chip Network," IEEE TPDS, 20(8):1126-1141, August 2009.
• Routing (Amritpal Singh/Rohith Uppala)
  • Reading: P. Geoffray, T. Hoefler, "Adaptive Routing Strategies for Modern High Performance Networks," HOT Interconnect, 2008.
  • Reading: X. Yuan, W. Nienaber, Z. Duan, and R. Melhem, "Oblivious Routing for Fat-Tree Based System Area Networks with Uncertain Traffic Demands," ACM Sigmetrics, pages 337-348, 2007.

• Data intensive computing (Shay Ellison/Bradley Neff) /
  • Reading: Kouzes, R.T., Anderson, G.A., Elbert, S.T., Gorton, I., Gracio, D.K., "The Changing Paradigm of Data Intensive Computing," IEEE Computer, 42(1):26-34, Jan. 2009.
  • Reading: Randal E. Bryant, "Data-Intensive Supercomputing: The Case for DISC," TR CMU-CS-07-128, School of Computer Science, CMU, 2007.
• Parallel IO (Jeffery Jestes/Kun Hou)
  • Reading: A. Nisar, Weikeng Liao, A. Choudhary, "Scaling Parallel I/O Performance through I/O Delegate and Caching System," ACM SC'08.
  • Reading: S. Ghemawa, H. gobioff, and S. T. Leung, "The Google File System," ACM SOSP 2003.

Lecture 24 (Nov. 25)

• Group 1 term project presentation (Charles Mcclendon/Matthew Guidry)
• Group 2 term project presentation (Fernando Torres/Peter Chau)
• Group 3 term project presentation (Shay Ellison/Bradley Neff)

• Group 4 term project presentation (Amritpal Singh/Rohith Uppala)
• Group 5 term project presentation (Surjyendy Ray/Yourej Pawar)
• Group 6 term project presentation (Tony Howard/Jaime Mahaffey)

• Group 7 term project presentation (Vanessa Cedeno/Anuja Jain)
• Group 8 term project presentation (Jeffery Jestes/Kun Hou)
• Group 9 term project presentation (Akil Merchant/Vineet Sahu)