Zero-Overhead Parallel Scans for Multi-Core CPUs
summary
Claims zero single-thread overhead parallel scans for multi-core CPUs and delivers two concrete algorithms: assisted reduce-and-scan and adaptive chain scan. Implementation uses block reduction with blocks sized to fit L1 cache (reads each element once), and benchmarks show single-thread performance equals a sequential scan (speed = 1) while multi-threaded performance matches or slightly improves state-of-the-art chain scans, limited to ~2–3× scaling by memory bandwidth; tests run on Intel, AMD and Apple silicon for comparison.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:07What is a scan
- 2:55Parallel scan challenges
- 5:45Scan algorithms
- 7:51Assisted reduced scan
- 9:13Benchmarking assisted scan
- 10:19Chain scans for GPUs
- 13:31Adaptive chain scans
- 15:37Memory bandwidth analysis
- 17:30Q&A: GPU generalization
- 20:59Q&A: Sequential vs parallel
related talks
01h 01mIntroduction to Vector Parallelism
24mTowards Understanding the Costs of Avoiding Out-of-Thin-Air Results
20mVectorizing Sparse Coiteration for Two-finger Loop Structure (Extended Abstract)
17mEvaluation of Speedup & Energy with Multigrain Parallelizing Compiler
29mReverse Automatic Differentiation for Accelerate (Extended Abstract)
20mThe status of parallel rustc
38mOptimized String Processing in RISC-V: How Toolchain Improvements Can Boost Performance
53mFROM SCALA TO ASSEMBLY THE COST OF ABSTACTION REVISITED