CS267 · 第 4 课 · Aydin Buluc

共享内存并行编程（OpenMP）

共享内存编程模型允许多个线程通过读写共享变量进行通信。OpenMP 提供了高层次的指令式接口，让并行编程更加简洁高效。

授课教师：Aydin Buluc

日期：2025-01-30

难度：中等

视频：Lecture 4 Video

共享内存编程模型

基本概念

在共享内存模型中：

程序是线程 (threads) 的集合
每个线程有私有变量（局部栈变量）
所有线程共享共享变量（静态变量、堆内存）
线程通过读写共享变量进行隐式通信
通过同步协调对共享变量的访问

POSIX Threads (Pthreads)

线程创建

#include <pthread.h>

int pthread_create(pthread_t *thread_id,
                   const pthread_attr_t *attr,
                   void *(*thread_fun)(void *),
                   void *fun_arg);

// 等待线程结束
int pthread_join(pthread_t thread, void **retval);

Hello World 示例

void* SayHello(void *foo) {
  printf("Hello, world!\n");
  return NULL;
}

int main() {
  pthread_t threads[16];
  for(int tn = 0; tn < 16; tn++)
    pthread_create(&threads[tn], NULL, SayHello, NULL);
  for(int tn = 0; tn < 16; tn++)
    pthread_join(threads[tn], NULL);
  return 0;
}

Pthreads 的陷阱

线程创建开销大：不适合细粒度并行（单次循环迭代）
数据竞争 (Data Race)：难以调试，可能间歇性出现
死锁 (Deadlock)：多个互斥锁时容易发生

OpenMP 概述

什么是 OpenMP？

OpenMP (Open specification for Multi-Processing) 是一个可移植的、线程化的共享内存编程规范：

主要由编译器指令组成（~80%）
少量库函数（~19%）
环境变量（~1%）
支持 C/C++ 和 Fortran

OpenMP 能做什么？

将程序分为串行区域和并行区域
隐藏栈管理细节
提供同步原语

OpenMP 不能做什么？

不能自动并行化
不能保证加速
不能免除数据竞争

OpenMP 的基本核心 (Common Core)

大多数 OpenMP 程序只需以下 19 个构造：

构造	功能
`#pragma omp parallel`	创建并行区域，生成线程组
`omp_get_thread_num()`	获取线程 ID
`omp_get_num_threads()`	获取线程数
`#pragma omp barrier`	同步屏障
`#pragma omp critical`	临界区（互斥）
`#pragma omp for`	循环并行化（worksharing）
`reduction(op:list)`	归约操作
`schedule(static/dynamic)`	循环调度策略
`private/firstprivate/shared`	数据作用域
`#pragma omp task`	任务并行

OpenMP 编程基础

Hello World in OpenMP

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

int main() {
  #pragma omp parallel
  {
    printf(" hello ");
    printf(" world \n");
  }
}

输出示例（非确定性）：

hello hello world
world
hello  hello world
world

Fork-Join 并行模型

OpenMP 使用 Fork-Join 模型：

主线程 (Master Thread) 顺序执行
遇到并行区域时，Fork 生成一组线程
并行区域结束时，Join 等待所有线程完成
并行性可以逐步添加

并行区域与线程创建

double A[1000];
omp_set_num_threads(4);

#pragma omp parallel
{
  int ID = omp_get_thread_num();
  pooh(ID, A);
}
// 隐式屏障：等待所有线程完成

注意：omp_set_num_threads() 只是"请求"线程数，实际获得的线程数可能更少。使用 omp_get_num_threads() 获取实际值。

数值积分案例：计算 π

串行版本

static long num_steps = 100000;
double step = 1.0 / (double) num_steps;
double sum = 0.0;

for (int i = 0; i < num_steps; i++) {
  double x = (i + 0.5) * step;
  sum += 4.0 / (1.0 + x * x);
}
double pi = step * sum;

并行版本：消除 False Sharing

#define PAD 8  // 假设 L1 cache line 为 64 bytes
double sum[NUM_THREADS][PAD];  // 填充以避免 false sharing

#pragma omp parallel
{
  int id = omp_get_thread_num();
  int nthrds = omp_get_num_threads();
  for (int i = id; i < num_steps; i += nthrds) {
    double x = (i + 0.5) * step;
    sum[id][0] += 4.0 / (1.0 + x * x);
  }
}
// 归约
double pi = 0.0;
for (int i = 0; i < nthreads; i++)
  pi += sum[i][0] * step;

False Sharing 问题

当独立的数据元素位于同一缓存行时，每次更新会导致缓存行在线程间来回"晃动"，严重影响性能。

线程数	朴素 SPMD	填充后
1	1.86s	1.86s
2	1.03s	1.01s
3	1.08s	0.69s
4	0.97s	0.53s

最佳实践：使用 Reduction

#pragma omp parallel
{
  double x;
  #pragma omp for reduction(+:sum)
  for (int i = 0; i < num_steps; i++) {
    x = (i + 0.5) * step;
    sum += 4.0 / (1.0 + x * x);
  }
}
double pi = step * sum;

循环并行化

Worksharing For

#pragma omp parallel
{
  #pragma omp for
  for (int i = 0; i < N; i++) {
    NEAT_STUFF(i);
  }
}

// 简写形式
#pragma omp parallel for
for (int i = 0; i < N; i++) {
  NEAT_STUFF(i);
}

调度策略

调度	描述	适用场景
`static`	编译时确定，块大小固定	每迭代工作量相同
`dynamic`	运行时从队列获取	每迭代工作量差异大
`guided`	块大小递减	介于 static 和 dynamic 之间

Static vs Dynamic 示例

// SpGEMM（稀疏矩阵乘法）的块间工作量差异大
#pragma omp parallel for schedule(dynamic) collapse(2)
for (int i = 0; i < B; i++)
  for (int j = 0; j < B; j++)
    for (int k = 0; k < B; k++)
      SpGEMM(A(i,k), B(k,j), C(i,j));

同步机制

Critical（临界区）

#pragma omp parallel
{
  for (int i = id; i < niters; i += nthrds) {
    double B = big_job(i);
    #pragma omp critical
    res += consume(B);
  }
}

Barrier（屏障）

#pragma omp parallel
{
  Arr[id] = big_ugly_calc(id);
  #pragma omp barrier  // 等待所有线程
  Brr[id] = really_big_and_ugly(id, Arr);
}

Nowait（消除隐式屏障）

#pragma omp parallel
{
  A[id] = big_calc1(id);
  #pragma omp barrier
  #pragma omp for
  for (i = 0; i < N; i++) C[i] = big_calc3(i, A);
  #pragma omp for nowait  // 无隐式屏障
  for (i = 0; i < N; i++) B[i] = big_calc2(C, i);
  A[id] = big_calc4(id);
}

数据作用域

默认规则

共享 (Shared)：全局变量、静态变量、动态分配内存
私有 (Private)：栈变量（函数内局部变量）

修改作用域

子句	行为
`private(var)`	每个线程获得未初始化的副本
`firstprivate(var)`	每个线程获得初始化的副本
`shared(var)`	所有线程共享（仅用于 parallel）
`default(none)`	强制显式声明所有变量作用域

Reduction 操作

操作符	初始值
+	0
*	1
min	最大正数
max	最小负数
&	~0
\|	0

任务并行 (Tasks)

Task 概念

任务是独立的代码块，由线程执行。适合不规则并行（如递归、链表遍历）。

#pragma omp parallel
{
  #pragma omp single  // 一个线程创建任务
  {
    #pragma omp task
    fred();
    #pragma omp task
    daisy();
    #pragma omp taskwait  // 等待子任务完成
    #pragma omp task
    billy();
  }
}

并行斐波那契

int fib(int n) {
  int x, y;
  if (n < 2) return n;
  #pragma omp task shared(x)
  x = fib(n-1);
  #pragma omp task shared(y)
  y = fib(n-2);
  #pragma omp taskwait
  return x + y;
}

int main() {
  #pragma omp parallel
  {
    #pragma omp single
    fib(5000);
  }
}

共享内存硬件与缓存一致性

缓存一致性问题

当多个处理器缓存同一内存位置时，可能出现不一致：

P1 写 u = 7，但只在自己的缓存中
P2 读 u，可能读到旧值 5

Snoopy 缓存一致性协议

基于总线广播：

所有缓存控制器"监听"总线事务
写操作时广播无效化 (invalidate) 或更新
简单但不可扩展（~100 处理器上限）

测验

Q1：OpenMP 的并行模型是什么？

Q2：False Sharing 会导致什么问题？

Q3：Reduction 操作中，操作符 "+" 的初始值是什么？

Q4：什么情况下应该使用 schedule(dynamic)？

Q5：OpenMP 中，private 和 firstprivate 的区别是什么？

要点总结

OpenMP 简洁高效

OpenMP 通过编译器指令实现并行，比 Pthreads 更简洁，适合循环级并行。

注意 False Sharing

False Sharing 会严重降低性能。使用 padding 或 reduction 来避免。

选择合适的调度

工作量相同时用 static，差异大时用 dynamic。collapse 增加并行度。

数据作用域很重要

使用 default(none) 强制显式声明变量作用域，减少 bug。