OpenMP 教程（一）深入剖析 OpenMP reduction 子句

2022 年 11 月 9 日
筆記
OpenMP

OpenMP 教程（一）深入剖析 OpenMP reduction 子句

前言

在前面的教程OpenMP入門當中我們簡要介紹了 OpenMP 的一些基礎的使用方法，在本篇文章當中我們將從一些基礎的問題開始，然後仔細介紹在 OpenMP 當中 reduction 子句的各種使用方法。

從並發求和開始

我們的任務是兩個執行緒同時對一個變數 data 進行 ++操作，執行 10000 次，我們看下面的程式碼有什麼問題：

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

static int data;

int main() {
  #pragma omp parallel num_threads(2) // 使用兩個執行緒同時執行上面的程式碼塊
  {
    for(int i = 0; i < 10000; i++) {
      data++;
      usleep(10);
    }
    // omp_get_thread_num 函數返回執行緒的 id 號 這個數據從 0 開始，0, 1, 2, 3, 4, ...
    printf("data = %d tid = %d\n", data, omp_get_thread_num());
  }

  printf("In main function data = %d\n", data);
  return 0;
}

在上面的程式碼當中，我們開啟了兩個執行緒並且同時執行 $pragma 下面的程式碼塊，但是上面的程式有一個問題，就是兩個執行緒可能同時執行 data++ 操作，但是同時執行這個操作的話，就存在並發程式的數據競爭問題，在 OpenMP 當中默認的數據使用方式就是🧍‍♂️執行緒之間是共享的比如下面的執行過程：

首先執行緒 1 和執行緒 2 將 data 載入到 CPU 快取當中，當前的兩個執行緒得到的 data 的值都是 0 。
執行緒 1 和執行緒 2 對 data 進行 ++ 操作，現在兩個執行緒的 data 的值都是 1。
執行緒 1 將 data 的值寫回到主存當中，那麼主存當中的數據的值就等於 1 。
執行緒 2 將 data 的值寫回到主存當中，那麼主存當中的數據的值也等於 1 。

但是上面的執行過程是存在問題的，因為我們期望的是主存當中的 data 的值等於 2，因此上面的程式碼是存在錯誤的。

解決求和問題的各種辦法

使用數組巧妙解決並發程式當中的數據競爭問題

在上面的程式當中我們使用了一個函數 omp_get_thread_num 這個函數可以返回執行緒的 id 號，我們可以根據這個 id 做一些文章，如下面的程式：


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

static int data;

static int tarr[2];

int main() {
  #pragma omp parallel num_threads(2)
  {
    int tid = omp_get_thread_num();
    for(int i = 0; i < 10000; i++) {
      tarr[tid]++;
      usleep(10);
    }
    printf("tarr[%d] = %d tid = %d\n", tid, tarr[tid], tid);
  }
  data = tarr[0] + tarr[1];
  printf("In main function data = %d\n", data);
  return 0;
}

在上面的程式當中我們額外的使用了一個數組 tarr 用於保存執行緒的本地的和，然後在最後在主執行緒裡面講執行緒本地得到的和相加起來，這樣的話我們得到的結果就是正確的了。

$./lockfree01.out
tarr[1] = 10000 tid = 1
tarr[0] = 10000 tid = 0
In main function data = 20000

在上面的程式當中我們需要知道的是，只有當並行域當中所有的執行緒都執行完成之後，主執行緒才會繼續執行並行域後面的程式碼，因此主執行緒在執行程式碼

  data = tarr[0] + tarr[1];
  printf("In main function data = %d\n", data);

之前，OpenMP 中並行域中的程式碼全部執行完成，因此上面的程式碼執行的時候數組 tarr 中的結果已經計算出來了，因此上面的程式碼最終的執行結果是 2000。

reduction 子句

在上文當中我們使用數組去避免多個執行緒同時操作同一個數據的情況，除了上面的方法處理求和問題，我們還有很多其他方法去解決這個問題，下面我們使用 reduction 子句去解決這個問題：

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

static int data;

int main() {
  #pragma omp parallel num_threads(2) reduction(+:data)
  {
    for(int i = 0; i < 10000; i++) {
      data++;
      usleep(10);
    }
    printf("data = %d tid = %d\n", data, omp_get_thread_num());
  }

  printf("In main function data = %d\n", data);
  return 0;
}

在上面的程式當中我們使用了一個子句 reduction(+:data) 在每個執行緒裡面對變數 data 進行拷貝，然後在執行緒當中使用這個拷貝的變數，這樣的話就不存在數據競爭了，因為每個執行緒使用的 data 是不一樣的，在 reduction 當中還有一個加號➕，這個加號表示如何進行規約操作，所謂規約操作簡單說來就是多個數據逐步進行操作最終得到一個不能夠在進行規約的數據。

例如在上面的程式當中我們的規約操作是 + ，因此需要將執行緒 1 和執行緒 2 的數據進行 + 操作，即執行緒 1 的 data 加上執行緒 2 的 data 值，然後將得到的結果賦值給全局變數 data，這樣的話我們最終得到的結果就是正確的。

如果有 4 個執行緒的話，那麼就有 4 個執行緒本地的 data（每個執行緒一個 data）。那麼規約（reduction）操作的結果等於：

(((data1 + data2) + data3) + data4) 其中 datai 表示第 i 個執行緒的得到的 data 。

除了後面的兩種方法解決多個執行緒同時對一個數據進行操作的問題的之外我們還有一些其他的辦法去解決這個問題，我們在下一篇文章當中進行仔細分析。

深入剖析 reduction 子句

我們在寫多執行緒程式的時候可能會存在這種需求，每個執行緒都會得到一個數據的結果，然後在最後需要將每個執行緒得到的數據進行求和，相乘，或者邏輯操作等等，在這種情況下我們可以使用 reduction 子句進行操作。redcution 子句的語法格式如下：

reduction(操作符:變數)

當我們使用 reduction 子句的時候執行緒使用的是與外部變數同名的變數，那麼這個同名的變數的初始值應該設置成什麼呢？具體的設置規則如下所示：

運算符	初始值
+/加法	0
*/乘法	1
&&/邏輯與	1
\|\|/邏輯或	0
min/最小值	對應類型的最大值
max/最大值	對應類型的最小值
&/按位與	所有位都是 1
\|/按位或	所有位都是 0
^/按位異或	所有位都是 0

下面我們使用各種不同的例子去分析上面的所有的條目：

加法+操作符

我們使用下面的程式去測試使用加法規約的正確性，並且在並行域當中列印進行並行域之前變數的值。

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

static int data;

int main() {

  #pragma omp parallel num_threads(2) reduction(+:data)
  {
    printf("初始值 : data = %d tid = %d\n", data, omp_get_thread_num());
    if(omp_get_thread_num() == 0) {
      data = 10;
    }else if(omp_get_thread_num() == 1){
      data = 20;
    }
    printf("變化後的值 : data = %d tid = %d\n", data, omp_get_thread_num());
  }
  printf("規約之後的值 : data = %d\n", data);
  return 0;
}

上面的程式的輸出結果如下所示：

初始值 : data = 0 tid = 0
變化後的值 : data = 10 tid = 0
初始值 : data = 0 tid = 1
變化後的值 : data = 20 tid = 1
規約之後的值 : data = 30

從上面的輸出結果我們可以知道當進入並行域之後我們的變數的初始值等於 0 ，第一個執行緒的執行緒 id 號等於 0 ，它將 data 的值賦值成 10 ，第二個執行緒的執行緒 id 號等於 1，它將 data 的值賦值成 20 。在出並行域之前會將兩個執行緒得到的 data 值進行規約操作，在上面的程式碼當中也就是+操作，並且將這個值賦值給全局變數 data 。

乘法*操作符


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

static int data = 2;

int main() {

  #pragma omp parallel num_threads(2) reduction(*:data)
  {
    printf("初始值 : data = %d tid = %d\n", data, omp_get_thread_num());
    if(omp_get_thread_num() == 0) {
      data = 10;
    }else if(omp_get_thread_num() == 1){
      data = 20;
    }
    printf("變化後的值 : data = %d tid = %d\n", data, omp_get_thread_num());
  }
  printf("規約之後的值 : data = %d\n", data);
  return 0;
}

上面的程式輸出結果如下所示：

初始值 : data = 1 tid = 0
變化後的值 : data = 10 tid = 0
初始值 : data = 1 tid = 1
變化後的值 : data = 20 tid = 1
規約之後的值 : data = 400

從上面的程式的輸出結果來看，當我們使用*操作符的時候，我們可以看到程式當中 data 的初始值確實被初始化成了 1 ，而且最終在主函數當中的輸出結果也是符合預期的，因為 400 = 2 * 10 * 20，其中 2 只在全局變數初始化的時候的值。

邏輯與&&操作符


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

static int data = 100;

int main() {

  #pragma omp parallel num_threads(2) reduction(&&:data)
  {
    printf("data =\t %d tid = %d\n", data, omp_get_thread_num());
    if(omp_get_thread_num() == 0) {
      data = 10;
    }else if(omp_get_thread_num() == 1){
      data = 20;
    }
  }
  printf("data = %d\n", data);
  return 0;
}

上面的程式的輸出結果如下所示：

初始化值 : data = 1 tid = 0
初始化值 : data = 1 tid = 1
在主函數當中 : data = 1

從上面的輸出結果我們可以知道，程式當中數據的初始化的值是沒有問題的，你可能會疑惑為什麼主函數當中的 data 值等於 1，這其實就是 C 語言當中對 && 操作服的定義，如果最終的結果為真，那麼值就等於 1，即 100 && 10 && 20 == 1，你可以寫一個程式去驗證這一點。

或||操作符


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

static int data = 100;

int main() {

  #pragma omp parallel num_threads(2) reduction(||:data)
  {
    printf("初始化值 : data = %d tid = %d\n", data, omp_get_thread_num());
    if(omp_get_thread_num() == 0) {
      data = 0;
    }else if(omp_get_thread_num() == 1){
      data = 0;
    }
  }
  printf("在主函數當中 : data = %d\n", data);
  return 0;
}

上面的程式輸出結果如下所示：

初始化值 : data = 1 tid = 0
初始化值 : data = 1 tid = 1
在主函數當中 : data = 1

從上面的結果看出，數據初始化的值是正確的，主函數當中得到的數據也是正確的，因為 100 || 0 || 0 == 1，這個也是 C 語言的條件或得到的結果。

MIN 最小值


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

static int data = 1000;

int main() {

  printf("Int 類型的最大值等於 %d\n", __INT32_MAX__);
  #pragma omp parallel num_threads(2) reduction(min:data)
  {
    printf("data =\t\t     %d tid = %d\n", data, omp_get_thread_num());
    if(omp_get_thread_num() == 0) {
      data = 10;
    }else if(omp_get_thread_num() == 1){
      data = 20;
    }
  }
  printf("data = %d\n", data);
  return 0;
}

上面的程式執行結果如下所示：

Int 類型的最大值等於   2147483647
data =               2147483647 tid = 0
data =               2147483647 tid = 1
data = 10

可以看出來初始化的值是正確的，當我們求最小值的時候，數據被正確的初始化成對應數據的最大值了，然後我們需要去比較這幾個值的最小值，即 min(1000, 0, 20) == 10 ，因此在主函數當中的到的值等於 10。

MAX 最大值


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

static int data = 1000;

int main() {

  #pragma omp parallel num_threads(2) reduction(max:data)
  {
    printf("data = %d tid = %d\n", data, omp_get_thread_num());
    if(omp_get_thread_num() == 0) {
      data = 10;
    }else if(omp_get_thread_num() == 1){
      data = 20;
    }
  }
  printf("data = %d\n", data);
  return 0;
}

上面的程式輸出結果如下所示：

data = -2147483648 tid = 0
data = -2147483648 tid = 1
data = 1000

可以看出程式被正確的初始化成最小值了，主函數當中輸出的數據應該等於 max(1000, 10, 20) 因此也滿足條件。

& 按位與


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

static int data = 15;

int main() {

  #pragma omp parallel num_threads(2) reduction(&:data)
  {
    printf("data = %d tid = %d\n", data, omp_get_thread_num());
    if(omp_get_thread_num() == 0) {
      data = 8;
    }else if(omp_get_thread_num() == 1){
      data = 12;
    }
  }
  printf("data = %d\n", data);
  return 0;
}

上面的程式輸出結果如下：

data = -1 tid = 0
data = -1 tid = 1
data = 8

首先我們需要知道上面幾個數據的比特位表示：

-1 = 1111_1111_1111_1111_1111_1111_1111_1111
8  = 0000_0000_0000_0000_0000_0000_0000_1000
12 = 0000_0000_0000_0000_0000_0000_0000_1100
15 = 0000_0000_0000_0000_0000_0000_0000_1111

我們知道當我們使用 & 操作符的時候初始值是比特為全部等於 1 的數據，也就是 -1，最終進行按位與操作的數據為 15、8、12，即在主函數當中輸出的結果等於 (8 & 12 & 15) == 8，因為只有第四個比特位全部為 1，因此最終的結果等於 8 。

|按位或


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

static int data = 1;

int main() {

  #pragma omp parallel num_threads(2) reduction(|:data)
  {
    printf("data = %d tid = %d\n", data, omp_get_thread_num());
    if(omp_get_thread_num() == 0) {
      data = 8;
    }else if(omp_get_thread_num() == 1){
      data = 12;
    }
  }
  printf("data = %d\n", data);
  return 0;
}

上面的程式輸出結果如下所示：

data = 0 tid = 0
data = 0 tid = 1
data = 13

我們還是需要了解一下上面的數據的比特位表示：

0  = 0000_0000_0000_0000_0000_0000_0000_0000
1  = 0000_0000_0000_0000_0000_0000_0000_0001
8  = 0000_0000_0000_0000_0000_0000_0000_1000
12 = 0000_0000_0000_0000_0000_0000_0000_1100
13 = 0000_0000_0000_0000_0000_0000_0000_1101

執行緒初始化的數據等於 0 ，這個和前面談到的所有的比特位都設置成 0 是一致的，我們對上面的數據進行或操作之後得到的結果和對應的按位或得到的結果是相符的。

^按位異或


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

static int data = 1;

int main() {

  #pragma omp parallel num_threads(2) reduction(^:data)
  {
    printf("data = %d tid = %d\n", data, omp_get_thread_num());
    if(omp_get_thread_num() == 0) {
      data = 8;
    }else if(omp_get_thread_num() == 1){
      data = 12;
    }
  }
  printf("data = %d\n", data);
  return 0;
}

上面的程式的輸出結果如下所示：

data = 0 tid = 0
data = 0 tid = 1
data = 5

各個數據的比特位表示：

0  = 0000_0000_0000_0000_0000_0000_0000_0000
1  = 0000_0000_0000_0000_0000_0000_0000_0001
8  = 0000_0000_0000_0000_0000_0000_0000_1000
12 = 0000_0000_0000_0000_0000_0000_0000_1100
5  = 0000_0000_0000_0000_0000_0000_0000_0101

大家可以自己對照的進行異或操作，得到的結果是正確的。

總結

在本篇文章當中我們主要使用一個例子介紹了如何解決並發程式當中的競爭問題，然後也使用了 reduction 子句去解決這個問題，隨後介紹了在 OpenMP 當中 reduction 各種規約符號的使用！

在本篇文章當中主要給大家介紹了 OpenMP 的基本使用和程式執行的基本原理，在後續的文章當中我們將仔細介紹各種 OpenMP 的子句和指令的使用方法，希望大家有所收穫！

更多精彩內容合集可訪問項目：//github.com/Chang-LeHung/CSCore

關注公眾號：一無是處的研究僧，了解更多電腦（Java、Python、電腦系統基礎、演算法與數據結構）知識。

Tags: OpenMP