Near-Optimal Wafer-Scale Reduce
arXiv:2404.15888v4 | HPDC 2024 Luczynski, Gianinazzi, Iff, Wilson, De Sensi, Hoefler (ETH Zurich + Cerebras + Sapienza)
首次系统性研究 Cerebras WSE 上的 Reduce/AllReduce collective。提出性能模型 → 设计新算法 → 建立下界 → 自动生成接近最优代码。
核心贡献
1. WSE 性能模型
T = max(C, E/N) + L + (2*TR+1)*D
四个瓶颈项：Contention（PE 瓶颈）、Energy/N（网络拥塞）、Distance（延迟）、Depth（串行依赖）。模型预测误差 < 4%。
2. Reduce 算法谱系
| 算法 | 最优区间 | 距下界 |
|---|---|---|
| Star | B=1（标量） | ≤5.9× |
| Chain | B ≫ TR·P（大向量） | ≤5.9× |
| Tree | 小 B | ≤5.9× |
| Two-Phase（新） | 中间 B | ≤2.4× |
| Auto-Gen（新） | 全范围 | ≤1.4× |
3. 1D/2D AllReduce
- Reduce-then-Broadcast 在 WSE 上因 multicast 经常优于 Ring AllReduce
- 2D Broadcast: 利用 multicast 大幅降低延迟 (√P vs P)
- Ring AllReduce 两种 mesh 映射（simple/distance-preserving）性能相同
4. 下界证明
1D Reduce 的 T*(P,B) 通过动态规划 O(P³) 可解。Auto-Gen 在所有输入范围内 ≤1.4× 于下界。
关键数字
- 3.27× 快于 Cerebras vendor Reduce
- 2.56× 快于 vendor AllReduce
- <4% 模型预测误差
- CS-2 @ 850 MHz, ~750K PE, 40GB SRAM
- TR ≈ 2 cycles (WSE-2)
与现有 wiki 的交叉
- Cerebras Wse — 目标硬件平台
- Cerebras Color Mechanism — Color 用于路由配置（论文用 ≤3/5 colors）
- Wse Performance Model — 论文提出的性能模型独立概念页
- Wse Reduce Algorithms — Reduce/AllReduce 算法族独立概念页
- AllReduce Algorithms — MPI 经典归约算法（Ring/RHD 前身）
- Deterministic Execution — WSE 确定性数据流架构使模型精确预测成为可能
- Noc Router Microarchitecture — WSE router 的 5-link 架构与 NoC 理论关联
- Switching Networks — mesh 拓扑下的 collective 算法设计