梯形法积分加速比随进程数变化的曲线行为解析

问题背景 #

使用C语言结合MPI实现积分$\int_0^{{1}\frac{4}{1+x}2}dx$的计算，分析不同分段数$N$下加速比（$S=T_1/T_s$，$T_1$为单进程串行时间，$T_s$为$s$进程并行时间）随进程数的变化关系。测试$N=1000$、$10^6$、$108$，进程数范围[1,12]后发现：

• $N=10^8$时，加速比曲线接近理想加速（线性增长）
• $N=1000$时，加速比曲线几乎平坦，增加进程数无明显提速

附上实现代码：

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
 
//int const n = 10e8;
 
double f(double x) {
    return (4 / (1 + x * x));
}
 
double partialArea(double indexSegment, int n, double h) {
    double area = 0.0;
    for (int i = 0; i < n; i++) {
        area += (0.5 * h * (f(indexSegment * h + i * h) + f(indexSegment * h + (i + 1) * h)));
    }
    return area;
}
 
int main(int argc, char *argv[]) {
    int myrank, size;
    MPI_Status Status; // MPI data type
    double integral = 0.0;
    double startwtime, endwtime;
    double a = 0.0, b = 1.0;
    int n;
 
    if (argc != 2) {
    printf("Usage: %s <n>\n", argv[0]);
        exit(1);
   }
 
    n = atoi(argv[1]); // Get n from command line argument
    double h = (b - a) / n;
 
    /* MPI programs start with MIP_Init; all "N" processes exist thereafter */
    MPI_Init(&argc, &argv);
 
    /* find out how big the world of processes is */
    MPI_Comm_size(MPI_COMM_WORLD, &size);
 
    /* and this process's rank is */
    MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
 
    MPI_Barrier(MPI_COMM_WORLD);
    startwtime = MPI_Wtime();
    if (myrank == 0) {
        for (int i = 0; i < n; i++) {
            integral += (0.5 * h * (f(a + i * h) + f(a + (i + 1) * h)));
        }
        printf("----------------------------------------------------\n");
        printf("Integral by sequential: %lf\n", integral);
        printf("Size (number of processes): %d\n", size);
        printf("N (number of small segments): %d\n", n);
        printf("----------------------------------------------------\n");
    }
    MPI_Barrier(MPI_COMM_WORLD);
    endwtime = MPI_Wtime();
    double sequential_time = endwtime - startwtime;
 
    MPI_Barrier(MPI_COMM_WORLD);
    startwtime = MPI_Wtime();
 
    int k = n / size; // number of small intervals 1 process has to work with
 
    int remain = n % size;
    int for_main = k + remain; // if there is a remainder n/size, then it is for the main process
    double result = 0.0;
    double partial = 0.0;
    int index;
 
    if (myrank == 0) {
        result += partialArea(0, for_main, h);
        for (int i = 1; i < size; i++) {
            MPI_Recv(&partial, 1, MPI_DOUBLE, i, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            result += partial;
        }
        printf("----------------------------------------------------\n");
        printf("Integral by the addition of all parts: %lf\n", result);
        printf("----------------------------------------------------\n");
    } else {
        index = for_main + k * (myrank - 1);
        partial = partialArea(index, k, h);
        MPI_Send(&partial, 1, MPI_DOUBLE, 0, 1, MPI_COMM_WORLD);
        printf("Rank %d: Partial Integral I%d = %lf\n", myrank, myrank, partial);
    }
 
    MPI_Barrier(MPI_COMM_WORLD);
    endwtime = MPI_Wtime();
    double process_time = endwtime - startwtime;
 
    if (myrank == 0) {
        printf("----------------------------------------------------\n");
        printf("Sequential time: %lf\n", sequential_time);
        printf("Process time: %lf\n", process_time);
        printf("Speed up: %lf\n", sequential_time / process_time);
        printf("----------------------------------------------------\n");
    }
    MPI_Finalize();
}

问题解答 #

1. 加速比公式$S=T_1/T_s$的核心逻辑 #

加速比衡量并行程序相对于串行程序的性能提升：

• $T_1$是单进程完成全部计算的时间
• $T_s$是$s$个进程并行完成计算的时间
  理想加速比为$S=s$（即线性加速，每个进程承担1/s的计算量且无额外开销），但实际中受计算量占比、通信开销、负载均衡等因素影响，加速比会偏离理想值。

2. 两种场景的差异原因分析 #

（1）$N=10^8$：接近理想加速

当$N$极大时，计算量远大于通信开销：

• 每个进程需要处理的分段数$k = N/s$依然很大（比如12进程时，$k≈8.3×10^6$），进程花费在计算partialArea循环的时间占总时间的绝大多数。
• 通信仅涉及每个从进程发送一个double类型的部分积分结果给主进程，这部分时间相对于整体计算时间可以忽略不计。
• 负载基本均衡：主进程多处理remain个分段（最多11个，相对于1e8可忽略），各进程的计算时间差异极小。
  此时$T_s≈T_1/s$，因此加速比$S≈s$，接近理想线性加速。

（2）$N=1000$：加速比平坦

当$N$较小时，通信开销占比主导：

• 每个进程处理的分段数极少：12进程时，主进程处理$1000/12 + 4≈87$个分段，从进程处理83个分段，计算时间极短（几微秒级）。
• 通信开销（MPI_Send/MPI_Recv的延迟、MPI_Barrier的同步时间）远大于计算时间。增加进程数时，额外的通信开销抵消了计算并行带来的时间节省，甚至可能让总时间$T_s$几乎不变。
• 从加速比公式看，$T_s$不会随进程数$s$增加而明显减小，因此$S=T_1/T_s$基本保持不变，曲线平坦。

3. 代码中的额外细节影响 #

你的代码中，串行计算是在MPI初始化后由rank0单独执行的，这部分计时包含了MPI环境的一些基础开销，但对整体趋势影响不大。真正的关键是计算量与通信开销的相对比例：只有当计算量足够大，让通信开销占比可忽略时，并行加速才能体现。

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