MPI并行NP-Complete背包问题中rank值异常输出的原因及解决求助

问题描述 #

我正在用MPI开发C语言版NP完全背包问题的并行解决方案，运行代码时发现一个异常：第一个if(rank == 0)分支末尾的printf语句输出的rank值是14，而非预期的0，但该语句明明处于要求rank为0的条件分支内。使用mpirun -np 1 code单进程运行时也出现此问题，期望rank 0仅执行指定代码，不会出现rank值被篡改的情况。相关代码如下：

//Parallel Code using MPI of the NP-Complete Knapsack problem

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

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main(int argc, char **argv) {
    // Initialize MPI
    MPI_Init(&argc, &argv);
    int numprocs, rank;
    MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Status status;

    // Declare variables
    double start_time, end_time;
    int n = 3; // number of items
    int W = 10; // knapsack capacity
    int weights[] = {4, 7, 3};// weight of each item
    int profits[] = {4, 5, 7}; // profit of each item

    int weightsbfr[] = {}; // weight buffer
    int profitsbfr[] = {}; // profit buffer

    int chunk_size = 0; // number of items to be processed by each process

    // Calculate chunk size
    chunk_size = n / numprocs;
    if (chunk_size * numprocs < n) {
        chunk_size++; // add 1 to chunk_size to account for the remainder
    }

    // best solution found so far
    int best_weights[] = {}; // weight of the best solution found so far
    int best_profits[] = {}; // profit of the best solution found so far

    int local_final_weight = 0; // weight of the local solution of the current process
    int local_final_profit = 0; // profit of the local solution of the current process

    //final summed values for profit and weight
    int global_final_profit = 0;
    int global_final_weight = 0;

    //Local variables
    int local_weights[] = {}; // local solution of the current process
    int local_profits[] = {}; // profit of the local solution of the current process

    weightsbfr = (int*) malloc(chunk_size * sizeof(int));
    profitsbfr = (int*) malloc(chunk_size * sizeof(int));


    if (rank == 0) {
        printf("Rank: %d\n", rank);
        start_time = MPI_Wtime();
        // send weights and profits to all processes
        int i;
        for (i = 1; i < numprocs; i++) {
            //Split up weights and profits into chunks for each process
            int j;
            for (j = 1; j < chunk_size; j++) { 
                weightsbfr[j] = weights[i * chunk_size + j]; //split weights
                profitsbfr[j] = profits[i * chunk_size + j]; //split profits
            }

            MPI_Send(weightsbfr, 1, MPI_INT, i, 0, MPI_COMM_WORLD); //send weights
            MPI_Send(profitsbfr, 1, MPI_INT, i, 0, MPI_COMM_WORLD); //send profits
        }
        //Copy weights and profits into local variables
        int g;
        for (g = 0; g < chunk_size; g++) {
            local_weights[g] = weights[g];
            local_profits[g] = profits[g];
        }
        //Calculate local solution
        int w;
        int K[n + 1][W + 1];

        // Build table K[][] in bottom up manner
        for (i = 0; i <= n; i++) {
            for (w = 0; w <= W; w++) {
                if (i == 0 || w == 0)
                    K[i][w] = 0;
                else if (weights[i - 1] <= w)
                    K[i][w] = max(profits[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w]);
                else
                    K[i][w] = K[i - 1][w];
            }
        }
        //Copy local solution into local variables
        int k;
        for (k = 0; k <= n; k++) {
            for (w = 0; w <= W; w++) {
                local_weights[k] = K[k][w];
                local_profits[k] = K[k][w];
            }
        }
        //Copy local solution into global variables
        global_final_weight = 0;
        global_final_profit = 0;
        for (k = 0; k <= n; k++) {
            best_weights[k] = local_weights[k];
            best_profits[k] = local_profits[k];
            //add up weight and profit of local solution
            global_final_weight += local_weights[k];
            global_final_profit += local_profits[k];
        }
        printf("Initial solution: %d, %d\n", global_final_weight, global_final_profit);
        //print best_weights and best_profits
        printf("Best weights: [");
        for (k = 0; k <= n; k++) {
            printf("%d ", best_weights[k]);
        }
        printf("]\n");
        printf("Rank at end of first if statement: %d\n", rank);
    }
    else {
        MPI_Recv(weightsbfr, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE); //receive weights
        MPI_Recv(profitsbfr, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE); //receive profits
        //Copy weights and profits into local variables
        int h;
        for (h = 0; h < chunk_size; h++) {
            local_weights[h] = weightsbfr[h];
            local_profits[h] = profitsbfr[h];
        }
        //Calculate local solution
        int z, w;
        int K[n + 1][W + 1];
        for (z = 0; z <= n; z++) { //for each item
            for (w = 0; w <= W; w++) { //for each weight
                if (z == 0 || w == 0) //if no items or no weight
                    K[z][w] = 0; //set value to 0
                else if (local_weights[z - 1] <= w) //if weight of item is less than or equal to current weight
                    K[z][w] = max(local_profits[z - 1] + K[z - 1][w - local_weights[z - 1]], K[z - 1][w]); //set value to max of profit of item + value of item at (i-1, w-weight of item) and value of item at (i-1, w)
                else
                    K[z][w] = K[z - 1][w]; //set value to value of item at (i-1, w)
            }
        }
        //Copy local solution into local variables
        int k;
        for (k = 0; k <= n; k++) {
            for (w = 0; w <= W; w++) {
                local_weights[k] = K[k][w]; //this might be an issue copying a 2D array into a 1D array
                local_profits[k] = K[k][w];
            }
        }
        //calculate local final profit and weight
        //sum contents of local_weights and local_profits
        local_final_profit = 0;
        local_final_weight = 0;
        for (h = 0; h < n; h++) {
            local_final_profit += local_profits[h];
            local_final_weight += local_weights[h];
        }

        //Send local solution to process 0
        MPI_Send(local_weights, 1, MPI_INT, 0, 0, MPI_COMM_WORLD); //send weights
        MPI_Send(local_profits, 1, MPI_INT, 0, 0, MPI_COMM_WORLD); //send profits
        MPI_Send(&local_final_weight, 1, MPI_INT, 0, 0, MPI_COMM_WORLD); //send final weight
        MPI_Send(&local_final_profit, 1, MPI_INT, 0, 0, MPI_COMM_WORLD); //send final profit
        printf("Process %d sent solution to process 0.\n", rank);
    }
    printf("Rank: %d\n", rank);
    if (rank == 0) {
        printf("inside loop");
        int x;
        printf("numprocs: %d\n", numprocs);
        for(x = 1; x < numprocs; x++) {
            printf("Receiving solution from process %d...\n", x);
            MPI_Recv(local_weights, 1, MPI_INT, x, 0, MPI_COMM_WORLD, &status); //receive weights
            MPI_Recv(local_profits, 1, MPI_INT, x, 0, MPI_COMM_WORLD, &status); //receive profits
            MPI_Recv(&local_final_weight, 1, MPI_INT, x, 0, MPI_COMM_WORLD, &status); //receive final weight
            MPI_Recv(&local_final_profit, 1, MPI_INT, x, 0, MPI_COMM_WORLD, &status); //receive final profit
            //Compare local solution to best solution
            if (local_final_profit > global_final_profit) {
                printf("New best solution found!\n");
                printf("New best profit total: %d\n", local_final_profit);
                printf("New best weight total: %d\n", local_final_weight);
                printf("Previous best profit total: %d\n", global_final_profit);
                printf("Previous best weight total: %d\n", global_final_weight);
                int l;
                for (l = 0; l <= n; l++) { //for each item
                    best_weights[l] = local_weights[l];
                    best_profits[l] = local_profits[l];
                }
            }
        }
        end_time = MPI_Wtime();
        printf("Time taken: %f\n", end_time - start_time);
        printf("Best profit total: %d\n", global_final_profit);
        printf("Best weight total: %d\n", global_final_weight);
        //Print arrays of best weights and profits

        //printf("Item weights: %d\n", &best_weights);
        //printf("Item values: %d\n", &best_profits);
    }
    /*
    free(weights);
    free(profits);
    free(weightsbfr);
    free(profitsbfr);
    free(best_weights);
    free(best_profits);
    free(local_weights);
    free(local_profits);
    */
    printf("Process %d finished.\n", rank);
    MPI_Finalize();
    return 0;
}

原因分析 #

• 空数组导致内存越界：代码中定义了多个长度为0的空数组（如local_weights[] = {}、best_weights[] = {}），后续对这些数组进行下标赋值操作时，会直接越界写入栈内存，覆盖了相邻的rank变量，导致其值被篡改。
• 数组拷贝逻辑越界：rank 0分支中，将二维DP表K的内容循环拷贝到一维数组时，循环范围远超数组实际容量，进一步加剧了内存越界，直接破坏了rank变量的存储。
• MPI通信参数不匹配：发送/接收的元素数量与实际数组大小不符（比如只发送1个元素但准备了chunk_size个），虽在单进程时不触发通信错误，但内存越界是核心问题。

解决方法 #

1. 正确分配动态数组 #

将所有空数组改为动态分配内存，根据实际需求指定大小：

// 替换原空数组定义为指针
int* weightsbfr = NULL;
int* profitsbfr = NULL;
int* best_weights = NULL;
int* best_profits = NULL;
int* local_weights = NULL;
int* local_profits = NULL;

// 计算chunk_size后分配对应内存
chunk_size = n / numprocs;
if (chunk_size * numprocs < n) chunk_size++;
weightsbfr = malloc(chunk_size * sizeof(int));
profitsbfr = malloc(chunk_size * sizeof(int));
// 背包DP相关数组需要适配n+1的大小
best_weights = malloc((n+1) * sizeof(int));
best_profits = malloc((n+1) * sizeof(int));
local_weights = malloc((n+1) * sizeof(int));
local_profits = malloc((n+1) * sizeof(int));

2. 修正数组访问边界 #

确保所有数组下标操作在合法范围内，比如调整DP表拷贝逻辑（示例：只保留DP表最后一行结果）：

// 替换原错误的拷贝逻辑
for (w = 0; w <= W; w++) {
    local_weights[w] = K[n][w];
}

3. 修复MPI通信参数 #

保证发送/接收的元素数量与数组实际大小一致：

// 发送chunk_size个元素而非1个
MPI_Send(weightsbfr, chunk_size, MPI_INT, i, 0, MPI_COMM_WORLD);
MPI_Send(profitsbfr, chunk_size, MPI_INT, i, 0, MPI_COMM_WORLD);

4. 添加内存释放逻辑 #

在程序结束前释放所有动态分配的内存，避免泄漏：

// 取消注释并修正free语句
free(weightsbfr);
free(profitsbfr);
free(best_weights);
free(best_profits);
free(local_weights);
free(local_profits);

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