CMSC858N: Fall 2026
Time and Location: Tuesday/Thursday, TBD
Instructor: Laxman Dhulipala (IRB 5150); Office hours: by appointment
Piazza: https://piazza.com/umd/fall2026/cmsc858n/home
This is a research-oriented course on parallel algorithms and data structures. 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.
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 | Primary Source(s) |
|---|---|---|
| Sep 08 (Tu) | Models and primitives: work–depth, scheduling, basic parallel primitives | BDS, Introduction to Parallel Algorithms (draft) |
| Sep 10 (Th) | Programming parallel algorithms (ParlayLib); other models and parallel complexity; seminar logistics | ParlayLib (SPAA’20); Aggarwal & Vitter (CACM’88); PBBS / PCBS |
| Sep 15 (Tu) | Writing Fast Parallel Code | Writing Fast Parallel Code |
| Sep 17 (Th) | Symmetry breaking: MIS and maximal matching | Luby (1986); “Greedy Sequential MIS and Matching are Parallel on Average” (SPAA’12) |
| Sep 22 (Tu) | Low-diameter decomposition and connectivity | Miller, Peng & Xu (SPAA’13); ConnectIt (VLDB’21) |
| Sep 24 (Th) | Transformer basics (tutorial lecture) | The Illustrated Transformer (Alammar); Transformer Explainer; optional: Karpathy, “Let’s build GPT” |
| Sep 29 (Tu) | Graph-based ANNS I: index construction | HNSW (TPAMI’20); DiskANN / Vamana (NeurIPS’19); ParlayANN (PPoPP’24) |
| Oct 01 (Th) | Graph-based ANNS II: dynamic indices | FreshDiskANN (WWW’23); IPDiskANN / DiskANN |
| Oct 06 (Tu) | Vector quantization | Product quantization (Jégou et al., TPAMI’11); ScaNN / anisotropic VQ (ICML’20); RaBitQ (SIGMOD’24) |
| Oct 08 (Th) | Software Transactional Memory | MicroSTM (arXiv’26) (code: uepoch.h) |
| Oct 13 (Tu) | Fall break — no class | |
| Oct 15 (Th) | Distributed ANNS: partitioning and routing | Gottesbüren et al., “Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search” (PVLDB’25 / arXiv’24) |
| Oct 20 (Tu) | Multi-vector approaches | ColBERT (SIGIR’20); MUVERA (NeurIPS’24) |
| Oct 22 (Th) | FlashAttention | Dao et al., FlashAttention (NeurIPS’22); optional: FlashAttention-2 / FlashAttention-3 |
| Oct 27 (Tu) | PagedAttention | PagedAttention (SOSP’23) |
| Oct 29 (Th) | NVMe and semi-external algorithms | The Read-Only Semi-External Model (APOCS’21); Scaling Parallel Algorithms to Massive Datasets using Multi-SSD Machines (SPAA’25) |
| Nov 03 (Tu) | Concurrency: definitions and basics | Herlihy & Wing, Linearizability (TOPLAS’90); Treiber (1986) |
| Nov 05 (Th) | Concurrency and Contention | Aggregating Funnels for Faster Fetch&Add and Queues (PPoPP’25) |
| Nov 10 (Tu) | Concurrency control | Kung & Robinson, Optimistic Concurrency Control (TODS’81); Silo (SOSP’13); Wu et al., Empirical Evaluation of In-Memory MVCC (VLDB’17) |
| Nov 12 (Th) | Consensus and Replication | Lamport, Time, Clocks, and the Ordering of Events (CACM’78); Raft (Ongaro & Ousterhout, ATC’14) |
| Nov 17 (Tu) | Distributed consistency I: strong consistency | Spanner (OSDI’12) |
| Nov 19 (Th) | Distributed consistency II: partitioning, quorums and eventual consistency | Dynamo (SOSP’07); DynamoDB (USENIX ATC’22) |
| Nov 24 (Tu) | Parallelizing some useful P-complete problems (clustering) | ParHAC (NeurIPS’22); TeraHAC (SIGMOD’24) |
| Nov 26 (Th) | Thanksgiving recess — no class | |
| Dec 01 (Tu) | Batch-dynamic trees | Batch Parallel Euler Tour Trees (ALENEX’19); UFO Trees (PPoPP’26) |
| Dec 03 (Th) | Dataflow (revisited) | The Dataflow Model (VLDB’15) |
| Dec 08 (Tu) | Project presentations I | |
| Dec 10 (Th) | Project presentations II |
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.