parallel-processing - MPI 通信复杂度

Question

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

"A single process gathers p regular samples from each of the other p-1 processes. Since relatively few values are being passed, message latency is likely to be the dominant term of this step. Hence the communication complexity of the gather is O(log p)" (O is actually a theta and p is the number of processors).

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

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

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

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

提前致谢!

Answer 1

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

对于聚集或分散，让 lambda 为延迟，而 beta 为带宽。然后需要log 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)。