Work Assisting: Linking Task-Parallel Work Stealing with Data-Parallel Self Scheduling
summary
Work Assisting implements a scheduler that links task-parallel work stealing with data-parallel self scheduling by having threads publish current loops in a shared activities array so idle threads can atomically claim blocks and join a loop dynamically. It preserves data-parallel structure, uses atomic increments for block claiming and a split reference count to avoid races, and runs benchmarks (LU on multiple matrices, compaction, quicksort partitioning) that are competitive with or faster than pure work-stealing, scaling beyond eight threads on 8-matrix runs.
AI-written summary · about
chapters (16)
- 0:00Parallelism types intro
- 1:17Data and task parallelism
- 3:04Work assisting scheduler
- 6:38Modeling data workloads
- 8:28Implementing parallel phase
- 10:13Parallel reduction work
- 11:39Finish phase and spawning
- 12:20Sharing tasks via array
- 13:45Task object structure
- 14:26Simulating execution
- 16:15Concurrent reference counting
- 17:20Benchmarking LU decomposition
- 19:07Compaction benchmark
- 19:29Quicksort mixed parallelism
- 20:11Benchmark results
- 20:57Q&A
related talks
20mSparseAuto: An Auto-Scheduler for Sparse Tensor Computations Using Recursive Loop Nest(…)
01h 13mTalk by I-Ting Angelina Lee (Washington University in St. Louis)
15mCertified and Efficient Instruction Scheduling: Application to Interlocked VLIW Processors
18mThe One Pass (OP) Compactor (an intellectual abstract)
18mParallelism in a Region Inference Context
27mDistributing and Parallelizing Non-canonical Loops
01h 01mIntroduction to Vector Parallelism
22mOpenMP-RT: Native Pragma Support for Real-Time Tasks and Synchronization with LLVM(…)