Parallel Programming (3:1)

The objective of this course is to give you some level of confidence in parallel programming techniques, algorithms and tools. At the end of the course, you would (we hope) be in a position to deal with real-life parallel  problems and to explore new avenues of research in the area of parallel programming.

Class

Instructor

Sathish Vadhiyar

Books

• Introduction to Parallel Computing
  by  Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar Publisher: Addison Wesley; (2003) ISBN: 0-201-64865-2
• 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
• 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. Motivations for parallel programming
   2. Challenges
   3. Metrics - speedup, utilization, efficiency, scalability
   4. Amdahl's law and Gustaffson's law
   5. Parallel architecture models , physical organization of parallel platforms
   6. Parallel programming paradigms, algorithm models
   7. Communication network topology in parallel machines
2.  Programming using the Message passing paradigm MPI-1
   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. OpenMP: A standard for directive based parallel programming
2. hybrid programming
6. Parallel Dense Linear algebra
   1. Solving a system of linear equations - Gaussian elimination
   2. Parallel Cholesky factorization
   3. Tridiagonal solve
   4. conjugate gradient
7. Parallel Sparse Linear algebra
1. Sparse Linear Algebra - basics and sequential solutions
2. parallel steps for ordering, symbolic factorization, numerical factorization, triangular solve
3. Parallel Kernighan-Lin, Nested dissection
4. sparse iterative methods
5. parallel graph coloring
8. Other Topics
1. FFT
2. Bioinformatics
3. Scheduling

Assignments

1. Implementation of collective communication algorithms
2. Matrix-Matrix Multiplication
3. Gauss-Seidel
4. Data and Loop Level Parallelism

Links

• Designing and Building Parallel Programs. Ian Foster