CS 594 Understanding Parallel Architectures:
From Theory To Practice
Spring 1999 - 3 credits - Room 655 Buehler

Jack Dongarra, Professor; Shirley Browne, Adjunct Professor; Graham Fagg, Research Assistant Professor; and Erich Strohmaier, Research Assistant Professor

Email: dongarra@cs.utk.edu browne@cs.utk.edu fagg@cs.utk.edu erich@cs.utk.edu
Phone: 423-974-8295
Fax: 423-974-8296
Office hours: Wednesday 11:00 - 1:00, or by appointment

TA: Tinghua Xu, xu@cs.utk.edu, Rm 1-B Ayres Hall

Phone: 423-974-0604

To find out more about this Course click here.


For the Course survey click here.
Lecture Notes: (Tentative outline of the class)
  • Jan 13
    Course Introduction
    Overview of High Performance Computing
    Reading on Overview of Scientific Computing
  • Jan 20
    Message Passing part 1
    Message Passing part 2
  • Jan 27
    PVM/MPI and Beyond
  • Feb 3
    Memory Hierarchy, Cache
  • Feb 10
    HPF and OpenMP
  • Feb 17
    Blocked Linear Algebra
    Reading: Notes on IBM RS6000 Algorithms and Architecture
  • Feb 24
    Linear Algebra Algorithms
  • Mar 3
    Parallel Debugging
  • Mar 10
    Network Enabled Servers
  • Mar 17
    Spring Break
  • Mar 24
    Metacomputing (parts 1 , 2 , 3 )
  • Mar 31
    The rest of MetaComputing, MPI-2 and Parallel I/O. Parts 1 , 2 and 3 . The homework for this part is here . This work is to be completed by the 21st of April.
  • Apr 7
    Performance Optimization Techniques Part 1
  • Apr 14
    Performance Optimization Techniques Part 2
  • Apr 21
    Performance Modeling of Parallel Applications
  • Apr 28
    Scalability Analysis
  • May 5
    Reports from Class Projects
  • May ? Final exam

  • Assignments
  • Homework 1: Due 2/2/99
    Home Work problems to be solved. Example diagram of the problem examined.
    The final work should be emailed to Graham Fagg by the end of Tuesday the 2nd of Feburary.
    Note. This is a writen piece that should contain psudeo code only, no extra points for implementing any of this one.

    Solutions to the first home work are here .

  • Homework 2: Due 2/9/99
    Programming Home Work problems to be solved. The final work should be emailed to Graham Fagg by the end of Tuesday the 9nd of Feburary.

    Remember to use the handout reference cards.
    Other usefull stuff includes a basic version of calculating pi in C code.
    A Makefile.aimk that allows you to make PVM executables in any directory.
    You should use this file. (To test just do an aimk pi ; rehash ; pi )

  • Homework 3: Due 2/17/99
    Programming Home Work problems to be solved. The final work should be turned into class to the TA on Wednesday the 17th of Feburary.

  • Homework 4: Due 2/17/99
    Home Work problems to be solved. The final work should be turned into class to the TA on Wednesday the 17th of Feburary.

  • Homework 5: Due 3/3/99
    Home Work problems to be solved. The final work should be turned into class to the TA on Wednesday the 3rd of March.

  • Homework 6: Due 3/10/99
    Home Work problems to be solved. The final work should be turned into class to the TA on Wednesday the 10th of March.

  • Homework 7: Due 3/24/99
    Home Work problems to be solved. The final work should be turned into class to the TA on Wednesday the 24th of March.

  • Homework 9: Due 4/28/99
    Home Work problems to be solved. The final work should be turned into class to the TA on Wednesday the 28th of April

  • Projects (due May 5, 1999) Preliminary list of projects click here.


  • Additional Reading/Materials

    Message Passing Systems.

    The PVM home page.
    A duplex postcript version of the PVM API (3.3)

    The MPI home page.
    This is the best place to get info on MPI from, including implementations and the MPI forum itself.

    The implementation that you should use, that is installed on the TORC cluster is MPICH .
    A duplex postcript version of the MPI 1.1 API (with thanks to the LAM team).


    Other useful reference material


  • A good introduction to message passing systems.


    J.J. Dongarra, G.E. Fagg, R. Hempl and D. Walker, Chapter in Wiley Encyclopedia of Electrical and Electronics Enginerring,
    to appear. ( postscript version )

    ``Message Passing Interfaces'', Special issue of Parallel Computing , vol 20(4), April 1994.

  • A paper by members of the PVM team on the differences between PVM and MPI.

    Geist, G.A, J.A. Kohl, P.M. Papadopoulos, `` PVM and MPI: A Comparison of Features '', Calculateurs Paralleles , 8(2), pp. 137--150, June, 1996. ( postscript version )

  • Papers by members of the MPI team on the differences between PVM and MPI.

    ``Why are PVM and MPI So Different'', William Gropp and Ewing Lusk (submitted to The Fourth European PVM - MPI Users' Group Meeting)

    and

    ``PVM and MPI are completely different'', William Gropp and Ewing Lusk, to appear in the journal Future Generation Computer Systems, 1998.



    Standard Books on Message Passing

    ``MPI - The Complete Reference, Volume 1, The MPI-1 Core, Second Edition'',
    by Marc Snir, Steve Otto, Steven Huss-Lederman, David Walker, Jack Dongarra, MIT Press, September 1998, ISDN 0-262-69215-5.

    ``Using MPI,''
    by William Gropp, Ewing Lusk, and Anthony Skjellum, published by MIT Press, October 1994; ISBN 0-262-57104-8.

    ``MPI: The Complete Reference - 2nd Edition: Volume 2 - The MPI-2 Extensions'',
    by William Gropp, Steven Huss-Lederman, Andrew Lumsdaine, Ewing Lusk, Bill Nitzberg, William Saphir, and Marc Snir, published by The MIT Press, September, 1998; ISBN 0-262-57123-4.


    Class Roster If your name is not on the list or some information is incorrect, please send mail to TA: Tinghua Xu, xu@cs.utk.edu.
    Student Names and Their Email addresses
    Antonin Bukovsky: bukovsky@cs.utk.edu.
    Hui Ji: ji@cs.utk.edu.
    Lawrence MacIntyre: lpz@ornl.gov.
    Keita Teranish: teranish@cs.utk.edu.
    John Thurman: thurman@cs.utk.edu.
    Tinghua Xu: xu@cs.utk.edu

    On-line Documentation and Information about Machines

  • Cray
  • IBM RS6000
  • Intel
  • Intel ASCI Red Paragon
  • SGI Power Challenge
  • Solaris Threads page
  • Catalog of Commercial Hardware and Software Vendors
  • Convex
    • Exemplar
    • Michielse, P. Programming the Convex Exemplar Series SPP system. Parallel Scientific Computing. First International Workshop, PARA '94. Proceedings. Lyngby, Denmark, 20-23 June 1994). Edited by: Dongarra, J.; Wasniewski, J. Berlin, Germany: Springer-Verlag, 1994. p. 374-82.
  • Cray Research
  • Digitial Equipment Corporation ( System Info
  • Hewlett-Packard
  • IBM
  • Sequent
    • Symmetry 5000
    • NUMA-Q
    • Raetz, G.M., Sequentz, G.M., Sequent general purpose parallel processing system, Northcon/87. Conference Record. Portland, OR, USA, 22-24 Sept. 1987)
  • Silicon Graphics
    • Power Challenge
    • Power Challenge (Techical Report)
    • Challenge XL
    • Galles, M.; Williams, E. Performance optimizations, implementation, and verification of the SGI Challenge multiprocessor. Proceedings of the Twenty-Seventh Hawaii Internation Conference on System Sciences Vol. I: Architecture, Wailea, HI, USA, 4-7 Jan. 1994, Edited by: Mudge, T.N.; Shriver, B.D. Los Alamitos, CA, USA: IEEE Comput. Soc. Press, 1994. p. 134-43.
    • Power Series
  • Sun Microsystems

  • Other Parallel Information Sites
  • NHSE - National HPCC Software Exchange
  • Netlib Repository at UTK/ORNL
  • BLAS Quick Reference Card
  • LAPACK
  • ScaLAPACK
  • GAMS - Guide to Available Math Software
  • Center for Research on Parallel Computation (CRPC)
  • Supercomputing & Parallel Computing: Conferences
  • Supercomputing & Parallel Computing: Journals
  • High Performance Fortran (HPF) reports
  • High Performance Fortran Resource List
  • Fortran 90 Resource List
  • CMU's list of supercomputing and parallel computing resources
  • Major Science Research Institutions from Caltech
  • Message Passing Interface (MPI) Forum
  • High Performance Fortran Forum
  • OpenMP
  • PVM
  • Parallel Tools Consortium
  • DoD High Performance Computing Modernization Program
  • DoE Accelerated Strategic Computing Initiative (ASCI)
  • National Computational Science Alliance

  • Related On-line Textbooks
  • Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM Publication, Philadelphia, 1994.
  • PVM - A Users' Guide and Tutorial for Networked Parallel Computing, MIT Press, Boston, 1994.
  • MPI : A Message-Passing Interface Standard
  • LAPACK Users' Guide (Second Edition), SIAM Publications, Philadelphia, 1995.
  • MPI: The Complete Reference, MIT Press, Boston, 1996.
  • Using MPI: Portable Parallel Programming with the Message-Passing Interface by W. Gropp, E. Lusk, and A. Skjellum
  • Parallel Computing Works, by G. Fox, R. Williams, and P. Messina (Morgan Kaufmann Publishers)
  • Computational Science Education Project TextBook.
  • Designing and Building Parallel Programs. A dead-tree version of this book is available by Addison-Wesley.
  • High Performance Fortran (HPF), a course offered by Manchester and North High Performance Computing Training & Education Centre, United Kingdom
  • Parallel Processing Laboratory, Colorado School of Mines
  • For performance analysis:

  • Raj Jain, The Art of Computer Systems Performance Analysis. John Wiley, 1991.
  • Papers on performance analysis tools:

  • Ruth A. Aydt, "The Pablo Self-Defining Data Format," November 1997, click here.
  • Daniel A. Reed, Ruth A. Aydt, Tara M. Madhyastha, Roger J. Noe, Keith A. Shields, and Bradley W. Schwartz, "Pablo: An Extensible Performance Analysis Environment for Parallel Systems", November 1992, click here.
  • Jeffrey K. Hollingsworth, Barton P. Miller, Marcelo J. R. Gongalves, Oscar Naim, Zhichen Xu and Ling Zheng, "MDL: A Language and Compiler for Dynamic Program Instrumentation", International Conference on Parallel Architectures and Compilation Techniques, San Francisco, CA, November 1997, click here.
  • Barton P. Miller, Mark D. Callaghan, Jonathan M. Cargille, Jeffrey K. Hollingsworth, R. Bruce Irvin, Karen L. Karavanic, Krishna Kunchithapadam and Tia Newhall. "The Paradyn Parallel Performance Measurement Tools", IEEE Computer 28(11), (November 1995). click here.
  • Steven T. Hackstadt and Allen D. Malony, "Distributed Array Query and Visualization for High Performance Fortran, February 1996, click here.
  • Jerry Yan and Sekhar Sarukkai and Pankaj Mehra, "Performance Measurement, Visualization and Modeling of Parallel and Distributed Programs using the AIMS toolkit", Software Practice and Experience 25(4), April 1995, 429--461
  • Jack Dongarra
    1/11/99