# On Scheduling Ring-All-Reduce Learning Jobs in Multi-Tenant GPU Clusters
with Communication Contention

Menglu Yu,1 Bo Ji,2 Hridesh Rajan,1 and Jia Liu3,1 1Department of Computer
Science, Iowa State University2Department of Computer Science, Virginia
Tech3Department of Electrical and Computer Engineering, The Ohio State
University

(2022)

###### Abstract.

Powered by advances in deep learning (DL) techniques, machine learning and
artificial intelligence have achieved astonishing successes. However, the
rapidly growing needs for DL also led to communication- and resource-intensive
distributed training jobs for large-scale DL training, which are typically
deployed over GPU clusters. To sustain the ever-increasing demand for DL
training, the so-called “ring-all-reduce” (RAR) technologies have recently
emerged as a favorable computing architecture to efficiently process network
communication and computation load in GPU clusters. The most salient feature
of RAR is that it removes the need for dedicated parameter servers, thus
alleviating the potential communication bottleneck. However, when multiple
RAR-based DL training jobs are deployed over GPU clusters, communication
bottlenecks could still occur due to contentions between DL training jobs. So
far, there remains a lack of theoretical understanding on how to design
contention-aware resource scheduling algorithms for RAR-based DL training
jobs, which motivates us to fill this gap in this work. Our main contributions
are three-fold: i) We develop a new analytical model that characterizes both
communication overhead related to the worker distribution of the job and
communication contention related to the co-location of different jobs; ii)
Based on the proposed analytical model, we formulate the problem as a non-
convex integer program to minimize the makespan of all RAR-based DL training
jobs. To address the unique structure in this problem that is not amenable for
optimization algorithm design, we reformulate the problem into an integer
linear program that enables provable approximation algorithm design called
SJF-BCO (Smallest Job First with Balanced Contention and Overhead); and iii)
We conduct extensive experiments to show the superiority of SJF-BCO over
existing schedulers. Collectively, our results contribute to the state-of-the-
art of distributed GPU system optimization and algorithm design.

††copyright: acmcopyright††journalyear: 2022††copyright:
acmcopyright††conference: The Twenty-third International Symposium on Theory,
Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile
Computing; October 17–20, 2022; Seoul, Republic of Korea††booktitle: The
Twenty-third International Symposium on Theory, Algorithmic Foundations, and
Protocol Design for Mobile Networks and Mobile Computing (MobiHoc ’22),
October 17–20, 2022, Seoul, Republic of Korea††price: 15.00††doi:
10.1145/3492866.3549716††isbn: 978-1-4503-9165-8/22/10††ccs: Computing
methodologies Distributed algorithms††ccs: Networks Network performance
analysis

##  1\. Introduction

Background and Motivation: In recent years, the rise of deep learning has
driven an ever-increasing need for large-scale distributed training in GPU
clusters, which leverages massive parallelism to speed up the training
processes. This has been evidenced by the popularity of several prevailing
distributed deep learning (DDL) frameworks (e.g., TensorFlow (TensorFlow, )
and PyTorch (Paszke19:PyTorch, )). In these DDL frameworks, the traditional
and most widely adopted computing-networking structure is based on the sever-
worker (SW) architecture, where DDL training jobs are decomposed into and
executed in parallel by a set of workers under the coordination of a parameter
server. However, as the number of workers increases, the SW architecture
suffers from serious scalability limitations since the server acts as a
communication bottleneck and a single-point-of-failure. To address the
scalability limitations of the SW architecture, the ring-all-reduce (RAR)
(Patarasuk09:Ring-AllReduce, ) architecture has attracted increasing attention
in recent years. The key idea of RAR is that, by forming a ring and working
collaboratively, the workers can update the learning model parameters without
needing any parameter server, thus removing the communication bottleneck and
alleviating the single point of failure. Moreover, it can be shown that the
RAR architecture enjoys the highly desirable “bandwidth optimality” in the
sense that, as the number of workers increases, the amount of information
exchanged in the network is asymptotically independent of the number of
workers (see Section 3 for details).

However, despite all these salient features, the performance of deploying RAR-
based training jobs in multi-tenant GPU clusters remains far from being
satisfactory in practice (Wang20:contention, ). The fundamental reason is that
the bandwidth optimality of RAR architecture only happens when there is only a
single training job in the system (i.e., a contention-free environment). In a
multi-tenant GPU cluster, however, such an ideal contention-free condition is
rarely satisfied. As a result, significant communication bottleneck links
could occur when deploying RAR-based training jobs in the system. For example,
researchers in (Wang20:contention, ) have found that on a cluster of four-GPU
servers connected by 10 Gbps Ethernet, when only one RAR training job is
executed with four GPUs in the cluster, the job completion time is 295
seconds. In comparison, when four jobs of the same type are executed
simultaneously with each job still using four GPUs but scheduled across GPU
servers, each job’s completion time dramatically increases to 675 seconds due
to the extensive communication contention. These empirical performance results
of RAR indicate that developing efficient and effective scheduling for RAR-
based DDL training jobs is well warranted to mitigate contention-induced
communication bottlenecks. However, in the literature so far, there remains a
lack of theoretical understanding on how to design contention-aware resource
scheduling algorithms for RAR-based DDL training jobs. In light of the rapidly
growing importance of RAR-based DDL deployment, our goal in this paper is to
fill this gap and develop contention-aware scheduling algorithms for RAR-based
training jobs in multi-tenant GPU clusters.

Technical Challenges: We note, however, that due to a number of technical
difficulties, developing contention-aware scheduling algorithms for RAR-based
DDL jobs in multi-tenant GPU clusters is highly challenging. _First and
foremost_ , just as any network optimization problems that deal with
contentions and interferences, the completion time of an RAR-based training
job depends not only on its resource allocation decisions (i.e., the number of
ring-forming workers and their locality), but also on the number of concurrent
RAR-based DDL jobs that (partially or completely) share the communication
links of this job. The complex communication coupling between concurrent RAR-
based training jobs renders it intractable to compute the per-iteration
execution time of an RAR-based DDL job in closed-form. _Second_ , there exists
a fundamental trade-off in terms of job locality. On one hand, co-locating all
workers of an RAR-based DDL job on the same server enjoys a faster intra-
server communication speed, but could lead to resource fragmentation. On the
other hand, spreading the ring of an RAR job over multiple servers could also
result in more contentions of communication links and overhead in establishing
connections between servers. _Last but not least_ , due to the resource
constraints of each server and the iterative nature of DDL training workload,
the resource allocation decision for each RAR-based training job is subject to
a mix of packing and covering types of constraints, both of which are known to
be NP-hard.

Our Contributions: In this paper, we overcome the above challenges and design
a suite of scheduling algorithmic techniques for efficient RAR-based DDL
training in multi-tenant GPU clusters with theoretical makespan performance
guarantees. The key idea of our algorithmic design is to transfer the
structural complexity of the intractable per-iteration running evaluation in
the original scheduling problem to the dimensional complexity of an equivalent
reformulated problem, which has a much cleaner integer linear program
structure to work with. Our main results and technical contributions are
summarized as follows:

  * •

We first propose a new analytical framework for RAR-based DDL training
resource allocation and scheduling that characterizes both communication
contention and overhead under the RAR architecture in a multi-tenant GPU
cluster. This analytical modeling serves as the foundation to enable us to
formulate the scheduling optimization framework to minimize the makespan of
all RAR-based training jobs.

  * •

As mentioned earlier, due to the complex resource contentions and couplings
between RAR-based DDL jobs, it is intractable to determine the closed-form
expression for the per-iteration execution time for each DDL job. To address
this challenge, we further reformulate the original problem into an equivalent
integer problem, which has a cleaner problem structure. Doing so allows us to
convert the structural complexity of the original problem to the exponential
dimensionality complexity in the reformulated problem, which is more amenable
for low-complexity search-based optimization algorithm design.

  * •

Based on the above problem reformulation, we propose an efficient scheduling
algorithm called SJF-BCO (smallest job first with balanced contention and
overhead) with theoretical approximation ratio guarantee. We conduct extensive
experiments to verify the performance of our proposed SJF-BCO algorithm and
compare with existing scheduling policies to show the superiority of SJF-BCO
over these baselines.

Collectively, our results contribute to a comprehensive and fundamental
understanding of RAR-based DDL resource scheduling optimization. The roadmap
of the rest of the paper is as follows. In Section 2, we review the related
literature. Section 3 present preliminaries to familiar readers with the
necessary background. Section 4 introduces the system model and problem
formulation. Section 5 demonstrates our algorithms and Section 6 provides
their performance analysis. Section 7 presents numerical results and Section 8
concludes this paper.

##  2\. Related Work

As mentioned in Section 1, DDL training job scheduling algorithms have
received growing interest recently. Research in this area aims to schedule DDL
jobs and manage computing resources efficiently in multi-tenant GPU computing
clusters. Early attempts in this field were mostly heuristic approaches based
on empirical observations and models to conduct the resource scheduling (e.g.,
(Gu19:Tiresias, ; Mahajan20:Themis, ; Mei17:energy, ; Chau17:energy, )). For
example, Gandiva (Xiao18:Gandiva, ) considered GPU time-slicing and job
scheduling by predicting DDL training jobs characteristics. Optimus
(Peng18:Optimus, ) leveraged performance models through online-fitting to
guide the job scheduling aiming to minimize training completion time. Rather
than using prediction models, another line of research is to take advantage of
the model-less data-riven learning methods for DDL job scheduling (e.g.,
(Bao19:Harmony, ; Hu19:Spear, ; Wang20:Metis, )). For instance, Harmony
(Bao19:Harmony, ), a deep-reinforcement-learning-based scheduler considered
minimizing the job completion time. Hu. et al. (Hu19:Spear, ) designed a new
scheduling framework called Spear to minimize the makespan of jobs by
leveraging the deep reinforcement learning techniques. However, these works do
not provide theoretical performance guarantee. Also, none of these works
considered RAR-based DDL job scheduling.

The most related work to this paper is GADGET (Yu22:GAGET, ), which
characterized RAR-based DDL job scheduling based on the assumption that the
bandwidth of each job is reserved. As a result, there is no need to consider
communication contention in (Yu22:GAGET, ). We note that a limitation of the
reserved bandwidth assumption is that it could lead to resource under-
utilization. In contrast, this paper considers communication contention to
avoid this limitation. This, however, renders the scheduling problem far more
challenging. Lastly, Wang et al. (Wang20:contention, ) also considered
contention under various all-reduce architectures, including RAR. However,
they also relied on a system-dependent online-fitting model to predict the
execution time and did not explicitly formulate any scheduling optimization
problem. Their solution was based on heuristics without theoretical
performance guarantee. In contrast, we develop an analytical model to
facilitate the job scheduling as a rigorous optimization problem, which in
turn entails approximation algorithm design with theoretical performance
guarantee.

##  3\. Ring-All-Reduce (RAR)-Based Distributed Learning: A Primer

In this section, we provide a quick overview on the RAR-based distributed
learning to familiarize readers with necessary background and fix the
terminologies that are useful in the rest of the paper.

Figure 1. A three-worker illustrative example of the ring-all-reduce (RAR)
process.

1) SGD-Based Distributed Learning: The training of many ML problems is
typically in the form of an empirical risk minimization (ERM) problem:
$\min_{\mathbf{w}\in\mathbb{R}^{d}}\bar{L}(\mathbf{w})\triangleq\frac{1}{P}\sum_{i=1}^{P}L(\mathbf{w},\delta_{i})$,
where $\mathbf{w}$ contains the model parameters to be learned,
$L(\mathbf{w},\delta_{i})$ is a loss function, and $P$ is the total number of
samples. Due to the high-dimensionality and the large dataset size of many ERM
problems (e.g., in deep learning), the stochastic gradient descent (SGD)
method has become the most widely adopted method. The SGD method can be
written as the following iterative process:
$\mathbf{w}_{k+1}=\mathbf{w}_{k}-(\eta_{k}/Q)\sum_{i\in\mathcal{Q}_{k}}\mathbf{g}_{k}^{i}$,
where $\eta_{k}$ denotes the learning rate in the $k$-th iteration,
$\mathcal{Q}_{k}$ represents the mini-batch in the $k$-th iteration with
$|\mathcal{Q}_{k}|=Q$, and $\mathbf{g}_{k}^{i}$ is a stochastic gradient based
on a random sample $\delta_{i}\in\mathcal{Q}_{k}$. The finite-sum and mini-
batch structure of SGD naturally lends itself to a distributed implementation
in a $Q$-worker DDL system coordinated by a parameter server as follows:
First, the dataset is partitioned by $Q$ workers. In each iteration $k$, each
worker retrieves the current model parameters from the server and randomly
draws a sample from its local dataset, and then computes a stochastic gradient
(e.g., using the backpropagation method). Then, all workers send their
gradients to the server to be aggregated.

2) The Ring-All-Reduce (RAR) Architecture: It can be seen from the above
discussions that SGD-based distributed learning naturally implies a server-
worker (SW) architecture. However, as mentioned in Section 1, the SW
architecture suffers from scalability limitations as the number of workers
increases. This is because all workers need to communicate with the server,
which creates a bottleneck. Specifically, a $w$-worker SW system that solves a
$d$-dimensional ERM problem requires $2wd$ amount of data exchange per
iteration (each worker sends and receives a $d$-dimensional vectors per
iteration), which scales linearly with respect to $w$.

To address this scalability limitation, the RAR (Patarasuk09:Ring-AllReduce, )
has been proposed to remove the server. Under RAR, the workers form a ring to
exchange and aggregate data collaboratively. For a $w$-worker RAR system, each
worker splits its stochastic gradient into $w$ sub-vectors (see Fig. 1 for an
example with $w=3$). Each iteration of RAR has $2(w-1)$ steps that can be
divided into two phases. In the first phase (steps $1,\ldots,w-1$), workers
perform gradients reduction (i.e., summation), where each worker receives a
gradient subvector from its upstream worker and sends its local reduction
result to its downstream worker (Share-Reduce phase). In the second phase
(steps $w,\ldots,2w-2$), each worker circulates its resultant sub-vectors
following the same token to obtain its final resultant gradients vector
(Share-Only phase). Since each worker sends $\frac{d}{w}$ amount of data for
$2(w-1)$ times, the total amount of data any worker receives is
$\frac{2d(w-1)}{w}$, which is asymptotically independent of $w$ as $w$
increases (also referred to as being bandwidth-optimal in the literature).

##  4\. System Model and Problem Formulation

In this section, we first introduce our system model in Section 4.1 and then
present the problem formulation for RAR-based DDL scheduling optimization in
multi-tenant GPU clusters in Section 4.2.

###  4.1. System Model

1) Scheduling Model: Consider a multi-tenant GPU cluster that contains a set
of servers $\mathcal{S}$. Each server is equipped with a set of homogeneous
(i.e., of equal computation speed) and synchronized GPUs. The servers in
$\mathcal{S}$ are connected by a network and the network topology can be
modeled as a connected graph. In the beginning of a scheduling horizon
$\mathcal{T}$ of length $|\mathcal{T}|=T$ time-slots, there is a set of RAR-
based DDL jobs $\mathcal{J}$ waiting to be scheduled for training over
$\mathcal{T}$. Each job $j\in\mathcal{J}$ is associated with a number of GPUs
$G_{j}$ and a total number of training iterations $F_{j}$ from its users, both
of which are requested by its users.111In practice, to prevent spending
excessively long time waiting for the training process of a DDL job to
converge, a maximum number of training iterations is usually given.

In this paper, we consider the “gang-scheduling” discipline that is widely
adopted in practical large-scale GPU clusters (Mahajan20:Themis, ;
Gu19:Tiresias, ; Wang20:contention, ). Under gang scheduling, all workers
(i.e., GPUs) of an RAR-based DDL job should be allocated simultaneously.
Moreover, once a job is scheduled to start, all GPUs allocated for this job
will run to the job’s completion and no preemption/migration is
allowed.222Besides the overhead and complication added for both software and
hardware, it has been shown that frequent job preemption and migration may
lead to significant performance degradation (Gu19:Tiresias, ). Upon the job’s
completion, the occupied resource will also be released simultaneously. Each
GPU can only be occupied by one worker of some job at any given time. As shown
in Fig. 2, the workers of a job can be allocated within a single server or
across multiple servers, as long as there exists a path in the underlying
network that connects these workers and forms a ring topology to perform the
RAR process. Note that Fig. 2(a) allocates the workers in the same server for
each job, thus having no communication overhead. On the contrary, Fig. 2(b)
allocates workers across different servers for each job, which introduces
communication contention when the two jobs happen to perform RAR communication
concurrently.

Figure 2. An example of worker placement.

In this system, the control decisions of the scheduler are: i) determine a
feasible scheduling for all jobs in $\mathcal{J}$ subject to network resource
capacity; and ii) determine each job’s starting time. Specifically, consider
an RAR-based DDL job $j$ scheduled with $w_{j}$ workers and its gradient size
is $m_{j}$. Let $y_{js}[t]\in\mathbb{Z}^{+}$ denote the number of GPUs
scheduled for job $j$ on server $s$ in time-slot $t\in\mathcal{T}$. Then, a
scheduling decision in time-slot $t$ can be fully defined by the vector
$\mathbf{y}[t]\triangleq[y_{js}[t],\forall j,s]$. Let
$a_{j}=\arg\min_{t}\\{y_{js}[t]>0,\forall s\\}$ be the starting time of job
$j$ (to be determined) by the scheduling and let $T_{j}$ be the resultant
completion time of job $j$. Let
$\mathcal{J}[t]\triangleq\\{j|t\in[a_{j},T_{j}]\\}$ represent the set of
active jobs (jobs being executed) in time slot $t$. Clearly, to satisfy the
$G_{j}$ number of GPUs requested for job $j$ during its training time, we
have:

(1) $\displaystyle\sum_{s\in\mathcal{S}}y_{js}[t]=G_{j},\quad\forall
j\in\mathcal{J}[t],t\in\mathcal{T}.$

Also, scheduling decisions $\mathbf{y}[t]$, $\forall t$ are subject to GPU
resource constraints. Let $O_{s}$ represent the GPU capacity of server $s$. To
ensure that the allocated GPUs do not exceed each server’s limit, we have:

(2) $\displaystyle\sum_{j\in\mathcal{J}[t]}y_{js}[t]\leq O_{s},\quad\forall
s\in\mathcal{S},t\in\mathcal{T}.$

Also, under the non-preemptive gang scheduling, we have:

(3) $\displaystyle y_{js}[t]=y_{js}[t-1],\quad\forall
s\in\mathcal{S},j\in\mathcal{J}[t],a_{j}<t\leq T_{j}.$

Finally, to ensure that no workers should be allocated for non-active jobs and
positive integer number of workers should be assigned to active jobs, we have:

(4) $\displaystyle y_{js}[t]=0,\quad\forall
s\in\mathcal{S},j\not\in\mathcal{J}[t],t\in\mathcal{T},$ (5) $\displaystyle
y_{js}[t]\in\mathbb{Z}^{++},\quad\forall
s\in\mathcal{S},j\in\mathcal{J}[t],t\in\mathcal{T}.$

2) Communication Contention Modeling: With the above scheduling model, we are
now in a position to present our communication contention model. We assume
that no communication contention will be introduced if at most one server is
used for the job. For example, in Fig. 2(a), jobs 1 and 2 both use intra-
server communication and does not incur any communication contention. By
contrast, in Fig. 2(b), jobs 1 and 2 induce communication contention since
they both compete for inter-server link bandwidth between servers 1 and 2. We
let $p_{j}[t]$ denote the largest number of concurrently running jobs that
share an inter-server communication link with job $j$ in time slot $t$, which
can be computed as:

$\displaystyle p_{j}[t]$
$\displaystyle=\max_{s\in\mathcal{S}}\bigg{\\{}\mathds{1}\\{0<y_{js}[t]<G_{j}\\}\sum_{j^{\prime}\in\mathcal{J}[t]}\mathds{1}\\{0\\!<\\!y_{j^{\prime}s}[t]<G_{j^{\prime}}\\}\bigg{\\}},$
(6) $\displaystyle\hskip 122.85876pt\forall
j\in\mathcal{J}[t],t\in\mathcal{T}.$

In (4.1), the first term $\mathds{1}\\{0<y_{js}[t]<G_{j}\\}$ indicates that
only active jobs using inter-server communication on server $s$ will be
considered. The second term
$\sum_{j^{\prime}\in\mathcal{J}[t]}\mathds{1}\\{0<y_{j^{\prime}s}[t]<G_{j^{\prime}}\\}$
represents the number of different jobs that compete for inter-server
communication on server $s$. Since job $j$ may not be transmitting at all
times (due to switching between communication and computation modes), we let
$k_{j}[t]$ be the actual largest number of contending jobs on average with job
$j$ in time-slot $t$, which can be assumed to be statistically linearly
proportional to $p_{j}[t]$, i.e.,

(7) $\displaystyle k_{j}[t]=\xi_{1}p_{j}[t],\quad\forall
j\in\mathcal{J}[t],t\in\mathcal{T},$

where $\xi_{1}\in(0,1]$ is a positive constant.

3) RAR-Based DDL Training Completion Time Modeling: To evaluate the job
completion time $T_{j}$ of job $j$, we need to first characterize the RAR
training speed. Note that the per-iteration RAR operation time of each DDL job
can be decomposed into three parts: i) information exchange time, ii)
computation time, and iii) communication overhead. Next, we will model the
operation time of each part individually.

2-1) Information Exchange Time: We use
$B^{\\{\omega_{j,1},\omega_{j,2}\\}}(\mathbf{y}[t])$ to denote the bandwidth
between two successive workers $\omega_{j,1}$ and $\omega_{j,2}$ in job $j$’s
ring in time-slot $t$ under a scheduling decision $\mathbf{y}[t]$, where
$\omega_{j,2}$ is the downstream worker of $\omega_{j,1}$. Note that, unlike
(Yu22:GAGET, ), we do not reserve bandwidth for each job in this paper, and
this bandwidth is determined by communication contention with other jobs under
the scheduling decisions $\mathbf{y}[t]$ (see Fig. 2(b)). We let
$B_{j}(\mathbf{y}[t])\triangleq\min_{(\omega_{j,1},\omega_{j,2})\in\mathcal{L}_{j}}B^{\\{\omega_{j,1},\omega_{j,2}\\}}(\mathbf{y}[t])$
represent the bandwidth of the bottleneck link of job $j$ under scheduling
decision $\mathbf{y}[t]$, where $\mathcal{L}_{j}$ is the set of all links of
job $j$. Recall from Section 3 that the amount of information exchanged in
each time-slot can be computed as $\frac{2m_{j}}{w_{j}}(w_{j}-1)$. Thus, the
number of time-slots for information exchange can be computed as
$\frac{2m_{j}}{w_{j}}(w_{j}-1)/B_{j}(\mathbf{y}[t])$.

Clearly, the bottleneck link of job $j$ occurs in those links that are shared
by the largest number of other concurrently running jobs. We let $b^{e}$ and
$b^{i}$ be the link bandwidth between and within servers, respectively, where
$b^{i}\gg b^{e}$ in practice (Zhang17:Poseidon, ; Shi18:DDL, ). Recall that
$k_{j}[t]$ denotes the actual largest number of contending jobs on average
with job $j$ in time-slot $t$. Ideally, each job on this bottleneck link has
an equal share of bandwidth $b^{e}/k_{j}[t]$ under communication contention.
In practice, however, the bandwidth performance often degrades when multiple
jobs compete for a link, which results in each job having less than
$b^{e}/k_{j}[t]$ share of bandwidth if $k_{j}[t]\geq 2$ (Wang20:contention, ).
To model this effect, we use a function $f(\boldsymbol{\alpha},k_{j}[t])$ to
represent the “bandwidth sharing degradation factor” under communication
contention, where $\boldsymbol{\alpha}\in\mathbb{R}^{d}$ captures all
parameters that could lead to degradation. We assume that
$f(\boldsymbol{\alpha},k_{j}[t])$ satisfies the following properties: i)
$f(\boldsymbol{\alpha},1)=1$ and ii) $f(\boldsymbol{\alpha},k_{j}[t])$ is an
increasing function of $k_{j}[t]$. For example, if
$f(\boldsymbol{\alpha},k_{j}[t])$ is a linear function
$k_{j}[t]+\alpha(k_{j}[t]-1)$, then
$B_{j}(\mathbf{y}[t])=b^{e}/f(\boldsymbol{\alpha},k_{j}[t])=b^{e}/(k_{j}[t]+\alpha(k_{j}[t]-1))$.

Recall that in the special case where all workers of a job $j$ are co-located
within a single server, there is no contention. Further, intra-server
communication is typically enabled by fast interconnect techniques (e.g.,
NVLink (Foley17:NVLink, )). Hence, we have $B_{j}(\mathbf{y}[t])=b^{i}$.

2-2) Computation Time: To characterize the computation time in the RAR
operation, we use $C$ to denote the computational speed of a GPU unit (defined
as the amount of data processed in each time-slot). Since there are
$\frac{m_{j}}{w_{j}}(w_{j}-1)$ amount of data for reduction in each RAR
operation, the number of time-slots to complete all reductions can be computed
as $\frac{m_{j}}{w_{j}}(w_{j}-1)/C$. In addition to the all-reduce operation
time, the computation time also includes the forward pass (FP) time and the
backward pass (BP) time to compute a stochastic gradient. We let
$\Delta^{f}_{j}$ ($\Delta^{b}_{j}$) denote the duration of one FP (BP) of job
$j$. Note that the FP time is proportional to the mini-batch size $M_{j}$,
which can be calculated as $\Delta^{f}_{j}M_{j}$ (the size of a mini-batch
multiplied by the FP processing time of one sample). Meanwhile, the BP time
$\Delta^{b}_{j}$ is usually not relevant to the mini-batch size $M_{j}$ and is
typically fixed. Thus, the total number of time-slots for per-iteration
computation can be computed as
$\frac{m_{j}}{w_{j}}(w_{j}-1)/C+\Delta^{f}_{j}M_{j}+\Delta^{b}_{j}$.

2-3) Communication Overhead: In practice, it has been observed that typically,
the more servers an RAR-based DDL job uses to perform the training, the larger
the latency due to communication overhead (e.g., ACK time for message
transmission, negotiation time among all workers before conducting all-reduce
(Sergeev18:Horovod, )) can be (Wang20:contention, ). In this paper, we use
$\gamma_{j}(\mathbf{y}_{j}[t])$ to denote the latency of job $j$ caused by
communication overhead in time-slot $t$. We assume that the latency is linear
proportional to the number of servers in use, i.e.,
$\gamma_{j}(\mathbf{y}_{j}[t])=\xi_{2}\sum_{s}\mathds{1}\\{y_{js}[t]>0\\}$,
where $\mathbf{y}_{j}[t]=[y_{js}[t]>0,\forall s]$ and $\xi_{2}\in(0,1]$ is a
positive constant.

Lastly, putting 2-1) – 2-3) together, we can compute the RAR operation time of
job $j$ under scheduling decision $\mathbf{y}[t]$ as follows:

(8) $\displaystyle\\!\\!\\!\tau_{j}[t]\\!=\\!\frac{\frac{m_{j}}{w_{j}}\cdot
2(w_{j}\\!-\\!1)}{B_{j}(\mathbf{y}[t])}\\!+\\!\frac{\frac{m_{j}}{w_{j}}\cdot(w_{j}\\!-\\!1)}{C}\\!+\\!\gamma_{j}(\mathbf{y}_{j}[t])\\!+\\!\Delta^{f}_{j}M_{j}+\Delta^{b}_{j}.$

Hence, the RAR training speed $\phi_{j}[t]$ (i.e., the number of mini-batch
iterations completed by job $j$) in time-slot $t$ can be computed as
$\phi_{j}[t]\triangleq\lfloor(\tau_{j}[t])^{-1}\rfloor$. Recall that $F_{j}$
is the requested number of iterations for training job $j$. Thus, job $j$’s
completion time can be calculated as:

(9) $\displaystyle
T_{j}=a_{j}+\arg\min_{t}\big{\\{}\sum\nolimits_{t\in\mathcal{T}}\phi_{j}[t]\geq
F_{j}\big{\\}},\quad\forall j\in\mathcal{J}[t].$

###  4.2. Problem Statement

In this paper, our goal is to determine the scheduling decisions
$\mathbf{y}[t]$ to minimize the makespan (i.e., $\max_{j}T_{j}$), which is one
of the most useful metrics to measure the efficiency of multi-tenant GPU
clusters (Grandl16:OSDI, ; Grandl16-2:OSDI, ). Putting all modeling
constraints and the objective together, the RAR-based DDL job scheduling
problem (RAR-DDLS) can be formulated as the following optimization problem:

$\displaystyle\text{\bf RAR-DDLS:}\underset{}{\ \min_{y_{js}[t],\forall
j,s,t}}\max_{j\in\mathcal{J}}$ $\displaystyle\ T_{j}$ subject to
$\displaystyle\text{Constraints}\leavevmode\nobreak\
(\ref{eqn:gpu})-(\ref{eqn:completion}).$

We note that Problem RAR-DDLS is an integer non-convex program with packing
and covering constraints, which is NP-Hard. In addition, the non-convex
constraint in (4.1) involves indicator functions and the $\max$ operator,
which cannot be written in a closed-from expression and hence is not amenable
to conventional optimization techniques. Due to these challenges, we will
pursue an approximation algorithmic approach in Section 5 that offers provable
approximation ratio guarantee. To conclude this section, we summarize the key
notations in this paper in Table 1.

Table 1. Notation. $\mathcal{T}/G_{j}$ | Scheduling time horizon/# of GPUs requested by job j
---|---
$\mathcal{S}$/$\mathcal{N}$ | Set of servers/GPUs in the cluster
$\mathcal{J}[t]$ | The set of active jobs in time-slot t
$k_{j}[t]$ |  | Actual largest number of contending jobs on average with
---
job j in time-slot $t$
$\tau_{j}[t]$ | Per-iteration training time of job j in time-slot t
$y_{js}[t]$ |  # of GPUs scheduled on server $s$ for job j in time-slot $t$
$O_{s}$ |  GPU capacity of server $s$
$a_{j}/T_{j}$ |  Starting/completion time slot of job $j$
$\mathcal{Y}$ |  |  The set of feasible scheduling schemes over $\mathcal{T}$
---
$\mathbf{y}_{j}^{k}$ |  |  A schedule of job $j$ indexed with $k$
---
$\rho(\mathbf{y}_{j}^{k})$ |  Actual execution time of job $j$ when schedule $\mathbf{y}_{j}^{k}$ is used
$\hat{\rho}(\mathbf{y}_{j}^{k})$ |  |  Estimated execution time of job $j$ when schedule $\mathbf{y}_{j}^{k}$ is used
---
$\mathcal{G}(\mathbf{y}_{j}^{k})$ |  |  Set of GPUs allocated for job $j$ when schedule $\mathbf{y}_{j}^{k}$ is used
---
$x_{j}^{k}$ |  |  Indicate whether job $j$ follows schedule $\mathbf{y}_{j}^{k}$ or not
---
$W_{jg}^{k}$ |  |  Execution time added to GPU $g$ by job $j$ if job j follows $\mathbf{y}_{j}^{k}$
---
$U_{s}^{g}$ |  |  The accumulative execution time of worker $g$ on server $s$
---

##  5\. Solution Approach

As mentioned in Section 4, a key challenge to solve Problem RAR-DDLS is that,
due to the mixed covering- and packing-type constraints, the number of job
scheduling combinations grows exponentially as the number of servers/jobs
increases. Thus, it is computationally prohibitive to enumerate all possible
combinations before the scheduler decides when to start and which GPU(s)
should be allocated to achieve the optimal scheduling. Exacerbating the
problem is the fact that communication contention renders a mixed-integer
bilinear structure in (4.1), making it intractable to express $p_{j}[t]$ in
closed-form. Due to these challenges, it is difficult to directly solve
Problem RAR-DDLS based on its original formulation. To overcome this
challenge, we propose the following “indirect” approach to solve Problem RAR-
DDLS.

1) Basic Idea: First, we note that, although not in closed-form expressions,
the per-iteration time $\tau_{j}[t]$ for each job can be computed in
polynomial time according to (4.1)-(8) once a schedule (i.e.,
$\mathbf{y}[t]=\\{y_{js}[t],\forall j,s\\}$) is given. Specifically, we note
that the per-iteration time $\tau_{j}[t]$ is determined by
$B_{j}(\mathbf{y}[t])$ and $\gamma_{j}(\mathbf{y}_{j}[t])$. Moreover,
$f(\boldsymbol{\alpha},k_{j}[t])$ increases as $k_{j}[t]$ gets larger, and
$\gamma_{j}(\mathbf{y}_{j}[t])$ increases as
$\sum_{s}\mathds{1}\\{y_{js}[t]>0\\}$ grows. Thus, the range of $\tau_{j}[t]$
can be estimated. The largest number of $k_{j}[t]$ is $\max_{s}O_{s}$, i.e.,
the worst case would be each job places one of its workers into the server
with the biggest capacity and they all compete for the bandwidth. Thus, we can
have
$B_{j}(\mathbf{y}[t])\in[b^{e}/f(\boldsymbol{\alpha},\max_{s}O_{s}),b^{i}]$.
In addition, we have $\sum_{s}\mathds{1}\\{y_{js}[t]>0\\}\in[1,G_{j}]$. Then
by plugging $B_{j}(\mathbf{y}[t])$ and $\sum_{s}\mathds{1}\\{y_{js}[t]>0\\}$
with their lower and upper bounds in Eqn. (8), respectively, we can attain the
lower and upper bounds.

The above insight suggests that we can solve Problem RAR-DDLS via the
following search-based approach to circumvent the structural difficulty in
(4.1)-(8) . We can first search for a schedule $\mathbf{y}$, then
$\tau_{j}[t],\forall t$ can be efficiently evaluated to estimate the makespan.
Then, we repeat the process until we find a “good enough” schedule. Therefore,
we can have the algorithmic framework as shown in Fig. 3 to obtain an
approximate makespan if the search space is given. Clearly, the search space
of $\mathbf{y}$ remains huge and difficult to sample. Nonetheless, in what
follows, we show that Problem RAR-DDLS can be reformulated to facilitate this
search-based approach.

Figure 3. Basic idea for solving Problem RAR-DDLS.

2) Problem Reformulation: In order to enable the search of a schedule, we
first reformulate Problem RAR-DDLS by introducing following notations. We let
$\mathcal{N}=\\{1,\ldots,N\\}$ be the set of all GPUs in the cluster. Let
$\mathcal{Y}=\\{\mathbf{y}^{1},\ldots,\mathbf{y}^{|\mathcal{Y}|}\\}$ be the
set of feasible scheduling schemes for the jobs to be scheduled, where
$\mathbf{y}^{k}=\\{\mathbf{y}_{1}^{k},\ldots,\mathbf{y}_{J}^{k}\\}$ and
$\mathbf{y}_{j}^{k}=\\{y^{k}_{js}[t],\forall
s\in\mathcal{S},t\in\mathcal{T}\\}\in\mathbb{Z}_{+}^{S\times T}$. Note that,
with a slight abuse of notation, we use $y^{k}_{js}[t]$ here as a constant
(not a variable) to denote the number of workers allocated for job $j$ on
server $s$ in time-slot $t$ if schedule $\mathbf{y}^{k}$ is used. We also use
$\rho_{j}(\mathbf{y}^{k})$ to denote the execution time of job $j$ if schedule
$\mathbf{y}^{k}$ is used. Also, we denote the starting time of job $j$ under
schedule $\mathbf{y}^{k}$ as
$a_{j}(\mathbf{y}^{k})\triangleq\arg\min\\{t|y^{k}_{js}[t]>0,\exists s\\}$.
Let $x_{j}^{k}\in\\{0,1\\}$ be the binary variable to indicate whether job $j$
follows schedule $\mathbf{y}^{k}$ ($x_{j}^{k}=1$) or not ($x_{j}^{k}=0$). Then
Problem RAR-DDLS can be reformulated as the following integer linear program
(ILP):

(10) $\displaystyle\min_{x_{j}^{k},\forall j,k}\max_{j}$ $\displaystyle\
x_{j}^{k}\big{(}a_{j}(\mathbf{y}^{k})+\rho_{j}(\mathbf{y}^{k})\big{)}$ (11)
subject to.
$\displaystyle\sum_{k\in\\{1,\ldots,|\mathcal{Y}|\\}}x_{j}^{k}=1,\quad\forall
j\in\mathcal{J},$ (12) $\displaystyle
x_{j}^{k}=x_{j^{\prime}}^{k},\quad\forall
j,j^{\prime}\in\mathcal{J},k\in\\{1,\ldots,|\mathcal{Y}|\\},$ (13)
$\displaystyle x_{j}^{k}\in\\{0,1\\},\quad\forall
j\in\mathcal{J},k\in\\{1,\ldots,|\mathcal{Y}|\\}.$

Constraint (11) ensures that exactly one schedule is chosen. Constraint (12)
ensures that all jobs use the same schedule $\mathbf{y}^{k}$. We note that,
although Problem (10) has a simpler structure compared to Problem RAR-DDLS, it
hides the complexity in the dimensionality of the exponential search space
$\mathcal{Y}$, which is intractable to explore. However, based on this
reformulated problem, we will show next that it is possible for one to
identify a “good enough” schedule such that the makespan can be upper bounded.

Unfortunately, Problem (10) remains an NP-hard problem. We state this formally
in Theorem 1, which can be proved based on the reduction to the vertex
coloring problem (VCP).

###### Theorem 1.

Let $n_{g}=\max_{j}G_{j}$. Solving Problem (10) to within an $O(\frac{\log
n_{g}}{2^{\sqrt{\log\log n_{g}}}})$-approximate ratio is NP-hard even when the
exact processing time of each job is available.

###### Proof.

Here, we consider the special case with all jobs having a unit processing time
($\rho(\mathbf{y}^{k})=1$). We first show that VCP can be reduced to the job
scheduling problem in Problem (14) in polynomial time. Given an instance $I$
of VCP, i.e., given a graph $G=(V,E)$ with bounded degree $n_{g}$, we can
construct our job scheduling problem as follows: i) For each node $v\in V$, we
create a job $j_{v}\in\mathcal{J}$, where it has only one schedule
$y_{j_{v}}=\emptyset$; ii) For each edge $(u,v)\in E$, we add a worker
$w_{u,v}$ to $\mathcal{S}$. Also, update the scheduling as
$y_{j_{u}}=y_{j_{u}}\cup\\{w_{u,v}\\}$ and
$y_{j_{v}}=y_{j_{v}}\cup\\{w_{u,v}\\}$. If the graph $G^{\prime}s$ maximum
degree is no greater than $n_{g}$, then the maximum number of workers that can
be allocated to each job is also $n_{g}$.

With this reduction, we next show the solution of VCP can be translated to the
solution of Problem (14), and vice verse. First, recall that each job has one
unit processing time. Thus, all jobs should be executed inside a unit time
interval ($[0,1),[1,2),\ldots$). If we have the solution to VCP, then we can
schedule jobs with the same color in the same interval. Also, if we have the
solution to the job scheduling problem, then the jobs in the same interval can
be marked as the same color. Hence, finding an optimal solution of Problem
(14) is equivalent to find an optimal solution of VCP.

Similarly, given an instance of job scheduling, we can construct an instance
of VCP, where the makespan equals to the number of colors. Therefore, if we
have an $\alpha$-approximate solution to the job scheduling problem, we have
an $\alpha$-approximate solution to VCP. However, with the graph of degree at
most $n_{g}$, it is known that coloring a $2^{\sqrt{\log\log
n_{g}}}$-colorable graph with $O(\log n_{g})$ colors is NP-Hard. This
completes the proof. ∎

The hardness result in Theorem 1 suggests that solving Problem (10)
necessitates the design of approximation algorithms, which is our goal in
algorithm development next.

3) Identify a Scheduling with Bounded Makespan: We let
$\mathcal{G}_{j}(\mathbf{y}^{k})$ be the set of GPUs allocated for job $j$
when schedule $\mathbf{y}^{k}$ is used. We use
$W_{jg}^{k}=x_{j}^{k}\rho_{j}(\mathbf{y}^{k})$ to denote the execution time
added to GPU $g$ by job $j$ if job $j$ follows schedule $\mathbf{y}^{k}$.
Since each job $j$ only chooses one schedule, the total execution time of GPU
$g$ can be computed as $W_{g}=\sum_{j}\sum_{k}W_{jg}^{k}$. However, due to
communication contention, the exact processing time $\rho_{j}(\mathbf{y}^{k})$
is hard to evaluate in computing $W_{jg}^{k}$. Fortunately, the estimated
processing time $\hat{\rho}_{j}(\mathbf{y}^{k})$ can be bounded as
$\hat{\rho}_{j}(\mathbf{y}^{k})\in[l\rho_{j}(\mathbf{y}^{k}),u\rho_{j}(\mathbf{y}^{k})]$
for some $l\leq 1$ and $u\geq 1$, since $\tau_{j}[t]$ is bounded. Here, we use
$\frac{\hat{\rho}_{j}(\mathbf{y}^{k})}{u}\leq\rho_{j}(\mathbf{y}^{k})$ to
replace $\rho_{j}(\mathbf{y}^{k})$ when computing $W_{jg}^{k}$. Consider a
search algorithm $\pi$ that solves the following ILP to choose one schedule
from $\mathcal{Y}$:

(14) $\displaystyle\min\ -1$ (15) subject to.
$\displaystyle\hat{W}_{jg}^{k}=x_{j}^{k}\frac{\hat{\rho}_{j}(\mathbf{y}^{k})}{u},\forall
j\\!\in\\!\mathcal{J},k\\!\in\\!\\{1,\ldots,|\mathcal{Y}|\\},g\\!\in\\!\mathcal{N},$
(16)
$\displaystyle\sum_{j\in\mathcal{J}}\sum_{k\in\\{1,\ldots,|\mathcal{Y}|\\}}\hat{W}_{jg}^{k}\leq\theta_{u},\quad\forall
g\in\mathcal{N},$ $\displaystyle\text{Constraints}\leavevmode\nobreak\
(\ref{eqn:all_placed})-(\ref{eqn:binary}).$

Note that Problem (14) has no objective function to be optimized since we are
only interested in whether a feasible solution no greater than a given maximum
execution time limit $\theta_{u}$ exists ($\theta_{u}$ depends on parameter
$u$). Constraints (15)–(16) ensure that no GPU’s execution time would exceed
$\theta_{u}$. Let $W^{\pi}_{\max}=\max_{g\in\mathcal{N}}W_{g}$ be the maximum
execution time of all GPUs returned by algorithm $\pi$. Due to the use of
estimated $\frac{\hat{\rho}_{j}(\mathbf{y}^{k})}{u}$, the solution of $\pi$
finds a lower bound of $W_{\max}^{\pi}$, which is also a lower bound of the
makespan under $\pi$ (due to potential idling resulted from synchronization
barrier).

Note that for any feasible scheduling with the upper bound $\theta_{u}$ for
Problem (14), we can find a corresponding feasible solution for Problem (10)
by setting $x_{j}^{k}=1$ if job $j$ follows schedule $\mathbf{y}^{k}$;
otherwise, set $x_{j}^{k}=0$. Thus, the challenge of solving Problem (10)
becomes finding a tightest execution time limit $\theta_{u}$ for Problem (14),
which is relatively easy since there is no need to explore the exponential
search space of schedules $\mathcal{Y}$.

It is insightful to understand the choice of $\theta_{u}$ in Problem (14). On
one hand, if $\theta_{u}$ is too small, Problem (14) could be infeasible, and
no scheduling for Problem (10) can be found. On the other hand, when
$\theta_{u}$ is too large, then all schedulings can be considered, and the gap
between the optimal maximum execution time and the optimal makespan can be
large, thus no meaningful lower bound of $W^{\pi}_{\max}$ can be found.
Fortunately, since determining an appropriate $\theta_{u}$ is a univariate
search, we can simply use the bisection method to efficiently find the minimum
$\theta_{u}$ feasible to Problem (14).

4) Algorithm Description: We next present our scheduling algorithm based on
bisection to search $\theta_{u}$ and the smallest job first strategy to solve
Problem (14) for a given $\theta_{u}$. Note that if a job’s ring of workers is
scheduled over a large number of servers, it may potentially worsen
communication contention with concurrent jobs and its communication overhead
could be large. Therefore, to control the number of active servers, we use a
threshold parameter $\kappa\in[1,n_{g}]$ to control the number of maximum
servers for scheduling jobs. We summarize our scheduling approach in Algorithm
1. The intuition behind Algorithm 1 is that: 1) When the job is small (i.e.,
$G_{j}\leq\kappa$), we prefer to pack the job into servers whose GPUs are
already occupied by some other jobs rather than opening new server(s) to host
its workers. Since the job is small, the induced contention is mild by using
the shared servers. Further, by packing its workers to these servers, we can
avoid fragmentation introduced by a small job and save space for larger jobs
that will be scheduled next. 2) If $G_{j}>\kappa$, we prefer to allocate the
job’s workers to new server(s). This is because shared servers may only have
limited available GPU(s), and in order to gang-schedule a large job, a large
number of shared servers may be used, which leads to a high communication
overhead.

1 Input: $\mathcal{J}$, $U_{s}^{g}$, $\hat{\rho}_{j}(\mathbf{y}^{k})$, $u$,
$\lambda_{j}$;

2 Initialization: Let $U_{s}^{g}\leftarrow 0,\forall g,s$;

3

4Sort jobs by $G_{j}$ in non-decreasing order, and denote as
$\mathcal{J}^{s}$;

5 $m\leftarrow T$, $\mathbf{y}\leftarrow\emptyset$, $left\leftarrow 1$,
$right\leftarrow T$;

6 while  _$left <=right$_ do

7 $\theta_{u}\leftarrow(left+right)/2$, $m_{\theta}\leftarrow T$,
$\mathbf{y}_{\theta}\leftarrow\emptyset$;

8 for  _$\kappa=1,2,\ldots,\max_{j}G_{j}$_ do

9 $\mathbf{y}_{\theta}^{k}\leftarrow\emptyset$,
m${}_{\theta}^{k}\leftarrow-1$;

10 for  _$j=1,2,\ldots,|\mathcal{J}^{s}|$_ do

11 if  _$G_{j}\leq\kappa$_ then

12 Return $\mathbf{y}_{j}$, $T_{j}$ using Algorithm 2;

13

14 else

15 Return $\mathbf{y}_{j}$, $T_{j}$ using Algorithm 3;

16

17 if  _$\mathbf{y}_{j}==\emptyset$_ then

18 break;

19

20
$\mathbf{y}_{\theta}^{k}\leftarrow\mathbf{y}_{\theta}^{k}\cup\\{\mathbf{y}_{j}\\}$,
$m_{\theta}^{k}\leftarrow\max\\{\text{m}_{\theta}^{k},T_{j}\\}$;

21

22 if  _$m_{\theta}^{k} <m_{\theta}$_ then

23 $m_{\theta}\leftarrow m_{\theta}^{k}$,
$\mathbf{y}_{\theta}\leftarrow\mathbf{y}_{\theta}^{k}$;

24

25 if  _$m_{\theta} <m$_ then

26 $m\leftarrow m_{\theta}$, $\mathbf{y}\leftarrow\mathbf{y}_{\theta}$;

27 $right\leftarrow\theta_{u}-1$;

28

29 else

30 $left\leftarrow\theta_{u}+1$;

31

32return m, $\mathbf{y}$;

33

Algorithm 1 Smallest Job First with Balanced Contention and Overhead (SJF-
BCO).

1 Input: A given job $j$, $\mathcal{S}$, $U_{s}^{g}$,
$\hat{\rho}_{j}(\mathbf{y}^{k})$, $u$, $\theta_{u}$;

2 $\mathcal{G}^{\theta_{u}}_{idle}\leftarrow$ available GPUs with execution
time not exceed $\theta_{u}$;

3 if  _$|\mathcal{G}^{\theta_{u}}_{idle}|\geq G_{j}$_ then

4 Pick top-$G_{j}$ workers with least $U_{s}^{g}$ from
$\mathcal{G}^{\theta_{u}}_{idle}$ as $\mathbf{y}_{j}$;

5
$T_{j}\leftarrow\arg\max_{t}\\{y_{js}[t]>0|y_{js}[t]\in\mathbf{y}_{j},\forall
s,t\\}$;

6 $U_{s}^{g}\leftarrow
U_{s}^{g}+\hat{\rho}_{j}(\mathbf{y}^{k})/u,\forall(g,s)\in\mathbf{y}_{j}$;

7 return $\mathbf{y}_{j},T_{j}$;

8

9if  _there exists running jobs_ then

10 Waiting for some job to exit and then goes to Line 2;

11

12return $\emptyset,T$;

13

Algorithm 2 Fragment-Aware First Fit Packing (FA-FFP).

1 Input: A given job $j$, $U_{s}^{g}$, $\hat{\rho}_{j}(\mathbf{y}^{k})$, $u$,
$\lambda_{j}$;

2 Sort the server set $\mathcal{S}$ by $\sum_{g}U_{s}^{g}/O_{s}$ in non-
decreasing order, and choose the top $m$-servers s.t.
$\sum_{s=1}^{m}O_{s}\geq\lambda_{j}G_{j}$, and denote the selected server set
as $\mathcal{S}_{selected}$;

3 $\mathcal{G}^{\theta_{u}}_{idle}\leftarrow\emptyset$;

4 for  _$s\in\mathcal{S}_{selected}$_ do

5 Sort GPUs whose $U_{s}^{g}+\hat{\rho}_{j}(\mathbf{y}^{k})/u\leq\theta_{u}$
by execution time in non-decreasing order, then append them to
$\mathcal{G}^{\theta_{u}}_{idle}$;

6

7if  _$|\mathcal{G}^{\theta_{u}}_{idle}|\geq G_{j}$_ then

8 Pick top-$G_{j}$ workers with least $U_{s}^{g}$ as $\mathbf{y}_{j}$;

9
$T_{j}\leftarrow\arg\max_{t}\\{y_{js}[t]>0|y_{js}[t]\in\mathbf{y}_{j},\forall
s,t\\}$;

10 $U_{s}^{g}\leftarrow
U_{s}^{g}+\hat{\rho}_{j}(\mathbf{y}^{k})/u,\forall(g,s)\in\mathbf{y}_{j}$;

11 return $\mathbf{y}_{j},T_{j}$;

12

13if  _there are running jobs_ then

14 Waiting for some job to exit and then goes to Line 3;

15

16return $\emptyset,T$;

Algorithm 3 Least Busy Server-GPU First (LBSGF).

In Algorithm 1, $U_{s}^{g}$ denotes the accumulative execution time of worker
$g$ on server $s$. We first sort jobs in non-decreasing order of their sizes
$G_{j}$ in Line 1. We search $\theta_{u}$ using the bisection method in the
range $[1,T]$, and use the pair $(\theta_{u},\kappa)$ to perform scheduling
(Lines 1-1). We then iterate through each job (Line 1). If its size is not
greater than the threshold $\kappa$ (Line 1), Algorithm 2 will be used to do
the scheduling (Line 1); otherwise, Algorithm 3 will be called (Line 1). If no
feasible scheduling of job $j$ is returned, then we quit the current loop and
update $\kappa$ (Line 1); otherwise, we will update the scheduling and
makespan given the current $(\theta_{u},\kappa)$ (Line 1). Upon finishing
scheduling all jobs, we will update the schedule and makespan for the given
$\theta_{u}$ if it has a smaller makespan (Lines 1-1). After exhausting all
values of $\kappa$ for a given $\theta_{u}$, we will update the global
makespan and the schedule if the current input $\theta_{u}$ has a better
performance (Lines 1-1). Also, it indicates that we can further decrease the
value of $\theta_{u}$ to find a potentially better schedule. Thus, we search
for the left half space by moving the right pointer (Line 1); otherwise, we
should increase the value of $\theta_{u}$ by moving the left pointer (Line 1).
By scheduling workers as described in Algorithm 1, no worker’s execution time
will exceed the given limit $\theta_{u}$. We denote the tightest execution
time limit returned as $\tilde{\theta}_{u}$.

Algorithm 2 is based on the idea of “fragment-aware first fit packing,” where
we first add all available GPUs whose
$U_{s}^{g}+\hat{\rho}_{j}(\mathbf{y}^{k})/u\leq\theta_{u}$ (Line 2). If there
are enough available GPUs to schedule for job $j$’s workers (Line 2), we
choose top-$G_{j}$ GPUs with least execution time first (Line 2). We then
evaluate the completion time of job $j$ (Line 2) and update the corresponding
GPUs’ execution time (Line 2); otherwise, we wait for some job to finish
(Lines 2-2).

Algorithm 3 is based on the idea of “least busy server-GPU first,” where we
sort the servers by its GPU’s average accumulative execution time (Line 3) and
add the available GPUs whose execution time does not exceed $\theta_{u}$ in a
non-decreasing order (Lines 3-3). Here, we introduce $\lambda_{j}\geq 1$ as a
tuning parameter. The smaller the $\lambda_{j}$ is, the fewer number of
servers can be used. If enough idle workers can be found, we schedule the job,
evaluate its completion time, update the execution time of the chosen GPUs,
and return the schedule (Lines 3-3); otherwise, we wait for some job to finish
(Lines 3-3). If there is no running job left, then return schedule $\emptyset$
and timespan $T$ (as makespan) to indicate the scheduling is infeasible (Line
3).

##  6\. Performance Analysis

In this section, we analyze the theoretical performance of SJF-BCO.
Specifically, we will establish the approximation ratio guarantee of our
proposed SJF-BCO algorithm as follows:

  * 1)

We first show in Lemma 2 that the maximum execution time (i.e.,
$\hat{W}_{\max}^{\mathrm{Alg1}}$) returned by our algorithm is equal to
$\tilde{\theta}_{u}$.

  * 2)

We then prove that the makespan is $O(\hat{W}_{\max}^{\mathrm{Alg1}})$ in
Lemma 3.

  * 3)

We further show that the gap between $\tilde{\theta}_{u}$ and the tightest
execution time limit $\theta_{u}^{*}$ returned by some offline optimal
algorithm in the right-hand-side (RHS) of (16) is bounded in Lemma 4.

Finally, by putting all these lemmas together, we arrive at the approximation
ratio result stated in Theorem 5.

###### Lemma 2 (Maximum Execution Time Upperbound).

Algorithm 1 produces a schedule with the maximum execution time
$\hat{W}_{\max}^{\mathrm{Alg1}}=\tilde{\theta}_{u}$.

###### Proof.

Note that in Algorithm 1, we can obtain a schedule such that the execution
time of every worker will not exceed $\tilde{\theta}_{u}$, i.e.,
$\sum_{j}\sum_{k}x_{j}^{k}\frac{\hat{\rho}_{j}(\mathbf{y}^{k})}{u}\leq\tilde{\theta}_{u}$,
$\forall g$ (cf. Line 2 in Algorithm 2 and Line 5 in Algorithm 3). Note that
$\tilde{\theta}_{u}$ is the tightest value found by Alg. 1 since we will keep
decreasing its value in the RHS of (16) until it becomes equal to
$\hat{W}_{\max}^{\mathrm{Alg1}}$ in the LHS of (16). It then follows that:

$\displaystyle\hat{W}_{\max}^{\mathrm{Alg1}}=\max_{g\in\mathcal{N}}\sum_{j\in\mathcal{J}}\sum_{k\in\\{1,\ldots,|\mathcal{Y}|\\}}x_{j}^{k}\frac{\hat{\rho}_{j}(\mathbf{y}^{k})}{u}=\tilde{\theta}_{u}.$

Thus, we can have the maximum execution time $\hat{W}_{\max}^{\mathrm{Alg1}}$
is equal to $\tilde{\theta}_{u}$, and the proof is complete. ∎

###### Lemma 3 (Makespan Upperbound).

Algorithm 1 achieves a makespan at most $n_{g}\hat{W}^{\mathrm{Alg1}}_{\max}$,
where $n_{g}$ is defined as in Theorem 1.

###### Proof.

To bound the makespan, we need to attain upper bounds of the total busy and
idle time for each worker. Recall that due to the synchronous gang scheduling
for training, the worker may wait for other workers to finish executing other
jobs before it could start processing the current job, which may result in
idling. First, we can have the total busy time
$T_{g}^{\mathrm{busy}}\leq\hat{W}^{\mathrm{Alg1}}_{\max}\overset{\mathrm{Lem.}\leavevmode\nobreak\
\ref{lem:execution time}}{=}\tilde{\theta}_{u}$. Next, we work on bounding the
total idle time $T_{g}^{\mathrm{idle}}$.

For any worker $g\in\mathcal{N}$, we use $g_{j}$ to denote the last job $j$ on
$g$. Suppose job $j$ follows schedule $\mathbf{y}^{k}$. At any time slot $t$
before worker $g$ processes job $j$, there are two cases: i) worker $g$ is
occupied by other jobs (i.e., $g$ is busy); ii) worker $g$ is idle, but at
least one worker $g^{\prime}\in\mathcal{G}_{j}(\mathbf{y}^{k})$ is busy with
executing other jobs. Since we consider the gang-scheduling discipline, the
job cannot be delayed if there is a sufficient number of GPUs available as
requested. Thus we have:

$\displaystyle
T_{g}^{\mathrm{idle}}\overset{\mathrm{(a)}}{\leq}\\!\\!\\!\\!\sum_{g^{\prime}\in\mathcal{G}_{j}(\mathbf{y}^{k})|g^{\prime}\neq
g}\\!\\!\\!\\!T_{g^{\prime}}^{\mathrm{busy}}\overset{}{\leq}\sum_{g^{\prime}\in\mathcal{G}_{j}(\mathbf{y}^{k})|g^{\prime}\neq
g}\\!\\!\\!\\!\hat{W}^{\mathrm{Alg1}}_{\max}\overset{\mathrm{(b)}}{\leq}(G_{j}\\!-\\!1)\hat{W}^{\mathrm{Alg1}}_{\max},$

where (a) follows from the fact that in any time slot $t$ that worker $g$ is
idle (case ii), we must be able to find at least one busy worker
$g^{\prime}\in\mathcal{G}_{j}(\mathbf{y}^{k})$. To calculate the idle time of
worker $g$, we can calculate the busy time of worker(s)
$g^{\prime}\in\mathcal{G}_{j}(\mathbf{y}^{k})$ instead, and the limit of each
worker’s busy time is $\hat{W}_{\max}^{\mathrm{Alg1}}$. Also, (b) follows from
the fact that at most $G_{j}-1$ number of GPUs (except worker $g$) are busy.
Then, we can upper bound the makespan $T^{\mathrm{total}}$ as:

$\displaystyle T^{\mathrm{total}}$
$\displaystyle=\max_{g\in\mathcal{N}}(T_{g}^{\mathrm{busy}}+T_{g}^{\mathrm{idle}})\leq\max_{j\in\mathcal{J}}\bigg{(}\hat{W}_{\max}^{\mathrm{Alg1}}+(G_{j}-1)\hat{W}_{\max}^{\mathrm{Alg1}}\bigg{)}$
$\displaystyle=\max_{j\in\mathcal{J}}G_{j}\hat{W}_{\max}^{\mathrm{Alg1}}=n_{g}\hat{W}_{\max}^{\mathrm{Alg1}},$

and the proof is complete. ∎

Next, we characterize the gap between the maximum execution time limit
$\tilde{\theta}_{u}$ and the optimal execution time $\theta^{*}_{u}$ in the
RHS of (16).

###### Lemma 4.

The maximum execution time $\tilde{\theta}_{u}$ returned by Algorithm 1
satisfies $\tilde{\theta}_{u}\leq\varphi\frac{u}{l}\cdot\theta^{*}_{u}$, where
$\varphi=\max_{j}\frac{\rho_{j}(\mathbf{y}^{k_{1}})}{\rho_{j}(\mathbf{y}^{k_{2}})},\forall
k_{1},k_{2}$.

###### Proof.

Let $k^{*}$ and $\tilde{k}$ be the schedule indices chosen by solving Problem
(14) optimally and Algorithm 1, respectively. Let
$\mathcal{G}(\mathbf{y}^{k})$ be the set of selected GPUs if schedule
$\mathbf{y}^{k}$ is used. We have

$\displaystyle\tilde{\theta}_{u}$
$\displaystyle\overset{\mathrm{Lem.\leavevmode\nobreak\ \ref{lem:execution
time}}}{=}\max_{g\in\mathcal{G}(\mathbf{y}^{\tilde{k}})}\sum_{j\in\mathcal{J}}\frac{\hat{\rho}_{j}(\mathbf{y}^{\tilde{k}})}{u}\overset{\mathrm{(a)}}{\leq}\max_{g\in\mathcal{G}(\mathbf{y}^{\tilde{k}})}\sum_{j\in\mathcal{J}}\frac{\varphi\frac{u}{l}\hat{\rho}_{j}(\mathbf{y}^{k^{*}})}{u}$
$\displaystyle\overset{\mathrm{(b)}}{\leq}\max_{g\in\mathcal{G}(\mathbf{y}^{k^{*}})}\sum_{j\in\mathcal{J}}\frac{\varphi\frac{u}{l}\hat{\rho}_{j}(\mathbf{y}^{k^{*}})}{u}\overset{\mathrm{Eq.}\leavevmode\nobreak\
\eqref{eqn:gpu_lp}}{\leq}\varphi\frac{u}{l}\theta^{*}_{u}.$

To see why (a) holds, recall that for any schedule $\mathbf{y}^{k}$, we have
$\hat{\rho}_{j}(\mathbf{y}^{k})\in[l\rho_{j}(\mathbf{y}^{k}),u\rho_{j}(\mathbf{y}^{k})]$.
Then, for any two different schedules $\mathbf{y}^{k_{1}}$ and
$\mathbf{y}^{k_{2}}$, we can calculate the worst-case ratio as
$\frac{\hat{\rho}_{j}(\mathbf{y}^{k_{1}})}{\hat{\rho}_{j}(\mathbf{y}^{k_{2}})}\leq\frac{u\rho_{j}(\mathbf{y}^{k_{1}})}{l\rho_{j}(\mathbf{y}^{k_{2}})}\leq\varphi\frac{u}{l}$.
The inequality in (b) can be established as follows. First, note that
$\tilde{k}$ is chosen using the least execution time first scheduling strategy
in Algorithm 2 (Line 2). Then, we have
$\max_{g\in\mathcal{G}(\mathbf{y}^{\tilde{k}})}\sum_{j\in\mathcal{J}}\frac{\hat{\rho}_{j}(\mathbf{y}^{\tilde{k}})}{u}\leq\max_{g\in\mathcal{G}(\mathbf{y}^{k})}\sum_{j\in\mathcal{J}}\frac{\hat{\rho}_{j}(\mathbf{y}^{k})}{u}$,
$\forall k$, which can be proved by contradiction as follows. Suppose there
exists
$g\in\mathcal{G}(\mathbf{y}^{k})\setminus\mathcal{G}(\mathbf{y}^{\tilde{k}})$
such that
$\sum_{j\in\mathcal{J}}\frac{\hat{\rho}_{j}(\mathbf{y}^{k})}{u}\leq\sum_{j\in\mathcal{J}}\frac{\hat{\rho}_{j}(\mathbf{y}^{\tilde{k}})}{u}$,
$\forall g^{\prime}\in\mathcal{G}(\mathbf{y}^{\tilde{k}})$. However, we know
that $\tilde{k}$ chooses the GPUs with the least execution time first, i.e.,
$g$ should be in $\mathcal{G}(\mathbf{y}^{\tilde{k}})$, which contradicts our
assumption. This completes the proof. ∎

Finally, by putting everything together, we have the following approximation
ratio for our proposed approach:

###### Theorem 5 (Approximation Ratio).

Alg. 1 is $n_{g}\varphi\frac{u}{l}$-approximate.

###### Proof.

We use $T^{*}$ to denote the optimal makespan that produced by some offline
optimal algorithm. It then follows that

$\displaystyle T^{total}$
$\displaystyle\overset{\mathrm{Lem.}\ref{lem:makespan}}{\leq}n_{g}\hat{W}^{\mathrm{Alg1}}_{\max}\overset{\mathrm{Lem.}\ref{lem:execution
time}}{=}n_{g}\tilde{\theta}_{u}\overset{\mathrm{Lem.}\ref{lem:wk_gap}}{\leq}n_{g}\varphi\frac{u}{l}\theta^{*}_{u}\overset{\mathrm{(a)}}{\leq}n_{g}\varphi\frac{u}{l}T^{*},$

where (a) is due to Problem (14) estimates the processing time as
$\frac{\hat{\rho}_{j}(\mathbf{y}^{k})}{u}$ without considering potential
idling (caused by synchronization barrier), which implies
$\theta^{*}_{u}\\!\leq\\!T^{*}$. This completes the proof. ∎

###### Remark 1.

Note that the result in Theorem 5 does not depend explicitly on the parameter
$\kappa$ in SJF-BCO. This is because Theorem 5 is only a worst-case upper
bound that depends on $\tilde{\theta}_{u}$, which in turn depends on $\kappa$.
Hence, $\kappa$ is implicitly captured in Theorem 5.

###### Theorem 6 (Polynomial Running Time).

Time complexity of SJF-BCO is $O(n_{g}|\mathcal{J}|N\log N\log T)$, where
$n_{g}$ is defined as in Thm. 1.

###### Proof.

The sorting operation plays a dominant role in the total running time in
Algorithm 1. For each job $j$, if $G_{j}\leq\kappa$, we need to sort all GPUs
in the cluster, which takes $O(N\log N)$ time in order to choose top-$G_{j}$
workers with least execution time first in Algorithm 2 (Line 2). Otherwise, we
only need to sort servers, which takes $O(S\log S)$ time in order to choose
top-$m$ servers as in Algorithm 3 (Line 3). Thus, it takes $O(N\log N)$ time
to schedule each job since $N>S$. Then, for all the jobs to be scheduled given
($\theta_{u},\kappa$), it has $O(|\mathcal{J}|N\log N)$ time complexity.
Recall that we use bisection to search $\theta_{u}$, where each iteration
contains an inner loop indexed by $\kappa\\!\in\\![1,n_{g}]$. This implies a
total of $n_{g}\log T$ trials. Thus, the overall time complexity is
$O(n_{g}|\mathcal{J}|N\log N\log T)$. ∎

Figure 4. Makespan comparison under different policies.

Figure 5. Impact of value of $\kappa$ on makespan.

Figure 6. Makespan as the number of servers increases.

Figure 7. Impact of the value of $\lambda$ on makespan.

##  7\. Numerical Results

In this section, we conduct simulation studies to evaluate the performance of
our proposed SJF-BCO algorithm.

1) Experiment Settings: Similar to the setting in (Wang20:contention, ), the
workload is generated based on the Microsoft job trace (Jeon19:microsofttrace,
). We generate 160 DDL jobs by scaling down the original job trace
(Jeon19:microsofttrace, ) following the job-type distribution, where there are
80 single-GPU jobs, 14 2-GPU jobs, 26 4-GPU jobs, 30 8-GPU jobs, 8 16-GPU
jobs, and 2 32-GPU jobs. We set $F_{j}\in[1000,6000]$. The extra time cost
brought by communication contention and overhead is within 15% of the total
actual execution time. We let $\xi_{1}=\xi_{2}$ (cf. Sec. 4.1) to make
communication contention and overhead cost comparable. We set
$\tau_{j}[t]\in[0.01,0.05]$ (Yu21:PD-ORS, ), and $\lambda_{j}=1,\forall j$. We
set the estimated execution time $\hat{\rho}(\mathbf{y}^{k})\in[50,300]$
(evaluated from the product of $\tau_{j}[t]$ and $F_{j}$). The GPU cluster has
20 servers. The number of GPUs on each server is chosen from $\\{4,8,16,32\\}$
uniformly at random.

2) Baselines for Comparison: We compare our algorithm with three
representative job scheduling algorithms: First-Fit (FF) (Stavrinides11:FF-LS,
), List-Scheduling (LS) (Stavrinides11:FF-LS, ), and Random (RAND)
(Wang20:contention, ). Here, we define $\theta_{u}^{f}$ as the maximum
execution time limit returned by the scheduling policy $f$. Given a job $j$,
FF picks the first $G_{j}$ available GPUs such that their accumulative
execution time does not exceed the limit $\theta_{u}^{FF}$, from server to
server. This policy tends to pack different jobs into the fewest number of
servers to avoid fragmentation introduced by small jobs, which can save space
for large jobs to be scheduled next. LS selects top-$G_{j}$ GPUs with least
execution time first, so that the accumulative execution time does not exceed
the limit $\theta_{u}^{LS}$. Note that this policy may introduce high
communication overhead since it may choose GPUs from a large number of
servers. Further, LS tries to balance the execution time between GPUs by
always selecting the one with the least execution time. RAND randomly chooses
servers and GPUs to schedule jobs. In this policy, we allocate GPUs to a job
as long as it does not exceed $T$, i.e., we set $\theta_{u}^{RAND}=T$, to
avoid the long running time in order to find a feasible schedule.

3) Experiment Results: First, we compare the makespan performance achieved by
our SJF-BCO algorithm with those of the baseline policies. We set $T=1200$. As
shown in Fig. 7, SJF-BCO outperforms other scheduling policies both in terms
of makespan and average job completion times, implying that SJF-BCO is also
superior in terms of total job completion time. Note that SJF-BCO tends to
open new server(s) for large jobs to avoid the large communication overhead
and use shared servers for small jobs to avoid the fragmentation, thus
achieving better average completion time and makespan than FF and RAND. Note
that SJF-BCO has more prominent advantages over these baselines when the
cluster has limited GPU resources.

Then, we examine the impact of $\kappa$ on the makespan in our proposed SJF-
BCO algorithm. We set $T=1200$, and select $\kappa$ from 1 to 32. As indicated
in Fig. 7, as the value of $\kappa$ increases, the makespan first drops and
then increases and then drops again. Recall that in Algorithm 1, FA-FFP is
used when the number of requested GPUs $G_{j}\leq\kappa$; otherwise LBSGF is
used. Note that before Turning point 1 in Fig. 7, as $\kappa$ increases, the
makespan drops since more small jobs are packed into the fewest number of
shared servers, resulting in decrement of communication contention and
overhead introduced by larger jobs to be scheduled later. However, as $\kappa$
continues to grow, communication contention becomes more noticeable since more
large jobs are scheduled to the shared servers, leading to the increase of
makespan. Finally, as $\kappa$ becomes sufficiently large, then the majority
or even all jobs use shared servers to schedule their workers, which can
slightly decrease the communication overhead due to the smaller resultant
ring-span (see Turning point 2 in Fig. 7).

Next, we investigate the influence of communication contention by reducing the
number of servers. We set $T=1500$. Intuitively, the larger number of servers,
the less communication contention. As we can see from Fig. 7, as we increase
the number of servers from 10 to 20, the makespan of FF, LS and SJF-BCO
decrease due to the degradation of contention level. Note that, if enough
resources are available in the cluster, then each job will have a separate set
of servers using SJF-BCO, i.e., its performance will become better as number
of GPUs increases. In this case, no communication contention will be
introduced using SJF-BCO. The intuition that FF has the largest makespan
reduction is that the average idle time for workers drops dramatically since a
smaller execution time limit could be set as the number of servers increases.

Lastly, we inspect the influence of $\lambda$ on the makespan for SJF-BCO with
$\lambda\in\\{1,2,4,8\\}$ and $\kappa=1$. As we can see from Fig. 7, the
makespan monotonically decreases as the $\lambda$ increases. Recall that a
larger $\lambda$-value implies a larger number of servers could be selected.
Then, the job has a higher chance to open new servers to schedule its workers,
resulting in less communication contention and a smaller communication
overhead. Interestingly, $\lambda$ plays a similar role as $\kappa$, with the
aim to balance communication overhead and contention. Specifically, $\kappa$
affects the overall balance between all jobs since it determines the portion
of jobs to use either FA-FFP or LBSGF, while $\lambda$ focuses more on the
balance between communication contention and overhead for a specific job that
uses LBSGF to schedule.

##  8\. Conclusion

In this paper, we studied resource scheduling for DDL jobs in a multi-tenant
GPU cluster, where we considered the communication contention and overhead
determined by the distribution of workers. We showed that this problem can be
formulated as a highly non-trivial non-linear integer program with nonconvex
and mixed packing-covering constraints. We then converted the problem into a
tractable integer linear program, which enables the design of approximation
algorithms. Specifically, we developed a new analytical model that jointly
considers the placements and starting times of the workers of each DDL job.
Through careful reformulation, we then transformed the problem into an integer
linear program with a more tractable structure, and proposed an approximation
algorithm with an approximation ratio performance guarantee. We provided
rigorous theoretical analysis and conducted experiments to demonstrate the
efficacy of our algorithms. Collectively, our results contribute to a
fundamental understanding on resource scheduling for DDL jobs in multi-tenant
GPU clusters.

##  9\. Acknowledgements

J. Liu’s work has been supported in part by NSF grants CAREER CNS-2110259,
CNS-2112471, CNS-2102233, CCF-2110252, and a Cisco Systems Research Grant
GR127298. B. Ji’s work has been supported in part by NSF CNS-2112694. H.
Rajan’s work has been supported in part by NSF 21-20448 and NSF 19-34884.

## References

  * (1) Abadi, M., Barham, P., et al. TensorFlow: A system for large-scale machine learning.  In Proc. of USENIX OSDI (2016).
  * (2) Bao, Y., Peng, Y., and Wu, C. Deep learning-based job placement in distributed machine learning clusters.  In in IEEE INFOCOM (2019).
  * (3) Chau, V., Chu, X., Liu, H., and Leung, Y.-W. Energy efficient job scheduling with dvfs for cpu-gpu heterogeneous systems.  In Proceedings of the Eighth International Conference on Future Energy Systems (2017), pp. 1–11.
  * (4) Foley, D., and Danskin, J. Ultra-performance pascal gpu and nvlink interconnect.  In IEEE Micr (2017), vol. 37, pp. 7–17.
  * (5) Grandl, R., Chowdhury, M., Akella, A., and Ananthanarayanan, G. Altruistic scheduling in multi-resource clusters.  In OSDI (2016).
  * (6) Grandl, R., Kandula, S., Rao, S., Akella, A., and Kulkarni, J. Graphene: Packing and dependency-aware scheduling for data-parallel clusters.  In OSDI (2016).
  * (7) Gu, J., Chowdhury, M., Shin, K. G., Zhu, Y., Jeon, M., Qian, J., Liu, H., and Guo, C. Tiresias: A gpu cluster manager for distributed deep learning.  In NSDI 19 (2019), pp. 485–500.
  * (8) Hu, Z., Tu, J., and Li, B. Spear: Optimized dependency-aware task scheduling with deep reinforcement learning.  In in 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS) (2019).
  * (9) Jeon, M., Venkataraman, S., Phanishayee, A., Qian, J., Xiao, W., and Yang, F. Analysis of large-scale multi-tenant gpu clusters for dnn training workloads.  In 2019 USENIX Annual Technical Conference (USENIX ATC 19) (2019).
  * (10) Mahajan, K., Balasubramanian, A., Singhvi, A., Venkataraman, S., Akella, A., Phanishayee, A., and Chawla, S. Themis: Fair and efficient gpu cluster scheduling.  In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20) (2020), pp. 289–304.
  * (11) Mei, X., Chu, X., Liu, H., Leung, Y., and Li, Z. Energy efficient real-time task scheduling on cpu-gpu hybrid clusters.  In IEEE INFOCOM 2017 - IEEE Conference on Computer Communications (2017), pp. 1–9.
  * (12) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Köpf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. Pytorch: an imperative style, high-performance deep learning library.  In NeurIPS (2019).
  * (13) Patarasuk, P., and Yuan, X. Bandwidth optimal all-reduce algorithms for clusters of workstations.  In Journal of Parallel and Distributed Computing (2009).
  * (14) Peng, Y., Bao, Y., Chen, Y., Wu, C., and Guo, C. Optimus: An efficient dynamic resource scheduler for deep learning clusters.  In Proc. of ACM EuroSys (2018).
  * (15) Sergeev, A., and Balso, M. D. Horovod: Fast and easy distributed deep learning in tensorflow.  In arXiv preprint arXiv:1802.05799 (2018).
  * (16) Shi, S., Qiang, W., and Chu, X. Performance modeling and evaluation of distributed deep learning frameworks on gpus.  In The 4th International Conference on Big Data Intelligence and Computing (DataCom) (2018), pp. 949–957.
  * (17) Stavrinides, G. L., and Karatza, H. D. Scheduling multiple task graphs in heterogeneous distributed real-time systems by exploiting schedule holes with bin packing techniques.  In Simulation Modelling Practice and Theory (2011), vol. 19, pp. 540–552.
  * (18) Wang, L., Weng, Q., Wang, W., Chen, C., and Li, B. Metis: Learning to schedule long-running applications in shared container clusters at scale.  In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis (2020), pp. 1–17.
  * (19) Wang, Q., Shi, S., Wang, C., and Chu, X. Communication contention aware scheduling of multiple deep learning training jobs.  In arXiv:2002.10105 (2020).
  * (20) Xiao, W., Bhardwaj, R., Ramjee, R., Sivathanu, M., Kwatra, N., Han, Z., Patel, P., Peng, X., Zhao, H., Zhang, Q., Yang, F., and Zhou, L. Gandiva: Introspective cluster scheduling for deep learning.  In in 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18) (2018), pp. 595–610.
  * (21) Yu, M., Liu, J., Wu, C., Ji, B., and Bentley, E. S. Toward efficient online scheduling for distributed machine learning systems.  IEEE Transactions on Network Science and Engineering (TNSE) (2021).
  * (22) Yu, M., Tian, Y., Ji, B., Wu, C., Rajan, H., and Liu, J. Gadget: Online resource optimization for scheduling ring-all-reduce learning jobs.  In IEEE INFOCOM (2022).
  * (23) Zhang, H., Zheng, Z., Xu, S., Dai, W., Ho, Q., Liang, X., Hu, Z., Wei, J., Xie, P., and Xing, E. P. Poseidon: An efficient communication architecture for distributed deep learning on gpu clusters.  In in 2017 USENIX Annual Technical Conference (USENIX ATC 17) (2017), pp. 181–193.