CMSC858N: Spring 2023
Time and Location: Tuesday/Thursday, 2–3:15pm, CSI 2107
Instructor: Laxman Dhulipala (IRB 5150)
This is a research-oriented course on parallel algorithms. The main goal is to develop a rigorous understanding of parallel algorithm design and analysis. The later parts of the course will study a variety of applications which can benefit from fast, scalable, and theoretically-efficient parallel implementations.
This course qualifies as a theory concentration requirement.
Prerequisites: You should be comfortable with algorithm design and analysis (e.g., you should be comfortable with the material from CMSC451). Prior experience with C++ will be helpful, but you should be able to pick up everything you need to know during this course.
| Date | Topic | Readings | Notes |
|---|---|---|---|
| Jan 26 (Th) | Brief History of Parallel Computing and Parallel Models | ||
| Algorithms on Sequences | |||
| Jan 31 (Tu) | Parallel Building Blocks, Basic Algorithms | ||
| Feb 02 (Th) | Merging and Sorting | ||
| Feb 07 (Th) | Integer Sorting: Counting and Radix Sort [HW1 out] | ||
| Algorithms on Trees | |||
| Feb 09 (Th) | List Ranking and Tail Bounds | ||
| Feb 14 (Tu) | Tree Contraction | ||
| Feb 16 (Th) | Lowest Common Ancestors | ||
| Feb 21 (Tu) | Dynamic Forest Connectivity [HW1 due, HW2 out] | ||
| Algorithms on Graphs | |||
| Feb 23 (Th) | BFS and Low-Diameter Decomposition | ||
| Feb 28 (Tu) | Boruvka, Random-Mate, and Work-Efficient Connectivity | ||
| Mar 02 (Th) | Luby’s Algorithm for MIS and Derandomization | ||
| Mar 07 (Tu) | Randomized Incremental MIS and Matching | ||
| Mar 09 (Th) | LE Lists and Strongly Connected Components [HW2 due] | ||
| Mar 14 (Tu) | Weighted Matching (Distributed Primal-Dual) [Midterm Out] | ||
| Mar 16 (Th) | Coreness and Densest Subgraphs [Midterm Due] | ||
| Spring Break | |||
| Scheduling and Models | |||
| Mar 28 (Tu) | Work-Stealing and Analysis [HW3 out] | ||
| Mar 30 (Th) | Parallel Cache-Oblivious Algorithms | ||
| Apr 04 (Tu) | Parallel In-Place Algorithms | ||
| Apr 06 (Th) | Massively Parallel Computation (MPC): Basics | ||
| Advanced Topics and Applications | |||
| Apr 11 (Tu) | Suffix Arrays [Project Check-in 1] | ||
| Apr 13 (Th) | LCP, Range Trees, and Suffix Trees | ||
| Apr 18 (Tu) | Binary-Forking Algorithms | ||
| Apr 20 (Th) | Block-Delayed Sequences [HW3 due] | ||
| Apr 25 (Tu) | GPU Algorithms | ||
| Apr 27 (Th) | Concurrent Key-Value Stores [Project Check-in 2] | ||
| May 02 (Tu) | Vector-Search: HNSW and Vamana | ||
| May 04 (Th) | Parallelism in Deep Learning and Accelerators | ||
| May 09 (Tu) | Discussion: Scale-Out or Scale-Up? Open-Problem Session. | ||
| May 11 (Th) | Project Presentations |
Any student eligible for and requesting reasonable academic accommodations due to a disability is requested to provide, to the instructor in office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester.
Some topics are drawn from recent courses by Umut Acar, Soheil Behnezhad, Guy Blelloch, Mohsen Ghaffari, Yan Gu, Julian Shun, and Yihan Sun. I am grateful to my colleagues for making their courses publicly available, and encourage new courses to make course material freely available (e.g., not on Piazza) as much as possible.