PaperlayerView exact revision on arXiv

Source-linked AI summary

A Smallest-Need-First Job Scheduling Framework with Adaptive Optimization of Idle Node Counts for Energy-Efficient HPC Systems

Reza Pulungan, Raka Satya Prasasta, Santana Yuda Pradata, Mursalim, Hiroyuki Takizawa, Muhammad Alfian Amrizal

arXiv:2608.29656v1cs.DC

TL;DR

HPC power-state management must reduce idle energy without imposing excessive wake-up delays on rigid parallel jobs. SNF-ICON combines SNF scheduling, predictive wake timing, workload-gated Markovian spare optimization, and SNF+IPM fallback. Across six workload–platform cases, it reduces average waiting time versus FCFS/B+IPM, while the best waiting-time–energy trade-off depends on workload and platform.

  • Problem

    Power-state management must balance idle-energy savings against wake-up delays for rigid parallel jobs, while future arrivals and node requests remain unknown.

  • Method

    SNF-ICON combines SNF scheduling, predicted queued-job releases, adaptive warm-spare selection, and workload-screened switching to SNF+IPM fallback.

  • Results

    SNF-ICON reduces average waiting time relative to FCFS/B+IPM in all six workload–platform cases, while remaining close to heuristic energy baselines in most cases.

  • Takeaways & Limitations

    The workload screen is useful for spare-node planning, but no single configuration gives the best waiting-time–energy trade-off across workloads and platforms.

Abstract

from arXiv · show

Power-state management in high-performance computing (HPC) clusters must reduce idle energy without excessive wake-up delays for rigid parallel jobs. This paper presents SNF-ICON, an event-driven controller combining smallest-need-first (SNF) gang scheduling, predictive wake timing, and adaptive warm-spare control. At each scheduler invocation, recent interarrival and completed-service samples are screened for sufficiency, exponential-like variability, low lag-one autocorrelation, and acceptable Kolmogorov-Smirnov distance. Rejected or data-sparse windows use SNF+IPM (Intelligent Power Manager), whereas accepted windows activate release prediction and an exponential next-event model. Warm-spare optimization is applied only when queue, event, and arrival-recency conditions permit, balancing estimated waiting and non-compute energy over a timeout-capped horizon. We evaluate four DAS2 trace segments and a generated Markovian workload on AOBA-derived 64-node models, plus SDSC Blue on an AOBA-derived 1152-node model. SNF-ICON is compared with SNF+IPM and First Come First Served (FCFS) + backfilling with IPM. It reduces average waiting time relative to the FCFS-based baseline in all six cases and remains close to at least one heuristic energy baseline in five. The generated workload spends substantial time in ICON mode, whereas DAS2 workloads operate mainly in fallback. Furthermore, cross-platform results show strong dependence on node-transition and power models. Thus, no single policy or parameter set works best in every case.

I. INTRODUCTION

HPC power management must balance idle-energy reduction against wake-up delays for rigid parallel jobs. SNF-ICON combines SNF scheduling, predictive node transitions, and adaptive warm-spare control, with SNF+IPM fallback when workload data are insufficient or unsuitable.

  • Motivation: Idle-node power management can reduce substantial energy use, but switching off too many nodes increases waiting time for rigid parallel jobs.JUSUF’s annual electricity use fell from about 660 MWh to 495 MWh, a 25% reduction, after idle nodes were powered down.
  • Motivation: Rigid jobs require all requested nodes simultaneously, so queue order and node power states must be managed together.A job requesting r nodes cannot start until all r nodes are available at the same time.
  • Scheduling rationale: SNF is motivated by theory showing a lower mean-waiting-time growth rate than FCFS for multiserver jobs, although that theorem does not cover this system’s practical constraints.The theorem excludes EASY backfilling, finite non-preemptive traces, node power states, and wake-up delays.
  • Proposed approach: SNF-ICON combines SNF scheduling, predicted wake times for queued jobs, and adaptive control of warm spare nodes for future jobs.Its main decision is how many spare nodes to keep ready while using recent data to determine whether model-based planning is appropriate.
  • Proposed approach: When workload data fail the screening check or contain too few samples, the method uses SNF+IPM instead of ICON-specific prediction and spare-node selection.The fallback retains queued-job scheduling, wake planning, and idle timeouts while omitting ICON-specific runtime and next-event modeling.

E[T FCFS

SNF is used as a queue-ordering policy for rigid jobs, while separate power-management logic handles node wake-ups and warm spares. The method uses recent workload windows to decide whether SNF-ICON’s Markovian spare calculation is applicable.

  • SNF motivation: SNF reaches the lower-bound waiting-time growth rate, whereas FCFS has a worse growth rate when the largest job size grows with the system.This result comes from a multiserver-job model under its stated heavy-traffic and maximum-need assumptions.
  • Power-management boundary: SNF alone does not determine when sleeping nodes should wake or how many idle nodes should remain ready for future jobs.Queued jobs support wake planning, but requested runtimes may differ from actual runtimes.
  • SNF priority: SNF orders queued jobs by requested node count, then requested runtime and arrival-based identifier to break ties.The smallest requested node count receives priority.
  • SNF dispatch: At each scheduling call, the first fitting SNF-ordered job starts immediately, and later jobs are not checked once the first non-fitting job is reached.Later jobs request at least as many nodes and therefore cannot fit during that call.
  • Mode selection: Accepted recent windows use SNF-ICON’s spare calculation, whereas rejected or data-sparse windows use SNF+IPM without spare-node planning.The decision is revisited at each scheduler invocation.

A. Markovianity of the observed workload

The workload screen tests whether recent arrival and service observations are sufficiently close to exponential, weakly dependent, and adequately sampled. Accepted windows enable ICON calculations; rejected or sparse windows trigger fallback control.

  • Screened series: The screen examines interarrival intervals and completed-job execution times because they determine the race between the next arrival and completion.Requested-node counts are modeled separately with an empirical probability mass function and need not be exponential.
  • Sample sufficiency: Each recent series must contain between nmin and nmax samples before further workload checks are applied.The screen uses observations from only the last TM seconds.
  • Exponential-like variability: The variability check compares the coefficient of variation with the exponential-distribution value CV = 1.The tolerance around this value is controlled by δcv.
  • Temporal dependence: The dependence check limits absolute lag-one autocorrelation, motivated by the zero population autocorrelation of independent identically distributed exponential observations.The allowed magnitude is controlled by δρ.
  • Acceptance rule: A recent series is accepted only when it has enough samples and satisfies every enabled screening condition, including the exponential-fit distance rule.Arrival and service acceptance are combined according to whether service samples are required.
  • Operational interpretation: Acceptance does not prove that the workload is Markovian; it only indicates that recent data are close enough to the exponential model for controller use.The screen is rerun at every scheduler call, with thresholds treated as configurable settings.
  • Mode execution: Rejected windows execute baseline SNF+IPM planning, whereas accepted windows enter ICON to dispatch fitting jobs, predict releases, and conditionally optimize warm spares.Warm-spare optimization additionally depends on queue, event, and arrival-recency conditions.

B. Policy and mode switching

SNF-ICON separates queued-job handling from future-job preparation, selecting fallback or ICON behavior at each invocation. In ICON mode, it dispatches queued jobs in SNF order, plans releases and wake-ups, and may prepare warm spares only at qualifying decision points.

  • Mode selection: Each invocation updates state and evaluates the workload window; rejected windows delegate the complete call to SNF+IPM, while accepted windows use ICON prediction and planning.A later window can return to ICON mode because mode selection applies only to the current call.
  • Mode selection: Warm-spare optimization requires an empty queue after immediate dispatch, a qualifying decision epoch, and an open arrival-recency gate.Arrived jobs always take precedence over preparation for future jobs.
  • Queued-job handling: Both modes use SNF for queued jobs, but ICON updates estimates and builds a future plan whereas fallback uses baseline SNF+IPM procedures.ICON-specific release prediction and spare planning distinguish the two paths.
  • Queued-job handling: For each queued job, ICON estimates the earliest feasible start, selects required nodes by lowest estimated pre-start non-compute energy, and plans its finish and wake time.Node-state priority, timeout priority, and identifier break selection ties.
  • Future-SNF planning: Sequential planning updates each selected node’s next-available time to the planned finish and sets the next planning barrier to the current planned start.This prevents later planned start times from moving backward.
  • Future-SNF planning: The future-SNF plan preserves SNF order while allowing different queued jobs to share a planned start when they use different nodes.A sleeping node selected for multiple jobs retains its earliest wake time.
  • Adaptive estimates: Arrival, service, and resource estimates are updated adaptively using exponential moving averages and request-count weights.The arrival estimate uses the newest interarrival interval and initializes from a configured positive arrival rate.

E. Predicting the next event and time window

ICON models the next arrival or completion as a competing-event process and caps the prediction horizon at the earliest relevant timeout. Completion rates use job-specific remaining-runtime predictions when available, otherwise an aggregate service-rate approximation.

  • Completion prediction: Completion-event estimation uses the earliest positive predicted remaining runtime when available and otherwise an aggregate service-rate approximation.The same completion estimate supports release prediction and the completion-rate calculation.
  • Competing events: At an ICON decision, arrival and completion times are modeled as independent exponential clocks with rates bλ(t) and bλC(t).The approximation treats the two event times as independent.
  • Competing events: The total next-event rate is the sum of arrival and completion rates, and the probability that the next event is an arrival is proportional to its rate.This follows the competing-exponential-clock model.
  • Prediction horizon: The prediction horizon is capped by the earliest future idle-node timeout, or by Hmax when no such timeout exists.The cap limits the modeled time window for subsequent planning.

F. Valid spare-node targets

SNF-ICON constrains warm-spare targets to feasible counts that preserve nodes already required to remain warm and switch off expired-timeout nodes. Candidate plans then estimate readiness delays for possible future requests.

  • Target definition: The warm-spare target x is the number of non-computing nodes prepared to run future jobs without a wake-up delay.Candidate targets are drawn from a nonempty feasible range.
  • Feasibility constraints: Nodes with expired idle timeouts are switched off in every candidate plan, while nodes that cannot currently switch off must remain warm.Other idle nodes may remain warm or be switched off according to x.
  • Feasibility constraints: The feasible target range respects configured Smin and Smax while including nodes already switching on and idle nodes that cannot switch off.These mandatory nodes can make the lower feasible bound exceed the configured minimum.
  • Feasibility constraints: Smax is a preferred limit rather than a strict limit because mandatory warm nodes may already exceed it.The bound therefore reflects current node-state constraints as well as configuration.
  • Readiness estimation: For each candidate target, the controller estimates readiness delays using node state and transition time, then sorts non-computing-node readiness times.Warm idle nodes have zero delay; sleeping or switching-off nodes include wake-related transition time.
  • Readiness estimation: The request-weighted readiness estimate uses predicted probabilities for future node requests, while waiting caused by currently running jobs is excluded because it is identical across targets.When the request exceeds available non-computing nodes, the index is capped at that availability.

H. Estimated energy and spare-node selection

ICON evaluates each feasible spare-node target over a capped horizon using estimated non-compute energy and power-induced waiting. It selects a unique target through lexicographic minimization of the combined cost and tie-break criteria.

  • Energy estimation: The controller estimates sleeping, switching, and idle-state energy over the mean capped horizon, excluding compute energy required by running jobs.The resulting energy is an estimate over the capped horizon rather than exact expected energy over a random interval.
  • Energy estimation: For every candidate target, node-level non-compute energy accounts for the relevant state duration and power, including idle and switching periods.Wake, sleep, and switch-off energy are calculated analogously.
  • Implementation: Fig. 2 summarizes the SPARS implementation architecture for the controller and its managers.The supplied passage identifies the figure as an implementation-architecture overview.
  • Target selection: The selected target minimizes a lexicographic cost that first prioritizes combined waiting and energy, then waiting, energy, and finally the target value.This ordering makes the selected target unique and deterministic.

I. Arrival-recency gate, completion shutdown, and idle timeout

The arrival-recency gate independently determines whether ICON may plan warm spares for future jobs, while closed-gate completions shut down newly released nodes unless queued or planned work needs them. The implementation separates fallback, spare-planning, and gate states and reports analytical complexity bounds without measuring actual scheduler runtime.

  • Arrival-recency gate: The arrival-recency gate opens only when the latest recorded arrival is recent enough; when closed, ICON remains active but skips warm-spare planning.The gate is checked in ICON mode after queued jobs are handled and is distinct from the Markovianity-based fallback rule.
  • Completion shutdown and idle timeout: After a completion with the gate closed, newly released nodes switch off unless queued or planned jobs require them.Other idle nodes follow the normal idle-timeout policy, and the next timeout caps the energy horizon.
  • Diagnostics: At each invocation, the implementation records policy mode, spare-planning status, gate state, screening diagnostics, and power-management actions separately.This separation prevents a closed gate or nonempty queue from being misclassified as fallback.
  • Control modes: Fallback invokes SNF+IPM planning, whereas ICON additionally predicts releases and performs warm-spare planning.Both modes can schedule wakes for queued jobs, but only ICON plans spare capacity.
  • Complexity and scope: The analytical bounds include O(n log n) screening, O(qN log N) future planning, and O(N^2 log N) spare optimization.These are algorithmic bounds; experiments did not measure scheduler execution time, so implementation profiling remains necessary.

B. Workloads and platform configurations

The evaluation spans six workload–platform cases, including four DAS2 traces, a generated Markovian workload, and SDSC Blue on a larger model. SNF-ICON consistently improves waiting time over FCFS/B+IPM, while energy remains near a heuristic baseline in most cases and ICON occupancy varies sharply by workload.

  • Workloads and platform configurations: The base evaluation uses four 3000-job DAS2 traces and a 3000-job generated Markovian workload on AOBA-derived 64-node models, plus SDSC Blue on an AOBA-derived 1152-node model.The generated workload uses exponential interarrival and service assumptions.
  • Waiting-time comparison: SNF-ICON reduces mean waiting time relative to FCFS/B+IPM in all six cases, by approximately 2.2%, 44.8%, 2.4%, 11.6%, 42.4%, and 16.4%, respectively.Relative to SNF+IPM, waiting improves in the first five cases and increases by 0.15% on SDSC Blue.
  • Energy comparison: SNF-ICON stays within about 1% of at least one heuristic energy baseline in five cases, but its generated-workload energy waste is 5.94 MWh.That generated-workload value is approximately 6.2% above SNF+IPM and 6.9% above FCFS/B+IPM.
  • RL comparison: Dataset-specific RL policies create more extreme trade-offs, exchanging 32–76% waiting reductions for 4.8–5.8 times SNF-ICON energy on three DAS2 traces.On DAS2 FS2 and Markovian 3000, RL instead lowers energy by approximately 14% and 17% while increasing waiting to about 1.9 and 6.5 times SNF-ICON.
  • Mode occupancy: The generated Markovian workload spends 70.9% of simulated time in ICON, whereas DAS2 FS1–FS4 spend only 0.7–2.1% there and operate mainly in fallback.DAS2 fallback often reflects sparse samples or failed workload-screen statistics; ICON is more active during busier intervals.

D. Variant comparison and empirical Pareto frontier

SNF-ICON and its variants generally expand the waiting-time–energy trade-off, with several configurations reaching empirical Pareto frontiers. Results also show that fallback, workload, platform, and parameter choices materially affect the preferred configuration.

  • Variant comparison: The complete SNF-ICON configuration lies on the empirical Pareto frontier in four of six panels, including DAS2 FS1–FS3 and Markovian 3000.The proposed family also supplies multiple nondominated points across workloads.
  • Variant comparison: On SDSC Blue, SNF+IPM slightly dominates complete SNF-ICON, while SNF-ICON-NF reduces waiting time by approximately 3.1% at approximately 8.6% higher wasted energy.SNF+IPM reduces mean waiting time by approximately 0.15% and wasted energy by 0.41% relative to the complete configuration.
  • Variant comparison: Disabling fallback changes the trade-off more visibly than disabling the arrival-recency gate, and no single proposed variant is nondominated everywhere.NG usually overlaps or remains close to the complete method, while NGNF remains close to NF.
  • Job-size effects: SNF-ICON generally has lower or comparable waiting-time medians to FCFS/B+IPM for small and medium job-size bins, without establishing starvation freedom.Large-job distributions are broad, and the Markovian 3000 workload has too few large jobs for a strong fairness conclusion.
  • Parameter effects: Longer Markovianity lookback windows can reduce waiting time while increasing energy, whereas increasing waiting-time weight α generally favors faster starts at higher energy use.For Markovian 3000, the complete configuration moves from approximately 2.9 min and 5.76 MWh at TM = 1 h toward approximately 2.0 min and 6.04 MWh for longer windows.
  • Cross-platform robustness: Platform models substantially change absolute energy and waiting-time scales, and the preferred nondominated configuration varies across workloads and platforms.SDSC Blue uses approximately 5.22 MWh on Taurus versus approximately 36.3–39.9 MWh on AOBA.
  • Overall evaluation: SNF-ICON reduces average waiting time relative to FCFS/B+IPM in all six workload–platform cases while remaining close to heuristic energy baselines in most cases.The generated Markovian workload spends substantial time in ICON mode, whereas DAS2 workloads operate mainly in fallback.

APPENDIX A JOB-SPECIFIC RUNTIME AND RELEASE PREDICTION

The appendix describes runtime and release prediction from observed-to-requested runtime ratios, using separate estimates for queued and active jobs. These estimates feed predicted finish times and the release map.

  • Runtime model: The predictor assumes a shared, slowly changing distribution for each job’s actual-to-requested runtime ratio.Its log-scale mean and variance are tracked with exponential moving averages.
  • Runtime model: Observed completed-job runtimes provide service-screen samples and update the log-ratio moments used by the predictor.The updates use the service smoothing factor ρS, producing estimated median and standard deviation values.
  • Runtime estimates: Queued jobs use the median predicted runtime, while active jobs use the conditional mean remaining runtime after accounting for elapsed execution.These estimates are intentionally different for queued and active cases.
  • Runtime estimates: The implementation evaluates the active-job survival-function ratio in log space to avoid numerical problems.The conditional remaining-runtime calculation subtracts elapsed runtime after combining the relevant numerator and denominator.
  • Release prediction: Predicted finish times are computed for active jobs and queued jobs planned to start at s_j, then used in the release map.The release map combines these finish-time estimates for node-release planning.

APPENDIX B EXPECTED UNFINISHED TRANSITION TIME

The appendix derives the expected unfinished portion of a node transition when the next modeled event may occur before the transition completes. This quantity captures residual transition time at the event.

  • Setup: The lemma models a node transition with d units of time remaining and a random time T to the next event.The transition can remain unfinished only when T < d.
  • Expected residual: The expected unfinished transition time is computed as the residual transition duration observed when the next event occurs before completion.The derivation uses a tail-integral identity.
Loading 2608.29656v1…