# OpenMP 简介

# 简介

# 什么是 OpenMP？

OpenMP（Open Multi-Processing）是一种广泛应用的多线程并行编程模型，它为共享内存系统上的并行计算提供了丰富的指令集和 API。起源于 1997 年，OpenMP 由多个领先硬件和软件供应商共同制定标准，旨在简化并行程序的设计与实现过程，以充分利用现代多核处理器的计算能力。

OpenMP 支持多种编程语言，包括 C、C++ 以及 Fortran 等，并通过在源代码中插入特定的编译指示（pragma），使得开发者能够轻松地将串行代码转化为高效的并行代码。其主要优势在于其简洁性和易用性，允许程序员使用熟悉的编程语言和开发环境，同时提供良好的可移植性和扩展性。

OpenMP 由非营利性组织管理，由多家软硬件厂家参与，包括 Arm，IBM，Intel，AMD，NVIDIA，Cray，Oracle 等。

# 历史版本

• 在 官网页面 可以查询到 OpenMP 的历史版本和发布日期。

# 基础知识

# 技术框架

OpenMP Runtime Library 是 OpenMP 规范中定义的一组函数和运行时支持结构，它是 OpenMP 并行编程框架的关键组成部分。这个库在编译器的支持下与用户程序链接，在程序执行时负责管理线程的创建、同步、调度以及数据共享等任务。它实现了 OpenMP 编译指导所指示的所有并行化机制。

OpenMP Runtime Library 包括了如下功能：

• 线程管理（创建、销毁、同步） = 工作共享（动态工作分配给各个线程） = 任务调度 = 同步原语（如 barriers, locks, atomic operations） = 动态调整线程数量
• 内存模型支持（数据环境变量、private, shared, reduction 变量等）

Compiler Directives 编译指导是以 #pragma omp 开头的预处理器指令，程序员在源代码中插入这些指令来指导编译器如何将串行程序转换为并行程序。例如，使用 #pragma omp parallel 指令定义一个并行区域，编译器会在此区域内生成多线程执行逻辑。

Environment Variables 环境变量是 OpenMP 运行时库的一部分，它们用于控制运行时行为，例如线程数量、调度策略等。

OpenMP Library 是一组函数库，包括了一些用于线程同步、原子操作、锁、并行循环等的函数。这些函数可以在用户程序中直接调用，以实现更细粒度的并行化。

总的来说，OpenMP 技术框架包括了编译器指导、运行时库、环境变量和函数库等多个组成部分，它们共同构成了一个完整的并行编程环境，共同协作以支持在共享内存系统上的并行编程。

# 执行模型：Fork-Join Model

OpenMP 的执行模型采用的是 Fork-Join 机制，这是一种用于并行编程中的同步原语模型。在该模型下，程序执行遵循以下步骤：

1. Fork（派生）阶段： 程序开始时以单个主线程执行，当遇到 OpenMP 编译指导（pragma）指示的并行区域时，主线程会通过 Runtime Library 创建一个或多个工作线程（worker threads）。这些工作线程是对主线程的派生，每个线程负责执行并行区域内的部分任务。并行区域可以是循环、段（sections）、单一任务或其他可并行化的代码块。

2. Parallel Execution（并行执行）阶段： 创建出的工作线程独立并发地执行分配给它们的任务，并且能够访问共享的数据结构。OpenMP 提供了一套丰富的指令来管理数据的同步和通信，确保在多线程环境下的正确性和一致性。

3. Join（合并）阶段： 当所有工作线程完成其在并行区域内的任务后，它们会自动或者通过显式同步指令（如 omp barrier ）汇聚到 join 点。在此阶段，所有线程等待直至所有其他线程都到达了同步点，随后 join 操作发生。这意味着主线程和其他工作线程重新同步，恢复为串行执行模式或继续执行后续的非并行代码。

4. Synchronization and Data Consistency（同步与数据一致性）： Fork-Join 模型确保了在并行执行过程中，通过适当的锁机制、原子操作和同步原语保证了对共享资源的互斥访问以及数据的一致性。

总结来说，OpenMP 的 Fork-Join 执行模型是一种基于动态线程创建和同步的并行处理框架，它允许开发者方便地将串行代码转化为并行执行的代码片段，同时简化了并行编程中常见的复杂性，如线程管理和数据同步问题。

# 线程与进程

• 进程

  • 每个进程都有自己独立的地址空间
  • CPU 在进程间切换时需要进行上下文切换

• 线程

  • 一个进程下的线程共享相同的地址空间
  • CPU 在线程之间切换开销较小

• 操作系统的线程设计

  • 现代操作系统如 Linux、Windows 等都支持一个进程下有多个线程。
  • 线程是操作系统调度的基本单位，进程是资源分配的基本单位。

# 线程的硬件调度

• 硬件调度机制与操作系统协同，负责将线程智能地映射至可用的 CPU 物理核心上执行。
• 因此，在多线程应用中，当活跃线程数超过了实际 CPU 物理核心的数量时，操作系统将不得不进行密集的上下文切换，以确保多个线程在有限的核心资源上交替运行，这种线程竞争过载的现象会导致整体性能瓶颈和效率下降。
• 超线程技术（Hyper-Threading） 通过在单个物理 CPU 核心上虚拟化出额外的逻辑处理单元，当前通常配置为每个物理核心承载两个逻辑核心。这些逻辑核心能够并行执行独立的任务流，尽管它们共享同一物理核心的基础计算资源，如执行引擎、缓存和其他底层硬件结构。通过这种方式，超线程旨在提高资源利用率和并发处理能力，尤其是在存在大量并行任务且其对计算资源需求相对较小的情况下，可以有效提升系统的总体吞吐量。然而，在某些高度依赖单一核心性能或内存带宽的应用场景下，如部分对 CPU 敏感的游戏或特定类型的数据密集型运算，增加逻辑核心可能并不一定能带来显著的性能提升。

# 硬件的内存模型

• 在现代多核处理器体系结构中，每个 CPU 核心为了进一步提升数据访问速度，在与主存之间设计有多级缓存层次结构。最靠近 CPU 核心的是 L1 缓存，通常其后是 L2 缓存，部分高端架构还包含 L3 缓存，这些高速缓存层级存储容量逐层增大，但访问延迟逐层增加。
• L1 和 L2 缓存通常是与特定 CPU 核心紧密耦合且私有的，这意味着每个核心拥有自己的独立缓存空间，以降低数据访问冲突并提高缓存命中率。L1 缓存由于距离计算单元最近，其访问速度最快，但容量最小；而 L2 缓存作为 L1 缓存的有效补充，具有相对较大的容量。
• 为确保在多核环境中不同 CPU 核心的缓存中对共享数据的一致性，硬件和操作系统共同实现了缓存一致性协议（如 MESI 协议）。这种机制允许系统自动维护一个全局一致的数据视图，即使数据在多个核心的缓存中存在副本也能保证它们同步更新，这一特性在某些架构中被称作 ccNUMA（cache-coherent non-uniform memory access） ，即缓存一致性非统一内存访问。
• 然而，这种缓存一致性管理也带来了一些挑战，其中之一就是“伪共享”(False Sharing)问题。当不同的线程修改位于同一缓存行内的各自独立变量时，尽管这些变量本身并无关联，但由于它们物理上相邻而被存储在同一缓存行内，因此任何针对其中一个变量的写操作都会导致整个缓存行失效并在所有核心间重新同步。这会引发不必要的缓存无效化与重新填充操作，从而显著降低性能。解决伪共享问题通常需要精心设计数据布局或利用缓存行对齐等技术手段来避免无关数据之间的争用。

# 线程亲和性和线程绑定

• 线程亲和性（Thread Affinity）是指操作系统或应用程序控制特定线程与处理器核心之间关联的能力。在多核或多处理器系统中，线程亲和性允许程序员或调度器决定将某个线程固定在特定的 CPU 核心上运行，而不是让操作系统自由地在所有可用的核心间进行动态调度。这种机制有助于减少上下文切换开销，提高缓存命中率，并且对于需要保持数据局部性的并行计算任务特别有益。
• 线程绑定（Thread Pinning）是实现线程亲和性的具体技术手段，它指明了将特定线程与特定硬件资源（如 CPU 核心或 NUMA 节点）之间的强制关联。通过线程绑定，可以确保指定的线程始终在其分配的核心上执行，避免被操作系统迁移到其他核心，从而优化性能、减少延迟并解决伪共享等问题。在 OpenMP 等并行编程模型中，可以通过相关的环境变量或编译指导来设置线程绑定策略，以适应不同的并行计算需求和硬件特性。
• 同一个插槽上的 CPU 对 L3 缓存的访问延迟是一致的，但不同插槽上的 CPU 对 L3 缓存的访问延迟是不一致的。因此，线程绑定的目的是为了减少线程在不同 CPU 之间的迁移，从而减少访存延迟。

• OpenMP 支持控制线程的绑定
  • 环境变量 OMP_PROC_BIND 或从句 proc_bind(master|close|spread) 控制线程绑定与否，以及线程对于绑定单元（称为 place）分布

# OpenMP 编程

# 安装

对于 Linux 系统，GCC 是常用的编译器，现代版本的 GCC 一般已默认支持 OpenMP。例如在 Ubuntu 20.04 LTS 上，可以通过以下命令安装含有 OpenMP 的 build-essential 包：

$ sudo apt-get update
$ sudo apt-get install -y build-essential

• 查看 OpenMP 版本

$ echo |cpp -fopenmp -dM |grep -i open
#define _OPENMP 201511

# 编译使用

• 直接在编译语句中添加 -fopenmp 选项即可开启 OpenMP 支持。

g++ -O2 -std=c++17 -fopenmp hello.cpp -o hello

• 如果使用 CMake 构建项目, 加入 -Wunknown-pragmas 选项可以在编译时报告未处理的 #pragma 指令。

find_package(OpenMP REQUIRED)
add_compile_options(-Wunknown-pragmas)

add_executable(hello hello.cpp)
target_link_libraries(hello PRIVATE OpenMP::OpenMP_CXX)

# Hello World!

• 第一个 OpenMP 程序

#include <omp.h>
#include <stdio.h>

int main() {
  #pragma omp parallel num_threads(8)
  {
    int id = omp_get_thread_num();
    int num_threads = omp_get_num_threads();
    printf("Hello World from thread %d of %d \n", id, num_threads);
  }
  return 0;
}

• 运行结果

$ gcc -fopenmp hello.c -o hello
$ ./hello
Hello World from thread 7 of 8
Hello World from thread 6 of 8
Hello World from thread 0 of 8
Hello World from thread 3 of 8
Hello World from thread 1 of 8
Hello World from thread 2 of 8
Hello World from thread 5 of 8
Hello World from thread 4 of 8

• 同一类 openmp 制导语句称为一种构造(construct)
• 形式为 #pragma omp <directive name> <clause>
• 使用 {} 包裹的代码块称为并行区域(parallel region)

# 线程数设置

• 优先级由低到高
  • 什么都不做，系统选择运行线程数
  • 设置环境变量 export OMP_NUM_THREADS=4
  • 代码中使用库函数 void omp_set_num_threads(int)
  • 通过制导语句 num_threads(4)
  • if 从句判断串行还是并行执行

# 常用库函数

• 设置并行区运行线程数：void omp_set_num_threads(int)
• 获取并行区运行线程数：int omp_get_num_threads()
• 获取当前线程编号：int omp_get_thread_num()
• 获得 OpenMP Wall Clock 时间（单位：秒）：double omp_get_wtime()
• 获得时间精度：double omp_get_wtick()

# Parallel 构造

支持的从句

• if(scalar_expression)：如果 scalar_expression 为真，则并行执行，否则串行执行。
• num_threads(integer_expression)：指定并行区域中的线程数。
• default(shared|none)：指定变量的默认共享性。
  • shared：所有变量默认为共享。
  • none：无默认变量类型，每个变量都需要显式声明共享或私有。
• shared(list)：指定共享变量列表。
  • 共享变量在内存中只有一份，所有线程都可以访问。
  • 请保证共享变量访问不会冲突。
  • 不特别指定并行区变量默认为 shared。
• private(list)：指定私有变量列表。
  • 私有变量在每个线程中都有一份独立的拷贝。
  • 变量需要 重新初始化。
• firstprivate(list)：指定首次私有变量列表。
  • 同 private
  • 对变量根据主线程中的数据进行初始化。

注释

示例 1： no clause、private、firstprivate

int results[4];
int cnt;
cnt = 1;

#pragma omp parallel num_threads(4)
{
    int tid = omp_get_thread_num();
    for (int i = 0; i < 4; i++) {
        cnt += 1;
    }
    results[tid] = cnt;
}

printf("no clause: ");
for (int i = 0; i < 4; i++) {
    printf("%d ", results[i]);
}
printf("\n");

cnt = 1;

#pragma omp parallel num_threads(4) private(cnt)
{
    int tid = omp_get_thread_num();
    for (int i = 0; i < 4; i++) {
        cnt += 1;
    }
    results[tid] = cnt;
}

printf("private(not init): ");
for (int i = 0; i < 4; i++) {
    printf("%d ", results[i]);
}
printf("\n");

cnt = 1;

#pragma omp parallel num_threads(4) firstprivate(cnt)
{
    int tid = omp_get_thread_num();
    for (int i = 0; i < 4; i++) {
        cnt += 1;
    }
    results[tid] = cnt;
}

printf("firstprivate: ");
for (int i = 0; i < 4; i++) {
    printf("%d ", results[i]);
}
printf("\n");

• 打印结果

no clause: 5 9 13 17
private(not init): 4 1572916964 1572916964 1572916964
firstprivate: 5 5 5 5

# For 构造

• 最常用的并行化构造之一

注释

示例 2：并行化 for 循环

#pragma omp parallel num_threads(8)
{
    int tid = omp_get_thread_num();
    int num_threads = omp_get_num_threads();
    #pragma omp for
    for (int i = 0; i < num_threads; i++) {
        #pragma omp ordered
        printf("Hello from thread %d of %d \n", tid, num_threads);
    }
}

• 打印结果

Hello from thread 0 of 8
Hello from thread 1 of 8
Hello from thread 2 of 8
Hello from thread 3 of 8
Hello from thread 4 of 8
Hello from thread 5 of 8
Hello from thread 6 of 8
Hello from thread 7 of 8

• 在并行区内对 for 循环进行线程划分，且 for 循环满足格式要求
  • init-expr:需要是 var=lb 形式，类型也有限制
  • test-expr:限制为 var relational-opb 或者 b relational-op var
  • incr-expr:仅限加减法

# Parallel for 构造

• 常常将 parallel 和 for 结合使用，合并为 parallel for 制导语句

• lastprivate(list)

  • 同 private
  • 执行完 for 循环后，将最后一个线程的值赋给主线程的变量。

• nowait：取消代码块结束时的栅栏同步(barrier)

• collapse(n)：应用于 n 重循环，合并(展开)循环

  • 注意循环之间是否有数据依赖

• ordered：声明有潜在的顺序执行部分

  • 使用 #pragma omp ordered 标记顺序执行代码(搭配使用)
  • ordered 区内的语句任意时刻仅由最多一个线程执行

• shedule(type[,chunk])

  • type：指定循环迭代的调度策略
    • static：静态调度，chunk 大小固定（默认 n/p ）
    • dynamic：动态调度，chunk 大小固定（默认为 1）
    • guided：引导调度，chunk 大小动态调整
    • runtime：由系统环境变量 OMP_SCHEDULE 指定
    • auto：自动调度
  • chunk：指定每个线程获取的迭代次数

# 特殊的数据从句：Reduction

在 OpenMP 中，reduction 是一种并行编程技术，用于解决多线程环境下的数据竞争问题，特别是在计算全局变量的累加或类似操作时。当多个线程需要同时修改同一个共享变量，并且这些修改可以通过某种二元运算符（如加法、乘法等）将所有线程的结果合并成一个最终结果时，可以使用 reduction 子句。

具体来说，reducton 的执行过程为：

• fork 线程并分配任务
• 每一个线程定义一个私有变量 omp_priv
  • 同 private。
• 各个线程执行计算
• 所有 omp_priv 和 omp_in 一起顺序进行 reduction，写回原变量。

相比之下，atomic 是 OpenMP 提供的另一种同步机制，它确保对单个内存位置的访问在多线程环境中是原子性的，即一次只允许一个线程对该内存位置进行读取或写入操作。通过 #pragma omp atomic 指令，可以保证一条简单的赋值语句（或某些特定类型的读改写操作）在并发环境下不会发生数据竞争。

注释

示例 3：Reduction

int sum = 0;
double start = omp_get_wtime();
#pragma omp parallel for num_threads(8) reduction(+ : sum)
for (int i = 0; i < 100000; i++) {
    sum += i;
}
printf("sum = %d\n", sum);
printf("Reduction time: %.5lf s\n", omp_get_wtime() - start);

// no reduction
sum = 0;
start = omp_get_wtime();
#pragma omp parallel for num_threads(8)
for (int i = 0; i < 100000; i++) {
    #pragma omp atomic
    sum += i;
}
printf("sum = %d\n", sum);
printf("Atomic time: %.5lf s\n", omp_get_wtime() - start);
return 0;

• 打印结果

sum = 704982704
Reduction time: 0.00062 s
sum = 704982704
Atomic time: 0.01021 s

• 两者结果相同，但是 reduction 的执行时间更短，这是因为 reduction 通过为每个线程分配一个私有副本，线程可以在其私有空间内自由地执行归约操作，而不需要在更新全局结果时与其他线程争夺锁资源，加上高效的数据合并方法等。

# 同步构造

# Sections 构造

• 将并行区的代码块划分为多个 section 分配执行。
• 可以搭配 parallel 合成为 parallel sections 构造。
• 每个 section 由一个线程执行
  • 线程数大于 section 数目：部分线程空闲
  • 线程数小于 section 数目：部分线程分配多个 section
• 示例代码：

#pragma omp sections
{
  #pragma omp section
  method1();
  #pragma omp section
  method2();
}

# Barrier 构造

• 在特定位置进行栅栏同步
• 在存在数据依赖的情况下，可以使用 barrier 保证数据的一致性

# Single 构造

• 用于标记只有一个线程执行的代码块，带有隐式的 barrier 同步，可以使用 nowait 取消隐式的 barrier 同步。

# Atomic 构造

• 用于保证对共享变量的原子操作，避免数据竞争。

# False Sharing

• 伪共享简单来说就是指多个线程同时访问同一缓存行的不同部分，导致缓存行的无效化和重新填充，从而降低了程序的性能。
• 不同核心对同一 Cache line 的同时读写会造成严重的冲突，导致改级缓存失效。

• 在 OpenMP 中，解决伪共享的方法主要有：
  • 数据结构对齐 ：通过使用编译器提供的对齐指令或关键字确保相关变量分别处于不同的缓存行中。例如，在 C++中可以使用 alignas 关键字来指定变量的内存对齐方式，确保每个线程的数据独立位于不同的缓存行。
  • 增大缓存行之间的间距 ：在相邻变量之间插入足够的填充空间，使得它们不会出现在同一个缓存行内。
  • 避免无意义的竞争 ：设计算法和数据结构以减少不必要的共享数据访问。如果可能，尽量让线程操作各自独立的数据段。
  • 自定义内存分配 ：使用特殊的内存分配函数，确保分配的连续内存区域对齐到缓存行边界，这样分配给不同线程的数据就不会落在同一缓存行上。
  • 在某些情况下，可以利用特定平台提供的硬件特性或者编译器支持的扩展，比如 Intel 的 __declspec(align(#)) 属性（对于 MSVC）或者 __attribute__((aligned(#)))（对于 GCC/Clang）。
  • 也可以通过控制变量的作用域或者利用动态创建私有副本等技术来间接避免伪共享问题。

# 任务构造

• 除了 Fork-Join 模型外，OpenMP 还支持任务并行模型，通过 task 制导语句来实现。
• 即动态地管理线程池和任务池，线程池中的线程可以动态地获取任务池中的任务进行执行，从而实现任务的并行执行。

注释

示例 4：任务并行

#include <iostream>
#include <omp.h>
#include <unistd.h>
#include <iomanip>

void big_task(int i) {
    sleep(10);
}

void small_task(int i) {
    sleep(1);
}

int main() {
    int ntasks = 8;
    double start = omp_get_wtime();
    #pragma omp parallel
    {
        #pragma omp single
        {
            std::cout << "Task 0 Created" << std::endl;
            #pragma omp task
            big_task(0);

            std::cout << "Task 1 Created" << std::endl;
            #pragma omp task
            big_task(1);

            for (int i = 2; i < ntasks; i++) {
                std::cout << "Task " << i << " Created" << std::endl;
                #pragma omp task
                small_task(i);
            }
        }
        #pragma omp taskwait
    }
    std::cout << "All tasks finished" << std::endl;
    std::cout << "Time: " << std::fixed << std::setprecision(2) << omp_get_wtime() - start << "s" << std::endl;
    return 0;
}

• 运行结果

$ g++ -fopenmp task.cpp -o task
$ ./task
Task 0 Created
Task 1 Created
Task 2 Created
Task 3 Created
Task 4 Created
Task 5 Created
Task 6 Created
Task 7 Created
All tasks finished
Time: 10.00s

• 这段代码中，我们使用了 #pragma omp task 制导语句来创建任务，任务的执行由线程池中的线程动态获取并执行。在任务创建后，我们使用 #pragma omp taskwait 来等待所有任务执行完毕。达到了一个异步执行的效果。

# 向量化：SIMD 构造

• SIMD（Single Instruction, Multiple Data）是一种并行计算模式，它通过一条指令同时对多个数据进行操作，从而实现高效的数据并行计算。
• 在 OpenMP 中，可以使用 #pragma omp simd 制导语句来实现向量化并行计算。
  • aligned 用于列出内存对齐的指针
  • safelen 用于标记循环展开时的数据依赖
  • linear 用于标记循环变量的线性关系
• 编译器例如 gcc 也自带向量化功能，一般使用以下编译选项
  • -O3
  • -ffast-math
  • -fivopts
  • -march=native
  • -fopt-info-vec
  • -fopt-info-vec-missed