Bellman-Ford算法的MPI并行实现问题求助

需要为Bellman-Ford算法实现MPI并行化，要求在4个不同规模的数据集上计算最短路径并记录每次运行的时间。目前串行版本和OpenMP并行版本均可正常运行，但自行编写的MPI版本虽能运行，计时结果明显不准确，请求修正。

#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include "mpi.h" 
#include <ctime>
 
using namespace std;
 
const int INF = 1e9;
const int Vmax = 10000;
const int Emax = Vmax * (Vmax - 1) / 2;
 
struct edges {
    int u, v, w;
};
 
int j, e = 0;
int peak = 0, start_peak = 1;
edges edge[Emax];
int d[Vmax];
 
int Rank, Numtask, P = peak;
double t1, t2;
 

//главная функция
int main(int argc, char* argv[])
{

    srand(time(NULL));
    setlocale(LC_ALL, "Rus");
    int weight;
    peak = 400;
 
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &Rank);
    MPI_Comm_size(MPI_COMM_WORLD, &Numtask);
 
 
    for (int k = 0; k < 4; k++) {
 
        //filling the graph with values
        for (int i = 0; i < peak; i++) {
            for (j = 0; j < peak; j++)
            {
                weight = rand() % 100;
                if (weight != 0)
                {
                    edge[e].v = i;
                    edge[e].u = j;
                    edge[e].w = weight;
                    e++;
                }
            }
        }
 
        for (int i = 0; i < peak; i++) {
            d[i] = INF;
            d[start_peak] = 0;
        }
 
        if (Rank == 0) {
            t1 = MPI_Wtime();
        }
        MPI_Bcast(&P, 1, MPI_INT, 0, MPI_COMM_WORLD);
        for (int i = Rank + 1; i <= P; i += Numtask) {
            for (int i = 0; i < peak - 1; i++) {
                for (int j = 0; j < e; j++) {
                    if (d[edge[j].v] + edge[j].w < d[edge[j].u]) {
                        d[edge[j].u] = d[edge[j].v] + edge[j].w;
                    }
                }
            }
        }
 
 
        if (Rank == 0) {
            t2 = MPI_Wtime();
 
            cout <<peak <<" Peaks" << endl; 
            printf("wall clock time = %f\n", (t2 - t1));
            
            //printf("", peak, " вершин");
            //printf("wall clock time = %f\n", (t2 - t1));
            
        }
        peak = peak * 2;        
    }
    MPI_Finalize();
    return 0;
}

1. 计时逻辑错误（核心问题） #

• 原代码仅在Rank=0进程启动计时，但未等待其他进程完成计算就直接结束计时，导致记录的是Rank=0自身的执行时间，而非整个并行程序的总运行时间。
• 修正：在计时开始前添加MPI_Barrier(MPI_COMM_WORLD)同步所有进程，计时结束前同样添加屏障等待所有进程完成计算，确保时间统计准确。

2. 图初始化的一致性与内存问题 #

• 所有进程各自生成图，且rand()种子基于time(NULL)，不同进程可能生成不同的图，导致计算结果不一致；同时每次循环e未重置，会导致edge数组越界（多次生成图后元素数量超过Emax）。
• 修正：
  • 仅在Rank=0进程生成图，然后通过MPI_Bcast将所有边广播给其他进程；
  • 每次循环开始时重置e=0，避免数组越界。

3. 并行逻辑错误 #

• 原代码中嵌套循环使用了同名变量i，导致外层循环被覆盖；且并行划分方式完全错误，Bellman-Ford的并行需要基于边的划分，每个进程处理一部分边，每次迭代后同步更新全局距离数组（因为每次松弛需要基于上一轮的全局最新距离）。
• 修正：
  • 将边集划分为Numtask份，每个进程处理自己负责的边子集；
  • 每次迭代后，使用MPI_Allreduce将各进程更新的距离数组合并为全局最优值，确保所有进程拥有一致的距离数据进入下一轮迭代。

4. 无效的广播操作 #

• 原代码广播的P变量初始值为0，未与当前peak关联，属于无效操作。应广播当前的图规模peak和边数e，确保所有进程知晓图的结构。

修正后的示例代码 #

#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include "mpi.h" 
#include <ctime>
 
using namespace std;
 
const int INF = 1e9;
const int Vmax = 10000;
const int Emax = Vmax * (Vmax - 1) / 2;
 
struct edges {
    int u, v, w;
};
 
int j, e = 0;
int peak = 0, start_peak = 1;
edges edge[Emax];
int d[Vmax];
int local_d[Vmax]; // 本地距离数组，用于存储本轮迭代的更新结果
 
int Rank, Numtask;
double t1, t2;
 
int main(int argc, char* argv[])
{
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &Rank);
    MPI_Comm_size(MPI_COMM_WORLD, &Numtask);
 
    // 仅Rank0设置随机种子，保证所有进程生成的图一致
    if (Rank == 0) {
        srand(time(NULL));
        setlocale(LC_ALL, "Rus");
    }
 
    peak = 400;
    for (int k = 0; k < 4; k++) {
        e = 0;
        // Rank0生成图
        if (Rank == 0) {
            for (int i = 0; i < peak; i++) {
                for (j = 0; j < peak; j++) {
                    int weight = rand() % 100;
                    if (weight != 0 && i != j) { // 避免自环
                        edge[e].v = i;
                        edge[e].u = j;
                        edge[e].w = weight;
                        e++;
                    }
                }
            }
        }
 
        // 广播图规模和边数
        MPI_Bcast(&peak, 1, MPI_INT, 0, MPI_COMM_WORLD);
        MPI_Bcast(&e, 1, MPI_INT, 0, MPI_COMM_WORLD);
        // 广播所有边
        MPI_Bcast(edge, e * sizeof(edges), MPI_BYTE, 0, MPI_COMM_WORLD);
 
        // 初始化距离数组
        for (int i = 0; i < peak; i++) {
            d[i] = INF;
        }
        d[start_peak] = 0;
 
        // 同步所有进程，开始计时
        MPI_Barrier(MPI_COMM_WORLD);
        if (Rank == 0) {
            t1 = MPI_Wtime();
        }
 
        // Bellman-Ford并行实现
        for (int iter = 0; iter < peak - 1; iter++) {
            // 复制当前全局距离到本地数组，避免迭代中覆盖
            for (int i = 0; i < peak; i++) {
                local_d[i] = d[i];
            }
 
            // 划分边集，每个进程处理部分边
            int start = (e * Rank) / Numtask;
            int end = (e * (Rank + 1)) / Numtask;
            for (int j = start; j < end; j++) {
                int u = edge[j].u;
                int v = edge[j].v;
                int w = edge[j].w;
                if (d[v] != INF && d[v] + w < local_d[u]) {
                    local_d[u] = d[v] + w;
                }
            }
 
            // 合并所有进程的本地更新，得到全局最优距离
            MPI_Allreduce(local_d, d, peak, MPI_INT, MPI_MIN, MPI_COMM_WORLD);
        }
 
        // 同步所有进程，结束计时
        MPI_Barrier(MPI_COMM_WORLD);
        if (Rank == 0) {
            t2 = MPI_Wtime();
            cout << peak << " Peaks" << endl;
            printf("wall clock time = %f\n", (t2 - t1));
        }
 
        peak *= 2;
    }
 
    MPI_Finalize();
    return 0;
}

额外说明 #

• 并行逻辑采用边划分+全局归约的方式，符合Bellman-Ford算法的并行特性：每次迭代中各进程独立松弛自己负责的边，再通过MPI_Allreduce同步得到全局最新的最短距离；
• 使用MPI_Barrier确保所有进程同时开始和结束计时，保证时间统计的准确性；
• 仅Rank0生成图并广播，避免多进程生成不一致的图，同时减少冗余计算。

内容的提问来源于stack exchange，提问作者MLLL