Source-linked AI summary
Themis: Fair and Efficient GPU Cluster Scheduling
Kshiteej Mahajan, Arjun Balasubramanian, Arjun Singhvi, Shivaram Venkataraman, Aditya Akella, Amar Phanishayee, Shuchi Chawla
TL;DR
Shared GPU clusters must divide resources fairly among ML workloads, but long-running, gang-scheduled, placement-sensitive tasks make established allocation schemes a poor fit. THEMIS introduces finish-time fairness and a two-level auction-based scheduler, improving fairness and efficiency over state-of-the-art schedulers while retaining placement sensitivity.
Problem
The central problem is how to fairly divide GPUs among ML applications when long-running tasks and placement preferences make established fair-allocation schemes inadequate.
Method
THEMIS uses finish-time fairness and a two-level architecture in which ML applications bid on GPU allocations through auctions run by a central arbiter.
Results
THEMIS improves fairness and efficiency compared with state-of-the-art schedulers, with reported benefits increasing as placement sensitivity and cluster contention increase.
Takeaways & Limitations
THEMIS provides a scheduling framework designed to share GPU clusters fairly while accounting for ML placement preferences and long task durations.
Takeaways & Limitations
The auction relies on application-reported finish-time fairness metrics, creating a risk that applications may submit false information to improve allocation chances.
Abstract
from arXiv · showhide
Modern distributed machine learning (ML) training workloads benefit significantly from leveraging GPUs. However, significant contention ensues when multiple such workloads are run atop a shared cluster of GPUs. A key question is how to fairly apportion GPUs across workloads. We find that established cluster scheduling disciplines are a poor fit because of ML workloads' unique attributes: ML jobs have long-running tasks that need to be gang-scheduled, and their performance is sensitive to tasks' relative placement. We propose Themis, a new scheduling framework for ML training workloads. It's GPU allocation policy enforces that ML workloads complete in a finish-time fair manner, a new notion we introduce. To capture placement sensitivity and ensure efficiency, Themis uses a two-level scheduling architecture where ML workloads bid on available resources that are offered in an auction run by a central arbiter. Our auction design allocates GPUs to winning bids by trading off efficiency for fairness in the short term but ensuring finish-time fairness in the long term. Our evaluation on a production trace shows that Themis can improve fairness by more than 2.25X and is ~5% to 250% more cluster efficient in comparison to state-of-the-art schedulers.
1 Introduction
THEMIS addresses the difficulty of fairly sharing GPUs among ML applications whose long-running, gang-scheduled, placement-sensitive tasks make established schemes ineffective. It introduces finish-time fairness and a two-level auction-based scheduler that aims to combine long-term fairness with short-term efficiency.
- Motivation: Shared GPU clusters need a fair division of resources across ML applications to provide users with a sharing incentive.Without such an incentive, users may face long waits or purchase dedicated hardware.
- Why Existing Schemes Fall Short: Long-running gang-scheduled tasks and placement-sensitive communication make conventional fair allocation schemes ineffective for ML workloads.Existing schemes can violate sharing incentive, Pareto efficiency, and envy-freedom when they ignore these workload properties.
- Design Goal: THEMIS defines finish-time fairness as an app’s shared-cluster running time divided by its running time alone in a 1/N-sized cluster.Its goal is to minimize the maximum finish-time fairness across apps while efficiently using GPUs.
- Auction Scheduling: A round-by-round auction lets apps express placement preferences by bidding on subsets of available GPUs offered to apps farthest from fair treatment.Leases account for long-running tasks, and auction rounds begin when leases expire.
- Long-Term Behavior: Losing apps become more likely to win later because waiting worsens their finish-time fairness, enabling long-term fairness while preserving short-term placement sensitivity and efficiency.THEMIS also uses a two-level architecture that integrates a centralized inter-app scheduler with existing hyper-parameter tuning frameworks.
- Evaluation: On a large enterprise trace, THEMIS improved fairness by at least 2.25X and cluster efficiency by 5% to 250% over state-of-the-art schedulers.An event-driven simulation further found greater benefits as network-intensive apps and cluster contention increased.
2 Motivation
Production ML applications are heterogeneous and often long-running, with bursty GPU demand and many hyper-parameter exploration jobs. These characteristics, combined with high contention, motivate scheduling that allocates resources fairly while allowing applications to complete in a timely way.
- Preliminaries: An ML app is one or more related model-training jobs, potentially exploring hyper-parameters to identify a target model.Apps may contain a single job or many jobs submitted through a hyper-parameter tuning framework.
- Preliminaries: App finish time is when the best model and relevant hyper-parameters are identified, or when a single model reaches target accuracy or its iteration limit.Hyper-parameter tuning may terminate clearly sub-optimal jobs early.
- Trace: The analyzed production trace covers 85 ML training apps from a GPU cluster supporting over 5000 unique users.The study focuses on apps submitted using a hyper-parameter tuning framework.
- Resource Demand: GPU demand is bursty, with average demand of ~50 GPUs in the analyzed trace.This reflects substantial contention in the production GPU cluster.
- App Structure: Around ~90% of apps perform hyper-parameter exploration with as many as 100 jobs, while ~10% contain one job.The median hyper-parameter exploration app has 75 jobs.
- Duration: The median app consumes 11.5 GPU days and the median task consumes 3.75 GPU hours, with substantial variation in both durations.Many jobs and apps are more than 10X shorter or longer than these typical values.
- Scheduling Challenge: ML apps vary in resource usage, job count, and running time, making performance control difficult in a highly contended shared cluster.Their running times are much longer than typical big-data analytics jobs, which usually run for a few hours.
- Goal: The scheduling goal is to allocate GPUs fairly across diverse apps so that all apps can execute their work in a timely way.The paper identifies the need for a new fairness metric and scheduler architecture suited to ML workloads.
3 Finish-Time Fair Allocation
ML cluster fairness must account for long-running, gang-scheduled tasks and placement-sensitive performance, which make existing fair-sharing schemes inadequate. Themis addresses these issues with finish-time fairness and multi-round auctions that incorporate app placement preferences while preserving key fairness properties.
- Fair Sharing Concerns for ML Apps: ML workloads’ long tasks and placement preferences make established fair-sharing schemes ineffective for GPU clusters.Production measurements report a median task duration of roughly 3.75 hours, while placement can substantially change performance.
- Fair Sharing Concerns for ML Apps: Existing schemes such as DRF and LAS can violate sharing incentive, Pareto efficiency, and envy-freeness because they ignore placement preferences.The paper formally states these violations and illustrates them with allocations that equalize resource shares but produce inferior placements.
- Metric: Finish-Time Fairness: Finish-time fairness ρ compares an app’s shared-cluster finish time with its finish time when running alone on an exclusive 1/N-sized cluster.The shared finish time includes placement slowdown and queuing delays.
- Metric: Finish-Time Fairness: Themis lets apps report finish-time fairness estimates for alternative GPU allocations through a wider interface, enabling placement-aware allocation.Apps encode allocation preferences as bid tables that map GPU subsets to estimated ρ values.
- Mechanism: Partial Allocation Auctions: Themis uses auctions to incentivize truthful reporting and multi-round allocation to preserve Pareto efficiency, envy-freeness, and strategy proofness while maximizing sharing incentive.The one-shot partial allocation auction guarantees SP, PE, and EF but not SI; round-by-round auctions preserve those properties and maximize SI.
4 System Design
The design requirements account for finish-time fairness and auction-based resource allocation while integrating with hyper-parameter optimizers.
- THEMIS’s scheduler architecture is guided by a fairness metric and auction mechanism.
- The design includes an API between the scheduler and hyper-parameter optimizers.
- The section discusses how the architecture supports integration with hyper-parameter tuning systems.
4.1 Design Requirements
THEMIS separates resource visibility from allocation and integrates with existing hyper-parameter tuning systems through a new two-level scheduler architecture.
- THEMIS makes resources visible to multiple apps while allocating each resource exclusively to one app.This separation is central to the partial allocation mechanism.
- THEMIS integrates existing hyper-parameter optimization systems with minimal modifications to their app-schedulers.Examples include Hyperband and Hyperdrive.
- These requirements motivate a two-level semi-optimistic scheduler and supporting abstractions for hyper-parameter tuning systems.
4.2 THEMIS Scheduler Architecture
THEMIS uses a two-level semi-optimistic architecture to support multi-app resource visibility, exclusive allocation, and round-based auctions. A central ARBITER coordinates leases, bids, and allocations while app-level schedulers retain control over constituent jobs.
- Need for a new scheduling architecture: Pessimistic schedulers restrict resource visibility to one app, preventing resources from being visible to many apps while allocated to one.
- Need for a new scheduling architecture: Fully optimistic schedulers couple multi-app visibility with simultaneous allocation, complicating global finish-time fairness and conflict resolution.
- Need for a new scheduling architecture: Existing pessimistic and fully optimistic scheduler architectures do not support the visibility and allocation requirements of multi-round auctions.
- THEMIS Scheduler Architecture: THEMIS divides scheduling between multiple app-schedulers and a cross-app ARBITER containing the scheduling logic.The top-level app-schedulers are minimally modified to interact with the ARBITER.
- THEMIS Scheduler Architecture: Each GPU has a lease, and expired leases trigger an auction round for pooled available resources.The round proceeds through visibility and allocation phases.
- THEMIS Scheduler Architecture: THEMIS offers resources to multiple apps but allocates each resource exclusively, implementing semi-optimistic concurrency control.App agents forward winning allocations to app-schedulers, which assign resources among constituent jobs.
4.3 AGENT and AppScheduler Interaction
The AGENT computes finish-time fairness for possible GPU allocations and submits bids, while the app scheduler supplies job-phase information and updates estimates as execution progresses. The interaction supports single- and multi-job apps, including successive halving and performance-curve stopping.
- AppScheduler Interaction: The app-scheduler API exposes phase and job information, GPU allocations, and the number of phases to support successive-halving and performance-curve schedulers.The AGENT co-resides with the app and integrates with the hyperparameter optimizer through this interface.
- Single-Job ML Apps: Finish-time fairness ρ compares an app’s shared-cluster finish time with its estimated finish time in an independent 1/N_avg cluster.The shared finish-time includes queuing or starvation time and remaining execution under the allocation, while placement sensitivity is represented by S(G).
- Single-Job ML Apps: The AGENT computes ρ for possible GPU subsets using shared and ideal finish-time estimates, then produces a bid table for the auction.The shared finish-time accounts for elapsed time, remaining iterations, allocation-dependent iteration time, and placement slowdown; the ideal finish-time estimates execution in an independent cluster.
- Multi-Job ML Apps: For successive halving, the optimizer divides the workload into phases, and the app’s shared finish-time is the sum of the finish times across those phases.With n initial jobs, successive halving has log2n phases as jobs are periodically stopped and the survivors receive larger GPU allocations.
- End-to-end Example: In the four-job example, the optimizer uses three phases with 4, 2, and 1 jobs, while the app assumes a 16-GPU cluster, 8-GPU maximum demand, and no slowdown.The example jobs have serial iteration times of 80, 100, 100, and 120 seconds, and the total budget is 10,000 seconds of GPU time.
- Multi-Job ML Apps: When future phase survivors are unknown, the system estimates their phase time using the median per-iteration job and revises bids in later auction rounds when observed jobs differ.This preserves an operational bid before termination decisions are known while allowing estimates to reflect the selected jobs’ actual iteration times.
5 Implementation
Themis is implemented on YARN by extending Submarine to manage groups of ML jobs, an app scheduler, an AGENT, and a separate ARBITER. Runtime profiling supplies iteration, loss, and placement-sensitivity information for bidding and early stopping.
- System Implementation: Themis extends Apache Hadoop YARN and Submarine to submit and manage groups of ML training jobs for hyperparameter exploration apps.The Submarine Application Master runs the ML app scheduler, Hyperband, and the AGENT.
- System Implementation: A profiler parses TensorFlow logs to track iteration times and loss values, estimating placement sensitivity and supporting Hyperband’s early-stopping decisions.Iteration times are used to estimate S for different GPU placements, while loss values guide early stopping.
- System Implementation: The ARBITER runs as a separate YARN ResourceManager module, with gRPC-based interfaces connecting the scheduling components.The implementation separates cluster-level arbitration from the application-side scheduler and AGENT.
- Runtime Adaptation: Evaluation programs checkpoint model parameters to HDFS every few iterations so jobs can resume after runtime allocation changes.Each job resumes from its most recent checkpoint when its GPU allocation changes.
6 Evaluation
THEMIS improves finish-time fairness and cluster efficiency across testbed and simulator evaluations, especially as placement sensitivity and contention increase. Its design also remains effective under estimation errors and exposes a fairness–efficiency trade-off controlled by filtering and lease duration.
- Macrobenchmarks: THEMIS achieves better finish-time fairness and cluster efficiency than the evaluated state-of-the-art schedulers.In the testbed, its finish-time fairness distribution is narrower, indicating more equal sharing incentive across apps.
- Sensitivity analysis: f = 0.8 and a 10-minute lease provide maximum fairness while maintaining efficient cluster utilization.Increasing f improves fairness up to 0.8, while higher f reduces bidding opportunities and efficiency; shorter leases increase checkpointing.
- Macrobenchmarks: 2.2X, 2.25X, 1.75X, and 3.25X better maximum finish-time fairness than Gandiva, Tiresias, Optimus, and SLAQ, respectively.These comparisons are reported for the maximum ρ value across apps.
- Macrobenchmarks: ~4.8% better cluster efficiency than Gandiva and ~250% better than SLAQ.The improvement is attributed to auction-based placement-driven packing rather than greedy local decisions.
- Macrobenchmarks: THEMIS gives the best placement scores in workload 2, while placement-agnostic schedulers perform poorly.Gandiva comes closest, but its greedy local packing is less efficient.
- Contention and workload sensitivity: THEMIS is the only evaluated scheme that maintains sharing incentive under 2X and 4X contention.Its maximum ρ remains closest to 1 across heterogeneous compute- and network-intensive mixes.
- Contention and workload sensitivity: ~8.1% better efficiency than Gandiva for workloads consisting entirely of network-intensive apps.As network-intensive workload share increases, THEMIS uses less aggregate GPU time for the same workload.
- Robustness: A 20% estimation error changes maximum finish-time fairness by only 10.76%.The error experiment samples random percentage errors in iteration-count and slowdown estimates.
7 Related Work
Prior cluster schedulers provide useful foundations but were designed primarily for batch analytics or instantaneous resource fairness. THEMIS instead targets long-term fairness for ML workloads with recurring synchronization and placement preferences.
- ML cluster schedulers: SLAQ, Gandiva, Tiresias, and Optimus are recent systems targeting ML cluster scheduling with different objectives.THEMIS compares against these schedulers in its evaluation.
- Foundations: THEMIS builds on resource offers, two-level schedulers, sharing incentive, and resource-aware packing from prior work.Its focus differs by using finish-time fairness as a long-term fairness metric.
- Distinction from prior work: Earlier schemes focus on batch analytics and instantaneous resource fairness, which do not account for long tasks and placement sensitivity.ML synchronization barriers occur every iteration rather than only occasionally.
8 Conclusion
The paper presents THEMIS as a fair scheduling framework tailored to long-running, placement-sensitive ML training workloads. Its finish-time fairness objective and auction-based architecture improve fairness and efficiency relative to state-of-the-art schedulers.
- Conclusion: THEMIS addresses the limitations of existing fair allocation schemes for long-running ML tasks with placement preferences.The paper introduces finish-time fairness as a long-term fairness objective.
- Conclusion: THEMIS uses a two-level semi-optimistic architecture in which ML apps bid on resources offered through an auction.The experiments report improvements in both fairness and efficiency compared with state-of-the-art schedulers.
A Appendix
The appendix establishes formal properties of THEMIS and related auction mechanisms under stated valuation and allocation assumptions. It explains how multi-round filtering and leftover allocation address fairness, strategy-proofness, efficiency, and work conservation.
- Fairness properties: DRF and LAS can violate sharing incentive, envy-freedom, and Pareto efficiency when allocations ignore placement preferences.The appendix illustrates these violations using VGG16, VGG19, and Inceptionv3 allocations.
- Auction assumptions: THEMIS assumes homogeneous valuation functions when proving auction guarantees for strategy-proofness, Pareto efficiency, and envy-freedom.Homogeneity follows when increasing GPUs on the same machine set proportionally reduces shared running time while slowdown remains unchanged.
- Auction properties: Partial allocation guarantees Pareto efficiency and envy-freedom, but hidden payments can violate sharing incentive and work conservation.THEMIS adds leftover allocation to remain work-conserving.
- Strategy-proofness: Multi-round auctions ensure strategy-proof reporting of finish-time-fairness estimates through cached estimates used by the AGENT.This applies both during visibility and when apps receive leftover allocations.
A.1 Workload Details
The evaluation uses two traces with different workload characteristics, including a scaled-down DNN-training trace and a synthetic successive-halving workload. The traces contain computer vision, natural language processing, and speech models, with their workload distributions summarized in Figure 17 and model details in Table 4.
- The evaluation uses two traces with different workload characteristics in both the simulator and testbed.
- Workload 1 is a publicly available DNN-training trace scaled to a two-week snapshot and a subset of Hyperdrive hyper-parameter exploration jobs.
- Figure 17 shows the distributions of tasks per job and jobs per application for the two workloads.
- Workload 2 reuses Workload 1's application arrival times and generates jobs using the successive-halving pattern characteristic of Hyperband.
- The traces comprise computer vision, natural language processing, and speech models, comprising 10%, 60%, and 30%, respectively.
- Table 4 summarizes the models used in the evaluation trace.