來自未知來源的MPI異步廣播

Question

我有一個C項目，有n個處理器在一種樹型搜索上工作。在程序的任何給定時間，這些進程中的任何一個都可能會感興趣並希望將其異步發送給所有其他處理器。

如何在其他進程上偵聽新消息，而不必在每個循環迭代中遍歷所有可能的發送方？

我已經閱讀了關於這個的其他問題，例如這個（MPI - Asynchronous Broadcast/Gather），但是，我迄今爲止所見到的所有或者不處理不可預知的發送者或者通過每個可能的發送者循環，而我並不真正喜歡。

EDIT澄清：

所找到的值發送到根秩和分發從那裏不在選項。如果我沒有這種條件，祖蘭的答案就會奏效，所以對於其他人來說，這可能會有所幫助。 在我的情況下，它可以（也是最肯定的）會發生，不同的隊伍找到他們需要分享多次的東西（這意味着競爭條件也可能發生）。

Answer 1

經過大量的試驗和錯誤（和其他反饋）後，我發現最高性能的解決方案使用異步廣播。

我第一種方法是通過使用多個非阻塞MPI_Isend（）調用來分發數據，只有一個單一的MPI_Irecv（）調用（任意源）以定期接收數據彼得魯杜米特的回答啓發。這種方法結果非常緩慢，因爲非阻塞MPI_ISend（）調用必須由發送方在每個創建的MPI_Request句柄上使用MPI_Test（）進行檢查。 原因是，異步操作在後臺工作的意義上並不是真正的異步操作，而是必須定期檢查。

在我的情況下，問題還表明新的解決方案可以（而且將會）被多次發現的可能性，這導致了現有的開放式MPI_Request句柄帶來的許多管理問題，這些問題必須等待或管理，否則。

我的第二種方法正在使用Zulan提出的中央傳播者。這種方法在消息不多的情況下非常快，但是當同時存在許多找到的解決方案時，根級排除堵塞，在特殊情況下速度非常緩慢。最重要的是，根級別沒有其他人那麼快（這是可以預料的），這導致了我的情況下整體速度較慢。

我的第三個也是最後一個方法正在使用多個非阻塞MPI_Ibcast（）調用，每個可能發送消息的可能的等級之一。例如這將意味着，在與3個不同的等級的情況下

• 秩0具有與根1兩個開口MPI_Ibcasts和2
• 秩1具有根0兩個開放MPI_Ibcasts和2
• 秩2有兩個開放的MPI_Ibcasts，其中包含root 0和1

當某個等級找到解決方案時，它會發布最後一個必需的MPI_Ibcast作爲根。起初，這似乎與方法1相似，但是，在這種情況下，發件人始終只需監視一個請求句柄（來自最終MPI_Ibcast的句柄），並使用MPI_Test（）定期檢查它。其他隊伍總是有相同數量的開放廣播（即世界大小減1），它們可以存儲在數組中並用MPI_Testany（）進行檢查。 然而，這種方法的困難在於，每個開放廣播都必須在自己的傳播者上進行操作，基本上需要儘可能多的傳播者。

因此，我的發現是第二種方法有時是可以接受的，使它成爲一個快速和可行的選項，當沒有很多消息時。這是最容易處理和實施的。第三種方法在負載較重時速度更快，並且使我的程序終止非常容易，因爲始終存在已知數量的開放連接。與其他實現相比，這是最難實施和使用最多的內存。 （我不知道原因，但它似乎與廣播的緩衝區管理和可能的附加通信器有關。） 最後，我不能強調第一種方法一開始似乎很容易，但是當你真的想要跟蹤每一個請求，那麼不幸的是，它很難管理和緩慢。

Answer 2

您可以選擇根級別，並將異步發送與源自此根目錄的異步廣播組合在一起。下面是一個小例子：

#include <stdio.h> 
#include <mpi.h> 

int main() 
{ 
    int size, rank; 
    MPI_Init(NULL, NULL); 
    MPI_Comm_size(MPI_COMM_WORLD, &size); 
    MPI_Comm_rank(MPI_COMM_WORLD, &rank); 

    const int root = 0; 
    const int found_tag = 42; 
    const long long chunk = 100000ll; 
    const long long target = 134861523ll; 

    MPI_Request found_request; 
    long long found_item; 
    if (rank == root) { 
     MPI_Irecv(&found_item, 1, MPI_LONG_LONG, MPI_ANY_SOURCE, found_tag, MPI_COMM_WORLD, &found_request); 
    } else { 
     MPI_Ibcast(&found_item, 1, MPI_LONG_LONG, root, MPI_COMM_WORLD, &found_request); 
    } 

    for (long long my_number = rank;; my_number += size) { 
     if (my_number == target) { 
      found_item = my_number; 
      printf("I found it: %d, %lld\n", rank, found_item); 
      // We don't stop here, we will continue until the root tells us to stop 
      // This also works if we are the root 
      MPI_Send(&my_number, 1, MPI_LONG_LONG, root, found_tag, MPI_COMM_WORLD); 
     } 
     // Avoid checking MPI_Test too often. 
     if ((1 + (my_number/size)) % chunk == 0) { 
      if (rank == root) { 
       int found = 0; 
       MPI_Test(&found_request, &found, MPI_STATUS_IGNORE); 
       if (found) { 
        printf("Someone told me that he found it: %d, %lld\n", rank, found_item); 
        MPI_Request bcast_request; 
        MPI_Ibcast(&found_item, 1, MPI_LONG_LONG, root, MPI_COMM_WORLD, &bcast_request); 
        MPI_Wait(&bcast_request, MPI_STATUS_IGNORE); 
        break; 
       } 
      } else { 
       int found = 0; 
       MPI_Test(&found_request, &found, MPI_STATUS_IGNORE); 
       if (found) { 
        break; 
       } 
      } 
     } 
    } 
    printf("%d, %lld\n", rank, found_item); 
    MPI_Finalize(); 
} 

此代碼假定您只能找到一個確切的數字 - 一次。查找多個號碼將需要一些額外的代碼。

正如你所說，你不能發佈廣播與未知的發件人。現在你可以發佈一個MPI_Allreduce（或者甚至MPI_Allgather） - 之後所有的隊伍都會知道發現的價值。但是，您不能只發布一次異步版本 - 因爲在發佈後您無法更改該值。

Answer 3

首先，其他集體原語的MPI廣播操作需要的所有進程的參與，這意味着，如果你想使用集體操作，需要所有進程進入聲明。 這是因爲MPI廣播原始做發送方和在同一個集體聲明接收： Corresponding Receive Routine of MPI_Bcast

這種抽象通常允許集體的非幼稚的實現，所有的進程實際上可以有助於廣播。這很好地解釋了這裏：http://mpitutorial.com/tutorials/mpi-broadcast-and-collective-communication/

如果你想異步通知每個找到的值，因爲它可能以某種方式對你的算法有貢獻，所以用異步發送循環每個進程可能是你最好的選擇，特別是如果這些值很小。

在你的問題中，你似乎只關心使用循環來收聽消息。請注意，您可以通過使用MPI_ANY_SOURCE作爲探測和接收消息的源參數來避免接收循環。這避免了循環，但只探頭/接收一個消息，所以這取決於你想要做什麼，你可能要循環，直到有在隊列中沒有更多的消息，或者有一些更復雜的，以防止大量預防的進度消息的處理。

Answer 4

您可能會在定期出現的同步點上發送值。不要立即發送找到的號碼，您可以延遲交付並在本地收集號碼，直到出現下一個同步點。那時，你一次發出一堆數字。當你每次發送一堆文件時，可能需要花費一些開銷來創建同步點。

可以使用全部創建同步點。每個流程都會將其本地收集的數字發送給所有其他人。全聚合就像一個障礙，之後你可以做你的實際廣播。在此障礙之後，所有流程都知道廣播將有多大以及它們包含多少項目。

Allgather也只是發送號碼，所以爲什麼不直接發送你的號碼？因爲allgather操作可能相對「空白」（如果你知道我的意思......），而其他進程在發生時不會知道thime的要點。如果您選擇固定同步點，則每個人都知道何時進行同步，並可能有多個號碼要傳輸。

另一種選擇可能是查看MPI-3的RMA（遠程內存操作）。它們也被稱爲「單向」，因爲接收器不需要調用相應的接收。所以你不需要知道根就可以接收廣播的數據。也許你可以用這些操作構建一個智能的put/get方案。

我還沒有找到一個很好的解決方案，仍然有類似的問題。到目前爲止，我的想法是：在每個進程中爲每個可能的廣播根啓動廣播監聽器（=線程）。當然，這會產生很大的開銷：您需要一個線程，並且他們必須爲每個bcast源使用一個自己的MPI_Communicator。聽衆將接收到的數據放在一個公共消息隊列中，然後你就可以走了。