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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| \subsection{节点匹配算法}
深度学习模型的训练是一个迭代式的渐近寻优过程。每一次反向传播计算完成后，都需要进行一次参数同步，因此同步算法的执行效率直接决定了系统整体的训练性能。在 tree 算法的多级同步机制中，以 reduce 阶段为例，每一级的通信都由若干通信对并发执行，其中一个节点作为 \emph{发送方} 完成数据传输，另一个节点作为 \emph{接收方} 完成聚合。需要注意的是，只有当本级中所有通信对均完成同步后，系统才能进入下一级通信。换言之，tree 算法的整体执行时间取决于各级中同步最慢的通信对。
根据上一节中生成树的构造方案，每一级的构建过程可抽象为两个集合（已加入生成树的集合 $U$ 与未加入的集合 $V$）之间的二分图匹配问题。匹配方式将直接影响该级的同步完成时间。在图论中，二分图匹配的基本原则是：两个集合中的节点可以两两配对形成匹配边，但每个节点最多只能与一个节点匹配。当匹配边数达到最大时称为 \textbf{最大匹配}；若在所有最大匹配中进一步使匹配边权重之和最大化，则称为 \textbf{最优匹配}。
Kuhn–Munkres (KM) 算法是解决加权二分图最优匹配问题的经典方法，时间复杂度约为 $O(n^3)$。该算法的核心思想是：当匹配发生冲突时，通过寻找增广路径并调整顶点权值，不断扩大二分子图的可匹配边集，直至获得最大权重匹配。其基本执行过程如图~\ref{fig:KM_flow} 所示。
在本文 tree 算法的场景下，设某一级构造过程中已加入生成树的节点集合为 $U$，未加入生成树的节点集合为 $V$。若采用 KM 算法求解该层的匹配，其优化目标可形式化为下面的加权最优匹配问题：
\begin{align}
\max \;& \sum_{i\in U}\sum_{j\in V} w(i,j)\, a_{ij} \tag{4-1}\label{eq:mwmm}\\
\text{s.t.}\;& \sum_{i\in U} a_{ij}=1,\quad j\in V \label{eq:mwmm-con1}\\
& \sum_{j\in V} a_{ij}=1,\quad i\in U \label{eq:mwmm-con2}
\end{align}
其中，$a_{ij}\in\{0,1\}$ 表示边 $(i,j)$ 是否被选中，$w(i,j)$ 表示边的带宽。
然而，\eqref{eq:mwmm}–\eqref{eq:mwmm-con2} 最大化的是匹配边权重的\emph{总和}，并不一定能带来最优的同步性能。由于系统必须等待最慢通信对完成，整体效率实际上受制于 \textbf{瓶颈链路}。换言之，KM 算法得到的“最大权匹配”并非本文场景下的“最优匹配”。
如图~\ref{fig:matching_example} 所示，集合 $U=\{A,B\}$，集合 $V=\{a,b\}$，边权表示带宽。两种匹配方式如表~\ref{tab:match_compare} 所示：方案（二）的权重和更大，但最小边权更小，从同步角度更不利。
因此，本文将问题建模为 \textbf{瓶颈匹配（Bottleneck Matching）}，目标是在所有可行匹配方案中最大化匹配结果的最小边权：
\begin{align}
\max \;& \min_{\,i\in U,\, j\in V:\, a_{ij}=1}\; w(i,j) \tag{4-4}\label{eq:bm-obj}\\
\text{s.t.}\;& \sum_{i\in U} a_{ij}=1,\quad j\in V \label{eq:bm-con1}\\
& \sum_{j\in V} a_{ij}=1,\quad i\in U \label{eq:bm-con2}
\end{align}
为此，本文提出 \textbf{瓶颈感知匹配算法}（Bottleneck-Aware Matching, BAM）：
(1) 引入全局带宽阈值 $t$，仅保留 $w(i,j)\ge t$ 的边参与匹配；
(2) 在阈值子图上使用匈牙利算法寻找最大匹配；
(3) 基于匹配是否成功，通过二分查找动态调整 $t$（失败则降低，成功则升高），直至收敛；
(4) 最终由保证最大匹配成功的最大阈值 $t^\star$ 给出结果。算法流程如算法~\ref{alg:bottleneck} 所示。
与 KM 相比，BAM 主要改进有两点：（i）\textbf{全局阈值机制}：统一筛选边，避免低带宽链路成为瓶颈；（ii）\textbf{高效搜索策略}：在边权集合上采用二分查找快速定位最优阈值。
此外，当系统总节点数 $S$ 不是 $2$ 的幂时，生成树构造需执行 $\log_2 S + 1$ 次匹配。前 $\log_2 S$ 次满足 $|U|\le|V|$；最后一轮通常 $|U|>|V|$，为保证算法正确性，可交换 $U$ 与 $V$ 的角色，匹配完成后再将结果还原。
\begin{figure}[t]
\centering
\includegraphics[width=0.85\linewidth]{figures/KM_flow.pdf}
\caption{KM 算法流程示意图。}
\label{fig:KM_flow}
\end{figure}
\begin{figure}[t]
\centering
\includegraphics[width=0.5\linewidth]{figures/matching_example.pdf}
\caption{匹配示例。边权表示链路带宽。方案 (1)：$A\!-\!a$, $B\!-\!b$；方案 (2)：$A\!-\!b$, $B\!-\!a$。}
\label{fig:matching_example}
\end{figure}
\begin{table}[t]
\centering
\caption{两种匹配方式的比较（指标：权重和与最小边权）}
\label{tab:match_compare}
\begin{tabular}{ccc}
\toprule
匹配方式 & 权重和 & 最小边权 \\
\midrule
方案（一） & 9 & 4 \\
方案（二） & 10 & 3 \\
\bottomrule
\end{tabular}
\end{table}
\begin{algorithm}[t]
\caption{Bottleneck Matching}
\label{alg:bottleneck}
\KwIn{$U$: left-side nodes; $V$: right-side nodes; $L$: edge weights in bipartite graph; $M$: adjacency matrix of topology}
\KwOut{$res$: best matching result}
$low \gets 0$, $high \gets len(L)-1$\;
\While{$low \leq high$}{
$mid \gets (low + high)/2$\;
$threshold \gets L[mid]$ \tcp*{Current threshold}
reset $u.match=None$, $v.match=None$ for all $u \in U, v \in V$\;
$cnt \gets 0$\;
\For{each $u \in U$}{
reset $v.visit=false$ for each $v \in V$\;
\If{MATCH($u$, $threshold$)}{
$cnt \gets cnt+1$\;
}
}
\If{$cnt =$ max matches}{
$low \gets mid+1$\;
record current result $res$\;
}
\Else{
$high \gets mid-1$\;
}
}
\BlankLine
\SetKwProg{Fn}{Function}{:}{}
\Fn{MATCH($u$, $threshold$)}{
\For{each $v \in V$}{
\If{$v.visit$}{continue\;}
\If{$M[u][v] \geq threshold$}{
$v.visit \gets true$\;
\If{$v.match$ is None or MATCH($v.match$, $threshold$)}{
$u.match \gets v$\;
$v.match \gets u$\;
\Return true\;
}
}
}
\Return false\;
}
\end{algorithm}
|
