PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Job Scheduling in Distributed Machine Learning Clusters

Yixin Bao, Yanghua Peng, Chuan Wu, Zongpeng Li

arXiv:1801.00936v1cs.DC

TL;DR

Shared ML clusters need to schedule resource-intensive jobs while balancing resource use and timely completion. OASiS makes online admission and dynamic worker and parameter-server allocation decisions to maximize job utility. The paper reports polynomial-time computation, a competitive-ratio guarantee, and outperformance of commonly adopted schedulers in its evaluations.

  • Problem

    Resource-intensive ML jobs must be scheduled in shared clusters to use server resources effectively and complete training promptly.

    Source: §I · pp. 1–2

  • Method

    OASiS schedules arriving jobs by adjusting their worker and parameter-server deployments over time and selecting schedules for long-term utility maximization.

    Source: §I · p. 2

  • Results

    OASiS has polynomial running time and a competitive-ratio guarantee, and evaluations report outperformance of commonly adopted schedulers, especially under resource scarcity.

    Source: §I · p. 2, D. Theoretical Analysis · p. 8, §VI · p. 9

  • Takeaways & Limitations

    Trace-driven simulation and testbed experiments, including a Kubernetes scheduler module for MXNet, demonstrate OASiS’s practical effectiveness in the evaluated settings.

    Source: §I · p. 2

Abstract

from arXiv · show

Nowadays large-scale distributed machine learning systems have been deployed to support various analytics and intelligence services in IT firms. To train a large dataset and derive the prediction/inference model, e.g., a deep neural network, multiple workers are run in parallel to train partitions of the input dataset, and update shared model parameters. In a shared cluster handling multiple training jobs, a fundamental issue is how to efficiently schedule jobs and set the number of concurrent workers to run for each job, such that server resources are maximally utilized and model training can be completed in time. Targeting a distributed machine learning system using the parameter server framework, we design an online algorithm for scheduling the arriving jobs and deciding the adjusted numbers of concurrent workers and parameter servers for each job over its course, to maximize overall utility of all jobs, contingent on their completion times. Our online algorithm design utilizes a primal-dual framework coupled with efficient dual subroutines, achieving good long-term performance guarantees with polynomial time complexity. Practical effectiveness of the online algorithm is evaluated using trace-driven simulation and testbed experiments, which demonstrate its outperformance as compared to commonly adopted scheduling algorithms in today's cloud systems.

I. INTRODUCTION

Distributed ML jobs consume substantial resources, and cluster operators must schedule them to use servers effectively and finish training promptly. OASiS addresses this by admitting jobs and dynamically adjusting workers and parameter servers to maximize long-term job utility.

I. INTRODUCTION

  • Training is resource intensive, and operators must allocate expensive server resources while completing jobs promptly.The introduction gives a 23.4-hour example for training GoogLeNet on a Titan supercomputer with 32 NVIDIA K20 GPUs.Source: §I · pp. 1–2

A. Distributed Machine Learning Systems

  • The paper focuses on data-parallel training using parameter servers, where workers exchange parameter updates through server-managed model parameters.Worker and parameter-server counts affect a job’s training speed and completion time.Source: §I · p. 1

B. Job Scheduling and Resource Allocation in Cloud Systems

  • Existing cluster schedulers commonly use FIFO, fairness, or priority-based policies, and the paper reports that they keep worker counts fixed during training.Related approaches also leave online multi-job resource sharing or changing per-job allocations unaddressed.Source: §I · pp. 1–2, B. Job Scheduling and Resource… · p. 2

I. INTRODUCTION

  • OASiS admits arriving jobs and schedules changing numbers of workers and parameter servers over time to maximize long-term utility.Its schedules account for projected resource availability and job utility contingent on completion time.Source: §I · p. 2
  • The online primal-dual design updates resource prices as allocations change and uses dual subroutines to compute schedules through dynamic programming.The schedule optimization is a multi-timeslot, multidimensional resource-packing problem.Source: §I · p. 2
  • Trace-driven simulation and testbed experiments report that OASiS outperforms commonly adopted schedulers, especially when resources are scarce.The evaluation implements OASiS as a Kubernetes scheduler module for MXNet.Source: §I · p. 2

A. Distributed Machine Learning System

  • The modeled cluster separates worker and parameter-server machines, with resources including GPU, CPU, memory, storage, and network bandwidth.The paper assumes separate machine pools because workers typically use GPU servers while parameter servers use high-bandwidth machines.Source: A. Distributed Machine Learning System · pp. 2–3

B. Asynchronous Training Workflow

The paper models asynchronous parameter-server training and formulates online admission and resource-allocation decisions for jobs with completion-time-dependent utility. Its scheduler must allocate enough worker time to complete each job while respecting cluster and job constraints.

B. Asynchronous Training Workflow

  • Workers process data chunks in mini-batches, send gradients to parameter servers, receive updated parameters, and continue through their assigned chunks.A job ends after its specified number of epochs over the input chunks.Source: B. Asynchronous Training Workflow · pp. 3–4
  • Asynchronous training lets each parameter server update upon receiving a worker’s gradients, unlike synchronous training, which waits for gradients from all workers.The paper states that asynchronous training improves bandwidth utilization and potentially speeds convergence; it also says accuracy is unaffected by changing worker populations, unlike synchronous training.Source: B. Asynchronous Training Workflow · p. 3

C. Offline Optimization Problem

  • The offline formulation maximizes total job utility, which is non-increasing with completion time, by choosing admission and per-time-slot worker and parameter-server counts.The model assumes jobs are internal so the algorithm can specify their worker and parameter-server counts.Source: C. Offline Optimization Problem · p. 4
  • Feasible schedules must provide enough worker time for all training epochs while respecting server capacities and job-level worker-to-parameter-server bandwidth requirements.The formulation sets deployment to zero before job arrival and bounds concurrent workers by the number of data chunks.Source: C. Offline Optimization Problem · p. 4
  • The paper proposes solving the integer, non-conventional optimization problem online without assuming knowledge of future job arrivals.Source: C. Offline Optimization Problem · p. 4

IV. ONLINE ALGORITHM

OASiS converts the scheduling problem into a job-schedule selection formulation and uses resource prices to guide admission and allocation. For each arriving job, it evaluates a best schedule and admits the job only when that schedule has positive payoff.

A. Problem Reformulation

  • The reformulation represents each feasible job schedule as a choice and assigns a binary decision indicating whether that schedule is selected.The schedule-selection formulation may have exponentially many variables, and the paper relates it to the original problem through equivalent feasible solutions and objective values.Source: A. Problem Reformulation · p. 5

B. Online Algorithm

  • OASiS computes a best schedule and payoff for each arriving job, admitting it only when the payoff is positive.The payoff compares job utility with the resource cost of its schedule.Source: B. Online Algorithm · p. 5, A. Problem Reformulation · p. 5
  • Efficient dual subroutines seek the best worker and parameter-server schedule, avoiding direct enumeration of the exponentially large feasible-schedule set.The paper identifies polynomial-time schedule computation as a subproblem of the online algorithm.Source: B. Online Algorithm · p. 5
  • The algorithm maintains dual resource prices and updates them as jobs are admitted or completed, using the prices to guide admission and allocation.The price inputs are estimated from past experience because their exact values are not known before all jobs arrive.Source: B. Online Algorithm · p. 6

C. Subroutine for Finding Best Job Schedule

The schedule subroutine compares candidate completion times, distributes each job’s training workload across time slots with dynamic programming, and chooses resource deployments using a greedy procedure. It accounts for deployment cost and feasibility at each slot.

C. Subroutine for Finding Best Job Schedule

  • The subroutine compares payoffs across completion times and selects the schedule with the highest payoff.The paper states that the dynamic-programming and greedy procedures efficiently and optimally solve the schedule problem.Source: C. Subroutine for Finding Best Job… · p. 7
  • For each candidate completion time, dynamic programming divides the total training workload across time slots and stores subproblem results to avoid recomputation.The recurrence compares the cost of work completed in the current slot with the cost of the remaining workload in earlier slots.Source: C. Subroutine for Finding Best Job… · p. 7
  • For a time slot, the procedure deploys workers on servers in non-decreasing resource-price order, then deploys parameter servers similarly subject to capacity and bandwidth constraints.A slot is infeasible if it cannot provide enough workers or parameter servers to meet the workload requirements.Source: C. Subroutine for Finding Best Job… · p. 7

D. Theoretical Analysis

The theoretical analysis establishes that OASiS uses an optimal scheduling subroutine, produces feasible solutions, and runs in polynomial time. It also gives a 2α-competitive guarantee whose ratio worsens with greater utility spread, timespan, or total resources.

D. Theoretical Analysis

  • The scheduling subroutine produces an optimal solution, with COST computing an optimal worker and parameter-server deployment for each time slot.The theorem identifies COST as computing an optimal solution of problem (32).Source: D. Theoretical Analysis · pp. 7–8
  • OASiS computes a feasible solution to the stated problems.The correctness theorem covers problems (1), (14), and (19).Source: D. Theoretical Analysis · p. 8
  • OASiS decides job admission and scheduling in polynomial time upon each job's arrival.The theorem states a polynomial-time bound, though the supplied complexity expression is incomplete.Source: D. Theoretical Analysis · p. 8
  • OASiS is 2α-competitive, and the stated ratio worsens as utility spread, timespan, or total resources increase.The discussion says a wrong admission decision can widen the gap from the offline optimum.Source: D. Theoretical Analysis · p. 8

V. PERFORMANCE EVALUATION

OASiS is evaluated through simulation studies and testbed experiments using a prototype system implementation.

V. PERFORMANCE EVALUATION

  • The evaluation includes simulation studies of OASiS.The passage introduces simulation as one of the evaluation modes.Source: §V · p. 8
  • The evaluation also includes testbed experiments.The experiments are based on the prototype system implementation.Source: §V · p. 8
  • The simulation studies and testbed experiments use a prototype system implementation.Source: §V · p. 8

A. Simulation Studies

OASiS outperforms commonly used schedulers in simulation and prototype experiments, with stronger advantages under scarce resources. The evaluations also examine completion timeliness, performance ratio, and sensitivity to inaccurate resource-utility estimates.

A. Simulation Studies

  • OASiS achieves the highest total utility among the compared schemes, especially as the number of jobs rises and resources become scarcer.The simulation comparison uses T = 300.Source: A. Simulation Studies · p. 8, Figure 3 · p. 8
  • For 100 time-sensitive and 100 time-critical jobs over T = 100, OASiS completion times are closest to targets and have the smallest variance.Among the other schemes, only RRH accounts for job utility and completion time, but its resource utilization is less efficient.Source: A. Simulation Studies · pp. 8–9, Figure 4 · p. 8
  • The simulated performance ratio is around 1.1 to 1.5, with no clear trend as server counts and maximum per-unit-resource utilities increase.The ratio is offline optimal total utility divided by OASiS total utility; the offline comparison is limited to 10 jobs because solving the optimum is time-consuming.Source: Figure 5 · p. 8, A. Simulation Studies · p. 9
  • Under scarce resources, underestimating resource-utility values yields higher total utility than overestimating them.The authors attribute this to avoiding abrupt price rises that could filter out jobs that should be accepted.Source: Figure 6 · p. 8, A. Simulation Studies · p. 9

B. Testbed Experiments

  • The testbed uses an MXNet-on-Kubernetes prototype with dynamically adjustable worker and parameter-server counts, deployed across nine servers.Its experiments run six model types on ImageNet and compare total utility and completion-time differences with the simulations.Source: B. Testbed Experiments · p. 9, Figure 7 · p. 9, Figure 8 · p. 9
  • OASiS runs in under one second to schedule each job for 100 time slots and 80 worker/parameter servers, while the 10-job offline optimum takes two days.The offline-optimum computation is reported as a comparison of computational cost.Source: B. Testbed Experiments · p. 9

VI. CONCLUSION

APPENDIX A THE PROPERTY OF PRICE FUNCTIONS (22)

The appendix characterizes scheduling decisions at resource-use boundaries: jobs with nonpositive payoff are rejected, while available capacity can permit acceptance.

APPENDIX A THE PROPERTY OF PRICE FUNCTIONS (22)

  • When no resources are in use across the servers at a time, any job can be scheduled under the stated condition.A job with a schedule that uses no resources across its relevant times and servers must be accepted.Source: Appendix A · p. 10
  • When a job's payoff is nonpositive, OASiS rejects it; a job cannot be scheduled when any resource is exhausted.The appendix states these conditions as properties of the price functions.Source: Appendix A · p. 11
  • Resource exhaustion on a server is treated as a boundary that prevents scheduling at that time.The appendix describes exhaustion for worker-host resources and states the no-scheduling rule when a resource is used up.Source: Appendix A · pp. 10–11

APPENDIX B PROOF OF THEOREM 1

The proof establishes that the greedy cost calculation and dynamic program find minimum-cost workload schedules, then shows that enumerating deadlines lets Algorithm 2 recover an optimal schedule.

A. Optimality of Function COST t and DP COST

  • The greedy deployment minimizes the cost of fulfilling workload d for a job at time t, and the dynamic program extends this minimum across [ai, t].Its recurrence splits workload d between the current time and the preceding interval.Source: A. Optimality of Function COST t and… · p. 11
  • Induction on time establishes that cost(t, d) is the minimum cost to fulfill workload d at time t.The recurrence takes the minimum over possible workload splits d′.Source: A. Optimality of Function COST t and… · p. 11

B. Optimality of Alg. 2

  • Enumerating deadlines from ai to T and retaining the best-payoff schedule produces the optimal solution of (27).The enumerated deadline is distinct from the job’s completion slot; non-increasing utility means a later deadline with the same schedule cannot displace the optimum.Source: B. Optimality of Alg. 2 · pp. 11–12

APPENDIX C PROOF OF THEOREM 2

The proof verifies that the generated schedule and dual variables are feasible. It also bounds the time needed to decide each arriving job’s schedule by a polynomial expression.

APPENDIX C PROOF OF THEOREM 2

  • Algorithm 2’s schedule satisfies the listed primal constraints, while Algorithm 1’s choice of μ_i ensures dual feasibility.The parameter-server assignment rule ensures constraint (7), and producing one schedule per job ensures constraint (17).Source: Appendix C · p. 12

APPENDIX D PROOF OF THEOREM 3

  • For each job i, the scheduling decision takes O(T(H log H + K log K) + TNiEi(H + K) + TNi²Ei² + TKV + THV) time, with server sorting performed once per time slot.Source: Appendix D · p. 12
  • Sorting servers by cost per worker or parameter server takes O(H log H) and O(K log K), respectively, per time slot before saved orders are reused.Deployment selection then loops over all servers.Source: Appendix D · p. 12

A. Preliminaries

The analysis relates resource-allocation costs to changes in dual resource prices and gives a conditional 2α-competitive guarantee for total job utility.

A. Preliminaries

  • 2α-competitive total job utility follows when each primal objective increment is at least 1/α of the dual increment and the stated initial-value conditions hold.The conditions are P0 = 0 and D0 ≤ 1/2OPT.Source: A. Preliminaries · p. 12
  • The allocation-cost relationship bounds each time-slot scheduling cost by increases in the corresponding dual resource-price terms.The price-function update is stated to ensure this relationship.Source: A. Preliminaries · p. 12
  • The price functions defined in (22) satisfy the differential allocation-cost relationship for the stated L1 and L2 parameters.The analysis defines α using the maximum of the resource-specific bounds.Source: A. Preliminaries · p. 13

B. Proof of Theorem 4

The proof uses a small-resource-demand assumption to derive the allocation-cost relationship and bounds OPT using the minimum job utility, assuming the offline optimum accepts a job.

B. Proof of Theorem 4

  • The differential allocation-cost relationship implies the allocation-cost relationship when each job’s resource demand is small relative to server capacity.The proof uses α = max_r(1, ln U_r/L1, ln U_r/L2).Source: B. Proof of Theorem 4 · p. 13
  • The proof identifies minimum overall worker and parameter-server resource consumption for each job using the stated lower bounds.The worker and parameter-server bounds are given separately.Source: B. Proof of Theorem 4 · p. 13
  • The proof bounds OPT below by the minimum achievable job utility, assuming the offline optimum accepts at least one job.It selects the job-schedule pair with minimum fi(til − ai).Source: B. Proof of Theorem 4 · p. 14

Related papers

Loading 1801.00936v1…