Cpp 并行计算学习笔记

基本概念

首先学习几组基本概念：

• 并发（Concurrency）/并行（Parallelism）
• 同步（Synchronous）/异步（Asynchronous）
• 进程（Process）/线程（Thread）

并发 / 并行

• 并发指的是多个任务在同一时间段内被同时推进，可能是同时执行不同的任务，也可能是频繁交替执行每一个任务的一小部分
• 并行指的是多个任务在同一时间段内真正同时执行

举个例子：

• 学生在课后可以并发地完成每一个科目的作业：一会写语文作业，一会又切换回写数学作业，切换可以非常频繁，但是不可能同时写两科作业，也就是不能并行
• 人体的消化系统的任务和循环系统的任务在并行地执行：在同一时间内，肠道蠕动和血液循环在同时进行，不可能说心脏跳动时就让肠道蠕动暂停

同步 / 异步

• 同步是指任务按照顺序依次执行，每个任务在前一个任务完成后开始执行。在同步模式中，任务之间需要等待其他任务完成才能继续执行。
• 异步是指任务可以独立于其他任务进行执行，它们的执行过程不会产生堵塞。在异步模式中，任务可以在后台执行，执行结果可能需要等待一段时间才能获得，但这不会影响其他任务的执行。

举个例子：

• 手洗衣服的流程是同步的：先将衣物放入盆中，再加入洗衣粉，然后开始洗衣，等到洗衣完成，最后取出衣物晾干或烘干，每一步的开始都依赖于前一步的完成，在过程中也干不了其他事。
• 使用洗衣机洗衣服是异步的：将衣物放入洗衣机并启动，洗衣机开始运作，此时人不需要等待在洗衣机旁，可以干其它任何事，等到洗衣机完成后会发出通知，然后取出衣物晾晒即可，当然也可以选择等在一边，不干其他事。

进程 / 线程

• 进程是程序执行的实例，是操作系统分配资源的基本单位，拥有自己的代码区、堆区、栈区、全局变量等。操作系统会确保进程之间相互独立，一个进程的崩溃不会影响其他进程。进程之间的通信开销相对较大，需要基于特殊的通信机制实现，例如MPI。
• 线程是进程中的执行单元，是CPU调度的基本单位。一个进程默认会有一个主线程，主线程从入口开始依次执行指令，也可以拥有多个线程，每一个线程从各自的入口开始独立地执行指令（拥有单独的指令执行流）。线程有自己独立的函数调用栈（因此函数内的局部变量是线程私有的），同一个进程中的不同线程共享代码区、堆区和其他资源（全局变量是不同线程共有的）。创建和切换线程，以及线程间的通信比进程间开销更小，但是存在数据竞争等问题。

举个例子：

• 一个可执行文件被执行，就会由系统创建一个进程，分配相应的内存和其他资源，将这个进程理解为一个办公室，里面有一个职员（主线程）正在办公，办公室里面的东西就是进程私有的资源，两个办公室之间有很强的独立性，办公室之间的通讯要通过走廊，因此进程的创建销毁和通讯开销都比较大。
• 什么是多线程？职员本人只能按照顺序一步步干活，这时候他可以申请一个助手（线程），助手和他一起在同一个办公室工作，助手干自己的活（一个单独的指令执行流），助手和职员之间的沟通非常方便，他们共享数据资源（在同一个办公室），缺点就是相互之间可能造成干扰。

硬件篇

现在关注从硬件角度如何理解并行计算。

目前的消费级个人电脑一般只有一个CPU插槽，有且只能有一个CPU。使用多个CPU需要选择专门型号的CPU以及主板等进行适配的，一般仅在高性能计算的服务器中应用，将在最后进行讨论。

对普通电脑进行来说，只有一个CPU（CPU物理数为1），有如下两个易混淆的概念：

• Core核心数（物理核心数）：一个物理CPU所拥有的独立运算单元数量，例如8核CPU代表物理核心数为8。
• Thread线程数（逻辑核心数）：在早期逻辑核心数直接等于物理核心数，但是超线程技术使两者产生了区别，对于使用超线程技术的CPU，一个物理核心可以作为两个逻辑核心来使用，因此逻辑核心数变成了物理核心数的两倍，例如一个8核CPU可以有16个逻辑核心。

一个物理核心就是一个独立的运算单元，有一套寄存器，以及L1、L2私有缓存，可以独立地执行一个任务（一般是线程，代表一个指令执行流），但是同一时刻一个物理核心只能运行一个线程。 物理核心可以在毫秒级的时间尺度上快速切换不同任务的线程。这里的切换并不一定只能切换同一个进程中的不同线程，也可以是不同进程的线程之间切换，但是付出的代价要大一点。

超线程技术是对上述基本情况的进一步性能压榨：一个物理核心在执行一个线程时并不能充分利用所有的计算资源，因此可以选择给它分配两个线程。 如果这两个线程当前使用的计算资源并不冲突，那么就可以同时执行（并行），否则只是并发地执行。为了描述的方便，下文都忽略超线程的情况。

从最简单的单核CPU开始：

• 对于单核CPU，因为只有一个独立运算单元，系统中的所有进程（所有线程）只能被唯一的核心并发执行，虽然核心可以快速切换不同的执行流，但是这只是并发，不是真正的并行。
• 对于多核CPU，由于有多个独立计算单元，系统中的所有进程会被分配给不同的核心执行，实现真正的并行执行；如果一个进程有多个线程，那么这些线程也可能在同一时刻被分配给不同的核心来实现并行计算。

这里实际还存在内核态线程和用户态线程的区别，后者实际是无法被分配到不同核心的，但是目前的主流多线程工具（pthread等）都是基于内核态线程实现的，因此直接忽略后者即可。

目前消费级的个人电脑都是使用一个多核CPU，因此这里的讨论到此为止。

软件篇

现在关注编程中如何使用硬件进行串行和并行计算，使用C/C++进行说明。

在科学计算中，可以使用并行来提高效率，多进程和多线程是实现并行计算的不同途径，它们各有优劣，例如OpenMP采用的是多线程，MPI采用的是多进程（还支持每一个进程位于不同的计算结点上，MPI负责在不同计算节点之间的通讯）

我们直接编写的C/C++程序通常只是一个串行程序，在执行时只有一个进程，并且进程只有一个主线程， 依次执行对应的指令直到程序结束（主要是从进入main函数到退出main函数）。

串行c++程序示例如下

#include <iostream>
#include <vector>

int main() {
    int n = 1000000;
    std::vector<int> data(n, 1);  // 初始化一个大小为n的数组，所有元素为1
    long long sum = 0;

    for(int i = 0; i < n; ++i) {
        sum += data[i] * data[i];  // 计算平方和
    }

    std::cout << "Sum of squares: " << sum << std::endl;
    return 0;
}

我们可以使用最基础的多线程库来手动创建多线程程序，例如Linux系统的pthread和C++标准库提供的std::thread，也可以使用OpenMP、TBB等多线程库，它针对并行计算进行了一些封装和定制语法支持，在使用时不需要手动创建和管理线程。

注意这里的std::thread是跨平台的，但是要求至少C++11。OpenMP依赖于编译器支持，因为在代码中使用了特殊的指令；TBB需要额外的运行库。

使用std::thread的多线程c++程序如下

#include <iostream>
#include <vector>
#include <thread>

void partial_sum(const std::vector<int>& data, long long& result, int start, int end) {
    result = 0;
    for (int i = start; i < end; ++i) {
        result += data[i] * data[i];
    }
}

int main() {
    int n = 1000000;
    std::vector<int> data(n, 1);
    long long sum1 = 0, sum2 = 0;

    // 创建两个线程来计算数组的平方和
    std::thread t1(partial_sum, std::ref(data), std::ref(sum1), 0, n / 2);
    std::thread t2(partial_sum, std::ref(data), std::ref(sum2), n / 2, n);

    t1.join();
    t2.join();

    long long total_sum = sum1 + sum2;
    std::cout << "Sum of squares (multithreaded): " << total_sum << std::endl;

    return 0;
}

使用OpenMP的多线程c++程序如下（OpenMP的最大优势是在原有串行基础上加上一些小改动即可实现并行）

#include <iostream>
#include <vector>
#include <omp.h>

int main() {
    int n = 1000000;
    std::vector<int> data(n, 1);
    long long sum = 0;

    #pragma omp parallel for reduction(+:sum)
    for (int i = 0; i < n; ++i) {
        sum += data[i] * data[i];
    }

    std::cout << "Sum of squares (OpenMP): " << sum << std::endl;
    return 0;
}

在编译时需要特殊的编译选项

g++ -fopenmp -o omp_program omp_program.cpp

对于多进程程序，通常需要使用MPI框架来完成，它可以实现不同进程之间的通信：

• 进程间通信：如果这些进程都在当前机器中，通常会使用消息队列等方式进行通信；
• 跨节点通信：如果这些进程分布在多个机器节点中，那么跨节点的通信会通过网络实现（通常是高速网络）。

使用MPI的多进程c++程序如下

#include <iostream>
#include <vector>
#include <mpi.h>

int main(int argc, char* argv[]) {
    MPI_Init(&argc, &argv);

    int world_size, world_rank;
    MPI_Comm_size(MPI_COMM_WORLD, &world_size);
    MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);

    int n = 1000000;
    int local_n = n / world_size;  // 每个进程处理的数组大小
    std::vector<int> local_data(local_n, 1);
    long long local_sum = 0;

    // 每个进程计算自己部分的数据
    for (int i = 0; i < local_n; ++i) {
        local_sum += local_data[i] * local_data[i];
    }

    long long total_sum = 0;
    MPI_Reduce(&local_sum, &total_sum, 1, MPI_LONG_LONG, MPI_SUM, 0, MPI_COMM_WORLD);

    if (world_rank == 0) {
        std::cout << "Sum of squares (MPI): " << total_sum << std::endl;
    }

    MPI_Finalize();
    return 0;
}

使用MPI的程序在编译时需要使用专门的编译器，在运行时也需要专门的启动方式，编译和启动命令如下

mpic++ -o mpi_program mpi_program.cpp
mpirun -np 4 ./mpi_program

这里使用的都是GNU编译器所对应的编译命令，如果使用的是MSVC，或者Intel编译器，对应的编译命令可能会略有不同。

一种更复杂的并行程序是同时使用多线程和多进程，经典的做法是OpenMP+MPI，示例c++程序如下

#include <iostream>
#include <vector>
#include <mpi.h>
#include <omp.h>

int main(int argc, char* argv[]) {
    MPI_Init(&argc, &argv);

    int world_size, world_rank;
    MPI_Comm_size(MPI_COMM_WORLD, &world_size);
    MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);

    int n = 1000000;
    int local_n = n / world_size;  // 每个进程处理的数据大小
    std::vector<int> local_data(local_n, 1);
    long long local_sum = 0;

    // OpenMP 并行化每个进程内部的计算
    #pragma omp parallel for reduction(+:local_sum)
    for (int i = 0; i < local_n; ++i) {
        local_sum += local_data[i] * local_data[i];
    }

    long long total_sum = 0;
    MPI_Reduce(&local_sum, &total_sum, 1, MPI_LONG_LONG, MPI_SUM, 0, MPI_COMM_WORLD);

    if (world_rank == 0) {
        std::cout << "Sum of squares (MPI + OpenMP): " << total_sum << std::endl;
    }

    MPI_Finalize();
    return 0;
}

编译和运行命令如下

mpic++ -fopenmp -o hybrid_program hybrid_program.cpp
mpirun -np 4 ./hybrid_program

除了上面提到几种经典的并行技术，还有利用GPU的CUDA，它提供了不一样的并行计算的方式，这里不作讨论。 并行相比于串行也不是百利而无一害的，虽然计算效率可以极大提升，但是随之而来的缺点就是编程难度的增大，对程序的错误进行调试非常困难。

进阶篇

前面讨论的都是在个人电脑中的情况，只有一个机器，一个CPU，因此对应的机制比较简单。 现在我们要讨论的目标是：多核CPU + 多CPU + 多机器集群，当前集群的信息如下：

• 一个管理节点（登陆节点）
• 二十个计算节点

二十个计算节点的硬件信息如下：每个节点有2个CPU，每个CPU有14个核或8个核

首先解决对于多CPU的理解，一个简单的理解方式为：操作系统并不会区分物理核心是否来自不同的CPU， 而是直接将所有的物理核心进行统一的资源管理，因此多核CPU与多个CPU看起来并没有什么区别。（当然实际上的开销是不一样的）

对于多个机器组成的集群，不同机器执行的程序默认是没有联系的，无论这些程序是多线程还是多进程等。 在集群上需要解决两个主要问题：计算任务和资源的调度分配，跨节点的并行计算。 通常使用PBS完成调度分配，使用MPI完成支持跨节点的多进程并行计算。

例如下面的PBS作业启动32个进程，在PBS脚本中申请相应的计算资源

#!/bin/bash
#PBS -N mpi_demo
#PBS -l nodes=4:ppn=8       # 请求 4 个节点，在每个节点使用 8 个核心

cd $PBS_O_WORKDIR           # 切换到作业提交目录

mpirun -np 32 ./mpi_demo    # 启动 MPI 程序

在收到新的计算任务时，PBS系统会根据当前的使用情况和任务需求，自动选择分配合适的计算节点以及对应的核心，更新使用情况记录。

在 PBS 脚本中，非 MPI 命令通常只会在分配的主计算节点上执行一次，而 MPI 命令会根据 PBS 的资源分配在多个节点上启动相应数量的进程。 PBS 通过环境变量（如 $PBS_NODEFILE）将节点信息传递给 MPI，从而正确启动 MPI 程序，使得多个进程可以在不同的节点上并行执行并进行通信。