最优的非流水线化 Reduce-scatter 和 Allreduce 算法及其在全连接通信中的应用

《ACM Transactions on Parallel Computing》：Optimal, Non-pipelined Reduce-scatter and Allreduce Algorithms with an Application to All-to-all Communication

reduce-scatter算法通过?log2p?轮通信实现最优性能，结合allgather算法构建高效allreduce方案，提出基于循环通信模式的实现方法，适用于MPI库的Reduce_scatter_block、Allreduce等操作，并与Bruck等人算法进行性能比较。

　　

摘要

“Reduce-Scatter”集体操作中，网络中的

个处理器共同将

个输入向量合并为一个结果向量，该结果向量被分割成

个部分并分配给各个处理器。这一操作本身非常重要，同时也是其他集体操作的基础。我们提出了一种简单却非平凡的算法，能够在?log?p?轮通信中最优地解决该问题：每个处理器恰好发送、接收和处理

- 1

个向量元素块，前提是二进制归约操作是可交换的。我们将这种算法与另一个同样简单且广为人知的“Allgather”算法结合起来，从而得到一个适用于“Allreduce”集体操作的算法，在该算法中结果向量会被复制到所有处理器上。所使用的通信模式是一个简单的、遵循?log?p?规则的结构化循环图（circulant graph），这种图在其他场景也有应用。循环图中跳过序列（skip sequence）的简单要求为通信模式的选择提供了灵活性，这对于实际实现非常有益。这些算法可以很容易地被应用于MPI标准中规定的集体操作MPI_Reduce_scatter_block、MPI_Reduce_scatter_block和MPI_Allreduce。为了完整性，我们还提供了一种?log?p?轮通信最优的“Allreduce”算法，适用于较小的输入向量。最后，我们发现“Reduce-Scatter”算法可以作为模板，用于实现一种通信量更小的全节点通信（all-to-all communication）；对于某些

值，其通信量甚至小于Bruck等人（1997年）提出的著名算法，可用于实现集体操作MPI_Alltoall。我们在一个小型集群上进行了实验验证，结果表明这些算法的性能优于或至少与其他已实现的MPI库算法相当。