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:

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.