## 3 The Proposed Method: SHAT
### Algorithm and Performance Consideration  
Algorithm 1 shows the whole training process of SHAT. At iteration \(t\), a worker \(i\) computes its gradients \(g_{t}^{i}\) based on the data sampled from \(X\), sends \(g_{t}^{i}\) to PS, and receives the updated global model \(\widehat{w}\) and \(c^{i}\) (lines 3-6 in Algorithm 1). Then, the worker updates its local model using our strategy represented in Equation 4 (lines 7-8 in Algorithm 1). While, whenever PS receives the gradients \(g^{i}\) from each worker, PS computes the degree of the heterogeneity of the other workers \(c^{k}(k\
eq i)\) (lines 13-19 in Algorithm 1). Then, PS updates the global model by applying the received gradients and sends the updated global model \(\widehat{w}\) and the degree of the staleness \(c^{k}\) to the worker. We highlight again that in SHAT, each worker updates its local models by taking into account (1) the scale of distributed training and (2) the heterogeneity among workers.  
```
1:FunctionSHAT_WORKER(\(w_{0},X,f,i\)):
2:for\(t=0,1,\ldots\)do
3:\(b\leftarrow\textsf{sampleBatch}(X)\)
4:\(g_{t}^{i}\leftarrow\frac{1}{|b|}\sum_{x\in b}\
abla F(w_{t},x)\)
5:sendGradientsToPS(\(g_{t}^{i}\))
6:\(\widehat{w},c^{i}\leftarrow\textsf{receiveModelFromPS}()\)
7:\(\alpha^{i}\gets 1-\frac{s^{i}}{\log n},\;\;s^{i}\leftarrow\frac{n}{c^{i}}\;\; \;//\;\textsf{Scale and heterogeneity aware strategy}\)
8:\(w^{i}\leftarrow(1-\alpha^{i})w^{i}+\alpha^{i}\widehat{w}\;\;\;//\;\textsf{ Generalized update rule}\)
9:endfor
10:FunctionSHAT_PS(\(n,\eta\)):
11:\(C\leftarrow\{0,0,\ldots,0\},C\in\mathbb{N}^{n}\)
12:\(c^{i}\in C\)
13:for\(s=0.1,\ldots\)do
14: Receive \(g^{i}\) from worker \(i\)
15:\(g^{i}\leftarrow\textsf{receiveGradientFromWorker}()\)
16:for\(k=0,1,\ldots,n-1\)do//Computing the staleness of each worker
17:if\(k\
eq i\)then
18:\(c^{k}\gets c^{k}+1\)
19:endif
20:endfor
21:\(\widehat{w}\leftarrow\widehat{w}-\eta\cdot g^{i}\)
22:sendUpdateModelToWorker(\(\widehat{w},c^{i}\))
23:\(c^{i}\gets 0\)
24:endfor
25:return\(\widehat{w}\)
```  
**Algorithm 1** Training processes of a worker and PS in SHAT  
In PS-based distributed training, PS may become the bottleneck of the entire training since a single PS is in charge of aggregating the training results (i.e., gradients) from all workers and sending back the updated global model to each worker. To alleviate this problem, parameter sharding [10; 28; 29; 34; 40] is generally applied to PS-based distributed training. Parameter sharding divides the parameters in the global model and distributes them into multiple PSs to process them in parallel as illustrated in Figure 3. Via parameter sharding, the communication and computation overhead are distributed to multiple PSs, thus improving the overall training performance.  
Layerwise parameter sharing is normally used because a layer is represented as a single data structure in many DNN frameworks (e.g., Tensor in Tensorflow) so that it can be processed sequentially, which means that the parameters in the same layer are stored in the same PS. In some DNN models, however, a single layer may contain the majority of the entire model parameters. For instance, in the VGG-16 model [2], the last two fully-connected layers are in charge of more than 90% of all parameters. In this case, the PS in charge of the extremely large layers suffers from a big burden, thereby becoming a bottleneck in the overall training. To address this issue, we apply memorwise parameter sharding to SHAT. Memorywise sharding defines the maximum size of sharded parameters and has multiple PSs process the parameters in a layer together if it is larger than the maximum size.