Heet: Accelerating Elastic Training in Heterogeneous Deep Learning Clusters

In a shared GPU cluster, "elastic" training jobs add and drop workers on the fly as machines free up or get taken away — but real clusters are a jumble of GPU types and interconnects (slow PCIe T4s, fast NVLink V100s), and how well a job speeds up as you add workers (its "scaling efficiency") depends on both the model and the exact hardware, so choosing how many and which GPUs to give each job needs to know the efficiency of every possible configuration; measuring all of them is combinatorially hopeless, and prior schedulers just assume the hardware is uniform and get it wrong; this paper (University of Macau) builds Heet, which predicts the efficiency of ALL configurations from only a handful of measurements by treating the job-by-hardware-by-workers table like a recommender system (matrix completion), then feeds those predictions into a price-based scheduler that balances running short jobs first against handing workers to jobs that actually scale — cutting job-completion time by 1.3 to 2.46x over state-of-the-art elastic schedulers with negligible overhead.

The argument in one glance

Problem

Elastic jobs must pick GPUs, but the right pick depends on the hardware

A shared GPU cluster runs many training jobs at once, and ELASTIC training lets each job grow and shrink its number of GPU workers on the fly — scaling up when the cluster has spare capacity, scaling down when resources are reclaimed for higher-priority work. Every time a job rescales, the system must choose an elastic configuration: how many workers, and which GPUs. That choice is not obvious, because modern clusters are HETEROGENEOUS — a mix of GPU generations (say T4, A10, V100) and interconnects (PCIe versus the much faster NVLink). How well a job speeds up as you add workers depends on both the model AND the exact hardware, so the best configuration on one kind of GPU is the wrong one on another.
What people did

Schedule with a size heuristic and assume the hardware is uniform

Existing elastic schedulers — AFS, SRSF, Gavel — allocate workers using simple policies: prioritize short or small jobs, or spread resources fairly. Most of them implicitly assume the hardware is homogeneous, treating one GPU as interchangeable with another, and pick worker counts from a size-based rule of thumb. This keeps the scheduler simple and fast.
Why it fell short

Assuming uniform hardware is wrong, and profiling every option is hopeless

Heterogeneity is not a small effect. Raw compute varies by up to 48.5x across GPU generations, NVLink speeds one model (VGG) up by 4x while doing nothing for another (DenseNet), and — counterintuitively — jobs often SCALE BETTER on low-end GPUs, because each GPU does less compute relative to the fixed communication cost, so adding workers helps more. A scheduler blind to this makes bad calls: in the paper's motivating example, heterogeneity-blind policies take 2408 and 2692 minutes to finish a job set that a heterogeneity-aware allocation finishes in 1680 — a 1.43 to 1.6x loss. But the obvious fix, actually MEASURING the throughput of every configuration, is a combinatorial trap: with M worker counts, N host types, and many model types, you need O(M x N x model-types) profiling runs, which is prohibitively expensive in a busy production cluster. So you are stuck between a fast-but-wrong heuristic and an accurate-but-unaffordable measurement.
This paper's idea

Predict every configuration from a few measurements, then price the tradeoff

This paper (University of Macau — Mo, Xu, Xu) presents Heet, which escapes that dilemma. First, it makes heterogeneity-aware scheduling AFFORDABLE by predicting the scaling efficiency of ALL configurations from only a handful of measurements, using 3-D COLLABORATIVE FILTERING: it treats the table of throughput indexed by (job, host type, worker count) like a recommender system, profiles just about six entries per job, reuses the profiles of similar past jobs when it can (91.2% accurate), and completes the rest by matrix factorization (77 to 90% accurate) — because a few latent factors, essentially a job's compute- and communication-intensity, explain the whole table. This cuts profiling from combinatorial to roughly linear. Second, it feeds those predictions into a PRICE-BASED scheduler that balances two competing goals in a single number — run short jobs first (scheduling efficiency, for low job-completion time) versus give workers to jobs that actually scale (scaling efficiency) — and allocates via min-weight bipartite matching plus opportunistic worker-trading, reusing placements to keep rescaling cheap. The result is 1.3 to 2.46x lower job-completion time than state-of-the-art elastic schedulers, with negligible scheduling overhead.

Why this problem is worth solving

GPU clusters are enormously expensive, and training jobs are the dominant consumer, so how well a scheduler packs elastic jobs onto heterogeneous hardware translates directly into how much compute an organization wastes. The setup to understand first is what “elastic” buys and what it must decide. An

an ELASTIC training job is a distributed deep-learning job that can change its number of GPU workers while it runs, rather than reserving a fixed allocation for its whole lifetime. This lets a shared cluster pack more jobs in: a job scales up to use idle GPUs and scales down when they are reclaimed, so capacity is never stranded. The quantity that governs whether adding workers is worth it is SCALING EFFICIENCY: the ratio between the throughput a job actually achieves with some number of workers and the throughput it would achieve under perfect linear scaling (throughput growing in exact proportion to worker count). Efficiency of one means adding a worker adds its full throughput; efficiency well below one means the extra workers mostly spend their time communicating gradients rather than computing, so the marginal GPU is largely wasted. A good elastic scheduler wants to put workers where scaling efficiency is high and avoid piling them onto jobs where it has collapsed

is the lever the whole system turns on. If you know each job’s scaling efficiency at each configuration, you can allocate GPUs where they do the most good.

The reason this is hard, and interesting, is that scaling efficiency is not a property of the job alone. It depends on the

the fact that a real cluster is a mix of different GPUs and interconnects, which affects scaling efficiency in two ways. COMPUTATION heterogeneity: GPU generations differ enormously in raw speed (up to 48.5x in the paper’s measurements), which changes how much work each worker does per step and therefore how communication overhead compares to compute. COMMUNICATION heterogeneity: the link between GPUs matters just as much — a fast NVLink interconnect can speed a communication-heavy model up by 4x over PCIe, while a compute-bound model sees no benefit at all. The two interact in non-obvious ways: because a low-end GPU does less compute per step, the same communication cost is a smaller fraction of a larger whole, so jobs frequently scale BETTER on low-end GPUs than on high-end ones sharing the same network — yet a fast interconnect can flip that ordering for models that are bottlenecked on communication. So the same job has different scaling efficiency, and a different optimal worker count, on every kind of host

. This is exactly what the homogeneous-hardware assumption throws away, and it is why the scheduler needs per-configuration efficiency — which is why the cost of getting that information is the crux of the whole problem.

What people did before, and where it broke

Homogeneous elastic schedulers (AFS, SRSF). Prioritize short or small jobs and treat GPUs as interchangeable. Fast and simple, but blind to the fact that the same job scales very differently on different hardware, so they place workers where they are wasted.
Heterogeneity-aware but not elastic (Gavel and similar). Account for GPU-type performance differences in scheduling, but do not model how scaling efficiency changes with worker count under elastic rescaling, so they still misjudge how many workers a job should get on each host.
Exhaustive profiling. Measure throughput for every combination of model, host type, and worker count to know scaling efficiency exactly. Accurate, but the number of measurements grows as O(model x hardware x workers) — prohibitively expensive to run in a live production cluster.
Fixed-resource (non-elastic) training. Reserve a static allocation and avoid the rescaling decision entirely. Simplest of all, but leaves idle GPUs stranded and cannot adapt to contention.
The gap. No prior system delivers heterogeneity-aware scaling efficiency for elastic jobs at an affordable profiling cost, then uses it to balance scheduling and scaling. That is the gap Heet fills.

How Heet allocates GPUs without profiling everything

Predict the efficiency table cheaply, then price and match jobs to GPUs

The setup: elastic jobs on heterogeneous GPUs

Jobs rescale their worker count as the cluster fills and empties, and a job's scaling efficiency depends on both the model and the hardware type (compute speed and interconnect). Choosing how many and which GPUs to give each job requires knowing the efficiency of every configuration, which is expensive to measure.
↓ →
Profile only a handful of configurations new

Instead of measuring every (model, host, worker-count) combination, Heet profiles just about six entries per job — one short mini-batch iteration on each host type at a specific worker count — turning a combinatorial measurement into a linear one.
↓ →
Complete the efficiency table by collaborative filtering new

Heet treats the sparse throughput table like a recommender system. If a new job resembles a past one (prediction error small enough), it reuses that job's profile (91.2% accurate); otherwise it fills the missing entries by matrix factorization, learning latent factors that capture the job's compute- and communication-intensity (77 to 90% accurate).
↓ →
Price each job to balance two goals new

A single scheduling price per job combines two competing objectives: favor short jobs to reduce the number of active jobs and overall completion time (scheduling efficiency), and favor jobs that scale well so workers are not wasted (scaling efficiency). Lower price means higher priority; the price falls both for short jobs and for jobs with high throughput at more workers.
↓ →
Allocate via bipartite matching and trading new

Heet partitions the cluster GPUs into equal chunks and casts allocation as a min-weight bipartite matching between jobs and partitions, with edge weights given by the prices, solved with a classic matching algorithm. It then opportunistically trades workers away from poorly-scaling jobs to starved ones when that improves overall completion time.
↓ →
Place cheaply and rescale new

When applying a new allocation, Heet reuses previous worker placements as much as possible to minimize reconfiguration overhead (group re-initialization and synchronization), running on Horovod's elastic interface. Scaling down is about 6x cheaper than scaling up, so shrinking is nearly free.

Evaluated on a real 24-GPU cluster across three host types (T4/PCIe, A10/PCIe, V100/NVLink) plus large-scale simulation, driven by Microsoft production job traces (800 and 1500 jobs) over CV, NLP, and speech models. Compared against AFS, SRSF, and Gavel.

The idea

Predict the whole table from a few samples — the efficiency map is low-rank. The move that makes heterogeneity-aware elastic scheduling affordable is refusing to measure everything. The scaling-efficiency table over (job, hardware, worker-count) is combinatorially large, but it is not arbitrary: a job’s behavior on all that hardware is governed by a few underlying traits — chiefly how compute-intensive and how communication-intensive it is — so the table is effectively low-rank. Heet exploits this exactly as a recommender system exploits the fact that users’ tastes are low-rank: profile a handful of entries and complete the rest by matrix factorization, or reuse a similar job’s known row. This predict-do-not-measure discipline is the same one the site’s quantum- circuit-search page uses when it replaces training every candidate with a cheap correlated predictor, and the autotuning pages use when a surrogate model stands in for a full evaluation: you never needed the exact number for every cell, only enough structure to fill the map, and paying to measure each cell is the waste.

Measure the true, hardware-specific cost instead of assuming it away. The whole failure of prior schedulers is a uniformity assumption — that one GPU is like another, that scaling efficiency is a job property. Heet’s premise is that the cost is heterogeneous and must be characterized per hardware type, including the non-obvious effects (jobs scaling better on low-end GPUs, NVLink helping only some models). This refuse-the-uniform- assumption, measure-the-real-cost discipline is one the site returns to again and again — the pages on interconnect contention and I/O scheduling insist on the true measured cost of an operation rather than an idealized uniform one, and the coherent-NIC page lays data out for the substrate’s real cost model. Heterogeneity-awareness is just this principle applied to a cluster: the schedule is only as good as the cost model behind it, and a uniform cost model is wrong.

Fold competing objectives into one price, then reduce allocation to a solved graph problem. The scheduler has two goals that pull against each other: minimize job-completion time by clearing short jobs quickly, and maximize throughput by giving workers to jobs that scale. Rather than pick one, Heet encodes both in a single price that is low when a job is short AND when it scales well, so the two pressures compose into one comparable number. Refusing the either/or and combining objectives into a single tunable score is the same move the site’s query and interface pages make when they balance latency against throughput rather than trading one away. And with a price on every job-partition pair, allocation becomes a min-weight bipartite matching — a classic, efficiently-solvable graph problem — the same cast-the-problem-onto-a-solved-one reduction the site rewards when a scheduling or placement task is mapped onto matching, max-flow, or another well-understood primitive.

Choosing GPUs without measuring every option

From a combinatorial profiling trap to a fast schedule

Heterogeneity-aware elastic scheduling. Numbers from the paper's real-cluster and trace-driven evaluation.

Step 1 of 5

Why heterogeneity breaks naive scheduling

The same job behaves very differently across hardware: compute varies up to 48.5x across GPU generations, NVLink speeds VGG up 4x but does nothing for DenseNet, and jobs often scale BETTER on low-end GPUs. A scheduler that assumes uniform hardware places workers where they are wasted.

a heterogeneity-blind schedule takes 2408 or 2692 minutes where a heterogeneity-aware one takes 1680 — a 1.43 to 1.6x loss
scaling efficiency is a property of the (job, hardware) pair, not the job alone

Why it works

Scaling efficiency depends on both the model and the hardware (compute up to 48.5x apart, NVLink helping only some models) → assuming uniform hardware misplaces workers → a heterogeneity-aware allocation finishes 1.43 to 1.6x faster in the motivating example.
The efficiency table over (job, hardware, workers) is governed by a few latent traits (compute- and communication-intensity) → it is low-rank, so a handful of measurements plus matrix completion recover it → profiling drops from combinatorial to roughly linear at 77 to 91% accuracy.
The scheduler only needs the right ranking of configurations, not exact numbers → approximate predictions suffice → even a 30% profiling error raises completion time by only 5.5%.
A single price that is low for short jobs and for well-scaling jobs encodes both objectives at once → allocation becomes a min-weight bipartite matching → the two competing goals are balanced in one efficiently-solvable step, beating single-objective policies by 1.74x.
Reusing previous placements keeps reconfiguration cheap and scaling down is 6x cheaper than scaling up → rescaling can happen often without eroding gains → the elasticity is actually usable in production.

What it costs (trade-offs and scope)

The efficiency predictions are approximate. Matrix completion is 77 to 90% accurate with a median error of 17%; Heet tolerates this because the scheduler needs the ranking, not exact throughput (a 30% error costs only 5.5% in completion time), but a job whose behavior is genuinely not low-rank could be mispredicted.
Collaborative filtering needs structure or similar past jobs. A brand-new model with an unusual compute/communication profile, unlike anything profiled before, gets less accurate predictions until it is measured — the method leans on the table being low-rank and on job similarity.
It targets data-parallel elastic training. The scaling-efficiency model and the Horovod-based placement assume data parallelism; giant- model regimes that need pipeline or tensor parallelism have a different configuration space the method does not directly address.
The scheduler is a heuristic, not an optimum. The price, matching, and opportunistic trading optimize completion time and makespan without a global optimality guarantee, and the size of the win depends on the workload — gains are largest under heavy contention and when co-scheduling elastic with non-elastic jobs.
Rescaling is not free. Reconfiguration costs about 3% of a scheduling interval and a scale-up about 2.5% per event; Heet minimizes this by reusing placements, but a policy that rescaled extremely often would spend those gains back.

The evaluation

A real 24-GPU cluster across three host types (T4 on PCIe, A10 on PCIe, V100 on NVLink), plus large-scale simulation, driven by Microsoft production traces of 800 and 1500 jobs over CV, NLP, and speech models (ResNet, VGG, DenseNet, LSTM, Transformer, DeepSpeech2, and others), comparing Heet against AFS, SRSF, and Gavel on job-completion time, makespan, scaling efficiency, starvation, and overhead.

Scheduling elastic jobs on heterogeneous GPUs

Property	Homogeneous-assuming (AFS, SRSF)	Exhaustive profiling	Heet (this work)
Knows per-hardware scaling efficiency
Profiling cost
Objective
Allocation method		n/a
Job-completion time

Prior schedulers are either blind to heterogeneity (fast but misallocating) or would need combinatorial profiling to see it (accurate but unaffordable). Heet predicts every configuration's scaling efficiency from about six measurements via collaborative filtering, then prices and matches jobs to GPUs — cutting job-completion time 1.3 to 2.46x over AFS, SRSF, and Gavel with 2.93 seconds of scheduling overhead for 5000 jobs.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Read the scope precisely. Heet’s scaling-efficiency numbers are PREDICTIONS (77 to 90% accurate, median error 17%), not measurements; the design works because the scheduler needs the right ranking rather than exact throughput, so a 30% error costs only 5.5% in completion time — but a job whose behavior is genuinely not low-rank, or a brand-new model unlike anything profiled, will be predicted less well until it is measured. The method assumes data-parallel elastic training on Horovod, so giant-model pipeline or tensor parallelism, with its different configuration space, is out of scope. The scheduler is a heuristic (price, bipartite matching, opportunistic trading) optimizing completion time and makespan without a global optimality guarantee, and the size of the win depends on the workload — largest under heavy contention and when elastic and non-elastic jobs share the cluster. And rescaling is not free (about 3% of a scheduling interval, a scale-up about 2.5% per event), so the gains rest on reusing placements to keep reconfiguration cheap. Within that scope the lessons are clean and general: when a cost map over a combinatorial space is governed by a few latent factors, predict the whole map from a few samples instead of measuring it exhaustively; refuse the uniform-hardware assumption and characterize the true, heterogeneous cost; fold competing objectives into a single price and reduce the allocation to a solved graph problem; and keep the adaptation itself cheap so you can afford to do it often.

Background

Predict the map, measure the true heterogeneous cost, and price the tradeoff

This paper sits in the site’s ML-systems and scheduling clusters and rhymes with several ideas covered elsewhere on this site. Its central move is to replace exhaustive measurement with cheap prediction, exploiting that the scaling-efficiency table over (job, hardware, worker-count) is low-rank — governed by a few latent traits — so a handful of samples plus matrix completion recover it. That is the same predict-do-not-measure, low-rank-completion discipline the quantum-circuit-search page uses when it replaces training every candidate with a cheap correlated predictor, and the autotuning pages use when a surrogate model stands in for a full evaluation. Its premise is a refusal of the uniform-hardware assumption: scaling efficiency depends on the specific GPU and interconnect, with non-obvious effects (jobs scaling better on low-end GPUs, NVLink helping only some models), the same measure-the-true-cost discipline the pages on interconnect contention and I/O scheduling apply, and the same lay-out-for- the-real-cost-model stance the coherent-NIC page takes. Its scheduler folds two competing objectives — clear short jobs fast, and feed workers to jobs that scale — into a single price, the same refuse-the-either/or, balance-both move the query and interface pages make when they trade latency against throughput in one objective, and it then reduces allocation to a min-weight bipartite matching, the same cast-the-problem-onto-a- solved-one reduction the site rewards when a placement task is mapped onto matching or max-flow. Even its care to keep reconfiguration cheap by reusing placements echoes the make-the-adaptation-cheap discipline the kernel-re-randomization and coherent-NIC pages rely on. Together they make Heet a case study in making an expensive, heterogeneous decision cheap enough to make well.

If you remember only three things

1. Elastic training jobs grow and shrink their GPU workers as a shared cluster fills and empties, and at each rescaling the scheduler must choose how many and which GPUs. This is hard because clusters are HETEROGENEOUS — compute varies up to 48.5x across GPU types, NVLink speeds some models up 4x and others not at all, and jobs often scale BETTER on low-end GPUs — so a job's SCALING EFFICIENCY depends on the hardware, not just the model. Prior schedulers assume uniform hardware and misallocate (a heterogeneity-blind schedule runs 1.4 to 1.6x slower), while measuring every (model, hardware, worker-count) configuration is combinatorially unaffordable.
2. Heet makes heterogeneity-aware scheduling affordable by predicting the scaling efficiency of ALL configurations from about six measurements via 3-D COLLABORATIVE FILTERING: it treats the (job, host, worker-count) throughput table like a recommender system, reusing similar past jobs (91.2% accurate) or completing the sparse table by matrix factorization into compute- and communication-intensity factors (77 to 90% accurate) — because the table is low-rank. It then prices each job to balance running short jobs first (scheduling efficiency) against feeding workers to jobs that scale (scaling efficiency), and allocates via min-weight bipartite matching plus opportunistic worker-trading, reusing placements to keep rescaling cheap.
3. Heet cuts job-completion time by 1.3 to 2.46x over AFS, SRSF, and Gavel, keeps scaling efficiency at 0.83 to 0.87 (95.3% better than SRSF), reduces starvation by 40.5% under heavy contention, and beats single-objective policies by 1.74x, all with negligible overhead (2.93 seconds for 5000 jobs). The transferable lessons: when a cost map over a combinatorial space is governed by a few latent factors, predict it from a few samples instead of measuring exhaustively; refuse the uniform-hardware assumption and model the true heterogeneous cost; fold competing objectives into one price and reduce allocation to a solved graph problem; and keep the adaptation itself cheap.

Check yourself

Check your understanding

1. To schedule elastic jobs well on heterogeneous GPUs, Heet needs the scaling efficiency of every configuration, yet it profiles only about six per job. Predict how it obtains the rest.
2. Prior schedulers treat one GPU as interchangeable with another. Predict why that assumption is so damaging for elastic training, using the paper's findings.
3. Heet's scheduler faces two goals that pull against each other: finish short jobs fast, and give workers to jobs that scale well. Predict how it reconciles them.
4. Heet's scaling-efficiency table is filled with PREDICTIONS that are only 77 to 90% accurate, yet its scheduling is robust — a 30% profiling error raises completion time by only 5.5%. Predict why approximate predictions are good enough.

Sources

Heet: Accelerating Elastic Training in Heterogeneous Deep Learning Clusters (ACM DL, DOI 10.1145/3620665.3640375) — ASPLOS 2024 (full text read via the ACM PDF).
ACM Digital Library entry — published version and metadata.