BML: A High-performance, Low-cost Gradient Synchronization Algorithm for DML Training
In distributed machine learning (DML), the network performance between machines significantly impacts the speed of iterative training. In this paper we propose BML, a new gradient synchronization algorithm with higher network performance and lower network cost than the current practice. BML runs on BCube network, instead of using the traditional Fat-Tree topology. BML algorithm is designed in such a way that, compared to the parameter server (PS) algorithm on a Fat-Tree network connecting the same number of server machines, BML achieves theoretically 
dominating communication cost. Therefore, in order to run DML in large scale, we need to carefully design the network with minimized synchronization overhead among machines.
The widely-used network topology to run DML in today's data centers is Clos network, or FatTree [5]. Although Fat-Tree achieves great success in providing uniform network performance to cloud computing applications, it may not well match the traffic model of gradient synchronization in DML. Running the typical parameter server (PS) synchronization algorithm in Fat-Tree, each synchronization flow needs to traverse multiple hops of switches before being aggregated. It not only hurts the gradient synchronization performance, but also wastes the bandwidth/link resource.
In this paper, we suggest using BCube [12] as the underlying network topology for DML training, and design a novel distributed gradient synchronization algorithm on top of BCube, called BML. BCube is a recursive network topology composed of commodity switches and servers with k (the typical value of k is 2∼4) interfaces. The synchronization algorithm of BML is designed in such a way that, compared to the PS algorithm running a Fat-Tree network connecting the same number of server machines, BML running on a BCube network can theoretically achieve 1 k of the gradient synchronization time, with only k 5 of switches. We have implemented BML in TensorFlow. We run two representative public deep learning benchmarks, namely, LeNet-5 [15] and VGG-19 [22], on a testbed with 9 dual-GPU servers. The experiment results show that, BML can reduce the job completion time of DML training by up to 56.4% compared with the PS algorithm on Fat-Tree network. The advantage of BML is higher when the sub-minibatch size per machine is smaller, which is important for large-scale DML to guarantee the model accuracy.
2 Background and Motivation DML Models and Notations: DML can run on multiple CPUs/GPUs in a machine or on multiple machines. In this work we focus on DML network among machines. In order to decouple the intermachine and intra-machine communications, throughout this paper we simply take one machine as a single training worker, though the machine can be equipped with multiple GPUs.
Based on splitting whether the training data or the model parameters onto multiple machines, DML can be divided into data-parallel and model-parallel ones. In data-parallel DML, each machine uses a shard of training data to compute the gradients; while in model-parallel DML, a machine computes gradients for part of the model. In this work we focus on data-parallel DML. In each iteration, every machine trains local gradients for the entire model based on its sub-minibatch of training data, and synchronizes the gradients with other machines. The aggregated gradients are calculated upon all the machines' local gradients, which are then applied to the model update.
According to the tradeoff between gradient freshness and computing resource utilization, there are three typical synchronization modes. 1) Bulk synchronous parallel (BSP). 2) Total asynchronous parallel (TAP). 3) Stale synchronous parallel (SSP). Given a predefined accuracy of the trained model, it is difficult to tell which synchronization mode runs the fastest in practice. BSP wastes the computation resource of some faster machines, but fully follows the sequential behavior as trained by a single machine. TAP makes full utilization of the computing resource, but the convergence speed is unpredictable with the possibility of no convergence at all [10]. SSP lies between the two with proven convergence [9,26]. In this work we focus on BSP synchronization, which is widely used in modern ML applications [11,24].
This paper observes that by putting network cards into computers, some of the router functionality can be performed for free by each compute node.  This potentially means less router equipment, and less transmission time for averaging data.  This paper then shows how to you how to do it for real, giving details of the averaging algorithm for 'k' network cards per compute node. For k=2 and small minibatches, they actually see their expected factor of 2 speedup experimentally. The algorithm has some little tricks in it that make it a useful contribution.   It is nice that this technique can in many cases be combined with other ways to reduce communication overhead. The technique is more something to consider when setting up a new compute cluster.  This is really a networking paper, since the technique describes how to aggregate [sum] and distribute any vector amongst N compute nodes. The vector could be a gradient, a set of model parameters, or, well, anything else. On the other hand, they actually demonstrate experimentally that it can work in practice for a fairly common machine learning scenario.  ### After author review ### Margin notes: line 95:    GST -  where defined? line 226: codes --> code  Some of the statements in the rebuttal seemed more understandably stated than the more difficult level of presentation in the paper. Occasionally I had to remember  previous statements and infer comparisons by myself.  As noted by reviewer #2, the comparison figure and its discussion helps bring out the practical importance of their paper.  I agree with reviewer #1 that Figure 4 and its discussion needs a very devoted reader.  If I had to make room, I might consider moving Figure 4, lines 165--203 and the dense notation use for it (148--157) to a Supplementary Material.  The body of the paper might contain a much simplified version of Fig. 4 and its discussion, with just the thread 0,1 link activity during the two steps each of aggregation and broadcast, and refer the reader to the supplementary material for details of precisely which gradient piece is chosen for transmission so as to lead to a final state where all servers know all pieces.