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没有正确的邻居.在将消息重新传递给邻居之后,从属处理器向主节点发送作业结束的确认.

代码大纲:

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数组,则可以使用a进行非常简单的操作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接收.在任何一种情况下都不会出现死锁.