Parallel Algorithms

PRAM Algorithms

8/27 Course overview and PRAM model
Read: Section 1 of Multithreaded Programming
8/29 Matrix multiplication
Read: Section 2.1 of Multithreaded Programming

9/3 Mergesort
Read: Section 2.2 of Multithreaded Programming
9/5 Prefix sums
Read: Sections 1.1-1.2 of Prefix Sums and Their Applications

Data Locality

9/10 I/O Models and matrix multiplication
Read Sections 1, 2, and 7 of Cache-Oblivious Algorithms
and watch Ideal Cache Model
9/12 Dynamic programming


9/17 Cache-oblivious dynamic programming
Read Sections 1-2 of Cache-Oblivious Dynamic Programming for Bioinformatics
9/19 Introduction to OpenMP

OpenMP Programming

9/24 DEAC Cluster
9/26 OpenMP programming: Knapsack assignment

LPRAM Algorithms

10/1 LPRAM model and matrix multiplication
Read Sections 1-2 of Communication Complexity of PRAMs
10/3 OpenMP Exercise: Parallel Mergesort
OpenMP Programming Assignment due

10/8 Midterm
10/10 Fall Break


10/15 BSP model and algorithms
Read Sections 1-3 of Scalable Computing
10/17 BSP matrix multiplication
Read Memory-Efficient Matrix Multiplication in the BSP Model

MPI Model

10/22 SUMMA
Read SUMMA: scalable universal matrix multiplication algorithm
Midterm corrections due
10/24 MPI collectives
Read Collective communication: theory, practice, and experience
MPI programming assignment part 1 due (10/26)

MPI Programming

10/29 Introduction to MPI
10/31 Collectives and dense matrix-vector multiplication
Project proposals due

11/5 No class
11/7 No class
MPI programming assignment part 2 due

Numerical Algorithms

11/12 Sparse matrix-dense vector multiplication (SpMV)
View slides from Parallel Scientific Computing:
Section 4.1, Section 4.2, Section 4.3
11/14 GEMV and SpMV continued

11/19 QR decomposition
Read Sections I-III of Reconstructing Householder Vectors from Tall-Skinny QR
11/21 QR continued


11/26 Sample/histogram sorting and AllToAll collective
11/28 Thanksgiving Break

Project Presentations

12/3 Sarah, Irina/Ziqin, Gabe, Esteban/Patrick
12/5 Lawton, Jinku/Fred, Dylan

12/9 Final Exam (2pm)