CS 594
Understanding Parallel Architectures:
From Theory To Practice

Jack Dongarra, Professor, Spring 2002 3 credits

This course is aimed at providing students with a deep knowledge of the techniques and tools needed to understand today's and tomorrow's high performance computers, and to efficiently program them. A mixture of theoretical and practical material will be provided.

Today's high performance computers range from expensive highly parallel distributed memory platforms down to cheap local networks of standard workstations. But the problems associated with software development are the same on all architectures: the user needs to recast his or her algorithm or application in terms of parallel entities (tasks, processes, threads, or whatever) that will execute concurrently. Parallelism is difficult to detect in an automatic fashion because of data dependencies. In many cases, one needs to perform some form of algorithm restructuring to expose the parallelism. Finally, to realize the restructured algorithm in terms of software on a specific architecture may be quite complicated.

Fortunately, there are well-established techniques and tools to help: portable computation libraries such as ScaLAPACK, portable communication libraries like MPI, general-purpose task systems such as PVM, or even data-parallel languages like HPF. These are the tools that the class targets.

In this course we plan to cover and understand the nuts and bolts of developing parallel applications. For instance our study of PVM goes with the foundations of task graph scheduling, that of MPI with the complexity analysis of collective communication operations like broadcasts etc, and that of HPF with data dependence analysis and automatic parallelization techniques. In addition we will study performance evaluation and benchmarking on today's high-performance computers. Each lecture of the class will make use of simple examples borrowed from numerical linear algebra. Matrix-matrix multiplication or LU decomposition will provide the framework needed to illustrate the theory.

Target audience is mainly computer science students. Students from other disciplines are welcome, provided they have a computer science background in the following areas: machine architecture, algorithm design, elementary graph algorithms, and complexity analysis.

Grading will be based:

• 30% on weekly homework (the lowest homework grade will be dropped)
• 30% on a written report and presentation(20 pages circa.) (The idea is to read three or four papers from the literature (references will be provided), and to synthesize them in terms of a report, (News ideas and extensions are welcome, as well as an eventual little prototype implementation if adequate.)
• 30% on a final exam,
• 10% on class participation.

There will be no substantial project on parallel programming, unless requested by a student willing to implement his particular application on a parallel machine (that would replace the report).

Tentative outline of the class is the following:

1. Overview of High Performance Computing
2. PVM/MPI
3. Memory Hierarchy, Cache
4. HPF and OpenMP
5. Blocked linear algebra
6. Linear Algebra Algorithms
7. Parallel Performance Analysis Tools
8. Network Enabled Servers
9. Metacomputing
10. Performance Optimization Techniques
11. Performance Optimization Techniques
12. Class Projects
13. Performance Modeling of Parallel Applications
14. Scalability Analysis

There is no book covering the scope of the class. But for each lecture a comprehensive document will be made available in postscript. A short bibliography is given below.

 
• References
• About this document ...