The best multicore-parallelization refactoring you've never heard of
summary
Refactors a recursive tree-sum into two paths—a parallel fork‑join version and an optimized serial iterator—then merges them so task creation is triggered only after amortized work, claiming better granularity control and no stack overflows on degenerate inputs. Uses CPS conversion and defunctionalization to turn continuations into data, implements promotion via heartbeat scheduling (example H≈4, measured amortization ~100µs), runs on a 64‑core machine and shows higher speedups than Silk without crashing where Silk overflows.
AI-written summary · about
chapters (18)
- 0:00Multicore parallelization intro
- 1:04Defunctionalization & CPS inspiration
- 2:10Parallel recursive algorithm
- 3:57Granularity control challenges
- 5:19Refactoring technique overview
- 6:01Lowering to CPS in parallel
- 8:09Fork-join to CPS parallel
- 9:12Defunctionalizing continuations
- 11:23Serial refactoring path
- 14:15Tail call elimination
- 16:22Heartbeat scheduling concept
- 17:25Heartbeat scheduling practice
- 20:15Introducing heartbeat
- 21:19Task spawning in heartbeat
- 23:26Merging algorithms
- 26:12Performance vs Silk
- 29:42Summary & future
- 31:51Q&A
related talks
41mParallel Programming, Fork Join, and Reducers
50mFrom Concurrent to Parallel
56mParallelizing the C++ Standard Template Library
37mScalable Parallel Algorithms
49mStriving to Make Things Simple and Fast
01h 01mFrom Concurrent to Parallel
58mTurbo Charge CPU Utilization in Fork/Join Using the ManagedBlocker
53mTurbo Charge CPU Utilization in Fork/Join Using the ManagedBlocker