8/26 | Course overview and PRAM model
Read Section 27.1 of Intro to Algorithms (CLRS) |
8/28 | Matrix multiplication
Read Section 27.2 of Intro to Algorithms (CLRS) |
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 and watch Ideal Cache Model (Vuduc) and Cache-Oblivious Matrix Multiply (Vuduc) Assignment 1 due |
9/11 | Cache-oblivious dynamic programming
Read Sections 1-2 of Cache-Oblivious Dynamic Programming for Bioinformatics |
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 | Catch-up day |
10/16 | In-class midterm |
10/21 | SUMMA
Read SUMMA: scalable universal matrix multiplication algorithm |
10/23 | MPI collectives
Read Collective communication: theory, practice, and experience |
10/28 | Introduction to MPI programming |
10/30 | Intro to MPI programming (continued)
Project proposals due |
11/4 | MPI in-class programming exercise |
11/6 | MPI in-class programming exercise |
11/11 | TBD |
11/13 | TBD
Assignment 4 due |
11/18 | TBD |
11/20 | TBD |
11/25 | TBD |
11/27 | TBD |
12/2 | TBD |
12/4 | TBD |
12/14 | Final Exam (2pm) |