Source-linked AI summary
Bounding Queue Waits for Fair Scheduling of Bursty HPC Workloads via Hierarchical Algorithms
Karaen Senthilkumar, Suman Raj, Maxime Gonthier, Kyle Chard, Donpaul Stephens, Ian Foster
TL;DR
Bursty HPC submissions concentrated among heavy users can leave occasional users absorbing queue delays, while existing schedulers do not combine hierarchical fairness with per-job wait bounds for rigid jobs. HyDRA assigns fairness-aware deadlines and ranks waiting jobs dynamically; on Polaris-derived workloads it improves project fairness, on-time starts, and bounded slowdown at a moderate utilization cost.
Problem
Bursty workloads and hierarchical project/user sharing make fairness difficult, while no existing scheduler enforces project budgets, within-project user fairness, and per-job wait bounds for rigid jobs.
Source: §I · pp. 1–2Method
HyDRA assigns each job a fairness-aware deadline using its size, priority, and backlog, ranks waiting jobs with an aging score, and backfills only when fairness limits and deadlines remain satisfied.
Source: §I · p. 2, B. Dynamic Priority Score · p. 5, C. Adaptive Deadlines · p. 5Results
HyDRA achieves 2× the project-level Jain’s index of the best baseline, starts 47% of jobs by their deadlines versus at most 36% for baselines, and lowers 95th-percentile bounded slowdown by 4.2×.
Source: §I · p. 2Takeaways & Limitations
The backlog term keeps deadlines achievable longer during bursts, improving both fairness and the on-time rate.
Source: §I · p. 2HyDRA has the lowest utilization among schedulers for every reported period, trading utilization for fairness.
Source: 1) Comparison with Baselines · p. 8
Abstract
from arXiv · showhide
HPC clusters are shared among many projects, each holding an allocation of node-hours, and ensuring fairness is becoming harder. Foundation models workflows and automated pipelines have made job submissions bursty and concentrated among a few heavy users, so occasional users absorb queueing delays created by frequent ones, with no indication of how long their jobs will wait. Existing schedulers either forget past usage, protect only the job at the head of the queue, or assume that running jobs can be preempted. We propose HyDRA, a Hybrid Deadline and Ranking-Aware scheduler that enforces fairness among users while bounding the queue wait of every job. HyDRA assigns each job a deadline on arrival based on its size, the priorities of its project and user, the current backlog, and how far its project and user are from their entitled share. It ranks waiting jobs by a priority score that grows with waiting time, serves jobs close to their deadlines first, and backfills a job only when no deadline, or fairness limit is violated. We evaluate HyDRA on workloads derived from a year of ALCF Polaris job traces, against conventional schedulers and variants inspired by PCS, Themis, and the PBS job-sort formula used at ALCF. HyDRA achieves $2\times$ the project-level Jain's fairness of the best baseline, starts 47\% of jobs by their deadlines compared with at most 36\% for the baselines even for largest workloads, and lowers the 95th-\%ile bounded slowdown by 4.2$\times$ relative to the next best baseline, at a moderate cost in utilization.
I. INTRODUCTION
Bursty submissions are concentrated among heavy users, leaving occasional users to absorb queue delays. HyDRA combines hierarchical fairness with per-job waiting-time bounds and improves fairness and on-time starts in the reported workloads, at a moderate utilization cost.
I. INTRODUCTION
- Roughly 20% of Polaris users consume more than 95% of core-hours, and users submitting the most jobs are also the burstiest.On both Polaris and Midway3, burstiness rises with the number of jobs submitted; queue time on Polaris also grows with requested core count, so occasional users with large jobs absorb delays from frequent submitters.Source: §I · p. 1, Figure 1 · p. 1, Figure 2 · p. 2
- No existing scheduler enforces project allocation budgets, user-level fairness within projects, and per-job waiting-time bounds for rigid, non-preemptible jobs.The challenge includes preventing one project’s burst from consuming another’s share while keeping bounds useful under bursty load and avoiding idle resources.Source: §I · pp. 1–2
- HyDRA assigns each waiting job a deadline from the fairness objective and permits backfilling only when deadlines, project budgets, and user service-deficit tolerances remain satisfied.Its design separates fairness across projects from fairness among users within each project.Source: §I · p. 2
- 2× the project-level Jain’s index of the best baseline, 47% of jobs started by their deadlines versus at most 36% for baselines, and 4.2× lower 95th-percentile bounded slowdown.The reported gains came at a modest cost in utilization.Source: §I · p. 2
II. RELATED WORK
Prior HPC schedulers address pieces of the problem, but none combines rigid-job support, project entitlements, user fairness, and per-job wait bounds. HyDRA’s related-work contrasts focus on backfilling and fair-share, fair queueing, and queue-wait prediction.
II. RELATED WORK
- None of the compared state-of-the-art approaches supports all four properties: rigid HPC jobs, project entitlements, user-level fairness, and per-job wait bounds.The comparison includes conventional scheduling, fair-share, fair queueing, and wait-bound approaches.Source: §II · p. 2
A. HPC Scheduling, Fair-Share, and Fair Queueing
- EASY backfilling protects only the queue head [6], while fair-share can restore a bursty user’s priority as usage decays; fair queueing assumes service can be divided into small pieces.HyDRA instead protects each waiting job with a deadline and enforces project allocations as hard budgets.Source: A. HPC Scheduling, Fair-Share, and… · p. 3
B. Queue-Wait Prediction and Wait-Time Bounds
- Queue-wait predictors are not fed back into scheduling, whereas HyDRA assigns each job a deadline that accounts for cluster capacity, queue position, user priority, and job size.Conservative backfilling also gives jobs start-time bounds, but bases them on arrival order.Source: B. Queue-Wait Prediction and Wait-Time… · p. 3
C. Deadlines, Slowdown, and Starvation
For rigid HPC jobs, HyDRA assigns scheduler-estimated start deadlines rather than relying on user-provided deadlines or service-lag repayment. Its framework models project budgets and user service, then routes jobs through budget checks, deadline and priority queues, and fairness-guarded backfilling.
C. Deadlines, Slowdown, and Starvation
- Unlike classical deadline scheduling with user-provided deadlines, HyDRA estimates deadlines for jobs without them; aging orders the queue, while deadlines provide a backstop against starvation.EDF’s optimality assumes a single preemptive processor, while other approaches interleave critical and non-critical tasks; HyDRA bounds execution start times for rigid jobs.Source: C. Deadlines, Slowdown, and Starvation · p. 3
A. Problem Formulation
- The framework models online rigid jobs from multiple projects, with project allocation budgets and cluster capacity constraining cumulative service.Jobs request nodes and walltime, hold all requested nodes until completion, and receive a scheduler-assigned start deadline based on a computed waiting-time bound.Source: A. Problem Formulation · pp. 3–4
B. Architecture
- HyDRA initializes each job’s demand, priority, score, and deadline, then checks its project’s remaining budget before inserting it into priority and deadline queues.Deadline-critical jobs are considered first; backfilling is allowed only if waiting-job deadlines, project budget, and user service-deficit tolerance are preserved.Source: Figure 3 · p. 4, B. Architecture · p. 4
IV. FAIRNESS-AWARE HIERARCHICAL SCHEDULING
HyDRA defines hierarchical project and user entitlements, then derives job priorities from the applicable hierarchy level. It normalizes priorities to a fixed range before using them to compute deadlines.
A. Hierarchical Entitlements and Priorities
- Projects receive shares according to project weights; users share a project’s entitlement equally when user weights are absent, or proportionally when they are assigned.Job weights affect job priority at Level-3 but do not change project or user entitlements.Source: A. Hierarchical Entitlements and… · p. 4
- Job priority multiplies the applicable project, user, and job weights at Levels 1–3, then HyDRA converts priorities to the fixed range [1, 5] before computing deadlines.The conversion keeps priorities consistent across hierarchy levels and facilities.Source: A. Hierarchical Entitlements and… · pp. 4–5
B. Dynamic Priority Score
HyDRA ranks waiting jobs with a priority score that rises with waiting time, while assigning each job an adaptive deadline based on its size, importance, and arrival-time backlog. The two mechanisms combine service ordering with a wait bound that reflects current cluster load.
B. Dynamic Priority Score
- The priority score combines job priority, time waiting, and size, so higher-priority and smaller jobs rank higher while aging gradually raises every waiting job’s rank.Aging prevents starvation; the size exponent γ tunes how strongly service demand affects ranking.Source: B. Dynamic Priority Score · p. 5
C. Adaptive Deadlines
- A job’s waiting-time bound has a base component that grows with service demand and shrinks with importance, scaled by κ and the size exponent γ.Large jobs need more nodes at once and are harder to place.Source: C. Adaptive Deadlines · p. 5
- The deadline also adapts to arrival-time backlog, measured against deliverable node-time over a window, ranging from zero for an empty queue to nearly one for a long queue.This adjustment avoids promising the same wait during a burst as on an idle cluster.Source: C. Adaptive Deadlines · p. 5
D. Admission, Selection, and Fairness-Safe Backfilling
HyDRA admits jobs only when project-budget-feasible, prioritizes deadline-critical jobs, and backfills only when the head job’s deadline and budget constraints remain satisfied. Its aging score changes produce predictable, non-oscillating rank changes while jobs wait.
D. Admission, Selection, and Fairness-Safe Backfilling
- Deadline-critical jobs are dispatched before the priority-queue head, while admission rejects jobs that exceed their project’s remaining budget.The scheduler keeps admitted jobs in both priority and deadline queues and removes stale copies after dispatch.Source: D. Admission, Selection, and… · p. 5
- A backfilled job may delay the dispatch-queue head only if the head can still start by its deadline and the candidate remains budget-feasible.Unlike EASY backfilling, HyDRA permits delay within the head job’s deadline, aiming to raise utilization without breaking its wait bound.Source: D. Admission, Selection, and… · pp. 5–6
E. Mathematical Analysis
- Because each waiting job’s score is linear in time, two jobs can swap rank at most once, and the higher-slope job stays ahead while both remain queued.The crossing matters only after both jobs arrive and before either starts; equal-priority, equal-size jobs retain arrival order.Source: E. Mathematical Analysis · p. 6
V. EVALUATION
HyDRA is implemented with deployment-like scheduler components and a simulated cluster, and its baselines share workloads and backfilling conditions. The comparisons include conventional policies, fair-scheduling variants, and ALCF’s production job-sort policy.
A. Implementation and Setup
- HyDRA’s C++20 components run as in a deployment, while the cluster and resource manager are simulated; most baselines use the same architecture with only queue ordering replaced.PCS and ANL instead run in a standalone multi-queue simulator.Source: A. Implementation and Setup · p. 6, B. Baselines · p. 6
B. Baselines
- The six baselines include SJF, project-priority ordering, WFQ, Themis-inspired scheduling, PCS, and an ANL model of ALCF’s PBS job-sort formula.SJF ignores job width and project membership and can starve long jobs; project priority ignores service already received.Source: B. Baselines · p. 6
- All baselines use the same workloads and simulated cluster as HyDRA, reservation-based backfilling, and requested walltimes rather than actual runtimes.WFQ orders by a virtual finish tag; the Themis-inspired variant prioritizes projects with the largest service deficit over a rolling 300 s window, while PCS uses four walltime-based queues.Source: B. Baselines · p. 6
C. Workloads
The evaluation builds workloads from ALCF Polaris production traces and measures fairness, deadline accuracy, slowdown, queue waits, and utilization. Workload windows are sampled across load categories and durations, with project, user, and job priorities drawn from the same five-level range.
C. Workloads
- Workloads are sampled from the 2025 ALCF Polaris production traces, whose fields map directly to the job model; runtimes exceeded walltimes in 19% of observed cases.Jobs were allowed to continue beyond walltime, with a p99 overshoot of 0.1%.Source: C. Workloads · pp. 6–7
- Synthetic workloads sample 2-, 6-, and 12-hour windows by user-load quantile, classify them as unconditioned, busy, bursty, or highly bursty, and vary project counts from 50 to 1,000.Project, user, and job priorities are drawn uniformly from 1 to 5.Source: C. Workloads · p. 7
D. Metrics
- Fairness is summarized by Jain’s index over received-to-entitled service ratios, while deadline evaluation reports on-time starts and deviation between actual and promised waits.The evaluation also reports bounded slowdown by priority tier, queue-wait averages and 95th percentiles, and cluster utilization.Source: D. Metrics · p. 7
E. Results
On the Large workloads, HyDRA improves project fairness and waiting-time outcomes over the baselines, with a moderate utilization cost. Under light load, all schedulers start jobs on time and achieve high fairness.
1) Comparison with Baselines:
- 0.24 project-level Jain’s index for HyDRA is twice SJF’s 0.12, the strongest baseline, and up to 4× the other schedulers.The comparison covers Large workloads.Source: Figure 4 · p. 8, 1) Comparison with Baselines · p. 8
- 47% median on-time rate for HyDRA exceeds at most 36% for the baselines, while its tail slowdown is 4.2× lower than the next-best baseline.The on-time rate and tail slowdown are reported across the Large workloads.Source: Figure 4 · p. 8, 1) Comparison with Baselines · p. 8
- HyDRA has the lowest utilization in every period but lies on the fairness-utilization Pareto front at its high-fairness end.The baselines with the highest utilization are 11×, 1.5×, and 1.3× less fair at 2, 6, and 12 h, respectively.Source: Figure 5 · p. 8, 1) Comparison with Baselines · p. 8
- Under light load, every scheduler starts all jobs on time and has Jain’s index of at least 0.97.Small and Medium workloads keep utilization below 43%, so jobs rarely wait.Source: 1) Comparison with Baselines · p. 8
- 74 node-hours median 95th-percentile project service lag for HyDRA is 34% below WFQ (111), the closest baseline.Themis, Priority, and PCS leave the worst-off projects 211–235 node-hours behind.Source: 1) Comparison with Baselines · p. 8
2) Performance of HyDRA in presence of bursts:
In a mixed workload with activity levels shuffled every 30 minutes, HyDRA’s backlog term adapts deadlines to queued demand. This keeps deadlines achievable longer and supports positive slack, higher on-time rates, and fairer dispatch.
2) Performance of HyDRA in presence of bursts:
- With the backlog term, HyDRA’s deadlines grow with queued demand, whereas without it the scheduler keeps promising the same waits as the queue fills.The first workload window is highly bursty, so the queue fills quickly.Source: Figure 6 · p. 9, 2) Performance of HyDRA in presence of… · p. 9
- When queued demand is small relative to cluster capacity, the backlog factor rises almost linearly with demand; when demand greatly exceeds capacity, it approaches 1 and deadline growth stops.This limits how much the deadlines can expand under sustained overload.Source: 2) Performance of HyDRA in presence of… · p. 9
- Longer positive slack raises the on-time rate and supports fairer dispatch because few jobs are deadline-critical and the priority queue serves most jobs.As slack turns negative, more jobs become deadline-critical and are served in deadline order.Source: 2) Performance of HyDRA in presence of… · p. 9
3) Performance of HyDRA across hierarchy levels:
HyDRA’s hierarchical priorities combine project, user, and job weights, with experiments comparing independently sampled weights against Polaris queue-based job priorities. Higher hierarchy levels produce longer deadlines on average, while queue-based job priorities tighten them.
3) Performance of HyDRA across hierarchy levels:
- Project, user, and job weights are sampled independently and uniformly from {1, . . . , 5}, producing increasingly low-skewed hierarchical priorities from Level-1 to Level-3.The experiment also samples job priorities from Polaris queue distributions, mapping queues to priorities in {1, . . . , 5}.Source: 3) Performance of HyDRA across… · p. 9, Figure 7 · p. 9, Table IV · p. 9
- Expected priority rises from 3 at Level-1 to 9 at Level-2 and 27 at Level-3 under independent uniform weight sampling.The weights are independently sampled from {1, . . . , 5}.Source: 3) Performance of HyDRA across… · p. 9
- Level-3 deadlines exceed Level-2 deadlines, which exceed Level-1 deadlines, for most of the run.The capped priority decreases with hierarchy level, and the waiting-time bound is inversely proportional to capped priority.Source: Figure 8 · p. 10, 3) Performance of HyDRA across… · p. 10
- Level-3 with queue-based job priorities gives jobs tighter deadlines on average than default Level-3.Polaris queue-based job priorities are skewed toward high weights, raising expected capped priority.Source: Figure 7 · p. 9, 3) Performance of HyDRA across… · p. 10
4) Performance of HyDRA against varying demand conditions:
Across ALCF Polaris workloads, HyDRA improves fairness and bounded slowdown at a moderate utilization cost. Under varying demand, scheduler performance shifts as the share of high-demand jobs rises, with HyDRA maintaining the best balance between fairness and deadlines.
4) Performance of HyDRA against varying demand conditions:
- The comparison conditions the 2 h Large workload by assigning jobs either 16 nodes for 3,600 s or 1 node for 900 s, with runtimes set to 90% of walltime.The 25-75 workload has 25% high-demand jobs and 75% low-demand jobs; 50-50 has equal shares, while arrivals and priorities stay unchanged.Source: 4) Performance of HyDRA against… · p. 10, Figure 9 · p. 10
- HyDRA is fairest on 25-75, with project-level Jain’s index 0.45 versus 0.34 for WFQ and 0.33 for Themis, but WFQ and Themis overtake it on 50-50.On 50-50, WFQ scores 0.40, Themis 0.36, and HyDRA 0.31; WFQ also has the lowest project lag on both workloads. Fixed runtimes at 90% of walltimes make WFQ’s walltime-based tags match actual service, unlike on Polaris traces where walltimes greatly overestimate runtimes.Source: 4) Performance of HyDRA against… · p. 10, Figure 9 · p. 10
- HyDRA and SJF start the most jobs by their deadlines on both workloads—42% and 44% on 25-75, and 23% and 29% on 50-50—while WFQ and Themis start at most 13%.HyDRA’s tail slowdown is within 8% of the best scheduler; overall, it alone offers the best balance between fairness and deadlines as high-demand jobs rise from 25% to 50%.Source: 4) Performance of HyDRA against… · p. 10, Figure 9 · p. 10
VI. CONCLUSION
- HyDRA achieves 2× fairness scores and lowers 95th-%ile bounded slowdown by 4.2× relative to the next best baseline, at a moderate cost in utilization.These overall results are reported for workloads sampled from ALCF Polaris traces.Source: §VI · p. 11