CMSC858N: Spring 2023
Time and Location: Tuesday/Thursday, 2–3:15pm, CSI 2107
Instructor: Laxman Dhulipala (IRB 5150); Office hours 3:15--4:15pm Tu/Th in IRB 5150
TA: Kishen Gowda (IRB 2104); Office hours 4--5pm Wed outside IRB 2104
Piazza: https://piazza.com/class/ld9jh8yfgtilr
Gradescope: https://www.gradescope.com/courses/504225
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 | ParAlg [Ch.1--2] | Notes |
| lgorithms on Sequences | |||
| Jan 31 (Tu) | Parallel Building Blocks, Basic Algorithms | ParAlg [Ch.4] | Notes |
| Feb 02 (Th) | Merging and Sorting | ParAlg [Ch.4] | Notes |
| Feb 07 (Tu) | Integer Sorting: Counting and Radix Sort [HW1(W) out] |
RegionsSort | Notes |
| Algorithms on Trees | |||
| Feb 09 (Th) | List Ranking and Tail Bounds | ParAlg [Ch.3] | Notes |
| Feb 14 (Tu) | Euler Tours and Parallel Tree Contraction | Notes | |
| Feb 16 (Th) | LCA and RMQ [[HW1(P)] out] |
||
| Feb 21 (Tu) [No Class -- Prerecorded Lecture] | Parallel Cartesian Trees [HW1(W) due] |
||
| Algorithms on Graphs | |||
| Feb 23 (Th) | BFS and Low-Diameter Decomposition | Notes | |
| Feb 28 (Tu) | No Class | ||
| Mar 02 (Th) | LDD Continued | Notes | |
| Mar 07 (Tu) | LDD Applications | Notes | |
| Mar 09 (Th) | Luby's Algorithm [HW1(P) due] |
Notes | |
| Mar 14 (Tu) | Randomized Algorithms Recap |
||
| Mar 16 (Th) | Random Incremental Algorithms |
||
| Spring Break | |||
| Scheduling and Models | |||
| Mar 28 (Tu) | Work-Stealing and Analysis | ||
| Mar 30 (Th) | Parallel Cache-Oblivious Algorithms
[HW2(W) due] |
||
| Apr 04 (Tu) | Parallel In-Place Algorithms | ||
| Apr 06 (Th) | Massively Parallel Computation (MPC): Basics | ||
| Other Topics and Applications (subject to change) | |||
| Apr 11 (Tu) | Optimal Binary-Forking [Project Check-in] |
||
| Apr 13 (Th) | Parallel Batch-Dynamic Trees | ||
| Apr 18 (Tu) | Graph Compression: Formats and Reordering | ||
| Apr 20 (Th) | Parallel Graph Processing: Julienne and GBBS | ||
| Apr 25 (Tu) | Guest Lecture by Brian Wheatman: SIMD and Vectorization | ||
| Apr 27 (Th) | Parallel Algorithms for Ordered Sets and Maps [Project Check-in] |
||
| May 02 (Tu) | Compressed and Augmented Maps | ||
| May 04 (Th) | Batch-Dynamic Algorithms: Forest Connectivity | ||
| May 09 (Tu) | Batch-Dynamic Algorithms: Dynamic Connectivity | ||
| May 11 (Th) | Project Presentations |
We will follow the masking and health guidelines laid out by the University. Note that masking is still recommended: “Effective Monday, August 29, wearing a mask will not be required while indoors in most situations, including classrooms. However, wearing a KN95 mask is recommended while indoors for added protection.”
Your education is very important to us, and we respect each of you regardless of how you do in the class. Our expectations of you are that you attend class and pay full attention, and give enough time to the course. We strongly encourage you to ask questions in class, and to come to the office hours (the instructors’ or the TAs’) with any further questions. We can have a very enjoyable educational experience if you pay attention in class, give sufficient time to our course, and bring any difficulties you have promptly to our attention. We look forward to our interaction both inside and outside the classroom.
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 you to make course material for new courses freely available (e.g., not on Piazza) as much as possible.