Optimization of Collective Reduction Operations
Author: Rolf Rabenseifner (HLRS, University of Stuttgart) | Venue: ICCS 2004, LNCS 3036 | PDF: Rabenseifner_Collective_Reduction_Operations_2004.pdf
一句话总结
针对 MPI 中 Allreduce/Reduce 占 >40% MPI 时间 且 25% 运行非 2 的幂进程数 的现状，Rabenseifner 给出 五种带宽/延迟优化算法（二叉树、recursive doubling、halving & doubling、binary blocks、ring），按 (p, 向量长度) 自适应选择；长向量相对当年 vendor 实现加速 3×–100×，RHD 已纳入 MPICH-2。
核心贡献
- 统一 α+nβ 代价模型 比较五种协议（双向/单向因子 f_α, f_β）
- Recursive halving & doubling：reduce-scatter + allgather，长向量 ~2nβ 级带宽；非 POT 预处理
- Binary blocks：非 POT 进程数块分解，降低 RHD 额外开销
- Ring：pairwise reduce-scatter + ring allgather，中等非 POT 长向量
- 运行时算法选择 heatmap（Cray T3E、IBM SP 实测）
关键数字
| 指标 | 值 |
|---|---|
| MPI 时间 in Allreduce+Reduce | 40.7%（T3E profiling） |
| 非 POT 进程占比 | 25% runtime |
| vs vendor (long vector) | 3× IBM sum — 100× Cray maxloc |
| IBM SP bandwidth gain | 1.5–5× (8 KB–8 MB) |
| Ring Allreduce steps | 2(p−1) |
| RHD (POT) bandwidth term | ≈ 2nβ |
与 wiki 交叉引用
- AllReduce Algorithms — 五算法机制与选择
- WSE Reduce Algorithms — Ring / reduce-scatter+allgather 在 WSE 上的扩展
- Linear and Ring Topology — Ring AllGather 逻辑环
- Interconnection Network Cost Model — α/β 通信代价
- Collective-Capable NoC — 硬件归约 offload
- Near-Optimal Wafer-Scale Reduce — 2024 WSE 归约算法系统研究
Citations
[1] Rabenseifner_Collective_Reduction_Operations_2004.pdf — Rabenseifner (2004)