Parallel Programming Practice

Class

Instructor

Sathish Vadhiyar

Books

• The Sourcebook of Parallel Computing
   by Jack Dongarra (Editor), Ian Foster, Geoffrey Fox (Editor), Ken Kennedy, Andy White (Editor), Linda Torczon, Wiliiam Gropp Publisher: Morgan Kaufmann; (November 2002) ISBN: 1-558-60871-0
• Introduction to Parallel Computing
  by  Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar Publisher: Addison Wesley; (2003) ISBN: 0-201-64865-2
• Numerical Linear Algebra for High Performance Computers
  by  Jack Dongarra, Iain Duff, Danny Sorensen, Henk van der Vorst Publisher: SIAM; (1998) ISBN: 0-89871-428-1 

Syllabus

1. Introduction
   1. Scope of parallel computing
   2. Definitions of speedup, utilization, efficiency, scalability
   3. Amdahl's law - Parallel Processing
   4. Parallel architecture models , physical organization of parallel platforms
   5. Parallel programming paradigms, algorithm models
   6. Communication costs in parallel machines
   7. Principles of parallel algorithm design - Preliminaries, Decomposition techniques, Data distribution methods, Mapping techniques for load balancing
   8. Analytical modeling of parallel programs - Sources of overhead in parallel programs, Performance metrics for parallel programs, Asymptotic analysis of parallel programs, Other scalability metrics, Communication costs in parallel machines
2.  Programming using the Message passing paradigm
   1. Principles of message-passing programming
   2. MPI: The Message Passing Interface
   3. Point-point, collectives
   4. Groups and communicators
   5. Process topologies
   6. Profiling interface
   7. Collective communication implementations
   8. MPI-2 overview
   9. An extended session on MPI I/O
3. A Few Parallel Programs
1. Vibrating string, Laplace equation, Molecular dynamics, WaTor
4. Programming shared address space platforms
1. Thread basics
2. OpenMP: A standard for directive based parallel programming
6. Linear algebra
1. Matrix-vector multiplication
2. Matrix-matrix multiplication
3. Solving a system of linear equations
4. Brief look at BLAS, LAPACK, ScaLAPACK
5. Iterative methods for linear systems - Parallel conjugate gradient
6. Parallel preconditioning
7. Eigenvalue problems - parallel aspects
8. Sparse solutions
   1. Sparse matrix direct methods
   2. Multifrontal methods
   3. Iterative methods
9. Templates and linear algebra
7. Other topics
1. Load balancing and scheduling
2. Parallel FFT
3. Parallel Checkpointing
4. LinPack, HPLinPack, Top500, NPB

Assignments

Small:

1. Parallel Programming Metrics

2. Communicators

3. Parallel Matrix Transpose by Dongarra, Sorensen

4. Bin-Pack Mapping

5. OpenMP Assignment

6. Parallel FFT

7. MPI-IO, OpenMP

Large:

1. Fundamental Concepts, point-point benchmarking, collective communication implementations

2. Molecular Dynamics Simulation and Load Balancing

3. Matrix-Matrix multiplication

4. Sparse Matrix-Vector Multiplication

5. Jacobi iterations for 3D Laplace equations

6. Parallel Conjugate Gradient

7. Parallel Ordering Using Kernighan-Lin

8. Parallel Ordering Using Level Structures

Final Project

• Parallelization of linear algebra algorithms
• Modeling Collectives
• Pipelining and blocking approaches for linear algebra routines - the right approach
• Developing simulation models of some parallel routines
• Inter-disciplinary parallel applications
• Detailed study of FFTW
• Sparse matrices - implementation of fast parallel reordering by Liu
• Sparse matrices - mapping tasks of elimination trees to processors
• LinPack and NAS parallel benchmark on parallel systems in SERC
• Molecular Dynamics - Implementing advanced algorithms and carrying out various observations