拓扑寻优器设计规格

版本：1.0.0 状态：Accepted 创建日期：2026-05-21 最后更新：2026-05-21 Accepted 日期：2026-05-21 作者：xiang.li 前置：拓扑生成器设计规格 v1.2.0

版本号规则 (SemVer):

major (X.0.0)：架构变更、接口不兼容、Generator 协议重构

minor (1.X.0)：新增 Generator 类型、新增评估目标、扩展 Layer

patch (1.0.X)：修正笔误、补充说明、更新 Implementation Notes

变更历史

版本	日期	变更说明
1.0.0	2026-05-21	初版：候选级搜索抽象 + 4 类 Generator + 5 层评估 + Phase 演进路线

Summary

拓扑寻优器解决的核心问题是：给定芯片总数、硬件约束、workload 描述和多个优化目标，自动搜索 Pareto-approximate 的网络拓扑实例集合（受评估器精度与算法限制，不保证收敛到真 Pareto-optimal），输出可直接部署的拓扑配置（与现有 YAML 格式兼容）。

模块是一个多目标进化搜索 + 分层评估框架。搜索单元是 TopologyCandidate（拓扑实例），不绑定到任何已知拓扑族——通过 4 类 Generator（Family / GenericTemplate / GraphMutator / GraphCrossover）共同采样候选，由 NSGA-II 在多目标空间内迭代选优。评估器分 5 层 funnel（拓扑结构 → 集合通信原语 → 训练 iter → workflow → 成本），用 math/解析粗筛 + g5 精筛的 2-stage 策略控制评估成本。

Motivation

现状与问题

项目当前已有拓扑生成器（v1.2.0），它是一个 约束满足 + 参数枚举 框架：用户输入芯片数 + 硬件约束，生成器列举出所有合法的"族 + 族参数"组合（标 recommended / edge-case），用户人工挑选最终方案。

生成器留下的开放问题：

不打分：枚举出几十个候选后，哪个对 GPT-3 175B 训练最快？哪个最便宜？哪个最容错？生成器不回答这些问题
族限制：枚举只覆盖已知 9 族（fat-tree / dragonfly / torus / ...）。如果某个 workload 的最优拓扑是已知族未表达的结构（如 ZCube 的端口非对称设计），生成器永远搜不到
手工试错代价高：现实中用户用生成器枚举出候选后，要把每个候选导入仿真器跑一次评估，多目标权衡靠经验

拓扑生成器 spec 的 Non-Goal 明确说"不做自动寻优——这是未来方向"——本 spec 承接该承诺。

驱动力

万卡级集群的网络硬件投资规模可观（详见 Alibaba HPN, SIGCOMM 2024）。在这个量级，节省 30% 网络成本就意味着可观的硬件投资节省。SIGCOMM 2025 论文 From ATOP to ZCube 实证：通过自动拓扑搜索发现的 ZCube 相对 ROFT 节省 26%–46% 网络硬件成本。

详细调研见 docs/interconnect/08-拓扑寻优/ 知识域 7 篇调研文档。

Terminology

名词	定义	区分/补充
Topology Candidate	搜索过程中的单个候选拓扑实例，含完整 `NetworkGraph`（switches + links + 物理分组） + 起源元信息（TopologyOrigin）	不绑定到任何族；与 YAML 配置文件一一对应
Topology Origin	候选的起源标签：来自哪个 Generator、何种参数	仅用于追溯与可解释性，不参与搜索
Generator	产生 `TopologyCandidate` 的方法。本 spec 定义 4 类：Family / GenericTemplate / GraphMutator / GraphCrossover	与拓扑生成器（topology generator，spec v1.2.0）概念不同——Generator 是候选生成器，包括但不限于族枚举
Family	已知拓扑族（如 fat-tree / dragonfly / torus），有明确的数学结构和参数空间	复用拓扑生成器 spec 中定义的 9 个族
Generic Template	广义参数化模板（如 ATOP 11 类超参数），不绑定到具体已知族，能表达已知族 + 未知族变体	参考 08-拓扑寻优/05。注：ATOP 论文用 "11 types" 但 Table 1 实际列 14 个独立符号（3 用户输入 + 5 层间 + 6 层内）——"11 types" 是论文聚类后的分类口径
Graph Mutation	在已有 `NetworkGraph` 上施加局部图编辑算子（加边/删边/重连交换机/端口非对称化等）	跳出"族"限制的关键机制
Layer （评估层级）	评估器的分层抽象（Layer 1-5），自底向上：拓扑结构 → 集合通信原语 → 训练 iter → workflow → 成本。硬件参数（链路带宽 / 延迟 / NIC 端口 / 交换机 radix）作为外部输入，不构成单独的评估 Layer	不同 Layer 用不同评估器（解析 / α-β / g5 仿真）
2-stage Funnel	评估器分级策略：Stage 1 粗筛（10⁴ 候选，Layer 1+2+5）+ Stage 2 精筛（Pareto ~5%, Layer 3+4）	参考 08-拓扑寻优/06
APL_fail	单交换机故障下任意 GPU 对的平均最短路径长度，量化拓扑容错性	ATOP §3.4 公式 2
Pareto-optimal Topology Set	在多目标空间内不被任何其他候选支配的拓扑集合	寻优器的最终产出

@tbl-topo-opt-terminology Terminology

Goals / Non-Goals

Goals:

G1 候选级搜索：搜索单元是 TopologyCandidate（含完整 NetworkGraph），不限制在已知拓扑族——通过多种 Generator 共同探索包含已知 + 未知结构的搜索空间
G2 多目标 Pareto 前沿：同时优化多个目标（Phase 1 P0 三目标：训练 iter time / 网络成本 / APL_fail 容错），输出 Pareto-optimal 候选集合
G3 分层评估：评估器按 5 个 Layer 分级，Layer 1+2+5 用解析/图论秒级粗筛，Layer 3+4 用 g5 仿真分钟级精筛
G4 复用现有资产：依赖现有 NetworkGraph 表达 + 拓扑生成器（作为 FamilyGenerator 实现）+ math/g5 评估器 + 路由策略
G5 兼容现有 YAML：寻优器输出 TopologyCandidate.graph 直接序列化为现有 YAML 格式（含 switches + links + 物理分组），可直接进入仿真 / 可视化 / 部署流程
G6 可扩展架构：4 类 Generator + 多 Layer 评估器都是可插拔接口，新增 Generator（如未来的 RandomRegularGraphGenerator）或新增目标（如 ForestColl 下界）不修改框架

Non-Goals:

不替代拓扑生成器——生成器仍是用户手动选型 / 寻优器初始化种子的快速入口
不做实时寻优（搜索是离线批处理，Phase 1 单次运行 4-8 小时数量级）
不做硬件参数（链路带宽 / 交换机 radix / NIC 端口数）的联合搜索——硬件作为外部约束输入，Phase 3 可考虑
不做训练策略（TP/PP/DP/EP 切分）联合搜索——并行策略作为 workload 描述的一部分输入
不重新发明集合通信调度——评估器可调用 ForestColl Phase 1 等理论下界，但不合成具体调度（这是 SCCL / TACCL / TE-CCL 的职责）

Background / Prior Art

详细业界调研见 docs/interconnect/08-拓扑寻优/ 7 篇文档。本节摘要关键决策依据。

业界拓扑寻优方案对比

工作	搜索单元	搜索算法	评估器	拓扑表达	部署状态
ATOP / ZCube (SIGCOMM 2025)	11 类超参数（14 个独立符号）	NSGA-II（4 算法实测均未收敛，NSGA-II 最佳平衡）	2-stage: flow-level 粗筛 + Astra-Sim 2.0 + SimAI workload + flow-level backend 精筛	广义参数化模板（分层 + 多维）	智谱 GLM-5.1 推理集群（媒体报道）
TopoOpt (NSDI 2023)	Circulant graph 度数+生成元	Alternating optimization + 群论	FlexFlow + 包级仿真	TotientPerms 数学构造	12 节点 testbed
SCCL/TACCL (PPoPP'21/NSDI'23)	集合通信调度	SMT/MILP	解析公式	不搜拓扑（拓扑作输入）	学术开源
Condor (SIGCOMM'15)	约束 DSL	SMT 求解	解析公式	DSL 表达任意图	学术
本 spec	TopologyCandidate （NetworkGraph 实例）	NSGA-II + 多 Generator	5 层 funnel	4 类 Generator 共同覆盖	Phase 1 待实现

@tbl-topo-opt-prior-art 业界拓扑寻优方案对比

与 ATOP 的关键差异

ATOP 是本设计的最直接参考，但本 spec 不是 ATOP 的复刻：

维度	ATOP	本 spec
搜索单元	11 类超参数向量 → 程序生成 graph	TopologyCandidate（含 graph 本体），参数只作为追溯元信息
拓扑表达	单一广义模板（"分层 + 多维"）	4 类 Generator 互补：已知族 + 广义模板 + 图编辑 + 跨族交叉
评估器粒度	2-stage（flow-level + 端到端 Astra-Sim 2.0 + SimAI）	5 层 funnel：Layer 1+2+5 ≈ ATOP Stage 1 内部指标的拆分，Layer 3+4 ≈ ATOP Stage 2
算法假设	ForestColl Phase 1 作为集合通信 oracle	同（Phase 2 加入），Phase 1 用 α-β 模型替代
部署规模	16K GPU 仿真 + 16 GPU testbed	Phase 1 目标 1K-4K GPU，Phase 2 扩展

注：本 spec 的"5 层评估器"不是相对 ATOP 新增评估能力——ATOP Stage 1 内部已包含 cost / APL_fail / ForestColl / JCT 共 4 类指标。本 spec 把这些指标按 Layer 拆分是工程组织上的选择，目的是早期剪枝 + 跨 workload 复用 + 可诊断，不是算法创新。

关键设计依据

为什么 NSGA-II 不是 MOBO：08-拓扑寻优/04 详细论证。评估秒级 + 维度 ≥ 10 + 目标 ≤ 4 时，NSGA-II 是默认正确选择。ATOP Appendix J 实测验证。
为什么不是邻接矩阵搜索：08-拓扑寻优/05 论证。$O(2^{N^2})$ 在 16K GPU 时 $> 10^{10^7}$ 不可行；ATOP 论文 §2 实测"用邻接矩阵搜 16K GPU 拓扑 10 小时连一个连通图都搜不出"。
为什么"族 + 程序生成"路线不够：业界（ATOP/TopoOpt）的核心创新是跳出已知族搜未知结构。本 spec 通过 GraphMutator + GenericTemplate 实现这点。

Guide-Level Explanation

用 GPT-3 175B 训练 1024 GPU 集群的拓扑寻优作为示例。

用户视角的使用流程

# 用户写一份寻优配置（不需要写拓扑细节）
# search_config.yaml
n_chip: 1024
workload:
  model: gpt-3-175b
  parallelism:
    tp: 8
    pp: 8
    dp: 16
  message_sizes_bytes: [1048576, 16777216, 268435456, 1073741824]  # IEC 二进制单位 1MiB / 16MiB / 256MiB / 1GiB
  required_primitives: [AllReduce, AllToAll]

hardware_constraints:
  nic_bandwidth_gb_per_s: 50  # ConnectX-7 NIC 400 Gbps = 50 GB/s（项目命名规范用 GB/s 不用 Gbps，见 .claude/rules/naming-conventions.md）
  switch_radix_options: [32, 64, 128]
  link_latency_us: 1.0
  max_optical_cable_length_m: 50

objectives:
  - iter_time         # Layer 3, P0
  - network_cost      # Layer 5, P0
  - apl_fail          # Layer 1, P0

generators:
  family:
    enabled: true
    families: [fat-tree, dragonfly, torus, slimfly]  # 用 4 个族初始化
  generic_template:
    enabled: false   # Phase 2 启用
  graph_mutator:
    enabled: true
    operators: [add_edge, remove_edge, rewire_switch]
  graph_crossover:
    enabled: false   # Phase 3 启用

search:
  algorithm: nsga2
  population_size: 200
  generations: 100   # 总评估数 = pop × gen = 20,000
  parallel_workers: 32

evaluator:
  stage_1: math_alpha_beta
  stage_2: g5_simulation
  pareto_threshold: 0.05  # Stage 1 前 5% 进 Stage 2

寻优器跑完后输出 Pareto 前沿（约 20-50 个最优候选）+ 选定方案的 YAML 配置：

# 寻优器输出 pareto_optimal/candidate_001.yaml
# 格式与现有 configs/topologies/*.yaml 完全一致
metadata:
  source: optimizer
  origin:
    method: graph_mutation
    seed_family: fat-tree
    seed_params: { k: 16, layers: 2, oversub_ratio: 1 }
    mutations: [add_edge × 4, rewire_switch × 2]
  metrics:
    iter_time_us: 12_345
    network_cost_usd: 1_240_000
    apl_fail: 3.14
chips_per_board: 4
boardGrouping:
  ...
network:
  switches: [...]
  links: [...]

用户可直接把任一 Pareto 候选导入 3D 可视化（frontend/src/components/Scene3D/）/ 仿真 / 部署流程，与现有工作流无缝衔接。

与拓扑生成器的关系

[用户输入: n_chip + workload + objectives]
                |
                v
        [拓扑寻优器 (本 spec)]
                |
       +--------+--------+--------+--------+
       v        v        v        v        v
   Family   Generic   Graph    Graph    (Phase 3+)
   Generator Template Mutator  Cross   未来 Gen
       |        |        |        |
       v        v        v        v
       [TopologyCandidate (NetworkGraph 实例)]
                |
                v
        [NSGA-II 搜索循环]
                |
        +-------+-------+
        v               v
    [Stage 1 粗筛]   [Stage 2 精筛]
   (math, 10⁴ 候选)   (g5, ~500 候选)
                |
                v
        [Pareto Optimal Set]
                |
                v
        [输出: 与现有 YAML 兼容]

FamilyGenerator 在内部调用现有拓扑生成器（spec v1.2.0）的实现，作为已知族候选的快速来源。

Detailed Design

概念模型

Topology Candidate

搜索过程中的最小单元：

@dataclass
class TopologyCandidate:
    """寻优器内部的拓扑候选表示。"""

    id: str                            # 唯一标识，便于追溯
    graph: NetworkGraph                # 完整拓扑实例（switches + links + 物理分组）
    origin: TopologyOrigin             # 起源元信息（仅追溯，不参与搜索）
    metrics: dict[str, float]          # 评估缓存，由 Evaluator 填充

@dataclass
class TopologyOrigin:
    method: Literal[
        "family_enum",       # FamilyGenerator 的枚举模式
        "family_sample",     # FamilyGenerator 的采样模式
        "generic_template",  # GenericTemplateGenerator
        "graph_mutation",    # GraphMutator
        "crossover",         # GraphCrossover
        "manual_seed",       # 用户提供的种子
    ]
    family: str | None = None              # 若与族相关
    family_params: dict | None = None
    template_params: dict | None = None    # ATOP 11 类等
    parent_ids: list[str] | None = None    # 变异/交叉的父代
    mutations_applied: list[str] | None = None  # 图变异轨迹

关键设计原理：搜索单元是 TopologyCandidate.graph（完整 NetworkGraph 实例），不是任何参数向量。这让搜索空间天然无族限制——任何 Generator 能产出有效 NetworkGraph 就能进入搜索。origin 字段只用于追溯（如"这个最优候选是从哪个族的哪种变异得到的"），不影响搜索逻辑。

Generator 协议

所有 Generator 实现统一协议：

class TopologyGenerator(Protocol):
    """候选生成器抽象协议。"""

    name: str                                       # 标识符
    capabilities: set[Literal["init", "mutate", "crossover"]]  # 支持的操作

    def init(self, n_chip: int, hw: HwConstraints, rng) -> Iterator[TopologyCandidate]:
        """产生初始候选（用于 NSGA-II 种群初始化）。"""

    def can_mutate(self, parent: TopologyCandidate) -> bool:
        """预判该 Generator 是否能对此父代做变异（用于 NSGA-II 算子选择）。
        例：FamilyGenerator 只能变异 origin.method 起源于 family 的候选。"""

    def mutate(
        self, parent: TopologyCandidate, rng
    ) -> TopologyCandidate:
        """对父代候选做变异（用于 NSGA-II 变异算子）。
        前置条件：`can_mutate(parent) == True`（调用方保证）。
        失败语义：如变异产物违反硬约束（如非连通），抛 `InvalidMutation` 异常，由调用方决定重试或换算子——**不用 None 表示失败**（避免与 can_mutate=False 的语义混淆）。"""

    def crossover(
        self, p1: TopologyCandidate, p2: TopologyCandidate, rng
    ) -> TopologyCandidate | None:
        """两个父代交叉（NSGA-II 交叉算子）。返回 None 表示不支持。"""

四类具体实现：

class FamilyGenerator(TopologyGenerator):
    """复用现有拓扑生成器，按已知族 + 族参数采样。"""
    name = "family"
    capabilities = {"init", "mutate"}  # crossover 不支持（不同族结构不可交叉）

    def init(self, n_chip, hw, rng):
        for family in self.enabled_families:
            for params in family.enumerate(n_chip, hw):  # 复用生成器 spec 的 enumerate
                yield self._materialize(family, params)

    def can_mutate(self, parent):
        return parent.origin.method.startswith("family")

    def mutate(self, parent, rng):
        # 同族内参数变异（如 fat-tree 的 k 从 8 → 16）
        return self._mutate_family_params(parent, rng)


class GenericTemplateGenerator(TopologyGenerator):
    """ATOP 11 类超参数广义模板。Phase 2 实现。"""
    name = "generic_template"
    capabilities = {"init", "mutate", "crossover"}

    def init(self, n_chip, hw, rng):
        # 按 ATOP Algorithm 1 + 2 采样 11 类超参数
        params = sample_atop_11_hyperparameters(n_chip, hw, rng)
        graph = build_graph_from_atop_template(params)
        yield TopologyCandidate(graph=graph, origin=TopologyOrigin("generic_template", template_params=params))


class GraphMutator(TopologyGenerator):
    """图编辑算子集。跳出族限制的关键。"""
    name = "graph_mutator"
    capabilities = {"mutate"}

    operators = [
        AddEdgeOperator(),
        RemoveEdgeOperator(),       # 保连通性
        RewireSwitchLayerOperator(),
        SplitSwitchOperator(),
        MergeSwitchOperator(),
        ChangePortAsymmetryOperator(),
        # ...
    ]

    def can_mutate(self, parent):
        return True  # 对任何候选都能尝试图编辑

    def mutate(self, parent, rng):
        op = rng.choice(self.operators)
        new_graph = op.apply(parent.graph, rng)
        if not new_graph.is_connected():  # 硬约束：连通性
            raise InvalidMutation("graph not connected after mutation")
        return TopologyCandidate(
            graph=new_graph,
            origin=TopologyOrigin("graph_mutation", parent_ids=[parent.id]),
        )


class GraphCrossover(TopologyGenerator):
    """跨候选图论交叉。Phase 3 实现。"""
    name = "graph_crossover"
    capabilities = {"crossover"}

关键设计原理：四类 Generator 是 NSGA-II 的算子来源，不是搜索空间的划分。NSGA-II 看到的是统一的 TopologyCandidate 种群，从每个 Generator 拉取变异/交叉操作。同一种群里来自不同 Generator 的候选可以互相变异（如 GraphMutator 对 FamilyGenerator 产出的候选做编辑，得到"族邻居"）。

5 层评估器

class Evaluator:
    """分层评估器，按 Layer 自底向上计算 metrics。"""

    def evaluate(
        self,
        candidate: TopologyCandidate,
        workload: WorkloadSpec,
        layers: set[int],
    ) -> dict[str, float]:
        """评估指定 Layer 的指标。Layer 间共享中间结果。"""
        results = {}

        if 1 in layers:
            results.update(self._compute_layer1(candidate.graph))      # 拓扑结构（与 workload 无关）
        if 2 in layers:
            results.update(self._compute_layer2(candidate.graph, workload))  # 集合通信原语
        if 3 in layers:
            results.update(self._compute_layer3(
                candidate.graph, workload, prev=results
            ))  # 训练/推理 iter（用 g5）
        if 4 in layers:
            results.update(self._compute_layer4(workload, prev=results))   # workflow 整合
        if 5 in layers:
            results.update(self._compute_layer5(candidate.graph, hw))      # 成本（与 workload 无关）

        return results

各 Layer 的具体计算见下文 算法 / 公式 子节。

设计原理

为什么搜索单元是 NetworkGraph 而非参数向量

ATOP 的限制：ATOP 用 11 类超参数向量作为搜索单元，所有候选都来自同一个广义模板。这意味着：

不能与"已知族 + 族参数"快速搜索混搭（族的参数空间结构不同）
不能加图编辑算子（编辑无法表示为 11 类超参数的扰动）
不能复用生成器 spec 的现有 9 族实现

本 spec 的选择：搜索单元升一级到 NetworkGraph 实例。任何 Generator 只要能产出有效 NetworkGraph 就能进入搜索循环。这让框架天然异构——FamilyGenerator 产出的"结构化候选"和 GraphMutator 产出的"自由变异候选"可以在同一 NSGA-II 种群里共存、竞争、互相变异。

代价：内存开销更大（每个候选保存完整 graph 而非参数向量），但对 1k-4k GPU 规模可承受（每候选 graph ~MB 级，种群 200 → ~200MB）。

为什么 4 类 Generator 而非单一 Generator

单一 Generator 选项	局限
只用 FamilyGenerator	退化为族枚举，永远搜不出 ZCube 类未知结构
只用 GenericTemplateGenerator	限定"分层+多维"模板，搜不出 Jellyfish 类 random regular graph
只用 GraphMutator	没有结构化种子，初始化只能随机起步，搜索极慢
只用 GraphCrossover	无父代来源

4 类组合是必要的最小集：

FamilyGenerator：提供结构化种子 + 快速覆盖已知拓扑
GenericTemplateGenerator：提供 ATOP 风格的广义模板探索
GraphMutator：提供局部邻居探索（跳出族限制的核心机制）
GraphCrossover：提供跨族重组（混合不同族的优势特征）

为什么 5 层评估器而非 2 层

ATOP 的 2-stage 在 16K GPU 单机 256 核单服务器上跑 71.2 小时（ATOP 论文 §4.1 / Appendix D 报告 80% 时间在拓扑评估）。项目复刻 ATOP 路线时，评估器加速是最高 ROI 的工作方向（评估开销加速 10% → 总时间 -8%）。

5 层分级带来三个机会：

更细粒度复用：Layer 1（拓扑结构指标）与 workload 无关，可在多 workload 评估中复用一次计算
更早剪枝：候选在 Layer 1 已显示"直径过大"或"成本超预算"时，直接淘汰，不进 Layer 2+
可解释诊断：当某候选 Layer 3 训练 iter 慢，可回看 Layer 2 是哪个集合通信原语拖后腿

为什么 NSGA-II 而非 MOBO

参考 08-拓扑寻优/04 决策树。本 spec 场景：

评估开销：Stage 1 秒级 / Stage 2 分钟级
参数维度：候选 graph 的"等效维度"在 50-200（视 Generator 而定，GraphMutator 产出的有效维度更高）
目标数：Phase 1 P0 三目标
总评估预算：10⁴ 量级

决策树落点：评估秒级 + 维度 > 20 + 目标 ≤ 4 → NSGA-II 是首选。ATOP Appendix J 实测验证：同时间预算下 NSGA-II 跑 100k 候选 vs Bayesian 仅 1k 候选，4 种算法在该实验中均未收敛到 Pareto-optimal 集合（论文原话 "None of these algorithms lead to the convergence of the Pareto-optimal topology set"），但 NSGA-II 取得最佳的效率-性能平衡。本 spec 输出的是 Pareto-approximate 集合而非真 Pareto-optimal。

留 Phase 3 扩展点：算法可替换为 NSGA-III / MOEA-D / MORBO 等，框架不变。

算法 / 公式

Layer 1：拓扑结构指标

直径（最大跳数）：

$$\begin{equation} \text{Diameter}(G) = \max_{u, v \in V} d_G(u, v) \label{eq:topo-opt-diameter} \end{equation}$$

$G = (V, E)$：拓扑图
$V$：节点集（GPU + switch）
$d_G(u, v)$：$u$ 到 $v$ 的最短路径长度（hops）

平均路径长度：

$$\begin{equation} \text{APL}(G) = \frac{1}{|V_g|^2 - |V_g|} \sum_{u, v \in V_g, u \neq v} d_G(u, v) \label{eq:topo-opt-apl} \end{equation}$$

$V_g \subseteq V$：GPU 节点集
分母是 GPU 节点对数

单交换机故障下平均路径长度（Phase 1 P0 目标之一，来自 ATOP §3.4 公式 2）：

$$\begin{equation} \text{APL}_{\text{fail}}(G) = \frac{1}{|V_s|} \sum_{v_s \in V_s} \frac{1}{|V_g|^2 - |V_g|} \sum_{u, v \in V_g, u \neq v} d_{G' = (V - v_s, E)}(u, v) \label{eq:topo-opt-apl-fail} \end{equation}$$

$V_s \subseteq V$：交换机节点集
$G' = (V - v_s, E)$：移除交换机 $v_s$ 后的图

Bisection Bandwidth：

$$\begin{equation} B_{\text{bis}}(G) = \min_{S \subset V_g, |S| = |V_g|/2} \sum_{(u, v) \in E, u \in S, v \notin S} \text{bw}(u, v) \label{eq:topo-opt-bisection} \end{equation}$$

$S$：GPU 节点集合的二等分子集
$\text{bw}(u, v)$：链路 $(u, v)$ 的带宽（GB/s）

Layer 2：集合通信原语完成时间

Phase 1 用 $\alpha$-$\beta$ 模型（详见 04-集合通信/02-理论下界）。Phase 2 加入 ForestColl Phase 1 下界。

Ring AllReduce（$N$ 节点，消息大小 $M$）：

$$\begin{equation} T_{\text{Ring-AR}}(N, M) = 2(N-1) \alpha + \frac{2 (N-1) M}{N \beta} \label{eq:topo-opt-ring-ar} \end{equation}$$

$\alpha$：每跳延迟（μs）
$\beta$：链路带宽（GB/s）

AllToAll、AllGather、ReduceScatter 等原语的公式同源（参考 4.8 AllReduce 等）。

ForestColl Phase 1 下界（Phase 2 加入）：

$$\begin{equation} T_{\text{FC-AG}}(G, M) = \frac{M}{\text{ForestThroughput}(G)} \label{eq:topo-opt-forestcoll} \end{equation}$$

$\text{ForestThroughput}(G)$：edge-disjoint spanning forest 分解给出的最大吞吐量下界（详见 08-拓扑寻优/06）

Layer 3：训练/推理 iter time

通过 g5 仿真器评估，模型为：

$$\begin{equation} T_{\text{iter}} = T_{\text{compute}} + \sum_{p \in \text{primitives}} T_p \cdot N_p \cdot \eta_p \label{eq:topo-opt-iter} \end{equation}$$

$T_{\text{compute}}$：单 iter 的纯计算时间（不含通信，由 workload 描述提供）
$T_p$：原语 $p$ 单次完成时间（来自 Layer 2）
$N_p$：单 iter 内原语 $p$ 的调用次数（由并行策略决定）
$\eta_p$：通信-计算重叠系数（$\eta = 1$ 无重叠；$\eta = 0$ 完全重叠）

g5 仿真直接产出 $T_{\text{iter}}$，无需手算重叠系数。$\eqref{eq:topo-opt-iter}$ 只用于 Layer 3 输出的语义解释。

Layer 5：网络硬件成本

$$\begin{equation} C_{\text{net}}(G) = \sum_{s \in V_s} c_{\text{switch}}(s) + \sum_{(u,v) \in E} c_{\text{link}}(u, v, l_{u,v}) + |V_g| \cdot c_{\text{nic}} \label{eq:topo-opt-cost} \end{equation}$$

$c_{\text{switch}}(s)$：交换机 $s$ 的单价（按 radix 和带宽查询报价表）
$c_{\text{link}}(u, v, l)$：链路 $(u, v)$ 的成本，取决于距离 $l$（DAC / 光纤跳线 / 光模块）
$c_{\text{nic}}$：单 NIC 单价

报价表来源：FS 与 Colfax Direct（参考 ATOP §4.1）。

约束与规则

硬约束（候选拒绝）

任何候选必须通过以下检查才能进入评估：

连通性：$G$ 是连通图（任意 GPU 对可达）
端口数匹配：每个交换机的端口数 ≤ 硬件 radix 限制
链路带宽匹配：每条链路两端的端口带宽相同
物理可行性：链路距离 ≤ 硬件支持的最大光纤长度（如 50m）
预算上限：$C_{\text{net}}(G) \le C_{\text{budget}}$（如用户设定）

不通过硬约束的候选直接从种群移除。

软约束（候选标记，不拒绝）

软约束影响候选评分但不剔除：

过度设计标记：如 32 chip 用 3-layer fat-tree
退化结构标记：如 4 节点的 dragonfly（退化为单 group）

软约束沿用拓扑生成器 spec 的 recommended / edge-case 分档。

算子内嵌约束（变异/交叉）

每个 GraphMutator 算子负责保证产出图满足硬约束。如：

RemoveEdge：删边后必须仍连通，否则拒绝该变异
SplitSwitch：拆出的两个交换机端口数总和不变
ChangePortAsymmetry：端口数变化后必须有匹配链路

不能保证产出合法图的算子抛 InvalidMutation 异常（详见 §Generator 协议），由 NSGA-II 调用方决定重试或更换算子。

集成点

与拓扑生成器（spec v1.2.0）

前置依赖：本 spec 假设拓扑生成器 spec v1.2.0 的 enumerate(family_name, n_chip, hw) → Iterator[params] 和 instantiate(family_name, params) → NetworkGraph 两个接口已规范化定义。截至本 spec 起草时，v1.2.0 仍为 Draft 且未实现这两个接口；本 spec 不要求 v1.2.0 已 Accepted/Implemented 作为前置条件——FamilyGenerator 可以基于 v1.2.0 spec 已定义的族结构和约束自行实现枚举/实例化逻辑。

FamilyGenerator 与生成器 spec 的接口契约：

class FamilyGenerator:
    """按照拓扑生成器 spec v1.2.0 定义的族结构与约束实现枚举/实例化。
    生成器实现可以是独立模块，也可以是本 spec 内嵌——契约对外一致即可。"""

    def __init__(self, family_implementations: dict[str, FamilyImpl]):
        self.families = family_implementations  # 9 个族的实例化器

    def init(self, n_chip, hw, rng):
        for family_name, impl in self.families.items():
            for params in impl.enumerate(n_chip, hw):  # 复用 v1.2.0 约束逻辑
                graph = impl.instantiate(params)
                yield TopologyCandidate(graph=graph, ...)

配套建议：拓扑生成器 spec v1.2.0 应同步升级为 v1.3.0，将 Non-Goal 第 113 行 "不做自动寻优" 改为 "由拓扑寻优器设计规格处理"。但这是生成器 spec 作者的工作，不阻塞本 spec 评审。

与评估器（math + g5）

5 层评估器复用现有实现：

Layer 1：图论计算，纯 Python 实现（无外部依赖）
Layer 2：调用现有 perfmodel/evaluation/comm/（$\alpha$-$\beta$ 模型）
Layer 3：调用现有 perfmodel/evaluation/g5/（事件级仿真）
Layer 5：解析公式 + 报价表（新增模块 cost_model.py）

与 NetworkGraph（topo_routing）

TopologyCandidate.graph 复用 perfmodel/arch/topo_routing/graph.py 的 NetworkGraph 类。Generator 产出的 graph 自动可用于路由策略（DOR / UGAL / ECMP / SP）的评估。

YAML 序列化

TopologyCandidate 序列化为 YAML 时直接展开 graph：

metadata:
  source: optimizer
  candidate_id: cand_042
  origin:
    method: graph_mutation
    parent_ids: [cand_021]
    mutations_applied: [add_edge, rewire_switch]
  metrics:
    iter_time_us: 12345
    network_cost_usd: 1240000
    apl_fail: 3.14

# 物理分组（与生成器 YAML 一致）
chips_per_board: 4
boardGrouping: { ... }

# 拓扑实例（与生成器 YAML 一致）
network:
  switches: [...]
  links: [...]

metadata 是新增字段。要求评估器与可视化在加载 YAML 时透传未知字段（不识别即忽略），不引入版本判别 / 兼容分支——这是统一前向演进策略。

引用

现有 spec: 拓扑生成器设计规格 v1.2.0
调研知识域：docs/interconnect/08-拓扑寻优/ 7 篇
ATOP 论文：From ATOP to ZCube, SIGCOMM 2025
TopoOpt 论文：TopoOpt, NSDI 2023
NSGA-II: Deb et al., 2002
pymoo: https://pymoo.org
ForestColl: arXiv:2402.06787

Alternatives Considered

搜索单元的选择

维度	方案 A （选定）：TopologyCandidate (NetworkGraph)	方案 B: 11 类超参数向量 (ATOP)	方案 C：邻接矩阵	方案 D: Circulant graph + 群论 (TopoOpt)
搜索空间	NetworkGraph 实例空间	11 类（14 个独立符号）	$O(2^{N^2})$	$O(n/\ln n)$ 个生成元（TotientPerms）
表达力	任意可表达图（受 Generator 限制）	分层 + 多维结构	任意图	仅 regular graph（环置换叠加）
与现有生成器复用	完全复用（FamilyGenerator）	难（参数空间不同）	难	难（结构完全不同）
是否能搜未知结构	是（GraphMutator + GenericTemplate）	是（限定模板内）	理论上是	仅 Circulant 类
是否支持端口非对称	是（图编辑算子可改变 switch 端口）	是（11 类超参数允许 ZCube 类非对称）	是	否（regular degree 强约束）
可搜索性	高（10⁴ 候选 / 小时）	高	极低（16K GPU 时不可搜）	高
内存开销	中（每候选 graph ~MB）	低（参数向量 ~KB）	极高	低

选择 A 的理由：唯一能同时（i）复用现有生成器（ii）搜索未知结构（含端口非对称设计）（iii）在可承受成本内执行的方案。

ATOP 路线（方案 B）排除了"复用现有 9 族实现"的可能
邻接矩阵（方案 C）实测不可行（ATOP §2 报告 16K GPU 跑 10 小时不出连通图）
TopoOpt 群论路线（方案 D）的 regular degree 约束无法表达 ZCube 类端口非对称结构，而 ZCube 正是 ATOP 论文证明的高性价比拓扑代表 → 该约束是关键 deal-breaker

评估器分级数

方案	层数	优点	缺点
2 层 (ATOP)	flow-level + 端到端	简单	粗粒度，无法跳过明显不合格候选
5 层（选定）	拓扑结构 / 集合通信 / iter / workflow / 成本	早剪枝 + 跨 workload 复用 + 可诊断	实现复杂度高
7 层（按 docs/09 全指标）	含容错 / 其他业界指标层	信息最全	多数层 Phase 1 用不到

选择 5 层：在最小复杂度下覆盖 P0 优化目标的评估链路。Phase 2 可扩展到 7 层（加入容错独立层、其他业界指标层）。

搜索算法

算法	适用	在本场景
NSGA-II （选定）	评估秒级、维度 ≥ 10、目标 ≤ 4	4 种算法（NSGA-II/Bayesian/QMC/Random）均未收敛，NSGA-II 取得最佳平衡
NSGA-III	目标数 ≥ 5	Phase 2 加 ForestColl 后可考虑
MOEA-D	目标 ≥ 10	Phase 3 加更多目标后可考虑
MOBO (qNEHVI)	评估开销 > 分钟级	不适合（评估器秒级）
Random + QMC	baseline	留作 Phase 1 对照实验

详细决策树见 08-拓扑寻优/04。

Drawbacks & Risks

风险	影响	缓解措施
Generator 协同复杂度	4 类 Generator 在同种群里共存，调试困难	Phase 1 只启用 Family + GraphMutator 两类，验证稳定后逐步加入其他
评估器精度上限决定搜索质量上限	math evaluator ~5% 误差可能掩盖 3% 性能差异（参考 ATOP 仿真器精度分析）	Stage 2 用 g5 精筛 Pareto 集合提升判别力；Future Possibilities 列入 NN surrogate model 加速
Phase 1 仅 3 个 P0 目标可能不足	训练 iter time 已覆盖性能，但忽略容错（仅 APL_fail 一个指标）	Phase 2 加入 ForestColl 下界 + 单交换机故障下吞吐降幅
ATOP 11 类超参数模板的复现工作量大	GenericTemplateGenerator 实现需 1-2 周（按论文 Algorithm 1/2）	Phase 1 不实现，作为 Phase 2 第一项工作
NSGA-II 收敛失败	ATOP Appendix J 证实 4 种算法都未收敛到 Pareto-optimal，仅"最佳平衡"	Spec 接受这个现实；输出明确标注"Pareto-approximate"而非"Pareto-optimal"
物理分组算法本 spec 未详述	board/rack/pod 分组的合法性可能影响候选有效性	沿用拓扑生成器 spec 中的 boardGrouping 规则；GraphMutator 算子需保证分组依然合法
Generator 间的 metric 可比性	不同 origin 的候选评估结果直接比较是否公平？	评估只看 candidate.graph，不看 origin，原则上公平。可在 Phase 1 验证实验中加入对照（同一 graph 标多种 origin，看评分是否一致）

Success Criteria

对应 Goal	场景	指标	目标值	测试方法
G1 候选级搜索	复现 ATOP ZCube 类结构	在 1024 GPU 集群上跑寻优器，输出 Pareto 前沿包含端口非对称候选	至少 1 个 Pareto 候选 switch 端口数非全等	启用 FamilyGenerator (fat-tree, dragonfly, slimfly) + GraphMutator + ChangePortAsymmetry 算子，跑 NSGA-II 100 代
G2 多目标 Pareto	三目标 Pareto 前沿分布	输出 Pareto 前沿覆盖目标空间	≥ 20 个非支配候选 + HyperVolume 指标 ≥ baseline（随机搜索）的 2×	单次寻优运行结束后用 pymoo 计算 HV
G3 分层评估	Stage 1 粗筛速度	Layer 1+2+5 单候选评估开销	平均 < 1 秒 / 候选（math + 图论）	profile 10⁴ 个候选的评估总时间
G3 分层评估	Stage 2 精筛速度	Layer 3+4 单候选评估开销	平均 < 5 分钟 / 候选（g5 仿真）	profile Pareto 候选的 g5 评估时间
G4 复用现有资产	FamilyGenerator 族覆盖	内置族数量	9 个族全部可用（与拓扑生成器 spec v1.2.0 一致）	用 `generators.family.families = ALL` 配置跑寻优器
G4 复用现有资产	评估器复用	math + g5 评估器无需修改	0 行修改（仅新增 adapter 层）	对比 `perfmodel/evaluation/` 的 git diff
G5 YAML 兼容	YAML 加载兼容性	寻优器输出的 YAML 可被现有评估器 / 可视化加载	0 个加载失败	把 Pareto 前沿全部 YAML 喂给 `perfmodel.evaluation.math` 和 `frontend.Scene3D`
G5 YAML 兼容	搜索效率	1024 GPU 拓扑寻优总耗时	< 4 小时（math 粗筛）+ < 4 小时（g5 精筛 Pareto 集合）	单服务器 32 核并行
G6 可扩展架构	新增 Generator 的工作量	新增一个虚构 Generator 类（如 `RandomRegularGraphGenerator`）只需实现 `TopologyGenerator` 协议	≤ 200 行代码 + 0 行修改框架文件	编写示例 Generator 验证
G6 可扩展架构	新增目标的工作量	在 Evaluator 添加新 Layer 指标（如 ForestColl 下界）	≤ 100 行代码 + 不影响已有 Layer	实现 ForestColl Phase 1 计算并验证
G1 突破能力	GraphMutator 突破性	启用 GraphMutator 后 Pareto 前沿优于纯 FamilyGenerator	至少 1 个目标 ≥ 5% 改进	A/B 对照实验
共性	硬约束零违规	Pareto 输出的所有候选满足连通性、端口匹配、距离约束	0 个违规	自动化校验脚本

单元测试场景：

test_topology_candidate_serialization: TopologyCandidate ↔ YAML 双向转换无损
test_family_generator_reuses_existing_spec: FamilyGenerator 输出的 graph 与拓扑生成器直接调用的输出 byte-equal
test_graph_mutator_preserves_connectivity: 10000 次随机变异，没有产出非连通图
test_evaluator_layer_caching：同一 candidate 重复评估 Layer 1，Layer 1 结果不重新计算
test_pareto_set_correctness：构造已知支配关系的 100 个 candidate，确认 Pareto 选择正确

Future Possibilities

方向	优先级	前置条件
GenericTemplateGenerator （ATOP 11 类超参数）	高	Phase 1 验证稳定
ForestColl Phase 1 集成（Layer 2 加入理论下界）	高	Phase 1 验证稳定
GraphCrossover （跨族图论交叉）	中	GraphMutator 验证稳定
RandomRegularGraphGenerator （Jellyfish 类）	中	评估器对非规则图的精度验证
Neural surrogate model 加速评估	中	累积足够评估历史数据
算法替换实验 (NSGA-III / MOEA-D / MOBO)	中	Phase 1 baseline 跑通
多 workload 联合优化	中	单 workload 验证稳定
硬件参数联合搜索（NIC 端口 / 交换机 radix）	低	硬件成本模型扩展
GPU 加速的图算法评估器 (Layer 1)	低	评估器瓶颈 profiling 显示 Layer 1 占比高

Implementation Notes

本节在 Phase 1 实现完成后补充，记录 spec 与实际实现的偏差。

变更历史​

Summary​

Motivation​

现状与问题​

驱动力​

Terminology​

Goals / Non-Goals​

Background / Prior Art​

业界拓扑寻优方案对比​

与 ATOP 的关键差异​

关键设计依据​

Guide-Level Explanation​

用户视角的使用流程​

与拓扑生成器的关系​

Detailed Design​

概念模型​

Topology Candidate​

Generator 协议​

5 层评估器​

设计原理​

为什么搜索单元是 NetworkGraph 而非参数向量​

为什么 4 类 Generator 而非单一 Generator​

为什么 5 层评估器而非 2 层​

为什么 NSGA-II 而非 MOBO​

算法 / 公式​

Layer 1：拓扑结构指标​

Layer 2：集合通信原语完成时间​

Layer 3：训练/推理 iter time​

Layer 5：网络硬件成本​

约束与规则​

硬约束（候选拒绝）​

软约束（候选标记，不拒绝）​

算子内嵌约束（变异/交叉）​

集成点​

与拓扑生成器（spec v1.2.0）​

与评估器（math + g5）​

与 NetworkGraph（topo_routing）​

YAML 序列化​

引用​

Alternatives Considered​

搜索单元的选择​

评估器分级数​

搜索算法​

Drawbacks & Risks​

Success Criteria​

Future Possibilities​

Implementation Notes​