Training Job Placement in Clusters with Statistical In-Network Aggregation

Training a large model across many machines means every machine must combine its gradient with everyone else's on every single step, and that combining has become a major bottleneck — so a clever recent idea moves the arithmetic into the network switches themselves, which add the numbers up as the packets pass through, cutting both traffic and processor work; the difficulty is that a switch has only a tiny amount of on-chip memory to do this with, and the elegant way to share it is to stop rationing it centrally and simply let jobs compete, since ordinary congestion control drives them to a fair split by itself, which is simpler and wastes less; but that elegance costs something nobody accounted for, because when allocation becomes emergent rather than assigned, the scheduler deciding where to put a new job can no longer SEE what is available; this paper (Tsinghua and Peking) answers by computing the equilibrium instead of measuring it, valuing each machine by what it can offer minus the harm the new job would do to its neighbours, and searching with a knapsack-style method rather than the intractable exact one — finishing jobs 45 percent faster.

The argument in one glance

Problem

Combining gradients is a bottleneck, and the fix has a very small budget

Training a neural network across many machines means that on every single iteration, each machine must combine the gradient it computed with everyone else's before the model can be updated. That operation moves enormous amounts of data and consumes processor time, and it has become one of the main things limiting how fast large models train. IN-NETWORK AGGREGATION is a clever attack on it — instead of shipping all the gradients to some machine to be added up, let the network SWITCHES add them as the packets pass through, which cuts the traffic that must be carried and offloads the arithmetic entirely. The catch is the budget. A switch has only a small amount of on-chip memory to hold partial sums, and that memory has to be divided among all the jobs sharing the cluster. How to divide it turns out to determine everything else.
What people did

Have a controller reserve a region of switch memory for each job

The straightforward approach gives each job its own reserved slice. A central controller partitions the switch memory, assigns a region to each job, and holds that region for the job's entire lifetime. Every job then knows exactly what it has, the controller knows exactly what is allocated, and nothing interferes with anything else — the same logic that makes any reservation system predictable.
Why it fell short

Reservations waste memory, and the alternative hides the state

Reserving for a job's whole lifetime wastes memory whenever a job is not using its share, and coordinating those reservations forces scheduling intervals of ten seconds or more while requiring the cluster scheduler to reach into the network and control it — awkward when compute and network are administered separately. The alternative, letting jobs contend for a shared pool, fixes all of that elegantly, because ordinary endpoint congestion control drives the jobs to a fair split by itself with nothing central enforcing it. But that elegance has an unbilled cost. When the allocation is EMERGENT rather than assigned, nobody holds a record of it, so a scheduler deciding where to place a new job cannot see what is free — and the resources it must balance are coupled, since memory that aggregates traffic is bandwidth that does not have to be carried.
This paper's idea

Compute the equilibrium you cannot observe, and price the harm you would do

This paper (Tsinghua and Peking — Zhao, Xu, Liu, Tian, Wang, Wu) builds NetPack, which accepts the shared-pool arrangement and supplies the missing visibility by CALCULATING it. Since the split emerges from congestion control converging to a fair share, its resting point is predictable, so a water-filling algorithm computes the steady state that bandwidth and switch memory would jointly settle into — treating the two as coupled rather than as separate budgets. On top of that estimate, each candidate machine is scored not merely by what it has spare but by what it has spare MINUS the throughput the new job would take from jobs already running there, which prices the harm rather than only the resource. The exact placement problem is intractable, so instead of solving it, the search is restructured as a series of knapsack problems solved by dynamic programming — placing thousands of jobs in under a minute. Jobs finish 45 percent faster on production traces, and revealingly, 87 percent faster even when the switch aggregation is turned off entirely.

Why this problem is worth solving

The bottleneck being attacked here is one of the central costs of training large models, so it is worth being clear about the mechanism.

Training a neural network across many machines splits the data among them, and each machine computes a GRADIENT — a set of proposed adjustments to every parameter in the model. Because they all must end up with the same updated model, every iteration requires combining all those gradients into one, an operation of enormous size since the gradient is as large as the model itself. Conventionally this means shipping gradients across the network to be summed, which consumes bandwidth and processor time and has become a major limit on training speed. IN-NETWORK AGGREGATION observes that modern network switches are programmable and can therefore do arithmetic on packets as they pass through — so rather than carrying all the gradients to a destination and adding them there, the switch adds them in flight, forwarding only the sum. This reduces the traffic that must be carried and removes the work from the machines. The constraint is that a switch holds partial sums in a small amount of on-chip memory, and because each partial sum is held for roughly one network round trip, the memory converts directly into a rate — the amount of memory divided by the round-trip time gives the peak aggregation throughput the switch can sustain

. That small budget is the resource everything then competes for.

How that budget is divided turns out to change the nature of the problem.

SYNCHRONOUS sharing gives each job a reserved region of switch memory, assigned by a central controller and held for the job’s lifetime. It is predictable and its state is explicitly recorded, but it wastes memory whenever a job is idle, forces scheduling decisions at ten-second-or-longer intervals, and requires the compute scheduler to reach in and control the network, which is awkward when the two are run by different teams. STATISTICAL sharing instead treats the memory as one pool that jobs grab from transiently, holding a slot for only tens of microseconds. Nothing coordinates them; each job simply runs ordinary endpoint CONGESTION CONTROL, increasing its sending rate gradually and backing off sharply when it meets contention, and the jobs collectively converge to a max-min fair split as a side effect. This uses memory far better, keeps the control plane simple, and needs no cross-domain coordination. Its hidden cost is observability: because the allocation is emergent rather than assigned, there is no record of who holds what, so a scheduler about to place a new job cannot query how much of anything is available

What people did before, and where it broke

Reserve switch memory per job. A controller partitions the memory and assigns regions for each job’s lifetime. Predictable and inspectable, but memory sits idle whenever its owner is not transmitting, and the coordination forces slow scheduling intervals.
Require the scheduler to control the network. Reservation schemes need the job scheduler to program the switches, which crosses an administrative boundary that in many organisations separates the compute cluster from the network.
Place jobs by balancing processors. Standard cluster schedulers spread jobs to keep processor usage even. Reasonable when computation is the scarce resource, but it ignores that where a job lands determines how much traffic it generates and how much switch memory it can obtain.
Place jobs by balancing network flows, or by minimising fragmentation. Other established policies optimise one dimension each. Each is defensible alone, and the paper measures all of them, but no single dimension captures efficiency when the resources trade against one another.
Existing schedulers with aggregation switched on. Every baseline evaluated had in-network aggregation enabled — they simply did not account for it when deciding placement, which is exactly the omission the paper targets.
The gap. Nobody had a placement method for the shared-pool arrangement, because it requires knowing an allocation that no component records. Since the arrangement is the one worth using — better utilization, simpler operation, no cross-domain coordination — the missing piece was a way to reason about resources you cannot query. That is the gap NetPack fills.

How placement works when nothing records the allocation

Compute the equilibrium, price the damage, then search with knapsacks

Shared-pool aggregation hides its own state

Letting jobs contend for switch memory beats reserving it, because congestion control converges them to a fair split with no central enforcement and no wasted reservations. But the allocation is emergent, so nothing records it, and a scheduler placing a new job cannot see what is free.
↓ →
Calculate the resting point instead of querying it new

Because the split is the equilibrium that congestion control converges to, it can be computed. A water-filling algorithm fills traffic to active jobs until links and switches saturate, freezing each job as its bottleneck is reached, and treats bandwidth and switch memory jointly since aggregated traffic is traffic that need not be carried.
↓ →
Score each machine by what it offers minus what it costs others new

A candidate machine is valued not just by its spare bandwidth but by that figure reduced by the throughput a new flow would take away from the jobs already there. Placement is treated as inflicting a cost on neighbours rather than merely consuming something free.
↓ →
Choose which jobs to admit new

From the waiting batch, selecting the most valuable set that fits the available processors is exactly a knapsack problem, and is solved as one rather than by a greedy rule.
↓ →
Place the workers without creating hotspots new

Dynamic programming runs over the machines, tracking the best value achievable for each combination of flow count and processor count so that concentrating too many flows on one machine is penalised, then the coordinating node is placed by evaluating every candidate location against each worker arrangement.
↓ →
Decide which jobs get to use the switch at all new

Since switch memory is finite, jobs are ranked by how much aggregation actually buys them — their throughput multiplied by how many flows converge on them — and aggregation is enabled down that list until the memory is exhausted, rather than granted to whoever asks first.

Evaluated on a testbed of five machines with a programmable switch, and in a simulator of a 16-rack network validated to 98 percent correlation with the testbed, driven by production traces and standard image models.

The idea

When decentralization removes the record, compute the equilibrium instead of querying it. The shared-pool arrangement is genuinely better — it wastes less memory, keeps the control plane simple, and avoids making the compute scheduler reach into the network. Its cost is that nothing knows the allocation, because the allocation is something the system settles into rather than something anybody decides. NetPack’s answer is that emergent does not mean unpredictable: congestion control converges to a known kind of fair split, so the resting point can be calculated by filling traffic to each job until some link or switch saturates. It is worth contrasting this with the opposite situation covered elsewhere on this site, where a quantum system’s drift could not be MODELLED and so was measured with a control experiment instead. Here the quantity cannot be measured but can be modelled, and recognising which of the two you face — and that one of them is always available — is the general lesson.

Price the externality, not just the resource. The scoring rule is the most portable idea here. A naive scheduler asks how much spare capacity a machine has; NetPack subtracts from that the throughput the new job would take away from jobs already running there. This reframes placement as inflicting a cost on neighbours rather than as consuming something free, which matters precisely because the sharing is statistical — an additional flow does not fail, it simply makes everyone else’s share smaller, and a policy that only counts free capacity is blind to exactly that. Accounting for the damage a decision does to existing work, rather than only for what it consumes, is the same consider-the-whole-system discipline covered elsewhere on this site, in the pages that count what was thrown away alongside what was used rather than reporting only the successful part.

An intractable problem restated as one that is already solved. Finding the optimal placement is NP-complete, and the exact formulation needs more than four hours at production scale. Rather than approximating the original problem, NetPack restates it as a sequence of knapsack problems — which jobs to admit given the processors available is literally a knapsack, and worker placement becomes dynamic programming over machines that tracks the best value for each combination of flow count and processor count. The result runs in under a minute for four thousand jobs. Recasting a hard problem into a shape with a known efficient algorithm, instead of attacking it directly, is the map-onto-a-solved-problem move covered elsewhere on this site wherever an apparently novel search turns out to be a familiar one in disguise.

Placing one training job

Deciding where a job goes when you cannot see what is free

One placement decision in NetPack. Numbers from the paper's testbed and simulator.

Step 1 of 5

What the cluster looks like

Machines hold processors; the switches above them can add gradients in flight, using a small pool of on-chip memory that jobs grab from transiently. No component records who holds how much, because each job simply runs congestion control and the split emerges from their contention.

a partial sum occupies switch memory for roughly one network round trip, so the memory divided by that round trip gives the switch's peak aggregation rate
running jobs are never moved, because relocating a training job across processors is prohibitively expensive

Why it works

Statistical sharing lets jobs contend rather than reserving memory → nothing records the allocation, so a scheduler cannot query it → but because congestion control converges to a known fair split, the resting point can be computed instead.
Switch memory that aggregates traffic is bandwidth that need not be carried → the two resources are coupled rather than independent budgets → so estimating them jointly with water-filling beats treating each separately, by up to 63 percent.
Under statistical sharing an extra flow does not fail but shrinks everyone else’s share → scoring a machine by spare capacity alone misses that cost → subtracting the throughput taken from existing jobs prices the actual damage.
The optimal placement is NP-complete and needs over four hours at scale → restating admission as a knapsack and placement as dynamic programming gives an efficient algorithm → four thousand jobs are placed within a minute.
Where a job lands determines both its traffic and the switch memory it can reach → placement is therefore a cross-layer decision, not a processor-packing one → which is why methods balancing processors alone lose even with aggregation switched on.

What it costs (trade-offs and scope)

Much of the benefit is not from the headline feature. With switch aggregation disabled entirely, the improvement is still 87 to 92 percent. The authors report this plainly, and it means the gains come substantially from cross-layer placement of processors and bandwidth rather than from in-network aggregation coordination alone.
It assumes one training architecture. The modelling targets parameter-server training, treating aggregation with multiple coordinators as a composition of single-coordinator cases. How well it transfers to ring-shaped aggregation schemes is not established.
The estimate is a model, and models have inputs. Accuracy depends on correct round-trip time and peak aggregation rate figures, and the theoretical analysis assumes a simplified network with full bisection bandwidth, though the experiments relax that.
Running jobs are never moved. Because relocating a training job across processors is prohibitively expensive, placement decisions are permanent for the job’s lifetime, so a poor early decision cannot be repaired and the quality of each individual choice matters more.
Several conditions are assumed rather than enforced. Jobs are taken to be independent, mutually concurrent, and well behaved in following network protocols, and processors are held until a job finishes rather than being preemptable — reasonable for a cooperative cluster, less so for an adversarial one.

The evaluation

NetPack was built as a prototype on a testbed of five machines with two processors each and a programmable switch, and evaluated more broadly in a simulator of a 16-rack network validated to 98 percent correlation against the testbed. Workloads were standard image models on a large image dataset together with production traces from a commercial cluster. It was compared against five established placement policies — balancing processors, balancing network flows, minimising fragmentation, and two well-known cluster schedulers — all of which had in-network aggregation enabled but none of which considered it when placing.

Sharing switch memory and placing training jobs

Property	Reserved per-job memory	Shared pool, processor-balanced placement	NetPack
Switch memory utilization
Operational burden
Knows what is available
Accounts for harm to neighbours
Job completion time

Jobs finish 45 percent faster than prior placement methods on production traces and up to 78 percent faster in larger simulated clusters, with a 31 percent average improvement across cluster sizes from a hundred to ten thousand machines. Joint optimization of the coupled resources beats optimizing them separately by up to 63 percent, and placement costs about thirteen milliseconds per job even at ten thousand machines.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Read one result carefully before attributing the gains. With switch aggregation disabled entirely the improvement is still 87 to 92 percent, which the authors report openly and which means much of the benefit comes from placing jobs with regard to both processors and network bandwidth, rather than from coordinating in-network aggregation specifically. The modelling also targets one training architecture, treating multi-coordinator aggregation as a composition of single-coordinator cases, and its transfer to ring-shaped schemes is not established. The availability estimate is a computed model rather than a measurement, so it depends on correct round-trip time and peak aggregation figures, and the theoretical analysis assumes a simplified fully-connected network even though the experiments relax that. Because relocating a training job is prohibitively expensive, placements are permanent for a job’s lifetime, so a poor decision cannot be repaired later. And several conditions are assumed rather than enforced — that jobs are independent and concurrent, that they follow network protocols honestly, and that processors are held until a job finishes. Within that scope the lessons travel well: when decentralization removes the record of who holds what, ask whether the equilibrium can be computed even though it cannot be queried; score a decision by the harm it does to existing work and not only by what it consumes; and when the exact problem is intractable, look for a restatement whose shape already has an efficient algorithm.

Background

Model what you cannot measure, and charge for the damage you do

This paper sits in the site’s machine-learning-systems and datacenter cluster and rhymes with several ideas covered elsewhere on this site. Its central difficulty is one worth naming — decentralization bought better utilization, a simpler control plane and freedom from cross-domain coordination, but it removed the record of who holds what, so observability was the unbilled cost of elegance. Its answer, computing the equilibrium that congestion control converges to rather than querying an allocation nobody stores, forms an instructive pair with the quantum-noise page covered elsewhere on this site, where the situation is exactly inverted: there a drift could not be modelled and so was measured with a control experiment, while here a quantity cannot be measured and so is modelled. Between them they make the point that one of the two routes is nearly always open. Its valuation rule, scoring a machine by spare capacity minus the throughput a new job would take from its neighbours, is the account-for-the-whole-cost discipline the site rewards, in the same spirit as the cloud-capacity page counting every machine fabricated including those discarded rather than only those used. Its restatement of an NP-complete placement as a sequence of knapsack problems is the map-onto-a-solved-problem move that recurs whenever a novel-looking search is a familiar one in disguise. And its treatment of switch memory and link bandwidth as coupled rather than separate budgets — since aggregated traffic is traffic nobody carries — echoes the cross-layer co-design the graphics-processor and open-hardware pages rely on, where optimizing each layer alone leaves the interaction unexploited.

If you remember only three things

1. Training a model across many machines requires combining every machine's gradients each iteration, which has become a major bottleneck. In-network aggregation attacks it by having programmable switches add gradients as packets pass through, cutting traffic and offloading work. But a switch holds partial sums in a small on-chip memory, and how that memory is divided changes the problem: reserving a region per job wastes it while idle, forces scheduling intervals of ten seconds or more, and requires the compute scheduler to control the network across an administrative boundary. Letting jobs contend for a shared pool fixes all of that, because ordinary congestion control converges them to a fair split by itself.
2. The unbilled cost of that elegance is observability. When allocation is emergent rather than assigned, nothing records it, so a scheduler placing a new job cannot query what is free — while the resources it must balance are coupled, since switch memory that aggregates traffic is bandwidth nobody has to carry. NetPack supplies the missing visibility by COMPUTING the equilibrium instead, using a water-filling algorithm that gives traffic to each job until some link or switch saturates. It then scores each candidate machine by its spare bandwidth MINUS the throughput a new flow would take from jobs already there, pricing the harm rather than just the resource, and restates an NP-complete placement search as knapsack problems solved by dynamic programming, placing four thousand jobs in under a minute.
3. Jobs finish 45 percent faster than prior placement methods on production traces, up to 78 percent in larger simulated clusters, with joint optimization of the coupled resources beating separate optimization by up to 63 percent. Notably, every baseline had aggregation enabled and simply ignored it when placing. The authors also report that with aggregation disabled entirely the improvement is still 87 to 92 percent, meaning much of the gain comes from cross-layer placement rather than from aggregation coordination. The transferable lessons: when decentralization removes the record, ask whether the equilibrium can be computed even if it cannot be queried; score a decision by the damage it does to existing work; and restate an intractable problem into a shape that already has an efficient algorithm.

Check yourself

Check your understanding

1. Letting jobs contend for a shared pool of switch memory is better than reserving regions, yet it creates the problem this paper solves. Predict what it costs.
2. NetPack scores a machine by its spare bandwidth minus the throughput a new job would take from jobs already there. Predict why the subtraction matters.
3. The authors report that with switch aggregation disabled entirely, NetPack still improves job completion time by 87 to 92 percent. Predict what that implies.
4. Finding the optimal placement is NP-complete and takes over four hours at production scale. Predict how NetPack gets an answer in under a minute.

Sources

Training Job Placement in Clusters with Statistical In-Network Aggregation (ACM DL, DOI 10.1145/3617232.3624863) — ASPLOS 2024; full text read for this explainer.
Wenfei Wu’s homepage — the senior author’s group and related in-network computing work.