Decentralized Training of Foundation Models in Heterogeneous Environments
Authors: Binhang Yuan
Yongjun He
Jared Quincy Davis
Tianyi Zhang
Tri Dao
Beidi Chen
Percy Liang
Christopher Re
Ce Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Decentralized training
Foundation model.

Abstract: Training foundation models, such as GPT-3 and PaLM, can be extremely expensive, often involving tens of thousands of GPUs running continuously for months. These models are typically trained in specialized clusters featuring fast, homogeneous interconnects and using carefully designed software systems that support both data parallelism and model/pipeline parallelism. Such dedicated clusters can be costly and difficult to obtain. Can we instead leverage the much greater amount of decentralized, heterogeneous, and lower-bandwidth interconnected compute? Previous works examining the heterogeneous, decentralized setting focus on relatively small models that can be trained in a purely data parallel manner. State-of-the-art schemes for model parallel foundation model training, such as Megatron and Deepspeed, only consider the homogeneous data center setting. In this paper, we present the first study of training large foundation models with model parallelism in a decentralized regime over a heterogeneous network. Our key technical contribution is a scheduling algorithm that allocates different computational “tasklets” in the training of foundation models to a group of decentralized GPU devices connected by a slow heterogeneous network. We provide a formal cost model and further propose an efficient evolutionary algorithm to find the optimal allocation strategy. We conduct extensive experiments that represent different scenarios for learning over geo-distributed devices simulated using real-world network measurements. In the most extreme case, across 8 different cities spanning 3 continents, our approach is 4.8× faster than prior state-of-the-art training systems.

Decentralized Training of Foundation Models in Heterogeneous Environments
Binhang Yuan ; Yongjun He'; Jared Quiney Davis Tianyi Zhang?, Tri Dao",
Beidi Chen Percy Liang". Christopher Re², Ce Zhang'
ETT Zürich, Switzerland 2Stanford University, USA *Carnegie Mellon University "Meta Al (binhang- yuan, yongjun.he he, ce.zhang) @inf.ethz.ch jjaredq, tz58, trid, beidic, pliang, chrismre | @stanford.edu
Abstract
Training foundation models. such as GPT-3 and PaLM, can extremely expensive, often involving tens of thousands of GPUs running continuously for months. These models are typically trained in specialized clusters featuring fast, homogeneous interconnects and using carefully designed software systems that support both data parallelism and model/pipeline parallelism. Such dedicated clusters can be costly and difficult to obtain. Can instead leverage the much greater amount of decentrulized, heterogeneous, and lower-bandwidth interconnected compute? Pre- vious works examining the heterogeneous, decentralized setting focus relatively small models that can be trained in purely data parallel manner. State-of-the- schemes for model parallel foundation model training, such Megatron and Deep- speed, only consider the homogeneous data center setting. In this paper, we present the first study of training large foundation models with model parallelism in a decentralized regime over a heterogeneous network. Our key technical contribution is scheduling algorithm that allocates different computational "tasklets" in the training of foundation models to a group of decentralized GPU devices connected by a slow heterogeneous network. We provide formal cost model and further propose an efficient evolutionary algorithm to find the optimal allocation strategy. We conduct extensive experiments that represent different scenarios for learning over geo-distributed devices simulated using real-world network measurements. In the most extreme case, across 8 different cities spanning continents, our approach is 4.8 faster than prior state-of-the -hhth-rrt training systems.
1 Introduction
Recent years have witnessed the rapid development of deep learning models, particularly foundation models (FMs) [1] such as GPT-3 [2) and PaLM (3]. Along with these rapid advancements, however, comes computational challenges training these models: the training of these FMs can be very expensive single GPT3-175B training takes 3.6K Petaflops-day 12] this amounts $4M on today's s AWS on demand instances, even assuming 50% device utilization (V100 GPUs peak at 125 TeraFLOPS)! Even the smaller scale language models, e.g., GPT3-1.3B (1.3 billion parameters), on which this paper evaluates, require 64 Tesla V100 GPUs to run for one week, costing $32K on AWS. As result, speeding up training and decreasing the cost of FMs have been active research areas. Due to their vast number of model parameters, state-of-the-ar systems (e.g.. Megatron [4), Deepspeed[5), Fairscale(6) leverage multiple forms of parallelism 4 8 10 design is only tailored to fast, homogeneous data center networks.
However, their
"qqual contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

"Tasklets"
tasklet allocationn
Batch
Ireland
Frankfurt
Lon
Oregon
Ohio
Ii Gips,
Virginia
b.d.lpp 24
0.4 Cheps 235
Seoul
Tokyo
Class 76 ml
Ld Cipe. 24 m
Ga Clap. 67
Chps, 136
DA Giqqa 221
0.5 O5es m.
helerogeneous bandwiclth
latency
Figure I: Given (I) a set of computation tasklets involved in training foundation models (correspond- ing different micro-batches and layers), and (2) heterogeneous network between devices, the goal is to find the optimal 3 allocation of tasklets to devices.
On the other hand, decentralization is a natural and promising direction. Jon Peddie Research reports that the PC and AIB GPU market shipped 101 million units in Q4 2021 alone [12]. Furthermore, many of these GPUs are underutilized. Leveraging this fact, volunteer computing projects such as Folding @ Home 13 have sourced upwards of 40K Nvidia and AMD GPUs continuously [14] Moreover, the incremental electricity and HVAC costs of running a V100 GPU for a volunteer are 50-100x lower than the spot prices for equivalent device AWS (IS]. If we could make use of these devices in a decentralized open- voen--ouuneering paradigm for foundation model training, this would be revolutionary alternative to the expensive solutions offered by data centers.
This vision inspired many recent efforts in decentralized learning, including both those that are theoretical and algorithmic [66] 17 18], as well as recent prototypes such as Learning @ Home [19] and DeDLOC 20) However, efforts to-date in decentralized training either focus solely on data parallelism 116
17 8 20], which alone is insufficient for FMs whose parameters exceed the capacity of a single device, or orient around alternative architectures, e.g., mixture of experts [9]. These alternative architectures provide promising directions for decentralized learning, however, they currently only trained and evaluated on smaller datasets and at a smaller computational scale (e.g.. MNIST and WikiText-2 in [19] than their state- oftthe-r-- counterparts, e.g., GLaM [2I]. In this paper, we focus on a standard GPT-style architecture, without considering any changes that might alter the model architecture or the convergence behaviour during training.
To fulfill the potential of decentralization for the training of FMs, we need to be able to (1) take advantage of computational devices connected via heterogeneous networks with limited bandwidth and significant latency, and (2) support forms of parallelism beyond pure data parallelism. In this paper, we tackle one fundamental aspect of this goal how can assign different computational "tasklets", corresponding to a micro-batch and a subset of layers, to a collection of geo-distributed devices connected via heterogeneous, slow networks? This is not easy task- even for fast and homogeneous data center networks, such assignments are still an open ongoing research challenge [22] For the heterogencouss setting, it becomes even more challenging as the size of the search space increases dramatically. In the homogeneous setting, the homogeneity of the edges in the communication graph reduces the search space into many equivalent classes representing allocation strategies with the same communication costs, enabling efficient polynomial runtime algorithms (23) 12 25 26]: however, in the heterogeneous setting, one has to consider potentially exponentially many more distinct allocation strategies as we will see later, because of the heterogeneity of the communication matrix, even the sub-problem of finding the best pipeline parallelism strategy equates to hard open loop travelling salesman problem (27)
23
24
25
26
24
In this paper, focus this challenging scheduling problem of decentralized training of FMs over slow, heterogeneous networks, and make the following contributions:
We study the problem of allocating distributed training jobs over a group of decentralized GPU devices connected via slow heterogeneous network. More specifically:
To capture the complex communication cost for training FMs, we propose a natural, but novel, formulation involving decomposing the cost model into two levels: the first level a balanced graph partitioning problem corresponding to the communication cost of data

---

parallelism, whereas the second level is joint graph matching and traveling salesman problem corresponding to the communication cost of pipeline parallelism.
We propose novel scheduling algorithm to search for the optimal allocation strategy given our cost model. Developing a direct solution to this optimization problem is hard; thus, we propose an efficient evolutionary algorithm based on collection of novel heuristics, going beyond the traditional heuristics used in standard graph partitioning methods [28].
We carefully designed and implemented a collection of system optimizations to hide communi- cation within the computation to further reduce the impact of slow connections P
We conduct extensive experiments that represent different scenarios of collaborative decentral- ized learning, simulated by using network measurements from different geographical regions of AWS. In the worldwide setting with 64 GPUs across 8 regions (Oregon, Virginia, Ohio, Tokyo, Seoul, London, Frankfurt, Ireland), we show that our system is 3.8-4.8x faster, in end-to-end runtime, than the ofte-of-the-ar systems, for training G.T3-1.3B, without any difference in what is computed or convergence dynamics. In addition, we also provide careful ablation studies to show the individual effectiveness of the scheduler and system optimizations.
We shed light on the potential of decentralized learning - our prototype in the global heteroge- neous setting is only 1.7-3.5x x slower than Megatron/Deepspped in data centers even though its network can be 100x slower. We hope this paper can inspire future explorations of decentralized learning for FMs, over geo-distributed servers, desktops, laptops, even mobile devices.
Limitations and Moving Forward. In this paper, we tackle one foundational aspect decentralized learning but leave as future work many problems that are important for practical system. We assume that communication between devices is relatively stable for a reasonable amount of time and that all devices are always online without failure eviction. Note that we also do not train full system to full convergence, instead running partial training to confirm intermediate result equivalence across regimes. Scheduling over dynamic, heterogeneous environment and providing fault tolerance, potentially with checkpointing, while training to convergence are directions for future exploration.
2 Decentralized Training of Foundation Models: Problem Formulation
Forward Activation
We first introduce concepts, technical terms, and the proce- dure of decentralized training. Then we formally define the scheduling problem this paper tackles.
Transfommnt
Transformer
Transferme
Device
Device
Micro-
Block
Block
Blog
Decentralized setting. We assume a group of devices (GPUs) participating collaborative training of a foundation model. Each pair of devices has connection with potentially different delay and bandwidth. These devices can be geo- distributed, illustrated in Figure [ with vastly different pairwise communication bandwidth and latency. In decen- tralized training, all layers of model are split into multiple stages, where each device handles a consecutive sequence of layers, e.g., several transformer blocks (29). In addition.
batch
Gradient
Device
Micro-
Tansform Block
Tansformer Block
Trinsformu Block
Device
batch
Gradient
since the input for foundation model pre-training is huge, e.g., a few millions of tokens, is also split into multiple micro-batches that can be handled in parallel.
Problem definition. We define tasklets as a collection of computational tasks in foundation model training- - Tasklet f.jj is the forward and backward computation for stage j with micro-batch of training data in a training iteration. We aim to design an effective scheduler to assign each tasklet to a particular device so that the training throughput is maximized in decentralized training.
Parallelism. The above setting involves two forms of parallelism. pipeline and data. In pipeline parallelism, the compute in multiple stages is parallelized - each device handles activation or gradient computation for different batches in parallel and the results can be communicated or passed to subsequent stages. Data parallelism means that devices compute the gradient for different micro-batches independently, but need to synchronize these gradients through communication. In a decentralized environment, the training procedure is coamuunication-buunne problem is to accelerate the communication procedure by allocating tasklets that require high communication volumes between them to devices with faster connections.
The scheduling
Our code is available at: ftttp:://gituub.com/SSSt
3

---

perfect matching, correspoeds to how devices Gand devices in C communicate in pipeline
Device
Device
(al Cummunication Trpology Graph over N devices
(b) Each partition G deals stage, running data parallel within each partition
(c) Coarsened graph decoding the cost of pipeline parallel
Open- ppeen-loop-oe loop-traveling- salesman provides pipeline structure
Figure 2: (a) Communication graph G; and (b, c, d, e) an illustration of the cost model given G.
Formalization of the scheduling problem. Formally, our scheduling problem as follows.
Let D {di ... d be of N devices; A R and B E R R- N be the communication matrix between these devices describing the delay and bandwidth respectively, where the delay and bandwidth between device d and d' is ad,d'' and Ba.dd.
Given the communication matrix A and B, we construct communication graph G (Figure 2(a) each device corresponds to a node in G and each edge between d and d' is labeled with the average latency and bandwidth between d and d': ((aa,d' + Ozd',a) (td',a)/,, (3a.a' + Ba (2). Even though A and B are asymmetric (i.e., upload and download speeds might be different), the communication graph G is symmetric because in our workloads all communications between two devices happen to involve the same amount upload and download.
The number of stages that a micro-batch needs to go through is Dyp (noted pipeline parallel degree); the number of batch partition that needs to run model gradient synchronization is Doe (noted as data parallel degree); we have Dop X Dre = N, i.e. the total number of devices. Cyp (resp. Cpp) represent the number of bytes of activations for a micro- batch (resp. parame- ters/gradients for stage) communicated in pipeline parallelism (resp. data parallelism).
We denote a training tasklet as li.j. where E (1, Doe) and j E {1,... Der each which corresponds one specific micro-batch and pipeline stage j.
An assignment strategy a E D Doe Dw assigns, for each tasklet fz.j. device oz. E D, which means that device oı runs the training tasklet 44 A valid assignment needs to be unique, i.e., V(i,j) & (i', Oie * ov We use Σ to denote the set of all valid assignments.
An optimal assignment strategy an assignment that minimizes the communication cost
arg min COMM-Cost (a) rE>
Challenges and Goals. Our goal is find the optimal assignment strategy, which involves two challenges: (1) How to effectively model the communication cost COMM-COST(a) for a given assignment under heterogeneous network environment? and (2) How to effectively search for the optimal assignment strategy that minimizes such cost? We tackle these two questions in Section 3
3 Scheduling in Heterogeneous Environments
Scheduling in the heterogeneous setting challenging task, the size of the search space increases dramatically compared to that of the homogeneous case. In the homogeneous data-center case, the network delay can be usually ignored (e.g., .. A 0) and the bandwidth B are assumed to be formed by just a few constants e.g., the communication bandwidths between different machines on the same rack are assumed be space - one can ignore the influence of communication given uniform connections (23 24! 22] or
23 24
22
22
26). This significantly constrains the search
organize the device with a hierarchical structure 22 26), making the scheduling problem solvable in
polynomial time in terms of the number of machines.
In contrast, in the fully heterogeneous scenario the communication matrix A and B consists of distinct values, which can make the search space grows exponentially. In this section, we describe scheduler that searches for optimal strategy in the complex search space.
3.1 Overview of the scheduler
We carefully design bi-level scheduling algorithm based on extended balanced graph partition problem (see Figure 2 and solve this problem by an evolutionary algorithm with carefully designed

---

local search strategy. Given an assignment strategy = {orst for all tasklets { we first model its communication cost. During the training of FMs, the communication costs come from two different sources: (1) Data parallel: All devices that are assigned with the tasklets dealing with the same stage j (handling the same layers) of different micro-batches need communicate within themselves to exchange gradients of these layers. For layer j. we call these devices its data parallel group: C = {oi.s | Vi E [Dor]]. We can implement the communication using different primitives, e.g., AllReduce 30), ScatterGatter [31], or other decentralized average protocols [6]. (2) Pipeline parallel: All devices that are assigned with the tasklets dealing with the same micro-batch of different stages need to form a pipeline, communicating within themselves to exchange activations and backward gradients. For micro- i, these devices are P, = {or.. Vjj E [Dre]]. Because these devices need to form a linear pipeline, any permutation over P. corresponds to one strategy of how these machines can conduct pipeline parallelism within them.
Scheduling Problem. The goal of our scheduler is to minimize both costs. One design decision that we made is to decompose this complex optimization problem into two levels. At the first level, we consider the best way of forming Cj 's, incurring data parallel communication costs within them. At the second level, we consider the cost of pipeline parallelism given an layout from the first level:
min COMM-COST (C1...CD.,) = Cp..Cppr
+ PIPELINEP-COST(CC..CO
(I)
s.t. |C] = =c.==...=|[0 D,r = Di.iV..j' C, = 0, C₁ U... UC..U.p =
where computing PIPELINEP-COST(C
involves finding the optimal pipeline structure.
we provide details on COMM-COST (C,...Cp,,). Notice that this modified objective makes our problem different from the textbook graph partition problem; thus, we need a carefully designed evolutionary algorithm for finding such solution introduced in Section 3.4
In Section 3.2 and Section 3.3
3.2 Modelling data parallel communication cost
Given the communication graph G forming data parallel groups C1...C CD. corresponds to a partition of G- In Figure b)), different colors correspond to devices in the same Cj. The data parallel cost within C only relies on all communication channels (edges in the communication graph) connecting devices in Cy. If we assume colocated sharded parameter server (31] implementation for communicating within each Cj, and recall that Cpp represents the total amount of data (in bytes) that needs be exchanged during gradient aggregation each device in Cj needs to manage cup/ Dup bytes of parameter shard. Once the gradient is ready, each device needs to send each of its local shards to the corresponding device; next, each device can aggregate the gradients it receives from all other devices in Cj; and finally, each device will send the aggregated gradient shard to all other devices. Therefore, we can model the data parallel cost for C, as follows:
DATAP-COST(C,) = max dEC;
2. addd'' + d'EC;-(d)
Σ
Dreea,d'
Cáp
(2)
Here, the total cost is bounded by the slowest device (maxaeC,) ). which needs to exchange data with all other machines (Edecc-(aa) (d)) Because the communication of these different data parallel groups Cp...Cp,, can be conducted in parallel and we are only bounded by the slowest data parallel group. This allows to model the total communication cost for data parallelism
DATAP-COST(CI...CC
max DATAP-COST(C.) jE(Dre)
3.3 Modeling pipeline parallel communication cost
Given C....Cpp. to model the communication cost of pipeline parallelism, we need to consider two factors: (1) each permutation æ of (CI...Dp,,) corresponds to specific pipeline strategy devices in Cuyy and devices in Czy4z communicates exchange activations (during forward pass) and
5

---

gradients on activations (during backward pass); and (2) devices in Cr, and devices in C CT,+ need be "matched" only devices that are dealing with the same micro-batch needs communicate. This makes modeling the cost of pipeline parallel communication more complex.
To model the cost of pipeline parallel communication, we first consider the best possible way that devices in C and Cy can be matched. We do this by creating a coarsened communication graph (Figure 2 c)). A coarsened communication graph GC,,..Co,, is a fully connected graph, and each partition C in the original communication graph G corresponds to a node in GG....CD..
In the coarsened graph G. the weight on an edge between Cj and C3' corresponds to the following - if Cj and Cy. need to communicate in a pipeline, what is the communicate cost of the optinal matching strategy between devices in C and devices in Cy? Recall that Cep represents the amount of data between two devices for pipeline parallel communication, we can model this cost by
( ('d.d' + Opp
min max 2 M (d,d')EM
(3)
Ba.d'
(d, where M is a perfect matching between C2 and C d') communicate with device d' E Cj' (i.e., they deal with the same nicro-batch).. Computing this value is similar to the classical minimal sum weight perfect matching problem (MinSum
E . means that device d E C3 will
in bipartite graphs [32] with the only difference being that we compute the max instead of the sum. As we will show in the supplementary material, similar to MinSum WPM, Eq can also be solved in PTIME.
The coarsened communication graph captures the pipeline parallel communication cost between two groups of devices, assuming they become neighbors in the pipeline. Given this, we need to find an optimal permutation of C.,,.DD. corresponds to the structure of the pipeline. This becomes the open-loop traveling salesman problem (27) over this condensed graph (Figure (e)). Formally, we have the following definition of the pipeline parallel cost:
PIPELINEP-COST (CI... = OPENLOOPTSP (GC,...Corr)
(4)
where Gc,...Cop is the coarsened graph defined above.
3.4 Searching via hybrid genetic algorithm
The scheduling problem solves the optimization problem in Eq [ which corresponds a balanced graph partition problem with complex objective corresponding to the communication cost. Balanced 33 Over the years, researchers have been tackling this problem via different ways [34] 35 36). We follow the line of research that uses hybrid
graph partition problem is challenging NP-hard problem
genetic algorithm 37 28
since it provides us the flexibility in dealing with complex objective.
Hybrid Genetic Algorithm. A hybrid genetic algorithm for balanced graph partition usually follows structure as follows. The input is set of candidate balanced graph partitions which serves the initial population. The algorithm generates the next generation as follows. It first generates a new "offspring" given two randomly selected "parents" P1 and pg. One popular way is to randomly swap some nodes between these two parents (we follow (28)) Given this offspring o, we then conduct local search starting o to find new balanced partitioning strategy o" that leads better cost. We then add o" to the population and remove the worst partition candidate in the population if o" has a better cost. As suggested by (37), the combination of heuristic-based local search al algorithms and genetic algorithm can accelerate convergence by striking the balance between local and global optimum.
Existing Local Search Strategy. The key in designing this algorithm is to come up with good local search strategy. For traditional graph partitioning task, one popular choice is to use the Kernighan- Lin Algorithm (38. Which, at each iteration, tries to find pair of nodes: d in partition C, and d' in partition Cy,, to swap. To find such a pair to swap, uses the following "gain" function:
GAINKI C,) + (d', CY,)),))) = Σ Wa.d"
Σ
Wa,d"
E'
d'E
Wil at"
Wal a 2w0
d'
d" (d'')

---

where wi corresponds to the weight between node i and j in the graph. However, directly applying this local search strategy, as we will also show in the experiment (Section 4 does not work well. Greedily following GAINKI. KT. does not decrease the communication cost of foundation model training. Therefore, we have to design a new local search strategy tailored to our cost model.
Improving Local Search Strategy. Our local search strategy is inspired by two observations:
1. Removing the device di with fast connection (say with d2) within partition C, will not tend to change the data parallel cost within C,. since it is only bounded by the slowest connections.
2. Once d1 is moved to Cy,, highly likely the pipeline parallel matching between C and Cj will consist of the link d1 + d2, since it is a fast connection.
Therefore, in our local search strategy we only consider the fastest connection within Cy: d1 ++ d2 and the fastest connection within Cy: d' <> d/ and generate four swap candidates: di <> d/. di ++ 22 d2 ++ d' d2 <+ dz We use the following gain function (take di <>> d' as an example):
GAIN((d, C2) + (d', Cy)) [cyl
Σ d'ECy'
Wdy,d" Wd,,da
We Wd'
[C,l d'EC,
where [c,i Ear dd measures the expected pipeline parallel cost of connecting di with other devices in Cj before the swap, and Wdi.d2 is the cost of connecting d1 with other devices in Cj' after the swap, assuming this fast link d1 ++ d2 will now be used for pipeline parallelism.
Just like how Kernighan-Lin Algorithm multiple nodes beyond pair, we can also extend our method into a circular one, following procedure as circular KI. with new gain function.
38 can be extended to circular version 28 to swap
3.5 Other System Optimizations
We also have some system optimizations to further improve the performance. The most important optimization involves pipelining of communications and computations. We divide each stage in the pipeline into three slots: receiving slot, computation slot, and a sending slot. The receiving slot of stage needs to build connections to receive activations from the stage j in forward propagation and to receive gradients of activations from stage j ++ 1. The computation slot handles the computation in forward and backward propagation. Symmetric to the receiving slot, the sending slot of stage needs to build connections to send activations to stage j + 1 in the forward propagation and send gradients of activations to stage j 1 in the backward propagations. These three slots assigned to three CUDA streams so that they will be further pipelined efficiently; as a result, communication will overlap with computation. In the decentralized scenario (communication bound), computation be fully hidden inside the communication time.
Evaluation
We demonstrate that our system can speed up foundation model training in decentralized setting. Specifically, (1) We show that our system is 4.8x faster, in end-to-end runtime, than the state-of-the- art systems (Megatron and Deepspeed) training GPT3-L.3B in world-wide geo-distributed setting. Surprisingly, it only 1.7 2.3x slower than these systems in data centers. This indicates that we can bridge the gap between decentralized and data center training (up 100x slower networks) through scheduling and system optimization; (2) We demonstrate the necessity of our scheduler through ablation study. We show that with the scheduler, our system is 2.7 faster in world-wide geo-distributed setting.
4.1 Experimental Setup.
To simulate the decentralized setting, we use 8 different AWS regions (Oregon, Virginia, Ohio, Tokyo, Seoul, London, Frankfurt, and Ireland) and measure the latency and bandwidth between these regions (we consider the bandwidth that we can realistically obtain using NCCL and UDP hole punching between these regions). Given these measurements, we use 64 Tesla V100 GPUs and control their pairwise communication latency and bandwidth for five different cases:
7

---

(a) Network Lalency (ms)
(b) Network Bandwidth (Gbps)
(c) PFLOPS
So Si So 5S1 Net Ni Mr MZ
1.4x
Data Center Demand
Ours
1.2x
Higher PLOPS (aater
15
1.0
More Layers Larger Batch
Data Center Spot Instances
4C211 Nachine IGPU Noe lines
4021 Machins TGPU Machimes
3.0
16-
1.5x Ours
1.2x
24
51100%
40
48
56
0.0
Cliic Machinss
Vingnia Machinns
Dilio Machines, Virjaii Machines
Multiple Data Centers
2.5
1.8x Ours
1.6x
Case
Virgina Oragon CA Ohio
Virgniaa Oragon
Osio
Regional Distributed
2.0
1.5
2.2x Ours
2.0x
Toom
Soud
Drggn
Vegas
Tougs
Sendl
mand
World-wide wide Distribated
1..
Case
32
3.6x
40
1.0
3.0x
Ours
0.5
56
124
122
140
81k
92K
B1k
026
84k
B1k
B24
84L
Model Arch Richttecerres
10
20
100
200
300
0.5
100
Ours FAl Schesster
Durs (All Scholuleri
Magatron
Despapoed
Figure 3: End to end compassion of our system with Megatron and Deepspeed in 5 different scenarios. Column (a) and (b) visualize the delay and bandwidth of 5 scenario respectively; Column (c) illustrate the comparison of Megatron, Deepspeed and our system w and w/o scheduler.
Cuse 1. Data center on demand. This standard setting user can obtain train foundation models. we use 8 AWS p3. 16xlarge nodes (each with 8 V100 GPUs); the intra-node connection NVLink 300 GB/s bi-directional bandwidth (150 GB/s unidirectional), and the inter-node connection has bandwidth of 25 Gbps. We do not manually control latency and bandwidth here.

---

00-
Litimated Cost
60-
65-
150-
40-
100
20-
50-
Tlenations
llerations:
Ilerutions
Spot
Multiple
Regional Disrtbuned
World
Randem llybrid
Figure 4: Comparison of Search Strategies.
Case 2. Data center spot instances. Spot GPUs are cheaper in data center, but can be located on different types of machine. In this case, we rent 4 AWS p3. 8xlarge nodes (each with 4 V100) and 32 p3. 2xlarge nodes (each with 1 V100); the intra- p3. Sxlarge node connection has bandwidth of 100 Gbps, and the inter-node connection has a bandwidth of Gbps. We do not manually control latency and bandwidth in this case.
Case 3. Multiple Data Centers. We consider two organizations, one in Ohio and another in Virginia. each organization contributes 32 V100 GPUs; within each organization, the bandwidth is 10 Gbps, and connections cross different campuses have a delay of 10 ms and bandwidth of 1.12 Gbps.
Case 4. Regional pro-distributed. We consider individual GPUs cross four different regions in US (California, Ohio, Oregon, and Virginia): ; within each region, the delay is ms and bandwidth is Gbps; cross different regions, the delay is 10~70ms and the bandwidth is 1.0~1.3 Gbps.
Case 5. World-wide geo-distributed. We consider individual GPUs cross eight different regions world-wide (Oregon, Virginia, Ohio, Tokyo, Scoul, London, Frankfurt, and Ireland); within each region, the delay is 5 ms and bandwidth is 2 Gbps; cross different regions, the delay is 10~250ms and the bandwidth is 0.3pss
Metrics and Model Architecture. Since we do not introduce any optimizations that might change the computation or convergence, we can compare all methods by its throughput, we can compare all systems by the total number of floating point operations per second (PFLOPS), which is inverse proportional to the runtime of each iteration (which we show Appendix). We use the standard GPT3-1.3B architecture 2 while also benchmarked different number of layers (24, 32, 40J. and batch sizes [1024, 2048, 40963.
Tuning of Megatron and Deepspeed. We did a careful grid search of different parallelism settings and report the optimal results each case-in Case the optimal setting includes tensor model parallelism in Megatron and ZeRO-S3 in Deepspeed; in all other cases, the optimal settings are based on pipeline and data parallelism. We discuss more details in Appendix.
4.2 Results
End-to-end Comparison. Figure 3(c) shows the end-to-end comparison in terms of averaged PFLOPS achieved across different settings and different batch sizes and number of layers. In the world-wide geo-distributed cases, we achieve an 4.8x speedup of Megatron, (3.6x speedup of Deepspeed). While in all other cases, system can be 1.2 2.5x faster. If compare our system in Case (world-wide geo-distributed) and Megatron/Deepsspee is exciting see that the performance slowdown caused by decentralization is only 1.7 1.5x! This illustrates the great potential of decentralized training for foundation models. Additionally, Figure 3(c) illustrates another interesting behavior pattern. As increasing the batch size does not increases the communication cost of data parallelism and increasing # layers per device does not increases the communication cost of pipeline parallelism. with larger batch size and deeper model, the gap between centralized Diggatron/Deepsper and our decentralized system is even smaller.
Case (data center on demand),
Effectiveness Scheduler. To evaluate the effectiveness of the scheduler, we disable it and use random assignment in all cases and the results are also illustrated in FigureBic.. We see that with our scheduler provides up to 2.7x speeds up. To evaluate our local search strategy, we also compare our scheduler with scheduler that uses the standard Kernighan- Lin algorithm for local search, illustrated in Figure We see that, while both outperform random, our carefully designed local search strategy significantly outperforms Kemnighan-Lin

---

5 Related Work
Foundation models. Foundation models[[] refer to models that are trained on large-scale data and can be adapted (c.g., fine-tuned) to a wide range of downstream tasks. Current examples include BERT 39, GPT-3 22, and 40] Foundation models are usually trained in a data center, where the connection between GPUs is fast and homogeneous. ML infrastructures such as Megatron 4 and TO have been proposed to distribute the training of these foundation models in data center. Megatron uses AllReduce to synchronize activations in tensor model parallelism; ZeRO adopts ScatterGather to dispatch sharded parameters for layer-wise data parallelism. However, such collective communication paradigms would cause serious performance problems with slow and heterogeneous connections (see Appendix for detailed discussions).
Decentralized optimization. Decentralized training is first proposed within the scope of data paral- lelism, where each worker only synchronizes gradients with its neighbors (instead of all workers) to Recently, (0 has also modified the imple- mentation of data parallelism to support training in an open collaborative environment. Varuna [55] released by Microsoft to support the training of GPT models in spot instances from a cloud service provider, which has the potential to be extended to the open collective scenario, but there is limited consideration with respect to the challenges of heterogeneous connections.
remove the latency bottleneck [17 16 42
43 44
Volunteer computing. Distributing computationally intensive tasks over open collaborative environment has been advocated for a few decades since the development of BOINC[46); for example, the folding @ home project [13] has been running simulations about protein dynamics volunteers' personal computers for more than 20 years. Recently, the learning @ home project [99] starts consider training of mixture-of-expert transformers in such volunteer computing setting.
6 Conclusion
In this paper, we probe the opportunity to train foundation models via a decentralized training regime with devices connected over heterogeneous network. We propose effective scheduling algorithm to assign tasklets from the foundation model pre-train computation. Empirical studies suggest that, in the worldwide geo-distributed scenario, our proposed scheduling algorithm enables 4.8x speed- up compared to prior state-of-the-ar training systems. We believe that the decentralization and democratization of the training of FMs can shift the balance of power positively, but also necessitate new governance structures to help ensure the responsible development and deployment of FMs.
Acknowledgments
CZ and the DS3Lab gratefully acknowledge the support from the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.0003 (for European Research Council (ERC) Starting Grant TRIDENT 101042665), the Swiss National Science Foundation (Project Number 200021 184628, and 197485), Innosuisse/SNF BRIDGE Discovery (Project Number 40B2-0 187132), European Union Horizon 2020 Research and Innovation Programme (DAPHNE, 957407), Botnar Research Centre for Child Health, Swiss Data Science Center, Alibaba, Cisco, eBay, Google Focused Research Awards, Kuaishou Inc., Oracle Labs, Zurich Insurance, and the Department Computer Science at ETH Zurich. CR gratefully acknowledges the support of NIH under No. U54EB020405 (Mobilize). NSF under Nos. CCF1763315 (Beyond Sparsity), CCF1563078 (Volume to Velocity), and 1937301 (RTML); ARL under No. W91 W991NNF-11 21-2-2251 (Intcractive Human-Al Teaming); ONR under No. N000141712266 (Unifying Weak Supervision); ONR N00014-20-14 1--20---2480; Understanding and Applying Non- aunEuulidean Geometry in Machine Learning: N000142012275 (NEPTUNE);
NXP. Xilinx. LETI-CEA, Intel, IBM, Microsoft, NEC, Toshiba, TSMC, ARM, Hitachi, BASF, Accenture. Ericsson, Qualcomm, Analog Devices, Google Cloud, Salesforce, Total, the HAI-GCP Cloud Credits for Research program, the Stanford Data Science Initiative (SDSI), and members of the Stanford DAWN project: Facebook, Google, and VMWare. The U.S. Government authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Any opinions. findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views, policies, endorsements, either expressed or implied, of NIH, ONR, the U.S. This work supported hy an Open Philanthropy Award. The computation required in this work was provided by Together Computer https://togethn .xzz/
10

---

References
[1] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108 07258, 2021.
[2] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neclakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[3] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.00311111 2022.
[4] Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-Im: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv:1909.0800 2019.
[5] Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He. Deepspeed: System optimizations enable training deep learning models with over 100 billion parameters. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 3505-350K 2020.
[6] Mandeep Baines, Shruti Bhosale, Vittorio Caggiano, Naman Goyal, Siddharth Goyal, Myle Out, Benjamin Lefaudeux, Vitaliy Liptchinsky, Mike Rabbat, Sam Sheiffer, et al. Fairscale: A general purpose modular pytorch library for high performance and large scale training. 2021.
[7] Yuanzhong Xu, HyoukJoong Lee, Dehao Chen, Blake Hechtman, Yanping Huang. Rahul Joshi, Maxim Krikun, Dmitry Lepikhin, Andy Ly, Marcello Maggioni, et al. Gspmd: general and scalable parallelization for ml computation graphs. arXiv preprint orXiv:2105, 105.:2205.00663,, 2021.
[8] Lianmin Zheng, Zhuohan Li, Hao Zhang, Yonghao Zhuang, Zhifeng Chen, Yanping Huang, Yida Wang, Yuanzhong Xu, Danyang Zhuo, Joseph E Gonzalez, et al. Alpa: Automating inter- and intra-operator parallelism for distributed deep learning, arXiv preprint arXiv:2201.12023; 2022.
[9] Zhuohan Li, Siyuan Zhuang, Shiyuan Guo, Danyang Zhuo Hao Zhang, Dawn Song, and Ion Stoica. Terapipe: Token-level pipeline parallelism for training large-scale language models. In International Conference on Machine Learning, pages 6543-6552. PMLR, 2021.
[10] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. Zero: Memory optimiza- tions toward training trillion parameter models. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-16. IEEE, 2020.
[11] Jie Ren, Samyam Rajbhandari, Reza Yazdani Aminabadi, Olatunji Ruwase, Shuangyan Yang, Minjia Zhang, Dong Li, and Yuxiong He. [ZeRO-Ofilond Democratizing (Billion-Scale model training. In 2021 USENIX Annual Technical Conference (USENIX ATC 21), pages
551-564, 2021.
[12] Q4'21 sees to-quarter. q421 sie-ssess--e -omeinal-ominal--ae
nominal
rise in gpu and pc shipments quarter- https://www. jonpeddi comppress-reeeateeee gpu-guuaaa and pc- shi pments quarter- to-
[13] Michael Shirts and Vijay S Pande. Screen savers of the world unite! Science, 290(5498):1903-
1904, 2000.
[14] OS Statistics. httpp://stats..fllligtttooo httpp:/reatuurbbaa.cco/////////1 2022].
2022. [Online; accessed 15-May-
[15] Gpu economics cost analysis. tta.-raa--cootto---niii-------i-
[16] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
11

---

[17] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pages 3478-3488 PMLR, 2019.
[18] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393. PMLR, 2020.
[19] Max Ryabinin and Anton Gusev. Towards crowdsourced training of large neural networks using decentralized tixture-of-experts Advances in Neural Information Processing Systems, 33:3659-3677 2020.
[20] Michael Diskin, Alexey Bukhtiyarov, Max Ryabinin, Lucile Saulnier, Anton Sinitsin, Dmitry Popov, Dmitry V Pyrkin, Maxim Kashirin, Alexander Borzunov, Albert Villanova del Moral, et al. Distributed deep learning in open collaborations. Advances in Neural Information Processing Systems, 34:7879-7897, 2021.
[21] Nan Du Yanping Huang, Andrew M. Dai, Simon Tong, Dmitry Lepikhin, Yuanzhong Xu, Maxim Krikun, Yanqi Zhou, Adams Wei Yu, Orhan Firat, Barret Zoph, Liam Fedus, Maarten Bosma, Zongwei Zhou, Tao Wang, Yu Emma Wang, Kellie Webster, Marie Pellat, Kevin Robinson, Kathy Meier-Hellstern, Toju Duke, Lucas Dixon, Kun Zhang, Quoc V. Le, Yonghui Wu, Zhifeng Chen, and Claire Cui. Glam: Efficient scaling of language models with mixture- of-experts. CoRR, abs/21 12.0690.9.. 2021.
[22] Deepak Narayanan, Aaron Harlap, Amar Phanishayee, Vivek Seshadri, Nikhil R Devanur, Gregory R Ganger, Phillip B Gibbons, and Matei Zaharia. Pipedream: generalized pipeline parallelism for dnn training. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, pages 1-15, 2019.
[23] Jakub M Tarnawski, Amar Phanishayee, Nikhil Devanur, Divya Mahajan, and Fanny Nina Par- avecino. Efficient algorithms for device placement of dnn graph operators. Advances in Neural Information Processing Systems, 1451-114636. 2020.
[24] Jakub M Tarnawski, Deepak Narayanan, and Amar Phanishayee. Piper: Multidimensional planner for dnn parallelization. Advances in Neural Information Processing Systems, 34, 2021.
[25] Shiqing Fan, Yi Rong, Chen Meng, Zongyan Cao, Siyu Wang, Zhen Zheng, Chuan Wu, Guoping Long, Jun Yang, Lixue Xia, et al. Dapple: A pipelined data parallel approach for training large models. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 431 441, 2021.
[26] Jay H Park, Gyeongehan Yun, M Yi Chang, Nguyen T Nguyen, Seungmin Lee, Jaesik Choi, Sam H Noh, and Young-ri Choi. (HetPipe}: Enabling large (DNN} training on (whimpy) heterogeneous {GPU) clusters through integration of pipelined model parallelism and data parallelism. In 2020 USENIX Anmual Technical Conference (USENIX ATC 20), pages 307-321, 2020.
[27] Christos H Papadimitriou. The euclidean travelling salesman problem is no-complcte. Theoreti- cal computer science, (3))2237-244, 1977.
[28] So-Jin Kang and Byung-Ro Moon. A hybrid genetic algorithm for multiway graph partitioning. In Proceedings of the 2nd Annual Conference Genetic and Evolutionary Computation, pages 159-166. Citeseer, 2000.
[29] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[30] Alexander Sergeev and Mike Del Balso. Horovod: fast and easy distributed deep learning in tensorflow. arXiv preprint arXiv: 2018.
12

---

[31] Yimin Jiang, Yibo Zhu, Chang Lan, Bairen Yi. Yong Cui, and Chuanxiong Guo. A unified architecture for accelerating distributed (DNN) training in heterogeneous (GPU/CPU) clusters. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20),
pages 463-479, 2020.
[32] Michel X Goemans. Lecture notes on bipartite matching. Massachusetts Institute of Technology. 2009.
[33] Michael R Garey and David S Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979.
[34] Konstantin Andreev and Harald Racke. Balanced graph partitioning, Theory of Computing Systems, 39(6);29-933, 2006.
[35] Peter Sanders and Christian Schulz. Think locally, act globally: Highly balanced graph partitioning. In International Symposium on Experimental Algorithms, pages 164-175. Springer, 2013.
[36] Aydın Buluç. Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent advances in graph partitioning. Algorithm engineering, pages 117-158, 2016.
[37] Tarek A El-Mihoub, Adrian A Hopgood, Lars Nolle, and Alan Battersby. Hybrid genetic algorithms: A review. Eng. Lett., 13(2): 2006.
[38] Thang Nguyen Bui and Byung Ro Moon. Genetic algorithm and graph partitioning, IEEE Transactions on computers, 45(7):841 855, 1996.
[39] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 2018.
[40] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pages 8748 8763. PMLR, 2021.
[41] Youjie Li, Mingchao Yu, Songze Li, Salman Avestimehr, Nam Sung Kim, and Alexander Schwing. Pipe-sgd: decentralized pipelined sgd framework for distributed deep net training. In Proceedings of the 32nd Intermational Conference on Neural Information Processing Systems, pages 8056-8067, 2018.
[42] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. International Conference on Machine Learning, pages 3043-3052. PMIR, 2018.
[43] Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentralized training. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 7663-7673, 2018.
[44] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D2: Decentralized training over decentralized data. In International Conference on Machine Learning, pages 4848-4856. PMLR, 2018.
[45] Sanjith Athlur, Nitika Saran, Muthian Sivathanu, Ramachandran Ramjee, and Nipun Kwatra. Varuna: scalable, low-cost training of massive deep learning models. In Proceedings of the Seventeenth European Conference on Computer Systems, pages 472-487, 2022.
[46] David Anderson. Boinc: A system for public-resource computing and storage. In Fifth IEEE/ACM international workshop grid computing, pages 4-10. IEEE, 2004.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In lines 122-124 124 of the Problem
Formulation, we highlight the core limitations and simplifying assumptions.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In lines 364-366 of the Conclusion, we discuss the potential negative impact of decentralization and democratization, noting that while there are positives, this can also lead to acceler- ation and lack of control. We look forward to actively engaging with the community on questions of governance.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] We fully follow the standard settings for GPT3-1.3B training.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] We repeated all the experiments for at least three times and reported the average in the paper. Details reported in Appendix.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] Our systems was built on PyTorch and CuPy and was evaluated using publicly available datasets. All of them use open-source licenses and can be used for nom-commercial educational purposes.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "r_Ru4M0ZV1i", "reviewer": "Reviewer_TDE8", "summary": "Proposes techniques for scheduling training tasks in decentralized heterogenous clusters. ", "questions": "* why not compare against other state of the art approaches such as\n\n1. Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He. Deepspeed: System optimizations enable training deep learning models with over 100 billion parameters. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3505–3506, 2020\n\n2. Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGresley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, et al. Efficient large-scale language model training on gpu clusters using megatron-lm. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–15, 2021.\n\n* It is not clear as to why there is a need for two-level optimization. Many of the cost functions are rather heuristic-driven. Is there a space for employing RL techniques for scheduling as suggested by others \"Shyalika, Chathurangi, Thushari Silva, and Asoka Karunananda. \"Reinforcement learning in dynamic task scheduling: A review.\"", "limitations": "* The related work and comparison could have been better.\n\n* Exploration of newer techniques for optimization rather than using genetic algorithms", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths\n---\n* achieves good speed up over Megatron in the decentralized setting\n* only 2x slower in such decentralized setting even though the bandwidth/latency is several orders slower when going geo distributed\n* 2 level scheduling models is intuitive\n\nWeakness\n---\n\n* Ignores some of the latest innovation in Tensor model-parallel (TMP) strategies\n* Ignores the fact that GPUs may itself be of different types across geos\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RXMWmioDUSa", "reviewer": "Reviewer_BmFa", "summary": "The authors propose a system for training large language models on hardware connected over the public internet and distributed around the world. This is a difficult problem (EleutherAI writes that “doing volunteer-driven distributed compute well for this use case is an unsolved problem”) and the authors tackle it with a combination of pipelining and data parallelism.\n\nAs this setting can’t assume homogeneous network performance, the parallelism assignment problem is much more difficult than it is in datacenters, and the authors apply a novel combination of algorithmic approaches to solve it, including treating pipelining and data parallelism independently and scheduling parallel units onto workers using an evolutionary algorithm.\n\nThe authors report benchmark results on a series of increasingly heterogeneous network configurations, showing significant speedup relative to a grid-search-optimized Megatron setup with homogeneous data and pipeline parallelism.\n", "questions": "How much do you lose by decomposing the assignment problem into separate data and pipeline levels? I think the answer might be “nothing”, but it would be great to be more explicit about that.\n\nThe intra-node bandwidth is quoted as 100 Gb/s in your experiments, but IIUC V100 NVlink is 150 GB/s (1200 Gb/s); is there a reason this isn’t the right number to use for intra-node bandwidth? And in general, are the bandwidths you’re assuming the result of benchmarks? If so, maybe include those benchmarks somewhere?\n\nWere the benchmarks run on cloud machines that were really physically located in different regions, or were the bandwidths between machines limited artificially to simulate inter-region connections?\n", "limitations": "The authors are clear about most of the limitations of their system, including lack of online failure handling and dynamic replanning.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors do a good job of motivating the problem and pointing out weaknesses in existing systems (e.g. a focus on data parallelism or mixture-of-experts models).\n\nThe paper uses the terminology “macro-batch” but it’s sometimes unclear whether this refers to the portion of the global batch that runs on one data-parallel replica, or to the portion that runs on one stage of one data-parallel replica (more often called a microbatch). I’d recommend being a little clearer here.\n\nThe algorithm the authors introduce seems reasonable and well-motivated. If it’s fast enough, and if decomposing the assignment problem into separate data and pipeline levels isn’t a restrictive assumption (both of these appear to be true!) then it also seems like the only algorithm we need for this problem. (It might be possible to optimize in an even greedier way, but if the evolutionary approach is fast enough I’m not sure it matters).\n\nI’m somewhat disappointed that a system for heterogeneous distributed training (justified in part by a seemingly accurate claim that home electricity is 50-100x cheaper than spot GPU instances) was benchmarked only on cloud machines with cloud networking, not on machines with conventional home internet. But it looks like the bandwidth between distant datacenters in the authors’ experiments is low enough that it might be representative of home network connections.\n\nThe authors present good benchmarks against grid-search-optimized Megatron configurations, and their ablations, although brief, are convincing about the value of their local search strategy.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6GO9ZYbezh", "reviewer": "Reviewer_rKen", "summary": "The work develops communication-efficient schedulers for parallel sub-units for the geo-distributed low-bandwidth high-latency training of GPT-2-style transformer language models. Both data-parallel sub-units (gradient communication) and pipeline-parallel sub-units (activation communication) are considered. The sub-units are optimized using statistics of latency and bandwidth together with a global genetic algorithm with local node-swap optimization (similar to Kernighan-Lin).\n", "questions": "Questions:\n\nHow does your approach scale vs Megatron as you scale the model?\n\nComments:\n- Typo in line 226: generic = genetic\n- Figure 4: It would be better to replace case 1,2... with On Demand, Spot, multiple DC, regional, world-wide. If you can find room, it would be beneficial to enlarge this figure as it is an important results that deserves a little more attention.\n- It is better to refer to GPT3-XL by the number of parameters, that is, GPT-3 1.3B\n", "limitations": "A few limitations are discussed in the paper, but no separate limitation section exists. Ethical considerations should be explored. Making large model training more accessible to not require a supercomputer-quality network increases accessibility both for small institutions (democratization) but might also favor those that already have the most resources more (companies buying all the cloud GPUs that they can find world-wide, to train large neural networks cheaply)", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The presentation is excellent. The writing is very clear, figures help with understanding and math is used appropriately.\n- The evaluations are robust and extensive. The experiments were conducted in real geo-distributed settings.\n- Ablations provide insight into baseline Kernighan-Lin search vs improved swapping algorithm\n\nWeaknesses:\n- Failure of nodes/GPUs is not discussed but mentioned as a limitation\n\nThis is one of the best papers that I read in this area for a while and I am happy to champion the paper and fight for its acceptance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept