跳到主要内容

TE-CCL

如何用 MILP 离线求解集合通信的最优路径与发送时序

核心要点：

  • 把集合通信调度建模为 Multi-Commodity Flow + Time-Expanded Graph
  • MILP + A* 搜索离线求最优 makespan，运行时按表执行无动态决策
  • 显式建模 α 延迟（time-expanded 边权重），优于 SCCL/TACCL 的隐式假设
  • 与 ECMP/AR/DQPLB 互补：TE-CCL 管规律 collective，运行时路由管 background traffic

TE-CCL（Traffic Engineering for Collective Communication，Microsoft SIGCOMM 2024）将集合通信调度建模为 Multi-Commodity Flow（MCF）问题[1]，通过 MILP + A* 搜索离线求解"每个 chunk 走哪条路径、何时发"。与 ECMP / AR / DQPLB 的根本区别在决策时机——前者运行时反应式调度，TE-CCL 在拓扑和流量矩阵确定下做一次全局优化。

为什么集合通信适合离线求解最优调度？​

为什么 ECMP / AR / DQPLB 不是最优​

ECMP / AR / DQPLB 这一类运行时路由策略本质上是 reactive——它们对每条流的处理都是局部的：

  • ECMP：哈希入口决定，全程对全网拥塞无感
  • AR：本地队列深度感知，对下游路径无感
  • DQPLB：CQE 反馈感知，但每个 QP 之间相互独立

但 AI 训练的 collective communication 流量具有三个特殊性：

  • 流量矩阵完全已知：AllReduce / AllToAll / ReduceScatter 的源-目-数据量在 op 启动前完全确定
  • 流量模式高度重复：训练每一步的通信模式几乎相同（除 KV cache 类动态部分）
  • 拓扑已知：物理网络拓扑、链路容量、α-β 参数在部署时确定

这三点意味着：集合通信的最优调度可以离线一次性求解——运行时不需要做任何决策，只按计划执行即可。TE-CCL 正是利用这一观察。

流量工程视角​

把集合通信看作一个 traffic engineering 问题：

  • 网络：GPU 互联拓扑（DAG），每条边有容量限制
  • 需求：每对 GPU 间需要传输的 chunk 数据量
  • 目标：最小化所有 chunk 全部到达目的地的总耗时（后续节统一记为 makespan $T$）

这正是经典的 Multi-Commodity Flow with Makespan Objective。求解后得到每个 chunk 的完整路径 + 时间表，运行时按表执行即可。

TE-CCL 如何把集合通信形式化为 MCF?​

Multi-Commodity Flow 简介​

MCF 是网络优化领域的经典问题：给定有向图 $G = (V, E)$、每条边的容量 $c_e$、$K$ 条流量需求 $\{(s_k, t_k, d_k)\}$（源、汇、需求量），求每条流在各边上的分配 $f_{k,e}$，满足容量约束和流守恒约束，并优化目标函数（如总传输完成时间、链路利用率等）。

TE-CCL 把每个 chunk 当作一个 commodity，最小化 makespan。

Time-Expanded Graph​

普通 MCF 不能直接表达"时间"——它只关心稳态流量分配。但集合通信的关键正是时序：chunk A 必须先到达节点 X 才能从 X 转发出去。

TE-CCL 用 time-expanded graph（时间展开图）解决：

原图：   节点 A --(链路)--> 节点 B
                              
时间展开（时间步 t = 0, 1, 2, ...）：
         A@t=0  ----[传输边]----> B@t=1
         A@t=1  ----[传输边]----> B@t=2
         A@t=2  ----[传输边]----> B@t=3
         ...
         A@t=0  ----[buffer 边]--> A@t=1   (留在原节点)
         A@t=1  ----[buffer 边]--> A@t=2
         ...
  • 每个原节点在每个 epoch $t \in \{0, 1, \ldots, T_{\max}\}$ 都有一个副本 $v@t$（一个 epoch 是离散化的最小时间粒度 $T_{\text{epoch}}$，由求解器配置）
  • 链路 $(u, v)$ 变为时间边 $(u@t, v@{t + \Delta_{(u,v)}})$，其中 $\Delta_{(u,v)}$ 是按 α-β 模型计算出的"传输 epoch 数"：
$$\begin{equation} \Delta_{(u,v)} = \left\lceil \frac{\alpha_{(u,v)} + s_{\text{chunk}} / \beta_{(u,v)}}{T_{\text{epoch}}} \right\rceil \label{eq:route-te-ccl-link-latency} \end{equation}$$

其中 $\alpha_{(u,v)}$、$\beta_{(u,v)}$ 为链路 $(u,v)$ 的 α-β 参数（见 6.2 Alpha-Beta 模型），$s_{\text{chunk}}$ 为 chunk 大小。高带宽短链路 $\Delta = 1$，低带宽长链路（如 cross-DC）可能跨多个 epoch。

  • 同节点不同 epoch 之间用 buffer 边连接，表示 chunk 可以"停在原节点等下一个 epoch 再发"

时间展开后，MCF 求解器自然处理时序约束——chunk 的发出时刻、传输用时、到达时刻在图结构中显式编码，这正是 TE-CCL 相对 SCCL/TACCL 能显式建模 α 延迟的根本原因。

三类核心约束​

TE-CCL 的 MILP 形式化包含三类约束：

1. 容量约束：每条物理链路在每个 epoch 上承载的 chunk 数不超过其传输能力。设 $T_{\text{epoch}}$ 为单 epoch 时长，则链路容量为

$$\begin{equation} c_{(u,v)} = \left\lfloor \beta_{(u,v)} \cdot T_{\text{epoch}} / s_{\text{chunk}} \right\rfloor \label{eq:route-te-ccl-chunk-capacity} \end{equation}$$

容量约束：

$$\begin{equation} \sum_{k} f_{k, (u@t, v@{t+\Delta_{(u,v)}})} \le c_{(u,v)} \quad \forall (u,v) \in E, \forall t \label{eq:route-teccl-capacity} \end{equation}$$

2. 流守恒约束：每个中间节点的入流量 = 出流量（不能凭空产生或消失）

$$\begin{equation} \sum_{e \in \text{in}(v@t)} f_{k,e} = \sum_{e \in \text{out}(v@t)} f_{k,e} \quad \forall v \notin \{s_k, t_k\}, \forall t \label{eq:route-teccl-conservation} \end{equation}$$

3. 目的地约束：每条 chunk 必须在最终时间 $T$ 之前到达所有目的节点

$$\begin{equation} \sum_{t \le T} \sum_{e \in \text{in}(t_k @ t)} f_{k,e} \ge d_k \quad \forall k \label{eq:route-teccl-destination} \end{equation}$$

目标函数​

TE-CCL 最小化 makespan $T$（最晚 chunk 到达的 epoch 编号），约束为前述 $\eqref{eq:route-teccl-capacity}$、$\eqref{eq:route-teccl-conservation}$、$\eqref{eq:route-teccl-destination}$：

$$\begin{equation} \min T \label{eq:route-teccl-objective} \end{equation}$$

$T$ 是 MILP 中的整数决策变量——这正是问题为什么不是纯 LP 而是 MILP 的根本原因。

求解器和部署流程是怎样的？​

MILP + A* 搜索​

直接求解上述 MILP 在大规模拓扑（如 1024 GPU）上的复杂度过高。TE-CCL 采用混合策略：

  • MILP 求解器（Gurobi 等）：处理容量、守恒、目的地约束
  • A* 搜索：在 chunk 数量维度上做剪枝——按 chunk 大小排序，逐步增加 chunk 数直到无法在更短 makespan 内放下，避免穷举所有 chunk 划分

两种 Switch 模型​

TE-CCL 支持两种交换机抽象，对应不同硬件能力：

Switch 模型描述对应硬件
Copying switch交换机可以复制 chunk给多个出口支持 SHARP 协议的交换机（InfiniBand Quantum 系列）
Non-copying switch交换机只能转发，不复制普通以太网/IB 交换机（类似 TACCL 的 hyper-edge model）

@tbl-route-teccl-switch-models 两种 switch 抽象与对应硬件

复制能力对 AllReduce / Broadcast 类操作影响显著——SHARP 交换机能在路径上做规约和复制，TE-CCL 能利用这一点找到更短的 makespan 方案。

输入与输出​

输入：
  - 网络拓扑 G = (V, E) 与每条边的 α (μs)、β (GB/s)
  - 集合通信原语类型（AllReduce / AllToAll / Broadcast 等）
  - chunk 划分粒度（chunk size，例如 25 KB）
  - switch 模型（copying / non-copying）

输出：
  - 完整 schedule：对每个 chunk c，给出
    * 路径序列 (source -> hop1 -> hop2 -> ... -> destination)
    * 每跳的发出时刻 t
  - 总 makespan T*

离线优化 + 运行时部署​

部署流程：
  1. 离线阶段（一次性）：
     输入拓扑 + α/β 参数 + collective op 类型 ->
     MILP 求解 -> 调度表 schedule.json
  2. 编译阶段：
     schedule.json -> NCCL/RCCL 可执行的 algo plugin
  3. 运行时：
     训练步骤启动 collective -> 按 plugin 表执行
     （不做任何动态决策，与 ECMP/AR/DQPLB 完全不同）

求解时间在分钟到小时级（取决于拓扑规模和 chunk 数），但分摊到训练全程（数天到数周）几乎可忽略。

TE-CCL 与运行时路由的根本区别在哪？​

维度TE-CCLECMPARDQPLB
决策时机离线（编译时）运行时（入口哈希）运行时（每包）运行时（每 segment）
全局视野完整（全网拓扑）局部（一跳）局部（本交换机）局部（本连接）
流量矩阵假设已知且静态未知未知已知（每对节点）
拥塞响应无（计划已避免拥塞）无有有
适用场景collective comm（流量规律）通用通用collective comm
求解开销分钟-小时（一次性）000

@tbl-route-teccl-vs-runtime TE-CCL 与运行时路由的对比

TE-CCL 不是 ECMP/AR 的替代方案，而是补集——TE-CCL 适合规律的 collective，运行时路由适合 background traffic 和不可预测的流量。生产部署中两者通常共存。

TE-CCL 比 TACCL / SCCL 提升在哪？​

TE-CCL 之前的工作 SCCL[2] 和 TACCL[3] 也用优化方法生成 collective schedule，但形式化和求解策略不同：

维度SCCLTACCLTE-CCL
形式化Step-based SMT (Z3)Sketch + MILP（用户引导搜索空间）Time-expanded MCF
α 延迟建模隐式（每步固定开销）隐式显式（time-expanded 边权重 + epoch）
流水线强制 barrier（步间同步）受限流水线完全流水线
求解策略SMT 求解器MILP（受 sketch 约束）MILP + A*
拓扑泛化弱（需要规则拓扑）中强（任意 DAG）

@tbl-route-teccl-vs-prior TE-CCL 与 SCCL / TACCL 对比

注意三者都是基于求解器的优化方法（SCCL 用 SMT，TACCL/TE-CCL 用 MILP），不是启发式——它们的真正差异在于问题建模方式（步数 vs sketch vs time-expanded flow）和对时序与流水线的处理粒度。

实测改进​

TE-CCL 论文[1]披露的 benchmark 数据（指标为 algorithm bandwidth (algbw) = 数据量 / makespan。algbw 与 makespan 数学上恒为倒数；但在小消息场景下 makespan 的下降幅度被 α 部分摊平，因此"algbw $k\times$ 改进"约等于"makespan 缩短 $k\times$"仅在大消息场景下成立，小消息下应直接看 makespan 数值）：

对比对象拓扑 / 场景改进幅度
TACCLTACCL 支持的拓扑（小规模）algbw 2×
TACCLGPU testbedalgbw 2.14×
RCCLGPU testbedalgbw 3.18×
SCCLchunk > 1 的所有场景TE-CCL 始终更优（流水线 vs barrier）

@tbl-route-teccl-results TE-CCL 实测改进

关键归因：TE-CCL 的流水线传输 vs SCCL 的barrier-based 步进——SCCL 要求一步内所有 chunk 都到达才能进入下一步，TE-CCL 允许 chunk 边到边发，时间利用更紧凑。

TE-CCL 综合性能特性？​

指标TE-CCLECMP（对照）DQPLB（对照）
大规模 AllReduce 完成时间理论最优（MILP 求解）受哈希碰撞限制高（动态平衡）
拥塞响应无（计划已避免拥塞）无有
拓扑适应性任意 DAGFat-tree / ClosRail-Optimized
流量矩阵变化适应弱（需重新求解）强强
求解开销分钟-小时（离线）00
部署门槛高（求解器 + plugin 集成）低中（通信库改造）

@tbl-route-teccl-perf 性能特性对比

何时该用 TE-CCL，何时不该？​

适用场景：

  • 流量矩阵高度规律的训练场景（标准 LLM 训练）
  • 拓扑稳定的集群（拓扑变更后需要重新求解）
  • 大消息 AllReduce / AllToAll（chunk 数足够多让 MILP 收益明显）
  • 有 SHARP 支持的 InfiniBand 集群（copying switch 模型收益最大）

局限：

  • 求解扩展性：MILP 求解时间随节点数和 chunk 数快速增长，TE-CCL 论文[1]实测 AllToAll 拓扑规模上限约 128 节点，AllGather 在 A* 剪枝下可处理更大规模，但仍远小于 10K+ GPU 训练集群
  • 流量矩阵变化敏感：流量需求变化需要重新求解，不适合动态 workload
  • 依赖准确的 α/β 参数：参数标定误差直接影响 schedule 最优性（见 6.2 Alpha-Beta 模型）
  • 集成开销：需要把求解结果编译为 NCCL/RCCL 算法 plugin（MSCCL plugin 格式）

选型建议：

  • 标准 LLM 训练（拓扑稳定 + 流量规律）：TE-CCL 是离线最优方案，与运行时路由（DQPLB / AR）共存
  • 拓扑频繁变化或多租户场景：使用运行时路由（DQPLB / AR）
  • 小规模集群（< 256 GPU）：TACCL 已足够，TE-CCL 的求解开销不划算
  • 大规模生产集群（> 10K GPU）：当前 MILP 求解器扩展性受限，仍以运行时路由为主

Takeaway​

知识点核心结论
离线性前提collective comm 的流量矩阵 + 拓扑 + α/β 都是已知静态量
形式化Time-Expanded Graph + MCF MILP，显式建模时序与 α 延迟
目标函数$\min T$（makespan），$T$ 是整数变量（MILP 而非纯 LP 的原因）
求解策略MILP + A* 在 chunk 数维度剪枝，分钟-小时级离线求解
Switch 模型copying（SHARP）/ non-copying，决定 Broadcast/AllReduce 收益
vs SCCL/TACCL流水线传输 vs barrier 步进；显式 α vs 隐式步开销
实测改进algbw 2× vs TACCL，3.18× vs RCCL；大消息场景
主要局限MILP 扩展性受限（AllToAll ~128 节点）；流量变化需重解
部署关系与运行时路由互补共存，不互相替代

参考资料​

  1. Liu et al., Rethinking Machine Learning Collective Communication as a Multi-Commodity Flow Problem, SIGCOMM 2024. https://dl.acm.org/doi/10.1145/3651890.3672249
  2. Cai et al., Synthesizing Optimal Collective Algorithms, PPoPP 2021. https://dl.acm.org/doi/10.1145/3437801.3441620
  3. Shah et al., TACCL: Guiding Collective Algorithm Synthesis using Communication Sketches, NSDI 2023. https://arxiv.org/abs/2111.04867

延伸阅读​