Think Parallel
summary
Argues that a parallel inclusive-scan primitive, implemented with decoupled look-back, replaces the classic two-pass upsweep/down-sweep and enables single-pass, scalable algorithms. Uses C++17 parallel algorithms, per-tile serial scans, an atomic fetch_add for monotonic tile IDs and a scan_tile_state for communication. Requires only O(tiles) storage instead of O(input), hides latency by overlapping tiles, and benchmarks on billions of elements (thousands of tiles) show 3×/11×/9× speedups (scan, copy_if, chunk_by) and GPU/distributed gains.
AI-written summary · about
chapters (25)
- 0:00Introduction
- 1:59Parallelism as default mindset
- 3:05Scan algorithm properties
- 5:14Three components of parallel problems
- 7:19Serial scan implementation
- 10:09Limitations of two-pass scan
- 11:57Scalable parallel programming principles
- 12:40Decoupled look back scan
- 16:15Monotonic progress in parallel
- 17:17Scan tile state for communication
- 20:06Decoupled look back scan example
- 25:24Wait for predecessor prefix
- 27:54Finalizing decoupled scan
- 28:36Scan methods comparison
- 29:39Scan foundation for parallel algorithms
- 30:03Copy if using scan
- 36:05Optimizing copy if with decoupled look back
- 39:41Introducing chunk by
- 42:08Interval data type for chunk by
- 46:06Multi-pass chunk by
- 56:10Limitations of multi-pass chunk by
- 56:31Single-pass chunk by
- 1:00:50Parallel algorithm design principles
- 1:03:01Resources on parallel programming
- 1:04:27Acknowledgments
