Bounding Queue Waits for Fair Scheduling of Bursty HPC Workloads via Hierarchical Algorithms

Bounding Queue Waits for Fair Scheduling of Bursty HPC Workloads via Hierarchical Algorithms Karaen Senthilkumar1 , Suman Raj1,2 , Maxime Gonthier3 , Kyle Chard1,2 , Donpaul Stephens4 , Ian Foster2,1 1

Department of Computer Science, University of Chicago, IL, USA Data Science and Learning Division, Argonne National Laboratory, Lemont, IL, USA 3 Inria Centre at the University of Bordeaux, Bordeaux, France 4 AirMettle, Inc., Houston, TX, USA Email: {karaen, sumanraj, chard}@uchicago.edu, maxime.gonthier@inria.fr, donpaul@airmettle.com, foster@anl.gov

100

106

80

104

60

102

40

100

20

10

−2

0

250

500

750

0 1000

0.9

Burstiness score (B)

108

Cumulative core-hours (%)

Total core-hours

Abstract—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× 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× relative to the next best baseline, at a moderate cost in utilization.

0.6 0.3 0.0 −0.3 −0.6 −0.9 101

102

104

103

Number of jobs submitted per user

User rank by core-hours consumed

100 90.9

104

72.7

102

54.5

100

36.4

10−2

18.2

10−4

0

400

800

1200

1600

User rank by core-hours consumed

0

0.9

Burstiness score (B)

107 106

Cumulative core-hours (%)

(a) Polaris: users ranked by core-hours(b) Polaris: burstiness B against consumed. number of jobs submitted.

Total core-hours

arXiv:2610.32027v1 [cs.DC] 23 Oct 2026

2

0.6 0.3 0.0 −0.3 −0.6 −0.9 101

102

103

104

105

106

Number of jobs submitted per user

(c) Midway3: users ranked by core-(d) Midway3: burstiness B against hours consumed. number of jobs submitted.

Fig. 1: On both Polaris and Midway3, a few users consume most of the resources (a, c), and the users who submit the most jobs are also the burstiest (b, d).

I. I NTRODUCTION Most HPC facilities, from leadership computing centers such as the Argonne Leadership Computing Facility (ALCF) to university clusters, allocate compute time to projects, which is consumed by jobs submitted by individual project users. At the job level, priority policies and backfilling determine which jobs run next. When HPC workloads consisted of long, planned batch campaigns, this was a reasonable approach; however, the adoption of machine learning models in scientific computing has changed submission behavior. Hyperparameter sweeps, inference campaigns, and checkpoint-restart training runs often arrive in dense bursts separated by relatively quiet periods. Arrivals are now far more variable, and that variability is concentrated among a small number of users. Figure 1 shows how uneven this sharing has become. We analyze traces from a year of job records on ALCF Polaris: roughly 20% of users consume more than 95% of the core-hours (Fig. 1a), and consumption on the University of Chicago’s RCC Midway3 cluster is similarly concentrated (Fig. 1c). The heaviest users are also the burstiest. On both

systems, the Goh–Barabási burstiness parameter B [1] rises with the number of jobs a user submits (Figs. 1b and 1d). Moreover, because the queue time on Polaris also grows with the number of cores requested (Fig. 2), the delay created by a burst is not shared evenly. Hence, we observe that a heavy user’s burst fills the queue, and a large job from an occasional user must wait behind the burst before it can be placed. Users who submit rarely and at scale end up absorbing the delay generated by users who submit often. Preventing bursty users from undermining fairness for occasional users is challenging for three major reasons. First, HPC jobs are rigid and usually non-preemptible. A tightly coupled job holds all of its nodes until it finishes and generally cannot be paused or resized without application support [2]. Second, fairness is hierarchical. Projects have allocation budgets that must not be exceeded, and within each project,

1

Median queue wait time

TABLE I: HyDRA compared to SOTA. ✓: supported; (✓): soft or partial; –: not supported. The last column gives the source of a per-job wait bound, if any.

Range (min max)

Queue Wait Time (Seconds)

107 105

Rigid Project User Per-job HPC jobs entitlement fairness wait bound

Approach

103 101 64

704 1344 2048 3200

4608 6656 8704 15360 35712

Number of Cores Requested

Fig. 2: Mean and range of queue times versus the number of CPU cores requested for Polaris.

✓ ✓ ✓ ✓ – – ✓

EASY backfilling [6], [3] Selective reservation [7] Learned schedulers [8] Fair-share (Slurm) [5] WF2 Q, H-PFQ [9], [10] UWFQ [11] Queue-wait predictors [12], [13] Deadline scheduling [14], [15]

– – – (✓)a ✓ – –

– – – (✓)a ✓ ✓ –

Arrival order Global threshold – – Divisible service only – Predicted, not enforced

(✓)b

–

–

Given as input

HyDRA (our work)

✓

✓

✓

Assigned at arrival

a

Relative shares computed from decayed usage; no hard budget. b EDF’s optimality assumes preemption; Gonthier et al. interleave critical and non-critical tasks instead of preempting them.

users have project-specific priorities, so the scheduler must prevent one project’s burst from consuming another’s share and one user’s burst from crowding out teammates. Third, waiting-time bounds are hard to guarantee. Under bursty load, and with walltime requests that overestimate runtimes [3], [4], a bound that is too tight is routinely missed, while a bound that is too loose is of no use to users. Moreover, enforcing a bound must not leave the machine idle. Existing mechanisms for fairness do not fully address this problem. Fair-share schedulers can use past usage to regulate fairness, but only with finite memory. For instance, Slurm’s multifactor plugin decays historical consumption with a configurable parameter [5], so a user who bursts, goes quiet, and returns has their fairness index restored. EASY backfilling [6], [3], commonly layered over First-Come-First-Served (FCFS) ordering in HPC clusters, raises utilization by letting a short job run ahead of the queue head, provided it does not delay the head job’s reservation. Thus, a job can be repeatedly overtaken because the mechanism does not account for how long it has already waited. As Table I summarizes, no existing scheduler enforces project-level allocation budgets, user-level fairness within each project, and per-job waiting-time bounds for rigid, nonpreemptible jobs. We present HyDRA, a hybrid deadline and ranking-aware hierarchical scheduler that explicitly separates fairness across projects from fairness among users within each project, while enforcing waiting-time guarantees for non-preemptible jobs. At the project level, the scheduler accounts for each project’s allocation budget. Within a project, service is allocated among users according to the desired fairness policy. Most importantly, each waiting job is assigned a deadline derived from this fairness objective. With our model, backfilling can now respect fairness as a lower-priority job may be backfilled only when doing so preserves the deadlines of waiting jobs, respects the project’s remaining allocation budget, and keeps each user’s service deficit within a specified tolerance. In this paper, we make the following key contributions: 1) We first characterize job traces from ALCF Polaris (§ I). We use this to motivate and define the problem of scheduling rigid jobs submitted by the users of many projects to

a shared HPC cluster while ensuring fairness (§ III-A). 2) We propose the architecture of HyDRA, a hierarchical scheduling framework, that enforces precise project allocation budgets while optimizing fairness between users within a project.(§ III-B). 3) We propose fairness-aware hierarchical scheduling heuristics for HyDRA that derive the entitlements and priorities of projects, users, and jobs at three levels of hierarchy, rank waiting jobs by a dynamic priority score that grows with their waiting time, and assign each job an adaptive deadline from its size, its priority, and the current backlog (Section IV). We also show mathematically that, with this score, any two waiting jobs exchange rank at most once (§ IV-E). 4) We evaluate HyDRA against six baselines, including SOTA schedulers and the production policies of ALCF, on workloads sampled from ALCF Polaris trace. Under heavy load, HyDRA achieves twice the project-level Jain’s index of the best baseline, starts 47% of jobs by their deadline compared with at most 36% for the baselines, and lowers the 95thpercentile bounded slowdown by 4.2×, at a modest cost of utilization. Its backlog term keeps deadlines achievable for longer under bursts, which improves both its fairness and its on-time rate (§ V). II. R ELATED W ORK We review prior HPC work in three areas: (1) scheduling, fair-share, and fair queueing; (2) queue-wait prediction and wait-time bounds; and (3) deadlines, slowdown, and starvation. Table I compares state-of-the-art (SOTA) approaches on the four properties that HyDRA combines: support for rigid HPC jobs, project-level entitlements, user-level fairness, and a perjob wait bound. None of the others provides all four. A. HPC Scheduling, Fair-Share, and Fair Queueing Most HPC centers combine a multifactor priority queue with backfilling [5], [16]. Backfilling variants differ in which jobs they protect. EASY backfilling protects only the job at the head of the queue [6], conservative backfilling protects every

2

job in arrival order [3], and selective reservation protects a job only once its slowdown passes a global threshold [7]. SOTA schedulers learn which job to run next [8] or account for burst buffers, multiple resources, power caps, and heterogeneous or changing cluster capacity [17], [18], but they still optimize averages from a cluster perspective and promise nothing to any single job. In contrast, HyDRA protects every waiting job with its own deadline, and it backfills a job only if every deadline still holds, the project stays within its budget, and the user’s service deficit stays within its tolerance. In HPC systems, fairness between users typically comes from fair-share, which lowers a user’s priority according to their recent usage [5]. Its outcome depends heavily on configuration [19], and because past usage decays, a user who bursts and then goes quiet soon gets their priority back. Metrics such as fair start time [20], Jain’s index [21], and packingaware fairness measures [22] can show the damage afterwards, but they do not prevent it. HyDRA instead enforces project allocations as hard budgets. Fair queueing offers what fair-share lacks [9]: each flow receives a proportional share with bounded delay. Some [10] extends this to a hierarchy form, much like our projects and users, while others [11] adapt it to bursty users. All of these assume that service can be divided into small pieces, such as packets in networking or short tasks, so that a user who falls behind can be repaid quickly. A rigid HPC job holds its nodes until it finishes, which leaves the scheduler a single knob of execution start time. HyDRA keeps project-to-user hierarchy but bounds execution start times rather than service lag.

ML clusters, Chronus [25] and DeepPlus [26] likewise try to meet completion deadlines that users provide. In HyDRA, by contrast, jobs arrive without deadlines, and the scheduler assigns each one an estimated deadline. Per-job delay is usually measured by stretch and maximum flow in theory [27], [28] and by bounded slowdown in HPC [29]. Favoring small jobs improves average stretch and slowdown but can be unfair to large jobs [30], and HyDRA makes the weight given to job size tunable. Some schedulers fight starvation with aging [17], but aging alone guarantees nothing, since how fast a job moves up depends on the other jobs in the queue. HyDRA therefore uses aging to order the queue and relies on deadlines as a backstop. III. H Y DRA F RAMEWORK In this section, we formulate the problem of scheduling rigid jobs submitted by users of many projects to a shared HPC cluster while ensuring fairness and describe the architecture of HyDRA scheduler we propose to solve it. A. Problem Formulation We assume an HPC facility, such as the ALCF, in which a cluster is shared by many projects, with users submitting jobs to a common batch scheduler. Our system model comprises three key components: the cluster that runs jobs, the projects to which resources are allocated, and the users who submit jobs under each project. The cluster has N nodes, each characterized by its CPU cores, memory, and network bandwidth. We denote by C(t) the node-time it can deliver during the time interval [0, t]. For this paper, we consider homogeneous CPU nodes. Each project pj ∈ P has an allocation budget Bj , the node-hours it may consume over an allocation period, and a set of users Uj who submit jobs against it, where uij denotes user i of project pj . A person who works on several projects is modeled as a separate user for each project. Users may submit jobs online, often in bursts. For example, a user running a hyperparameter sweep may submit hundreds of jobs within minutes, whereas another user on a different project submits a single large simulation. Let Sij (t) denote the cumulative service, in the same units as the budgets, that user uij has received P up to time t, so that project pj has receivedPSj (t) = i Sij (t) and the cluster has delivered S(t) = j Sj (t). Two constraints hold at all times: a project cannot exceed its budget, Sj (t) ≤ Bj , and the cluster cannot deliver more than its capacity, S(t) ≤ C(t). Each job submitted by a user is represented as a tuple Jk = (ak , τk , nk , p(Jk ), u(Jk )), where ak is its arrival time, τk its requested walltime, nk the number of nodes it requests, and p(Jk ) and u(Jk ) identify the project and the user that submitted it. Its service demand qk = nk τk is the node-time that the job may consume. Jobs are rigid and non-preemptible: a job starts only when all of its requested nodes are free, and holds them until it completes. If job Jk starts at time sk and runs for rk , it completes at ek = sk + rk after waiting ωk = sk − ak in the queue. The runtime rk is unknown when the job arrives and is typically well below τk . Each submitted

B. Queue-Wait Prediction and Wait-Time Bounds Users have long wanted to know how long their jobs will wait in the queue. Early work predicted queue times using various methods, including statistical bounds on observed waits [12]. More recently, supervised models have been trained on job data from ALCF [13], and runtime predictors aim to make backfilling reservations more precise [23], although better predictions do not always produce better schedules [24]. In all of these works, however, the prediction is never fed back into the scheduler. HyDRA, in contrast, predicts a deadline for each incoming job and then schedules the job to meet it. Conservative backfilling also gives each job a start-time bound [3], but it computes that bound from an arrival-ordered queue, so a job that arrives behind a burst inherits the burst’s delay regardless of which user submitted it. HyDRA’s deadline likewise accounts for the current cluster capacity and the job’s position in the queue, but it also weighs the user’s priority and the job’s size, so the bound reflects the intended fairness between users rather than arrival order alone. C. Deadlines, Slowdown, and Starvation Classical deadline scheduling takes deadlines as provided by the user. EDF is optimal on a single preemptive processor [14], and Gonthier et al. [15] avoid reserving or preempting resources by interleaving critical and non-critical tasks. In

3

Project Users

A deadline handler monitors the head of the deadline queue and moves each job that becomes deadline-critical, i.e., Dk − t ≤ δ for a slack δ ≥ 0, into an FCFS critical queue. The job selector then pushes jobs into an FCFS dispatch queue: it first drains every job in the critical queue and, only when that queue is empty, takes the job at the head of the priority queue. Draining the critical queue first ensures that jobs close to their deadlines are considered before higher-ranked jobs that can still wait. The decision logic and priorities used are discussed in § IV. Since every job is held in both the priority and the deadline queues, a job dispatched from one queue leaves a stale copy in the other. HyDRA records each dispatched job in an in-memory map; when the job selector later encounters a job already in the map, it discards that copy, removes the job from the map, and does not dispatch it again. Stale copies in the priority queue are also removed lazily during its periodic score updates. A backfiller starts the job at the head of the dispatch queue if the resource manager reports enough free nodes. Otherwise, it backfills a later job that fits into the free nodes, provided this preserves the deadlines of waiting jobs and keeps the project within budget and the user’s service deficit within a set tolerance. Each placed job is recorded in the scheduler plan and appended to an FCFS executor queue, which launches it on the HPC cluster. When a job starts or finishes, the resource manager updates the free nodes and charges the job’s service to its user and project in the project budgets table, updating Sij (t), Sj (t), and the deficits used for subsequent deadlines.

Job Requests Scheduler Plan

Update πk(t), remove duplicates

Job Buffer

Dispatch Queue

Job Selector

Priority Queue πk(t)

Initializer

Budget Manager

Batch poll

Reject if over budget

Project Budgets

Backfiller Batch push

Resource check Executor Queue

Deadline Handler Deadline Queue Dk

Update budget usage

Critical Queue

HPC CLUSTER Resource Manager

Job start / finish

Fig. 3: HyDRA scheduler architecture.

job is assigned a deadline Dk = ak + Ωk when it arrives, i.e., the latest time by which the job should start, where Ωk bounds its waiting time. Unlike a deadline supplied by the user, Ωk is computed by the scheduler using Eqn. 3. A job meets its deadline if sk ≤ Dk , or equivalently wk ≤ Ωk . We consider three levels of hierarchy. The facility assigns each project pj a weight wj that reflects its relative priority, and the project assigns each of its users uij a weight wij that reflects the user’s priority within the project. These weights determine the share of the cluster that each project and user is entitled to (Level-2). If a project does not assign weights to its users, all of its users have the same entitlement (Level-1). A job Jk may also carry its own weight wk , e.g., from the queue to which it is submitted (Level-3). A job thus inherits the priority of its project at Level-1, the combined priority of its project and user at Level-2, and the combined priority of its project, its user, and itself at Level-3. We normalize these weights to a fixed range, which we discuss in detail in § IV-A. Problem. For a stream of rigid jobs submitted online by the users of multiple projects, schedule them on the cluster such that: (i) no project exceeds its allocation budget, (ii) each job starts no later than its deadline Dk , (iii) the service delivered to each project and user tracks its entitlement, and (iv) the cluster utilization remains high.

IV. FAIRNESS -AWARE H IERARCHICAL S CHEDULING In this section, we describe the mechanisms and scheduling logic of HyDRA. A. Hierarchical Entitlements and Priorities Entitlement refers to the share of the cluster each project and each user should receive over time. The entitlement of a project is itsP weight divided by the total weight of all projects, ŵj = wj / j ′ wj ′ . For example, a project with weight 2, when the weights of all projects add up to 10, should receive 20% of the cluster. Each project then shares its entitlement among its own users. At Level-2 and Level-3, each user receives a part of the project’s entitlement in proportion to its weight. At Level-1, where the project does not assign weights to its ŵj ), where users, all of its users receive equal shares (Eij = |Uj | |Uj | is the number of users in project pj . However, Eij = wij ŵj P , at Level-2 and Level-3. Job weights, which are ′ i′ wi j used only at Level-3, do not change these entitlements; they only affect the priority of the job to which they belong. Next, the priority ρk of a job is obtained by multiplying the weights that apply at the chosen level. At Level-1, a job simply inherits the weight of its project, i.e., ρk = wj . At Level-2, ρk = wj wij , and at Level-3, ρk = wj wij wk . In this way, a job submitted by a high-priority user in a high-priority project receives a high priority, and vice versa. The value of this product depends on which level is active and on the

B. Architecture Fig. 3 shows the architecture of the HyDRA scheduler. Users of each project submit job requests to the scheduler, which places them in a job buffer in FCFS order. An initializer thread takes one job Jk at a time from this buffer, computes its service demand qk , its priority ρk , and its initial priority score πk (ak ), and assigns its deadline Dk . The job is then passed to the budget manager, which looks up the remaining budget Bj −Sj (t) of its project in the project budgets table and rejects the job request if its service demand qk exceeds this amount. On a successful check, the budget manager inserts the job simultaneously into two queues: a priority queue ordered by the dynamic priority score πk (t), and a deadline queue ordered by the deadline Dk . Since πk (t) grows as a job waits, the scores in the priority queue are updated periodically.

4

Algorithm 1 HyDRA scheduling at a decision point t

weight ranges the computing facility supports. For example, with weights between 1 and 5, the product range is[1, 5] at Level-1, but [1, 25] at Level-2. To maintain consistency across all the levels and across different facilities, HyDRA converts each priority to a fixed range of values [1, 5] before using it to compute a deadline. ρk − ρmin , (1) ρ̃k = 1 + 4 ρmax − ρmin

1: for each job Jk in the job buffer do ▶ initializer 2: qk ← nk τk ; compute ρk and Dk (Eqns. 1, 3) 3: if qk > Bj − Sj (t) then ▶ budget manager 4: reject Jk 5: else 6: insert Jk into Qπ by πk (t) and into QD by Dk 7: end if 8: end for 9: recompute πk (t) for all jobs in Qπ ; drop stale copies 10: while the head Jh of QD has Dh − t ≤ δ do ▶ deadline handler 11: move Jh to the critical queue QC 12: end while 13: B ← all jobs in QC , or the head of Qπ if QC = ∅ ▶ job selector 14: for each Jk ∈ B do 15: if Jk ∈ M then 16: remove Jk from M ▶ stale copy 17: else 18: add Jk to M and append it to the dispatch queue QS 19: end if 20: end for 21: Jh ← head of QS ▶ backfiller 22: if nh ≤ Nfree (t) then 23: S TART(Jh ) 24: else 25: Rh ← earliest time at which nh nodes are free 26: for each later job Jc ∈ QS with nc ≤ Nfree (t) do ′ ≤ D , J is budget-feasible, and F (t) ≥ −ζ then 27: if Rh c ij h ′ : start of J if J runs 28: S TART(Jc ) ▶ Rh c h 29: end if 30: end for 31: end if 32: procedure S TART(Jk ) 33: record Jk in the scheduler plan and append it to the executor queue 34: update Nfree (t), Sij (t), Sj (t), and the deficits 35: end procedure

where ρmin and ρmax are the lowest and highest priorities that the chosen weights allow, and ρ̃k = 3 when all weights are equal. We avoid using ranges in [0,1], as smaller ranges in the denominator tend to significantly inflate the deadline. B. Dynamic Priority Score The priority queue orders waiting jobs by a dynamic priority score that combines a job’s priority, its age in the queue, and its size: 1 + Ak (t) , Ak (t) = t − ak , (2) πk (t) = ρ˜k qkγ where Ak (t) is the time the job has waited so far. ρk places jobs in the queue according to their priority. The numerator grows the longer a job waits, so every waiting job slowly moves up the queue. The constant 1 in the numerator gives a newly arrived job a non-zero score. This dynamic priority score captures three behaviors. First, jobs of higher-priority projects and users rank higher. Second, jobs that have waited longer gradually rise in the queue, which prevents starvation. Third, smaller jobs rank higher since they are easier to place, with γ = 0 ignoring job size and γ = 1 fully normalizing by service demand. Since πk (t) grows linearly with t, two waiting jobs exchange rank at most once, and we characterize when this happens in § IV-E. Aging alone, however, cannot bound how long a job waits. This is the role of the deadline, which we describe next.

the cluster can deliver within a window of backlog length T (§ III-A). It ranges from 0 for an empty queue to nearly 1 for a long one. For HyDRA, we design three deadline variants, one for each level of the hierarchy, which differ only in the priority ρ̃k used in Eqn. 3. At Level-1, ρ̃k = ρk = wj , since project weights between 1 and 5 already lie in the target range. At Level-2 and Level-3, ρ̃k is obtained by converting ρk = wj wij and ρk = wj wij wk , respectively, to [1, 5] with Eqn. 1.

C. Adaptive Deadlines HyDRA assigns a deadline to each job during the initialization stage. The estimated deadline should reflect three factors: the size of the job, its importance, and the cluster’s current workload. We denote the waiting-time bound of job Jk as: Ωk = κ

qkγ · [1 + L(ak )], ρ̃k

Dk = ak + Ωk .

D. Admission, Selection, and Fairness-Safe Backfilling Algorithm 1 summarizes how HyDRA combines these mechanisms at each scheduling decision point t. On arrival, the budget manager admits a job Jk of project pj only if it is budget-feasible, i.e., qk ≤ Bj − Sj (t), and otherwise rejects it early. Admitted jobs enter both the priority queue Qπ , ordered by Eqn. 2, and the deadline queue QD , ordered by Eqn. 3. The deadline handler moves every deadline-critical job into the critical queue QC , and the job selector dispatches all of them before the head of Qπ , using the map M to discard the stale copy of a job already dispatched from the other queue. The backfiller starts the head Jh of the dispatch queue QS if nh nodes are free. Otherwise, it computes the reservation Rh , the earliest time at which nh nodes become free based on the walltimes of running jobs, and scans the later jobs in QS . A candidate Jc of user uij that fits in the free nodes starts only

(3)

The first component is the base bound. It grows with the service demand qk of the job, since a large job needs many nodes at once and is harder to place, and it shrinks with the importance of the job, ρ̃k . The constant κ > 0 scales all bounds to the cluster, and γ is the same size exponent as in Eqn. 2. The second component adapts the bound to the cluster state upon job arrival. A bound computed from the job alone would promise the same wait during a burst as on an idle cluster, and would be missed if the queue
is long. The backlog factor L(t) = Q(t)/ Q(t) + C(T ) measures how much work is waiting, i.e., the total service demand Q(t) of queued jobs, relative to the node-time C(T ) = N T that

5

if two conditions hold: (i) Jh can still start by its deadline, i.e., its estimated start Rh′ if Jc runs satisfies Rh′ ≤ Dh ; and (ii) Jc is budget-feasible. Condition (i) distinguishes HyDRA from EASY backfilling [6], which forbids any delay to the reserved job: HyDRA lets a backfilled job delay the head job as long as the head job still meets its deadline, which raises utilization without breaking the waiting-time bound. Conditions (ii) prevent backfilling from exhausting a project’s budget.

NVIDIA DGX Spark node (20-core ARM CPU, 128 GB of memory) of a university HPC cluster. B. Baselines We compare HyDRA against six baselines: three conventional scheduling policies, two SOTA fair schedulers that we adapt to rigid HPC jobs, and the production policies of Argonne National Laboratory (ANL). PCS and ANL run in a standalone multi-queue simulator, which we implement on top of HyDRA. All other baselines run within our architecture (Section III-B), with the deadline queue disabled and the dynamic priority score πk (t) replaced by the ordering key of the baseline. Shortest Job First (SJF) orders jobs by their requested walltime τk . Because short jobs are expected to release their resources quickly, SJF tends to reduce average wait time. However, it can starve long-running jobs, and it ignores job width and project membership entirely. Priority orders jobs by the priority wj of their project, so it honors the relative importance of projects but not how much service they have already received. Weighted Fair Queueing (WFQ) [31] orders jobs by a virtual finish tag computed from their service demand and the weight of their project, so that each project is served in proportion to its weight. Themis [32] introduced finish-time fairness for GPU clusters. Our Themis-inspired variant keeps its core idea and prioritizes the jobs of the project with the largest service deficit over a rolling 300 s window, but omits the leases and auctions of the original. PCS [33] balances performance, fairness, and predictability by sorting jobs into size classes, which we implement as four queues split by requested walltime: A: ≤ 300 s; B: (> 300, ≤ 1, 800 s); C: (> 1, 800 s, ≤ 7, 200 s); D: > 7, 200 s. Jobs are served FIFO within a queue, and queue i receives a share of the resources weighted by e−ωi , so that short jobs are preferred without starving long ones. ANL models the job-sort formula of the PBS scheduler at ALCF [34], [35]. It ranks each waiting job k of project j by

E. Mathematical Analysis Since the priority queue always serves jobs in order of their priority score, the way πk (t) changes over time decides when one waiting job overtakes another. We therefore analyze how the score of a job evolves while it waits in the queue, to show that aging reorders the jobs in priority queue in a predictable way. Substituting the waiting time Ak (t) = t − ak into Eqn. 2 shows that the score of a waiting job is a straight line in time: πk (t) = bk + mk t,

mk =

ρ˜k , qkγ

bk = mk (1 − ak ).

(4) The slope mk sets how fast a job gains priority while it waits. It is larger for jobs with a higher priority ρ˜k , and smaller for larger jobs when γ > 0, so a large job of a low-priority user rises the slowest. The intercept bk also depends on the arrival time, so a job that arrives later starts lower. Two jobs with the same priority and size have parallel lines that never cross, so they are served in the order in which they arrived. Since each score is a line, two waiting jobs Ja and Jb with different slopes swap places at most once, at the time their lines cross: bb − b a t∗ = , ma ̸= mb . (5) ma − mb The swap takes effect only if t∗ falls after both jobs have arrived and before either of them starts. After that, the job with the larger slope stays ahead for as long as both jobs wait. This analysis applies only while a job is in the queue, i.e., from ak until it is sent for execution. This analysis helps strengthen the fact that aging in HyDRA never makes the jobs oscillate inside the queue. Every pair of jobs swaps places at most once, and a job with a larger slope mk eventually overtakes any job with a smaller slope that is still waiting.

Sk (t) = 51 + 105

nk ek (t) ek (t)2 πj + , 3 w̃k N 1800

(6)

where ek (t) is the job’s waiting time, w̃k is its requested walltime clamped to [6, 12] hours, πj is the project priority, and nk /N is the fraction of the system the job requests. To ensure a fair comparison, all baselines run the same workloads on the same simulated cluster as HyDRA, use the same reservation-based backfilling, and see only the requested walltimes, never the actual runtimes.

V. E VALUATION A. Implementation and Setup

C. Workloads

We implement HyDRA in C++20. Its components, from the job buffer to the executor queue, run as they would in a deployment, while the cluster and its resource manager are simulated: the executor holds nk nodes of the simulated cluster for the trace runtime rk of each job. The baselines share this code and replace only the ordering of the priority queue, except PCS and ANL, which run in a standalone multiqueue simulator written in C++17. Each run executes on one

For our experiments, we generate workloads by sampling projects, users, and jobs from the production traces of the 2025 job trace of ALCF Polaris [36]. The characteristics are summarized in Table II. The trace is used without postprocessing, as each of its fields maps directly onto the job model of Section III-A. Moreover, we observed that the runtime for a job exceeded their walltimes in 19% of the cases, with a

6

TABLE II: Production traces used for synthetic workload generation. Source trace

Polaris (ALCF)

Year, duration Nodes × cores Projects, users Jobs Active users per projecta Peak active projects / usersb

2025, 365 d 560 × 64 304, 953 208,405 1.17 / 1 / 55 51 / 100

∗ and Sij (t) = Eij S(t), respectively. The service lag is the gap between this entitled service and the service actually received:

∆j (t) = Sj∗ (t) − Sj (t),

∗ ∆ij (t) = Sij (t) − Sij (t). (7)

A positive lag means that the project or user has received less than its entitlement and is under-served, while a negative lag means that it is over-served. The user lag is measured end to end, i.e., against the user’s share of the whole cluster rather than of its project, so it captures unfairness at both levels of the hierarchy. To summarize fairness across all projects in a single number, we use Jain’s fairness index [21] over the ratios xj = Sj (t)/Sj∗ (t) of received to entitled service: JFI =
2 P j xj P , where |P | is the number of projects. The index |P | j x2j equals 1 when every project receives exactly its entitlement, and it decreases as service becomes more uneven. We compute the same index end to end over the users of all projects, using ∗ the ratios xij = Sij (t)/Sij (t) and the total number of users in place of |P |. Both indices include only the projects and users with a positive entitlement. Further, we evaluate how close the estimated waiting-time bounds are. The on-time rate is the fraction of jobs that start by their deadline, i.e., with sk ≤ Dk . A high on-time rate alone, however, can be achieved with very loose deadlines that tell users little. We therefore also report the deadline deviation sk − Dk = ωk − Ωk , the difference between the actual and the promised wait. A negative deviation is slack that the job did not need, while a positive deviation means that HyDRA overpromised, so an accurate estimate keeps the deviation close to zero and rarely positive. Since the baselines do not assign deadlines, we evaluate them against the deadlines that HyDRA assigns to the same jobs at Level-1. To compare waits across jobs of different sizes, we report the bounded slowdown [37] of each job, i.e., its waiting time ωk relative to its runtime rk : BSDk = 1 + max(rωkk,τmin ) , where the threshold τmin = 10 s keeps very short jobs from inflating the metric. A job that starts immediately has BSDk = 1, and a job that waits as long as it runs has BSDk = 2. To check that HyDRA does not shorten the waits of high-priority jobs at the expense of low-priority ones, we report the median and 95th percentile of BSDk separately for each project-priority and user-priority tier. Finally, we report the average and 95th-percentile queue wait ωk , and the cluster utilization S(emax )/C(emax ), i.e., the fraction of the node-time that the cluster could deliver until the last job completes at emax = maxk ek that is used by running jobs. These show what HyDRA’s fairness and deadlines cost in performance.

a Mean / median / maximum over active projects. b In any 2 h window.

p99 overshoot of 0.1%, so we let the jobs continue to execute even if the runtime exceeds their walltime. For our experiments, we generate candidate windows of durations of 2, 6 and 12 hours with each window starting 1 hour apart. For each window, we calculate the load as number of active users for that window. Based on the quantile value (l) of the load distribution in that window, we categorize the windows as unconditioned (l=0), busy (l=0.9), bursty (l=0.95) and highly bursty (l=0.99). Based on the kind of workload required for each window, we then start by randomly picking one eligible window of the required category. The number of active project in that window is extracted, along with its associated users and jobs. If the number of projects are fewer than what’s specified in the workload, we append projects from other eligible windows of the same category. If a chosen window holds more projects than requested, we sample the required number of projects from it without replacement and discard the rest. The arrival time of jobs in those windows are taken relative to the start of the window. Project, user and job priorities are drawn uniformly from {1, . . . , 5}, where 5 is the highest priority. Maximum possible deliverable service in a window is the total capacity N × the budget window T = 300s = C(T ). If there is a job with qk > C(T ), it would get rejected by the budget manager. For our experiments, we create 3 workloads for each duration: Small, Medium and Large with 50, 100 and 1000 projects respectively. Overall, our workload spans 197 − 12, 356 jobs with 54 − 4, 365 users. Unless stated otherwise, all HyDRA variants use the same hyperparameters on every workload. We set κ = 5, γ = 0.75, with waiting times in seconds, after sweeping each parameter on its own while keeping the others at their defaults, over κ ∈ {1, 5, 10, 100}, γ ∈ {0.5, 0.75, 1}. The backlog factor uses a window of T = 30 s, a job becomes deadlinecritical when it is within δ = 300 s of its deadline, the deficits use ϵ = 10−12 . D. Metrics

E. Results

We evaluate HyDRA on three aspects: fairness, deadline, and system performance metrics. Fairness is measured by comparing the service received against entitlement. If the service S(t) delivered up to time t were divided exactly according to entitlement (Section IV-A), project pj and user uij would have received Sj∗ (t) = ŵj S(t)

1) Comparison with Baselines: We compare HyDRA with the baselines on the Polaris workloads of the unconditioned load, for the three periods (2, 6, and 12 h) and three workload sizes. We run HyDRA at Level-1 in this comparison. Fig. 4 shows the on-time rate, the project-level Jain’s index, the 95th-percentile project service lag, and the 95th-percentile

7

Jain fairness (project)

On-time rate (%)

100 80 60 40 20 0

A F y Q S is L DR SJ riorit WF PC hem AN Hy T P

Worst value Scheduler

A F y Q S is L DR SJ riorit WF PC hem AN Hy T P

(a) On-time rate

400 300 200 100

(c) Project service lag (p95)

1k 100 10 1

A F y Q S is L DR SJ riorit WF PC hem AN T P

Hy

(d) Bounded slowdown (p95). Log scale.

Fig. 4: Comparison across the Large workloads.

Jain fairness (project)

HyDRA SJF 2h (front: solid)

Priority WFQ 6h (front: dashed)

PCS Themis 12h (front: dotted)

ANL on front

0.3 0.2 0.1 0.0

DNF: ANL 12h

80

82

Jain’s index

Lag p95 (node-h)

BSD p95

Utilization (%)

100 All

0.97 Themis

8.38 Priority

2.23 Priority

4.5–42.7 All

hours. To put them in perspective, the index equals k/n when only k of n projects share the service evenly and the rest receive none, so HyDRA serves nearly 25% projects evenly, whereas the baselines serve only 6–12%. Interestingly, Themis and WFQ are no fairer than SJF, even though they explicitly balance service between projects. Balancing tags or deficits does not by itself start the jobs of an under-served project when they need more nodes than are free, whereas HyDRA’s deadlines cap how long any job can be passed over. Waiting-time guarantees. HyDRA maintains a high on-time completion rate, a median of 47% against at most 36% for the baselines (Fig. 4a), and its tail slowdown is 4.2× lower than that of the next best baseline (Fig. 4d). This advantage shrinks when the overload lasts 12 h, since the backlog term can at most double a bound and most queued jobs then become deadline-critical. Service lag. The 95th-%ile project lag in Fig. 4c shows how far the hardest-hit projects fall behind their entitlement. HyDRA keeps it at a median of 74 node-hours, 34% below WFQ (111), the closest baseline, and about half that of SJF and ANL (143 and 142). Themis, Priority, and PCS leave the worst-off projects 211–235 node-hours behind, about three times as far as HyDRA. WFQ also has the highest variation, so how well it protects lagging projects depends strongly on the workload. Fairness versus utilization. HyDRA’s fairness comes at a moderate cost in utilization. Fig. 5 plots the cluster utilization against the project-level Jain’s index for the Large workloads. As we observe, HyDRA has the lowest utilization for every period. This is expected, since HyDRA schedules jobs by their deadlines and their projects’ entitlements rather than by how easily they fit. A wide job close to its deadline, for example, holds nodes idle until enough of them are free, whereas PCS prefers short jobs that keep filling the cluster. Nevertheless, HyDRA lies on the Pareto front for every period, at its highfairness end, and the baselines with the highest utilization are 11×, 1.5×, and 1.3× less fair at 2, 6, and 12 h, respectively. Overall, HyDRA achieves the best balance between fairness and waiting-time guarantees under heavy load. 2) Performance of HyDRA in presence of bursts: Next, to understand the effect of the backlog term, we compare the performance across all the levels of hierarchy. Since the main focus of the experiment is to observe the reaction to a sudden change in workload activity, we evaluate them for a mixed workload. Here, the load distribution is shuffled randomly every 30 minutes between normal (l=0), busy (l=0.9), bursty (l=0.95) and highly bursty (l=0.99) for a 2 hour experiment.

10k

0

A F y Q S is L DR SJ riorit WF PC hem AN Hy T P

0.4

On-time (%)

(b) Project Jain’s index

p95 bounded slowdown

Project service lag, p95 (node-h)

TABLE III: Worst value of each metric over all schedulers and over the 2, 6, and 12 h Small and Medium workloads, and the scheduler with that value.

1.00 0.80 0.60 0.40 0.20 0.00

84

86

88

90

Cluster utilisation (%)

92

94

Fig. 5: Cluster utilization against project-level Jain’s index on the Large workloads. Marker shape shows the duratin of experiment, and the step lines connect the Pareto front of each period, whose members are outlined.

bounded slowdown of each scheduler. Each bar represents the median across the three periods, and the whiskers indicate the minimum and maximum. Every scheduler is compared against the deadlines that HyDRA assigns to the same jobs. ANL did not finish the 12 h Large workload within 12 hours, so we mark it as DNF and do not include it in the bars. Light load. The Small and Medium workloads keep the utilization below 43%, so jobs rarely wait. Even in the worst case, every scheduler starts all jobs on time with a Jain’s index of at least 0.97 (Table III). Without contention, the ordering policy hardly matters, so we focus on the Large workloads for the rest of this section. Fairness. Under heavy load, HyDRA is clearly the fairest scheduler (Fig. 4b). Its median project-level Jain’s index is 0.24, twice that of SJF (0.12), the strongest baseline, and upto 4× compared to others. The absolute values are low for all schedulers because 1, 000 projects share 560 nodes over a few

8

10 1 0 -1 -10 -280

Load

400 100

without backlog (IQR) with backlog (IQR)

Deadline slack (min)

without backlog (median) with backlog (median)

Deadline slack (min)

Deadline slack (min)

261

10 1 0 -1 -10 -209

l = 0.99

l=0

0.5

l = 0.95

1.0

Load

l = 0.9

1.5

2.0

477 100 10 1 0 -1 -10 -176

l = 0.99

l=0

0.5

l = 0.95

1.0

Load

l = 0.9

1.5

l = 0.99

2.0

l=0

0.5

l = 0.95

1.0

l = 0.9

1.5

Arrival time (hours)

Arrival time (hours)

Arrival time (hours)

(a) Level-1

(b) Level-2

(c) Level-3

2.0

Fig. 6: HyDRA adapts better to bursty workload when adapting to the cluster current available capacity. Plots show the median and inter-quartile range (IQR) of Hydra variants.

Fig. 6 shows how HyDRA reacts to this workload. The very first window is highly bursty, so the queue fills up quickly. Without the backlog term, HyDRA struggles from the start: its deadlines depend only on the job itself, so it keeps promising the same waits even as the queue grows. With the backlog term, the deadlines grow with
the queued demand Q(t), since L(t) = Q(t)/ Q(t) + C(T ) rises almost linearly with Q(t) while the queue is small compared with the node-time C(T ) that the cluster can deliver. This keeps the promised waits realistic for a long time. Once the queue becomes much larger than the capacity, i.e., Q(t) ≫ C(T ), L(t) approaches 1 and the deadlines stop growing with the queued demand. Because the backlog term keeps deadlines achievable for longer, jobs also maintain a positive slack, i.e., time left before their deadlines, which raises the on-time rate (Fig. 7b). It improves fairness as well. While the slack is positive, few jobs are deadline-critical, so most jobs are dispatched from the priority queue, which ranks them by their priority, waiting time, and size. Once the slack becomes negative, more and more jobs become deadline-critical and are dispatched from the deadline queue instead, which serves them only in the order of their deadlines. Hence, the longer a scheduler stays in the positive-slack region, the fairer it is. 3) Performance of HyDRA across hierarchy levels: HyDRA supports hierarchical priorities across three entities: projects, users, and jobs. The priority ρk of a job, and hence its deadline Dk , combines the weights that apply at each of the three levels (Section IV-A). In this experiment, we study how the distribution of these priorities affects the performance of HyDRA. During workload generation, the project, user, and job priorities wj , wij , and wk are each sampled uniformly from {1, . . . , 5}. Their products, however, are not uniform: the hierarchical priorities wj , wj wij , and wj wij wk increasingly skew towards low values from Level-1 to Level-3. On Polaris, jobs are submitted to dedicated queues according to their role (e.g., debug or backfill) or their size (e.g., small or large). Since a job’s queue already reflects its role and size, it translates directly into a job priority. We therefore also generate another workload by sampling the job

0.4

debug

without backlog with backlog project user

preemptable

Jain fairness index

small debug-scaling backfill-small medium demand run_next large

Level 1 Level 2 Level 3

0.3

M5902799 0

4

8

12 ×10⁴ jobs

(a) Polaris queue distribution

0.2

20

30

40

50

On-time jobs (%)

60

70

(b) Effect of the backlog term

Fig. 7: (a) Share of jobs in the ten most used Polaris queues, from which the queue-based job priorities wk are sampled (Table IV). (b) Jain’s index and on-time rate of HyDRA at each hierarchy level, with and without the backlog term, on the mixed workload. TABLE IV: Job priority assigned to each of the five most frequent Polaris queues. Shares are each queue’s fraction of the jobs in these five queues available in the traces. Priority

Queue

Share

5 4 3 2

debug debug-scaling small preemptable

59.74% 7.59% 13.23% 16.01%

1

backfill-small

3.43%

Basis Short jobs, dedicated nodes Above regular production Normal production queue Documented as below demand and can be terminated Documented as low priority

priority wk from the distribution of jobs across these queues, instead of uniformly. Based on Fig. 7a, we map each queue to a priority in {1, . . . , 5}, as listed in Table IV. We compare the deadlines of four variants: Level-1, Level2, Level-3, and Level-3 with queue-based job priorities. With the default sampling, wj , wij , and wk are drawn independently and uniformly from {1, . . . , 5}, so each has an expected value of 3. By independence, the expected priority is therefore E[wj ] = 3 at Level-1, E[wj wij ] = E[wj ] E[wij ] = 9 at Level-2, and E[wj wij wk ] = E[wj ] E[wij ] E[wk ] = 27 at Level-3. Now, the expectation for capped priority ρ˜k for each

9

-10 -100

3

6

9

Arrival time (hours)

0 -1 -10

3

6

9

Arrival time (hours)

Jain fairness index

0.155 0.150 0.145

project user

0.140

10

8

10

12

On-time jobs (%)

14

0.40 0.30 0.20 0.10 0.00

A F y Q S is L DR SJ riorit WF PC hem AN T P

Hy

(a) On-time rate

(b) Project Jain’s index

80 60 40 20 0 A F y Q S is L DR SJ riorit WF PC hem AN y H T P

(c) Project service lag (p95)

0.135 0.130

20

12

(b) Level 3 (Uniform and Queue sampling)

Level 1 Level 2 Level 3 Level 3 + job queue priority

30

0 A F y Q S is L DR SJ riorit WF PC hem AN y H T P

-100 -1897 0

12

(a) All levels (1, 2, 3)

1

50-50 25-75

40

Jain fairness (project)

-1

On-time rate (%)

0

-2023 0

Level 3 Level 3 + job queue priority

10

Project service lag, p95 (node-h)

1

p95 bounded slowdown

54

Level 1 Level 2 Level 3

Deadline slack (min)

Deadline slack (min)

18

100

10

A F y Q S is L DR SJ riorit WF PC hem AN T P

Hy

(d) Bounded slowdown (p95). Log scale.

Fig. 9: Comparison on varying demand conditions, 2 hour, Large workload, 25% high, 75% low using dots and 50-50 using hatch.

(c) Level 3 (Uniform and Queue sampling)

Fig. 8: Deadline slack vs. arrival for all hierarchical variants on Polaris (12 hr) level is:

job arrivals and priorities stay the same, but each job is made either high-demand, using 16 nodes for a walltime of 3,600 s, or low-demand, using 1 node for 900 s, and its runtime is set to 90% of its walltime. We generate two such workloads, in which 50% (50-50) and 25% (25-75) of the jobs are highdemand, and compare the schedulers on both in Fig. 9.

Level 1 (ρmin = 1, ρmax = 5), ρ̃k = wj , so E[ρ̃k ] = E[wj ] = 3 Level 2 (ρmin = 1, ρmax = 25), E[wj wij ] − 1 9−1 7 =1+4· = ≈ 2.33 24 24 3 Level 3 (ρmin = 1, ρmax = 125),

With more high-demand jobs, the 50-50 workload loads the cluster more heavily, so every scheduler waits longer: compared to 25-75, the project lag grows by 1.6–2.0× and the tail slowdown by up to 2.2× (Figs. 9c and 9d). HyDRA E[wj wij wk ] − 1 27 − 1 57 E[ρ̃k ] = 1 + 4 =1+4· = ≈ 1.84 is the fairest scheduler on 25-75, with a project-level Jain’s 124 124 31 index of 0.45 against 0.34 for WFQ and 0.33 for Themis, but As a result, E[ρ̃k ] decreases as the hierarchy level increases. WFQ (0.40) and Themis (0.36) overtake it (0.31) on 50-50 Since the waiting-time bound Ωk is inversely proportional (Fig. 9b). Since runtimes here are a fixed 90% of walltimes, to ρ̃k , the deadlines grow with the level: Fig. 8a shows the tags that WFQ computes from requested walltimes match that Level-3 deadlines exceed those of Level-2, which in the service that jobs actually receive, so WFQ comes close to turn exceed those of Level-1, for most of the run. Queuethe weighted fair share against which the index is measured. based job priorities have the opposite effect. Under the default On the Polaris traces, where walltimes greatly overestimate Level-3, wk is uniform, whereas with job-queue priorities its runtimes, WFQ is far less fair (Fig. 4b). WFQ also keeps the distribution is heavily skewed toward high weights (Fig. 7a). lowest project lag on both workloads. Since ρk = wj wij wk with independent factors, a larger E[wk ] HyDRA and SJF start the most jobs by their deadlines raises E[ρk ] and, because the conversion to [1, 5] is linear, also E[ρ̃k ]. Jobs under Level-3 with job-queue priorities therefore on both workloads, 42% and 44% on 25-75 and 23% and 29% on 50-50, whereas WFQ and Themis start at most 13% receive tighter deadlines on average (Fig. 8b). 4) Performance of HyDRA against varying demand condi- (Fig. 9a). HyDRA’s tail slowdown is also within 8% of the tions: Besides how many jobs arrive, contention also depends best scheduler, while that of WFQ is 2.5–2.9× higher and on how much each job demands, since a few high demand that of ANL 4.4–4.6× higher. Overall, as high-demand jobs jobs can hold back many small ones. To study this effect grow from 25% to 50% of the workload, HyDRA is the only without changing the activity or burstiness of the workload, scheduler that offers the best balance between fairness and we condition the demand of the 2 h Large workload (l=0). Its deadlines. E[ρ̃k ] = 1 + 4

10

VI. C ONCLUSION In this paper, we presented HyDRA, a hierarchical scheduler that shares an HPC cluster fairly among projects, users, and jobs while bounding the queue wait of every job. HyDRA assigns each job a deadline on arrival from its size, its priority, and the current backlog and ranks waiting jobs by a score that grows with their waiting time. On workloads sampled from ALCF Polaris traces, HyDRA achieves 2× fairness scores and lowers the 95th-%ile bounded slowdown by 4.2× relative to the next best baseline, at a moderate cost in utilization. As future work, we will adapt the deadlines to sustained overload and integrate HyDRA into a production resource manager such as Slurm.

[12] Daniel Nurmi, John Brevik, and Rich Wolski. QBETS: Queue Bounds Estimation from Time Series. In Job Scheduling Strategies for Parallel Processing (JSSPP 2007), volume 4942 of Lecture Notes in Computer Science, pages 76–101. Springer Berlin Heidelberg, 2008. DOI: 10.1007/978-3-540-78699-3_5. [13] Nwamaka Okafor, Bethany Lusch, and Venkatram Vishwanath. Queue wait time prediction in high performance computing (HPC) systems. The Journal of Supercomputing, 82(2), 2026. DOI: 10.1007/s11227025-08221-7. [14] C. L. Liu and James W. Layland. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. Journal of the ACM, 20(1):46–61, 1973. DOI: 10.1145/321738.321743. [15] Maxime Gonthier, Kyle Chard, Ian Foster, Loris Marchal, and Frédéric Vivien. Deadline-aware scheduling of mixed-criticality tasks. In Proceedings of the 54th International Conference on Parallel Processing (ICPP ’25), pages 178–187. ACM, 2025. DOI: 10.1145/3754598.3754639. [16] William Allcock, Paul Rich, Yuping Fan, and Zhiling Lan. Experience and Practice of Batch Scheduling on Leadership Supercomputers at Argonne. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, pages 1–24. Springer International Publishing, 2018. DOI: 10.1007/978-3-319-77398-8_1. [17] Kohei Yoshida, Ryuichi Sakamoto, Kento Sato, Abhinav Bhatele, Hayato Yamaki, Hiroki Honda, and Shinobu Miwa. VAHRM: Variation-Aware Resource Management in Heterogeneous Supercomputing Systems. IEEE Transactions on Parallel and Distributed Systems, 36(8):1713– 1727, 2025. DOI: 10.1109/tpds.2025.3577252. [18] Anne Benoit, Joachim Cendrier, and Frédéric Vivien. Scheduling Jobs Under a Variable Number of Processors. IEEE Transactions on Parallel and Distributed Systems, 37(2):427–442, 2026. DOI: 10.1109/tpds.2025.3638703. [19] Dalibor Klusáček and Václav Chlumský. Fair-sharing simulator: Toward fair scheduling in batch computing systems. The International Journal of High Performance Computing Applications, 40(2):254–270, 2025. DOI: 10.1177/10943420251385673. [20] G. Sabin, G. Kochhar, and P. Sadayappan. Job fairness in nonpreemptive job scheduling. In Proceedings of the 2004 International Conference on Parallel Processing (ICPP ’04), pages 186–194. IEEE, 2004. DOI: 10.1109/icpp.2004.1327920. [21] Rajendra K. Jain, Dah-Ming W. Chiu, and William R. Hawe. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Technical Report DEC-TR-301, Eastern Research Laboratory, Digital Equipment Corporation, Hudson, MA, 1984. [22] Alexander V. Goponenko, Kenneth Lamar, Christina Peterson, Benjamin A. Allan, Jim M. Brandt, and Damian Dechev. Metrics for Packing Efficiency and Fairness of HPC Cluster Batch Job Scheduling. In 2022 IEEE 34th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), pages 241–252. IEEE, 2022. DOI: 10.1109/sbac-pad55451.2022.00035. [23] Eric Gaussier, David Glesser, Valentin Reis, and Denis Trystram. Improving backfilling by using machine learning to predict running times. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’15), pages 1–10. ACM, 2015. DOI: 10.1145/2807591.2807646. [24] Vinish Kumar. Trace-driven HPC scheduling with runtime prediction: A reproducible study of backfilling, uncertainty, and fairness constraints, 2026. DOI: 10.21203/rs.3.rs-9372280/v1. [25] Wei Gao, Zhisheng Ye, Peng Sun, Yonggang Wen, and Tianwei Zhang. Chronus: A Novel Deadline-aware Scheduler for Deep Learning Training Jobs. In Proceedings of the ACM Symposium on Cloud Computing (SoCC ’21), pages 609–623. ACM, 2021. DOI: 10.1145/3472883.3486978. [26] Yupeng Xi and Chao Jing. DeepPlus: An adaptive deadline and fairness aware scheduler for accelerating mixed deep learning training and inference workloads in GPU cluster. Computer Networks, 275:111883, 2026. DOI: 10.1016/j.comnet.2025.111883. [27] Michael A. Bender, Soumen Chakrabarti, and S. Muthukrishnan. Flow and Stretch Metrics for Scheduling Continuous Job Streams. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’98), pages 270–279. Society for Industrial and Applied Mathematics, 1998.

ACKNOWLEDGMENTS The authors would like to thank members of the Globus Labs at the University of Chicago, including Akshat Singhania, Augustus Ellerm and Haochen Pan for their assistance with this paper. They would also like to thank Parmanand Sinha, and the University of Chicago Research Computing Center (RCC), for their assistance and feedback. We also acknowledge the Argonne Leadership Computing Facility (ALCF) for access to the Polaris traces used in our evaluation. R EFERENCES [1] K.-I. Goh and A.-L. Barabási. Burstiness and memory in complex systems. Europhysics Letters, 81(4):48002, jan 2008. DOI: 10.1209/02955075/81/48002. [2] Yuping Fan, Zhiling Lan, Paul Rich, William Allcock, and Michael E. Papka. Hybrid workload scheduling on hpc systems. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 470–480, 2022. DOI: 10.1109/IPDPS53621.2022.00052. [3] Ahuva W. Mu’alem and Dror G. Feitelson. Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling. IEEE Transactions on Parallel and Distributed Systems, 12(6):529–543, 2001. DOI: 10.1109/71.932708. [4] Dan Tsafrir, Yoav Etsion, and Dror G. Feitelson. Backfilling Using System-Generated Predictions Rather than User Runtime Estimates. IEEE Transactions on Parallel and Distributed Systems, 18(6):789–803, 2007. DOI: 10.1109/tpds.2007.70606. [5] Rosen Center for Advanced Computing, Purdue University. About Slurm fairshare on RCAC clusters. https://docs.rcac.purdue.edu/blog/2025/08/ 08/job-priority-and-scheduling/, August 2025. [6] David A. Lifka. The ANL/IBM SP scheduling system. In Job Scheduling Strategies for Parallel Processing (JSSPP), volume 949 of Lecture Notes in Computer Science, pages 295–303. Springer, 1995. DOI: 10.1007/3540-60153-8_35. [7] Srividya Srinivasan, Rajkumar Kettimuthu, Vijay Subramani, and Ponnuswamy Sadayappan. Selective Reservation Strategies for Backfill Job Scheduling. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, pages 55–71. Springer Berlin Heidelberg, 2002. DOI: 10.1007/3-540-36180-4_4. [8] Lingfei Wang, Maria A. Rodriguez, and Nir Lipovetzky. Optimizing HPC scheduling: a hierarchical reinforcement learning approach for intelligent job selection and allocation. The Journal of Supercomputing, 81(8), 2025. DOI: 10.1007/s11227-025-07396-3. [9] J.C.R. Bennett and Hui Zhang. WF2 Q: Worst-case Fair Weighted Fair Queueing. In Proceedings of IEEE INFOCOM ’96, pages 120–128. IEEE, 1996. DOI: 10.1109/infcom.1996.497885. [10] Jon C. R. Bennett and Hui Zhang. Hierarchical packet fair queueing algorithms. In Proceedings of ACM SIGCOMM ’96, pages 143–156. ACM, 1996. DOI: 10.1145/248156.248170. [11] Dāvis Kažemaks, Laurens Versluis, Burcu Kulahcioglu Ozkan, and Jérémie Decouchant. Balancing fairness and performance in multiuser Spark workloads with dynamic scheduling. In Proceedings of the ACM Symposium on Cloud Computing (SoCC), 2025. DOI: 10.1145/3772052.3772214.

11

[28] Louis-Claude Canon, Anthony Dugois, and Loris Marchal. Bounding the Flow Time in Online Scheduling with Structured Processing Sets. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 683–693. IEEE, 2022. DOI: 10.1109/ipdps53621.2022.00072. [29] Dror G. Feitelson. Metrics for Parallel Job Scheduling and Their Convergence. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, pages 188–205. Springer Berlin Heidelberg, 2001. DOI: 10.1007/3-540-45540-x_11. [30] Francesco De Pellegrini, Vaibhav Kumar Gupta, Rachid El Azouzi, Serigne Gueye, Cedric Richier, and Jeremie Leguay. Fair Coflow Scheduling via Controlled Slowdown. IEEE Transactions on Parallel and Distributed Systems, 35(12):2347–2360, 2024. DOI: 10.1109/tpds.2024.3446188. [31] A.K. Parekh and R.G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: the singlenode case. IEEE/ACM Transactions on Networking, 1(3):344–357, 1993. DOI: 10.1109/90.234856. [32] Kshiteej Mahajan, Arjun Balasubramanian, Arjun Singhvi, Shivaram Venkataraman, Aditya Akella, Amar Phanishayee, and Shuchi Chawla. Themis: Fair and efficient GPU cluster scheduling. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI

20), pages 289–304, Santa Clara, CA, 2020. USENIX Association. [33] Abdullah Bin Faisal, Noah Martin, Hafiz Mohsin Bashir, Swaminathan Lamelas, and Fahad R. Dogar. When will my ML job finish? toward providing completion time estimates through Predictability-Centric scheduling. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pages 487–505, Santa Clara, CA, 2024. USENIX Association. [34] OpenPBS Community. Job_sort_formula Examples. https://community. openpbs.org/t/job-sort-formula-examples/3588, June 2023. Online discussion, accessed Oct. 8, 2026. [35] Argonne Leadership Computing Facility. pbsq: Pbs qstat filter. https: //github.com/argonne-lcf/pbs_utils/blob/main/pbsq, 2026. GitHub repository. [36] Argonne Leadership Computing Facility. ALCF data dictionary: DIM_JOB_COMPOSITE. https://reports.alcf.anl.gov/data/ datadictionary/datadictionary_dim_job_composite.html, 2025. [37] Dror G. Feitelson, Larry Rudolph, Uwe Schwiegelshohn, Kenneth C. Sevcik, and Parkson Wong. Theory and practice in parallel job scheduling. In Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, pages 1–34. Springer Berlin Heidelberg, 1997. DOI: 10.1007/3-540-63574-2_14.

12

Related documents

• Bounding Queue Waits for Fair Scheduling of Bursty HPC Workloads via Hierarchical Algorithms#1447394
• SafePar: Monitoring Asynchrony in Microservices#1117793
• SafePar: Monitoring Asynchrony in Microservices#1108661
• LaissezCloud: Continuous Resource Renegotiation for the Public Cloud#134521
• Live Architecture Models for Cloud-Native Architecture-as-Code: Early Results from Kubernetes Conformance Checking#1130990