并行计算基础

各位同学，今天我们来聊聊并行计算的基础知识。这部分内容看起来偏理论，但它是后面理解 GPU 集群调度和 BLAST 加速的基石。我个人习惯把并行计算比作"一群人搬砖"——一个人搬得慢，那就多上几个人，但前提是分工要合理，不能互相绊脚。

什么是并行计算

并行计算，说白了就是同时用多个计算资源来解决同一个问题。核心思路很简单：把一个大任务拆成多个小任务，然后同时执行。你想想看，如果你的程序跑在 10 个核上，理想情况下速度能提升近 10 倍——当然，实际中因为通信开销和负载不均，很难达到线性加速。

为什么需要并行计算？两个原因：

• 性能墙：单核频率已经很难再往上提了，功耗和散热都扛不住。
• 数据太大：像 BLAST 这种比对任务，动不动就几百万条序列，单机跑要等到天荒地老。

Flynn 分类法

Flynn 分类法把计算机架构按指令流和数据流的维度分成四类。我记得刚接触时老把 SIMD 和 MIMD 搞混，后来靠一个例子才彻底记住——SIMD 像教官喊口号，所有人做同一个动作；MIMD 像自由市场，各干各的。

分类	指令流	数据流	典型代表	我见过的应用场景
SISD	单	单	普通单核 CPU	串行程序，比如早期的 BLAST 单线程版本
SIMD	单	多	GPU、CPU 向量指令（AVX/SSE）	BLAST 中的打分矩阵计算，一条指令处理多个碱基对
MISD	多	单	容错系统（少见）	说实话，我在高性能计算领域几乎没见过实用案例
MIMD	多	多	多核 CPU 集群、分布式系统	GPU 集群上的 BLAST 并行调度，每个节点处理不同的查询序列

在我们的 BLAST 加速场景里，最常打交道的是 SIMD 和 MIMD。SIMD 用来做单节点内的细粒度并行，MIMD 用来做跨节点的粗粒度调度。

共享内存与分布式内存

这两种内存架构的差异，直接决定了你怎么写并行程序。

特性	共享内存	分布式内存
物理内存	多个处理器共享同一块内存	每个节点有自己的私有内存
通信方式	直接读写内存（隐式通信）	通过消息传递（显式通信）
编程模型	OpenMP、POSIX Threads	MPI、PGAS
可扩展性	受限于总线带宽，一般 ≤ 几十个核	可以扩展到成千上万个节点
典型硬件	多核 CPU、NVIDIA GPU（全局内存）	HPC 集群、GPU 集群

我做 BLAST 集群调度时，通常会混合使用两种架构：节点内部用共享内存（OpenMP 或 CUDA），节点之间用分布式内存（MPI）。这样既利用了共享内存的低延迟优势，又保留了分布式架构的可扩展性。

并行编程模型

实际写代码时，你选哪个编程模型，取决于你的硬件平台和问题特点。我按自己的经验，把主流模型分成三类：

1. 共享内存模型（OpenMP）

OpenMP 用编译器指令来标记并行区域，开发效率很高。你只需要在 for 循环前加一行 pragma，就能把任务分给多个线程。

#pragma omp parallel for reduction(+:score)
for (int i = 0; i < num_sequences; i++) {
    score[i] = align(query, database[i]);
}

这个片段里，reduction 子句帮我们自动处理了累加时的竞态条件。我刚开始用 OpenMP 时经常忘加 reduction，结果算出来的分数忽大忽小，排查了半天才发现是数据竞争。

2. 消息传递模型（MPI）

MPI 是分布式内存的标配。每个进程有独立的地址空间，通过 send 和 recv 交换数据。

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

if (rank == 0) {
    // 主进程分发任务
    MPI_Send(query_chunk, chunk_size, MPI_CHAR, 1, 0, MPI_COMM_WORLD);
} else {
    // 工作进程接收并计算
    MPI_Recv(query_chunk, chunk_size, MPI_CHAR, 0, 0, MPI_COMM_WORLD, &status);
    result = run_blast(query_chunk);
}

3. GPU 加速模型（CUDA）

CUDA 模型本质上是 SIMT（单指令多线程），它把大量线程组织成网格和线程块。GPU 上的并行粒度比 CPU 细得多——你可以轻松启动几万个线程。

__global__ void blast_kernel(char *query, char *database, int *scores, int num_queries) {
    int idx = blockIdx.x * blockDim.x + threadIdx.x;
    if (idx < num_queries) {
        scores[idx] = smith_waterman(query[idx], database);
    }
}

// 启动 256 个线程块，每块 256 个线程
blast_kernel<<<256, 256>>>(d_query, d_database, d_scores, num_queries);

这里要注意，GPU 上的内存访问模式对性能影响极大。我在优化 BLAST 的 CUDA 版本时，发现合并内存访问能让带宽利用率提升 3 倍以上。说白了，就是让相邻线程访问相邻地址，充分利用 GPU 的缓存行。

4. 混合模型（MPI + OpenMP + CUDA）

在 GPU 集群上，我最常用的方案是三层混合：

• 节点间：MPI 做任务分发和结果汇总
• 节点内 CPU 端：OpenMP 做数据预处理和 I/O
• 节点内 GPU 端：CUDA 做核心比对计算

这个架构在后面的章节里会反复出现，是整套课程的技术支柱。

这张图把本章的核心脉络串在了一起。从并行计算概念出发，通过 Flynn 分类法理解不同架构，再落到内存架构和编程模型的选择。后面的 GPU 集群 BLAST 调度，本质上就是在这个框架下做工程决策——选对模型、用好硬件、平衡通信与计算。