PaperlayerView exact revision on arXiv

Source-linked AI summary

Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads

Deepak Narayanan, Keshav Santhanam, Fiodar Kazhamiaka, Amar Phanishayee, Matei Zaharia

arXiv:2008.09213v1cs.DC

TL;DR

Existing accelerator-cluster schedulers generally do not account for model- and hardware-dependent performance while optimizing objectives such as fairness and makespan. Gavel transforms these policies into heterogeneity-, colocation-, and placement-aware optimization problems, then uses round-based scheduling to realize the resulting allocations. Its policies sustain higher cluster load and improve average job completion time, makespan, and cost relative to heterogeneity-agnostic policies.

  • Problem

    Accelerator performance varies across models, but existing cluster schedulers largely optimize multi-job objectives without accounting for this heterogeneity.

  • Method

    Gavel transforms existing scheduling policies into heterogeneity-, colocation-, and placement-aware optimization problems and realizes allocations with a decoupled round-based scheduler.

  • Results

    Gavel improves average job completion time by 3.5×, makespan by 2.5×, and cost by 1.4× while supporting higher maximum cluster load.

  • Takeaways & Limitations

    Gavel provides heterogeneity-aware versions of many existing policies, including fairness, FIFO, makespan, cost, shortest job first, and hierarchical policies.

  • Takeaways & Limitations

    Gavel does not propose new scheduling policies or performance optimizations, and leaves strategy-proof policies to future work.

Abstract

from arXiv · show

Specialized accelerators such as GPUs, TPUs, FPGAs, and custom ASICs have been increasingly deployed to train deep learning models. These accelerators exhibit heterogeneous performance behavior across model architectures. Existing schedulers for clusters of accelerators, which are used to arbitrate these expensive training resources across many users, have shown how to optimize for various multi-job, multi-user objectives, like fairness and makespan. Unfortunately, existing schedulers largely do not consider performance heterogeneity. In this paper, we propose Gavel, a heterogeneity-aware scheduler that systematically generalizes a wide range of existing scheduling policies. Gavel expresses these policies as optimization problems, making it easy to optimize for objectives in a heterogeneity-aware way, while also being cognizant of performance optimizations like space sharing. Gavel then uses a round-based scheduling mechanism to ensure jobs receive their ideal allocation given the target scheduling policy. Gavel's heterogeneity-aware policies allow a heterogeneous cluster to sustain higher input load, and improve end objectives such as average job completion time and makespan by up to 3.5x compared to heterogeneity-agnostic policies.

1 Introduction

Heterogeneous accelerators and model-dependent performance complicate multi-tenant cluster scheduling, especially when policies must also account for cost, colocation, and placement. Gavel reformulates existing policies as heterogeneity-aware optimization problems and realizes their allocations through round-based scheduling.

  • Scheduling Gap: Existing cluster schedulers must allocate diverse resources across users while optimizing objectives such as fairness, makespan, and hierarchical resource sharing.These settings include public clouds with multiple accelerator generations and private clusters accumulated over time.
  • Performance Heterogeneity: Model performance varies substantially across accelerator types, with ResNet-50 seeing nearly 10× V100-over-K80 speedup while A3C sees 2×.On a dollar-normalized basis, older P100 GPUs can remain competitive or cheaper for many models.
  • Design Motivation: Gavel explicitly models space sharing and placement sensitivity alongside hardware and workload heterogeneity when optimizing global scheduling objectives.The paper reports up to 2.2× improvement over Gandiva’s ad-hoc space-sharing approach.
  • Gavel Framework: Gavel generalizes policies including fair sharing, FIFO, minimum makespan, cost subject to SLOs, finish-time fairness, shortest job first, and hierarchical scheduling.These policies are expressed as optimization problems whose objectives depend on achieved throughput and can be transformed for heterogeneity, colocation, and placement awareness.
  • Scheduling Mechanism: A preemptive round-based mechanism maps computed heterogeneous allocations to placements for distributed jobs and concurrently colocated jobs.The scheduler grants resources in time fractions that closely resemble each job’s target allocation.
  • Results: 3.5× improvement in average job completion time accompanies 2.5× makespan and 1.4× cost improvements on a larger simulated cluster.On a smaller physical cluster, objectives improve by up to 1.4×.

2 Background

DNN training is iterative and can be time-multiplexed at iteration boundaries, while accelerator utilization and distributed placement vary across workloads. Gavel’s overview connects throughput measurement, policy optimization, and round-level placement decisions.

  • DNN Training: DNN training processes minibatches iteratively, allowing throughput to be estimated across hundreds of iterations.Jobs commonly run for hours to days and may be distributed across many workers.
  • Gavel Overview: Figure 2 shows Gavel measuring job throughput by accelerator type, optimizing an allocation for an objective such as fairness, and approximating it through per-round placements.The scheduling mechanism accepts the policy allocation and realizes its proportions over time.
  • DNN Training: Schedulers can suspend and resume DNN jobs at iteration boundaries, checkpointing model parameters so progress is preserved during time multiplexing.This makes preemptive sharing of physical resources practical.
  • Space Sharing: Space sharing concurrently runs smaller models on one GPU through mechanisms such as NVIDIA MPS or CUDA streams to improve utilization.The optimization is useful because smaller models may not use the full computational capacity of modern GPUs.
  • Placement Sensitivity: Distributed models differ in scaling when workers are spread across servers, making placement a performance-sensitive scheduling choice.Existing schedulers use placement heuristics to keep some training jobs consolidated.

3 Overview of Gavel

Gavel first computes heterogeneity-aware allocations for jobs across accelerator types, then realizes them through preemptive round-based scheduling. Its optimization framework also incorporates space sharing, placement sensitivity, throughput estimates, and existing scheduling objectives.

  • Heterogeneity-Aware Policies: Gavel computes each job’s target fraction of time on different accelerator types using performance-aware allocation matrices.The matrices can represent homogeneous, heterogeneous, and optimized allocations.
  • Heterogeneity-Aware Policies: 60% of job 0’s time is allocated to V100 GPUs in the illustrative Xexample allocation.Figure 3 visualizes the cumulative accelerator time associated with this allocation.
  • Heterogeneity-Aware Policies: Gavel formulates scheduling objectives as optimization problems over allocation matrix X and effective job throughputs.Constraints enforce nonnegative allocations, per-job limits, and no worker oversubscription.
  • Space Sharing: Space-sharing allocations add rows for viable job combinations and throughput estimates for those combinations.Gavel limits considered combinations to at most two jobs because larger combinations rarely increase net throughput.
  • Placement Sensitivity: Placement-sensitive policies model distributed-job performance under consolidated and other task-placement settings.Observed throughput depends on task locations, model, and accelerator type.
  • Scheduling Mechanism: A preemptive round-based scheduler assigns jobs or combinations to accelerator types so received time fractions approach the computed allocation.Priorities are higher for job–accelerator pairs that have received less than their target fraction, and scheduling supports concurrent and distributed jobs.
  • Throughput Estimation: Gavel estimates concurrent-job throughputs by mapping new jobs to pre-profiled reference jobs, while individual-job throughput can be measured on the fly.The estimator supplies initial performance estimates for job combinations.
  • Scope: Gavel’s scope is resource sharing across users and jobs with heterogeneity-aware support for existing objectives, rather than introducing new policies or optimizations.Its reusable scheduling mechanism and narrow API support deployment with minimal code changes.

4 Scheduling Policies

Gavel formulates heterogeneity-aware versions of fairness, completion-time, cost, FIFO, and hierarchical scheduling policies as optimization problems over effective throughput. It also establishes policy properties, including sharing incentive, while identifying unsupported hierarchical combinations and trade-offs among fairness desiderata.

  • Max-Min Fairness: Vanilla LAS can be unfair on heterogeneous clusters because equal resource shares may produce unequal throughput reductions across jobs.A job assigned a K80 instead of a V100 may experience much lower performance despite receiving the same number of resources.
  • Max-Min Fairness: Gavel addresses heterogeneity by applying max-min fairness to weighted normalized effective throughputs, scaled against equal time-sharing allocations.The equal-share allocation provides the reference used to make effective throughputs comparable across jobs.
  • Max-Min Fairness: 10% higher throughput results from Gavel’s allocation compared with isolated allocation giving each of three users 1/n of every accelerator.The comparison uses a cluster containing one V100 and one K80.
  • Other Policies as Optimization Problems: Gavel expresses many policies through effective-throughput optimization, using linear programs for most, sequential linear programs for makespan, and linear-fractional formulations for cost.The framework covers policies such as makespan, shortest job first, finish-time fairness, FIFO, and cost-aware objectives.
  • Other Policies as Optimization Problems: Cost-adjusted objectives divide time-averaged effective throughput by time-averaged accelerator cost, while space sharing requires avoiding double-counting instance costs.Time SLOs can be added as constraints for jobs with completion deadlines.
  • Hierarchical Scheduling Policies: Hierarchical policies allocate entity shares proportionally to entity weights, then apply entity-specific policies such as fairness or FIFO to individual jobs.Gavel currently supports fairness at upper levels and fairness or FIFO at lower levels; extending this to other combinations remains future work.
  • Properties of Gavel’s Policies: All Gavel policies have sharing incentive, and max-min allocations with water filling are Pareto efficient.However, the paper leaves strategy-proof policies for future work because fair-sharing policies cannot simultaneously satisfy all three properties in the cited setting.

5 Scheduling Mechanism

Gavel realizes heterogeneity-aware allocations through round-based scheduling of jobs and job combinations, including distributed jobs and space sharing. A greedy mechanism selects feasible high-priority combinations, while later rounds correct occasional sub-optimal choices.

  • Allocation realization: Gavel schedules runnable jobs so their wall-clock fractions on accelerator classes approximate the computed optimal allocation Xopt.The mechanism supports jobs running on multiple accelerators and allocation recomputation events.
  • Round-based scheduling: Rounds assign work to all available workers for a configurable duration, limiting starvation and resource under-utilization for large jobs.Experiments use 6-minute rounds; each worker receives a micro-task during a round.
  • Priority updates: Each round prioritizes jobs whose accumulated time fractions need to move closer to Xopt on each accelerator type.High-priority jobs receive time on the relevant accelerator type.
  • Scheduling complexity: With distributed jobs and space sharing, exact selection becomes similar to a multiple-choice knapsack problem and is NP-hard.The restricted single-accelerator, no-space-sharing case can be solved exactly by selecting the highest-priority jobs.
  • Scheduling algorithm: Gavel greedily selects highest-priority combinations that fit the resource budget and removes conflicting or infeasible combinations.A combination that runs loses priority, while an omitted job gains priority in subsequent rounds, enabling recovery from occasional sub-optimal choices.
  • Placement: After selecting jobs for a round, Gavel places them in decreasing order of requested workers and prefers accelerators on the same server to reduce fragmentation.The mechanism is decoupled from policies, so the same scheduler can support multiple policies.

6 Implementation

Gavel combines a scheduler prototype, framework interface, and throughput estimator to support heterogeneity-aware scheduling and space sharing. Its estimator uses profiling and matrix completion to infer missing colocated-job performance.

  • Prototype: The prototype comprises approximately 8000 lines of Python, using cvxpy for policies and gRPC for scheduler-worker control messages.These components implement the scheduler and its communication layer.
  • Application interface: Gavel currently supports applications written in PyTorch through a narrow API and GavelIterator.Users provide checkpoint load and save functions, while the iterator synchronizes distributed iterations and round conclusions.
  • Application interface: GavelIterator renews leases near round completion and checkpoints jobs when the scheduler assigns another job to the worker.The user-supplied checkpoint methods need only call appropriate framework methods in the implementation.
  • Throughput estimation: For colocated jobs, Gavel combines profiling with matrix completion to reconstruct sparse throughput measurements and identify a similar reference job.The reference job’s measurements provide an initial estimate for missing performance combinations.

7 Evaluation

Across physical and simulated heterogeneous clusters, Gavel’s policies support higher load and improve scheduling objectives relative to heterogeneity-agnostic or ad-hoc baselines. The evaluation also examines scalability, allocation fidelity, and online throughput estimation.

  • Experiment setup: The evaluation uses physical and simulated clusters, static and continuous traces, and metrics tailored to fairness, FIFO, makespan, and cost policies.The physical cluster has 48 GPUs; the simulated cluster has 108 GPUs spanning V100, P100, and K80 types.
  • Physical cluster: Physical experiments improve target objectives by up to 1.4×, while physical and simulated metrics differ by less than 5%.The comparison covers fairness on continuous traces and makespan against Gandiva-style space sharing on static traces.
  • End-to-end simulation: Heterogeneity-aware policies support higher load and reduce average JCT by up to 3.5× for single-worker traces and 2.2× for multi-worker traces.Gavel essentially matches AlloX on average JCT at moderate load while supporting additional objectives, and principled packing improves average JCT by 2.2× over Gandiva-style packing.
  • Finish Time Fairness (FTF): The heterogeneity-aware FTF policy reduces average JCT by 3× and improves average FTF by 2.8× over its heterogeneity-agnostic counterpart.The comparison is performed on the simulated cluster and continuous-multiple trace.
  • Makespan: The heterogeneity-aware makespan policy reduces makespan by 2.5× versus FIFO and 1.4× versus Gandiva’s ad-hoc space sharing.With many jobs, space sharing reduces makespan by a further 8%.
  • FIFO: For FIFO, heterogeneity-aware scheduling reduces average JCT by up to 2.7× without space sharing and 3.8× with space sharing at high load.Space sharing is less effective for distributed jobs, reducing average JCT by 1.1× versus 1.4× for single-GPU traces.
  • Cost and SLOs: Cost minimization reduces total cost by roughly 1.4× versus throughput maximization but causes approximately 35% of jobs to violate SLOs.Adding SLOs eliminates violations at a cost reduction of 1.23× versus the baseline by placing tight-SLO A3C jobs on V100s.
  • Scaling: The hierarchical policy runs in under 10 minutes with 2048 active jobs without space sharing and with 512 jobs with space sharing.The single-level LAS policy is cheaper to compute.

8 Related Work

Prior schedulers address workload or resource heterogeneity but generally lack Gavel’s combination of accelerator-performance awareness, policy generality, and allocation realization. Gavel formulates policies as optimization problems and supports richer objectives such as multi-level fairness.

  • DNN training schedulers: Gandiva improves utilization through time and space sharing but lacks an explicit scheduling policy and randomly explores job combinations without using performance data in policy decisions.This contrasts with Gavel’s policy-driven treatment of isolated and colocated performance.
  • DNN training schedulers: Tiresias and Themis optimize fairness without incorporating jobs’ accelerator affinities, and their policy-coupled mechanisms hinder support for more sophisticated policies.The cited example is multi-level fairness.
  • DNN training schedulers: AlloX and Gandivafair consider worker and model heterogeneity but support only single policies: average JCT and max-min fairness, respectively.Gandivafair also lacks guarantees about the optimality of its final allocation.
  • Traditional cluster schedulers: Traditional schedulers support fixed heterogeneous resource requests but do not reason about diverse job performance across interchangeable accelerators.Mesos and YARN assume jobs declare required resource types and ratios rather than modeling heterogeneous accelerator performance.
  • Resource allocation: MIRA introduces effective throughput but does not formulate policies as optimization problems or address space sharing, placement sensitivity, and physical allocation realization.Gavel extends this direction across policy specification and execution concerns.
  • DNN training schedulers: Omega, Apollo, and Hydra model heterogeneity in task counts and durations, whereas Gavel addresses performance differences among interchangeable accelerator types.Gavel considers policies that allocate time fractions across accelerator types.
  • Dynamic performance estimation: Gavel uses profiling and matrix completion, following Quasar, to estimate colocated-job performance online in this accelerator setting.The work reports that Quasar’s techniques can be successfully applied here.

9 Conclusion

Gavel extends scheduling policies to optimize fairness, makespan, and cost under accelerator and workload heterogeneity. Its policies improve objectives on both physical and simulated clusters while supporting higher maximum load.

  • Gavel optimizes high-level metrics including fairness, makespan, and cost through heterogeneity-aware scheduling policies.
  • Gavel expresses existing policies as optimization problems and extends them to account for heterogeneity.
  • Gavel uses a decoupled round-based mechanism to realize the computed optimal allocation.
  • 3.5× average job completion time, 2.5× makespan, and 1.4× cost improvements are reported alongside higher maximum cluster load.

A Appendix

This appendix section describes practical solution methods for more complicated optimization formulations and presents additional results.

  • The appendix addresses how more complicated optimization problem formulations can be solved in practice.
  • The section also presents additional experimental results.
  • Its scope combines practical optimization methods with supplementary evaluation.

A.1 Policies requiring multi-step solutions

The appendix gives multi-step procedures for makespan and fairness computations, including bottleneck identification through a mixed-integer linear program and colocation measurements.

  • A.1 Policies requiring multi-step solutions: The makespan policy binary searches for the smallest M satisfying the allocation constraints.
  • A.1 Policies requiring multi-step solutions: Bottleneck jobs after a fairness iteration are identified by solving a mixed-integer linear program.
  • A.1 Policies requiring multi-step solutions: The binary variable z_m indicates whether job m’s throughput exceeds its previous throughput.
  • A.1 Policies requiring multi-step solutions: The conditional constraint on z_m is represented using two linear inequalities and a sufficiently large Y.
  • A.1 Policies requiring multi-step solutions: Figure 15 reports normalized throughput for pairs of concurrently colocated DNN models on a single P100 GPU.

A.2 Additional Results

Additional results compare heterogeneity-agnostic policies with heterogeneity-aware counterparts and illustrate colocation and hierarchical fairness behavior. Gavel supports higher load and reduces end objectives across the evaluated traces.

  • A.2 Additional Results: Figure 15 presents a heat map of colocated DNN-model performance on one NVIDIA P100 GPU.
  • A.2 Additional Results: Figures 16–20 compare vanilla heterogeneity-agnostic policies with heterogeneity-aware counterparts across single-worker and multi-worker traces.
  • A.2 Additional Results: Across the evaluated traces, Gavel’s heterogeneity-aware policies support higher average job input rates and reduce end objectives.
  • A.2 Additional Results: The hierarchical policy combines higher-level fairness with low-level FIFO, allocating colored-band widths according to entity weights.
  • A.2 Additional Results: Within each entity, effective job throughputs respect arrival order, while low-weight entities receive no resources under high load.
Loading 2008.09213v1…