MPI通信复杂度

Question

我正在研究MPI快速排序的并行实现的通信复杂度，并在一本书中发现了以下内容：

“单个进程从其他p-1个进程中收集p个常规样本。由于传递的值较少，消息延迟可能是这一步骤的主导项。因此，聚集的通信复杂性为O（log p）”（O实际上是theta，p是处理器数量）。

广播信息也有相同的说法。

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

如果延迟不是主导项，并且有大量数据被发送怎么办？复杂度是否为O(n log (p))��其中n为发送数据的大小除以可用带宽？

那么，MPI_Send()和MPI_Recv()的通信复杂度又如何呢？

谢谢！

- dx_mrt

---

p的值是多少？ - suszterpatt

哦，抱歉，p是处理器的数量。 - dx_mrt

Answer 1

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

对于收集或分散，假设lambda是延迟，beta是带宽。需要进行log p步骤。假设你正在发送表示每个整数使用4个字节的n个整数。发送它们的时间为

当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)。

- Massimo Cafaro