# Modeling the Training Iteration Time for Heterogeneous Distributed Deep Learning Systems

Authors: Yifu Zeng; Bowei Chen; Pulin Pan; Kenli Li; Guo Chen
Journal: International Journal of Intelligent Systems
 (2023)

---

## Abstract

Distributed deep learning systems effectively respond to the increasing demand for large-scale data processing in recent years. However, the significant investment in building distributed learning systems with powerful computing nodes places a huge financial burden on developers and researchers. It will be good to predict the precise benefit, i.e., how many times of speedup it can get compared with training on single machine (or a few), before actually building such big learning systems. To address this problem, this paper presents a novel performance model on training iteration time for heterogeneous distributed deep learning systems based on the characteristics of the parameter server (PS) system with bulk synchronous parallel (BSP) synchronization style. The accuracy of our performance model is demonstrated by comparing real measurement results on TensorFlow when training different neural networks with various kinds of hardware testbeds: the prediction accuracy is higher than 90% in most cases.


---

## Body

## 1. Introduction

In recent years, we have witnessed the boom of deep learning which has been successfully applied in numerous areas (also changed these areas), including image processing[1], speech processing [2], natural language processing [3], human-machine gaming [4], autonomous driving [5], and health care [6]. As the complexity of application scenarios and user requirements grow fast, deep learning models scale larger and larger, having massive data as training input, which exceed the processing capability of one single machine. Therefore, large-scale computer clusters are used to speedup the training of such big neural network models, driving the rapid development of distributed deep learning systems [7–10].It requires significant investment to build such distributed learning systems, which consist of multiple high-end servers connected between each other with high speed networks. For example, the Google Brain project, which began exploring the use of very large-scale deep learning systems in 2011, costs an average of more than $100 million per year. For researchers in general universities, a distributed learning system often contains several computing nodes, each node has several GPUs/CPUs/FPGAs/TPUs, and requires a network connection of at least 10 Gbps, which cost up to $100,000. For such large investment, it will be good to predict the precise benefit, i.e., how many times of speedup it can get compared with training on single machine (or a few), before actually building such big learning systems. However, above question is still hard to answer.Although several recent works [11–18] have tried mathematically modeling (some combined with experimental methods) the computation and communication part in distributed training, they are still not accurate enough in practice. Particularly, when modeling the communication time in multimachine training environment, they simply assume that all worker nodes (machines) have the same processing speed and are synchronized during communication (passing parameters/gradients), fairly sharing the network bandwidth. However, such communication model is too idealistic for large distributed learning systems in practice with worker nodes potentially being very heterogeneous with each other [19, 20]. Under such practical scenarios, it is neglected by previous models that worker machines may be complexly overlapped or interleaved with each other on both computation and communication during each training iteration. For example, the worker with the best computing capability pushes gradients as soon as it finishes calculation, which overlaps with the calculation of the other workers.To address the above problem, we present a novel performance model on training iteration time for heterogeneous distributed deep learning systems. By carefully analyzing the steps of computing and communication during a training iteration, we can model the iteration time by inductively calculating the overlap and interference among multiple worker nodes. With our model, one can easily predict the speedup for different distributed hardware platforms only if knowing the target neural network and its configurations, before actually building the system and training on it.We have evaluated the accuracy of our performance model by comparing real measurement results on TensorFlow [21] when training different neural networks on various kinds of hardware testbeds. Experimental results show that our model can predict the training iteration time in an average accuracy over 95%, with the worst accuracy being 78.3%, under various conditions (training alexnet and vgg11/16/19 using various number of machines with or without GPU connected with 1 Gbps or 10 Gbps networks).The rest of the paper is organized as follows. Section2 introduces the background and contributions of our research. Section 3 generally explained the input and output of our prediction model. The floating-point traffic statistics formula is derived in Section 4. Training Time Modelings of stand-alone/distributed platforms with CPU/GPU are performed in Section 5. The experimental results are explained in Section 6.


### 1.1. Notes

The performance model presented in this paper only focuses on (one of) the most widely used architecture of distributed deep learning systems, i.e., data-parallel parameter server (PS) system with bulk synchronous parallel (BSP) synchronization style [22, 23], which is shown to have better performance in both practice and theory [24, 25]. However, our performance model is easy to be extended using the same methods to different architectures such as all-reduce [26] and stale synchronous parallel (SSP) synchronization style [27, 28]. The extension is omitted in this paper. As previous works (i.e., [15]), we model the computation part based on the number of float-point operations and the communication part based on the network bandwidth and delay. We assume that distributed deep learning systems can fully utilize the hardware processing capability (which is the case in most of the current implementations), so implementation issues are not considered in our performance model. Moreover, this paper focuses on predicting the training speedup when using various hardware resources; hence, we do not model the convergence time for training a neural network to a desired accuracy, since the required number of iterations to converge will not change when using different number or different kinds of machines when the other configurations of the neural network remain unchanged.


## 1.1. Notes

The performance model presented in this paper only focuses on (one of) the most widely used architecture of distributed deep learning systems, i.e., data-parallel parameter server (PS) system with bulk synchronous parallel (BSP) synchronization style [22, 23], which is shown to have better performance in both practice and theory [24, 25]. However, our performance model is easy to be extended using the same methods to different architectures such as all-reduce [26] and stale synchronous parallel (SSP) synchronization style [27, 28]. The extension is omitted in this paper. As previous works (i.e., [15]), we model the computation part based on the number of float-point operations and the communication part based on the network bandwidth and delay. We assume that distributed deep learning systems can fully utilize the hardware processing capability (which is the case in most of the current implementations), so implementation issues are not considered in our performance model. Moreover, this paper focuses on predicting the training speedup when using various hardware resources; hence, we do not model the convergence time for training a neural network to a desired accuracy, since the required number of iterations to converge will not change when using different number or different kinds of machines when the other configurations of the neural network remain unchanged.


## 2. Background, Related Works, and Problems

### 2.1. Background

In March 2017, Jeff Dean, head of Google Brain, gave a speech titled “Building Intelligent Systems with Large Scale Deep Learning” at UC Santa Barbara [29], where he predicted that machine learning expertise could be replaced by super computing power. Distributed machine learning systems are positioned to provide greater computing power. In distributed machine learning systems, the main parallel models include model parallelism (different machines (GPU/CPU, etc.) in a distributed system are responsible for different parts of the network model) and data parallelism (different machines have multiple copies, each machine is assigned a different data, and the computation results of all the machines are then merged in some way). The main system architecture includes PS (this architecture isolates the calculation of each worker node, and each worker node only interacts with the server) and All-Reduce (this architecture integrates data from different training nodes, and distributes the results to all training nodes after the integration is complete). The main parameter update methods include BSP (Bulk Synchronous Parallel), ASP (Asynchronous Parallel), and SSP (Stale Synchronous Parallel).Among these combinations of system architecture and parameter update methods,PS+BSP is the most popular one that is demonstrated to have better performance in both practice and theory [24, 25]. With PS architecture, the bottleneck bandwidth is utilized up to twice more efficient than All-Reduce. Furthermore, PS+BSP can be used as asynchronous.Therefore, the performance model presented in this paper only focuses on data-parallel parameter server (PS) system with bulk synchronous parallel (BSP) synchronization style.


### 2.2. Related Work

Previous work of predicting the training iteration time include [11–15, 17]. They build pure mathematical models or combined with experimental measurements to model the computation part and communication part. All of them assume all workers start to pull and push in a synchronized way, and calculate the time as parameter_size/gradient_size/bandwidth.In computation part, the references [11, 13, 17] combine mathematical models and experimental measurements, while [12, 14, 15] predict the training iteration time with mathematical models alone.


### 2.3. Problems and Our Contributions

The iteration time modeling is not accurate in previous work, since distributed learning systems have heterogeneous computation hardware and each computing unit (GPUs/CPUs/FPGAs/TPUs) may have different computing power. As shown in Figure1(a), the modeling in previous work is modeled as synchronized, which requires multiple computing units in the system to have the same processing speed. However, as shown in Figure 1(b), the computing process is generally unsynchronized in practice, since heterogeneous hardwares have different computation time. Therefore, the accuracy of total iteration time modeling can be improved by further considering the effect of heterogeneous computation hardware.Figure 1
Comparison of the communication time modeled in previous works and in practice. (a) Modeled as synchronized, (b) but unsynchronized in practice.
(a)(b)Therefore, we combine the performance and working principle of training equipment, neural network structure, and network bandwidth to establish a mathematical model of one round of iterative time for distributed training underPS+BSP. Our analysis is based on stochastic gradient descent (SGD) since SGD and its variants are the main algorithms for training DNN models. What is more, sigmoid is one of the famous activation functions because of continuity and differentiability. Since it is proposed and widely used earlier, it is used as the first step of our modeling of activation function. Other activation functions will be further modeled in future work. Moreover, we measured the iteration time of a variety of deep neural network (DNN) models and compared it with the predicted iteration time; the experimental results that demonstrate our prediction model is highly accurate.


## 2.1. Background

In March 2017, Jeff Dean, head of Google Brain, gave a speech titled “Building Intelligent Systems with Large Scale Deep Learning” at UC Santa Barbara [29], where he predicted that machine learning expertise could be replaced by super computing power. Distributed machine learning systems are positioned to provide greater computing power. In distributed machine learning systems, the main parallel models include model parallelism (different machines (GPU/CPU, etc.) in a distributed system are responsible for different parts of the network model) and data parallelism (different machines have multiple copies, each machine is assigned a different data, and the computation results of all the machines are then merged in some way). The main system architecture includes PS (this architecture isolates the calculation of each worker node, and each worker node only interacts with the server) and All-Reduce (this architecture integrates data from different training nodes, and distributes the results to all training nodes after the integration is complete). The main parameter update methods include BSP (Bulk Synchronous Parallel), ASP (Asynchronous Parallel), and SSP (Stale Synchronous Parallel).Among these combinations of system architecture and parameter update methods,PS+BSP is the most popular one that is demonstrated to have better performance in both practice and theory [24, 25]. With PS architecture, the bottleneck bandwidth is utilized up to twice more efficient than All-Reduce. Furthermore, PS+BSP can be used as asynchronous.Therefore, the performance model presented in this paper only focuses on data-parallel parameter server (PS) system with bulk synchronous parallel (BSP) synchronization style.


## 2.2. Related Work

Previous work of predicting the training iteration time include [11–15, 17]. They build pure mathematical models or combined with experimental measurements to model the computation part and communication part. All of them assume all workers start to pull and push in a synchronized way, and calculate the time as parameter_size/gradient_size/bandwidth.In computation part, the references [11, 13, 17] combine mathematical models and experimental measurements, while [12, 14, 15] predict the training iteration time with mathematical models alone.


## 2.3. Problems and Our Contributions

The iteration time modeling is not accurate in previous work, since distributed learning systems have heterogeneous computation hardware and each computing unit (GPUs/CPUs/FPGAs/TPUs) may have different computing power. As shown in Figure1(a), the modeling in previous work is modeled as synchronized, which requires multiple computing units in the system to have the same processing speed. However, as shown in Figure 1(b), the computing process is generally unsynchronized in practice, since heterogeneous hardwares have different computation time. Therefore, the accuracy of total iteration time modeling can be improved by further considering the effect of heterogeneous computation hardware.Figure 1
Comparison of the communication time modeled in previous works and in practice. (a) Modeled as synchronized, (b) but unsynchronized in practice.
(a)(b)Therefore, we combine the performance and working principle of training equipment, neural network structure, and network bandwidth to establish a mathematical model of one round of iterative time for distributed training underPS+BSP. Our analysis is based on stochastic gradient descent (SGD) since SGD and its variants are the main algorithms for training DNN models. What is more, sigmoid is one of the famous activation functions because of continuity and differentiability. Since it is proposed and widely used earlier, it is used as the first step of our modeling of activation function. Other activation functions will be further modeled in future work. Moreover, we measured the iteration time of a variety of deep neural network (DNN) models and compared it with the predicted iteration time; the experimental results that demonstrate our prediction model is highly accurate.


## 3. Performance Model Overview

According to the floating-point calculation formula of neural networks that derived in Section4, the floating-point statistics module in Figure 2 output the specific floating-point operations of various neural networks to the next module. Afterwards, combined with the floating-point operations, and the learning system’s network bandwidth and hardware parameters, an iterative time prediction module for both single machine and distributed system can be established in Section 5. Prediction times output by the iterative time prediction module are demonstrated to be accurate in Section 6.Figure 2
One round of iterative time modeling framework.


## 4. Derivation of Floating Point Operations Calculation Formula

According to our investigations, although some floating-point calculation statistics of neural networks have been proposed on some academic or technical platforms, there are some errors after our verification. Therefore, out of scientific rigor, the floating-point traffic statistics formula is derived in this section by combining the specific calculation process of forward-propagation and back propagation.


### 4.1. Formula Derivation of Convolutional Floating Point Operations

The matrix multiplication operation is the most basic calculation in the forward-propagation convolution operation. The premise of the matrix multiplication is that the size of the two multiplied matrices must be the same. After the two matrices are multiplied by a moment, the output is a natural number. The calculation of the moment multiplication can be expressed by formula (1). Among them, aij and bij are the elements of n -order matrices A and B, respectively.(1)output=∑i=0,j=0n−1aijbij.Now, we use5×5×3 samples and two 2×2×3 convolution kernels F0 and F1 to illustrate the process of forward-propagation. The 5×5×3 samples are expanded to obtain three 5×5 matrices, which is shown in Figure 3. First of all, the first three 2×2 matrix among the three sample matrices and the three 2×2 matrices of the convolution kernel F0 are, respectively, subjected to moment multiplication (marked in red in Figure 3). Secondly, the results of the three moment multiplication plus the F0 ’s bias value 1 equals to the first matrix value 4 in the output matrix (also marked in red in Figure 3). The specific calculation process is as follows:(2)1×1+2×0+3×0+4×0=1,1×0+0×0+0×2+1×1=1,2×1+0×0+1×0+0×1=2,1+1+2+1=4.Figure 3
One round of iterative time modeling framework.The calculation process has a total of 24 floating-point operations. It is noted that all parameters other than the bias value correspond to one floating-point operation. So further, the calculation of the number of floating-point operationsf in this part can be generalized to formula (3). Among them, inch represents the input third dimension value, and kw and kh, respectively, represent the width and height of the convolution kernel.(3)f=inch×kh×kw×2.Third of all, move the “matrix to be multiplied” in the input sample to the left by one position. Similarly, perform a moment multiplication with the convolution kernelF0, and finally add a bias value of 1 to obtain the second value 7 of the output. According to the above method, the first 4×4 matrix output can be calculated.Next, we calculate the value of each element of the second4×4 matrix output. The only difference between this process and the previous steps is that the convolution kernel F0 is replaced with F1. After the convolution operation, the second two-dimensional tensor in the output tensor can be obtained, so that the complete 4×4×2 matrix tensor can be obtained.It can be observed from this example that each element in the output4×4×2 matrix tensor corresponds to 24 floating-point operations, that is, the amount of floating-point operations consumed by this example is 4×4×2×24=576. That is, outn×outh×outw×24, where the value of 24 is obtained by formula (3), and outn, outh, and outw are the length, width, and height of the output tensor, respectively. Therefore, we can combine formula (3) to deduce the statistics of floating-point operations of each layer of convolution as formula (4).(4)FLOPcov=inch×kh×kw×outn×outh×outw×2.The actual neural network is usually composed of multilayer convolution and a fully connected neural network, such as Alexnet and VggNet. The parameters of the fully connected layer usually occupy more than90% of the entire neural network, although unlike the convolutional layer, the same parameter will not be recalculated. But its floating-point capacity cannot be ignored. The fully connected layer is usually a one-dimensional tensor. Therefore, the calculation of floating-point operations can also use formula (4), where kh, kw, outh, and outw are all set to 1, and inch and outn are, respectively, the number of elements contained in the two one-dimensional tensors before and after the layer.


### 4.2. Formula Derivation of Back-Propagation Floating Point Operations

Back-propagation is the process of calculating the gradient, and the calculation of the gradient is performed based on the calculation result of the forward-propagation. According to the calculation of forward-propagation, (5) and (6) can be derived as follows:(5)zl=wlal−1+bl,(6)al=σzl,where σ is the activation function; here, we choose Sigmod function as the activation function. zl is the result obtained by calculating the convolution of the forward-propagation of the l -th layer, and adding the bias value bl, al is the output processed by the activation function σ of the forward-propagation training result of the l -th layer.The mean square error is the most commonly used loss function, so that the loss function is derived as (7) based on the mean square error. Among them, 1/2 is to offset the coefficients obtained after the derivation, and has no effect on the surface calculation.(7)Cw,b=12al−y2.The gradient of the weightw and and bias value b of the last layer of the neural network (the output layer) ∂Cw,b/∂wl and ∂Cw,b/∂bl is calculated as(8)∂Cw,b∂wl=∂Cw,b∂al∂al∂zl∂zl∂wl=al−yσ′zlal−1,(9)∂Cw,b∂bl=∂Cw,b∂al∂al∂zl∂zl∂bl=al−yσ′zl.The common part of (8) and (9) can be written as(10)δl=∂Cw,b∂al∂al∂zl=al−yσ′zl.The value ofσ′zl is shown in equation (16).The gradient of the output layer (l-th layer) has been calculated in (8) and (9); in the same way, the gradient of the l−1-th layer can be calculated. Since the error of the output layer l has been calculated above, according to the back-propagation theory, the error of the current layer is the composite function of all the neuron errors of the previous layer, that is, the error of the previous layer can be used to express the error of the current layer.Assume thatδl+1 of the l+1-th layer is calculated, then the δl of the l-th layer is (the l-th layer here is not the output layer but any non-last layer) as follows:The common part of (8) and (9) can be written as(11)δl=∂Cw,b∂zl+1∂zl+1∂zl=δl+1∂zl+1∂zl.Among (11), zl+1 is derived by(12)zl+1=wl+1al+bl+1=wl+1σzl+bl+1.Then, we have (13) and (14):(13)∂zl+1∂zl=wl+1σ′zl,(14)δl=wl+1σ′zlδl+1.Derived from the Sigmod function, Formula (15) and (16) can be obtained.(15)σzl=11+e−x,(16)σ′zl=σzl1−σzl.Therefore, for the calculation of the intermediate layer gradient, there is a recursive formula (17).(17)δl=wl+1σzl1−σzlδl+1.Finally, new parametersw and b can be obtained by (18) and (19) Among them, the η is the learning rate (generally a fixed value).(18)w=w−η∂Cw,b∂wl,(19)b=b−η∂Cw,b∂bl.In summary, it can be seen from (8) that each parameter of the last layer of parameters has 4+sig floating-point operations, where sig is the number of floating-point operations required for the calculation of the Sigmod function. The value of sig is explained in section 4.3. Combined with 2 floating-point operations in (18), the total number of floating-point operations is 6+sig. The gradient corresponding to each parameter of the middle layer can also be obtained as 6+sig times by formula (17) and equation (18). The gradient ∂Cw,b/∂bl of the bias value b corresponding to w is calculated as in equation (9), and this value has been calculated in equation (8). Therefore, the calculation of equation (9) has no additional floating-point operations, and there are 2 floating-point operations in equation (19). From the above, the statistical formulas for back-propagation floating-point numbers are shown in equations (22)–(24) in section 4.3.


### 4.3. Derivation of Total Floating Point Operations

The total floating-point number of forward-propagation needs to be calculated separately according to the number of layers of the neural network. According to formula (4), the floating-point number of the i-th layer is shown in formula (20). Among them, inch represents the number of input channels of the i-th layer, kh and kw, respectively, represent the length and width of the i-th layer convolution kernel, outn, outh, and outw, respectively represent the matrix number, height, and width of the output tensor of the i-th layer. The total FLOPS of forward-propagation is shown in formula (21).(20)FLOPSi=inch×kh×kw×outn×outh×2,(21)FLOPSforward=∑i=1nFLOPSi.The sum of the number of parametersw and b is the sum of the parameters of the neural network para. The number of bparab is the result of length×width×height of the tensor size output by each layer. The number of w is the number of all parameter (para and parab). Therefore, the FLOPS of back-propagation is shown in equations (22)–(24). Among them, FLOPSw represents the number of floating-point calculations required for a weight in a back-propagation, and FLOPSb represents the number of floating-point calculations required for a bias value in a back-propagation.(22)FLOPSbackward=para×FLOPSw+parab×FLOPSb,(23)FLOPSw=6+sig,(24)FLOPSb=2.From the formula (15), the value of sig is 2+x, where x represents the number of floating-point calculations consumed to calculate the exponential function ex. Since the calculation of the exponential function ex in Python3 is essentially an approximation obtained by calculating the Taylor expansion of ex (equation (25)), we can get equation (26). Among them, i is Taylor’s expansion series, and this value is uncertain in the underlying implementation of Python3. Python3 is dynamically adjusted according to the actual calculated value, and the calculation accuracy is increased by 3 digits each time. Due to the complexity and uncertainty of the parameters in deep learning, we will take the value of i based on the results of experiments, and through the results of multiple experiments, i is approximately equal to 20.(25)ex=1+x+x22!+x33!+x44!+x55!+0x6,(26)x=1+4i.In summary, in a round of iteration with a batch size ofbs, the number of floating-point numbers (FLOPS) is expressed as formula (27).(27)FLOPS=bs×FLOPSforward+FLOPSbackward.


## 4.1. Formula Derivation of Convolutional Floating Point Operations

The matrix multiplication operation is the most basic calculation in the forward-propagation convolution operation. The premise of the matrix multiplication is that the size of the two multiplied matrices must be the same. After the two matrices are multiplied by a moment, the output is a natural number. The calculation of the moment multiplication can be expressed by formula (1). Among them, aij and bij are the elements of n -order matrices A and B, respectively.(1)output=∑i=0,j=0n−1aijbij.Now, we use5×5×3 samples and two 2×2×3 convolution kernels F0 and F1 to illustrate the process of forward-propagation. The 5×5×3 samples are expanded to obtain three 5×5 matrices, which is shown in Figure 3. First of all, the first three 2×2 matrix among the three sample matrices and the three 2×2 matrices of the convolution kernel F0 are, respectively, subjected to moment multiplication (marked in red in Figure 3). Secondly, the results of the three moment multiplication plus the F0 ’s bias value 1 equals to the first matrix value 4 in the output matrix (also marked in red in Figure 3). The specific calculation process is as follows:(2)1×1+2×0+3×0+4×0=1,1×0+0×0+0×2+1×1=1,2×1+0×0+1×0+0×1=2,1+1+2+1=4.Figure 3
One round of iterative time modeling framework.The calculation process has a total of 24 floating-point operations. It is noted that all parameters other than the bias value correspond to one floating-point operation. So further, the calculation of the number of floating-point operationsf in this part can be generalized to formula (3). Among them, inch represents the input third dimension value, and kw and kh, respectively, represent the width and height of the convolution kernel.(3)f=inch×kh×kw×2.Third of all, move the “matrix to be multiplied” in the input sample to the left by one position. Similarly, perform a moment multiplication with the convolution kernelF0, and finally add a bias value of 1 to obtain the second value 7 of the output. According to the above method, the first 4×4 matrix output can be calculated.Next, we calculate the value of each element of the second4×4 matrix output. The only difference between this process and the previous steps is that the convolution kernel F0 is replaced with F1. After the convolution operation, the second two-dimensional tensor in the output tensor can be obtained, so that the complete 4×4×2 matrix tensor can be obtained.It can be observed from this example that each element in the output4×4×2 matrix tensor corresponds to 24 floating-point operations, that is, the amount of floating-point operations consumed by this example is 4×4×2×24=576. That is, outn×outh×outw×24, where the value of 24 is obtained by formula (3), and outn, outh, and outw are the length, width, and height of the output tensor, respectively. Therefore, we can combine formula (3) to deduce the statistics of floating-point operations of each layer of convolution as formula (4).(4)FLOPcov=inch×kh×kw×outn×outh×outw×2.The actual neural network is usually composed of multilayer convolution and a fully connected neural network, such as Alexnet and VggNet. The parameters of the fully connected layer usually occupy more than90% of the entire neural network, although unlike the convolutional layer, the same parameter will not be recalculated. But its floating-point capacity cannot be ignored. The fully connected layer is usually a one-dimensional tensor. Therefore, the calculation of floating-point operations can also use formula (4), where kh, kw, outh, and outw are all set to 1, and inch and outn are, respectively, the number of elements contained in the two one-dimensional tensors before and after the layer.


## 4.2. Formula Derivation of Back-Propagation Floating Point Operations

Back-propagation is the process of calculating the gradient, and the calculation of the gradient is performed based on the calculation result of the forward-propagation. According to the calculation of forward-propagation, (5) and (6) can be derived as follows:(5)zl=wlal−1+bl,(6)al=σzl,where σ is the activation function; here, we choose Sigmod function as the activation function. zl is the result obtained by calculating the convolution of the forward-propagation of the l -th layer, and adding the bias value bl, al is the output processed by the activation function σ of the forward-propagation training result of the l -th layer.The mean square error is the most commonly used loss function, so that the loss function is derived as (7) based on the mean square error. Among them, 1/2 is to offset the coefficients obtained after the derivation, and has no effect on the surface calculation.(7)Cw,b=12al−y2.The gradient of the weightw and and bias value b of the last layer of the neural network (the output layer) ∂Cw,b/∂wl and ∂Cw,b/∂bl is calculated as(8)∂Cw,b∂wl=∂Cw,b∂al∂al∂zl∂zl∂wl=al−yσ′zlal−1,(9)∂Cw,b∂bl=∂Cw,b∂al∂al∂zl∂zl∂bl=al−yσ′zl.The common part of (8) and (9) can be written as(10)δl=∂Cw,b∂al∂al∂zl=al−yσ′zl.The value ofσ′zl is shown in equation (16).The gradient of the output layer (l-th layer) has been calculated in (8) and (9); in the same way, the gradient of the l−1-th layer can be calculated. Since the error of the output layer l has been calculated above, according to the back-propagation theory, the error of the current layer is the composite function of all the neuron errors of the previous layer, that is, the error of the previous layer can be used to express the error of the current layer.Assume thatδl+1 of the l+1-th layer is calculated, then the δl of the l-th layer is (the l-th layer here is not the output layer but any non-last layer) as follows:The common part of (8) and (9) can be written as(11)δl=∂Cw,b∂zl+1∂zl+1∂zl=δl+1∂zl+1∂zl.Among (11), zl+1 is derived by(12)zl+1=wl+1al+bl+1=wl+1σzl+bl+1.Then, we have (13) and (14):(13)∂zl+1∂zl=wl+1σ′zl,(14)δl=wl+1σ′zlδl+1.Derived from the Sigmod function, Formula (15) and (16) can be obtained.(15)σzl=11+e−x,(16)σ′zl=σzl1−σzl.Therefore, for the calculation of the intermediate layer gradient, there is a recursive formula (17).(17)δl=wl+1σzl1−σzlδl+1.Finally, new parametersw and b can be obtained by (18) and (19) Among them, the η is the learning rate (generally a fixed value).(18)w=w−η∂Cw,b∂wl,(19)b=b−η∂Cw,b∂bl.In summary, it can be seen from (8) that each parameter of the last layer of parameters has 4+sig floating-point operations, where sig is the number of floating-point operations required for the calculation of the Sigmod function. The value of sig is explained in section 4.3. Combined with 2 floating-point operations in (18), the total number of floating-point operations is 6+sig. The gradient corresponding to each parameter of the middle layer can also be obtained as 6+sig times by formula (17) and equation (18). The gradient ∂Cw,b/∂bl of the bias value b corresponding to w is calculated as in equation (9), and this value has been calculated in equation (8). Therefore, the calculation of equation (9) has no additional floating-point operations, and there are 2 floating-point operations in equation (19). From the above, the statistical formulas for back-propagation floating-point numbers are shown in equations (22)–(24) in section 4.3.


## 4.3. Derivation of Total Floating Point Operations

The total floating-point number of forward-propagation needs to be calculated separately according to the number of layers of the neural network. According to formula (4), the floating-point number of the i-th layer is shown in formula (20). Among them, inch represents the number of input channels of the i-th layer, kh and kw, respectively, represent the length and width of the i-th layer convolution kernel, outn, outh, and outw, respectively represent the matrix number, height, and width of the output tensor of the i-th layer. The total FLOPS of forward-propagation is shown in formula (21).(20)FLOPSi=inch×kh×kw×outn×outh×2,(21)FLOPSforward=∑i=1nFLOPSi.The sum of the number of parametersw and b is the sum of the parameters of the neural network para. The number of bparab is the result of length×width×height of the tensor size output by each layer. The number of w is the number of all parameter (para and parab). Therefore, the FLOPS of back-propagation is shown in equations (22)–(24). Among them, FLOPSw represents the number of floating-point calculations required for a weight in a back-propagation, and FLOPSb represents the number of floating-point calculations required for a bias value in a back-propagation.(22)FLOPSbackward=para×FLOPSw+parab×FLOPSb,(23)FLOPSw=6+sig,(24)FLOPSb=2.From the formula (15), the value of sig is 2+x, where x represents the number of floating-point calculations consumed to calculate the exponential function ex. Since the calculation of the exponential function ex in Python3 is essentially an approximation obtained by calculating the Taylor expansion of ex (equation (25)), we can get equation (26). Among them, i is Taylor’s expansion series, and this value is uncertain in the underlying implementation of Python3. Python3 is dynamically adjusted according to the actual calculated value, and the calculation accuracy is increased by 3 digits each time. Due to the complexity and uncertainty of the parameters in deep learning, we will take the value of i based on the results of experiments, and through the results of multiple experiments, i is approximately equal to 20.(25)ex=1+x+x22!+x33!+x44!+x55!+0x6,(26)x=1+4i.In summary, in a round of iteration with a batch size ofbs, the number of floating-point numbers (FLOPS) is expressed as formula (27).(27)FLOPS=bs×FLOPSforward+FLOPSbackward.


## 5. Predictive Modeling of Distributed Training Time Based on CPU and GPU

### 5.1. Training Time Modeling of Stand-Alone CPU Platform

The Single Instruction Multiple Datastream (SIMD) technology enables multiple data to be calculated in parallel within the same CPU clock cycle with only one instruction. In general, the parallel data calculation of Single Instruction to Multiple Execution depends on the number of CPU registers. If it is 64 bits, it can be split into 8 8 bit registers, and 8 8 bit data operations can be completed at the same time. The efficiency is increased by 8 times. Similarly, it can be divided into 2 32 bit or 4 16 bit registers as well. According to the operating principle of the CPU, the mathematical model of the single-core cpu’s one round iteration time can be established as formula (28). Among them, Tcpu represents the training prediction time. The value of FLOPs is obtained by formula (27) in Section 4.3. cpuhz represents the CPU frequency, and simd represents the number of data that can be operated in parallel after optimization with SIMD instructions.(28)Tcpu=FLOPscpuhz×simd.


### 5.2. Training Time Modeling of Distributed CPU Platform

Most of the 64 bit processors on the server market now have a clock speed between 1.6 Ghz and 2.6 Ghz, so the computing power for 32 bit floating-point numbers is between 3.2 and 5.2 GFLOPs. Commonly used neural networks such as Alexnet and Vgg have parameters ranging from tens to hundreds of megabytes. Specifically, Alexnet has 63 M parameters, which is equivalent to 2 Gbit data, while Vgg has 133 M parameters, which is 4.25 Gbit data. If the computing power of each training node is not far apart, and the total bandwidth is below 1 Gb, then the communication overhead will inevitably seriously affect the training performance. The communication overhead will become a performance bottleneck for training when the time for each node to execute push is in conflict, which will cause network congestion. The purpose of our modeling is to help relevant personnel obtain the most cost-effective overall system architecture solution by predicting what kind of equipment constitutes a system architecture that can avoid the performance bottleneck caused by communication.Based on the PS architecture and combined with the synchronization communication algorithm, mathematical models for training nodes with equal computing power and nonequal computing power is established. The one-round iteration time modeling on platforms with equal computing power are illustrated in formulas (29)–(31). Among them, T represents the total time of one-round iteration, Tcpu is obtained by formula (28). Tpull is the total time for all workers to pull parameters, and Tpush is the total time for all workers to send gradients. Tpull and Tpush are both communication time, and the communication performance is mainly manifested in Tpush. n is the number of workers, P and G are, respectively, the amount of parameters and gradient (need to be converted to bit), and B is the bandwidth of the parameter server (bit/s).(29)T=Tcpu+Tpush×n+Tpull×n,(30)Tpull=PB,(31)Tpush=GB.The one-round iteration time modeling on platforms with nonequal computing power and equal communication power are illustrated in Algorithm1. The main scenario considered in this paper is the case where multiple workers as well as PSs are connected to the same switch. In this case, it is common that each machine have equal communication power. And the link between the PS and the switch is the main communication bottleneck. Figure 4 gives a brief explanation of Algorithm 1. In the figure, nodes w0w3 have the same push time and pull time, but the calculation time is different and gradually increases. To calculate one round of iteration time T, first initialize T to the sum of the calculation time of w0 and the push time. Second, since T=Tcpu0+Tpush>=Tcpu1 and Tcpu0>Tcpu1, the push of w0 has not ended when w1 is calculated. Thanks to the communication bottleneck in the link between the PS and the switch, the gradient of w1 will enter the sending queue and wait for the gradient of w0 to be sent before pushing, and the push of w1 will finish after the push of w0 ended with Tpush, which can be shown in yellow. Therefore, the total time consumption from the start of local calculation of w0 to the end of the push of w1 is equal to the sum of calculation time of w0, the push time of w0 and the push time of w1, which represented as T. As shown in Figure 4, the current value of T can be represented by moving the push legend of w1 directly behind the push legend of w0. Third, since the calculation time of w2 is larger than the current value of T, so T is directly set to the sum of the calculation time of w2 and the push time of w2. Fourth, similar to the second step, the current value of T is the calculation time of w2 plus the push time of w2 and the push time of w3. Finally, add the pull time to T, that is the result of one round of iteration time (By default, the parameter server will use a balanced algorithm to ensure that each computing node can receive new parameters at the same time).Figure 4
One-round iteration time modeling algorithm with nonequal computing power CPUs.In our analysis, the ratio of computation time to communication time and the local computation time for each worker is uncertain. When the ratio of computation time to communication time is different, the one-round iteration time will be calculated differently according to Algorithm1 and Algorithm 2. In particular, when the communication time is greater than the computation time of each worker, the one-round iteration time is simply summarized as(32)T=n∗Tpull+Tmin+n∗Tpush,where Tmin is the local computation time of the fastest worker(with the best computing capability in n workers). In this case, the bottleneck push process starts as soon as the fastest worker completes its computation and the iteration time is not related to the computation time of other workers. In other words, under the communication bottleneck, replacing some of the workers with those with worse computational performance does not change the iteration training time, but it significantly saves computational resources compared with equal computing power. And it will be better to make the communication time as equal to the computation time as possible. When there is a communication bottleneck, replacing a higher bandwidth network device can result in a better performance improvement than replacing a better computing device. The reverse is also true.Algorithm 1: One-round iteration time modeling Algorithm with nonequal computing power CPUs and equal communication power.
Require:FLOPs, CPUhz1,CPUhz2…CPUhzn, simd=2, B,G,P,n.Ensure: One-round iteration time T.1: Calculate the computing time of each device by formula (28), and arrange the CPUs in ascending order as Tcpu1,Tcpu2…Tcpun;2: CalculateTpull and Tpush by formulas (30) and (31);3:T=Tcpu1+Tpush;4:fori in 2,ndo5:ifT≥Tcpuithen6:T+=Tpush;7:else8:T=Tcpui+Tpush;9:T+=n×Tpull;


### 5.3. Training Time Modeling of Stand-Alone GPU Platform

The floating-point computing power of GPU is usually expressed in FLOPs/s per second. The maximum GPU floating-point computing power for computing with stream processor isgpuhz×sp×fc, where gpuhz represents the GPU clock speed, sp represents the number of stream processors, and fc represents the number of floating-point operations that can be performed per stream processor in a single clock cycle. From this, the single iteration time mathematical model of a single-GPU computer can be established as formula (33). In this formula, the value of FLOPs is obtained by formula (27). In addition, the value of fc depends on whether the Fused-Multiply-Add(FMA) instruction set is used. If it is used, fc=2. Otherwise, fc=1.(33)Tgpu=FLOPsgpuhz×sp×fc.


### 5.4. Training Time Modeling of Distributed GPU Platform

Since sending data is executed by the CPU, a training device that uses GPU for distributed training can execute the two tasks of training and sending data in parallel. In this scenario, the first push of the training node occurs after the back-propagation completes the calculation of the gradient of the first layer. In addition, since most of today’s GPUs are clocked at more than 1.5 Ghz, even if there is only one stream processor, its calculation speed is 1.5× 32 Gbit/s. Therefore, if and only if the sending speed is greater than 48 Gbit/s, the sending time will be less than the calculation time. However, the number of stream processors of current GPUs is usually more than hundreds, so the calculation speed is obviously much faster than the sending speed. In this way, the calculation time of one round of iterative time modeling for distributed multimachines using GPUs can be regarded as the forward-propagation time plus the time to complete the first layer of back propagation. This time can be obtained by dividing the total time of back propagation by the number of pushes. The number of pushes depends on the experimental results, which are shown in Table 1. The one-round iteration time modeling algorithm of distributed GPU platform is shown in Algorithm 2.Table 1
Statistics of FLOPs and number of push.
Convolutional neural networkForward-propagationBack-propagationNumber of pushAlexnet1.6776×10+095.2554×10+0919Overfeat5.8584×10+091.2402×10+1020Vgg11A1.5224×10+101.1292×10+1024Vgg13B2.2623×10+101.1308×10+10—Vgg16C2.3548×10+101.1358×10+1034Vgg16D3.0947×10+101.1759×10+10—Vgg19E3.9270×10+101.2210×10+1040Resnet183.5924×10+99.7808×10+8—Resnet347.2898×10+91.8366×10+9—Resnet506.9943×10+91.8015×10+9269Resnet1011.4421×10+103.4114×10+9524Resnet1522.1845×10+104.7372×10+9779Algorithm 2: Training time modeling algorithm of distributed GPU platform.
Require: forwardpropagationFLOPs, backpropagationFLOPs, numberofpushes, the gpuhz,sp,fc,B,G,P of each node, batch−size set by each node, number of nodes n.Ensure: One-round iteration time T.1: CalculateTpull and Tpush by formulas (30) and (31);2:fori in 1,ndo3:FLOPsi=forwardpropagationFLOPs×batch−sizei+backpropagationFLOPs÷numberofpushes;4:Tgpui=FLOPsi÷gpuhzi×sp×fc5: SortTgpu1,Tgpu2…Tgpun in ascending order;6:T=Tgpu1+Tpush;7:fori in 2,ndo8:ifT≥Tgpuithen9:T+=Tpush;10:else11:T=Tgpui+Tpush;12:T+=n×Tpull;Now, we give a briefly explanation of Algorithm2 in conjunction with Figure 5. In the figure, w0w3 are four training nodes, and the red square represents the forward-propagation time. The blue square and the green square represent the back-propagation time and push time, respectively, and both are divided into several small segments according to the number of pushes. As mentioned above, the calculation speed is greater than the sending speed, so each green segment is slightly larger than the blue segment. First, when w0 finishes calculating the first blue segment, it starts to send the gradient. When the second blue segment is calculated, since the first gradient has not yet been sent, it enters the sending queue and waits. That is to say, the green segment representing the push of second gradient needs to be placed behind the green segment representing the push of first gradient, and same for subsequent operations. Second, when w1 calculates the first gradient (the first blue segment) and starts sending, since the gradient of w0 has not been sent yet (green square), the gradient of w1 enters the waiting queue. The corresponding push time is directly added to the push time of w0. At this time, the total time T equals to the forward-propagation time of w0 (red square), plus the calculation time of the first gradient of w0 (the first blue segment), plus the push time of w0 and w1 (green square and yellow square). In the third step, we can see that the forward-propagation time of w2 plus the back-propagation time of the first layer is greater than T, so the value of T is set to the forward-propagation time plus the back-propagation time of the first layer plus the push time of of w2. Fourth, it can be seen that the forward-propagation time of w3 plus its first-layer back-propagation calculation time is less than T. Therefore, the push time of w3 can be added to T as the current total time T. Finally, adding the total pull time pull × 4 is the iteration time T. Finally, by adding T to the total pull time (pull×4, the four gray squares in the figure), one round of iteration time T can be obtained.Figure 5
One-round iteration time modeling with GPUs.Similarly, when the communication time is greater than the computation time of each worker, the one round iteration time can also be summarized as ??. The iteration time is only related to the computation time of the fastest worker.


## 5.1. Training Time Modeling of Stand-Alone CPU Platform

The Single Instruction Multiple Datastream (SIMD) technology enables multiple data to be calculated in parallel within the same CPU clock cycle with only one instruction. In general, the parallel data calculation of Single Instruction to Multiple Execution depends on the number of CPU registers. If it is 64 bits, it can be split into 8 8 bit registers, and 8 8 bit data operations can be completed at the same time. The efficiency is increased by 8 times. Similarly, it can be divided into 2 32 bit or 4 16 bit registers as well. According to the operating principle of the CPU, the mathematical model of the single-core cpu’s one round iteration time can be established as formula (28). Among them, Tcpu represents the training prediction time. The value of FLOPs is obtained by formula (27) in Section 4.3. cpuhz represents the CPU frequency, and simd represents the number of data that can be operated in parallel after optimization with SIMD instructions.(28)Tcpu=FLOPscpuhz×simd.


## 5.2. Training Time Modeling of Distributed CPU Platform

Most of the 64 bit processors on the server market now have a clock speed between 1.6 Ghz and 2.6 Ghz, so the computing power for 32 bit floating-point numbers is between 3.2 and 5.2 GFLOPs. Commonly used neural networks such as Alexnet and Vgg have parameters ranging from tens to hundreds of megabytes. Specifically, Alexnet has 63 M parameters, which is equivalent to 2 Gbit data, while Vgg has 133 M parameters, which is 4.25 Gbit data. If the computing power of each training node is not far apart, and the total bandwidth is below 1 Gb, then the communication overhead will inevitably seriously affect the training performance. The communication overhead will become a performance bottleneck for training when the time for each node to execute push is in conflict, which will cause network congestion. The purpose of our modeling is to help relevant personnel obtain the most cost-effective overall system architecture solution by predicting what kind of equipment constitutes a system architecture that can avoid the performance bottleneck caused by communication.Based on the PS architecture and combined with the synchronization communication algorithm, mathematical models for training nodes with equal computing power and nonequal computing power is established. The one-round iteration time modeling on platforms with equal computing power are illustrated in formulas (29)–(31). Among them, T represents the total time of one-round iteration, Tcpu is obtained by formula (28). Tpull is the total time for all workers to pull parameters, and Tpush is the total time for all workers to send gradients. Tpull and Tpush are both communication time, and the communication performance is mainly manifested in Tpush. n is the number of workers, P and G are, respectively, the amount of parameters and gradient (need to be converted to bit), and B is the bandwidth of the parameter server (bit/s).(29)T=Tcpu+Tpush×n+Tpull×n,(30)Tpull=PB,(31)Tpush=GB.The one-round iteration time modeling on platforms with nonequal computing power and equal communication power are illustrated in Algorithm1. The main scenario considered in this paper is the case where multiple workers as well as PSs are connected to the same switch. In this case, it is common that each machine have equal communication power. And the link between the PS and the switch is the main communication bottleneck. Figure 4 gives a brief explanation of Algorithm 1. In the figure, nodes w0w3 have the same push time and pull time, but the calculation time is different and gradually increases. To calculate one round of iteration time T, first initialize T to the sum of the calculation time of w0 and the push time. Second, since T=Tcpu0+Tpush>=Tcpu1 and Tcpu0>Tcpu1, the push of w0 has not ended when w1 is calculated. Thanks to the communication bottleneck in the link between the PS and the switch, the gradient of w1 will enter the sending queue and wait for the gradient of w0 to be sent before pushing, and the push of w1 will finish after the push of w0 ended with Tpush, which can be shown in yellow. Therefore, the total time consumption from the start of local calculation of w0 to the end of the push of w1 is equal to the sum of calculation time of w0, the push time of w0 and the push time of w1, which represented as T. As shown in Figure 4, the current value of T can be represented by moving the push legend of w1 directly behind the push legend of w0. Third, since the calculation time of w2 is larger than the current value of T, so T is directly set to the sum of the calculation time of w2 and the push time of w2. Fourth, similar to the second step, the current value of T is the calculation time of w2 plus the push time of w2 and the push time of w3. Finally, add the pull time to T, that is the result of one round of iteration time (By default, the parameter server will use a balanced algorithm to ensure that each computing node can receive new parameters at the same time).Figure 4
One-round iteration time modeling algorithm with nonequal computing power CPUs.In our analysis, the ratio of computation time to communication time and the local computation time for each worker is uncertain. When the ratio of computation time to communication time is different, the one-round iteration time will be calculated differently according to Algorithm1 and Algorithm 2. In particular, when the communication time is greater than the computation time of each worker, the one-round iteration time is simply summarized as(32)T=n∗Tpull+Tmin+n∗Tpush,where Tmin is the local computation time of the fastest worker(with the best computing capability in n workers). In this case, the bottleneck push process starts as soon as the fastest worker completes its computation and the iteration time is not related to the computation time of other workers. In other words, under the communication bottleneck, replacing some of the workers with those with worse computational performance does not change the iteration training time, but it significantly saves computational resources compared with equal computing power. And it will be better to make the communication time as equal to the computation time as possible. When there is a communication bottleneck, replacing a higher bandwidth network device can result in a better performance improvement than replacing a better computing device. The reverse is also true.Algorithm 1: One-round iteration time modeling Algorithm with nonequal computing power CPUs and equal communication power.
Require:FLOPs, CPUhz1,CPUhz2…CPUhzn, simd=2, B,G,P,n.Ensure: One-round iteration time T.1: Calculate the computing time of each device by formula (28), and arrange the CPUs in ascending order as Tcpu1,Tcpu2…Tcpun;2: CalculateTpull and Tpush by formulas (30) and (31);3:T=Tcpu1+Tpush;4:fori in 2,ndo5:ifT≥Tcpuithen6:T+=Tpush;7:else8:T=Tcpui+Tpush;9:T+=n×Tpull;


## 5.3. Training Time Modeling of Stand-Alone GPU Platform

The floating-point computing power of GPU is usually expressed in FLOPs/s per second. The maximum GPU floating-point computing power for computing with stream processor isgpuhz×sp×fc, where gpuhz represents the GPU clock speed, sp represents the number of stream processors, and fc represents the number of floating-point operations that can be performed per stream processor in a single clock cycle. From this, the single iteration time mathematical model of a single-GPU computer can be established as formula (33). In this formula, the value of FLOPs is obtained by formula (27). In addition, the value of fc depends on whether the Fused-Multiply-Add(FMA) instruction set is used. If it is used, fc=2. Otherwise, fc=1.(33)Tgpu=FLOPsgpuhz×sp×fc.


## 5.4. Training Time Modeling of Distributed GPU Platform

Since sending data is executed by the CPU, a training device that uses GPU for distributed training can execute the two tasks of training and sending data in parallel. In this scenario, the first push of the training node occurs after the back-propagation completes the calculation of the gradient of the first layer. In addition, since most of today’s GPUs are clocked at more than 1.5 Ghz, even if there is only one stream processor, its calculation speed is 1.5× 32 Gbit/s. Therefore, if and only if the sending speed is greater than 48 Gbit/s, the sending time will be less than the calculation time. However, the number of stream processors of current GPUs is usually more than hundreds, so the calculation speed is obviously much faster than the sending speed. In this way, the calculation time of one round of iterative time modeling for distributed multimachines using GPUs can be regarded as the forward-propagation time plus the time to complete the first layer of back propagation. This time can be obtained by dividing the total time of back propagation by the number of pushes. The number of pushes depends on the experimental results, which are shown in Table 1. The one-round iteration time modeling algorithm of distributed GPU platform is shown in Algorithm 2.Table 1
Statistics of FLOPs and number of push.
Convolutional neural networkForward-propagationBack-propagationNumber of pushAlexnet1.6776×10+095.2554×10+0919Overfeat5.8584×10+091.2402×10+1020Vgg11A1.5224×10+101.1292×10+1024Vgg13B2.2623×10+101.1308×10+10—Vgg16C2.3548×10+101.1358×10+1034Vgg16D3.0947×10+101.1759×10+10—Vgg19E3.9270×10+101.2210×10+1040Resnet183.5924×10+99.7808×10+8—Resnet347.2898×10+91.8366×10+9—Resnet506.9943×10+91.8015×10+9269Resnet1011.4421×10+103.4114×10+9524Resnet1522.1845×10+104.7372×10+9779Algorithm 2: Training time modeling algorithm of distributed GPU platform.
Require: forwardpropagationFLOPs, backpropagationFLOPs, numberofpushes, the gpuhz,sp,fc,B,G,P of each node, batch−size set by each node, number of nodes n.Ensure: One-round iteration time T.1: CalculateTpull and Tpush by formulas (30) and (31);2:fori in 1,ndo3:FLOPsi=forwardpropagationFLOPs×batch−sizei+backpropagationFLOPs÷numberofpushes;4:Tgpui=FLOPsi÷gpuhzi×sp×fc5: SortTgpu1,Tgpu2…Tgpun in ascending order;6:T=Tgpu1+Tpush;7:fori in 2,ndo8:ifT≥Tgpuithen9:T+=Tpush;10:else11:T=Tgpui+Tpush;12:T+=n×Tpull;Now, we give a briefly explanation of Algorithm2 in conjunction with Figure 5. In the figure, w0w3 are four training nodes, and the red square represents the forward-propagation time. The blue square and the green square represent the back-propagation time and push time, respectively, and both are divided into several small segments according to the number of pushes. As mentioned above, the calculation speed is greater than the sending speed, so each green segment is slightly larger than the blue segment. First, when w0 finishes calculating the first blue segment, it starts to send the gradient. When the second blue segment is calculated, since the first gradient has not yet been sent, it enters the sending queue and waits. That is to say, the green segment representing the push of second gradient needs to be placed behind the green segment representing the push of first gradient, and same for subsequent operations. Second, when w1 calculates the first gradient (the first blue segment) and starts sending, since the gradient of w0 has not been sent yet (green square), the gradient of w1 enters the waiting queue. The corresponding push time is directly added to the push time of w0. At this time, the total time T equals to the forward-propagation time of w0 (red square), plus the calculation time of the first gradient of w0 (the first blue segment), plus the push time of w0 and w1 (green square and yellow square). In the third step, we can see that the forward-propagation time of w2 plus the back-propagation time of the first layer is greater than T, so the value of T is set to the forward-propagation time plus the back-propagation time of the first layer plus the push time of of w2. Fourth, it can be seen that the forward-propagation time of w3 plus its first-layer back-propagation calculation time is less than T. Therefore, the push time of w3 can be added to T as the current total time T. Finally, adding the total pull time pull × 4 is the iteration time T. Finally, by adding T to the total pull time (pull×4, the four gray squares in the figure), one round of iteration time T can be obtained.Figure 5
One-round iteration time modeling with GPUs.Similarly, when the communication time is greater than the computation time of each worker, the one round iteration time can also be summarized as ??. The iteration time is only related to the computation time of the fastest worker.


## 6. Performance Evaluation

### 6.1. Experimental Preparation and Experimental Environment Introduction

Existing neural network-related papers generally do not count the amount of floating-point operations, and there is no reliable statistical work on the amount of floating-point operations in neural networks. As a prework for performance evaluation, we have performed statistics on the forward-propagation and back propagation of a number of commonly used convolutional neural networks according to formulas in Section4. In addition, we also obtain the number of push gradients in one round of iteration of some neural networks according to related distributed experiments. The result is shown in Table 1.For the experimental environment, Ubuntu18.04 andPython3.7 are selected to implement the functional modules of the distributed machine learning performance modeling system. The construction of the distributed system is based on TensorFlow2.1, TensorFlow/benchmark, and CUDA-10.2. The CPUs are Intel ® Xeon™ E5-2660 @ 2.2 GHz and Intel ® Xeon™ E5-2620 @ 2.0 GHz. The GPUs are NVIDIA Quadro RTX 4000 8 GB @ 1.545Ghz and GeForce GTX 1060 6 GB @ 1.506 Ghz. The end network bandwidth is 1 Gb/s. Alexnet, Vgg11A, Vgg16D, and Vgg19E are selected as representatives of neural networks. The dataset is ImageNet, and the size of each sample is 224×224×3. The source code is available at https://github.com/bocway/Distributed-DNN-Modeling.


### 6.2. Experimental Results of CPU and GPU in Stand-Alone Platform

The experimental results of prediction time and actual measurement time of one round of iteration on stand-alone CPU platform are shown in Table2 and Figure 6. It can be seen that the experimental results in this section are relatively ideal with an average accuracy of more than 90%, which demonstrates the effectiveness of the proposed prediction model. The experiments prove that our modeling of the computation time is essentially correct. There are two main reasons for the error, including the randomness of system scheduling, and the limit of floating calculation accuracy of Python 3.7. Due to these two reasons, even if the same experiment is performed on the same device multiple times, the results will not be exactly the same.Table 2
Prediction time (PT), measurement Time (MT), and accuracy on stand-alone CPU platform.
Frequency (Ghz)bs = 32PTMTAccuracybs = 64PTMTAccuracy2.0Alexnet11.5911.740.987Alexnet22.1821.720.979Vgg11118.68108.620.915Vgg11234.68210.760.898Vgg16208.75230.260.897Vgg16415.06415.360.999Vgg19264.35265.870.994Vgg19526.15519.270.9872.2Alexnet10.549.660.917Alexnet20.1719.580.971Vgg1194.4191.420.968Vgg11186.68178.640.957Vgg16189.78174.320.919Vgg16377.33351.990.933Vgg19230.71218.680.948Vgg19459.19440.370.959Figure 6
Comparison between prediction time and measurement time on stand-alone CPU platform. (a) 2.0 GhzCPU, bs = 32, (b) 2.0 GhzCPU, bs = 64, (c) 2.2 GhzCPU, bs = 32, and (d) 2.2 GhzCPU, bs = 64.
(a)(b)(c)(d)The experimental results of prediction time and actual measurement time of one round of iteration on stand-alone GPU platform are shown in Table3 and Figure 7. Since the FMA instruction are not used in these experiments, the value of fc is 1. There are two reasons for the errors in stand-alone GPU training. The first one is the computing power is too strong, which finishes training too fast that the time management function cannot be accurately captured. The second one is some training models such as Alexnet are too small and the GPU’s stream processors are not all used. It means the GPU’s computing power is not fully utilized, which result in errors in the prediction. It can be seen that the accuracy of single-machine GPU training increases as the scale of the neural network increases. Vgg19 is the largest of these four neural networks, and the accuracy is above 96% under the actual measurement with bs=32 and bs=64. The scale of Vgg16 is slightly inferior to that of Vgg19, and the accuracy can also be stabilized at around 90%. However, Alexnet and Vgg11 have relatively large fluctuations in the accuracy between bs=32 and bs=64 due to the smaller neural network scale, which verifies the above-mentioned reasons for the errors.Table 3
Prediction time (PT), measurement time (MT), and accuracy on stand-alone GPU platform.
bs = 32PTMTAccuracybs = 64PTMTAccuracyAlexnet11.5911.740.987Alexnet22.1821.720.979Vgg11118.68108.620.915Vgg11234.68210.760.898Vgg16208.75230.260.897Vgg16415.06415.360.999Vgg19264.35265.870.994Vgg19526.15519.270.987Figure 7
Comparison between prediction time and measurement time on stand-alone GPU platform. (a) bs = 32 and (b) bs = 64.
(a)(b)


### 6.3. Experimental Results of CPU and GPU in Distributed Platform

The CPU frequency of the two training nodes is 2 Ghz (Intel ® Xeon™ E5-2620), and the CPU frequency of the parameter service node is 2.2 Ghz (Intel ® Xeon™ E5-2660). The experimental results of prediction time and actual measurement time of one round of iteration on distributed CPU platform are shown in Table4 and Figure 8.Table 4
Prediction time (PT), measurement time (MT), and accuracy on distributed CPU platform.
bs = 32PTMTAccuracybs = 64PTMTAccuracyAlexnet19.5115.280.783Alexnet30.0924.750.823Vgg11120.68115.270.955Vgg11222.34216.390.973Vgg16225.71211.860.939Vgg16432.77423.350.978Vgg19282.74275.610.975Vgg19544.54512.750.942Figure 8
Comparison between prediction time and measurement time on distributed CPU platform. (a) bs = 32 and (b) bs = 64.
(a)(b)It can be seen that the performance onAlexnet is only mediocre that the accuracy is 78.3% and 82.3% when the bs is 32 and 64, respectively. However, the accuracy of the other three convolutional neural networks can reach around 95%. Since the distributed platform is built on two virtual machines on a physical machine, we speculate that the parameter server only performs one pull operation on the physical machine, and the two virtual machines obtain updated parameters through the shared space. Due to the small scale of Alexnet, the training time is short, so less counting of the time of a pull has a great impact on accuracy. If the measurement time is added to the time of a pull, the accuracy of can be increased from 78.3% and 82.3% to about 86% and 89%, respectively. The other three convolutional neural networks have a much larger scale than Alexnet, which means less counting of the time of a pull has a little impact on accuracy.The experiment of distributed GPU platform uses two physical machines and each one has a GPU (NVIDIA quadro RTX4000). The CPU of the parameter service node is Intel ® Xeon™ E5-2660. It can be seen from Table5 and Figure 9 that the accuracy is relatively stable and mainly around 95%. This is because the GPU has strong computing power, and its calculation time is negligible in one round of iteration time. Therefore, the measurement time is mainly composed of the communication time of parameters and gradient transmission, which can maintain a high level of accuracy and stability.Table 5
Prediction time (PT), measurement time (MT), and accuracy on distributed GPU platform.
bs = 32PTMTAccuracybs = 64PTMTAccuracyAlexnet7.938.380.943Alexnet7.948.590.918Vgg1117.1418.420.925Vgg1117.2818.510.929Vgg1617.9918.640.964Vgg1618.2619.040.957Vgg1918.7418.930.990Vgg1919.0919.320.988Figure 9
Comparison between prediction time and measurement time on distributed GPU platform. (a) bs = 32 and (b) bs = 64.
(a)(b)We also complete experiments of distributed heterogeneous GPU platform by adding a heterogeneous GPU (GeForce GTX 1060 6 GB), which only has close to half the computing performance of the other GPU. Since the communication time in our experimental environment is greater than the computation time, the iteration time can be formulated by formula (32). It can be seem from Table 6 and Figure 10 that the accuracy is relatively stable and over 93%. Similarly, this is because the GPU has strong computing power, and its calculation time is negligible in one round of iteration time. To further verify the modeling accuracy, we increased the network bandwidth to 10GbE, and the result is shown in Table 7 and Figure 11. It can be seem that the accuracy is relatively mainly over 80% and the iteration training time is reduced significantly by alleviating the network bottlenecks. However the accuracy decreases by 10% compared to the result connected with 1 GbE by the below reasons:(1)
Communication time error: we experimented and found that there is startup overheada in the pull and push process, which is not related to batch size and the bandwidth we use. In our experimental environment, the startup overhead a is about 0.5s, which cannot be ignored in our 10 GbE experiments.(2)
Computation time error: in the GPU training process, it exits the process of memory copy from host to GPU, which cannot be ignored if the local computation time of worker is short.Table 6
Prediction time (PT), measurement time (MT), and accuracy on distributed heterogeneous GPU platform which connected with 1GbE.
bs = 16PTMTAccuracybs = 32PTMTAccuracyAlexnet12.1712.830.949Alexnet12.1912.8170.951Vgg1125.5827.430.933Vgg1125.6527.510.933Vgg1626.7128.570.935Vgg1628.8528.660.937Vgg1927.7629.630.937Vgg1927.9429.910.934Resnet504.955.230.947Resnet504.985.240.95Figure 10
Comparison between prediction time and measurement time on distributed heterogeneous GPU platform with 1 GbE. (a) bs = 16 and (b) bs = 32.
(a)(b)Table 7
Prediction time (PT), measurement time (MT), and accuracy on distributed heterogeneous GPU platform which connected with 10 GbE.
bs = 16PTMTAccuracybs = 32PTMTAccuracyAlexnet1.231.440.854Alexnet1.231.390.885Vgg112.623.190.821Vgg112.693.280.820Vgg162.803.400.824Vgg162.943.390.867Vgg192.943.480.845Vgg193.113.480.894Resnet500.520.550.944Resnet500.550.610.902Figure 11
Comparison between prediction time and measurement time on distributed heterogeneous GPU platform with 10 GbE. (a) bs = 16 and (b) bs = 32.
(a)(b)As for Resnet50, the startup overhead can be ignored in our experiment and percentage of computation is much higher than the others. So, it still maintains high accuracy.In this section, we built a distributed PS system based on the Linux system and TensorFlow/benchmark. Through the use of synchronous communication algorithms, distributed measurements were carried out on various types of CPUs and GPUs. Through the analysis of the results, it is known that although the cause of the error cannot be solved by mathematical modeling, the mathematical model established in this paper still has a high level of accuracy of around90%.


## 6.1. Experimental Preparation and Experimental Environment Introduction

Existing neural network-related papers generally do not count the amount of floating-point operations, and there is no reliable statistical work on the amount of floating-point operations in neural networks. As a prework for performance evaluation, we have performed statistics on the forward-propagation and back propagation of a number of commonly used convolutional neural networks according to formulas in Section4. In addition, we also obtain the number of push gradients in one round of iteration of some neural networks according to related distributed experiments. The result is shown in Table 1.For the experimental environment, Ubuntu18.04 andPython3.7 are selected to implement the functional modules of the distributed machine learning performance modeling system. The construction of the distributed system is based on TensorFlow2.1, TensorFlow/benchmark, and CUDA-10.2. The CPUs are Intel ® Xeon™ E5-2660 @ 2.2 GHz and Intel ® Xeon™ E5-2620 @ 2.0 GHz. The GPUs are NVIDIA Quadro RTX 4000 8 GB @ 1.545Ghz and GeForce GTX 1060 6 GB @ 1.506 Ghz. The end network bandwidth is 1 Gb/s. Alexnet, Vgg11A, Vgg16D, and Vgg19E are selected as representatives of neural networks. The dataset is ImageNet, and the size of each sample is 224×224×3. The source code is available at https://github.com/bocway/Distributed-DNN-Modeling.


## 6.2. Experimental Results of CPU and GPU in Stand-Alone Platform

The experimental results of prediction time and actual measurement time of one round of iteration on stand-alone CPU platform are shown in Table2 and Figure 6. It can be seen that the experimental results in this section are relatively ideal with an average accuracy of more than 90%, which demonstrates the effectiveness of the proposed prediction model. The experiments prove that our modeling of the computation time is essentially correct. There are two main reasons for the error, including the randomness of system scheduling, and the limit of floating calculation accuracy of Python 3.7. Due to these two reasons, even if the same experiment is performed on the same device multiple times, the results will not be exactly the same.Table 2
Prediction time (PT), measurement Time (MT), and accuracy on stand-alone CPU platform.
Frequency (Ghz)bs = 32PTMTAccuracybs = 64PTMTAccuracy2.0Alexnet11.5911.740.987Alexnet22.1821.720.979Vgg11118.68108.620.915Vgg11234.68210.760.898Vgg16208.75230.260.897Vgg16415.06415.360.999Vgg19264.35265.870.994Vgg19526.15519.270.9872.2Alexnet10.549.660.917Alexnet20.1719.580.971Vgg1194.4191.420.968Vgg11186.68178.640.957Vgg16189.78174.320.919Vgg16377.33351.990.933Vgg19230.71218.680.948Vgg19459.19440.370.959Figure 6
Comparison between prediction time and measurement time on stand-alone CPU platform. (a) 2.0 GhzCPU, bs = 32, (b) 2.0 GhzCPU, bs = 64, (c) 2.2 GhzCPU, bs = 32, and (d) 2.2 GhzCPU, bs = 64.
(a)(b)(c)(d)The experimental results of prediction time and actual measurement time of one round of iteration on stand-alone GPU platform are shown in Table3 and Figure 7. Since the FMA instruction are not used in these experiments, the value of fc is 1. There are two reasons for the errors in stand-alone GPU training. The first one is the computing power is too strong, which finishes training too fast that the time management function cannot be accurately captured. The second one is some training models such as Alexnet are too small and the GPU’s stream processors are not all used. It means the GPU’s computing power is not fully utilized, which result in errors in the prediction. It can be seen that the accuracy of single-machine GPU training increases as the scale of the neural network increases. Vgg19 is the largest of these four neural networks, and the accuracy is above 96% under the actual measurement with bs=32 and bs=64. The scale of Vgg16 is slightly inferior to that of Vgg19, and the accuracy can also be stabilized at around 90%. However, Alexnet and Vgg11 have relatively large fluctuations in the accuracy between bs=32 and bs=64 due to the smaller neural network scale, which verifies the above-mentioned reasons for the errors.Table 3
Prediction time (PT), measurement time (MT), and accuracy on stand-alone GPU platform.
bs = 32PTMTAccuracybs = 64PTMTAccuracyAlexnet11.5911.740.987Alexnet22.1821.720.979Vgg11118.68108.620.915Vgg11234.68210.760.898Vgg16208.75230.260.897Vgg16415.06415.360.999Vgg19264.35265.870.994Vgg19526.15519.270.987Figure 7
Comparison between prediction time and measurement time on stand-alone GPU platform. (a) bs = 32 and (b) bs = 64.
(a)(b)


## 6.3. Experimental Results of CPU and GPU in Distributed Platform

The CPU frequency of the two training nodes is 2 Ghz (Intel ® Xeon™ E5-2620), and the CPU frequency of the parameter service node is 2.2 Ghz (Intel ® Xeon™ E5-2660). The experimental results of prediction time and actual measurement time of one round of iteration on distributed CPU platform are shown in Table4 and Figure 8.Table 4
Prediction time (PT), measurement time (MT), and accuracy on distributed CPU platform.
bs = 32PTMTAccuracybs = 64PTMTAccuracyAlexnet19.5115.280.783Alexnet30.0924.750.823Vgg11120.68115.270.955Vgg11222.34216.390.973Vgg16225.71211.860.939Vgg16432.77423.350.978Vgg19282.74275.610.975Vgg19544.54512.750.942Figure 8
Comparison between prediction time and measurement time on distributed CPU platform. (a) bs = 32 and (b) bs = 64.
(a)(b)It can be seen that the performance onAlexnet is only mediocre that the accuracy is 78.3% and 82.3% when the bs is 32 and 64, respectively. However, the accuracy of the other three convolutional neural networks can reach around 95%. Since the distributed platform is built on two virtual machines on a physical machine, we speculate that the parameter server only performs one pull operation on the physical machine, and the two virtual machines obtain updated parameters through the shared space. Due to the small scale of Alexnet, the training time is short, so less counting of the time of a pull has a great impact on accuracy. If the measurement time is added to the time of a pull, the accuracy of can be increased from 78.3% and 82.3% to about 86% and 89%, respectively. The other three convolutional neural networks have a much larger scale than Alexnet, which means less counting of the time of a pull has a little impact on accuracy.The experiment of distributed GPU platform uses two physical machines and each one has a GPU (NVIDIA quadro RTX4000). The CPU of the parameter service node is Intel ® Xeon™ E5-2660. It can be seen from Table5 and Figure 9 that the accuracy is relatively stable and mainly around 95%. This is because the GPU has strong computing power, and its calculation time is negligible in one round of iteration time. Therefore, the measurement time is mainly composed of the communication time of parameters and gradient transmission, which can maintain a high level of accuracy and stability.Table 5
Prediction time (PT), measurement time (MT), and accuracy on distributed GPU platform.
bs = 32PTMTAccuracybs = 64PTMTAccuracyAlexnet7.938.380.943Alexnet7.948.590.918Vgg1117.1418.420.925Vgg1117.2818.510.929Vgg1617.9918.640.964Vgg1618.2619.040.957Vgg1918.7418.930.990Vgg1919.0919.320.988Figure 9
Comparison between prediction time and measurement time on distributed GPU platform. (a) bs = 32 and (b) bs = 64.
(a)(b)We also complete experiments of distributed heterogeneous GPU platform by adding a heterogeneous GPU (GeForce GTX 1060 6 GB), which only has close to half the computing performance of the other GPU. Since the communication time in our experimental environment is greater than the computation time, the iteration time can be formulated by formula (32). It can be seem from Table 6 and Figure 10 that the accuracy is relatively stable and over 93%. Similarly, this is because the GPU has strong computing power, and its calculation time is negligible in one round of iteration time. To further verify the modeling accuracy, we increased the network bandwidth to 10GbE, and the result is shown in Table 7 and Figure 11. It can be seem that the accuracy is relatively mainly over 80% and the iteration training time is reduced significantly by alleviating the network bottlenecks. However the accuracy decreases by 10% compared to the result connected with 1 GbE by the below reasons:(1)
Communication time error: we experimented and found that there is startup overheada in the pull and push process, which is not related to batch size and the bandwidth we use. In our experimental environment, the startup overhead a is about 0.5s, which cannot be ignored in our 10 GbE experiments.(2)
Computation time error: in the GPU training process, it exits the process of memory copy from host to GPU, which cannot be ignored if the local computation time of worker is short.Table 6
Prediction time (PT), measurement time (MT), and accuracy on distributed heterogeneous GPU platform which connected with 1GbE.
bs = 16PTMTAccuracybs = 32PTMTAccuracyAlexnet12.1712.830.949Alexnet12.1912.8170.951Vgg1125.5827.430.933Vgg1125.6527.510.933Vgg1626.7128.570.935Vgg1628.8528.660.937Vgg1927.7629.630.937Vgg1927.9429.910.934Resnet504.955.230.947Resnet504.985.240.95Figure 10
Comparison between prediction time and measurement time on distributed heterogeneous GPU platform with 1 GbE. (a) bs = 16 and (b) bs = 32.
(a)(b)Table 7
Prediction time (PT), measurement time (MT), and accuracy on distributed heterogeneous GPU platform which connected with 10 GbE.
bs = 16PTMTAccuracybs = 32PTMTAccuracyAlexnet1.231.440.854Alexnet1.231.390.885Vgg112.623.190.821Vgg112.693.280.820Vgg162.803.400.824Vgg162.943.390.867Vgg192.943.480.845Vgg193.113.480.894Resnet500.520.550.944Resnet500.550.610.902Figure 11
Comparison between prediction time and measurement time on distributed heterogeneous GPU platform with 10 GbE. (a) bs = 16 and (b) bs = 32.
(a)(b)As for Resnet50, the startup overhead can be ignored in our experiment and percentage of computation is much higher than the others. So, it still maintains high accuracy.In this section, we built a distributed PS system based on the Linux system and TensorFlow/benchmark. Through the use of synchronous communication algorithms, distributed measurements were carried out on various types of CPUs and GPUs. Through the analysis of the results, it is known that although the cause of the error cannot be solved by mathematical modeling, the mathematical model established in this paper still has a high level of accuracy of around90%.


## 7. Conclusions and Further Study

Based on the PS architecture, this paper deeply studies various key factors that affect the performance of distributed machine learning training, and combines these factors to establish the one round of iterative time prediction model for training on stand-alone/distributed CPU/GPU platforms. In addition, this paper also designed rigorous experiments to verify that the accuracy of the proposed performance prediction model is higher than90% in most cases. In addition, the highest accuracy rate 99.4% is achieved in the prediction of stand-alone CPU Platform with Vgg19E. As for our future work, on the one hand, considering the increase of training nodes will lead to the emergence of communication bottlenecks, we will study one round of iterative time modeling of multiparameter servers. On the other hand, we are going to incorporate local SGD synchronization communication into the scope of modeling.



---

*Source: 2663115-2023-02-21.xml*