| 8/24 |
Course introduction and overview |
| 8/26 |
PRAM model Read Section 27.1 of Intro to Algorithms (CLRS) Watch Multithreaded Programming (Leiserson) |
| 8/31 |
Matrix multiplication and mergesort Read Sections 27.2-27.3 of Intro to Algorithms (CLRS) Watch Multithreaded Algorithms (Leiserson) |
| 9/2 |
Dynamic programming Read Visualizing Parallel Dynamic Programming using the Thread Safe Graphics Library |
| 9/7 | No class: Labor Day |
| 9/9 |
Cache models and matrix multiplication Read Cache-Aware Analysis of Algorithms (Lee) Watch Ideal Cache Model (Vuduc) Assignment 1 due |
| 9/14 |
Cache-oblivious algorithms Watch Cache-Oblivious Matrix Multiply (Vuduc) |
| 9/16 |
Cache-oblivious algorithms for dynamic programming Read Sections 1-2 of Cache-Oblivious Dynamic Programming for Bioinformatics |
| 9/21 |
Introduction to OpenMP Review slides from OpenMP Basics (Kale) |
| 9/23 |
OpenMP in-class programming exercise Peruse the DEAC User Wiki |
| 9/28 | OpenMP in-class programming exercise |
| 9/30 |
LPRAM model and matrix multiplication Read Sections 1-2 of Communication Complexity of PRAMs Assignment 2 due |
| 10/5 |
Communication lower bounds for matrix multiplication Read Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds |
| 10/7 | LPRAM lower bounds and algorithms (continued) |
| 10/12 | No class: Fall break |
| 10/14 | In-class Midterm |
| 10/19 |
BSP model and algorithms Read Sections 1-3 of Scalable Computing |
| 10/21 |
BSP Strassen Read Section 4 of Memory-Efficient Matrix Multiplication in the BSP Model |
| 10/26 |
BSP sorting Read Sections 1-3 of Parallel Sorting by Regular Sampling |
| 10/28 |
SUMMA Read SUMMA: scalable universal matrix multiplication algorithm Assignment 3 due |
| 11/2 |
MPI collectives Read Collective communication: theory, practice, and experience |
| 11/4 |
Catch-up |
| 11/9 | Intro to MPI programming |
| 11/11 | MPI in-class programming exercise Project proposals due |
| 11/9 | MPI in-class programming exercise |
| 11/11 | MPI in-class programming exercise |
| 11/16 |
Sparse matrix-dense vector multiplication (SpMV) View slides from Parallel Scientific Computing: Section 4.1, Section 4.2, Section 4.3 |
| 11/18 |
SpMV continued Project progress report due |
| 11/23 | Householder QR |
| 11/25 | No class: Thanksgiving break |
| 11/30 | TBD |
| 12/2 | TBD |
| 12/7 | TBD |
| 12/14 | Final Exam (2pm) |