并行计算基础与 MPI 编程

为什么需要并行计算

2004 年前后，单核处理器的性能提升遇到了多重瓶颈：晶体管集成度已进入纳米级别，难以继续大幅提高；指令级并行技术（流水线、分支预测、超标量、乱序执行等）已接近极限；CPU 速度与主存速度的差距日益拉大（CPU 访问约 1ns，主存约 100ns）；频率提升导致功耗急剧增加（功耗 P = CV²f），Intel 在 2004 年放弃 Tejas 4GHz 处理器计划，标志着"升频时代"的终结。

此后，工业界全面转向多核与众核并行计算。从双核、四核到如今的数十核通用处理器，以及 GPU、TPU 等专用众核加速器，并行计算已成为提升性能的核心途径。与此同时，应用领域的数据规模也在爆炸式增长——Google 每天处理数十亿次搜索，大型强子对撞机每年产生 15PB 数据，基因测序中心每天产出数百 GB 数据。这些需求催生了对并行计算技术的迫切需要。

并行计算的分类

Flynn 分类法

1966 年，斯坦福大学教授 Flynn 从指令和数据流的角度提出了经典的计算机结构分类：

类型	全称	说明	典型系统
SISD	单指令单数据流	传统串行处理器	早期单核 CPU
SIMD	单指令多数据流	一条指令同时处理多个数据	向量机、GPU
MISD	多指令单数据流	很少实际使用	容错系统
MIMD	多指令多数据流	最常见的并行形式	多核 CPU、集群

TOP500 超级计算机几乎全部属于 MIMD 类型。

按并行粒度分类

• 位级并行：增加处理器字长（4→8→16→32→64 位）
• 指令级并行（ILP）：流水线、超标量、乱序执行
• 线程级并行：多线程同时执行
• 数据级并行：将大数据块划分为小块，由不同处理器并行处理
• 任务级并行：将大任务分解为子任务，分配给不同处理器

按存储访问架构分类

graph TD
    subgraph A[共享内存 UMA]
        P1[处理器] --- Bus[总线]
        P2[处理器] --- Bus
        P3[处理器] --- Bus
        Bus --- M[共享内存]
    end

    subgraph B[分布式内存]
        P4[处理器] --- M1[本地内存]
        P5[处理器] --- M2[本地内存]
        P6[处理器] --- M3[本地内存]
        P4 <-.->|网络| P5
        P5 <-.->|网络| P6
    end

• 共享内存（UMA）：所有处理器通过总线访问同一内存，编程简单但扩展性有限，典型代表是 SMP（对称多处理）系统
• 分布式内存：每个处理器拥有独立的本地内存，通过网络通信，扩展性强但编程复杂，典型代表是集群和 MPP
• 分布式共享内存（NUMA）：兼具两者特点，处理器有本地内存也可访问全局内存，需处理缓存一致性问题

按系统类型分类

从紧耦合到松散，各类系统在可扩展性和能耗上各有取舍：

类型	全称	特点
MC	Multicore/Manycore	处理器核通过片上网络（NOC）集成在一个芯片上，功耗很低
SMP	Symmetric Multiprocessing	多个相同处理器通过总线共享内存，运行一个 OS，规模较小（2-8 处理器）
MPP	Massive Parallel Processing	专用内联网连接独立处理器，各有独立内存和 OS，TOP500 中有 80 多个
Cluster	集群	商品化服务器通过网络互联，可扩展性强，TOP500 中有 400 多个
Grid	网格	地理上广泛分布的异构计算资源，极为松散，主要用于低并行度的大规模科学计算

按计算特征分类

• 数据密集型：数据量极大但计算相对简单，如大规模 Web 信息搜索
• 计算密集型：数据量不大但计算复杂，如 3D 建模与渲染、气象预报
• 混合型：兼具两者特征，如 3D 电影渲染

Amdahl 定律

Amdahl 定律描述了并行程序的理论加速上限。设程序中可并行化的比例为 P，处理器数量为 N，则加速比 S 为：

\[S = \frac{1}{(1-P) + \frac{P}{N}}\]

当 N 趋于无穷大时，最大加速比为 1/(1-P)。这意味着：

可并行比例 P	理论最大加速比
50%	2×
75%	4×
90%	10×
95%	20×
99%	100×

Amdahl 定律揭示了一个重要事实：串行部分是并行化的瓶颈。即使增加再多的处理器，程序的加速比也受限于不可并行的部分。这启示我们在设计并行算法时，应尽量减小串行比例。

并行计算的主要技术问题

并行计算涉及硬件架构、软件架构和并行算法三个层面，概括起来有以下关键技术问题：

• 多核/多处理器网络互连：研究处理器间互联拓扑结构，包括共享总线、交叉开关矩阵、环形结构（Torus）、Mesh 网络、片上网络（NOC）等
• 存储访问架构：共享存储需解决数据访问同步控制；分布存储需解决数据通信和节点同步；分布共享存储需解决缓存一致性问题
• 分布式数据与文件管理：如 RedHat GFS、IBM GPFS、Google GFS、Hadoop HDFS 等
• 任务分解与算法设计：将大任务从数据或计算方法上划分为子任务，分配给各节点并行处理
• 并行程序设计模型：共享内存式（Pthread、OpenMP）、消息传递式（MPI）、MapReduce 等
• 数据同步与通信控制：解决共享数据访问的竞争状态（race condition）和死锁问题
• 可靠性与容错：设 1 万个节点，每个 MTBF 为 1000 天，则平均每天 10 个节点出错——系统需要有效的失效检测和恢复机制
• 并行计算软件框架：如 MapReduce 提供自动化并行处理能力，屏蔽底层细节，让程序员专注于应用问题本身
• 性能评估：使用 High-Performance Linpack Benchmark 评估浮点计算能力，TOP500 据此排名

MPI 简介

MPI（Message Passing Interface）是基于消息传递的高性能并行计算编程接口标准，1994 年发布 1.0 版本，经过 MPI 2.x、MPI 3.x 发展到 MPI 4.0（2021 年）乃至 MPI 5.0（2025 年）。其核心特点：

• 提供可靠的、面向消息的通信
• 独立于语言的编程规范（C/C++、Fortran、Python、Java 均有实现）
• 广泛用于科学计算领域的计算密集型任务
• 主要实现包括 MPICH、OpenMPI、Intel MPI 等

六个基本 API

MPI 提供了 6 个最基本的编程接口，理论上任何并行程序都可以通过它们实现：

// 1. 初始化 MPI 环境
MPI_Init(&argc, &argv);

// 2. 获取通信组中的进程总数
MPI_Comm_size(MPI_COMM_WORLD, &numprocs);

// 3. 获取当前进程的标识号
MPI_Comm_rank(MPI_COMM_WORLD, &myid);

// 4. 发送消息
MPI_Send(buf, count, datatype, dest, tag, comm);

// 5. 接收消息
MPI_Recv(buf, count, datatype, source, tag, comm, &status);

// 6. 终止 MPI 环境
MPI_Finalize();

其中 MPI_COMM_WORLD 是默认的全局通信组，dest/source 是目标/源进程的标识号，tag 是消息标签用于区分不同类型的消息。

点对点通信

MPI 的点对点通信分为同步（阻塞）和异步（非阻塞）两种模式：

阻塞通信：MPI_Send 和 MPI_Recv 在通信完成前不会返回，保证数据已发送/接收完毕。

非阻塞通信：MPI_Isend 和 MPI_Irecv 立即返回，通过 MPI_Wait 等待完成或 MPI_Test 查询状态，允许通信与计算重叠以提高效率。

集合通信

集合通信提供一个进程与多个进程间同时通信的功能，主要包括三类：

类型	函数	功能
同步	MPI_Barrier	设置同步屏障，所有进程在此等待直到全部到达
数据移动	MPI_Bcast	一对多广播
数据移动	MPI_Gather	多对一收集
数据移动	MPI_Scatter	一对多分发
规约	MPI_Reduce	将各进程数据按指定操作规约到一个进程

MPI_Reduce 支持多种规约操作：MPI_SUM（求和）、MPI_MAX（最大值）、MPI_MIN（最小值）、MPI_PROD（求积）等。

编程示例：Monte Carlo 方法计算圆周率

Monte Carlo 方法通过随机抽样来近似求解问题。计算 π 的原理是：在边长为 1 的正方形内随机撒点，统计落入内切圆（半径 0.5）内的点数比例，π ≈ 4 × (圆内点数 / 总点数)。

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

int main(int argc, char **argv) {
    int myid, numprocs;
    long count = 1000000;  // 每个进程的采样点数
    long m = 0;            // 圆内点数
    double x, y, pi;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);
    MPI_Comm_size(MPI_COMM_WORLD, &numprocs);

    srand((int)time(0) + myid);  // 每个进程使用不同随机种子

    // 每个进程独立进行随机采样
    for (long i = 0; i < count; i++) {
        x = (double)rand() / RAND_MAX;
        y = (double)rand() / RAND_MAX;
        if ((x - 0.5) * (x - 0.5) + (y - 0.5) * (y - 0.5) < 0.25)
            m++;
    }

    // 使用 MPI_Reduce 将各进程的圆内点数求和到主进程
    long total_m;
    MPI_Reduce(&m, &total_m, 1, MPI_LONG, MPI_SUM, 0, MPI_COMM_WORLD);

    if (myid == 0) {
        pi = 4.0 * total_m / (count * numprocs);
        printf("pi = %f\n", pi);
    }

    MPI_Finalize();
    return 0;
}

编译和运行：

mpicc -o monte_carlo_pi monte_carlo_pi.c
mpirun -np 4 ./monte_carlo_pi
# 输出示例: pi = 3.141823

这个例子展示了 MPI 并行编程的基本模式：每个进程独立计算局部结果，然后通过 MPI_Reduce 将结果规约汇总。随着进程数增加，总采样点数成倍增长，计算精度和速度都能得到提升。

编程示例：使用集合通信计算积分

用梯形法计算函数 f(x) = x² 在区间 [0, 10] 上的定积分：

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

#define N 100000000  // 总区间数
#define A 0.0
#define B 10.0

int main(int argc, char **argv) {
    int myid, numprocs;
    double local_sum = 0.0, global_sum;
    double dx = (B - A) / N;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);
    MPI_Comm_size(MPI_COMM_WORLD, &numprocs);

    // 每个进程计算一部分矩形面积
    for (int i = myid; i < N; i += numprocs) {
        double x = A + i * dx + dx / 2;  // 矩形中心点
        local_sum += x * x * dx;          // 矩形面积
    }

    // 使用 Reduce 将各进程的局部和规约为全局和
    MPI_Reduce(&local_sum, &global_sum, 1, MPI_DOUBLE,
               MPI_SUM, 0, MPI_COMM_WORLD);

    if (myid == 0)
        printf("Integral of x^2 in [0, 10] = %.15f\n", global_sum);

    MPI_Finalize();
    return 0;
}

这个例子中，N 个矩形按循环方式分配给各进程（进程 myid 处理第 myid、myid+numprocs、myid+2×numprocs... 个矩形），最后通过 MPI_Reduce 求和得到积分值。理论值为 1000/3 ≈ 333.333...。

MPI 的特点与局限

优势：

• 灵活性好，适合各类计算密集型并行任务
• 独立于语言和平台，可移植性强
• 有丰富的开源和商业实现

局限：

• 需要程序员手动处理数据划分、通信、同步等细节
• 缺少分布式文件系统支持
• 通信开销大，节点规模增大时性能下降明显
• 无内置的容错机制，节点失效可能导致整个计算失败

这些局限性正是后来 MapReduce 等大数据并行计算框架诞生的动因——它们将数据分布、任务调度、容错处理等复杂细节交由框架自动处理，让程序员专注于业务逻辑本身。