mpi - MPI 障碍的复杂性

Question

MPI障碍的时间复杂度是多少？它们是否适用于大量内核（>> 10k）？

Answer 1

屏障复杂性是高度特定于实现的。它可能是线性的，可能是对数的，或者可能更好或更糟。一些架构为一些集体操作提供了专用网络，例如 IBM 的 Blue Gene 有一个专用的全局中断网络，它允许非常快速的MPI_BARRIER实现，具有几乎恒定的复杂性，但只有在执行时才能完成MPI_COMM_WORLD。

Answer 2

虽然 Hristo Iliev 是正确的，但您可以假设在这些尺度上使用的任何合理的 MPI 实现在集体操作上都具有对数复杂性。是的，这确实可以扩展 >> 10k 个内核。不同的现代实现之间仍然可能存在显着因素。同样在这个规模上，OS 噪声会对集体操作产生非常显着的影响（参见例如 [ 1 ]）。

Answer 3

复杂性应该不会比 O(log N) 差，因为可以将屏障实现为单个单词的 allreduce，并且 allreduce 的规模为 O(log N)。