1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| In Parameter Server (PS)-based distributed training, the inherent many-to-one communication pattern can cause severe network congestion, significantly limiting the overall training throughput. To mitigate bandwidth contention on the PS side, we further propose an \textit{Interleaved Communication Scheduling strategy}. Building upon the gradient fusion strategy, this method interleaves the transmission of merged gradients, effectively reducing simultaneous large-volume transfers and alleviating network resource contention among workers.
Fig.~\ref{fig:interleaved_comm} illustrates the comparison between the Merged-gradient communication strategy and the proposed Interleaved merged-gradient communication scheduling strategy.Specifically, Fig.~\ref{fig:interleaved_comm}(a) shows gradient fusion alone, where consecutive layers are merged to reduce startup latency but still result in considerable concurrent network traffic.Fig.~\ref{fig:interleaved_comm}(b) illustrates the proposed interleaved merged-gradient scheduling, which combines both \textit{inter-iteration} and \textit{intra-iteration} interleaving. The former reduces the data volume communicated per iteration, while the latter decreases the concurrency among workers, thereby lowering peak network usage and improving overall communication efficiency.
\begin{figure}[htbp]
\centering
\subfigure[Merged-gradient communication.]{
\includegraphics[width=0.9\linewidth]{figures/fusion_communication.png}
}
\subfigure[Interleaved merged-gradient communication.]{
\includegraphics[width=0.9\linewidth]{figures/interleaved_fusion_communication.png}
}
\caption{Comparison between merged-gradient communication and interleaved merged-gradient communication scheduling.}
\label{fig:interleaved_comm}
\end{figure}
The goal of inter-iteration interleaving is to stagger the communication of adjacent parameter groups across different iterations. Based on the gradient fusion strategy, consecutive layers are first merged into transmission units, which are then distributed across synchronization periods. Given a synchronization period $T$, the $i$-th group participates in synchronization during iterations indexed as $i \% T + kT$ ($k=0,1,2,\dots,N$). This mechanism spreads parameter synchronization evenly across iterations, effectively reducing per-iteration communication load.
This approach inherently lowers the communication frequency of each parameter group. In most iterations, local models update independently and only synchronize globally during assigned periods. However, such independent exploration may cause divergence among local models. Simple averaging at synchronization points could undermine useful information learned locally. To address this, we adopt Elastic Averaging SGD (EASGD)~\cite{zhang2015deep} for parameter updates, as described in Eqs.~(\ref{eq:local_update}) and (\ref{eq:global_update}). The local update rule constrains each worker to remain close to the global consensus, while the global update retains part of the historical global state, striking a balance between local exploration and global consistency.
\begin{align}
w_{t+1}^k &= w_t^k - \eta g_t^k(w_t^k) - \alpha(w_t^k - w_t) \label{eq:local_update} \\
w_{t+1} &= (1 - \beta) w_t + \beta \left(\frac{1}{K}\sum_{k=1}^{K}w_t^k\right) \label{eq:global_update}
\end{align}
Intra-iteration interleaving staggers the communication times of workers within the same iteration, preventing simultaneous usage of network resources and avoiding congestion. Unlike asynchronous training, this method ensures that each iteration’s global update still incorporates all workers, maintaining synchronous training properties in both accuracy and convergence.
With inter-iteration interleaving, only a subset of parameter groups communicate in each iteration. For example, in Fig.~\ref{fig:Inter-iteration}, when parameters are divided into nine groups (0--8) with a synchronization period of three, groups 2, 5, and 8 communicate in iteration 1; groups 1, 4, and 7 in iteration 2; and groups 0, 3, and 6 in iteration 3. This pattern repeats every three iterations. Within each iteration, the involved groups are non-adjacent, resulting in idle communication slots. These slots can be allocated to workers, reducing concurrency and mitigating network congestion.
\begin{figure}[htbp]
\centering
\includegraphics[width=0.75\linewidth]{figures/Inter-iteration.png}
\caption{Illustration of inter-iteration interleaving.}
\label{fig:Inter-iteration}
\end{figure}
Fig.~\ref{fig:intra_iter_slots} illustrates intra-iteration interleaving at iteration 2, with nine groups and a staggering period of three. For instance, group 1 communicates in the slot between groups 5 and 2, while group 4 communicates between groups 8 and 5.
\begin{figure}[htbp]
\centering
\includegraphics[width=0.75\linewidth]{figures/intra_iter_slots.png}
\caption{Illustration of intra-iteration interleaving.}
\label{fig:intra_iter_slots}
\end{figure}
Since the backward computation time varies across layers, different groups have unequal available slots. Algorithm~\ref{alg:allocate_slots} provides the slot allocation rule. For a group $k_0$, the allowed communication duration is bounded by the start of group $k_0+T$, i.e.,
\[
\tau_b(k_0+T) - \tau_b(k_0),
\]
which can be approximated as
\[
\tau_b(k_0+T+1) - \tau_b(k_0+1),
\]
where $\tau_b$ denotes the backward start time of the earliest layer in a group. As shown in Fig.~\ref{fig:intra_iter_slots}, for the example in Fig.~\ref{fig:Inter-iteration} (9 groups, $T=3$), at iteration 2, the slot for group 1 equals the difference between the start times of group 5 and group 2.
For the last groups in an iteration (e.g., groups 6, 7, and 8 in Fig.~\ref{fig:Inter-iteration}), no group $k_0+T$ exists. In this case, the slot extends until the start of the next iteration’s forward propagation. The available duration consists of two parts: (1) from the start of communication of the current group to the end of backward propagation; and (2) from the end of backward to the start of the next forward pass. Prior work~\cite{liu2022modeling} shows that backward takes approximately twice as long as forward, so the second part is approximated as half of the first. The total communication time is then the sum of both parts.
During scheduling, we directly compute slots using the timeline $\tau_b$, and with the known group index $g^{(l)}$ for each layer, evenly divide them among the $P$ workers to avoid network congestion.
\begin{algorithm}[htbp]
\caption{Allocate Communication Slot for Each Group}
\label{alg:allocate_slots}
\KwIn{$N$: number of merged groups; $\tau_b[1...L]$: backward start time of each layer;\\
$P$: number of workers; $g = [g^{(1)}, g^{(2)}, \dots, g^{(L)}]$: group index; $T$: stagger period}
\KwOut{$s$: slot of each group}
Initialize $end\_comp$; \tcp*{Backward phase completion time}
Initialize $\tau_g[1...N]$; \tcp*{Backward start time of each group}
\For{$idx = 0 \rightarrow N-1$}{
\tcp{Current group communication start}
\eIf{$idx + 1 < N$}{
$cur\_comm \gets \tau_g[idx + 1]$;
}{
$cur\_comm \gets end\_comp$;
}
\tcp{Next group communication start}
\eIf{$idx + 1 + T < N$}{
$next\_comm \gets \tau_g[idx + 1 + T]$;
}{
\eIf{$idx + 1 + T == N$}{
$next\_comm \gets end\_comp$;
}{
$next\_comm \gets end\_comp + 0.5 \cdot (end\_comp - cur\_comm)$;
}
}
$s[idx] \gets (next\_comm - cur\_comm)/P$;
}
\end{algorithm}
|
