Multi-Priority Graph-Based Parallel Execution Using Taskflow
summary
Benchmarks add priority to C++ Taskflow with two practical modes: a buffered three-queue design (one chase-lev deque per priority plus a local buffer) and an enforced-steal mode that always steals to honor priority. A complex chunk-based priority queue is evaluated too but proves harder to implement and slower under high contention. Microbenchmarks (example on a 14‑core Mac) show a pathological schedule dropping makespan from 9s to 6s with longest-first ordering; the buffered mode matches default latency on uniform work and improves mixed-work cases. A PR exists upstream.
AI-written summary · about
chapters (9)
- 0:00Introduction to Taskflow
- 1:49Taskflow scheduling
- 6:22Non-deterministic execution problem
- 13:10Longest processing time heuristic
- 16:17Priority-aware data structures
- 24:43Priority queue benchmarks
- 26:31Priority-aware scheduling solution
- 35:26Future work and conclusion
- 37:39Q&A
related talks
01h 01mTaskflow: A Parallel and Heterogeneous Task Programming System Using Modern C++
01h 03mIntro to Concurrent Programming 3/3: Relaxed Data Structures for Parallel Algorithms
01h 05mFusing Efficient Parallel For Loops with a Composable Task Scheduler
01h 08mBetter Code: Concurrency
35mC++ Workflow: Task-based Parallel Computing and Asynchronous Networking Engine
35mAutomatic Parallelism Management
01h 18m“Work Stealing"
01h 17mForward Progress in C++