Task Parallelism Dag Execution

Task Parallelism and DAG Execution is the programming model where computation is decomposed into discrete tasks with explicit dependency relationships forming a directed acyclic graph (DAG) — enabling the runtime scheduler to dynamically assign tasks to available processors, achieving load balance and parallelism without requiring the programmer to specify thread assignments.

DAG Task Model:
- Task Definition: a task is an indivisible unit of work with defined inputs, outputs, and a computational function — tasks are typically fine-grained (microseconds to milliseconds) to expose maximum parallelism
- Dependency Edges: directed edges in the DAG represent data or control dependencies — task B depends on task A if B requires A's output or must execute after A completes
- Critical Path: the longest dependency chain in the DAG determines the minimum possible execution time regardless of processor count — parallelism only helps for tasks not on the critical path
- DAG Width: the maximum number of independent tasks available at any point in execution — wider DAGs expose more parallelism and achieve better scaling across more processors

Runtime Scheduling:
- Ready Queue: tasks with all dependencies satisfied enter the ready queue — scheduler assigns ready tasks to idle processors using priority or locality heuristics
- Work Stealing: idle processors steal tasks from busy processors' local dequeues — achieves near-optimal load balance with O(P log N) total steal operations for P processors and N tasks
- Priority Scheduling: tasks on or near the critical path prioritized over non-critical tasks — reduces total execution time by ensuring critical tasks aren't delayed behind non-critical work
- Locality-Aware Scheduling: prefer scheduling tasks on the processor where their input data resides — reduces data movement overhead, especially for NUMA architectures where remote memory access costs 2-3× more than local

Programming Frameworks:
- Intel TBB (oneTBB): C++ template library with task_group and flow_graph APIs — work-stealing scheduler with per-thread task deques and automatic load balancing
- OpenMP Tasks: #pragma omp task and #pragma omp taskwait provide portable task parallelism — dependency clause (depend(in:x) depend(out:y)) expresses DAG structure declaratively
- Cilk Plus: fork-join model with cilk_spawn and cilk_sync keywords — provably efficient work-stealing scheduler with theoretical bounds on space and time
- Legion/Regent: data-centric task model where tasks declare data regions they access — runtime automatically determines dependencies from data region overlap and manages data movement between memories

Task parallelism and DAG execution represent the modern alternative to bulk-synchronous parallel programming — by expressing computation as fine-grained tasks with explicit dependencies, applications achieve dynamic load balance and adapt to heterogeneous hardware without manual thread management.