May 12, 2026

miniyuan

MPI 编程

---

题目 1：并行计算向量点积

代码编写思路

尝试使用 MPI_Send 和 MPI_Recv 操作实现了一下 MPI_Scatter 和 MPI_Reduce。

然后将长度为 $N$ 的向量 $A$、$B$ 均分给 $size$ 个进程。每个进程计算本地子向量的点积，再通过 my_reduce 将局部结果规约求和，得到全局点积。

源代码

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

#define N 10000000

// 尝试使用 Send/Recv 实现 Scatter
void my_scatter(void *sendbuf, int sendcount, MPI_Datatype sendtype,
                void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm) {
    int rank, size;
    int typesize;
    char *sendpos;

    MPI_Comm_rank(comm, &rank);
    MPI_Comm_size(comm, &size);

    // 计算数据类型大小
    MPI_Type_size(sendtype, &typesize);

    if (rank == root) {
        // 根节点发送数据
        for (int i = 0; i < size; i++) {
            sendpos = (char *)sendbuf + i * sendcount * typesize;
            if (i == root) {
                // 不能自己发给自己，否则会死锁
                memcpy(recvbuf, sendpos, recvcount * typesize);
            } else {
                MPI_Send(sendpos, sendcount, sendtype, i, 0, comm);
            }
        }
    } else {
        // 普通节点接受数据
        MPI_Recv(recvbuf, recvcount, recvtype, root, 0, comm, MPI_STATUS_IGNORE);
    }
}

// 尝试使用 Send/Recv 实现 Reduce
void my_reduce(const void *sendbuf, void *recvbuf, int count,
               MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm) {
    int rank, size;
    int typesize;

    MPI_Comm_rank(comm, &rank);
    MPI_Comm_size(comm, &size);

    // 计算数据类型大小
    MPI_Type_size(datatype, &typesize);

    if (rank == root) {
        // 不能自己与自己规约，否则会死锁
        memcpy(recvbuf, sendbuf, count * typesize);

        // 临时缓冲区，用于接收数据
        void *tmpbuf = malloc(count * typesize);

        for (int i = 0; i < size; i++) {
            if (i == root)
                continue;

            MPI_Recv(tmpbuf, count, datatype, i, 0, comm, MPI_STATUS_IGNORE);
            MPI_Reduce_local(tmpbuf, recvbuf, count, datatype, op);
        }

        free(tmpbuf);
    } else {
        // 普通节点发送数据
        MPI_Send(sendbuf, count, datatype, root, 0, comm);
    }
}

int main(int argc, char **argv) {
    int rank, size, root = 0;
    double *A = nullptr, *B = nullptr;
    double start, end;
    double local_dot = 0.0, global_dot = 0.0;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    // 根节点生成向量
    if (rank == root) {
        A = (double *)malloc(N * sizeof(double));
        B = (double *)malloc(N * sizeof(double));
        for (int i = 0; i < N; i++) {
            A[i] = 1.0;
            B[i] = 2.0;
        }
    }

    // 记录开始时间
    MPI_Barrier(MPI_COMM_WORLD); // 等待根节点生成向量
    start = MPI_Wtime();

    // 均分向量
    int local_n = N / size; // 假设可以整除
    double *local_A = (double *)malloc(local_n * sizeof(double));
    double *local_B = (double *)malloc(local_n * sizeof(double));

    my_scatter(A, local_n, MPI_DOUBLE, local_A, local_n, MPI_DOUBLE, root, MPI_COMM_WORLD);
    my_scatter(B, local_n, MPI_DOUBLE, local_B, local_n, MPI_DOUBLE, root, MPI_COMM_WORLD);

    // 各进程计算本地结果
    for (int i = 0; i < local_n; i++) {
        local_dot += local_A[i] * local_B[i];
    }

    // 规约求和
    my_reduce(&local_dot, &global_dot, 1, MPI_DOUBLE, MPI_SUM, root, MPI_COMM_WORLD);

    // 记录结束时间
    MPI_Barrier(MPI_COMM_WORLD); // 等待规约求和
    end = MPI_Wtime();

    // 输出结果
    if (rank == root) {
        printf("向量长度 = %lld, 进程数 = %d\n", N, size);
        printf("点积结果 = %.6lf\n", global_dot);
        printf("预期结果 = %.6lf\n\n", (double)2.0 * N);
        printf("并行计算时间 = %.6lf 秒\n", end - start);

        free(A);
        free(B);
    }

    free(local_A);
    free(local_B);
    MPI_Finalize();

    return MPI_SUCCESS;
}

测试结果

向量长度 = 10000000, 进程数 = 1
点积结果 = 20000000.000000
预期结果 = 20000000.000000

并行计算时间 = 0.180529 秒

向量长度 = 10000000, 进程数 = 2
点积结果 = 20000000.000000
预期结果 = 20000000.000000

并行计算时间 = 0.146890 秒

向量长度 = 10000000, 进程数 = 4
点积结果 = 20000000.000000
预期结果 = 20000000.000000

并行计算时间 = 0.131881 秒

向量长度 = 10000000, 进程数 = 8
点积结果 = 20000000.000000
预期结果 = 20000000.000000

并行计算时间 = 0.124590 秒

进程数 $p$	计算时间 (s)	加速比 $S$	并行效率 $E$
1	0.180529	1.000	100.0%
2	0.146890	1.229	61.5%
4	0.131881	1.369	34.2%
8	0.124590	1.449	18.1%

可能是因为我自己实现 my_scatter 和 my_reduce 比较低效，所以通信开销占比太大了。

题目 2：并行计算定积分

代码编写思路

采用梯形法计算 $\int_0^1 x^2 \, dx$。将区间 $[a,b]$ 划分为 $n$ 个小区间，每个进程负责计算自己区间上的梯形面积之和，最后通过 MPI_Reduce 汇总。

源代码

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

double f(double x) {
    return x * x;
}

int main(int argc, char *argv[]) {
    int rank, size, root = 0;
    long long n = 100000000;
    double start, end;
    double a = 0.0, b = 1.0, h = (b - a) / n;
    double local_int = 0.0, global_int = 0.0;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    // 记录开始时间
    MPI_Barrier(MPI_COMM_WORLD); // 计时同步
    start = MPI_Wtime();

    long long local_n = n / size;
    double local_a = a + rank * local_n * h;
    double local_b = local_a + local_n * h;

    local_int = 0.5 * f(local_a) + 0.5 * f(local_b);
    for (long long i = 1; i < local_n; i++) {
        local_int += f(local_a + i * h);
    }
    local_int *= h;

    // 规约求和
    MPI_Reduce(&local_int, &global_int, 1, MPI_DOUBLE, MPI_SUM, root, MPI_COMM_WORLD);

    // 记录结束时间
    MPI_Barrier(MPI_COMM_WORLD); // 计时同步
    end = MPI_Wtime();

    // 输出结果
    if (rank == root) {
        printf("积分区间 = [%.1lf, %.1lf], 划分数 = %lld\n", a, b, n);
        printf("进程数 = %d\n", size);
        printf("积分结果 = %.6lf\n", global_int);
        printf("预期结果 = 0.333333\n\n");

        printf("并行计算时间 = %.6lf 秒\n", end - start);
    }

    MPI_Finalize();

    return MPI_SUCCESS;
}

测试结果

积分区间 = [0.0, 1.0], 划分数 = 100000000
进程数 = 1
积分结果 = 0.333333
预期结果 = 0.333333

并行计算时间 = 0.374256 秒

积分区间 = [0.0, 1.0], 划分数 = 100000000
进程数 = 2
积分结果 = 0.333333
预期结果 = 0.333333

并行计算时间 = 0.188580 秒

积分区间 = [0.0, 1.0], 划分数 = 100000000
进程数 = 4
积分结果 = 0.333333
预期结果 = 0.333333

并行计算时间 = 0.094433 秒

进程数 $p$	计算时间 (s)	加速比 $S$	并行效率 $E$
1	0.374256	1.000	100.0%
2	0.188580	1.985	99.2%
4	0.094433	3.963	99.1%

题目 3：并行素数统计

代码编写思路

将区间 $[2, \text{MAX}]$ 划分给各进程，每个进程用试除法判断本地范围内的素数，统计个数后通过 MPI_Reduce 求和。 然后利用 MPI_Gather 汇总各进程找到的素数数量并在根节点输出。

源代码

#include <math.h>
#include <mpi.h>
#include <stdbool.h>
#include <stdio.h>

#define MAX 10000000

// 试除法
bool is_prime(int n) {
    if (n < 2)
        return false;

    if (n == 2)
        return true;

    int bound = (int)sqrt(n) + 1;

    for (int i = 2; i <= bound; i++) {
        if (n % i == 0)
            return false;
    }

    return true;
}

int main(int argc, char *argv[]) {
    int rank, size, root = 0;
    double start, end;
    long long *local_cnts = nullptr; // 统计各进程素数数
    long long local_cnt = 0, global_cnt = 0;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    // 记录开始时间
    MPI_Barrier(MPI_COMM_WORLD); // 计时同步
    start = MPI_Wtime();

    // 数据划分
    long long local_n = (MAX - 1) / size;
    long long left = (MAX - 1) % size;
    long long local_a, local_b;

    if (rank < left) {
        // 前 left 个进程需处理 local_n + 1 个数
        local_a = 2 + rank * (local_n + 1);
        local_b = local_a + local_n;
    } else {
        // 后面进程需处理 local_n 个数
        local_a = 2 + rank * local_n + left;
        local_b = local_a + local_n - 1;
    }

    // 统计本地素数
    for (long long i = local_a; i <= local_b; i++) {
        if (is_prime(i))
            local_cnt++;
    }

    // 规约求和
    MPI_Reduce(&local_cnt, &global_cnt, 1, MPI_LONG_LONG, MPI_SUM, root, MPI_COMM_WORLD);

    // 统计各进程素数数
    if (rank == root) {
        local_cnts = (long long *)malloc(size * sizeof(long long));
    }
    MPI_Gather(&local_cnt, 1, MPI_LONG_LONG, local_cnts, 1, MPI_LONG_LONG, root, MPI_COMM_WORLD);

    // 记录结束时间
    MPI_Barrier(MPI_COMM_WORLD); // 计时同步
    end = MPI_Wtime();

    // 输出结果
    if (rank == root) {
        printf("范围 [2, %lld], 进程数 = %d\n", (long long)MAX, size);
        printf("素数总数 = %lld\n", global_cnt);
        printf("各进程找到的素数数量:\n");
        for (int i = 0; i < size; i++) {
            printf("  进程 %d: %lld 个\n", i, local_cnts[i]);
        }
        printf("\n并行计算时间 = %.6lf 秒\n", end - start);

        free(local_cnts);
    }

    MPI_Finalize();

    return MPI_SUCCESS;
}

测试结果

范围 [2, 10000000], 进程数 = 1
素数总数 = 664579
各进程找到的素数数量:
  进程 0: 664579 个

并行计算时间 = 5.451695 秒

范围 [2, 10000000], 进程数 = 2
素数总数 = 664579
各进程找到的素数数量:
  进程 0: 348513 个
  进程 1: 316066 个

并行计算时间 = 3.404928 秒

范围 [2, 10000000], 进程数 = 4
素数总数 = 664579
各进程找到的素数数量:
  进程 0: 183072 个
  进程 1: 165441 个
  进程 2: 159748 个
  进程 3: 156318 个

并行计算时间 = 1.824406 秒

进程数 $p$	计算时间 (s)	加速比 $S$	并行效率 $E$
1	5.451695	1.000	100.0%
2	3.404928	1.601	80.1%
4	1.824406	2.988	74.7%