MPI障礙的複雜性

Question

MPI障礙的時間複雜度是多少？它們是否可以擴展大量內核（>> 10k）？

Answer 1

屏障複雜度爲高度實現特定。它可以是線性的，可以是對數的，也可以是更好或更差。一些體系結構爲一些集體操作提供專用網絡，例如， IBM的Blue Gene有一個專門的全局中斷網絡，它允許以非常快的MPI_BARRIER實現幾乎不變的複雜性，但只有在MPI_COMM_WORLD上執行時纔是如此。

Answer 2

儘管Hristo Iliev是正確的，但您可以假設在這些等級上使用的任何合理的MPI實現在集體操作上具有對數複雜度。是的，這確實規模>> 10k核心。不同的現代實現之間仍然存在一個戲劇性的因素。同樣在這種規模下，操作系統噪聲可能對集體操作產生非常重要的影響（參見[1]）。

Answer 3

複雜性應該不會比O（log N）差，因爲可以通過一個單詞實現屏障作爲allreduce，並且allreduce按比例縮放爲O（log N）。