Here is the schedule for this class. Slides, videos and other materials will be added.
Week
|
Date
|
Lecture
|
Assignments
|
Readings
|
3
|
1/11
|
Introduction & Course overview
|
Assignment 1: Sequential Coding
|
Intro to Sequential Algorithms
Intro to Parallel Algorithms
Parallel Algorithms
|
|
|
1/13
|
Performance & Scalability
|
|
Flynn’s Taxonomy
Amdahl’s law multicore era
Gustafson’s take on Amdahl
Limits on fundamental limits to computation
|
|
4
|
1/18
|
MLK Day
|
Assignment 1 Due
|
|
|
|
1/20
|
Parallel Thinking, OpenMP
|
Assignment 2: OpenMP
|
Intro to Parallel Algorithms
Parallel Computing - Blaise Barney, LLNL
PRAM Algorithms
|
|
5
|
1/25
|
OpenMP
|
|
OpenMP Tutorial - LLNL
Guide to OpenMP
|
|
|
1/27
|
PRAM Scan, Reduce, MatVec
|
|
Prefix Sums & Applications
|
6
|
2/1
|
Thread Sanitizer
|
|
Thread Sanitizer
|
|
|
2/3
|
Topology, Network Models
|
Assignment 2 Due
|
|
|
7
|
2/8
|
CHPC Resources & Parallel Debugging
|
Assignment 3: MPI
|
MPI Introduction
MPI Reference
|
|
|
2/10
|
MPI, Collective Communications
|
|
Optimizing Collective Communications
|
|
8
|
2/15
|
Presidents Day
|
|
|
|
|
2/17
|
MPI : Live Coding
|
|
|
|
9
|
2/22
|
Search, Ranking, Merge, Sorting
|
|
Parallel k-Select
|
|
|
2/24
|
Bitonic Sort
|
Assignment 3 Due
|
Parallel Sorting
open-mpi debugging FAQ
Debugging Parallel Programs
|
Discrete Algorithms
|
|
10
|
2/29
|
Overlapping Communication & Computations
|
Assignment 4: Sorting
|
Advanced MPI tutorial
|
|
|
3/2
|
Randomized Algorithms, Graph Coloring
|
|
|
|
11
|
3/7
|
Hypercube Quicksort, Samplesort
|
|
HykSort - My recent paper on scalable sorting
|
|
|
3/9
|
Midterm
|
Assignment 4 Due
Select final project (Assignment 5)
|
|
|
12
|
|
Spring Break
|
|
|
|
13
|
3/21
|
Trees, Quadtrees & Octrees
|
|
Fast Algorithms using Trees
|
|
|
3/23
|
Graphs, Traversals, BFS, DFS
|
|
Karypis Chapter 10
|
|
14
|
3/28
|
Graph Coloring
|
Initial report on Final Project due
|
Luby’s paper on MIS and Graph Coloring
parallel random numbers
Randomized Algorithms
|
Numerical Algorithms
|
|
14
|
3/30
|
Vectors, Matrices, Products
|
Assignment 6: Matrices & Graphs
|
|
|
15
|
4/4
|
Matrix Multiplication, LU
|
|
Matrix Multiplication
|
|
|
4/6
|
LU, Cholesky
|
|
Gaussian Elimination, Cholesky
|
|
16
|
4/11
|
Tridiagonal matrices, cyclic reduction
|
Assignment 6 due
|
|
|
|
4/13
|
Fast Fourier Transform
|
|
Solving the Discrete Poisson Equation
|
|
17
|
4/18
|
\(n\)-body problems, Barnes Hut
|
|
Prof. Demmel’s notes on the N-body Problem
|
|
|
4/20
|
\(n\)-body problems, FMM
|
|
Prof. Demmel’s notes on FMM
|
|
18
|
4/25
|
|
|
|
|
19
|
5/4
|
Exam week
|
Final Project Due
|
|