PP Syllabus

Kaushik Datta

1.  Numerical Algorithms (Ref. [2], [4], [7])

• Dense Matrix Multiplication- serial and parallel ([2] Ch. 3)

• Sparse Matrix-Vector Multiplication- serial and parallel ([4] and [7])

• Direct Solvers - Dense LU Factorization- serial and parallel ([2] parts of Ch. 6 and 7)

• Iterative Solvers - Jacobi, Gauss-Seidel, Multigrid- serial and parallel ([2] Ch. 8)

2.  Computer Architecture (Ref. [3])

• Memory Hierarchy Design ([3] Ch. 5)

• Multiprocessors and Thread-Level Parallelism ([3] Ch. 6)

3.  Depth Topic - Optimizing 3D Multigrid Performance (Ref. [1], [5], [6])

• Cache Tiling ([5])

• Temporal Blocking ([6])

• Parallelization Strategies ([1])

• Here is a link to work on this topic from last semester (which I am continuing right now): CS252 project

References (in addition to the appropriate CS267 lectures)

[1]  Briggs, William L., A Multigrid Tutorial, Society for Industrial and Applied Mathematics, Lancaster, PA, 1987.

[2]  Golub, Gene and James M. Ortega.  Scientific Computing- An Introduction with Parallel Computing, Academic Press, San Diego, CA, 1993.

[3]  Hennessy, John L. and David A. Patterson.  Computer Architecture- A Quantitative Approach (Third Edition), Morgan Kaufman Publishers, San Francisco, CA, 2003.

[4]  Im, Eun-Jin and Katherine Yelick, "Model-Based Memory Hierarchy Optimizations for Sparse Matrices".

[5]  Rivera, Gabriel and Chau-Wen Tseng, "Tiling Optimizations for 3D Scientific Computing".

[6]  Sellappa, Sriram and Siddhartha Chatterjee, "Cache-Efficient Multigrid Applications".

[7] Shewchuk, Johnathan R. et al, "Automated Parallel Solution of Unstructured PDE Problems".