| 8/26 | Course overview and PRAM model
Read Section 27.1 of Intro to Algorithms (CLRS) Watch Multithreaded Programming (Leiserson) |
| 8/28 | Matrix multiplication
Read Section 27.2 of Intro to Algorithms (CLRS) Watch Multithreaded Algorithms (Leiserson) |
| 9/2 | Mergesort
Read Section 27.3 of Intro to Algorithms (CLRS) |
| 9/4 | Dynamic programming
Watch DP1:LCS and DP2:Knapsack videos from Intro to Graduate Algorithms (Vigoda) |
| 9/9 | Cache models and matrix multiplication
Read Cache-Aware Analysis of Algorithms (Lee) Watch Ideal Cache Model (Vuduc) |
| 9/11 | Cache-oblivious algorithms
Read Sections 1-2 of Cache-Oblivious Dynamic Programming for Bioinformatics Watch Cache-Oblivious Matrix Multiply (Vuduc) Assignment 1 due |
| 9/16 | Introduction to OpenMP
Review slides from OpenMP Basics (Kale) |
| 9/18 | DEAC cluster
Peruse the DEAC User Wiki |
| 9/23 | OpenMP in-class programming exercise |
| 9/25 | OpenMP in-class programming exercise
Assignment 2 due |
| 9/30 | LPRAM model and matrix multiplication
Read Sections 1-2 of Communication Complexity of PRAMs |
| 10/2 | Communication lower bounds for matrix multiplication
Read Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds |
| 10/7 | BSP model and algorithms
Read Sections 1-3 of Scalable Computing |
| 10/9 | BSP sorting
Assignment 3 due |
| 10/14 | In-class midterm |
| 10/16 | Catch-up day Take-home midterm due |
| 10/21 | SUMMA
Read SUMMA: scalable universal matrix multiplication algorithm |
| 10/23 | MPI collectives
Read Collective communication: theory, practice, and experience |
| 10/28 | MPI collectives (continued) |
| 10/30 | Intro to MPI programming
Project proposals due |
| 11/4 | Intro to MPI programming (continued) |
| 11/6 | MPI in-class programming exercise |
| 11/11 | MPI in-class programming exercise |
| 11/13 | MPI in-class programming exercise |
| 11/18 | Sparse matrix-dense vector multiplication (SpMV)
View slides from Parallel Scientific Computing: Section 4.1, Section 4.2, Section 4.3 |
| 11/20 | SpMV continued
Project progress report due |
| 11/25 | Householder QR |
| 11/27 | No class: Thanksgiving break |
| 12/2 | Aditi, Parry, Maruf/Risal, Debashis, Alejandro/William |
| 12/4 | Lisette/Aubrie, J, Chris/Meredith, Nathan |
| 12/14 | Final Exam (2pm) |