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

OpenMP

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

BSP

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

Sorting

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)