# Pipelined Stochastic Gradient Descent with Taylor Expansion
## 3 Proposed Methods  
### Pipelined SGD Work Scheduling and Model Replicas for the Proposed Methods  
The proposed work scheduling for pipelined SGD is depicted in the left part of Figure 2. It shows the simultaneous execution of forward or backward passes for different mini-batches. For example, when the forward pass of the 5 th mini-batch is executed in the 2 nd computing node (denoted as \(F_{2}^{5}\)), the forward pass of the 6 th mini-batch is executed concurrently in the first computing node (denoted as \(F_{1}^{6}\)). Similarly, \(B_{2}^{1}\), which denotes the backward pass of the 1 st mini-batch in the second computing node, and \(B_{3}^{2}\), which denotes the backward pass of the 2 nd mini-batch in the 3 rd computing node, are executed in parallel.  
The master model and the model replicas required to prevent the weight inconsistency problem caused by the naive pipelined SGD are shown in the right part of Figure 2.  
Figure 2: Work scheduling (**left** part) and model replicas (**right** part) of the proposed pipelined SGD. \(F_{n}^{t}\) and \(B_{n}^{t}\) represent the forward pass and backward pass, respectively, at computing node \(n\) for mini-batch index \(t\). \(W_{n}^{t}\) represents the local model parameters in computing node \(n\) for mini-batch index \(t\). \(\bar{W}_{n}\) represents the master model parameters in computing node \(n\).  
The proposed pipelined SGD creates \(2N-1\) model replicas when the number of computing nodes is \(N\). In Figure 2, for example, seven model replicas are created for the pipelined SGD with four computing nodes. To access the model parameters used in \(F_{3}^{3}\) (the forward pass of the 3 rd mini-batch in the 3 rd computing node) and the output values of \(F_{3}^{3}\) when \(B_{3}^{3}\) (the backward pass of the 3 rd mini-batch in the 3 rd computing node) is executed, the model parameters used in \(F_{3}^{3}\) must not be changed during the backward passes from \(B_{3}^{1}\) to \(B_{3}^{2}\), and the output values of \(F_{3}^{3}\) must not be changed after forward passes \(F_{3}^{4}\) and \(F_{3}^{5}\). Therefore, three sets of model parameters of different time points (\(W_{3}^{3}\), \(W_{3}^{4}\), and \(W_{3}^{5}\)) must be maintained at the 3 rd computing node until \(B_{3}^{3}\) is executed. Also, three sets of output values from \(F_{3}^{3}\), \(F_{3}^{4}\), and \(F_{3}^{5}\) must be maintained. Similarly, seven sets of model parameters (\(W_{1}^{1}\), \(W_{1}^{2}\),..., \(W_{1}^{7}\)) of different time points and seven sets of output values from \(F_{1}^{1}\), \(F_{1}^{2}\),..., \(F_{1}^{7}\) must be maintained until \(B_{1}^{1}\) is executed at the first computing node. To support data parallelism, however, \(2N-1\) sets of model parameters and output values of different time points must be maintained at every computing node because any local model replica of the same time point as the one in the first computing node should be accessible in each computing node. Since \(2N-1\), different DNN models use different mini-batches in parallel training, and data parallelism occurs as well as model parallelism in the proposed pipelined SGD. In this case, the master model corresponds to the model of the parameter server in ASGD; by contrast, in the proposed pipelined SGD, each stage of the master model is separately stored at each computing node by model parallelism (\(\bar{W}_{1}\), \(\bar{W}_{2}\), \(\bar{W}_{3}\), and \(\bar{W}_{4}\) in Figure 2).  
Combining these \(2N-1\) model replicas to produce the master model can be performed using data parallelism techniques. ASGD algorithms have many advantages over SSGD, including efficiency and error resilience, so these ASGD algorithms can be applied to combine model replicas. However, direct use of ASGD induces the delayed gradient problem, as in the original data parallelism algorithms. Therefore, we propose a new pipelined SGD algorithm, TaylorPipe, which applies the Taylor expansion to mitigate the delayed gradient problem of the naive pipeline parallelism.