Parallel Algorithms

PRAM Algorithms

8/23	Course overview and PRAM model Read Section 27.1 of Intro to Algorithms (CLRS)
8/25	Matrix multiplication Read Section 27.2 of Intro to Algorithms (CLRS)

8/30	Mergesort Read Section 27.3 of Intro to Algorithms (CLRS)
9/1	Dynamic programming Watch DP1:LCS and DP2:Knapsack videos from Intro to Graduate Algorithms (Vigoda)

Data Locality

9/6	Cache models and matrix multiplication Read Cache-Aware Analysis of Algorithms and watch Ideal Cache Model (Vuduc) and Cache-Oblivious Matrix Multiply (Vuduc) Assignment 1 due
9/8	Cache-oblivious dynamic programming Read Sections 1-2 of Cache-Oblivious Dynamic Programming for Bioinformatics

OpenMP

9/13	Introduction to OpenMP Review slides from OpenMP Basics (Kale)
9/15	DEAC cluster Peruse the DEAC User Wiki

9/20	OpenMP in-class programming exercise
9/22	OpenMP in-class programming exercise Assignment 2 due

LPRAM

9/27	LPRAM model and matrix multiplication Read Sections 1-2 of Communication Complexity of PRAMs
9/29	Communication lower bounds for matrix multiplication Read Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds

BSP

10/4	BSP model and algorithms Read Sections 1-3 of Scalable Computing
10/6	BSP sorting Assignment 3 due

10/11	In-class midterm
10/13	Fall Break

MPI Model

10/18	SUMMA Read SUMMA: scalable universal matrix multiplication algorithm
10/20	MPI collectives Read Collective communication: theory, practice, and experience Midterm takehome due

MPI Programming

10/25	Collectives (continued)
10/27	Introduction to MPI programming Project proposals due

11/1	MPI in-class programming exercise
11/3	MPI in-class programming exercise

Scientific Computing

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

11/15	QR decomposition Read draft Orthogonalization chapter from Communication-Avoiding Algorithms (available in Canvas)
11/17	QR continued

Data Analysis

11/22	Nonnegative Matrix Factorization Read The Why and How of Nonnegative Matrix Factorization (Gillis)
11/24	Thanksgiving Break

11/29	NMF continued Read MPI-FAUN: An MPI-Based Framework for Alternating-Updating Nonnegative Matrix Factorization Assignment 4 due
12/1	No class

12/10

Final Exam (9am): Project presentations