Profile Only Where the Rounding Looks: Hardware-Certified Scheduling from Sparse LP Supports

Schedulers for mixed hardware, such as a cluster with several GPU generations or a phone chip with fast and slow cores, need a table of how long each job takes on each machine type. In practice that table comes from a simulator or a learned estimator, because running every job on every machine type is expensive. Those estimates are biased in ways that matter. Simulated power and performance models break on workloads unlike their training set, and real contention, memory stalls and migration costs are missing from them. The obvious fix is to measure everything on real hardware, and that is exactly the cost the estimates were meant to avoid.

This proposal argues that a classical fact from approximation algorithms says which few measurements are worth paying for. The scheduling problem is first solved as a linear program, an optimization in which jobs may be split fractionally across machines. The corner-point solutions of that program have very sparse structure. Their fractional job–machine pairs form a pseudoforest: a graph whose connected pieces each contain at most one cycle, so it has no more edges than vertices. Standard rounding turns such a solution into a real schedule whose error depends only on the processing times along those few edges. We propose to measure on hardware only the job–machine pairs that the solution uses or that could plausibly enter it, round with pseudoforest rounding, and return a schedule together with a makespan bound stated in measured hardware time rather than simulated time. The cost of measurement then grows with the number of jobs plus machines, not with their product.

Core Claim

Let $p_{ij}$ be the true hardware processing time of job $j$ on machine $i$, and let $\hat p_{ij}$ be the simulator's estimate. Suppose we have calibrated intervals $[\ell_{ij}, u_{ij}]$ that contain $p_{ij}$ with high probability. Solve the makespan assignment program with target $T$. Any corner-point solution has a support graph $G$ that is a pseudoforest, so it has at most $|J|+|M|$ edges, where $J$ is the set of jobs and $M$ the set of machines. Cancel the cycles in $G$ by shifting load around them, which leaves every job's total assignment and every machine's load unchanged, as in the rotation technique of Leah Epstein et al.. Then round the remaining forest so that each machine receives at most one extra fractional job. The realized hardware makespan then satisfies

$$C_{\max}^{\text{hw}} \le T + \max_{(i,j) \in G} p_{ij},$$

where every quantity on the right is either a decision variable or a pair we have measured.

The rounding error therefore lives entirely on the support edges. The remaining question is whether $T$ is a valid lower bound on the hardware optimum. That holds if the program stays infeasible at $T-\delta$ when each unmeasured pair is set to its interval lower bound $\ell_{ij}$. It suffices to measure the pairs whose reduced cost, the LP's own estimate of how much a pair would improve the objective, changes sign over its interval. The claim we will test is that this set is small in realistic traces. If it is, a schedule certified within roughly a factor of two of the hardware optimum costs on the order of $|J|+|M|$ hardware profiles instead of $|J|\cdot|M|$.

Positioning Against Prior Work

Two bodies of work motivate this proposal without solving it. On the theory side, pseudoforest rounding gives sharp guarantees, but every paper in our file assumes exact, static processing times. Examples are the $(1.36+\epsilon)$ iterative rounding for weighted completion time in Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs, the oriented-pseudoforest rounding for malleable jobs in Malleable scheduling beyond identical machines, and the pseudotree analysis with fixed setup times in Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines. We supply the technique these papers lack: an account of which inputs the guarantee actually depends on, and the cost of learning those inputs.

On the systems side, Gavel solves a continuous allocation over GPU types, profiles throughput, and runs the fractional allocation directly by time slicing. Hadar/HadarE uses primal-dual pricing and job forking. Neither uses the sparsity of corner points, and neither treats measurement as a budgeted resource tied to the rounding.

The calibration literature constrains the design. Walker et al. show that black-box performance and power models fit their training workloads but fail badly on new ones, and that a physically informed model reaches 2.8% mean absolute percentage error. We therefore do not trust a single global correction of the simulator. Instead, intervals are calibrated per workload class and checked against held-out measurements. Air Learning shows that targeted hardware-in-the-loop measurement can close a simulation gap: in their setting the flight-time gap fell from 37.73% to 0.5%. We take the same lesson into combinatorial scheduling.

Research Program

The first component is the measurement loop. We start from simulator estimates and draw a small random calibration sample of hardware pairs. From that sample we form per-class intervals using a distribution-free quantile method, so the coverage claim does not depend on a model of simulator error. Each iteration has four steps. We solve the program, measure every support edge, compute interval reduced costs for the remaining pairs, and measure those whose sign is ambiguous. We stop when the support is fully measured and no reduced cost is ambiguous. At that point the bound above holds, with probability set by the interval coverage. We will prove that the loop terminates, and we will bound the number of measurements in terms of the number of ambiguous pairs. Characterizing when that number stays near $|J|+|M|$ is the main analytical question.

The second component exploits slack in the rounding. Cycle cancellation can move load in either direction around a cycle, and the forest rounding can choose which machine absorbs each leftover fractional job. These choices do not change the guarantee. We use them to send the job whose hardware time is most uncertain, or most exposed to interference from other jobs on the same node, onto the machine with the most measured slack. This is the one place where contention enters the method. Pseudoforest rounding adds at most one job per machine beyond its fractional load, which limits how much interference can be introduced.

The third component is an extension to splittable jobs with setup costs, following the formulation in Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines. There the measured quantity is the real migration or warm-up cost on each support edge rather than a fixed constant. This connects to Gavel's observation that preemption costs under 5 seconds only when rounds last at least 6 minutes.

Baselines

The naive reference is pseudoforest rounding run directly on uncorrected simulator estimates, with no hardware measurement. It shows how large the gap is when nothing is done. The schedule is then executed on hardware, and its realized makespan is compared with the hardware optimum. On the small testbed that optimum is known exactly; on the cluster we use the full-measurement lower bound.

The strongest existing systems method is Gavel with full profiling and time slicing, re-run on the same trace, the same GPU mix and the same simulator inputs. It is the strongest competitor because it is the deployed heterogeneity-aware approach and executes fractional allocations without any rounding loss. Its reported results include up to 3.5× better average job completion time for single-GPU jobs (Gavel). Hadar reports 1.20× faster total training time than Gavel on the 480-job Microsoft trace (Hadar), and we include Hadar as a second systems baseline. We found no reported result on Lacuna for makespan as a function of the hardware-profiling budget, which is the axis we care about. We will therefore give each method the same profiling budget, counted as GPU-minutes. Beating these baselines means matching their realized makespan within 5% while using at most a third of their profiling budget, or achieving strictly lower makespan at equal budget.

A full-measurement oracle, meaning pseudoforest rounding on the true matrix, serves as the upper reference.

Two ablations isolate the key ingredient. In the first, the same number of measurements is spent on uniformly random pairs. In the second, measurements are spent only on the pairs the final rounded schedule uses, without the reduced-cost check. If the second ablation matches the full method, our certification step adds nothing in practice, and we will report that.

Why not just…?

Why not just measure the pairs the scheduler picks? This is the real threat. It is cheap, and it already corrects the load on every machine. What it cannot do is detect an unmeasured pair whose true time is much better than the simulator claims. Such a pair would lower the optimum, so the schedule may be poor without any symptom. The ablation above measures how often this happens. We will also build adversarial traces in which the simulator overestimates one GPU type, where we expect the failure to be visible.

Why not just calibrate the whole simulator matrix with a learned model? Walker et al. show that this kind of model fails on unseen workloads (Accurate and stable empirical CPU power modelling for multi- and many-core systems). A calibrated estimator still gives no hardware-time certificate. We use calibration only to set intervals, and we measure wherever an interval could change the decision. We will compare against a regression-corrected matrix fed to the same rounding at equal budget.

Why not just time-slice the fractional solution, as Gavel does? Time slicing avoids rounding loss but pays migration and preemption costs on every split. It also does not apply to jobs that cannot be preempted. Moreover, it still needs the full throughput matrix. Our experiments report both the measurement budget and the realized migration overhead.

Why not a greedy scheduler? Greedy activation carries an unavoidable logarithmic loss in cost (Energy Efficient Scheduling via Partial Shutdown). It also provides no lower bound against which to certify. We include a greedy earliest-finish baseline on measured-on-demand times so that it gets the same feedback our method does.

Proposed Experiments

The first testbed is the 480-job Microsoft trace on K80, P100 and V100 GPUs, the setting used by Gavel and Hadar. A throughput estimator stands in for the simulator, and real profiling runs are the hardware measurements. The second testbed is fully controlled: gem5 serves as the simulator and an ODROID-XU3 board with fast Cortex-A15 and slow Cortex-A7 cores as the silicon, running the 45+ benchmarks used by Walker et al. Measurement on this board is cheap, so we can compute the exact hardware optimum and check every certificate. That makes it the testbed where the coverage claims are verified rather than assumed.

We track five metrics: realized hardware makespan, the ratio of realized makespan to the certified lower bound, the number of hardware profiles used, the empirical coverage of the certificates, and total migration overhead.

Three outcomes decide the proposal. First, the number of ambiguous pairs should stay within a small multiple of $|J|+|M|$ as the trace grows. If it grows with $|J|\cdot|M|$, the approach offers no savings. Second, certificates must hold at their nominal rate on the ODROID ground truth. Third, the method must outperform the measure-what-you-picked ablation on at least the adversarial traces. If it does not, we will conclude that the support-sparsity argument, and not the certification, is what carries the practical value.