parallel-processing - MPI 通信复杂度

Question

我正在研究 MPI 中 Quicksort 的并行实现的通信复杂性，我在一本书中发现了类似的内容：

“单个进程从其他 p-1 个进程中收集 p 个常规样本。由于传递的值相对较少，因此消息延迟很可能是这一步的主要术语。因此，收集的通信复杂度为 O(log p)"（O 实际上是一个 theta，p 是处理器的数量）。

对广播消息进行同样的确认。

为什么这些组通信复杂度为 O(log p)？是因为通信是使用某种基于树的层次结构完成的吗？

如果延迟不是主要术语并且正在发送大量数据怎么办？复杂度会是 O(n log (p))，其中 n 是发送数据的大小除以可用带宽吗？

而且，MPI_Send() 和 MPI_Recv() 的通信复杂度如何？

提前致谢！

Answer 1

是的，聚集和分散是使用（取决于特定的 MPI 版本）例如二叉树、超立方体、线性阵列或 2D 方形网格来实现的。可以使用超立方体等来实现全聚集操作。

对于聚集或分散，设 lambda 为延迟，beta 为带宽。然后需要记录 p 个步骤。假设您发送 n 个整数，每个整数用 4 个字节表示。发送它们的时间是

当 n = O(1) 时为 O(log p)，否则为 O(log p + n)。对于广播，所需的时间是

当 n = O(1) 时为 O(log p)，否则为 O(n log p)。

最后，对于像 MPI_Send() 这样的点对点通信，如果您发送 n 个整数，则通信复杂度为 O(n)。当 n = O(1) 时，复杂度显然是 O(1)。