树形归约Tree collective

时间与空间#

p 为参与者数，m 为向量长度；假设平衡树与可结合的归约操作。

时间复杂度

关键路径 $O(\log p)$ 个层级，每层处理相应消息

辅助空间

常见每节点数据缓冲 $O(m)$，分块流水线状态另计

总归约工作仍需合并所有输入，不能把层数误读为总算术量。朴素 reduce 后广播与分块双树的带宽行为不同；浮点加法的顺序改变也可能改变最后几位结果。