MPI通信複雜

Question

我學習的MPI並行實現快速排序的通信複雜性我發現像這樣的一本書：

「一個單一的過程中從每個收集p定期樣本由於相對較少的值被傳遞，消息延遲可能是這一步的主要條件，因此該收集的通信複雜度爲O（log p）「（O實際上是θ和p是處理器的數量）。

對廣播消息做出同樣的肯定。

爲什麼這些組的通信複雜度爲O（log p）？是因爲通信是使用某種基於樹的層次結構完成的嗎？

如果延遲不是占主導地位的術語，並且發送了大量數據？複雜度是否爲O（n log（p）），其中n是發送數據的大小除以可用帶寬？

而且，MPI_Send（）和MPI_Recv（）的通信複雜度如何？

在此先感謝！

Answer 1

是的，收集和分散是使用（取決於特定的MPI版本）實現的，例如二叉樹，超立方體，線性陣列或2D方形網格。全聚集操作可以使用超立方體等來實現。

對於收集或分散，讓lambda爲延遲並測試帶寬。然後記錄p步驟是必需的。假設你正在發送n個整數，每個整數用4個字節表示。送他們的時間是

這是爲O（log P），當n = O（1）和爲O（log P + n）的說明。 對於廣播，所需要的時間是

其是爲O（log P），當n = O（1）和O（N日誌p）的說明。

最後，對於像MPI_Send（）這樣的點對點通信，如果發送n個整數，通信複雜度爲O（n）。當n = 0（1）時，複雜度顯然是O（1）。