YEO ET AL.

*Sangyoon Oh, World cup-ro 206, Yeongtong-gu, Suwon-si, Gyeonggi-do, Republic of Korea. National Supercomputing Center with supercomputing resources including technical support (KSC-2019-CRE-0105), the MSIT (Ministry of Science and ICT),Korea, under the ITRC (Information Technology Research Center) support program (IITP-2020-2018-0-01431) supervised by the IITP (Institute for Information communications Technology Promotion), Basic Science Research Program Through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2018R1D1A1B07043858), and Electronics and Telecommunications Research Institute (ETRI) grant funded by the Korean government (20ZT1100, Development of ICT Convergence Technology based on Urban Area),

# Crossover-SGD: A gossip-based communication in distributed deep learning for
alleviating large mini-batch problem and enhancing scalability

Sangho Yeo  Minho Bae  Minjoong Jeong  Oh-Kyoung Kwon  Sangyoon Oh  Department
of Artificial Intelligence, Ajou University, Suwon, Republic of Korea
Artificial Intelligence Convergence Research Section, ETRI, Seongnam, Republic
of Korea  Supercomputing Department, Korea Institute of Science and
Technology, Daejeon, Republic of Korea<EMAIL_ADDRESS>
###### Abstract

[Abstract]Distributed deep learning is an effective way to reduce the training
time of deep learning for large datasets as well as complex models. However,
the limited scalability caused by network overheads makes it difficult to
synchronize the parameters of all workers. To resolve this problem, gossip-
based methods that demonstrates stable scalability regardless of the number of
workers have been proposed. However, to use gossip-based methods in general
cases, the validation accuracy for a large mini-batch needs to be verified. To
verify this, we first empirically study the characteristics of gossip methods
in a large mini-batch problem and observe that the gossip methods preserve
higher validation accuracy than AllReduce-SGD(Stochastic Gradient Descent)
when the number of batch sizes is increased and the number of workers is
fixed. However, the delayed parameter propagation of the gossip-based models
decreases validation accuracy in large node scales. To cope with this problem,
we propose Crossover-SGD that alleviates the delay propagation of weight
parameters via segment-wise communication and load balancing random network
topology. We also adapt hierarchical communication to limit the number of
workers in gossip-based communication methods. To validate the effectiveness
of our proposed method, we conduct empirical experiments and observe that our
Crossover-SGD shows higher node scalability than SGP(Stochastic Gradient
Push).

###### keywords:

distributed deep learning, gossip based, hierarchical communication, large
mini-batch problem, segment-wise

††articletype: SPECIAL ISSUE PAPER

##  1 Introduction

Recently, there has been an increased application of machine learning and deep
learning in knowledge discovery and intelligent services. The main reason for
this development is the successful convergence of the advances in deep
learning algorithms and techniques (e.g., pretraining, ReLU activation
function, and regularization) and considerable big data generated from various
Internet of Things (IoT) devices and smartphones. However, there is still
scope for improvement in deep learning performance because it still takes
several days to train a single machine with large-scale data. Thus,
researchers have attempted to reduce the training time of large-scale data by
utilizing a distributed deep learning framework on the massive computing
capacity of supercomputers or graphic processing unit (GPU) clusters. Using
multiple workers, deep learning models that require several days to train on a
single node can be trained in hours or minutes. For example, the ResNet50
model took 8,831.3 min (i.e., 6 days) to achieve 75.9% validation accuracy
when only one P100 GPU was used. Utilizing multiple advanced GPUs for
training, Yamazaki et al. reduced this training time to almost 1 min 1.

The major advantage of distributed deep learning is that the amount of
computation on each node decreases with an increase in the number of nodes.
However, distributed deep learning algorithms were originally designed to
synchronize the model parameters on all nodes (i.e., AllReduce-SGD), and there
are inevitable communication overheads for synchronization between large-scale
participating nodes; thus, obtaining the full benefits of parallel processing
is difficult owing to the network overhead.

The simplest way to resolve this is to sufficiently increase the amount of
work on each node (i.e., increase the size of the mini-batch) to reduce the
synchronization frequency. This solution addresses the problem well because
the communication overhead becomes relatively smaller than the computation
overhead when the synchronization frequency is reduced. However, this does not
solve the large mini-batch problem 2, wherein the model accuracy degrades as
the size of the batch increases; moreover, we cannot significantly increase
the global mini-batch size. Thus, the large mini-batch problem has become a
key issue to be addressed for improving the performance of distributed deep
learning. To alleviate the large mini-batch problem, many effective techniques
have been proposed. In particular, LARS (Layer-wise Adaptive Rate Scaling) 3
has been developed; LARS is a widely used layer-wise learning rate scaling
technique for stabilizing the training process of distributed deep learning.
This layer-wise learning rate scaling adapts the learning rate of each layer
by the ratio of the weight norm to the gradient norm. As a result, LARS does
not allow the layers to diverge when a high learning rate is set. However,
this approach still uses AllReduce-SGD and has not been validated in other
communication methods.

There are two other approaches that adapt a network communication scheme for
parameter synchronization. The first approach involves the segmentation of
models into chunks of layers (i.e., segments). Using segment-wise
communication 4, 5, 6, 7, 8, the network bandwidth of each worker node can be
used more efficiently than in layer-wise or model-wise communication. In
particular, Horovod 4 which is a well-known distributed deep learning
communication library, utilizes a segment-wise communication scheme (i.e.,
tensor fusion) to reduce network overhead.

Studies following the second approach attempt to provide novel parameter
synchronization approaches instead of the AllReduce-SGD scheme to alleviate
network communication overhead increased due to the increased number of
participating nodes. Gossip-based communication, which is a widely studied
communication method, effectively reduces network overhead for synchronization
9, 10, 11, 12. In the gossip-based method, it is not necessary for each worker
process to be synchronized with all other processes. Instead, each worker
process communicates with a few other worker processes that are selected using
a predefined network topology at every training step. Thus, these methods show
linear speed-up even when numerous worker processes are added, unlike
AllReduce-SGD. However, in gossip-based methods, the propagation delay of the
weight parameters results in an additional decrease in the validation accuracy
with a large mini-batch problem. Thus, although the gossiping-SGD scheme has
the advantage of low network overhead, we cannot increase the number of
workers as desired. As a result, it is only advantageous in relatively small
mini-batches in small clusters.

In summary, increasing the size of the mini-batch has the advantage of
scalability by reducing the synchronization frequency but still has heavy
network traffic owing to the use of the AllReduce-SGD scheme. Conversely, the
gossip-based SGD scheme reduces the network traffic itself, but the accuracy
in the large mini-batch problem, which should be analyzed on large-scale
nodes, has not been verified. Therefore, we studied the validation accuracy of
gossip-based methods under the condition of large mini-batch problems. In this
analysis, we verified that gossip-based SGD can achieve higher accuracy than
AllReduce-SGD with fixed number of worker nodes and that expanding node
scalability is crucial by alleviating delay propagation of parameters in order
to fully utilize this characteristic of gossip-based SGD.

To alleviate the node scalability problem of gossip-based SGD, we propose a
novel segment-wise communication scheme, called Crossover-SGD, based on the
gossiping-SGD algorithm for high node scalability. Our proposed Crossover-SGD
is inspired by the uniform crossover method 13 of genetic algorithm; however,
the detailed method of Crossover-SGD is different from that of genetic
algorithm. For fast and direct propagation of the weight parameter, we section
the model into segments and utilize the overlapped segment-wise communication
and load-balancing random network topology. By overlapping segment-wise
communication and load-balancing random network topology, Crossover-SGD
achieves higher and more robust accuracy with increasing mini-batch size in
large mini-batch problem conditions; it also has higher node scalability with
regard to validation accuracy. Furthermore, we adapt the hierarchical
communication method 14, 15 to Crossover-SGD to limit the number of workers
communicating using gossip-based communication.

The contributions of our study are as follows:

  * •

We propose a novel load-balancing random network topology and observe that
this random network topology is better than directed exponential network
topology, which is used in SGP. This result is valuable because the
utilization of random network topology has been avoided in previous studies
owing to its unbalanced communication.

  * •

We analyze gossip-based methods in large mini-batch problem conditions with
state-of-the-art techniques (e.g., LARS). In this evaluation, we verify that
the gossip-based methods can achieve higher validation accuracy than
AllReduce-SGD with fixed number of worker nodes owing to their exploration
characteristics caused by the slightly different weights of each worker
process.

  * •

We compare SGP, Crossover-SGD, and AllReduce-SGD in a high-performance GPU
cluster environment requiring high cost. Through evaluations of this cluster
environment, we obtain expensive results from many perspectives (i.e.,
increasing mini-batch size, worker size, and time efficiency) in large mini-
batch problem conditions, which have not been evaluated in previous studies.
As a result, we verify that Crossover-SGD and hierarchical Crossover-SGD are
stronger contenders to AllReduce-SGD than SGP while preserving the time
efficiency of gossip-based methods.

The remainder of this paper is organized as follows. In Section 2, we present
related works on both gossip-based and segment-wise communication optimization
of distributed deep learning. We represent our proposed method, Crossover-SGD,
in Section 3 We then present our results and discussion in Section 4.
Specifically, Section 4.2 presents the analysis of gossip-based methods in
large mini-batch problem conditions. Section 4.3 comprises a comparison of
node scalability and Section 4.4 presents a comparison on time efficiency.
Finally, we provide concluding statements in Section 5.

##  2 Related Works

Recently, the optimization of network overhead in distributed deep learning
has been a topic of considerable research interest. For our study, we explored
two categories of researches: gossip-based distributed deep learning and
segment-wise communication optimization in distributed deep learning.

###  2.1 Gossip-based communication methods in distributed deep learning

Common distributed deep learning synchronizes the model parameters of all
nodes at each iteration. The problem with this kind of synchronization is the
increase in the network overhead with the number of nodes. To resolve this
problem, distributed deep learning with parameter servers communicates each
node in an asynchronous manner 16, 17, 18. Elastic Averaging SGD (EA-SGD) 18,
which is one of asynchronous methods, is a communication method utilizing the
exploration of weight parameters for training. In detail, EA-SGD does not
synchronize all model parameters. Instead, it makes a slight difference
between the global and local models to explore the averaged model parameters.

In centralized asynchronous communication methods, the network overhead is
concentrated in a few parameter servers. Therefore, decentralized gossip-based
methods have been developed to spread the concentrated network overhead to
every worker node. DP-SGD 10 is a significant research on gossip-based
distributed deep learning. This method shows that gossip-based communication
methods can achieve similar accuracy as AllReduce-SGD when the number of
worker nodes is limited to a small number. ADP-SGD 11 is an asynchronous
version of DP-SGD. It shows that asynchronous and decentralized distributed
deep learning can achieve convergence accuracy similar to that of AllReduce-
SGD.

Assran et al. 12 proposed the latest well-known method of decentralized deep
learning, stochastic gradient push (SGP). They adopted the SGP for distributed
deep learning. There are two main differences between the SGP method and the
previous DP-SGD and ADP-SGD. The first difference is the push-sum mechanism.
This mechanism can spread the parameter information faster than previous
studies because it is not necessary for the sender and receiver of the
information to be the same. The second difference is the time-varying graph
for the network topology. Using a time-varying graph, the model information
can be sent to multiple locations.

Figure 1 shows three representative gossip-based communications in distributed
deep learning. These three methods are slightly different from each other. For
example, DP-SGD communicates with others using a bidirectional ring network
topology. In ADP-SGD, the workers are divided into two types. The first type
is the active (i.e., A in the figure) workers, and the second type is the
passive (i.e., P in the figure) workers. The passive workers act as parameter
servers. Thus, it does not actively communicate with others; however, if a
request for communication comes, it communicates with others. An active worker
is one who can initiate the communication of passive workers. Two types of
workers are configured to resolve the deadlock issue caused by asynchronous
communication. Finally, SGP utilizes directional network topology, and unlike
other methods, it uses time-varying network topology, as mentioned earlier.

Figure 1: Overview of previous gossip-based methods

###  2.2 Segment-wise communication optimization in distributed deep learning

Segment-wise control for communication optimization has been continuously
studied in distributed deep learning. It is difficult to communicate at once
in the model used in distributed deep learning owing to its size; however,
layer-wise communication leads to underutilization of network bandwidth. Thus,
merging multiple layers into one large layer (i.e., tensor fusion 4) is
efficient for communicating in a cluster environment. Figure 2 shows an
overview of the tensor fusion. The transformation process between layers and
segments is necessary because the number of layers is different from the
number of segments, which is the chunk of layers created by tensor fusion.

Tensor fusion can be efficiently used in ring-AllReduce, which is a
communication method for distributed deep learning that sets segments created
by tensor fusion as the unit of communication. Many advanced methods have been
proposed after tensor fusion. For example, lazy AllReduce 5 defines a memory
pool to stack the tensor of layers onto the same places; subsequently, the
size of the stacked tensor exceeds the threshold $\theta$, and the ring-
AllReduce process starts. More recently, optimal merged gradient
sparsification with SGD (OMGS-SGD) 6 was proposed to obtain an optimal merged
size considering both gradient sparsification and overlapping between
communication and computation. To obtain the optimal size of merged tensors, a
mathematical model was analyzed and defined by verifying whether merging the
neighbor layer shortens the training time. As a result, OMGS-SGD has the
advantage of adaptively defining merging layers in various models.

Figure 2: Overview of DNN model segment

Many methods have been proposed to merge multiple layers into one large layer
to effectively communicate with other processes in distributed deep learning.
However, only a few methods have been proposed for gossip-based methods. In
gossip-based methods, model segmentation is mainly used for selecting
different network topologies on each layer/segment for direct diffusion of
gradients/parameters. GossipGrad 9 was the first method proposed that
considers the layer-wise selection of a partner (i.e., peer-to-send weight
parameter) at each layer. In their study, Layer-wise selection of partners is
considered in asynchronous SGD (AGD) 16 which is comparing targets for
GossipGraD; however, layer-wise selection is not applied in GossipGraD method.
Instead, GossipGraD applies batch-wise gossip that selects a changed partner
in each training step and changes the network topology at every
$log_{2}(the\,number\,of\,worker\,nodes)$ train step to select diverse partner
processes for a fast diffusion of weight parameters. In federated learning,
COMBO 8 was proposed to reduce network bandwidth utilization in each
communication. COMBO selects the worker process using a random network
topology with constraints to select all workers at least once as peer when
constructing the entire DNN model for the next step. However, this constraint
on worker selection does not balance the network overhead among workers at
each training step.

##  3 Crossover-SGD

Our analysis of gossip methods in the large mini-batch problem conditions with
fixed number of worker nodes (explained later in Section 4.2) shows that as
the number of mini-batch increases, gossip-based methods actually show higher
validation accuracy than AllReduce-SGD. Thus, increasing the speed of
parameter propagation of gossip-based SGD becomes a crucial point to utilize
the high accuracy of gossip-based SGD when a large mini-batch problem occurs.
Crossover-SGD is a novel gossip communication method that utilizes (i)
overlapped segment-wise communication and (ii) load-balancing random network
topology with the following features.

  * •

Overlapped segment-wise communication : In COMBO 8, segment-wise communication
is helpful in utilizing the limited network bandwidth of the federated
learning environment. In addition, in GossipGraD 9, layer-wise gossip can be
utilized for the fast propagation of weight parameters. By analyzing these two
approaches, we conclude that segment-wise communication can more quickly
propagate the weight parameter to other worker nodes as well as use network
bandwidth efficiently.

  * •

Load balanced random network toplogy : In GossipGraD 9, the network topology
is changed at every $log_{2}(the\,number\,of\,worker\,nodes)$ step for direct
diffusion of the weight parameter. Inspired by this approach, we utilize
random network topology for our communication methods. However, random network
topology does not fit well in distributed deep learning owing to the
possibility of unbalanced communication among nodes. Thus, we propose a novel
random network topology that avoids unbalanced network overhead.

Crossover-SGD is similar to COMBO in terms of segment-wise communication
However, COMBO mainly considers the low network bandwidth of federated
learning environment and effectively utilizes the low network bandwidth with
segment-wise communication. However, It does not consider load balancing
between worker nodes well; thus, an unbalanced network load among worker nodes
can increase the entire training time for federated learning; in addition,
COMBO does not need to consider the large mini-batch problem because federated
learning sets smaller local-mini-batch sizes, thereby reducing the large mini-
batch problem. However, this small local-mini-batch size cannot adapt to a
common GPU cluster owing to its low utilization of GPUs. As a result, COMBO 8
is difficult to utilize in a large mini-batch problem setting. GossipGraD 9 is
proposed for the fast propagation of the weight parameter, which is similar to
the purpose of Crossover-SGD. However, Crossover-SGD utilizes different
network topologies and is based on segment-wise communication, unlike
GossipGraD, which is based on batch-wise gossip.

When Crossover-SGD is compared to SGP 12, which is the state-of-the-art gossip
communication method for distributed deep learning, we observe that SGP has
load-balancing network topology similar to Crossover-SGD. However, SGP uses
model-wise communication and directed exponential network topology to balance
the network communication overhead and fair communication between worker
nodes. These two differences affect the weight parameter propagation speed
among nodes because the entire model parameter is sent to the worker node with
directed exponential network topology that can select only limited workers in
the worker node group. Thus, the validation accuracy of Crossover-SGD is
higher than that of SGP for a large mini-batch problem.

Figure 3: Overview of Crossover-SGD

Crossover-SGD is a gossip communication method based on segment-wise
communication and random network topology. Figure 3 shows an overview of
Crossover-SGD. We discuss the three parts of the Crossover-SGD in detail. The
first part involves flattening multiple tensors into one large segment or
unflattening the tensors to apply the received tensor into a layer-wise model.
In particular, a segment is a group of multiple layers in the model. Thus, we
can more efficiently utilize the network bandwidth than layer-wise
communication and reduce bottlenecks caused by model-wise communication.

The second part creates a load-balancing random network topology for each
segment. The flattened tensor (i.e., segment) is communicated among worker
nodes based on a load-balancing random network topology. If we set the same
network topology on every segment of the model, the result of the
communication is equal to that of model-wise communication. Thus, we set
different random network topologies for each segment, as shown in the bottom
left of Figure 3

The third part is the overlapped segment-wise communication. After we set a
random network topology for each segment, the worker nodes are communicated
based on the random network topology. To use the network bandwidth of each
node efficiently, we overlap the segment-wise communication. If the gossip
communication process of the whole model is completed, the flattened tensor is
flattened to multiple layers to merge the received segment to the DNN model of
each rank. A detailed description of our proposed methods is presented in
Sections 3.1 and 3.2. We also explain variants of our method utilizing
hierarchical communication to increase node scalability with regard to
validation accuracy in Section 3.3.

###  3.1 Overlapped segment-wise communication of Crossover-SGD

Segment-wise gossip communication 8 is an efficient method when the model
suffers from network overhead; however, it is difficult to overlap
communication with computation because parameter averaging is processed after
the gradient is applied to the weight parameters. In addition, segment-wise
communication is effective in terms of usage of network bandwidth. However, it
increases network latency compared to model-wise communication, which is
widely used in distributed deep learning. This latency problem of segment-wise
communication occurs because each layer communicates sequentially. For
effective segment-wise communication, we overlap segment-wise communication
using asynchronous send and receive.

Algorithm 1 Overlapped Segment-wise Communication

1: model segments : segments of current training model, my rank : rank ID of
current process,
rseed : random seed which is shared by every process, world_size : the total
number of training process,
roulettes : probability table of all processes which is used to select
destination rank,
send_list, recv_list : list for saving send and recv distributed request
object

2: part_model : partial DNN model corresponding to the current unflattened
segment

3:for i=1…len(model,segments) do $\triangleright$ request send and recv of
each segment asynchronously

4: $segment\leftarrow\textit{model\,segment[i]}$

5: $tensor\\_flatten\leftarrow flatten\\_tensors(segment)$ $\triangleright$
transform multiple tensors into one large tensor for communication

6: $destinations=select\\_destinations(rseed,world\\_size,roulettes)$
$\triangleright$ select destination rank of all ranks by load balanced random
topology

7: $receive\\_from=destinations[my\,rank]$

8: $send\\_to=destinations.index[my\,rank]$

9: $completed\\_send=isend(segment,send\\_to)$ $\triangleright$ asynchronously
send segment

10: $completed\\_recv=irecv(segment,recv\\_to)$ $\triangleright$
asynchronously receive segment

11:
$append\,completed\\_send\,to\,send\\_list,\,append\,completed\\_recv\,to\,recv\\_list$

12:end for

13:$n\leftarrow 0$

14:for send, recv in zip (send_list, recv_list) do

15: $\textbf{wait}\,send\,and\,recv$ $\triangleright$ wait until communication
of all segments are completed

16: $segment\leftarrow\textit{model segment[n]},n++;$

17: $tensor\\_unflatten=unflatten\\_tensors(segment)$ $\triangleright$
transform one large tensor into multiple tensors for merging weight parameter
to model

18: for layer, received_layer in zip (part_model, tensor_unflatten) do

19: $layer=(layer+received\\_layer)\,/\,2$

20: end for

21:end for

Algorithm 1 shows the process of overlapped segment-wise communication in
Crossover-SGD. In lines 1–10, it sends and receives the segment of the model
asynchronously. Before merging the received segments into the model, which is
updated by each process, it waits until all asynchronous peer-to-peer
communication is completed. After all asynchronous communication is completed,
the flattened tensor is transformed into unflattened tensors. Finally, these
unflattened tensors are averaged using the weight parameter of the
corresponding layer of each process model.

An overview of the segment-wise communication of Crossover-SGD is shown in
Figure 4. In the figure, we represent the send and receive processes for each
segment in terms of Process 1. In the sending process of the left part of the
figure, each segment of Process 1 is randomly propagated into other processes.
When the weight parameter of each segment is received by the destination
process, the received weight parameter is merged with the weight parameter of
Process 1, as shown in the right side of the figure. This segment-wise gossip
communication can propagate the weight parameter more widely than model-wise
communication as well as efficiently use of network bandwidth for each worker
node.

Figure 4: Oveview of segment-wise communication of Crossover-SGD

###  3.2 Load balanced random topology of Crossover-SGD

Algorithm 2 Load balanced random network topology

1: rseed : random seed which is shared by every process, world_size : the
total number of training process,
roulettes : probability table of all processes which is used to select
destination rank,
dest_list : destination rank list of every worker node

2:This algorithm is the selection_destinations function in Algorithm 1

3:for i…world_size do

4: for j in dest_list do

5: $roulettes[i][j]=0$

6: end for

7: roulette_sum = sum(roulettes[i])

8: roulettes[i] = [r/roulette_sum for r in roulettes[i]]

9: selected_rank = choice(world_size, roulette=roulettes[i], seed=rseed)

10: dest_list.append(selected_rank)

11:end for

12:return dest_list

Crossover-SGD allows one process to communicate with other processes on load-
balancing random network topology. The topology is an essential part of the
method that differentiates our proposed Crossover-SGD from COMBO and
GossipGraD 8, 9. To achieve this, we build a probability table, called
roulettes, to manage the selection of peer worker nodes for communication. In
roulettes, the row index represents the ID of the source process and the
column index represents the ID of the destination process. Furthermore,
roulettes should avoid being selected by the peer workers. Therefore, the
initial roulettes are created as a stochastic matrix with its major diagonal
elements having zero value(i.e., zero possibility).

Even if roulettes (i.e., a shared probability table) are created, more
procedures are required to build a load-balancing network topology. For
example, a selected rank (i.e., process ID) should not be selected for another
process again in one peer setting because duplicated selection means that some
processes do not communicate in this training step. This unbalanced selection
leads to a decrease in validation accuracy because uncommunicated workers that
do not receive the weight parameters of other workers are less optimized than
communicated workers in each time step.

Algorithm 2 shows the process used to create a load-balancing random network
topology. This algorithm corresponds to the select-destination function used
in Algorithm 1. In lines 2 and 4, the process already selected as destination
has its probability set as zero to avoid duplicated selection. In lines 5 and
6, the roulettes for rank $i$ are reconfigured to reflect the removal of
duplicated selections and the sum of probability is set as 1. After the
roulettes for rank $i$ are fully modified, our algorithm selects the
destination rank using reconfigured roulettes for rank $i$ in line 7.

###  3.3 Hierarchical communication methods for high validation accuracy

We discussed our gossip-based SGD for the fast propagation of weight
parameters in Sections 3.1 and 3.2. However, the validation accuracy is still
decreased owing to the characteristics of gossip-based communication. The
hierarchical communication method 14, 15 was recently studied to increase
scalability of the AllReduce-SGD by reducing the number of communications at
each step. Likewise, we adapt a hierarchical communication method to
Crossover-SGD to utilize our method in a large cluster environment.
Interestingly, the network overhead is increased compared to the case of
utilizing only the gossip-based method owing to the additional synchronization
overhead in each group unlike in the cases of AllReduce-SGD. However the
validation accuracy can be preserved if hierarchical communication is used in
gossip-based methods.

Figure 5 is the overview of hierarchical Crossover-SGD with hierarchical
communication. In this figure, hierarchical Crossover-SGD is presented in
three steps. The first step is to reduce the gradients of the worker nodes in
each group. In this step, we reduced the gradients for two reasons. First, it
utilizes computation and communication overlap, which can be utilized easily
when gradients are communicated. Second, LARS 3, when it is used with
AllReduce-SGD, decreases the validation accuracy when the gradient norm is not
synchronized among worker nodes. Thus, the L node, which is the leader node in
each group, collects gradients from each worker and reduces them to apply a
reduced gradient to the model. The second step is the communication of the
inter-group by utilizing Crossover-SGD. Subsequently, the gossiped model
parameter of the leader node propagates to other workers in each group.

Figure 5: Hierarchical Crossover-SGD for node scalability about preserving
high validation accuracy

##  4 Evaluation

In this section, we present the empirical experiment results in two fold
because our evaluation has two goals: 1) to study the issue of the gossip-
based approach in a large mini-batch environment, and 2) to measure the
scalability and accuracy enhancement of our proposed method.

To achieve the first goal, we conducted an analysis on the performance of the
gossip-based approach in a large mini-batch environment. The most intuitive
way to perform the analysis is to set the condition as that of the large mini-
batch problem. The ResNet-50 model 19with the ImageNet ILSVRC 2012 dataset 20
is commonly used as the base model and dataset. Reproducing the large mini-
batch problem is difficult to configure for the ResNet50 model owing to the
economic cost of utilizing a large GPU cluster. Thus, we chose to increase the
communication interval and accumulate the loss during this interval instead of
increasing the physical scale. The increase in communication interval has
almost the same effect as a large mini-batch environment except for the
statistics update of batch normalization that incurs a decreasing validation
accuracy when the mini-batch size of each worker becomes smaller.

To verify that our proposed Crossover-SGD effectively addresses the large
mini-batch problem, which is our second goal, we conduct empirical comparison
experiments between our method and conventional schemes such as AllReduce-SGD
and SGP. The AllReduce-SGD scheme is the most representative method for
distributed learning, and the gradient of every model is synchronized at each
training interval. Thus, the accuracy of this approach is known to be the most
stable compared to any other communication approach. SGP 12 is a state-of-the-
art gossip-based communication scheme for distributed learning. The training
time of this approach is known to be the fastest, however, its validation
accuracy decreases when the number of worker nodes increases.

###  4.1 Evaluation Environment

In our evaluation, we ensure that the starting point of the valuation is the
state-of-the-art research result of a large mini-batch problem. Most recently,
Fujitsu achieved approximately 75.9% validation in 86,016 mini-batch sizes.
Thus, we first set the validation accuracy of our ResNet-50 model with
AllReduce equal to or slightly lower than the convergence accuracy. As a
result, we achieved a 75.67% accuracy in our model with AllReduce-SGD. To
achieve 75.67% accuracy, the implementation of LARS is critical to the
performance. To increase accuracy, we implemented the LARS of MXNet on
PyTorch. This implementation showed the highest accuracy compared to any other
user implementation of LARS on PyTorch.

A summary of the hyperparameter settings is shown in Table 1. For our
evaluation, we used the ResNet-50 model with the ImageNet ILSVRC 2012 dataset.
Our hyperparameter setting was based on the hyperparameter setting of Fujitsu
21. As shown in Table 1, we set the communication interval as 42 to simulate
the condition of a large mini-batch problem in a small cluster environment
because the maximum mini-batch size in V100 is limited to hundreds with a GPU
memory size 16 or 32 GB. In terms of data augmentation of input data, we only
utilized random resizing, random cropping, and horizontal flipping for our
training. These augmentations were originally adapted from the official
example code of Resnet-50 in PyTorch 22. In addition, we used mixed precision
training 14 to reduce the training time.

Table 1: Hyperparameter setting in Training with 86,016 mini-batch size Hyper-parameter Type | Value
---|---
LARS Coefficient | 0.0025
Learning rate | 9
Optimizer | Adam with $5\times 10^{-5}$ weight decay and 0.96 momentum
Warm-up epoch | 36
training epoch | 90
Communication Interval | 42
Mini-batch size per Node | 256
Data augmentation | Random resize crop , Horizontal flip
Model segment | Segmenting blocks and FC layer of ResNet
Mixed precision training | Yes
$\epsilon$ in Label smoothing | 0.1

The evaluation is executed on the NEURON GPU cluster environment of KISTI 23
as shown in Table 2. Because we utilize only four worker nodes in this cluster
environment, we create multiple processes for each GPU device in the
evaluation discussed in Section 4.3. For evaluating time efficiency, we
utilize the AWS cluster environment because the fact that the impact of
network overhead is relatively small in small cluster environment of NEURON
with InfiniBand. The worker nodes in the AWS cluster environment are
communicated by low network bandwidth and GPUs, which have a relatively lower
performance than V100 GPU. For the evaluation, we use PyTorch 1.4, with Apex
24 as the distributed deep learning framework and OpenMPI 3.1.0 25 as the
communication library. To utilize the cluster environment, we use the
container library, singularity 3.1.0 26. We use the ResNet-50 model in
torchvision 27, which is an official DNN model and dataset library of PyTorch.

Table 2: Hardware Specification Hardware for Section 4.2 and 4.3 except for
the evaluation in Figure 9
---
CPU | Intel Xeon Cascade Lake (Gold 6226R) / 2.90GHz (16-core) / 2 socket
GPU | NVIDIA Tesla V100 32GB(or 16GB) X 2
RAM | DDR4 384GB
Network Bandwidth | 56000Mb/s
Hardware for the evaluation in Figure 9 (i.e., AWS g4dn.2xlarge 28 EC2
Instance)
CPU | AWS-custom Second Generation Intel® Xeon® Scalable (Cascade Lake) processors(8-core)
GPU | NVIDIA Tesla T4
RAM | 32 GiB
Network Bandwidth | up to 3125Mb/s

###  4.2 Analysis of gossip methods in the large mini-batch problem condition

To analyze the gossip methods, we compare two gossip methods with our baseline
model. First, we determined the optimal learning rate of each global mini-
batch size. Generally, this optimal learning rate increases linearly with
increasing global mini-batch size. Figure 6 shows a comparison of each method.
In this figure, we can derive and confirm two important insights. First, a
linear increase in the learning rate does not effectively work in a large
mini-batch setting. In our evaluation with increasing mini-batch size, we did
not increase the learning rate linearly with increasing mini-batch size;
however, we increase the learning at a much smaller rate than in the linear
increasing case. Second, each method has a different optimal learning rate.
The second insight shows that each method has different validation accuracies
for each learning rate. Most importantly, our proposed method, Crossover-SGD,
shows the most robust results on changes of learning rate, whereas AllReduce-
SGD shows the most fluctuating result on learning rate changes.

Figure 6:  Impact of learning rate when the mini-batch size is increased

Figure 7 compares the accuracy of the methods for the mini-batch size with the
optimal learning rate of each method. Crossover-SGD showed the highest
accuracy compared to the other methods. As shown in Figure 7, AllReduce-SGD
was most affected by the large mini-batch problem. Conversely, two gossip-
based methods, Crossover-SGD and SGP are more robust than AllReduce-SGD in
terms of the large mini-batch problem, if the number of worker nodes is fixed.
This is an interesting result because we assumed that AllReduce is the most
stable communication method. However, we confirmed that the exploration
characteristic of the gossip-based method is helpful in preserving validation
accuracy. As the mini-batch size is increased, the difference in validation
accuracy with Crossover-SGD and SGP decreases. This is because the random
network topology results in unstable convergence of the neural network when
the number of training steps is decreased. In summary, the two gossip methods
show higher validation accuracy than AllReduce-SGD when a large mini-batch is
utilized with a limited number of workers. This means that gossip methods can
be utilized for large mini-batch conditions if the node scalability problem is
alleviated.

Figure 7: Validation accuracy with increasing of mini-batch size for the large
mini-batch problem

###  4.3 Node scalability comparison in the large mini-batch problem

In this section, we evaluate the node scalability of Crossover-SGD in both
time and validation accuracy. First, Figure 8 shows the comparison of
validation accuracy when the number of worker processes is increased and the
mini-batch size is fixed. As the number of worker processes is increased, the
validation accuracy of two gossip-based methods, Crossover-SGD and SGP,
decreases. This is due to the delayed propagation of weight parameters of the
gossip-based algorithm that worsens as the number of worker processes
increases. However, Crossover-SGD is more robust with an increase in the
number of nodes compared to the SGP. We assumed that this is because of the
fast propagation of weight parameters caused by the two characteristics of our
methods: segment-wise communication and random network topology.

Figure 8: Validation accuracy with increasing number of worker processes and
fixed mini-batch size (i.e., 86,016)

Crossover-SGD is more robust when the number of nodes is increased. However,
it is apparent that the validation accuracy of the gossip methods also
decreases. We assume that this perceptible decrease in the validation accuracy
originates from the delayed propagation of the weight parameters of the gossip
methods. To alleviate this problem, we applied hierarchical grouping to
Crossover-SGD. In Figure 8, hierarchical Crossover-SGD shows similar
validation accuracy as AllReduce-SGD because only a limited number of workers
are involved in the communication of Crossover-SGD. Furthermore, Crossover-SGD
with hierarchical grouping is more robust to the condition of large mini-batch
problems, and it is verified from our evaluation results of Crossover-SGD
shown in Section 4.2. Thus, Crossover-SGD with hierarchical grouping is a
better alternative method to AllReduce-SGD in both general conditions and the
large mini-batch problem conditions.

Figure 9: Time efficiency comparison about training time ( dataset : Cifar10
29, model : ResNet-50)

Figure 9 shows the comparison of time efficiency among the evaluated methods.
In this evaluation, the optimal line shows the optimal time efficiency cases
when the number of nodes is increased. As can be seen in this figure, the two
gossip-based methods, Crossover-SGD and SGP, show approximately 40% higher
time efficiency than AllReduce. The two gossip methods show higher scalability
than the Allreduce method owing to the low network overhead of the gossip-
based method. However, Crossover-SGD has approximately 3–4% lower scalability
than SGP. This decrease is due to the additional computation overhead for
creating a load-balancing random network topology. As a result, Crossover-SGD
shows linear scalability to the number of worker nodes. However, we have not
yet evaluated hierarchical Crossover-SGD in terms of time efficiency. We
expect that the time efficiency of hierarchical Crossover-SGD is higher than
AllReduce-SGD because each group only needs to be synchronized with a
relatively smaller number of workers than the number of entire workers, where
AllReduce-SGD requires all workers to be synchronized.

##  5 Conclusion

In this study, we analyzed the characteristics of gossip-based SGD on large
mini-batch problems. We observed that gossip-based SGD achieves higher
validation accuracy owing to its exploration characteristics when the number
of workers is fixed. Thus, the delay propagation of gossip-based SGD becomes
crucial when using gossip-based methods for large cluster environments. Based
on these insights, we proposed Crossover-SGD, a gossip-based communication
method that utilizes both the load-balancing random network topology and
overlapped segment communication. These two characteristics of Crossover-SGD
make it possible to propagate the weight parameter to other workers more
efficiently and faster than previous gossip-based methods. We also conducted
empirical evaluations and found that Crossover-SGD outperforms AllReduce-SGD
in large mini-batch problems; it also shows higher accuracy than the state-of-
the-art gossip-based method SGP for distributed deep learning when either the
number of workers and local mini-batch size is increased.

However, there is still scope for improvement in the scalability of Crossover-
SGD by delaying the propagation of weight parameters. Even if it can achieve
faster propagation than SGP, owing to the delay propagation of weight
parameters in gossip-based methods, it is observed that the validation
accuracy decreases significantly when the number of workers is increased.
Thus, we apply hierarchical grouping communication for worker processes to
alleviate the decrease in validation accuracy of gossip-based methods.
Crossover-SGD with this grouping method (i.e., hierarchical Crossover-SGD)
shows similar validation accuracy as AllReduce-SGD. Therefore, hierarchical
Crossover-SGD is a better alternative communication method to AllReduce-SGD,
reducing network overhead efficiently while preserving high validation
accuracy.

## Acknowledgements

This research was supported by National Supercomputing Center with
supercomputing resources including technical support (KSC-2019-CRE-0105), the
MSIT (Ministry of Science and ICT), Korea, under the ITRC (Information
Technology Research Center) support program (IITP-2020-2018-0-01431)
supervised by the IITP (Institute for Information & communications Technology
Promotion), Basic Science Research Program Through the National Research
Foundation of Korea (NRF) funded by the Ministry of Education
(2018R1D1A1B07043858), and Electronics and Telecommunications Research
Institute (ETRI) grant funded by the Korean government (20ZT1100, Development
of ICT Convergence Technology based on Urban Area). We would like to thank
Editage (www.editage.co.kr) for English language editing.

## References

  * 1 Yamazaki M, Kasagi A, Tabuchi A, et al. Yet another accelerated sgd: Resnet-50 training on imagenet in 74.7 seconds. arXiv preprint arXiv:1903.12650 2019\.
  * 2 Keskar NS, Mudigere D, Nocedal J, Smelyanskiy M, Tang PTP. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.04836 2016\.
  * 3 You Y, Gitman I, Ginsburg B. Large batch training of convolutional networks. arXiv preprint arXiv:1708.03888 2017\.
  * 4 Sergeev A, Del Balso M. Horovod: fast and easy distributed deep learning in TensorFlow. arXiv preprint arXiv:1802.05799 2018\.
  * 5 Sun P, Feng W, Han R, Yan S, Wen Y. Optimizing network performance for distributed dnn training on gpu clusters: Imagenet/alexnet training in 1.5 minutes. arXiv preprint arXiv:1902.06855 2019\.
  * 6 Shi S, Wang Q, Chu X, et al. Communication-efficient distributed deep learning with merged gradient sparsification on gpus. In: IEEE. ; 2020.
  * 7 Jiang J, Hu L, Hu C, Liu J, Wang Z. BACombo—Bandwidth-Aware Decentralized Federated Learning. Electronics 2020; 9(3): 440.
  * 8 Hu C, Jiang J, Wang Z. Decentralized federated learning: A segmented gossip approach. arXiv preprint arXiv:1908.07782 2019\.
  * 9 Daily J, Vishnu A, Siegel C, Warfel T, Amatya V. Gossipgrad: Scalable deep learning using gossip communication based asynchronous gradient descent. arXiv preprint arXiv:1803.05880 2018\.
  * 10 Lian X, Zhang C, Zhang H, Hsieh CJ, Zhang W, Liu J. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In: ; 2017: 5330–5340.
  * 11 Lian X, Zhang W, Zhang C, Liu J. Asynchronous decentralized parallel stochastic gradient descent. In: PMLR. ; 2018: 3043–3052.
  * 12 Assran M, Loizou N, Ballas N, Rabbat M. Stochastic gradient push for distributed deep learning. In: PMLR. ; 2019: 344–353.
  * 13 Syswerda G. Uniform crossover in genetic algorithms. In: ; 1989: 2–9.
  * 14 Jia X, Song S, He W, et al. Highly scalable deep learning training system with mixed-precision: Training imagenet in four minutes. arXiv preprint arXiv:1807.11205 2018\.
  * 15 Kurth T, Zhang J, Satish N, et al. Deep learning at 15pf: supervised and semi-supervised classification for scientific data. In: ; 2017: 1–11.
  * 16 Dean J, Corrado G, Monga R, et al. Large scale distributed deep networks. Advances in neural information processing systems 2012; 25: 1223–1231.
  * 17 Zhang W, Gupta S, Lian X, Liu J. Staleness-aware async-sgd for distributed deep learning. arXiv preprint arXiv:1511.05950 2015\.
  * 18 Zhang S, Choromanska AE, LeCun Y. Deep learning with elastic averaging SGD. Advances in neural information processing systems 2015; 28: 685–693.
  * 19 He K, Zhang X, Ren S, Sun J. Deep residual learning for image recognition. In: IEEE. ; 2016: 770–778.
  * 20 Russakovsky O, Deng J, Su H, et al. Imagenet large scale visual recognition challenge. International journal of computer vision 2015; 115(3): 211–252.
  * 21 mlperf/training_results_v0.6. https://github.com/mlperf/training_results_v0.6; .  (Date Accessed December 27, 2020).
  * 22 Paszke A, Gross S, Massa F, et al. Pytorch: An imperative style, high-performance deep learning library. In: ; 2019: 8026–8037.
  * 23 NEURON specification. https://www.ksc.re.kr/ggspcpt/neuron; .  (Date Accessed December 27, 2020).
  * 24 Nvidia Apex. https://github.com/NVIDIA/apex; .  (Date Accessed December 27, 2020).
  * 25 OpenMPI. https://www.open-mpi.org/; .  (Date Accessed December 27, 2020).
  * 26 Kurtzer GM, Sochat V, Bauer MW. Singularity: Scientific containers for mobility of compute. PloS one 2017; 12(5): e0177459.
  * 27 PyTorch torchvision. https://github.com/pytorch/vision; .  (Date Accessed December 27, 2020).
  * 28 Amazon EC2 G4 Instances. https://aws.amazon.com/ko/ec2/instance-types/g4/; .  (Date Accessed December 27, 2020).
  * 29 CIFAR-10 and CIFAR-100 datasets. https://www.cs.toronto.edu/~kriz/cifar.html; .  (Date Accessed December 27, 2020).