BWoS: Formally Verified Block-based Work Stealing for Parallel Processing
summary
Presents Block-based Work Stealing (BWoS), a queue design that splits per-core queues into fixed-size blocks so owners work inside a block using relaxed atomics while stealing and heavy fences occur only at block boundaries; implements a randomized, size-biased stealing policy and a model-checking workflow with Vsync. Claims include 8–11x better microbenchmark throughput, 1.26x speedup in Go JSON and up to 1.25x or 1.12x on Java GC and Rust Tokio, and is formally verified on weak memory models.
AI-written summary · about
chapters (15)
- 0:00BWoS introduction
- 1:09Workload distribution strategies
- 2:13Work stealing balance
- 3:17Overheads in fine-grained tasks
- 4:22Three overhead sources
- 6:10BWoS overhead reduction
- 7:13Block-based synchronization
- 8:39Randomized stealing policy
- 10:03Formal verification with VSYNC
- 11:29Weak memory benefits
- 11:50Microbenchmark comparisons
- 12:35JSON decoding improvements
- 13:16Tokyo HTTP server impact
- 13:59Future block-based apps
- 14:21Conclusion
related talks
01h 18m“Work Stealing"
04mInterview
48m“Is Parallel Programming still hard? PART 2 of 2”
52mSecrets of high performance in multicore systems ☠️
53mTurbo Charge CPU Utilization in Fork/Join Using the ManagedBlocker
36mThe Good, The Bad, and the Ugly: A Journey from this synchronized to Asynchronous Code
22mBBQ: A Block-based Bounded Queue for Exchanging Data and Profiling
01h 35mThinking Outside the Synchronisation Quadrant