MPI发送/接收程序永远不会完成

Question

我刚刚花了很长时间为别人的问题编写了一篇长答案，但在我发布答案之前就被删除了。我不想浪费这份努力，所以我在这里发布问题和答案。

这不仅是关于发送/接收死锁的标准答案，因为我还发现了一个有趣的半解决方案，它只适用于某些编译器

在并行课程中，我们需要根据主从设计模式进行练习，其中主进程0向所有从进程发送消息，这些从进程将重新将消息发送给它们的右侧和左侧邻居（处理器id +/- 1，除了没有左侧邻居的处理器0和没有右侧邻居的最后一个处理器id）。在将消息转发给邻居之后，从进程向主进程发送确认作业已完成的信息。

这个练习很简单，但我的代码有一个问题，因为我在程序开始时就收到了确认结束消息...我不知道问题出在哪里。我尝试使用fflush，但实际上程序的最后一行应该在接收完成后才写入控制台。

有人有任何想法吗？我对MPI/C概念还很陌生，所以可能我所做的有问题？

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

int main(int argc, char *argv[]){
    int np, myId;
    char send[100], recv[100];

    MPI_Init(&argc, &argv);

    MPI_Comm_size(MPI_COMM_WORLD, &np);
    MPI_Comm_rank(MPI_COMM_WORLD, &myId);

    MPI_Status stat;
    if(myId == 0){
        int t = sprintf(send, "hey!"); //MPI_get_processor_name
        for(int i = 1; i < np; i++){
            printf("send %d => %d\n", myId, i);
            fflush(stdout);
            MPI_Send(send, 50, MPI_CHAR, i, 0, MPI_COMM_WORLD);
        }

        for(int i = 1; i < np; i++){
            MPI_Recv(recv, 50, MPI_CHAR, i, 0, MPI_COMM_WORLD, &stat);
            printf("%s\n", recv);
            fflush(stdout);
        }


    }else{
        if(myId < (np - 1)){
            printf("send %d => %d\n", myId, myId + 1);
            fflush(stdout);
            MPI_Send(send, 50, MPI_CHAR, myId + 1, 0, MPI_COMM_WORLD);
        }

        if(myId > 1){
            printf("Envoie %d => %d\n", myId, myId - 1);
            fflush(stdout);
                    MPI_Send(send, 50, MPI_CHAR, myId - 1, 0, MPI_COMM_WORLD);
        }

        MPI_Recv(send, 50, MPI_CHAR, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &stat); 

        printf("Réception %d <= %d\n", myId, 0);
        fflush(stdout);

        if(myId != (np - 1)){
            MPI_Recv(send, 50, MPI_CHAR, myId + 1, 0, MPI_COMM_WORLD, &stat);
            printf("Receive %d <= %d\n", myId, myId + 1);
            fflush(stdout);
        }

        if(myId != 1){
            MPI_Recv(send, 50, MPI_CHAR, myId - 1, 0, MPI_COMM_WORLD, &stat);
            printf("Receive %d <= %d\n", myId, myId - 1);
            fflush(stdout);
        }

        int t = sprintf(recv, "End for %d.", myId);
        MPI_Send(recv, 50 , MPI_CHAR, 0, 0, MPI_COMM_WORLD); 
    }

    MPI_Finalize();
    return 0;
}

- hcarver

Answer 1

解决方案1

让我们比较所有非0的“从”核心实际上正在做什么，以及您所说的他们应该做什么。

您希望他们这样做：

主进程0向所有从进程发送一条消息，后者将重新将消息发送给其右侧和左侧的邻居（处理器ID +/- 1，除了没有左侧邻居的处理器0和没有右侧邻居的最后一个处理器ID）。在将消息重新传递给邻居之后，从处理器向主处理器发送确认作业已结束的消息。

代码概述：

Send_To_Right_Neighbour();

Send_To_Left_Neighbour();

Receive_From_Master();

Receive_From_Right_Neighbour();

Receive_From_Left_Neighbour();

Send_To_Master();

看到区别了吗？从主节点到邻居节点的消息不再需要先经过从节点。将代码更改为：

Receive_From_Master();

Send_To_Right_Neighbour();

Send_To_Left_Neighbour();

Receive_From_Right_Neighbour();

Receive_From_Left_Neighbour();

Send_To_Master();

我会修复它，然后代码能够完成运行。

出了什么问题

MPI_Send可以是一个阻塞函数——也就是说，调用MPI_Send不会返回，直到另一个进程调用匹配的MPI_Recv（尽管它并不一定是阻塞函数）。在编写代码时应该假定它总是是阻塞函数。

现在让我们想象当你使用>5个进程运行时，非0进程会发生什么。

• 进程1发送给右边的邻居（进程2），并等待那里，直到进程2调用 MPI_Recv。
• 进程2发送给右边的邻居（进程3），并等待那里，直到进程3调用 MPI_Recv。
• 进程3发送给右边的邻居（进程4），并等待那里，直到进程4调用 MPI_Recv。
• ...
• 进程n-2发送给右边的邻居（进程n-1），并等待那里，直到进程n-1调用 MPI_Recv
• 进程n-1没有右邻居，所以继续发送给左邻居，并等待那里，直到进程n-2调用 MPI_Recv。

这永远不会发生，因为进程n-2正在忙于等待进程n-1接收其数据，然后才尝试从n-1接收。这是死锁，两个进程都不会动。

为什么解决方案有效

我已经说过上述解决方案对我有效，但它并不完美。我所做的唯一更改是将接收从进程0移动到第一步--为什么这会影响死锁呢？

答案是它根本不应该影响死锁。我的猜测是编译器足够聪明，意识到每个核心都在发送和接收到相同的邻居，并将左右邻居的单独MPI_Send和MPI_Recv调用组合成MPI_Sendrecv调用。这样可以在同一步骤中向邻居发送和接收，消除死锁问题。以前，从0接收的调用位于向同一邻居发送和接收之间，因此编译器无法将其优化为单个操作。

但我们不想依赖好的编译器--您的代码应该在任何符合标准的编译器上工作--因此我们应该手动修复死锁问题，而不是依赖编译器聪明。

解决方案2

首先，对于您的课程可能已经涵盖或未涵盖的一些注释。

• 进程0将相同的信息发送给所有其他核心。如果您了解 MPI_Bcast，则应使用此函数代替所有这些发送和接收。
• 进程0最后从所有其他核心接收。如果您愿意有多个字符数组用于接收，则可以通过 MPI_Gather 很简单地完成此操作。
• 我真的不理解主进程向每个其他进程发送一些数据，然后每个进程与其相邻的每个进程共享相同的数据的逻辑（这些进程已经被主进程提供了该数据）。如果共享的数据在某种程度上是不同的，或者如果主进程只向一些从属进程发送数据，并且它们必须在自己之间共享该数据，那么对我来说会更有意义。

话虽如此，让我们谈谈如何避免死锁。因此，根本问题在于我们必须确保无论一个进程调用什么 MPI_Send，另一个进程都可以同时调用匹配的 MPI_Recv，而无需等待发送进程执行任何其他操作。问题出现在每个核心同时尝试发送的情况下。

因此，我们可以通过决定信息首先完全沿一个方向移动来解决这个问题。我选择了从左到右。在这种情况下，每个从核需要执行以下操作：

Receive_From_Master();

// Make sure all info is sent from left to right
Send_To_Right_Neighbour();
// Make sure any info is received from left to right
Receive_From_Left_Neighbour();

// Now send all info from right to left
Send_To_Left_Neighbour();
// Make sure any info is received 
Receive_From_Right_Neighbour();

Send_To_Master();

现在发生的是这样的事情：

• 进程2开始发送给进程3
• 进程3开始发送给进程4
• ...
• 进程n-2开始发送给进程n-1
• 进程n-1没有右邻居，所以继续接收来自进程n-2的消息
• 进程n-2完成向进程n-1的发送后，继续从进程n-3接收
• ...
• 进程3完成向进程4的发送并继续从进程2接收。

从左到右发送时也会发生同样的情况，只不过现在进程1没有左邻居可以发送给，因此可以直接从进程2接收。在任一情况下都不会发生死锁。

- hcarver