cs.LGApr 10, 2026
SaveOn the Role of DAG topology in Energy-Aware Cloud Scheduling : A GNN-Based Deep Reinforcement Learning Approach
Organizations: CEA, List, Université Paris-Saclay, France · Université Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, France
Abstract
Cloud providers must assign heterogeneous compute resources to workflow DAGs while balancing competing objectives such as completion time, cost, and energy consumption. In this work, we study a single-workflow, queue-free scheduling setting and consider a graph neural network (GNN)-based deep reinforcement learning scheduler designed to minimize workflow completion time and energy usage. We identify specific out-of-distribution (OOD) conditions under which GNN-based deep reinforcement learning schedulers fail and provide a principled explanation of why these failures occur. Through controlled OOD evaluations, we demonstrate that performance degradation stems from structural mismatches between training and deployment environments, which disrupt message passing and undermine policy generalization. Our analysis exposes fundamental limitations of current GNN-based schedulers and highlights the need for more robust representations to ensure reliable scheduling performance under distribution shifts.
Figures & tables
Figure 1. Overview of the workflow scheduling problem in a heterogeneous cloud . The scheduler receives a DAG with ready tasks and a set of machines with different speed and power. It must decide which task runs on which machine, and each choice changes both completion time and energy.
Figure 2. Schematic comparison of a wide DAG (left, shallow with many parallel branches) and a Long - CP DAG (right, deep dependency chain with limited side - branch concurrency).
Figure 3. Fitness landscape of the scheduling search space. We exhaustively enumerate all feasible action sequences for a small scenario and project them onto a 2D plane using a Hilbert curve. The Z-axis shows energy consumption (lower is better). Left: LongCP DAG. Right: wide DAG . A pair of side‑by‑side 3D landscapes compares scheduling fitness for two small task graphs. In each panel, every feasible scheduling action sequence is plotted as a point on a 2D plane generated by a Hilbert space‑filling curve; nearby coordinates represent similar sequences, and axis units are indices without physical meaning. The vertical axis is energy consumption, with lower height indicating a more efficient schedule. \parThe surface forms peaks, valleys, and plateaus. Valleys and basins mark clusters of low‑energy schedules. Peaks and ridges indicate schedules or neighborhoods with higher energy. Sharp drops or cliffs reflect cases where small changes in the action sequence cause large changes in energy, while smooth regions indicate insensitivity to local perturbations. \parThe left panel corresponds to a graph with a long critical path; the right panel corresponds to a graph with many parallel branches. The two surfaces differ in the location, size, and apparent density of low‑energy regions, illustrating how graph topology affects the distribution of good schedules and the ruggedness of the search space. Readers can use these landscapes to judge whether efficient schedules are concentrated in a few basins or dispersed across many regions, and whether exploring locally similar schedules is likely to yield gradual improvement or encounter abrupt changes. \parBoth panels were produced with the same enumeration and projection procedure, and the vertical scale represents energy in the same units, enabling qualitative comparison of landscape shape and the relative prevalence of low‑energy areas across the two task graphs.
Figure 4. Speed–power host regimes. Illustration of the four queue-free host regimes studied in this paper. Homogeneous-Speed: all VMs share the same processing speed but differ in power, isolating energy trade-offs at fixed makespan. Homogeneous-Power: all VMs share the same active power but differ in speed, isolating time trade-offs. Heterogeneous Aligned: speed and power are monotonically aligned, inducing an intuitive Pareto frontier between makespan and active energy. Heterogeneous Non-Aligned: speed and power are not aligned, creating counter-intuitive trade-offs and stronger generalization challenges for learned schedulers. A four quadrant schematic compares queue free host regimes by how virtual machines differ in processing speed and active power. Each quadrant shows a small set of VM markers that illustrate the relation between speed and power. \parHomogeneous Speed: all VMs have the same speed and different power. For a fixed workload the makespan is the same regardless of which VM is chosen, while total active energy changes with the selected power levels. \parHomogeneous Power: all VMs have the same active power and different speeds. Power per unit time is constant. Faster VMs shorten runtime and reduce active energy, slower VMs lengthen runtime and increase energy. \parHeterogeneous Aligned: speed and power increase together. Faster VMs always draw more power. This yields a clear trade off between time and energy, forming an intuitive Pareto frontier from slow low power to fast high power choices. \parHeterogeneous Non Aligned: speed and power have no consistent order. Some VMs are fast and low power, others are slow and high power. Dominance is unclear and the Pareto set can be irregular, creating counterintuitive trade offs and tougher generalization for learned schedulers.
Figure 5. Overview of the proposed GIN-based actor–critic scheduler architecture. Block diagram of a scheduler that uses an actor and a critic with a shared graph neural network. Inputs are two sets of nodes and two edge types. Task nodes carry status flags, remaining work, completion time, and resource needs. VM nodes carry current load, completion times, speed, core counts, available cores, memory capacity, free memory, and idle and peak power. Dependency edges connect parent and child tasks. Compatibility edges connect tasks to VMs that can run them. \parTwo small multilayer perceptrons encode tasks and VMs into a common latent space. Encoded nodes pass through several Graph Isomorphism Network layers that aggregate over both edge families. A global pooling produces a single graph embedding shared by both heads. \parThe actor head builds an embedding for each feasible task and VM pair by combining the task node, the VM node, and the graph embedding. A small scorer maps each pair to a scalar. Invalid pairs are masked. The remaining scores form a task by VM matrix, flattened and passed through softmax to produce a probability distribution over actions. \parThe critic head takes only the graph embedding and uses a small multilayer perceptron to output a single value that estimates expected return from the current state. Arrows indicate shared parameters between encoders and backbone, and separate outputs for policy and value.
| Host cfg | Method | Eval Domain | Makespan | Active Energy |
| HS host configuration | ||||
| HS | LongCP | LongCP | 2.08 | 52.87 |
| HS | wide | LongCP | 2.08 | 51.00 |
| HS | LongCP | wide | 0.70 | 58.92 |
| HS | wide | wide | 0.70 | 57.11 |
| HP host configuration | ||||
Table 1. Cross-domain evaluation of heterogeneous agents across host configurations. Best results for each evaluation domain within a host configuration are in bold.
Figure 6. Empirical attainment functions (EAFs) over 100 test jobs for the wide and LongCP specialists on the wide configuration (top) and the LongCP configuration (bottom). Each panel shows the distribution of the trade-off between normalized makespan (x-axis) and normalized active energy (y-axis), with color indicating the attainment level and black contours marking . Two stacked panels summarize empirical attainment over 100 test jobs for two schedulers: a LongCP specialist and a wide specialist. Axes show normalized makespan on the horizontal axis and normalized active energy on the vertical axis. Each panel depicts the empirical attainment function as filled levels with overlaid contours at attainment levels 0.5, 0.75, and 0.9. The top panel uses the wide host configuration; the bottom panel uses the LongCP configuration. In each panel, the shapes of the attainment regions indicate how often a scheduler reaches points in the time–energy plane. Regions shifted left indicate shorter makespan, regions shifted down indicate lower energy. The side by side attainment patterns allow comparison of which scheduler more frequently reaches low time versus low energy regions, and how the full distribution of outcomes spreads across the trade off frontier.
Figure 7. Correlation between makespan and active energy across Pareto checkpoints for AL (top row) and NA (bottom row), with LongCP and wide specialists. Grid of subplots reporting the correlation between makespan and active energy across saved Pareto checkpoints. The top row corresponds to an aligned regime and the bottom row to a non aligned regime. Columns compare LongCP and wide specialists. Each subplot summarizes, for a sequence of model checkpoints along the Pareto front, how strongly time and energy move together. Positive correlation means runs with longer time also tend to use more energy; negative correlation means improvements in time often come with higher energy or vice versa, indicating a stronger trade off. Near zero indicates weak or inconsistent relationship. The layout lets the reader see how regime and specialization affect the sign and magnitude of the objective correlation across training checkpoints.
Figure 8. Panels: a) Active energy, case NA; b) Active energy, case AL; c) Makespan, case NA; d) Makespan, case AL. A 2 by 2 layout shows objective landscapes in a 2D projection of the actor’s parameter space, with the same axes across panels labeled First Principal Direction and Second Principal Direction. Each panel displays a background field representing the objective value over this plane and a single training trajectory drawn as a curve with a start marker (filled circle) and an end marker (X). Lower values are better for both objectives. \parPanel a (active energy, non aligned regime): the trajectory starts near the upper left and moves downhill toward a broad low energy basin near the center left, then continues to the right, ending slightly above the basin’s minimum. \parPanel b (active energy, aligned regime): the path again descends toward a central low energy region but finishes to the right of the minimum, indicating a modest rise relative to the best area. \parPanel c (makespan, non aligned regime): the trajectory begins left of center, ascends mildly, then turns and descends toward the lower right, finishing close to a region with low makespan. \parPanel d (makespan, aligned regime): the path starts near the upper left, curves toward a low basin near the lower center, and ends mid right, not at the lowest area. \parAcross panels, the same projected coordinates allow comparison of how training moves through different landscapes under two regimes (aligned and non aligned) and two objectives (active energy and makespan). A colorbar is present to indicate objective magnitude, while the curve and markers highlight the progression from initialization to the final checkpoint.
Figure 9. State visitation under a fixed mixed objective and non-aligned speed–power. (a) Conceptual state-space diagram with anti-aligned red (makespan) and blue (energy) descent directions, plus an inset showing non-aligned host speed–power. (b) Long Critical Path (LongCP) training: KDE contours and rollouts concentrate in high-parallelism regions. (c) wide DAG training: visitation shifts toward lower-parallelism states. A 2 by 2 layout shows objective landscapes in a 2D projection of the actor’s parameter space, with the same axes across panels labeled First Principal Direction and Second Principal Direction. Each panel displays a background field representing the objective value over this plane and a single training trajectory drawn as a curve with a start marker (filled circle) and an end marker (X). Lower values are better for both objectives. \parPanel a (active energy, non aligned regime): the trajectory starts near the upper left and moves downhill toward a broad low energy basin near the center left, then continues to the right, ending slightly above the basin’s minimum. \parPanel b (active energy, aligned regime): the path again descends toward a central low energy region but finishes to the right of the minimum, indicating a modest rise relative to the best area. \parPanel c (makespan, non aligned regime): the trajectory begins left of center, ascends mildly, then turns and descends toward the lower right, finishing close to a region with low makespan. \parPanel d (makespan, aligned regime): the path starts near the upper left, curves toward a low basin near the lower center, and ends mid right, not at the lowest area. \parAcross panels, the same projected coordinates allow comparison of how training moves through different landscapes under two regimes (aligned and non aligned) and two objectives (active energy and makespan). A colorbar is present to indicate objective magnitude, while the curve and markers highlight the progression from initialization to the final checkpoint.