Scalable Parallel Algorithms
summary
SIGMOD paper implements a work-efficient, easy-to-code k-core decomposition that unifies offline and online peeling, uses ParlayLib on a 96-core machine and OpenCilk for analysis, and reports consistent speedups versus prior methods. Key ingredients are multi-level sampling to cut atomic-update contention (reducing concurrent decrements to coreness(v)+log n) and vertical granularity control (local fixed-size queues) to collapse many subrounds. Sampling helps very dense graphs (~8 cases with large gains), VGC helps sparse graphs, and restarts for sampling errors never occur in experiments.
AI-written summary · about
chapters (15)
- 0:00Scalable parallel algorithms intro
- 1:14Parallel algorithms theory vs practice
- 3:57Work-span model and design
- 5:30K-core decomposition
- 8:10Online vs offline peeling
- 13:13Challenges in parallel approaches
- 15:28New algorithmic framework
- 19:18Multi-level sampling
- 22:03Vertical granularity control
- 25:36Granularity control theory
- 29:24Experimental setup and datasets
- 30:11Performance vs baselines
- 31:42Sampling and VGC impact
- 32:06Burden span analysis
- 33:40Summary and future work
related talks
39mThe best multicore-parallelization refactoring you've never heard of
23mParallel Sequences in Multicore OCaml
56mParallelizing the C++ Standard Template Library
01h 05mThink Parallel
01h 18m“Work Stealing"
41mParallel Programming, Fork Join, and Reducers
49mStriving to Make Things Simple and Fast
48m“Is Parallel Programming still hard? PART 2 of 2”