跳到主要内容

拓扑参数化编码

核心要点：

  • 邻接矩阵不可搜：$O(2^{N^2})$ 在 N > 100 即不可行，16k GPU 时 $> 10^{10^7}$ 量级
  • 三种压缩范式：专家先验模板 （ATOP 11 类） / 约束 DSL (Condor SMT) / 群论约束 (TopoOpt Circulant)
  • ATOP 11 类：3 类 User Input + 5 类 Inter-layer + 6 类 Intra-layer，覆盖 Clos / Fat-tree / Dragonfly / Torus / HyperX
  • 核心约束：整除关系 ($H_{ij}^i | N_i$) 保证 block 划分整齐，决定 ZCube 能搜出端口非对称
  • 建模决定能搜出什么：算法只是搜索手段，11 类超参数能搜出 ZCube 是因为允许独立取值

把网络拓扑表示成可被优化算法搜索的形式是拓扑寻优的关键工程问题。本文详解 ATOP 的 11 类超参数 + 对照邻接矩阵 / Condor DSL / TopoOpt TotientPerms 三种压缩方法的边界。

为什么必须参数化​

核心问题：直接搜邻接矩阵为什么不可行？业界有哪三种压缩范式？

邻接矩阵的不可行性​

最直白的拓扑表示是 $N \times N$ 邻接矩阵 $A$，其中 $A_{ij} = 1$ 表示节点 $i, j$ 相连。

  • 搜索空间大小：$O(2^{N(N-1)/2})$
  • N = 16384 时：$> 10^{10^7}$ 量级
  • ATOP 论文 §2 实测："we implement a program for searching 16k GPU topologies using an adjacency matrix, which takes 10 hours without producing a connected topology, as hundreds of millions of parameters are required"

直接搜邻接矩阵在万卡规模上完全不可行 — 10 小时连一个连通拓扑都搜不出来。

三种压缩范式​

范式代表工作搜索空间大小表达力
专家先验模板ATOP[1]$10^{6-8}$ （11 类超参数）已知 DCN / HPC 拓扑族 + 非对称变体
约束 DSLCondor (SIGCOMM 2015[2])由 DSL 语法决定工程师手工表达约束
群论约束TopoOpt[3]$O(n/\ln n)$ (Circulant graph)Circulant graph 族 (regular degree)

@tbl-toposearch-encoding-paradigms 拓扑参数化的三种范式

ATOP 11 类超参数怎么覆盖已知拓扑​

核心问题：11 类超参数分别建模什么？怎么覆盖 Clos / Fat-tree / Dragonfly / Torus?

整体结构​

ATOP 的拓扑模型基于两个观察：

  1. 分层结构 (layered architecture)：经典 DCN 拓扑 (CLOS / Fat-Tree / BCube) 的节点分层
  2. 层内多维结构 (intra-layer dimensional structure)：Dragonfly / HyperX / Torus 在同层内有多维连接

11 类超参数分两组，分别建模这两个维度的结构。

11 类超参数完整定义 （论文 §3.2 / Table 1）​

类别类型符号含义
User Input （3 类）$L_{\max}$最大层数用户指定
$N_1$总 GPU 数 (first-layer nodes)用户指定
$D_{\max}$层内节点可分的最大维数用户指定
Inter-layer （5 类）$N_i$第 $i$ 层节点数搜索变量 ($2 \le i \le L_{\max}$)
$H_{ij}^i$$i \leftrightarrow j$ 互联中第 $i$ 层的 block 数搜索变量
$H_{ij}^j$$i \leftrightarrow j$ 互联中第 $j$ 层的 block 数搜索变量
$E_{ij}$第 $i$ 层 block 到第 $j$ 层 block 的链路数搜索变量
$B_{ij}$层间链路带宽倍数 (1-4)搜索变量
Intra-layer （6 类）$D_i$第 $i$ 层维数搜索变量 ($0 \le D_i \le D_{\max}$)
$S_i^k$第 $i$ 层第 $k$ 维大小搜索变量
$P_i^k$第 $i$ 层第 $k$ 维 outward connections 数搜索变量
$A_{rt}^{ik}$坐标计算源节点 $r$-th 坐标在 $t$-th 目标维度的因子搜索变量
$C_t^{ik}$偏置项搜索变量
$B_{ii}$层内链路带宽倍数搜索变量

@tbl-toposearch-encoding-atop-hyperparams ATOP 11 类超参数 （论文 Table 1）

注：表格 "3+5+6=14" 个独立符号，但论文用 "11 types of hyperparameters" 这个说法 — 某些类型在 Table 1 行数里被拆开。

Algorithm 1：层间连接生成​

# 论文 Algorithm 1 - Generate hyperparameters for inter-layer connections
def gen_inter_layer_hyperparameters(L_max, N_1):
    H = set()  # 待搜索超参数集合
    for i in range(2, L_max + 1):
        H.add(N_i ∈ [0, N_1])   # 第 i 层节点数
    for i in range(1, L_max):
        for j in range(i + 1, L_max + 1):
            H.add(H_ij_i ∈ {d | d > 0, N_i mod d == 0} ∪ {0})
            H.add(H_ij_j ∈ {d | d > 0, N_j mod d == 0} ∪ {0})
            H.add(E_ij ∈ [1, N_j / H_ij_j])
            H.add(B_ij ∈ [1, 4])
    return H

核心约束 （保证拓扑合法）：

  • $H_{ij}^i | N_i$ （整除关系，保证 block 划分整齐）
  • $H_{ij}^j | N_j$ （同上）
  • $H_{ij}^j \ge H_{ij}^i$ (确保每个 $j$ 层 block 至少连接一个 $i$ 层 block)

Algorithm 2：层内连接生成​

# 论文 Algorithm 2 - Generate hyperparameters for intra-layer connections
def gen_intra_layer_hyperparameters(D_max, L_max, N_i):
    H = set()
    for i in range(1, L_max + 1):
        H.add(D_i ∈ [0, D_max])
        N_remained = N_i
        for k in range(1, D_i + 1):
            if k < D_i:
                # 各维大小满足 N_remained > 0 且整除
                H.add(S_i_k ∈ {d | N_remained > 0, N_remained mod d == 0})
            else:
                # 最后一维由前面决定
                S_i_k = N_remained
            N_remained = N_remained / S_i_k
            H.add(P_i_k ∈ [0, S_i_k - 1])
            for t in range(1, D_i + 1):
                for r in range(0, D_i):
                    H.add(A_rt_ik ∈ [-S_i_k, S_i_k])
                H.add(C_t_ik ∈ [-S_i_k, S_i_k])
        H.add(B_ii ∈ [1, 4])
    return H

层内 destination 节点公式 （论文公式 1）​

每节点坐标 $(X_1, X_2, \ldots, X_{D_i})$ 的第 $k$ 维 outward connection 计算目的节点坐标 $X'_t$:

$$\begin{equation} X'_t = \left[ A_{0t}^{ik} \times m + \sum_{r=1}^{D_i} (A_{rt}^{ik} \times X_r) + C_t^{ik} \right] \mod S_i^k \label{eq:toposearch-encoding-intra-layer-dest} \end{equation}$$

其中：

  • $m$：第 $m$-th connection ($1 \le m \le P_i^k$)
  • 第一项：不同 connection 的偏移 （让多条连接走向不同目标）
  • 第二项：源节点坐标的线性变换 （决定 destination 在每维上的偏移）
  • 第三项：常数偏置

公式 $\eqref{eq:toposearch-encoding-intra-layer-dest}$ 能表达 Torus / FullMesh / Dragonfly / HyperX 等多维拓扑结构。

搜索空间大小估算​

类别典型取值范围离散值数
$L_{\max}$2-4 层3
$D_{\max}$1-4 维4
$N_i$整除关系$\sqrt{N_1}$ 量级
$H_{ij}^{i/j}$$N_i$ 的因子$d(N_i)$ （因子数）
$E_{ij}$$[1, N_j / H_{ij}^j]$数十-数百
$B_{ij}, B_{ii}$$\{1, 2, 3, 4\}$4
$S_i^k$$N_{\text{remained}}$ 的因子$d(N)$
$P_i^k$$[0, S_i^k - 1]$数十
$A_{rt}^{ik}, C_t^{ik}$$[-S_i^k, S_i^k]$数百

@tbl-toposearch-encoding-atop-space ATOP 11 类超参数搜索空间估算

整体规模：基于因子数粗估，远小于邻接矩阵的 $O(2^{N^2})$，且论文实测 10 万次评估能合理覆盖 （具体组合数论文未给）。

TopoOpt TotientPerms 跟 ATOP 怎么对比​

核心问题：Circulant graph 单层 vs ATOP 多维分层模板的本质差异？

详见 8.3 TopoOpt。简述：

  • 数学基础：Euler totient 函数 $\varphi(n)$ 枚举与 $n$ 互素的整数 $p$
  • 每个 $p$ 定义一个环置换：节点 $S_i$ 直连 $S_{(i+p) \mod n}$
  • 进一步限制 $p$ 为素数 （按素数定理）：搜索空间降到 $O(n / \ln n)$

与 ATOP 11 类超参数的本质差异：

维度ATOP 11 类超参数TopoOpt TotientPerms
搜索空间多维分层模板Circulant graph （单层）
拓扑结构支持 Clos / Fat-tree / Dragonfly / Torus / HyperX 等仅 regular graph （"跳 p 步"环置换叠加）
端口非对称支持 （如 ZCube 的 2n / 3n 端口）不支持 (regular degree)
数学性质复杂 （拓扑性质要 case-by-case 证明）简洁 (直径上界 $O(d \cdot n^{1/d})$ 有理论保证)

@tbl-toposearch-encoding-atop-vs-topoopt ATOP 11 类超参数 vs TopoOpt TotientPerms

Condor 的约束 DSL 为什么不能跑通生产​

核心问题：SMT 求解为什么解决不了"性能优化目标"?

Condor (SIGCOMM 2015[2]) 提出用约束语言 (DSL) 描述拓扑设计意图，再交给 SMT solver 求解。

设计哲学​

  • 用户用 DSL 写约束 （如"每 ToR 度数 ≥ 4" / "任意两 server 路径长度 ≤ 3"）
  • Condor 求解器自动生成满足约束的拓扑实例
  • 不需要枚举参数空间，让 SMT 自动找

优劣​

维度评价
表达力高 （任何能 SMT 编码的约束）
工程门槛高 （要工程师精通 SMT 公式 + 性能调优）
性能中 （SMT 在大规模拓扑上爆炸）
工业部署几乎没有

@tbl-toposearch-encoding-condor Condor DSL 优劣

ATOP 论文 §2 评价 Condor: "it still relies on human experts to express their intuition using the DSL. Although the DSL allows for experts to describe hardware constraints..., it is very difficult and unintuitive to express application-level, end-to-end performance optimization goals (e.g., minimizing LLM training iteration time) using a constraint language."

Condor 解决了"硬件约束表达"，但解决不了"性能优化目标" — 这正是 ATOP 选用模板 + NSGA-II 的动机。

还有什么其他参数化方法​

核心问题：GNN 编码 / 图同构 / 混合连续离散这些前沿尝试可行吗？

邻接矩阵 + GNN 编码​

  • 用 GNN 把邻接矩阵编码成低维 latent vector，在 latent space 搜索
  • 优点：理论上能表达任意图
  • 缺点：训练 GNN 需要大量已知"好拓扑"样本 （鸡生蛋问题）；学术尝试，无生产案例

图同构 / 自同构群约束​

  • 利用图论对称性 （自同构群） 压缩搜索空间
  • 例：Cayley graph、Vertex-transitive graph
  • TopoOpt 是这类思想的简化版 (Circulant graph)

离散参数 + 连续参数混合​

  • 拓扑结构 （离散） + 链路带宽 / 端口数 （连续）
  • 需要混合优化算法 （如 NSGA-II + Gradient Descent）
  • 当前没有成熟工程实现

建模决定能搜出什么​

核心问题：11 类超参数能搜出 ZCube 的关键是什么？仍有什么局限？

11 类超参数 / TotientPerms / Condor DSL / GNN 编码 — 这些都不是"算法选择"的问题，而是"建模选择"的问题。算法只是搜索手段，建模决定能搜出什么。

ATOP 的 11 类超参数能搜出 ZCube 这种端口非对称结构，是因为 $E_{ij}$ 和 $H_{ij}^{i/j}$ 可以独立取值 — 天然允许不同层节点连接不同数量。如果建模时强制"每层端口数相同" （如 BCube 的 regular constraint），ATOP 永远搜不出 ZCube。

这是 ATOP 真正的工程贡献 — 把"自动搜索拓扑"从"邻接矩阵的 NP 问题"降维到"11 类超参数的多目标优化"。

11 类超参数的局限：ATOP 能覆盖已知 DCN / HPC 拓扑族，但搜不出：

  • Jellyfish (random regular graph) — 没有分层结构
  • Xpander （结构化 expander） — 基于矩阵积构造，不是分层
  • PolarFly （射影平面） — 基于有限几何，跨维度
  • 混合 OCS-Electrical — 动态可重配拓扑

未来扩展方向是把这些拓扑族纳入建模 — 可能需要 12-15 类超参数 （增加"对称性约束" / "扩展子结构"等维度）。

Takeaway​

知识点核心结论
邻接矩阵不可搜$O(2^{N^2})$ 在 16k GPU 时 $> 10^{10^7}$，必须压缩搜索空间
三种压缩范式专家先验模板 (ATOP) / 约束 DSL (Condor) / 群论约束 (TopoOpt)
ATOP 11 类3 User Input + 5 Inter-layer + 6 Intra-layer，覆盖 Clos / Fat-tree / Dragonfly / Torus / HyperX
整除约束$H_{ij}^i \mid N_i$ 保证 block 划分整齐，是合法拓扑的必要条件
端口非对称能搜出$E_{ij}$ 和 $H_{ij}^{i/j}$ 独立取值是搜出 ZCube 的关键
Condor 局限SMT 解决硬件约束但不解决性能优化，工业无部署
11 类局限搜不出 Jellyfish / Xpander / PolarFly / 动态可重配
普遍规律算法只是搜索手段，建模决定能搜出什么

参考资料​

  1. Yan et al., ATOP, SIGCOMM 2025. https://dl.acm.org/doi/10.1145/3718958.3750503
  2. Schlinker et al., Condor, SIGCOMM 2015. https://dl.acm.org/doi/10.1145/2829988.2787486
  3. Wang et al., TopoOpt, NSDI 2023. https://www.usenix.org/conference/nsdi23/presentation/wang-weiyang