c - 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;
}

Answer 1

解决方案1

让我们将所有非0，“从属”内核的实际作用与您说的应该做的事情进行比较。

您希望他们做什么:

主进程0向其所有从属发送一条消息，该从属将重新发送消息至其左右邻居(处理器ID +/- 1，除了没有左邻居的处理器0和最后一个没有ID的处理器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最后从所有其他核心接收。如果您愿意接收多个char数组，则可以使用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进行接收。在两种情况下都不会出现死锁。