MPI并行二分搜索进程增多时性能下降问题求助

核心问题诊断 #

1. 数据集规模过小 #

当前数组大小为 10 * comm_sz，例如8进程时仅80个元素。二分查找在这种极小数据集上仅需约7次迭代，耗时可以忽略不计。而MPI通信（Scatter、Reduce、Barrier）的开销远大于并行搜索节省的时间，导致进程数越多总耗时越长——这是并行计算中典型的通信开销超过计算收益的场景。

2. 二分查找实现逻辑错误 #

BinarySearch函数中的for循环设计完全错误：使用无关的i变量递增，而非基于lower和heigher的边界变化控制循环。这会导致不必要的迭代，甚至可能引发数组越界访问，同时降低搜索效率。

3. 冗余MPI同步与全局变量风险 #

• 搜索后的MPI_Barrier是冗余的：MPI_Reduce本身就是阻塞式集体操作，会自动等待所有进程完成后才继续执行，额外的屏障只会增加同步开销。
• 使用全局变量index和found_rank在MPI多进程环境中存在状态不一致风险，不符合并行程序的设计规范。

修复后的代码 #

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

void BinarySearch(int local_x[], int search, int lower, int higher, int rank, int base_offset, int* result_index, int* result_rank);
int* create_array(int n);

int main() {
    int search = 7;
    
    MPI_Init(NULL, NULL);

    int my_rank, comm_sz;
    double start = 0;
    double finish = 0;
    MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
    MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

    // 大幅增加数据集规模，让并行计算的收益超过通信开销
    const int size = 1000000; 
    int* x = NULL;

    // 计算每个进程的本地数组大小（处理不能整除的情况）
    int local_size = size / comm_sz;
    if (my_rank < size % comm_sz) {
        local_size += 1;
    }
    int* local_x = (int*)malloc(local_size * sizeof(int));

    // 计算当前进程在全局数组中的起始偏移量
    int base_offset = 0;
    for (int i = 0; i < my_rank; ++i) {
        base_offset += size / comm_sz;
        if (i < size % comm_sz) {
            base_offset += 1;
        }
    }

    MPI_Barrier(MPI_COMM_WORLD);
    start = MPI_Wtime();

    if (my_rank == 0) {
        printf("总数组大小: %d，每个进程本地大小: %d\n", size, local_size);
        x = create_array(size);
    }

    // 使用MPI_Scatterv处理非均匀数据分配
    int* sendcounts = NULL;
    int* displs = NULL;
    if (my_rank == 0) {
        sendcounts = (int*)malloc(comm_sz * sizeof(int));
        displs = (int*)malloc(comm_sz * sizeof(int));
        int offset = 0;
        for (int i = 0; i < comm_sz; i++) {
            sendcounts[i] = size / comm_sz;
            if (i < size % comm_sz) {
                sendcounts[i] += 1;
            }
            displs[i] = offset;
            offset += sendcounts[i];
        }
    }
    MPI_Scatterv(x, sendcounts, displs, MPI_INT, local_x, local_size, MPI_INT, 0, MPI_COMM_WORLD);

    int local_index = -1;
    int local_rank = -1;
    BinarySearch(local_x, search, 0, local_size - 1, my_rank, base_offset, &local_index, &local_rank);

    // 收集全局结果：MPI_MAX会自动筛选出有效索引（无效为-1）
    int global_index = -1;
    int global_rank = -1;
    MPI_Reduce(&local_index, &global_index, 1, MPI_INT, MPI_MAX, 0, MPI_COMM_WORLD);
    MPI_Reduce(&local_rank, &global_rank, 1, MPI_INT, MPI_MAX, 0, MPI_COMM_WORLD);

    finish = MPI_Wtime();

    if (my_rank == 0) {
        printf("\n总耗时 = %g\n", finish - start);

        if (global_rank == -1 || global_index == -1) {
            printf("未找到目标值\n");
        } else {
            printf("值 %d 位于全局索引 %d，所属进程 rank: %d\n", search, global_index, global_rank);
        }

        free(x);
        free(sendcounts);
        free(displs);
    }

    free(local_x);
    MPI_Finalize();

    return 0;
}

void BinarySearch(int local_x[], int search, int lower, int higher, int rank, int base_offset, int* result_index, int* result_rank) {
    *result_index = -1;
    *result_rank = -1;

    // 标准二分查找循环逻辑
    while (lower <= higher) {
        // 用lower + (higher-lower)/2避免整数溢出
        int mid = lower + (higher - lower) / 2;

        if (local_x[mid] == search) {
            *result_index = base_offset + mid;
            *result_rank = rank;
            break;
        } else if (local_x[mid] < search) {
            lower = mid + 1;
        } else {
            higher = mid - 1;
        }
    }
}

int* create_array(int n) {
    int* tmp = (int*)calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) {
        tmp[i] = i + 1;
    }
    return tmp;
}

关键优化点说明 #

1. 扩大数据集规模：将数组大小设置为100万，确保并行搜索的计算收益能覆盖MPI通信开销。
2. 修复二分查找逻辑：用标准while循环替代错误的for循环，避免无效迭代和潜在bug。
3. 处理非均匀数据分配：使用MPI_Scatterv替代MPI_Scatter，确保数组元素能均匀分配到所有进程（即使总大小不能被进程数整除）。
4. 移除冗余屏障：删除搜索后的MPI_Barrier，利用MPI_Reduce的阻塞特性完成同步。
5. 替换全局变量：使用局部变量存储每个进程的搜索结果，通过MPI_Reduce收集全局结果，避免多进程状态冲突。

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