不规则与流水化 AllToAll
稀疏 MoE 场景下 Wave Scheduling 如何应对不规则发送与长尾延迟
核心要点：
- 经典 AllToAll 假设规则 $N \times N$ 同尺寸方阵，稀疏 MoE / V4 EP 取消该假设
- 发送矩阵数据相关、稀疏、长尾，p95 link 数据量可达均值 2×+
- Wave-scheduled 把单次 a2a 切 $W$ 个 wave 与 compute / combine 流水，最优 $W^* = \sqrt{M / (\alpha \beta)}$
- 长尾延迟 → adaptive routing + 拥塞控制从"可选"变"必选"
- 上游耦合 distributed top-k，下游耦合 expert compute / combine
经典 AllToAll 见 4.9 AllToAll。本节讨论取消静态 routing 约束后的稀疏 / wave-scheduled AllToAll。
经典 vs 不规则
核心问题：不规则与经典 a2a 差异在哪，为什么经典优化路径不能直接用？
| 维度 | 经典 (dense) | 不规则 (sparse) |
|---|---|---|
| 发送矩阵 | 每对 $(i, j)$ 大小 $m$ 相同 | 每对不同，可为 0 |
| 决定时机 | 静态可知 | 运行时由 routing 决定 |
| 典型场景 | 经典 MoE （固定路由约束） | DeepSeek V4 EP （无 routing target 约束） |
| 库接口 | MPI_Alltoall / ncclAllToAll | MPI_Alltoallv / 自定义 sparse send list |
| Link 利用 | 均衡 | 长尾，部分 link 瞬时拥塞 |
| 拥塞控制 | 低需求 | 高需求 |
@tbl-cc-sparse-a2a-vs-dense 经典 vs 不规则 AllToAll
EP 不规则 a2a 的来源
核心问题：MoE 中什么时候 a2a 会变不规则？
受约束情形 （V3 风格）
V3 强制每 token top-k expert 分布在固定 $k_{\text{node}} = 4$ 节点:
- 每 token 命中节点数固定 → 发送矩阵接近均衡
- Dispatch pattern 静态可规划
- 代价：路由不自由，选不到真正最相关 expert
无约束情形 （V4 风格）
V4 取消 routing target node 约束，每 token 真自由选 top-k of $E$:
- 命中节点集是数据相关 sparse subset
- 发送矩阵稀疏，行 / 列长尾分布 （热门 expert 集中少数 node）
- 库必须
Alltoallv风格，传完整 send-count / recv-count 矩阵
长尾延迟问题
Batch 充分大时热门 expert 让某 link 瞬时数据量远超均值。设每 token 命中节点 $j$ 概率 $p_j$，多项分布正态近似下 95-th percentile link 数据量：
$$\begin{equation} m_{\text{p95}} \approx m_{\text{avg}} \cdot \left( 1 + 1.645 \sqrt{\frac{1}{B \bar{p}}} \right) \label{eq:cc-sparse-a2a-p95} \end{equation}$$$\bar{p} = 1 / N$ 均匀路由期望，1.645 是标准正态 95% 分位数。多项分布 $\mathrm{Multinomial}(B, \bar{p})$ 单格方差 $\sigma^2 = B \bar{p} (1 - \bar{p}) \approx B \bar{p}$, p95 = mean + 1.645σ。
$B \bar{p} < 10$ （小 batch 或路由严重倾斜） 时正态近似失效，实际长尾更严重，p95 可达均值 2×+。同步式 a2a 关键路径由最慢 link 决定。
Wave-Scheduled 流水化
核心问题：同步等所有 token dispatch 完才算太慢，能否流水？
调度模式
Expert 分 $W$ 个 wave，每 wave $E / W$ 个, DeepSeek V4 MegaMoE:
时间 →
Wave 1: dispatch ──→ compute ──→ combine ──→
Wave 2: dispatch ──→ compute ──→ combine ──→
Wave 3: dispatch ──→ compute ──→ combine ──→
理想下 wave 间错开"dispatch 延迟"相位，加速比相对 naive 串行接近 $W / (W + 2)$。
Wave 数与消息粒度
| $W$ | 单 wave 通信量 | Overlap | 网络要求 |
|---|---|---|---|
| 1 （无 wave） | $M$ | 无 | 大消息带宽 |
| 4 | $M / 4$ | 中 | 中等消息延迟 |
| 8 | $M / 8$ | 高 | 小消息低延迟 |
| 16+ | $M / 16$ 以下 | 高，收益递减 | 极低启动延迟 |
@tbl-cc-sparse-a2a-wave Wave 数与网络要求
$W$ 增大单消息变小，$\alpha$ 项占比上升，是 RDMA verbs / NVSHMEM 小消息性能拐点。
最优 wave 数
端到端时间：
$$\begin{equation} T(W) \approx W \alpha + \frac{M}{\beta} + \frac{M}{W \beta} \label{eq:cc-a2a-window-time} \end{equation}$$三项含义：
- $W \alpha$: $W$ 次 wave 启动延迟
- $M / \beta$：通信总量在带宽上的下界
- $M / (W \beta)$：流水尾部最后一 wave 无法重叠的残差
对 $W$ 求导 ($\alpha = M / (W^2 \beta)$) 得最优：
$$\begin{equation} W^* \approx \sqrt{\frac{M}{\alpha \beta}} \label{eq:cc-sparse-a2a-optimal-w} \end{equation}$$NVLink 5.0 ($\beta \approx 50$ GB/s 单链路单向，$\alpha \approx 1 \mu s$, $M = 16$ MB) 下 $W^* \approx 18$，与 MegaMoE 实测 8–16 wave 一致 （实测略小因还需考虑 expert compute 时间）。
对硬件 / 通信库的新需求
核心问题：不规则 + 流水化让经典 a2a 优化路径失效，新需求在哪？
自适应路由
长尾发送矩阵让特定 link 短时间过载，静态最短路由形成持续拥塞。Dragonfly / Slim-Fly 类拓扑的 adaptive routing 在不规则 a2a 下从"可选"变"必选"。NVSwitch 内部多路径调度也属此。
流量隔离与 QoS
Wave 间需延迟可预测性：某 wave dispatch 不能被前一 wave combine 阻塞。需：
- 多 channel / 多 QP 并发：不同 wave 走不同 hardware queue
- 优先级调度：dispatch （关键路径） 优先于 combine （非关键路径）
细粒度集合通信原语
NCCL ncclAllToAllv 仍是单次同步调用，流水化需：
- 异步分块 a2a：每 wave 独立发起 / 独立完成事件
- 应用层在前一 wave 完成事件触发后立刻计算
与传统"先 a2a 再算"同步模型不同。NVSHMEM / GPUNetIO 类 device-initiated 通信是天然契合方向。
拥塞控制
IB ECN / Adaptive Routing、Ethernet DCQCN / HPCC 在大消息均衡 a2a 时几乎无效 （队列不积压）。小消息不规则 a2a 下特定 link 瞬时排队 → ECN 标记 → 上层调速率。RoCE v2 + 完善拥塞控制成为前提。
与其他原语的衔接
核心问题：不规则 AllToAll 如何与 AllReduce/AllGather 等其他原语衔接优化端到端性能？
不规则 a2a 常是前序 top-k 选择的下游：
[token 计算 affinity]
→ distributed top-k (见 13-distributed-top-k)
→ 构造 sparse send list
→ sparse / wave-scheduled a2a 做 dispatch
→ expert compute
→ combine 阶段 sparse a2a (Expert 输出按原路径回送)
Top-k 输出的索引集合直接作为 a2a 的 send count 矩阵。两原语在端到端通信栈紧耦合。
Takeaway
| 知识点 | 核心结论 |
|---|---|
| 不规则 a2a 来源 | 取消 routing 约束 （V4 风格），发送矩阵数据相关 + 长尾 |
| 长尾延迟 | 关键路径由最慢 link 决定，p95 可达均值 2× |
| Wave scheduling | 拆 $W$ wave 流水，dispatch / compute / combine 重叠 |
| 最优 $W^*$ | $\sqrt{M / (\alpha \beta)}$, NVLink 5.0 上 ~18 |
| Adaptive routing | 从"可选"变"必选" |
| QoS | 多 channel / 多 QP + dispatch 优先 |
| 库接口 | 需异步分块 + device-initiated |
| 拥塞控制 | RoCE v2 + DCQCN / HPCC 成为前提 |
| 上游耦合 | distributed top-k 输出 = a2a send count 矩阵 |
@tbl-cc-sparse-a2a-takeaway 不规则 / 流水化 AllToAll 要点
参考资料
- DeepSeek-V3 Technical Report — 受约束 EP
- DeepSeek-V4 / MegaMoE 文档 — wave scheduling 与无约束路由
- 上游：4.13 Distributed Top-K
- 同主题：4.9 AllToAll — 经典 dense a2a