From Algorithm to Generic, Parallel Code
summary
Parallel inclusive scan is implemented from a textbook algorithm into several concrete backends: a naive recursive version using std::async that runs about 1,500× slower on a 64-core Knights Landing machine, chunked recursion that drops the penalty to ~200×, an iterative chunked variant using Threading Building Blocks task_groups, and an OpenMP loop version that performs best. A custom thread-pool + executor and latch/arrival helpers are built, intermediate storage uses optionals to avoid default construction, and tuning chunk size proves essential.
AI-written summary · about
chapters (29)
- 0:00Introduction
- 3:54Sequential
- 5:19Parallelization
- 6:52Algorithm
- 7:46Piece
- 9:26One direction
- 9:57Memory
- 11:23Benchmark
- 12:08The Algorithm
- 13:19Lockstep
- 15:17Benchmarking
- 16:25OpenMP
- 17:41InclusiveScan
- 19:35Print Principle
- 20:33Task Group
- 25:06Graph
- 27:03Subrange
- 28:35Execute
- 31:27Task Scheduler
- 32:50Executor
- 33:30Suspect Pool
- 35:03Thread Pool
- 35:43Scheduling
- 36:06Lock
- 36:37Executors
- 42:10Parallel Version
- 42:53Conclusions
- 44:35Questions
- 46:48When
