task graph scheduling dag
**Task Graph Scheduling (DAG)** is the **scheduling of computational tasks represented as a Directed Acyclic Graph (DAG) onto parallel processing resources**, where nodes represent tasks with defined execution costs and edges represent data dependencies with communication costs — the fundamental abstraction for extracting and managing parallelism in both compile-time and runtime scheduling systems.
Every parallel computation can be modeled as a DAG: matrix multiplication decomposes into independent multiply-accumulate tasks with data flow dependencies; neural network inference has layer-by-layer dependencies; and even irregular applications like sparse solvers form DAGs through their dependency structure.
**DAG Scheduling Fundamentals**:
| Property | Definition | Impact |
|----------|-----------|--------|
| **Critical path** | Longest weighted path from entry to exit | Lower bound on execution time |
| **Parallelism** | Total work / critical path length | Upper bound on useful processors |
| **Schedule length** | Makespan (completion time) | Primary optimization objective |
| **Granularity** | Task size relative to communication cost | Determines scheduling efficiency |
| **Scheduling complexity** | NP-complete in general | Heuristics required for practice |
**Scheduling Algorithms**: **List scheduling** assigns priorities to tasks (critical path length, bottom level, etc.) and greedily assigns the highest-priority ready task to the earliest-available processor. **HEFT (Heterogeneous Earliest Finish Time)** extends list scheduling to heterogeneous processors where task execution time varies by processor type. **Clustering algorithms** group communicating tasks onto the same processor to eliminate inter-processor communication, then map clusters to physical processors. **Work-stealing** defers scheduling to runtime: each processor has a local queue and steals from other processors' queues when idle.
**Runtime DAG Scheduling**: Modern frameworks (Intel TBB, OpenMP tasks, CUDA Graphs, Taskflow) generate DAGs dynamically at runtime: the programmer specifies tasks and dependencies, and the runtime schedules across available cores. **CUDA Graphs** capture a sequence of GPU kernel launches and memory copies as a DAG, enabling the driver to optimize launch overhead and overlap computation with data transfer — reducing CPU-side overhead by 10-100x for graphs of small kernels.
**Communication-Aware Scheduling**: On distributed systems, edge weights represent data transfer costs between processors. Scheduling must co-optimize computation placement and communication: placing communicating tasks on the same node eliminates network transfer but may create load imbalance. The **BSP (Bulk Synchronous Parallel)** model simplifies this by separating computation and communication into distinct phases, while **asynchronous scheduling** overlaps them for better hardware utilization.
**DAG Scheduling Metrics**: **Speedup** = sequential time / parallel time; **efficiency** = speedup / number of processors; **schedule length ratio (SLR)** = schedule length / critical path length (optimal = 1.0, practical = 1.1-1.5 for good schedulers); and **load balance** = max processor load / average processor load (optimal = 1.0).
**Task graph scheduling is the mathematical foundation of parallel execution — it transforms the abstract notion of parallelism into concrete processor assignments and execution orderings, and the quality of the scheduler directly determines how effectively a parallel system converts hardware resources into application performance.**