来自未知来源的 MPI 异步广播

Question

我有一个 C 项目，它有 n 个处理器在进行一种树搜索。在程序的任何给定时间，这些进程中的任何一个都可能发现一些感兴趣的东西，并希望将其异步发送给所有其他处理器。

我如何才能在其他进程上侦听新消息而不必在每次循环迭代中遍历所有可能的发件人？

我已经阅读了关于此的其他问题，例如这个 (MPI - Asynchronous Broadcast/Gather)，但是，到目前为止我所看到的要么不处理不可预测的发件人，要么循环遍历每个可能的发件人，我不太喜欢。

编辑说明：

将找到的值发送到根等级并从那里分配它是不可能的。如果我没有那个条件，祖兰的回答会起作用，所以对其他人来说这可能会有所帮助。在我的例子中，它可能（而且肯定会）发生不同的等级发现他们需要多次共享的东西（这意味着竞争条件也可能发生）。

Answer 1

您可以选择根等级并将异步发送与源自该根的异步广播结合起来。这是一个小例子：

#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();
}

此代码假设您只找到一个数字 - 一次。查找多个号码需要一些额外的代码。

如您所述，您无法 post 与未知发件人进行广播。现在您可以 post 和 MPI_Allreduce（甚至 MPI_Allgather）——之后所有等级都会知道找到的值。但是，您不能只 post 一次异步 - 因为您无法在 post 编辑后更改该值。

Answer 2

首先，与其他集体原语一样，MPI广播操作需要所有进程参与，也就是说如果要使用集体操作，需要所有进程都进入语句。这是因为 MPI 广播原语在同一个集体声明中进行发送和接收： Corresponding Receive Routine of MPI_Bcast

这种抽象通常允许集体的非天真实现，所有进程实际上都可以参与广播。这在这里得到了很好的解释：http://mpitutorial.com/tutorials/mpi-broadcast-and-collective-communication/

如果您希望收到关于找到的每个值的异步通知，因为它可能以某种方式对您的算法有所贡献，那么使用异步发送在每个进程上循环可能是您最好的选择，尤其是当这些值较小时.

在您的问题中，您似乎只关心使用循环来收听消息。请注意，您可以通过使用 MPI_ANY_SOURCE 作为探测和接收消息的源参数来避免接收循环。这避免了循环，但只有 probe/receive 一条消息，因此根据你想做什么，你可能想要循环直到队列中没有更多消息，或者有更复杂的东西来防止大量消息阻止进度一个过程。

Answer 3

您可以在周期性出现的同步点发送值。您可以延迟发送并在本地收集号码，直到下一个同步点出现，而不是立即发送找到的号码。那时，您立即发送了一堆数字。当您一次发送一堆时，创建同步点可能需要一些开销。

使用all可以创建同步点。每个进程将他本地收集的号码发送给所有其他进程。 allgather 就像一个障碍，之后你可以进行实际的广播。在这个障碍之后，所有进程都知道广播的大小以及它们包含多少项。

Allgather 也只是发送号码，所以为什么不直接发送您的号码呢？因为 allgather 操作可能相对 "empty"（如果你知道我的意思......）并且其他进程在它发生时不会知道时间点。如果选择固定的同步点，大家都知道什么时候同步，可能不止一个号要转

另一种选择可能是查看 MPI-3 的 RMA（远程内存操作）。它们也被称为 "one-sided" 因为接收方不需要调用相应的接收。所以你不需要知道根来接收广播数据。也许您可以使用这些操作构建智能 put/get 方案。

我还没有为自己找到好的解决方案，仍然有类似的问题。到目前为止我最好的想法：在每个进程中为每个可能的广播根启动一个广播监听器（=线程）。当然，这会产生很大的开销：您需要一个线程，并且他们必须为每个广播源使用自己的 MPI_Communicator。侦听器将接收到的数据放入公共消息队列中，然后就可以了。

Answer 4

经过大量试验和错误（以及其他反馈）后，我发现性能最高的解决方案是使用异步广播。

我的第一种方法 的灵感来自于 Petru 的回答，他使用多个非阻塞 MPI_Isend() 调用来分发数据并且只有一个 MPI_Irecv() 调用（与任何来源）定期接收数据。这种方法非常慢，因为非阻塞 MPI_ISend() 调用必须由发件人使用 MPI_Test() 在创建的每个 MPI_Request 句柄上进行检查。这样做的原因是，异步操作在后台工作的意义上并不是真正的异步，而是必须定期检查。

在我的案例中，这个问题还表明可以（并且将会）多次找到新解决方案的可能性，这导致了现有的许多管理问题，开放的 MPI_Request 句柄，必须是等待或以其他方式管理。

我的第二种方法是使用 Zulan 提出的中央通信器。这种方法在消息不多的时候非常快，但是当同时有很多找到的解时，root rank 就会堵塞，在特殊情况下会很慢。最重要的是，根排名不再像其他排名那么快（这是可以预料的），这导致我的程序整体变慢。

我的第三种也是最后一种方法 是使用多个非阻塞 MPI_Ibcast() 调用，一个用于可以发送消息的每个可能等级。例如，这意味着在具有 3 个不同等级的情况下

rank 0 有两个开放的 MPI_Ibcasts 与根 1 和 2
等级 1 有两个开放的 MPI_Ibcasts，根为 0 和 2
等级 2 有两个开放的 MPI_Ibcasts，根为 0 和 1

当排名随后找到解决方案时，它会发布最后一个必要的 MPI_Ibcast 并将其自身作为根。起初这似乎与方法一相似，但是，在这种情况下，发送方总是只需要监视一个请求句柄（来自最终 MPI_Ibcast 的请求句柄）并使用 MPI_Test() 定期检查它.其他行列总是有相同数量的开放广播（即世界大小-1），可以将其存储在数组中并使用MPI_Testany() 进行检查。然而，这种方法的困难在于，每个开放广播都必须在它自己的通信器上运行，本质上需要与等级一样多的通信器。

因此，我的发现 第二种方法有时是可以接受的，当消息不多时，这是一个快速可行的选择。这是最容易处理和实施的。第三种方法在较重的负载下速度更快，并且也使我的程序终止非常容易，因为始终存在已知数量的打开连接。它是最难实现的，也是最耗时的，并且比其他实现消耗了更多的内存。（我不知道这是什么原因，但它似乎与广播的缓冲区管理以及可能的额外通信器有关。）最后，我怎么强调都不为过，第一种方法一开始看起来很简单，但是当你真的想跟踪每一个请求时，那么它就很难管理，而且速度也很慢，不幸的是。

来自未知来源的 MPI 异步广播

MPI asynchronous broadcast from unknown source

c

asynchronous

communication

broadcast

mpi