多芯片互联路由算法设计调研
目录
- 背景与需求
- 路由策略调研
- 2.1 静态最短路径路由
- 2.2 ECMP（等价多路径）
- 2.3 拓扑感知分层路由
- 2.4 自适应路由
- 2.5 In-Network Compute（SHARP）
- 策略对比
- 分层设计方案
- 4.1 数学模型路由方案
- 4.2 G5 仿真路由方案
- 两套模型的协作关系
- 参考文献
背景与需求
LLM 推理对互联的特殊要求
大模型推理（LLM Inference）在多芯片部署时，集合通信（AllReduce、AllToAll、AllGather 等）占据关键路径的相当大比例。以 Tensor Parallelism 为例，每个 Transformer 层的 FFN 计算结束后都需要执行一次 AllReduce，其延迟直接叠加进 TPOT（每 token 生成时间）。MoE 模型的 Expert Parallelism 则依赖大量 AllToAll，进一步放大了通信瓶颈。
当前平台的路由建模存在以下局限：
- 固定延迟假设：
resolve_path()对 c2c/b2b/r2r/p2p 四级路径各取固定参数，无法反映实际负载下的排队延迟。 - 无多路径利用：拓扑图中存在多条等价路径时，模型仍按单条路径计算，低估了可用带宽。
- 交换机黑盒化：交换机延迟取固定 0.25 μs，无法体现跳数差异和端口竞争。
- 集合通信路径展开失真：G5 仿真层中集合通信假设芯片间直连，绕过了交换机的实际调度逻辑。
核心问题
| 问题 | 影响 |
|---|---|
| 热点链路（Hotspot） | 部分链路过载，AllReduce 尾延迟恶化 |
| 流量不均衡 | 多路径未被充分利用，有效带宽低于理论值 |
| Elephant Flow 干扰 | 大 tensor 传输占满链路，小消息延迟抖动剧烈 |
| 多跳累积延迟 | 跨 Rack/Pod 路由经历多级交换，延迟需逐跳叠加 |
路由策略调研
静态最短路径路由
原理：使用 Dijkstra 算法（有权图）或 BFS（无权图）在拓扑图上预先计算每对芯片之间的最短路径，并将结果固化为静态路由表。路径权重可定义为跳数、延迟或带宽的倒数。
适用场景：
- 小规模拓扑（单机板内、2-4 芯片）
- 通信模式高度规律、负载相对均衡
- 数学建模的基础层（作为 ECMP 的候选路径集来源）
局限性：
- 不感知负载：路径在离线计算后固定，运行时不感知链路拥塞，高负载下延迟被低估。
- 单路径浪费：当多条等价最短路径存在时，只选其中一条，有效带宽受限。
- 跳数权重设置敏感：权重函数选取不当会导致路径选择偏差，对异构拓扑尤为明显。
ECMP（等价多路径）
原理：ECMP（Equal-Cost Multi-Path）在有多条等价最短路径的情况下，通过哈希函数将不同流（Flow）分配到不同路径上。标准做法是对五元组（源 IP、目的 IP、源端口、目的端口、协议）做哈希，取模决定路径编号。在芯片互联场景中，可等价地对（源芯片 ID、目的芯片 ID、流 ID）哈希。
优点：
- 负载分散：多条路径并行承载不同流，聚合带宽接近链路总和。
- 实现简单：不需要实时状态，路由表静态生成，开销极低。
- 对称性好：Fat-Tree、Clos 等数据中心拓扑的等价路径数量充足，ECMP 效果显著。
局限性：
- Hash 碰撞：多条流可能哈希到同一路径，造成局部拥塞，其余路径空闲。
- Elephant Flow 问题：一条大型 AllReduce 流可能独占某路径，破坏均衡性，且 ECMP 无法感知流大小来重新分配。
- 不感知实时拥塞：哈希结果固定，即使某路径已满载，新流仍可能被分配到同一路径。
在 LLM 推理的数学模型中，ECMP 可用于估算每条路径分摊的流量，进而计算 M/D/1 队列的到达率输入。
拓扑感知分层路由
原理：仿照 NCCL 的设计思路，将通信分为域内（intra-domain）和域间（inter-domain）两层，每层采用与网络特性匹配的通信原语和路径选择策略。
在 Tier6+ 的五级层级（Die → Chip → Board → Rack → Pod）中，分层路由的对应关系为：
| 层级 | 连接类型 | 典型带宽 | 通信策略 |
|---|---|---|---|
| Chip 内 | c2c（芯片内 Die 间） | 448 GB/s | 直连，无路由开销 |
| Board 内 | b2b（芯片间 NVLink） | 400 GB/s | 域内 Ring/AllReduce |
| Rack 内 | r2r（板间交换） | 400 GB/s | 层级 AllReduce 或 AllToAll |
| Pod 内/间 | p2p（Rack 间 IB/ETH） | 400 GB/s | 域间 Ring 或 Tree |
关键设计：路由算法在拓扑图遍历时，优先利用带宽高、延迟低的本地链路，只有跨域通信才升级到上层链路。这与并行策略映射（TP 优先同 Board 内芯片）相互协同，减少了高延迟链路上的流量。
优点：
- 与实际硬件层级自然对齐，路径计算开销小
- 带宽/延迟估算与真实拓扑的匹配度高
局限性：
- 层级划分固化，对非规则拓扑（如 DragonFly）适应性差
- 跨层路径仍需手动定义域边界
自适应路由（Adaptive Routing）
原理：自适应路由在转发决策时参考实时链路状态（队列深度、拥塞信号），动态选择当前最优路径，而不是依赖离线计算的静态表。典型机制包括：
- 基于队列深度：交换机为每条候选路径维护输出端口队列深度，转发时选择队列最短的端口。
- 基于拥塞信号：结合 ECN（Explicit Congestion Notification）或 PFC（Priority Flow Control）信号，感知下游拥塞并绕行。
- Spritz / Flare 等方案：将大流（Elephant Flow）切割为若干小数据包，在路径之间轮流发送（per-packet 路由），最大化带宽利用率，但会引入乱序问题。
ECMP vs 自适应路由对比：
| 维度 | ECMP | 自适应路由 |
|---|---|---|
| 状态维护 | 无状态（哈希） | 有状态（队列/拥塞） |
| 负载均衡效果 | 中等（依赖哈希分布） | 较好（实时调整） |
| 实现复杂度 | 低 | 高（需要硬件支持） |
| 包乱序风险 | 低 | 中至高（per-packet 路由） |
| 适用场景 | 流量模式较规律 | 突发性高、流量不均衡 |
在 G5 仿真层，VOQ（Virtual Output Queue）+ iSLIP 调度器已提供了交换机内自适应调度的基础，可在此之上扩展路径选择逻辑。
In-Network Compute（SHARP）
原理：SHARP（Scalable Hierarchical Aggregation and Reduction Protocol）由 NVIDIA Mellanox 提出，核心思想是将 AllReduce 的归约（Reduce）计算下推到网络交换机中执行，从而避免数据在网络中的多次传输。传统 Ring AllReduce 需要数据在所有节点间绕行两圈，而 SHARP 通过交换机层级树形聚合，使流量缩减为 O(log N) 量级。
实现原理：
- 通信发起方将本地 tensor 切片发往指定的"聚合点"（通常为叶层交换机）
- 交换机对收到的数据执行加法/最大值等归约操作
- 归约结果沿树向上汇总，最终广播回所有参与节点
适用场景：
- 大规模 AllReduce（DP gradient synchronization）
- 支持 SHARP 的 InfiniBand 交换机环境
- 数据精度无损归约（INT32/FP32 加法）
局限性：
- 强依赖专用交换机硬件，通用以太网交换机不支持
- 不适用于 AllToAll（MoE Expert 路由）等非归约型集合通信
- 需要预分配交换机聚合资源（Tree Group），并发集合通信数量受限
在当前 Tier6+ 平台的建模范围内，SHARP 可作为特定场景（InfiniBand 互联、DP 梯度同步）的延迟优化因子纳入数学模型的参数配置，但不作为默认路由机制。
策略对比
| 路由策略 | 实现难度 | 精度提升 | 适用拓扑 | 适用通信类型 | 是否需要运行时状态 |
|---|---|---|---|---|---|
| 静态最短路径 | 低 | 基础 | 任意 | 点对点 P2P | 否 |
| ECMP | 低-中 | 中等（多路径利用） | Fat-Tree、Clos | AllReduce、AllGather | 否 |
| 拓扑感知分层路由 | 中 | 较高（层级匹配） | 层次化（Rack/Pod） | 全类型集合通信 | 否 |
| 自适应路由 | 高 | 高（实时均衡） | 通用（需交换机支持） | 突发流量、混合负载 | 是 |
| SHARP（In-Network） | 高（硬件依赖） | 高（降低流量） | InfiniBand 网络 | AllReduce（DP） | 是（交换机资源） |
建模优先级建议：数学模型优先实现拓扑感知分层路由 + ECMP；G5 仿真优先实现静态路由表展开 + 自适应调度（VOQ/iSLIP 已有基础）。
分层设计方案
数学模型路由方案
数学模型（L4 评估层）的目标是在毫秒级内给出集合通信的估算延迟，供 TTFT/TPOT 计算使用。设计流程如下：
第一步：拓扑图构建
- 以每个芯片为节点，以互联链路为有向边构建图
- 边属性包含：带宽（GB/s）、基础延迟（μs）、跳数、链路类型（c2c/b2b/r2r/p2p）
- 交换机作为中间节点加入图，并标注其端口数和内部延迟
第二步：最短路径计算
- 对所有参与集合通信的芯片对，使用 Dijkstra 计算加权最短路径
- 权重函数：
w = latency_us + data_size_gb / bandwidth_gbps * 1e6（单位 μs） - 输出：每对芯片的路径序列（节点列表）和路径总延迟
第三步：ECMP 多路径分流
- 枚举两节点间所有等价最短路径
- 按流 ID 哈希分配流量到各路径，计算每条路径的分摊流量
- 分摊后的有效带宽 = 单路径带宽 × 路径数量（理想情况）
第四步：M/D/1 排队延迟叠加
- 对每条链路，根据分摊流量计算到达率 λ
- 服务率 μ = 链路带宽 / 平均消息大小（确定性服务时间，D 分布）
- M/D/1 队列平均等待时间：
W_q = ρ / (2μ(1-ρ))，其中ρ = λ/μ - 将路径上各链路的排队延迟累加，得到端到端总延迟
第五步：集合通信延迟汇总
- AllReduce（Ring 算法）：
T = 2(N-1)/N × (α + data/β)，其中 β 为有效带宽（含 ECMP 分流和排队延迟） - AllToAll：
T = (N-1) × (α + chunk_size/β) - 最终输出集合通信延迟供上层 EvaluationEngine 使用
G5 仿真路由方案
G5 仿真（tier6 层）的目标是事件驱动地精确模拟每个数据包的传输过程，验证数学模型的精度。
第一步：路由表生成
- 在仿真初始化阶段，对拓扑图运行全局路由算法（最短路径 + ECMP 表）
- 生成每个交换机端口的转发规则（目的芯片 ID → 输出端口映射）
- 对 ECMP，生成哈希分桶表
第二步：集合通信路径展开
- 根据集合通信类型和参与芯片集合，将逻辑通信原语展开为具体的点对点消息集合
- Ring AllReduce 展开为 N 轮、每轮 N-1 条 P2P 消息
- AllToAll 展开为 N×N 条 P2P 消息矩阵
第三步：按真实路径调度 DMA
- 每条 P2P 消息按路由表逐跳转发
- 每跳生成一个 DMA 事件，注入对应芯片/交换机的事件队列
- 交换机端口按 VOQ + iSLIP 仲裁，并支持 PFC/ECN 信号
- 记录每个数据包在每跳的入队时间、出队时间，用于延迟分析
第四步：结果聚合
- 集合通信完成时间 = 最后一个参与芯片收到完整数据的时间戳
- 输出链路利用率热图、队列深度时序、端到端延迟分布
两套模型的协作关系
共享配置（SwitchConfig）
数学模型和 G5 仿真共享同一套拓扑配置参数，由 SwitchConfig 统一描述交换机的端口数、内部延迟、带宽、缓冲区大小等。二者从相同的拓扑 YAML 文件读取配置，确保对比基准一致。
职责分工
| 维度 | 数学模型（L4） | G5 仿真（tier6） |
|---|---|---|
| 计算速度 | 毫秒级（参数扫描可行） | 秒至分钟级（精确但慢） |
| 建模粒度 | 流级别（聚合延迟估算） | 数据包级别（事件驱动） |
| 适用场景 | 快速设计空间探索 | 热点验证、算法调试 |
| 交换机建模 | M/D/1 队列模型 | VOQ + iSLIP 精确调度 |
| 路由策略 | 最短路径 + ECMP 分流 | 路由表逐跳转发 |
交叉验证方式
- 标定场景：选取小规模拓扑（4-8 芯片）和简单通信模式（单次 AllReduce），分别运行数学模型和 G5 仿真，对比延迟结果。
- 偏差分析：若数学模型与 G5 仿真偏差超过 15%，分析来源（排队延迟参数、哈希碰撞率估计）并调整数学模型参数。
- 参数反馈：G5 仿真输出的实测链路利用率可用于反校 M/D/1 模型中的到达率估算精度。
- 版本对齐：两套模型的拓扑图构建逻辑共用同一模块，路径权重函数保持一致，避免因配置不同导致对比失效。
典型工作流
- 用户提交大规模仿真任务（如 256 芯片 DeepSeek-V3）
- 数学模型在秒级内完成路由估算，输出 TTFT/TPOT 预测值
- 如预测结果显示通信瓶颈，选取关键场景用 G5 仿真精确复现
- G5 仿真输出热点链路报告，指导拓扑优化（调整 ECMP 哈希策略、增加链路带宽）
- 优化后再次运行数学模型验证改进效果
参考文献
-
NCCL 源码与文档：NVIDIA Collective Communications Library，https://github.com/NVIDIA/nccl — 分层通信策略与域内/域间路由的工程实现参考。
-
SHARP 论文：Mellanox Technologies, "Scalable Hierarchical Aggregation Protocol (SHArP): A Hardware Architecture for Efficient Data Reduction," Interconnect2016。
-
ECMP in Data Centers：A. Greenberg et al., "VL2: A Scalable and Flexible Data Center Network," SIGCOMM 2009 — Fat-Tree + ECMP 均衡原理。
-
M/D/1 排队论：Kleinrock, L., Queueing Systems Volume 1: Theory, Wiley, 1975 — 确定性服务时间排队模型。
-
Adaptive Routing：Zahavi, E., "Fat-Tree Routing and Node Ordering Providing Contention-Free Traffic for MPI Global Collectives," IEEE HPCS 2010 — 自适应路由在 IB 网络的实现。
-
Spritz / CONGA：Alizadeh, M. et al., "CONGA: Distributed Congestion-Aware Load Balancing for Datacenters," SIGCOMM 2014 — 自适应路由与拥塞感知分流。
-
DeepSeek-V3 技术报告：DeepSeek-AI, "DeepSeek-V3 Technical Report," 2024 — MoE 模型多芯片通信模式分析。
-
iSLIP 调度算法：McKeown, N., "The iSLIP Scheduling Algorithm for Input-Queued Switches," IEEE/ACM Trans. Networking, 1999 — VOQ + iSLIP 交换机仲裁基础。