使用 OpenMPI 的 BFS

Question

我正在尝试使用 OpenMPI（如果相关，则在 C++ 上）实现广度优先搜索，我得到了几乎所有东西运行，除了最后。不知道when/how停止执行。

我使用二维数组来跟踪图中的所有边，如下所示：

graph[start][finish] - there is an edge from vertex start to vertex finish

我目前的算法是：

根距离为0，其他距离为INT_MAX
根向所有邻居发送距离并停止
每个其他节点接收一个距离
如果新距离比当前距离更好（更小），则更新距离并将新距离发送给所有其他邻居
从第 3 步开始永远重复

我真的不知道如何更改第 5 步以使一切停止。我在一个小图上进行测试（这样我就可以很容易地了解发生了什么）并且它很快就会停止，这意味着所有非根进程都卡在了第 3 步，因为每个最小距离都已找到并且没有进程正在发送更新。

我没有包含我的代码，因为算法应该很容易理解，而且我的问题与算法的关系比与代码本身的关系更大。

Answer 1

我找到的解决方案是在 4 和 5 之间添加一个中间步骤，将更新从进程发送到根。

每次迭代后，进程p都会向root发送一条消息，告诉它本次迭代是否更新了距离。当所有进程"report" 表示他们还没有更新距离时，他们将收到一条停止消息（来自根）。

所以要更改伪代码：

if (rank == 0) // root
{
    distance = 0;
    for each neighbor
        send distance

    vector<bool> status(no_processes - 1, true)
    while (status contains one true value)
        receive update from one process
        update status

    // status is full of false
    send all STOP
}
else
{
    distance = INT_MAX;
    while (true)
    {
        receive message

        if STOP
            stop execution

        status = false;
        if (recv_distance + 1 < distance)
        {
            status = true

            distance = recv_distance + 1;

            for each neighbor
                send distance
        }

        send status to root
    }
}

使用 OpenMPI 的 BFS

BFS with OpenMPI

c++

graph-theory

breadth-first-search

openmpi