task graph parallel execution

**Task Graph Parallel Execution** is the **parallel programming model that represents computation as a directed acyclic graph (DAG) of tasks with dependency edges — where a runtime scheduler dynamically assigns ready tasks (all dependencies satisfied) to available processor cores, automatically maximizing parallelism, balancing load, and respecting data dependencies without requiring the programmer to manage thread creation, synchronization, or scheduling explicitly**. **Why Task Graphs** Many computations have dependencies that are neither trivially parallel (loop parallelism) nor fully sequential. A compilation pipeline has parsing → optimization → register allocation → code emission, but different functions can be processed in parallel. Task graphs express exactly which tasks depend on which — the scheduler exploits all available parallelism automatically. **Task Graph Components** - **Task Node**: A unit of computation (function, lambda, kernel). Each task executes atomically — once started, it runs to completion on one core. - **Dependency Edge**: A directed edge from task A to task B means B cannot start until A completes. Dependencies encode data flow (B uses A's output) or control flow (B must follow A). - **Ready Queue**: Tasks with all incoming dependencies satisfied. The scheduler dequeues ready tasks and assigns them to idle workers. **Scheduling Algorithms** - **Work-Stealing**: Each worker has a local deque of ready tasks. When a worker's deque is empty, it steals from another worker's deque (random victim selection). Intel TBB, Cilk, and Taskflow use work-stealing. Achieves provably good load balance: completion time ≤ T1/P + T∞ (work/processors + critical path length). - **Priority-Based**: Assign priorities based on critical path length from the task to the graph exit. Schedule highest-priority ready tasks first. Optimal for minimizing makespan on bounded processors. Used in HPC runtimes (StarPU, PaRSEC). - **CUDA Graphs**: GPU task graphs captured by the CUDA runtime. A sequence of kernel launches and memory copies is recorded as a graph, then launched with a single API call — eliminating per-launch overhead (5-20 μs per kernel saved). CUDA graphs are instantiated once and launched repeatedly. **Task Graph Frameworks** - **Intel oneAPI Threading Building Blocks (TBB)**: flow_graph for data-flow task graphs, task_group for fork-join. - **Taskflow (C++)**: Header-only library for expressing complex task DAGs including conditional tasking, looping, and GPU kernels. Clean C++ API. - **CUDA Graphs**: GPU-specific — capture kernel launch sequences as executable graphs. cudaGraphLaunch() replaces individual kernel launches, reducing CPU overhead by 10-50% for small-kernel workloads. - **Dask (Python)**: Task graph parallel computing for data science. Builds DAGs from NumPy/Pandas operations and executes on multi-core or distributed clusters. - **Apache Airflow**: Workflow orchestration using DAGs for data engineering pipelines (ETL, ML training). **Task Granularity** - Too fine (1 μs per task): scheduling overhead dominates — work-stealing steal latency is ~1 μs. Net slowdown. - Too coarse (100 ms per task): insufficient parallelism, poor load balance. Optimal: 10 μs - 10 ms per task, depending on the number of cores and task graph depth. Task Graph Parallel Execution is **the natural programming model for computations with complex, irregular dependencies** — providing automatic parallelization and load balancing through dynamic scheduling that adapts to runtime conditions, freeing programmers from the error-prone manual management of threads and synchronization.