Think Parallel: Scans
summary
Shows how the inclusive scan becomes a parallel primitive using a decoupled lookback protocol and a scan tile state object that replaces O(input) temporaries with O(tiles) metadata, converts two-pass scans into a single pass, and reduces global synchronizations. Implements parallel inclusive scan, a copy_if and a chunk_by (range-of-ranges) using tiling; reports ~3× faster scan, ~11× faster copy_if and ~9× faster chunk_by on a 64‑core CPU with a 4GB input, at the cost of duplicated tile‑level aggregates.
AI-written summary · about
chapters (11)
- 0:00Introduction to parallelism
- 2:10Understanding the scan
- 5:21Parallelizing scan with tiling
- 12:59Decoupled lookback strategy
- 21:48Implementing decoupled lookback
- 28:41Performance and efficiency
- 31:41Copy-if algorithm
- 36:45Optimized copy-if
- 39:52Chunk-by algorithm
- 54:01Scalable chunk-by
- 59:16Final discussion and Q&A
