“Work Stealing"
summary
Explains why randomized work stealing in C++ runtimes (Intel Cilk Plus, TBB, PPL and the proposed parallel STL) approximates a greedy scheduler and often hits near-optimal CPU utilization, needing roughly 10× parallelism relative to cores. Shows centralized FIFO queues vs per-worker double-ended deques, demonstrates a Fibonacci example where work usually moves between workers only once, and contrasts child-stealing with continuation-stealing. Covers compiler/runtime support (Intel compiler, Cilk runtime), cactus-stack lifetime bugs and fixes (capture-by-value, thread sanitizer).
AI-written summary · about
chapters (16)
- 0:00Introduction to work stealing
- 1:24Why scheduling matters
- 8:08Expressing parallelism in C++
- 15:13Measuring parallelism
- 18:56Greedy scheduling explained
- 21:46Static scheduling limitations
- 23:51Thread-based scheduling issues
- 25:19Work stealing analogy
- 29:53Work stealing in C++
- 32:47Centralized work queues
- 38:09Distributed work queues
- 46:18Child vs continuation stealing
- 53:29Advantages of child stealing
- 54:32Advantages of continuation stealing
- 56:41Cactus stack and object lifetimes
- 58:25Conclusion and Q&A
related talks
01h 08mBetter Code: Concurrency
15mBWoS: Formally Verified Block-based Work Stealing for Parallel Processing
48m“Is Parallel Programming still hard? PART 2 of 2”
01h 03mIntro to Concurrent Programming 3/3: Relaxed Data Structures for Parallel Algorithms
51mFrom Linux Threads To ForkJoinPool
59mAn Introduction to Multithreading in C++20
39mThe best multicore-parallelization refactoring you've never heard of
29mConcurrency and Parallelism From The Ground Up