Source-linked AI summary
Taskflow: A Lightweight Parallel and Heterogeneous Task Graph Computing System
Tsung-Wei Huang, Dian-Lun Lin, Chun-Xun Lin, Yibo Lin
TL;DR
Existing task graph systems struggle to express heterogeneous workloads and control flow while efficiently scheduling dynamic CPU-GPU tasks. Taskflow introduces an expressive task graph model with in-graph control flow and a heterogeneous work-stealing runtime, reporting faster execution, lower memory use, and higher throughput than oneTBB on a representative machine-learning workload.
Problem
Existing task graph systems rely on DAGs, provide limited support for CPU-GPU task graphs, and rarely support both CPU- and GPU-focused work simultaneously.
Method
Taskflow combines an expressive heterogeneous task graph programming model with in-graph control flow and an adaptive work-stealing runtime for dynamically generated task parallelism.
Results
29% faster, 1.5× less memory, and 1.9× higher throughput than oneTBB were reported for a large-scale machine-learning problem on 40 CPUs and 4 GPUs.
Takeaways & Limitations
Taskflow provides a lightweight system for expressing heterogeneous tasks with general control flow and optimizing runtime performance across latency, energy efficiency, and throughput.
Takeaways & Limitations
Taskflow focuses on a single heterogeneous node and does not dynamically choose CPU versus GPU execution or manage GPU data through another abstraction.
Abstract
from arXiv · showhide
Taskflow aims to streamline the building of parallel and heterogeneous applications using a lightweight task graph-based approach. Taskflow introduces an expressive task graph programming model to assist developers in the implementation of parallel and heterogeneous decomposition strategies on a heterogeneous computing platform. Our programming model distinguishes itself as a very general class of task graph parallelism with in-graph control flow to enable end-to-end parallel optimization. To support our model with high performance, we design an efficient system runtime that solves many of the new scheduling challenges arising out of our models and optimizes the performance across latency, energy efficiency, and throughput. We have demonstrated the promising performance of Taskflow in real-world applications. As an example, Taskflow solves a large-scale machine learning workload up to 29% faster, 1.5x less memory, and 1.9x higher throughput than the industrial system, oneTBB, on a machine of 40 CPUs and 4 GPUs. We have opened the source of Taskflow and deployed it to large numbers of users in the open-source community.
1 INTRODUCTION
Taskflow addresses limitations of existing task graph computing systems by combining expressive heterogeneous task graphs, in-graph control flow, and a runtime designed for dynamic scheduling. Its evaluation reports improved performance on real-world workloads.
- Motivation: Existing task graph systems rely on DAGs, forcing control-flow decisions outside graph descriptions and complicating end-to-end parallelism.This limitation is especially relevant to irregular algorithms with iterations, conditionals, and dynamic behavior.
- Programming model: Taskflow combines an expressive C++-closure-based programming model with in-graph control flow for heterogeneous task decomposition.Condition tasks represent conditional dependencies, cyclic execution, and non-deterministic flows within the task graph.
- Runtime: Taskflow’s heterogeneous work-stealing runtime adapts workers to dynamically generated parallelism while targeting latency, energy usage, and throughput.The algorithm seeks to avoid both underutilized threads and excessive resource waste when available tasks are scarce.
- Evaluation: 29% faster, 1.5× less memory, and 1.9× higher throughput were reported for a large-scale machine learning problem versus oneTBB on 40 CPUs and 4 GPUs.The evaluation used real-world applications to assess Taskflow’s performance.
- Heterogeneous execution: Existing runtimes rarely support CPU- and GPU-focused work simultaneously, motivating Taskflow’s heterogeneous task graph environment for a single node.The target setting includes CPU-GPU dependent tasks and algorithmic control flow.
3 PRELIMINARY RESULTS
Taskflow extends the CPU-only Cpp-Taskflow system from DAG-based parallelism to heterogeneous computing with a heterogeneous task dependency graph model. Its open-source implementation has been adopted by multiple software projects.
- Prior system: Taskflow builds on Cpp-Taskflow, which targeted CPU-only parallelism using a DAG model.
- Extension: Taskflow extends the earlier system to heterogeneous computing through a heterogeneous task dependency graph programming model beyond DAG.
- Adoption: The open-source Cpp-Taskflow and Taskflow projects have been adopted by multiple software projects, including CAD projects.
4 TASKFLOW PROGRAMMING MODEL
Taskflow provides a composable task-graph model for static, dynamic, conditional, and heterogeneous CPU-GPU computation. Its condition tasks integrate control flow into graphs, while cudaFlow expresses GPU operations and can combine them with CPU tasks.
- Task Types: Taskflow supports static tasks, dynamically spawned subflows, reusable module tasks, condition tasks, and cudaFlow tasks.These task types cover basic dependencies, runtime graph creation, graph composition, in-graph control flow, and GPU task graphs.
- Dynamic Tasking: Dynamic tasks spawn subgraphs during execution, with child tasks grouped into a subflow that normally joins its parent.A subflow can instead be detached so its execution proceeds independently.
- Composable Tasking: Composable tasking builds large graphs from modular taskflows, but module tasks sharing one taskflow must not run concurrently.Unlike dynamically created subflows, module tasks maintain a soft mapping to their composed taskflow.
- Conditional Tasking: Condition tasks encode if-else, iterative, and non-deterministic control flow directly within task dependencies.They can represent cycles and probabilistic branching without partitioning control flow or unrolling it into a flat DAG.
- Conditional Tasking: Condition tasks also allow independent control-flow blocks to overlap, with one example implementing three blocks in 30 lines of code.The cited example states that cond_1 can run in parallel with cond_2 and cond_3.
- Heterogeneous Tasking: cudaFlow expresses dependent GPU operations as a task graph inside a closure, while Taskflow combines such graphs with CPU tasks and condition tasks.cudaFlow maps by default to a CUDA graph, can fall back to stream-based execution, and supports iterative CPU-GPU workloads such as k-means.
5 TASKFLOW SYSTEM RUNTIME
Taskflow’s runtime schedules heterogeneous task graphs at task and worker levels, with explicit support for conditional control flow and GPU task execution.
- Runtime overview: Task-level scheduling executes in-graph control flow and transforms GPU tasks into runnable GPU instances.The runtime separates task-level goals from worker-level performance optimization.
- Conditional task scheduling: Conditional scheduling uses weak dependencies from condition tasks and strong dependencies elsewhere to handle branching and cyclic execution.Tasks with satisfied strong dependencies execute, while weak dependencies follow the condition task’s returned successor index.
- Conditional task scheduling: The scheduler can create cyclic execution by following indexed successors returned by condition tasks.A condition result can select a later successor that routes execution back to an earlier task.
- Conditional task scheduling: Figure 10 identifies two conditional-tasking pitfalls: graphs without a start source and races caused by concurrent control-flow paths.The proposed fixes add a zero-dependency source or partition control flow with an auxiliary node.
- GPU task scheduling: CUDA Graphs schedule GPU tasks, while cudaFlow capturer tasks are transformed into native CUDA graphs using stream capture.The capturer transformation seeks kernel concurrency without violating task dependencies.
19 end
Taskflow’s worker-level scheduler applies domain-specific work stealing across CPU and GPU workers, adapting worker activity to dynamic heterogeneous workloads.
- Worker-level scheduling: Heterogeneous work stealing remains challenging because CPU and GPU tasks can submit dependent work across domains.Taskflow addresses this with a scheduler architecture and adaptive worker management algorithm generalized to heterogeneous domains.
- Worker-level scheduling: Yielding workers can oversubscribe scarce workloads, while sleeping workers require careful wake-up and worker-count decisions.These trade-offs affect latency, throughput, and energy efficiency.
- Adaptive worker management: Taskflow extends CPU-only adaptive work stealing with per-domain invariants and controls for cross-domain dependencies and notifications.Separating decision controls by domain addresses the difficulty of heterogeneous worker management.
- Scheduler architecture: The scheduler maintains separate worker sets for task domains such as CPU and GPU, with workers stealing only within their own domain.Figure 12 depicts the two-domain architecture.
- Scheduler architecture: Lock-free work-stealing queues and per-domain event notifiers support concurrent task movement and non-blocking worker notification.The event notifier uses a two-phase commit protocol and is implemented per domain.
10 end
The scheduling algorithms execute tasks, propagate dependencies, route condition successors, and adapt workers between stealing and sleeping as queues change.
- Adaptive worker control: Workers track active and stealing populations with atomic variables to decide when to sleep and when to resume useful work.The ordering of active-worker and thief comparisons synchronizes worker decisions.
- Task execution: Condition tasks submit the successor indexed by their return value, while ordinary tasks release successor dependencies and submit newly ready tasks.This behavior is implemented by execute_task.
- Task submission: Task submission places work in the corresponding domain queue and wakes a worker when the task belongs to another domain.External threads do not invoke the internal submit_task function.
- Implementation detail: The implementation pads atomic variables to avoid false-sharing effects.The pseudocode omits this implementation detail for brevity.
- Worker waiting: When local work is exhausted, a worker attempts same-domain stealing before becoming a sleep candidate.Two-phase commit prevents missed notifications while the worker transitions toward sleep.
28 end
The worker-waiting logic tests whether tasks remain available in the worker’s domain before deciding whether active workers should continue.
- Worker waiting: A worker’s waiting decision checks whether its domain’s task queue is nonempty.The surrounding scheduling logic uses queue availability to adapt active workers to available task parallelism.
40 end
Taskflow’s scheduler coordinates heterogeneous workers and task queues through bounded stealing and synchronized submission. Its design includes configurable steal-attempt limits and safeguards against sleeping workers missing available parallelism.
- Workers repeatedly steal tasks from randomly selected victims and shared queues within their domain.
- MAX_STEALS limits the number of steal iterations; experiments found ten times the total worker count sufficient for most applications.
- Graph submission places zero-dependency tasks into shared queues and notifies a worker in the corresponding domain.
- Shared task queues are lock-protected because multiple callers may access them concurrently.
- A two-phase commit protocol synchronizes submission and worker waiting, preventing all workers from sleeping while parallel tasks remain undetected.
6 ANALYSIS
The analysis establishes correctness, resource utilization, and a worst-case bound for Taskflow’s heterogeneous work-stealing scheduler. The bound applies at each moment rather than across an entire graph execution because control flow can make execution time nondeterministic.
- When an active worker exists in a domain, at least one other worker attempts to steal unless all workers are active.
- The work-stealing algorithm correctly completes execution of a heterogeneous task dependency graph.
- The scheduler does not undersubscribe thread resources while tasks exceed the number of available workers, unless no tasks remain.
- At any moment, wasteful steals are bounded by O(MAX_STEALS × (|W| + |D| × (E/es))).
- The analysis bounds wasteful steals at a time point rather than over full execution because control flow can produce nondeterministic execution times requiring assumptions about task distribution.
7 EXPERIMENTAL RESULTS
Experiments evaluate Taskflow on micro-benchmarks and realistic VLSI and machine-learning workloads across runtime, memory, energy efficiency, throughput, and programming effort. Results show advantages from its tasking model, scheduler, and CUDA Graph integration, with some memory trade-offs for CUDA Graphs.
- Micro-benchmarks: 1.37×, 1.44×, 1.53×, and 1.40× faster than oneTBB, StarPU, HPX, and OpenMP, respectively, Taskflow completed the largest heterogeneous task graph.Taskflow also consumed consistently fewer joules than the baselines.
- Micro-benchmarks: 1–15% better throughput than oneTBB for corunning task graphs, except with seven coruns, Taskflow and oneTBB outperformed the other methods.The comparison used weighted speedup and related throughput to CPU utilization.
- Micro-benchmarks: 3.9 hours versus 6.1 hours for oneTBB and 4.3 hours for StarPU, Taskflow required less implementation time; debugging oneTBB and StarPU took 3–4× longer.
- CUDA Graph Comparisons: 9–17% runtime speed-up over stream-based implementations, cudaFlow improved large GPU timing-analysis workloads with over 1K dependent GPU operations.cudaFlow used more memory because CUDA Graph stores kernel parameters in advance.
- Large Sparse Neural Network Inference: 1.5–1.7× less memory than oneTBB and StarPU, Taskflow scaled better in the large sparse neural-network workload using four GPUs.The result is attributed in the passage to cyclic condition-task representation and heterogeneous work stealing.
- Large Sparse Neural Network Inference: 1.9× higher throughput than oneTBB and 2.1× higher than StarPU, Taskflow processed the 1920×4096 neural network.
8 RELATED WORK
Related work spans directive-based, functional, and GPU-focused heterogeneous programming systems. The paper identifies heterogeneous worker management as an open challenge for adapting work-stealing advances beyond CPU-only settings.
- Directive-based models support loop parallelism but cannot efficiently handle irregular task-graph patterns.
- Existing heterogeneous runtimes use work stealing to simplify load balancing, with worker management remaining a key design challenge.
- Prior work improves work stealing for selected aspects such as space sharing, frequency scaling, distributed memory, locality, or memory-bound applications, but results are limited to CPUs.
- How to migrate CPU-domain work-stealing approaches to heterogeneous targets remains an open question.
- GPU task-scheduling research has addressed sparse parallelism, reinforcement-learning placement, CUDA-graph optimization, and compilation from OpenMP directives.
10 CONCLUSION
Taskflow provides a lightweight task graph system for heterogeneous programs with general control flow, supported by a runtime optimized for latency, energy efficiency, and throughput. Its evaluation includes substantial gains over oneTBB, while ongoing work targets distributed execution, SYCL integration, and task-graph translation.
- Taskflow expresses heterogeneously dependent tasks with general control flow in a lightweight task graph computing system.
- Its work-stealing runtime is optimized for latency, energy efficiency, and throughput.
- 29% faster, 1.5× less memory, and 1.9× higher throughput were achieved on a large-scale machine-learning problem versus oneTBB using 40 CPUs and 4 GPUs.
- Taskflow remains under active development, with future directions including distributed tasking, SYCL-based heterogeneous graphs, and automatic task-graph translation.
- A proposed CUDA Graph interface would move conditional control-flow decisions into the CUDA runtime to reduce CPU–GPU control-flow cost.