Sia: Heterogeneity-aware, goodput-optimized ML-cluster scheduling — Detailed Summary

Suhas Jayaram Subramanya, Daiyaan Arfeen, Shouxu Lin, Aurick Qiao, Zhihao Jia, Gregory R. Ganger | Carnegie Mellon University / Cornell University / Petuum Inc. | SOSP '23, Koblenz, Germany, October 23–26, 2023 | DOI: 10.1145/3600006.3613175

Per-section summary organized by the paper's own headings. Each section gives paragraph-level bullet points and preserves the paper's exact quantitative results, equations, and named methods.

"In Egyptian mythology, Sia is the god of perception/intelligence, not to be confused with the popular music artist."

Abstract

• Sia is a scheduler that assigns heterogeneous DL cluster resources to elastic, resource-adaptive jobs.
• Prior schedulers address one axis or the other (heterogeneity or resource-adaptivity) but none address both, and most scale poorly to large clusters and/or heavy workloads even without the combined complexity.
• Two claimed technical contributions: (a) a new scheduling formulation that scales to the enlarged search space while intentionally matching jobs and their configurations to GPU types and counts, adapting to cluster load and job mix over time; (b) a low-profiling-overhead bootstrapping method for the per-job throughput models used to score candidate assignments.
• Sia is stated to be the first cluster scheduler to support elastic scaling of hybrid parallel jobs.
• Headline numbers as stated in the abstract, on 44- to 64-GPU clusters with a mix of three GPU types, for workloads derived from three real-world environments:

• Additional claims: scales to at least 2000-GPU clusters, improves fairness, and is not over-sensitive to scheduler parameter settings.
• CCS concepts: scheduling algorithms; cloud computing. Keywords: cluster scheduling, resource allocation, deep learning training.

1. Introduction

Setting.

• Sizable DL clusters shared by multiple users training different models are now data-center staples; a scheduler assigns cluster resources to submitted jobs.
• Increasingly these clusters contain a mix of GPU types, due to incremental deployment over time and advances in GPU design.
• The paper uses "GPU" as shorthand for any DL accelerator — traditional GPUs, TPUs, FPGAs, and other ML accelerators.

Partitioning of prior work (the gap).

• Heterogeneity-aware schedulers (e.g., Gavel, AlloX, Gandiva) explicitly consider GPU-type differences, but only accommodate what the paper terms rigid jobs: jobs that must run with a user-specified number of GPUs, do not allow elastic scaling, and do not adapt to the resources they are given.
• Adaptivity-aware schedulers (e.g., Pollux, Optimus, Singularity) explicitly model how non-rigid jobs adapt (e.g., batchsize adjustment) and perform at different GPU counts, but assume all GPUs are of one type.

Figure 1 — the motivating three-scenario comparison.

• Left: adaptive (non-rigid) jobs on a homogeneous cluster — Pollux and Sia both beat Gavel on average JCT.
• Right: rigid jobs on a 3-GPU-type heterogeneous cluster — Gavel and Sia both beat Pollux.
• Center: non-rigid jobs and heterogeneous resources — Sia beats both state-of-the-art schedulers; the paper reports 40–70% lower average JCTs in this middle trio of bars.
• The gaps widen for more intense workloads (Figures 7 and 9), because the baselines scale poorly with contention (Gavel) and with cluster size (Pollux).

Conceptual statement of Sia.

• In each scheduling round, Sia considers every possible assignment of GPUs (number and type) to current jobs, estimates their aggregate goodput (including job resizing costs), and selects the best cluster-wide assignment for the next period.
• Goodput is defined (borrowing Pollux's definition) as a DL efficiency metric that combines sample-processing throughput and statistical efficiency to reflect the rate of training progress.

Two fundamental challenges.

1. Search-space size. Huge for a sizable cluster, and much worse when multiple GPU types exist and each job can use any number of GPUs of any type.
2. Per-job heterogeneity in scaling behavior. Different DL jobs experience different performance changes across GPU types, across GPU counts, and in the interaction of the two (different GPU types have distinct compute-to-network-bandwidth ratios) — yet profiling every job on every possible allocation is prohibitively expensive.

Sia's two answers.

• A new ILP formulation plus pragmatic search-space reductions, letting Sia efficiently find GPU types, GPU counts, and batchsizes for all pending jobs as load and cluster size grow.
• A new online-learning approach to throughput modeling: bootstrap each new job's model from profiles of just one minimum-sized configuration per GPU type, initially assume simple scaling/projection across unknown configurations, and dynamically refine as different configurations get used.
• The minimum size is 1 GPU for traditional data-parallel jobs; for model-parallel forms (which the paper calls "hybrid parallel"), the submitter-specified GPU count is the minimum.

Evaluation preview.

• Workloads derived from three real cluster environments; comparisons against Pollux, Gavel, and Shockwave plus others.
• Sia is implemented as a plugin-compatible scheduler replacement in the open-source AdaptDL framework, enabling head-to-head comparison with the public Pollux implementation.
• On a 44-GPU, 3-GPU-type physical cluster: Sia gives 35% and 50% lower average JCT than Pollux and Gavel, respectively. These runs also re-validate the Pollux simulator, which is then used for broader exploration (larger clusters, more intense workloads).
• Advantages grow with cluster load/contention: up to 95% lower avgJCT vs. Gavel and up to 47% lower avgJCT vs. Shockwave, both of which treat all jobs as rigid.

Summary of results claimed in the Introduction.

• (Note: the paper reports slightly different ranges for GPU hours in the abstract (12–55%) versus the Introduction and Section 5.2 (12–60%); both are reproduced here as stated.)
• Additional results confirm Sia's (1) ability to improve cluster efficiency even when many jobs disallow batchsize/GPU-count changes, (2) ability to schedule and elastically scale Megatron-style pipeline-model-parallel jobs (scaling out via data parallelism), (3) scheduler-runtime scalability to clusters of up to 2000 GPUs, (4) robustness to scheduler-parameter defaults, and (5) minor penalty for initially-crude bootstrapped throughput models.

Five stated contributions.

1. Exposes a gap in state-of-the-art schedulers that leaves a large untapped opportunity.
2. Introduces Sia, with an ILP formulation addressing the compounded complexity of heterogeneous GPU types and job adaptivity.
3. Shows per-job per-GPU-type throughput models can be bootstrapped from just a few mini-batches and then refined as the job runs in Sia-optimized configurations.
4. Presents the first cluster scheduler able to elastically scale hybrid parallel jobs.
5. Shows Sia matches state-of-the-art schedulers in their target domains and significantly outperforms them in the union of those domains.

2. DL cluster scheduling and related work

DL training jobs as a scheduling workload.

• A DL training job trains a DNN iteratively over epochs; per minibatch, an optimizer updates parameters by minimizing a loss.
• Because minibatch size is usually fixed for extended periods, most DL jobs take a consistent and predictable amount of time per minibatch.
• Jobs are generally pre-emptible — the model and optimizer state can be checkpointed after any minibatch and resumed without losing much progress.
• They are amenable to scaling, since gradient computation parallelizes across GPUs within a node and across nodes.

Data parallelism.

• Most training jobs use synchronous data parallelism (DP): each GPU holds a model replica and computes gradients on a partition of the minibatch (the local batch size); gradients are reduced (e.g., by collective all-reduce) and the optimizer (SGD, Adam) applies the update on each GPU.
• Scaling quality depends on job characteristics (compute intensity, parameter count), the GPUs, and the inter-GPU network: per minibatch, the gradient compute phase is divided across GPUs while the reduce phase synchronizes them.
• Prior work has shown job scalability can be modeled effectively with relatively few measurements.

Model parallelism and hybrid parallelism.

• Some jobs use pipeline model parallelism (PMP) or tensor model parallelism (TMP) when the model does not fit in one GPU's memory.
• Powerful optimizers exist for modeling configuration performance and partitioning a model across GPUs.
• Megatron-LM mixes PMP and TMP at moderate scale and then uses synchronous data parallelism to scale out to hundreds of nodes.

Elastic and resource-adaptive DL jobs.

• Data-parallel jobs can be elastically resized by checkpointing and restarting on a different GPU count with a different sample division.
• Aspects of how the job works can also be adapted — e.g., increasing minibatch size when using more GPUs, to increase per-GPU compute per minibatch and thereby increase scalability.
• Different minibatch sizes have different statistical efficiency impacts, which depend on job characteristics but can be measured and modeled.
• Non-data-parallel jobs are usually submitted with a predetermined configuration; changing it usually requires re-running the hybrid-parallel optimizer. They can still be scaled data-parallel-style by replicating the original configuration — e.g., a PMP job needing 4 GPUs can use 8 GPUs with a doubled minibatch, one 4-GPU instance each.

Resource heterogeneity.

• GPU types differ in memory size and in compute and communication performance.
• Multi-type clusters arise because clusters are grown over time and the most cost-effective hardware is bought at each purchase.
• Looking ahead, rapid development of new DL accelerators — including some targeting specific DL models — will make multiple "GPU types" a design feature rather than a deployment consequence.
• A DL job may perform differently on different GPU types and scale differently on them (e.g., because the compute-to-network ratio changes).

Figure 2. Goodput scaling vs. GPU count for different (GPU type, job) combinations, with goodput shown relative to single-T4 goodput; different DL jobs experience different speedups and different scalability.

DL cluster schedulers in practice.

• Many schedulers only accommodate fixed-GPU-count requests, ignoring elasticity, resource-adaptivity, and heterogeneity opportunities; others address some. Sia seeks to address them all.

2.1 Related work in DL cluster scheduling

Claim. To the authors' knowledge, no prior scheduler optimizes assignments for resource-adaptive jobs on a heterogeneous DL cluster. Prior work is grouped by unaddressed aspect.

(a) Heterogeneous clusters, no resource-adaptive jobs.

• Schedulers designed for in-cluster heterogeneity do not adaptively tune the number of GPUs assigned nor account for other job adaptations; the user specifies a GPU count per job.
• Gavel is the best-performing state-of-the-art heterogeneous DL cluster scheduler, using a fast linear-program formulation that scales to large cluster sizes.
• Gavel limitations: it does not support job adaptivity, and only optimizes the assigned GPU type given the submitter-specified minibatch size and GPU count. This can under-utilize newer, more powerful GPUs because batch sizes are too small. Under congestion, Gavel time-shares resources between jobs, wasting GPU time on checkpoint-restore operations.
• Extending Gavel to handle adaptivity is non-trivial: Gavel expresses options via a throughput matrix over (job_id, GPU_type) pairs. Expanding it to (job_id, GPU_type, num_GPUs, minibatch_size) causes two problems — (1) populating a non-trivial portion of the matrix requires extensive per-job profiling, and (2) the resulting optimization program becomes too large to solve quickly.

(b) Elastic/resource-adaptive jobs, no heterogeneity.

• Such schedulers assume all GPUs are identical.
• Pollux is the state-of-the-art here. It uses per-job goodput models to assign both a GPU count and a batchsize to each job, re-considering all assignments every scheduling cycle based on updated job behavior and the job queue, thereby avoiding unused or over-committed GPUs.
• Each Pollux goodput model has two components: a statistical efficiency model (training progress per sample, based on Gradient Noise Scale) as a function of batchsize, and a throughput model (samples/sec) as a function of GPU count and batchsize. Scaling behavior is learned by scaling the job up, measuring each count tried, and interpolating for others.
• Pollux uses a genetic algorithm to search the space of allocations (and corresponding batchsizes) for all current jobs to maximize aggregate cluster-wide goodput weighted by fairness.
• Pollux limitations: its no-pre-profiling throughput-modeling approach blocks consideration of GPU heterogeneity; and its genetic formulation scales very poorly with cluster size even for homogeneous clusters with hundreds of GPUs.
• Root cause of the scaling problem: for each (job, GPU_count) pair, Pollux considers every possible placement across all nodes, so the number of solutions is exponential in the number of nodes and number of GPUs per node. For 1000+ GPU clusters it is too slow to respond to cluster changes — the genetic algorithm takes tens of minutes to terminate (Figure 9).

(c) Rigid jobs on homogeneous clusters.

• Most existing DL schedulers require the submitter to specify GPU count and job configuration. They do not adjust GPU count based on current load or job scalability/efficiency, and assume all GPUs are identical — so they use resources less efficiently than the two prior categories.
• Shockwave is a recent example improving performance and fairness relative to prior schedulers in this category; it is included in the evaluation.
• Batch schedulers like Kubeflow and Volcano can adjust GPU count to improve utilization, but do not co-adapt batch size, GPU count, and GPU type simultaneously.

(d) Parallelism optimizers that are not cluster schedulers.

• Various optimizers select an individual job's configuration before acquiring cloud resources or submitting to a scheduler; especially important for hybrid parallelism.
• They are not cluster schedulers: they consider an individual job in isolation, without cluster load or the trade-off of giving a resource to one job rather than another.
• To the authors' knowledge, no existing scheduler co-optimizes non-data-parallel job configurations and cluster resource assignments, even for homogeneous clusters.

3. Sia Design and Implementation

Sia is a pre-emptive, round-based scheduler that optimizes allocations for a set of jobs to maximize cluster-wide goodput. Each round, jobs receive bundles of resources (CPU, GPU, network — like VMs in the cloud), and Sia uses checkpoint-restore preemption to realize job adaptivity.

3.1 Sia components and job life cycle

Figure 3 job lifecycle (steps 1–8).

• (1) A user submits job J, declaring the maximum batchsize (max_bsz) and maximum GPU count (max_ngpus).
• (2) Sia profiles J's throughput on a few batchsizes using one GPU of each type.
• (3) The Goodput Estimator bootstraps a throughput model for J on each GPU type from those profiles.
• (4) J waits in the Queue until Sia allocates GPUs.
• (5) Policy finds an optimal partitioning of cluster resources among all jobs, giving J, say, 2 GPUs of type GREEN.
• (6) Placer determines which 2 physical GPUs to assign, given the current assignment, attempting to reduce unnecessary migrations caused by de-fragmentation.
• (7) Adaptive Executors run the job and report gradient/throughput statistics; Goodput Estimator updates the goodput model for J on GREEN.
• (8) Policy queries updated goodput estimates for J on all GPU types, closing the loop (5 → 6 → 7 → 8 → …) so J's goodput is continuously optimized until termination.

Goodput Estimator composition. Sia's own throughput model plus a statistical efficiency model borrowed from Pollux.

Adaptive Executors support three things:

1. Transparent checkpoint-restore for low-overhead preemption and resource scaling.
2. Batchsize adaptivity to maximize statistical efficiency.
3. Frequent reporting of gradient and throughput statistics for the current allocation (default = 30 seconds).

Heterogeneous execution. GPU memory capacity, interconnect speeds, and throughput are modeled in the Goodput Estimator. Gradient accumulation is used when statistical efficiency dictates a higher batchsize than GPU memory supports, so goodput is optimized over a larger range of per-GPU batchsizes for larger-memory GPUs.

Job scaling policy. Simple scale-up rule: start each job with exactly 1 GPU, and scale it up by at most 2× per scheduling round. If a job requires min_ngpus to start, Sia respects that minimum and ignores smaller allocations. Jobs may be scaled down to min_ngpus to fit more jobs, as determined by the scheduling objective.

Decoupled allocation and placement. Sia splits the problem into:

• (a) an Allocation stage (step 5) deciding the number and type of resources per job, and
• (b) a Placement stage (step 6) deciding the exact physical resources (and network topology) satisfying those allocations.
• This decoupling restricts the placement space, since many placements exist for a given allocation.

Placer's three rules.

• (a) Partial-node allocations (fewer GPUs than max GPUs per node) must not be split across two nodes.
• (b) Whole-node allocations must take whole nodes.
• (c) If no placement satisfies (a) and (b) — resource fragmentation — evict some jobs and retry.
• Fragmentation-driven evictions are quite rare and often result in fewer than 3 evictions at once.

3.2 Bootstrapping of throughput models

• A naive throughput model (as a function of GPU count and batchsize) for every GPU type would require profiling many multi-GPU allocations per GPU type to collect compute and communication times; that overhead grows linearly in both the number of GPU types and the number of nodes of each type.
• Sia instead starts with minimal profiling and refines based on observed allocations: one throughput model per GPU type, plus one statistical efficiency model per job.

Initial profiling.

• Running example: job J on a cluster with GPU types A and B, needing min_GPU_count = 1 GPU per data-parallel worker.
• Sia profiles J on one GPU of each type, starting from a minimum batchsize and profiling increasingly larger batchsizes until GPU memory limits are hit — typically 10 profiled batchsizes per GPU type.
• Average per-job profiling cost: < 20 GPU seconds per GPU type.
• This yields (1) compute times for combinations of GPU type and batchsize, and (2) comparison of compute times across GPU types.
• Crucially, compute time is independent of GPU-count increases (since scaling is data-parallel with all-reduce), so only communication time remains to be predicted.

Refinement sequence.

• Models are initialized from the 1-GPU profiles and used to place J on 1 GPU of, say, type A.
• While running on a single A GPU, online profiling (a) learns J's statistical efficiency model as a function of batch size, and (b) refines the 1-GPU-A throughput model.
• These models still cannot estimate communication time, so Sia makes a one-time simplifying assumption to estimate 2-GPU-A throughput: throughput of two data-parallel replicas is twice that of a single replica (perfect scaling, zero communication time).
• Once J actually runs on 2 GPUs of A, online profiling refines the model using measured communication times on a multi-GPU allocation; the refined model then accurately covers both compute and communication for A.

Cross-GPU-type bootstrapping (Equation 1).

• Since J has not yet run multi-GPU on B, its B model lacks communication time. Sia combines the learned A multi-GPU model with the initially profiled single-GPU throughputs for both A and B:

                     xput_B(1)
est-xput_B(N)  =  ------------- * xput_A(N)                        (1)
                     xput_A(1)

• Here xput_B(1)/xput_A(1) is the ratio of 1-GPU throughputs and xput_A(N) is throughput on N GPUs of type A.
• Interpretation: if the communication time for B is unknown, assume the scaling of the compute:communication ratio for B is the same as for A (which is known).
• Section 5.7 shows bootstrapped models are accurate enough to guide Sia toward useful explorative steps.
• est-xput_B is used to estimate goodput for multi-GPU B allocations; once J actually runs multi-GPU on B, the bootstrapped model is discarded, because online profiling can now refine xput_B to predict B's communication time directly.

3.3 Configurations

• A configuration is a bundle of resources (CPU, GPU, network), analogous to a cloud VM size, represented as a 3-tuple (n, r, t): n nodes containing a total of r resources of type t. Example: (2, 16, T4).
• Sia's Policy optimizes over a small valid set of configurations designed to simplify Placer logic, decomposed into a single-node set (n = 1) and a multi-node set (n > 1).

Construction. For a cluster with N physical nodes and R GPUs of type X per node:

C = { (1, 2^0, X), (1, 2^1, X), ..., (1, R, X) }          <- single-node
    U
    { (2, 2R, X), ..., (N, N*R, X), n in N }              <- multi-node

• The single-node set constrains in-node allocations to powers of 2, capped at R. If R is not a power of 2, decompose R into a sum of powers of 2 and model one physical node as multiple virtual nodes with different GPU counts.
• The multi-node set constrains all allocations to use all available GPUs in a node (GPU count is a multiple of R).
• With these sets, the Submesh Shape Covering theorem (from Alpa) guarantees a placement for all valid allocations where no two distributed jobs share any nodes — desirable because it eliminates NIC contention, which can cause significant slowdown to all contending jobs.

Complexity reduction.

• Despite the smaller configuration set, Sia matches Pollux's performance in a homogeneous cluster (Table 4), suggesting the restrictions do not significantly impact job runtimes.
• This complexity reduction is what allows Sia's optimization to scale to clusters with thousands of GPUs at practical runtimes (Section 5.6).

3.4 Scheduler objective

Running example. A heterogeneous cluster with (a) one node of 2 GPUs of type A and (b) one node of 4 GPUs of type B. Jobs J = {J1, J2}, each requiring a minimum of 1 GPU.

Valid configurations. C = {(1,1,A), (1,2,A), (1,1,B), (1,2,B), (1,4,B)}. Assigning c = (n, m, X) means the job runs with m GPUs of type X split across n nodes. A job receives either no resources in a round, or exactly one valid configuration.

Goodput estimation.

• One throughput model per (job, GPU_type) combination; combined with the per-job statistical efficiency model to yield one goodput estimator per (job, GPU_type). In the example, (f_A, f_B) for J1 and (g_A, g_B) for J2.
• A goodput matrix G of size |J| × |C|, where G_ij is estimated goodput for job J_i in configuration c_j.
• Within a row, values are comparable: G_ij > G_ik means c_j is better than c_k for J_i. Across rows they are not: G_mj > G_nj does not imply J_m deserves c_j over J_n. Row-normalization fixes this.

Normalized goodput matrix. For each job J_i with minimum required GPU count N_i^min:

G_ij  <-  N_i^min * ( G_ij / min_j G_ij )

• Two benefits of normalizing by the row minimum: (1) G can be read as a utility matrix, with G_ij the utility of configuration C_j to job J_i; (2) utilities become comparable across jobs for a given configuration.
• Consequently, the highest value along a job's row makes the most progress for that job, and a configuration is best used by the job with the highest value along that configuration's column.
• Each new job adds a row and each completion deletes one, keeping G current. If statistical efficiency changes or a throughput model is refined, G is updated.

Table 1 — normalized goodput matrix G for the running example (boxed entries = the allocation maximizing the goodput sum):

• The optimum assigns J1 → (1,4,B) and J2 → (1,2,A).

ILP formulation (Equation 2). Binary matrix A of the same shape as G, with A_ij = 1 if configuration c_j is chosen for job J_i:

max_A  sum_{i=1..|J|} sum_{j=1..|C|}  A_ij * G_ij  +  lambda * (1 - ||A_i||_1)   (2)

• Two terms: the sum of normalized goodputs of jobs in chosen configurations, and a scheduler penalty — no penalty if some configuration is chosen (||A_i||_1 = 1), and a constant penalty -lambda otherwise.
• lambda can be read as an incentive to reduce scheduler queue occupancy: if lambda is large, Sia will allocate at least one GPU to each job in the cluster, if available.

Constraints.

1. Each job chooses at most one configuration: ||A_i||_1 <= 1.
2. Allocated GPUs must not exceed available GPUs for each GPU type.

• Solving gives a binary solution matrix A: J_i gets nothing if ||A_i||_1 = 0, otherwise it runs under c_j for the next round.

Restart Factor (Equation 3).

• Frequent restarts harm performance, so a re-allocation factor r_i adjusts utilities in G for configurations differing from the job's current one. This multiplicative factor models expected goodput by projecting the historical restart rate into the future.
• It is necessary because DL restart cost can be high — 25–250 seconds for the models in Table 2.
• For a job J_i with age T_i, wasting S_i GPU-seconds per restart and having restarted N_i times:

r_i = ( T_i - N_i * S_i ) / ( T_i + S_i )                          (3)

• If J_i currently runs under c_k, then for all c_j != c_k requiring a restart: G_ij <- r_i * G_ij.
• Without it, every tiny change in G would trigger reallocations and extra checkpoint-restore overhead. By discounting only restart-requiring entries, Sia restarts a job only if not doing so causes a big reduction in the optimal objective value.

Balancing goodput with fairness (Equation 4).

• A single knob p manipulates the scale-free matrix G by raising elements to the power p. If p < 0, the objective's sign is flipped (minimize instead of maximize) to preserve semantics.
• Section 5.7 shows p provides robust fairness with minimal negative impact on efficiency metrics across settings between -1.0 and 1.0; the default is p = -0.5.
• Full objective for p > 0:

max_A  sum_{i} sum_{j}  A_ij * ( r_i * G_ij )^p  +  lambda * (1 - ||A_i||_1)    (4)

Support for limited adaptivity.

• Sia supports jobs with some adaptations disabled (batch size, GPU count, and/or type).
• Motivation: large batch sizes give high throughput and GPU utilization but may cause a generalization gap — the trained model performs poorly on unseen samples.
• Two restricted job classes:
  • Strong-scaling jobs: fixed batch size, but GPU count and type may be optimized.
  • Rigid jobs: fixed batch size and GPU count; only GPU type is optimized.
• Both preserve model quality and training semantics by keeping batch size fixed, while still allowing limited optimization.
• For strong-scaling jobs, goodput is directly proportional to throughput at fixed batch size, so Sia uses throughput directly in place of goodput in Equation (4).

Rigid-job objective (Equation 5).

max_B  sum_{i=1..|J_R|} sum_{g=1..N_g}  B_ig * ( r_i * T_ig )^p
                                        + lambda * (1 - ||B_ig||_1)             (5)

• J_R = set of rigid jobs, N_g = number of GPU types, T_ig = goodput of job J_i on GPU type g, r_i = the job's restart factor. ILP constraints are then updated to bound total GPUs allocated per GPU type across all active jobs.
• With few changes to Equation (4) and the constraints, Sia's formulation can also support custom resource requests and jobs with user-defined parallelism tuned to a specific GPU count, type, and/or batch size.

Preemption and reservation.

• Sia assumes all jobs are preemptive, but supports a small number of non-preemptive jobs (as long as aggregate demand is satisfiable): for each, a constraint is added to Equation (4) forcing the requested resources to be allocated, guaranteeing non-preemption each round. Reservations are implemented similarly.

Support for other parallelization techniques.

• Sia only requires that a job provide a goodput estimator evaluable on valid configurations — this is what admits more advanced parallelization strategies.
• Sia's throughput models are extended to jobs combining pipeline and data parallelism, allowing scheduling of multi-billion-parameter models.
• Mechanics: a PMP strategy partitions a large model onto P GPUs across all partitions. A job with N data-parallel replicas uses exactly N × P GPUs. Given mini-batch size M and micro-batch size m, each replica computes gradients locally using M / (m·N) micro-batches of size m across P GPUs; the N pipeline replicas then synchronize with a gradient all-reduce to finish one iteration.
• The distinct compute and communication phases of such jobs are what let Sia reuse its throughput models for goodput estimation at various batch sizes.
• Since these jobs scale in units of P GPUs, additional terms and constraints (similar to Equation 5) are added to the objective.
• Existing hybrid-parallel optimizers are time-consuming, so efficient elastic scaling without fixing non-data-parallel degrees is left as future work.

Scheduling other workload types.

• Sia exploits DL-training-specific characteristics, but the authors believe it could handle other batch-processing workloads via a workload-customized goodput estimator.
• Example 1: batch DL inference over a large dataset — use throughput as a proxy for goodput.
• Example 2: latency-sensitive inference — set goodput = 1 if a configuration meets the promised latency constraint, 0 otherwise.

3.5 Implementation

• Implemented on the open-source AdaptDL framework, replacing its scheduler and data-loader implementations. AdaptDL is PyTorch-based and natively supports dynamically adjusting batch size and GPU count for DL training jobs on Kubernetes-managed GPU clusters.
• For data-parallel jobs: AdaptDL data-loaders vary batch size during training; all-reduce synchronizes gradients across workers.
• Sia Adaptive Executor continually profiles minibatch runtimes and gradient statistics, periodically (default 30 s) optimizes goodput model parameters from those profiles, and communicates the new parameters to Sia Policy. It also selects the batch size maximizing goodput for the allocated resources and scales the learning rate accordingly via a configurable rule.
• Learning-rate scaling rules used for Table 2 models: square-root scaling for models using the AdamW optimizer, and AdaScale for models using SGD.
• Sia Policy runs as a Kubernetes service; at the start of each round it uses the latest goodput model parameters to optimize allocation via Equation (4).
• Equation (4) is formulated as a Mixed-Integer Linear Program using the GLPK_MI solver from the CVXPY package; the solution determines allocations.

Preemption with checkpoint-restore.

• On an allocation change, Sia preempts a job only after the current minibatch finishes, so there is no communication in flight.
• It then checkpoints the latest model weights, data-loader state (sampler and iterator states), and optimizer state (e.g., Adam's gradient statistics) to shared persistent storage, and releases all GPUs.
• On the new resources it launches one Adaptive Executor per GPU, restores state from disk, and resumes training.
• The same mechanism provides failure recovery: Sia checkpoints weights and optimizer state after every epoch, so worker failures in the next epoch can be recovered from the last checkpoint on different resources.

4. Experimental Setup

4.1 Workloads and Traces

• Traces are derived from three production DL clusters, following an approach common to Gavel, Pollux, and Shockwave.
• Jobs in a trace are categorized by total GPU time:

• XXL models are used only for the hybrid-parallel experiments in Section 5.3.

Trace sources.

• Philly — from 100k jobs executed over two months in a multi-tenant Microsoft cluster with multiple GPU types.
• Helios — from the Saturn cluster in the Helios traces; the originals contain 3.3M jobs over six months in a heterogeneous cluster with over 6k GPUs. Compared with Philly, Helios jobs request more GPUs and run longer, giving higher cluster load.
• Sampling for Philly and Helios: ten traces per workload, randomly sampling the 8 busiest hours, at an average arrival rate of 20 jobs/hr, giving 160 jobs over the 8-hour window.
• newTrace — a more recent trace from a production system spanning multiple clusters with thousands of GPUs. Like Philly, it allocates VMs to DL jobs, each provisioned a pre-configured amount of CPU, GPU, and memory. It exhibits a wide range of resource requests with diurnal patterns and bursts from job submission scripts (e.g., hyper-parameter tuning).
• newTrace sampling: 10 traces over a 48-hour period at an average arrival rate of 20 jobs/hr, totalling 960 jobs per trace.
• The 48-hour newTrace evaluates a more realistic setting where congestion slowly builds from long-running jobs. Arrival rates vary significantly from 5 to 100 jobs/hr over the 48-hour submission window, giving insight into how schedulers handle congestion and load variance.

Table 2 — models used in the evaluations:

4.2 Hardware measurements and simulator

• Most experiments use the discrete-time simulator open-sourced by the Pollux authors, whose fidelity was verified by prior work and by the Sia authors' own measurements.
• The authors added a Gavel implementation and open-source Shockwave to the simulator, and extended Pollux to support heterogeneous clusters.
• The original Pollux simulator simulates checkpoint-restore with the same constant delay for all jobs; the authors replaced this with model-specific checkpoint-restore delays.

Four GPU node types used:

• The authors had only limited dedicated time on the on-prem nodes, which allowed direct experiments on a 44-GPU, 3-GPU-type cluster; Section 5.1 results confirm both Sia's efficacy and the simulator's fidelity.

4.3 Evaluated settings

Tuning job hyper-parameters (TunedJobs).

• Gavel cannot auto-tune job parameters, so the authors manually tune batch size and requested GPU count for each job to ensure optimal performance, following the Pollux approach.
• Search over (batch size, GPU count) combinations — GPU count ≤ 64 for Homogeneous, ≤ 16 for Physical and Heterogeneous — randomly choosing a combination whose simulated runtime is 50–80% of ideal speedup over the 1-GPU baseline runtime with the optimal batch size.
• These are referred to as TunedJobs (TJ), acknowledging that real-world jobs may be submitted with worse-performing parameters.

Fixing mixed-GPU allocations from Pollux.

• To make Pollux work on heterogeneous clusters, 8-GPU nodes are presented as two virtual 4-GPU nodes to eliminate node-capacity heterogeneity.
• Pollux may still schedule a job across more than one GPU type (disallowed in this setup), so a heuristic is applied: pick the GPU type with the most GPUs; on a tie, pick the more powerful type (a100 > quad > rtx > t4).
• The authors note this is imperfect but enables fair comparison, and that designing the perfect heuristic is not the paper's focus.

Default parameters.

5. Evaluation

The evaluation shows Sia outperforms state-of-the-art schedulers for both resource-adaptive and rigid jobs on both homogeneous and heterogeneous resources, and also provides better finish-time fairness, scales to large clusters, and is not overly sensitive to default parameter settings.

5.1 Physical cluster experiments

• Setting: 44-GPU physical cluster (3 rtx + 1 quad + 2 a100), compared with Pollux and Gavel.
• Trace: a smaller single 3-hour trace with 30 jobs, mixing all Table 2 models. Owing to resource-availability constraints, each scheduler is run four times to account for schedule randomness. (Unlike profiling runs, scheduler experiments require extended isolated control over the whole machine collection, blocking out all other users.)
• Result: on the physical cluster, Sia gave lower average JCT than Gavel by 50% and than Pollux by 35–50%.

Figure 5 — allocation dynamics. Resource allocations for three jobs over 45 minutes illustrate how Sia dynamically adjusts GPU count and type:

• Rising congestion triggers Sia to scale down and then move the ImageNet job to rtx GPUs, leaving the fastest a100 GPUs for incoming CIFAR-10 jobs.
• Over time, Sia scales up and refines throughput models for each job (e.g., the DeepSpeech2 job) while adapting to GPU type and count changes.
• When congestion decreases sufficiently, Sia shifts ImageNet back to a100 and scales out DeepSpeech2 on rtx GPUs for better throughput.

Simulator fidelity.

• The simulator had less than 5% error in average JCT and makespan for both Sia and Gavel, validating its accuracy.
• However, Pollux performed significantly worse on the physical cluster than the simulator predicted, due in part to the simulator modifications giving Pollux an advantage when scheduling a single job over heterogeneous resources (Section 4.3).
• Pollux's schedules can vary greatly due to randomness in its optimization and potentially misguided job adaptivity (noisy throughput estimators), producing bad worst-case scenarios. The heterogeneity of hardware mapped to virtual nodes that Pollux assumes are homogeneous can also contribute to variation.

5.2 Simulator experiments

Table 3 — Sia vs. Pollux vs. Gavel+TunedJobs, Heterogeneous setting. ("Contention" = number of jobs contending for resources in the cluster.)

• Across all traces and metrics, Sia outperforms both the heterogeneity-aware (Gavel) and job-autoscaling (Pollux) schedulers: avgJCT reduced by 30–93%, p99 JCT reduced by 28–95%, and 12–60% fewer GPU hours per job.

Why Gavel+TunedJobs does poorly.

1. Time-sharing overheads reduce the useful GPU time spent on training progress in a given round.
2. Using a batch size that fits the smallest-memory GPU under-utilizes more powerful GPUs.

Why Pollux falls behind Sia.

• Pollux outperforms Gavel because of job adaptivity, but (1) it treats heterogeneous hardware as homogeneous, failing to exploit performance heterogeneity, and (2) it can output placements spanning more than one GPU type; forcing single-type placements idles some GPUs — though this is still better than mixing types and running at the speed of the slowest.
• From Table 3, Pollux restarts jobs twice as often as Sia on moderately congested clusters (Philly and Helios), because it optimizes allocations in steps of 1 GPU, while Sia allocates configurations with steps as large as an entire node.

Congestion in newTrace.

• newTrace contains bursts of up to 100 jobs/hr during the busiest hour.
• Gavel struggles with these bursts, and the problem compounds into a positive feedback loop: rising contention forces Gavel to swap jobs in/out more frequently, wasting significant GPU capacity on checkpoint-restore when GPUs are already scarce. Gavel's average and p99 JCTs degrade far worse than Sia's and Pollux's.
• During peak congestion, both Sia and Pollux scale jobs down to 1 GPU per job, narrowing the gap between them; Sia's heterogeneity-aware scheduling still improves cluster goodput over Pollux by better matching jobs to GPUs.

Matching jobs to GPU types (Figure 6).

• Figure 6 shows min-normalized average GPU hours per model on Helios traces for Sia (S), Pollux (P), and Gavel (G).
• Pollux is heterogeneity-unaware and has no distinct (job, GPU type) preferences; Gavel and Sia are heterogeneity-aware and strongly prefer certain GPU types for particular models.
• Sia allocates BERT models almost exclusively to a100 GPUs, aggressively exploiting goodput heterogeneity across GPU types. Gavel's time-sharing forces BERT jobs to rotate between a100, rtx, and t4 GPUs, resulting in less-efficient execution.
• Sia prefers rtx GPUs for DeepSpeech2, leaving a100 GPUs free for BERT, and significantly reduces GPU hours per job relative to Gavel.
• Caveat reported by the authors: on average, YOLOv3 and DeepSpeech2 consume about 5% more GPU hours under Sia than under heterogeneity-unaware Pollux, because Pollux (out of randomness) gives them more GPU time on faster GPUs.

Workload intensity (Figure 7).

• Average JCT is plotted against average job arrival rate, sampling jobs from Helios traces in the Heterogeneous setting on a fixed 64-GPU cluster.
• Pollux and Sia outperform Gavel at larger arrival rates because they can scale down running jobs rather than having to time-share GPUs.
• Sia consistently outperforms Pollux by 50–65% by aggressively matching jobs to preferred GPU types.
• As arrival rates increase, jobs wait longer for resources, a problem that worsens with congestion. An 8-hour submission window is too short to observe these effects; on the 48-hour newTrace (Table 3), Gavel sees about 7× more contention than Sia (versus < 2× on the 8-hour traces).

5.3 Adapting hybrid parallel jobs

• Simulated training of a 2.8B-parameter GPT model using PMP to scale to a few GPUs and data parallelism with gradient all-reduce to scale across nodes.
• Statistical efficiency profiles are borrowed from BERT (closest match) to simulate fine-tuning the GPT model; compute times for micro-batches and all-reduce times for different placements on a100 and rtx GPUs are profiled to seed the simulator.
• The job is assumed to use the commonly used GPipe schedule internally for PMP, with 2 stages on a100 and 8 stages on rtx (1 per GPU), reflecting the larger a100 memories. Each data-parallel replica runs 48 microbatches of size 1 each.
• Result (left panel): the hybrid-parallel GPT model's throughput scales linearly with GPU count, because computation dominates communication for this model.
• Result (right panel): Sia adapts the model to changing cluster conditions — scaling it down around the 1-hour mark and back up around the 4-hour mark.
• Claim: Sia is the first cluster scheduler to support elastically scaling hybrid-parallel jobs on heterogeneous resources; supporting additional adaptation dimensions for PMP jobs is left to future work.

5.4 Attribution of primary benefits

The authors isolate each key aspect (resource heterogeneity, job adaptability) by evaluating scenarios where only one is present.

(a) Job adaptability, but not resource heterogeneity — Table 4. Philly traces, Homogeneous 64-GPU setting; TunedJobs used for Shockwave, Themis, and Gavel, with hyper-parameters re-tuned to fully exploit the 64-GPU cluster.

• Pollux was designed for this scenario, and Sia matches it on all metrics, even slightly outperforming it because Sia's ILP formulation can guarantee a global optimum while Pollux's genetic algorithm cannot.
• Sia had fewer restarts: 2.6 vs. 5.1 restarts per job, so Sia wasted fewer GPU hours on checkpoint-restore.
• Shockwave is the best inelastic scheduler, because its objective optimizes job progress and finish-time fairness while penalizing schedules with large makespan. Themis (optimizing FTF) and Gavel (optimizing cluster throughput) fall behind Shockwave on all metrics.
• Sia and Pollux both exploit adaptivity and show a 50–70% improvement over the state-of-the-art inelastic baselines on all metrics.

(b) Resource heterogeneity, but not job adaptability.

• Right-most bars of Figure 1: every job is treated as rigid — it must run with the batch size and GPU count specified in the trace. Auto-scaling and co-adaptive batch-size tuning are disabled for Sia and Pollux, evening the playing field with Gavel.
• Even though Gavel was designed for this scenario, Sia outperforms it by about 25%.
• Attribution: Sia explicitly optimizes goodput (a max-sum-goodput policy) while Gavel optimizes cluster throughput (max-sum-throughput). With inelastic jobs, Sia always provides higher per-GPU goodput.
• Pollux also optimizes for a sum of goodput but produces worse JCTs because it is blind to GPU heterogeneity.

5.5 Finish Time Fairness

• Finish-time fairness (FTF), from Themis, captures the fairness of allocations to a job over its cluster lifetime. For a job J seeing average contention N_avg (total jobs requesting resources) and taking T_s to complete, the FTF ratio ρ is T_s / T_f, where T_f is JCT in an isolated, fair-sized cluster containing N_gpus / N_avg GPUs and N_gpus is the cluster size.
• The authors extend FTF to heterogeneous clusters (Equation 6):

rho = sum_G  P(G = g) * rho_g                                       (6)

• rho_g is the FTF ratio for GPU type g; P(G = g) = N_g / N_total is the probability that a random cluster GPU is of type g. rho_g is computed with the homogeneous-cluster definition, restricted to the N_g GPUs of type g.
• With one GPU type, Equation (6) reduces to the homogeneous definition, preserving semantics. For heterogeneous clusters, ρ is the expectation of the FTF ratio over GPU types.
• Interpretation: ρ > 1 means unfair execution (the job would finish faster in isolation than under the scheduler's policy); ρ < 1 means resource sharing improved runtime by using idle GPUs. A vertical CDF with all jobs at ρ ≤ 1 means a perfectly finish-time-fair scheduler.
• Three metrics of interest: (a) worst FTF ratio across all jobs, (b) unfair job fraction (fraction with ρ > 1), and (c) CDF(ρ).

Figure 8 (left) — FTF CDFs, Helios traces, heterogeneous setting.

• Sia is visually more fair than Gavel, Pollux, or Shockwave — its CDF is more vertical and below 1.
• Shockwave does better than Gavel and Pollux because it penalizes jobs with high FTF ratios, trading worst FTF ratio for unfair job fraction relative to the others. Sia achieves by far the lowest unfair job fraction and worst FTF ratio.

Figure 8 (right) — JCT CDFs.

• Gavel and Shockwave prioritize either makespan or long jobs, producing worse outcomes for short jobs during congestion.
• Sia instead adapts between minimizing average JCT and minimizing makespan based on congestion level: scale down long jobs during congestion to prioritize incoming short jobs (which reduces congestion), and scale out long jobs when congestion drops to minimize makespan.

5.6 Policy overhead and scalability

Policy runtime, 64-GPU Heterogeneous setting, Helios traces:

• Sia's overheads are insignificant for 60 s scheduling rounds. Pollux's longer times indicate it may not scale to larger cluster sizes. Gavel is significantly faster because it does not consider job adaptation.

Figure 9 — policy runtime vs. cluster size (Heterogeneous setting, Helios traces, scaled up to 2048 GPUs with proportionally scaled traces; error bars are 25th/75th percentiles):

• Sia scales well, with single-second runtime for policy optimization, enabling management of clusters with thousands of GPUs and many GPU types.
• Pollux's genetic algorithm runs ~100× slower than Sia's ILP formulation and struggles to find optimal solutions for large clusters due to search-space explosion — even without the extra complexity induced by heterogeneity.
• Gavel is much quicker, because it does not consider job adaptation.

5.7 Sia Parameter Sensitivity

Fairness parameter p (Figure 10 left).

• The impact of p on p99 JCT is very evident: Sia allocates more GPUs to jobs that better exploit both scale and newer GPU types (particularly BERT and ImageNet training jobs). Since these jobs also run long, this drastically reduces their JCTs, bringing down p99 JCT at the expense of average JCT.
• This also affects allocation fairness: p = 1.0 has a higher unfair job fraction than p = -0.5.
• The default p = -0.5 is chosen because it performs best among the tested values on average JCT, average makespan, and finish-time-fairness.

Scheduling round duration (Figure 10 right).

• All experiments use a 60 s round.
• Increasing the round from 60 s to 300 s increased Sia's average JCT by 333 s (12%).
• A shorter 30 s round caused a higher rate of re-allocations and worsened average JCT.
• Sia's policy optimization takes less than 1 second even for moderately sized clusters; 60 s performed best. No significant change in p99 JCT or makespan was observed across round durations.

Fraction of jobs supporting adaptivity (Figure 11).

• Sia supports adapting batch size, GPU count, and GPU type. Figure 11 shows average JCT and makespan for Sia on Philly traces, normalized to all AdaptiveJobs (0% constrained), while varying the percentage of jobs restricted along each dimension.
• Strong-scaling jobs fix the user-supplied batch size but allow Sia to optimize GPU number and type. Rigid jobs fix batch size and GPU count but allow Sia to optimize GPU type.
• Conclusions drawn:
  1. Optimizing number of GPUs in addition to GPU type improves average JCT by 56%.
  2. Additionally optimizing batch size (together with GPU count and type) improves average JCT by another 13%.

Profiling overheads.

• Profiling incurs overhead, and profiling every possible configuration is impractical: too little profiling yields sub-optimal schedules; too much wastes cluster resources for marginal efficiency gains.
• Three settings evaluated on Helios traces:

• Sia with Bootstrap performs 30% better than No Prof and only 8% worse than Oracle, demonstrating the effectiveness of the bootstrapping mechanism for heterogeneity-aware job adaptivity with minimal profiling overhead.
• Profiling two GPU counts per GPU type performed worse than Sia's minimized approach.
• Bootstrapping scales well: for a cluster with 20 GPU types, bootstrapping adds < 5% overhead to a job's execution.

6. Conclusion

• Sia efficiently schedules adaptive DL jobs on heterogeneous resources, co-adapting each job's GPU count, GPU type, and batch size, increasing DL cluster performance.
• Numbers as stated in the conclusion: 30–93% reductions in average JCT, 28–95% reductions in p99 JCT and makespan, and 22–31% reductions in the unfair job fraction versus existing schedulers.
• Sia is positioned as a critical component for emerging heterogeneous DL clusters.

7. Acknowledgements

• Thanks to Amar Phanishayee, anonymous SOSP reviewers, and shepherd Douglas Terry; to the members and companies of the PDL Consortium (Amazon, Google, Hitachi, Honda, IBM, Intel, Meta, Microsoft, Oracle, Pure Storage, Salesforce, Samsung, Two Sigma, Western Digital) and VMware.
• Supported in part by NSF Award #2211882 and by the U.S. Army Research Office / U.S. Army Futures Command under Contract No. W911NF-20-D-0002.

Cross-cutting summary of named mechanisms

Limitations and stated future work

• Efficient elastic scaling without fixing non-data-parallel degrees is left as future work — existing hybrid-parallel optimizers are time-consuming, so Sia only scales hybrid-parallel jobs in units of P GPUs by replicating a submitter-fixed PMP/TMP configuration data-parallel-style.
• Supporting additional adaptation dimensions for PMP jobs is explicitly left to future work (Section 5.3).
• Most results come from the Pollux discrete-time simulator (with the authors' Gavel/Shockwave additions and heterogeneity extension), not a physical cluster; the physical experiments cover only a 44-GPU, 3-GPU-type cluster with a single 3-hour, 30-job trace run four times.
• Pollux performed significantly worse on the physical cluster than the simulator predicted, which the authors attribute in part to their own simulator modifications advantaging Pollux for single-job heterogeneous scheduling.
• The heuristic used to force Pollux's mixed-GPU placements onto a single GPU type (a100 > quad > rtx > t4, most-GPUs-wins) is acknowledged as imperfect; the authors state designing the perfect heuristic is not the paper's focus.
• Sia's restricted configuration set permits only power-of-2 within-node and whole-node multi-node allocations; nodes whose GPU count is not a power of 2 must be modeled as multiple virtual nodes.
• The GPU-hours result is not uniformly favorable: YOLOv3 and DeepSpeech2 consume about 5% more GPU hours under Sia than under Pollux on Helios traces.
• Sia exploits DL-training-specific characteristics; support for other workload types (batch inference, latency-sensitive inference) is described only as a belief with sketched goodput estimators, not evaluated.
• The est-xput bootstrap rests on a stated simplifying assumption (perfect 2-GPU scaling with zero communication, and equal compute:communication scaling across GPU types) that is only justified empirically via the Bootstrap-vs-Oracle gap (8%).