OpenMP 入門教程
| 編輯推薦: |
| 本文來自於cnblogs，文章主要介紹了OpenMP迴圈的並行化，管理公有和私有資料以及負載均衡使等相關知識。 |
前兩天(其實是幾個月以前了)看到了程式碼中有 #pragma omp parallel for 一段，感覺好像是 OpenMP，以前看到並行化的東西都是直接躲開，既然躲不開了，不妨研究一下：
OpenMP 是 Open MultiProcessing 的縮寫。OpenMP 並不是一個簡單的函式庫，而是一個諸多編譯器支援的框架，或者說是協議吧，總之，不需要任何配置，你就可以在 Visual Studio 或者 gcc 中使用它了。
我們就分三部分來介紹吧，因為我看的那個英文教程就是分了三部分（哈哈) . 以下翻譯自英特爾的文件
Hello World
把下面的程式碼儲存為 omp.cc
#include <iostream>
#include <omp.h>
int main()
{
#pragma omp parallel for
for (char i = 'a'; i <= 'z'; i++)
std::cout << i << std::endl;
return 0;
}
然後 g++ omp.cc -fopenmp就可以了
入門
迴圈的並行化
OpenMP的設計們希望提供一種簡單的方式讓程式員不需要懂得建立和銷燬執行緒就能寫出多執行緒化程式。為此他們設計了一些pragma，指令和函式來讓編譯器能夠在合適的地方插入執行緒大多數的迴圈只需要在for之前插入一個pragma就可以實現並行化。而且，通過把這些惱人的細節都丟給編譯器，你可以花費更多的時間來決定哪裡需要多執行緒和優化資料結構
下面個這個例子把32位的RGB顏色轉換成8位的灰度資料，你只需要在for之前加上一句pragma就可以實現並行化了
#pragma omp parallel for
for (int i = 0; i < pixelCount; i++) {
grayBitmap[i] = (uint8_t)(rgbBitmap[i].r * 0.229 +
rgbBitmap[i].g * 0.587 +
rgbBitmap[i].b * 0.114);
}
神奇吧，首先，這個例子使用了“work sharing”，當“work sharing”被用在for迴圈的時候，每個迴圈都被分配到了不同的執行緒，並且保證只執行一次。OpenMP決定了多少執行緒需要被開啟，銷燬和建立，你需要做的就是告訴OpenMP哪裡需要被執行緒化。
OpenMP 對可以多執行緒化的迴圈有如下五個要求：
迴圈的變數變數（就是i）必須是有符號整形，其他的都不行。
迴圈的比較條件必須是< <= > >=中的一種
迴圈的增量部分必須是增減一個不變的值（即每次迴圈是不變的）。
如果比較符號是< <=，那每次迴圈i應該增加，反之應該減小
迴圈必須是沒有奇奇怪怪的東西，不能從內部迴圈跳到外部迴圈，goto和break只能在迴圈內部跳轉，異常必須在迴圈內部被捕獲。
如果你的迴圈不符合這些條件，那就只好改寫了
檢測是否支援 OpenMP
#ifndef _OPENMP
fprintf(stderr, "OpenMP not supported");
#endif
避免資料依賴和競爭
當一個迴圈滿足以上五個條件時，依然可能因為資料依賴而不能夠合理的並行化。當兩個不同的迭代之間的資料存在依賴關係時，就會發生這種情況。
// 假設陣列已經初始化為1
#pragma omp parallel for
for (int i = 2; i < 10; i++) {
factorial[i] = i * factorial[i-1];
}
編譯器會把這個迴圈多執行緒化，但是並不能實現我們想要的加速效果，得出的陣列含有錯誤的結構。因為每次迭代都依賴於另一個不同的迭代，這被稱之為競態條件。要解決這個問題只能夠重寫迴圈或者選擇不同的演算法。
競態條件很難被檢測到，因為也有可能恰好程式是按你想要的順序執行的。
管理公有和私有資料
基本上每個迴圈都會讀寫資料，確定那個資料時執行緒之間共有的，那些資料時執行緒私有的就是程式設計師的責任了。當資料被設定為公有的時候，所有的執行緒訪問的都是相同的記憶體地址，當資料被設為私有的時候，每個執行緒都有自己的一份拷貝。預設情況下，除了迴圈變數以外，所有資料都被設定為公有的。可以通過以下兩種方法把變數設定為私有的：
在迴圈內部宣告變數，注意不要是static的
通過OpenMP指令宣告私有變數
// 下面這個例子是錯誤的
int temp; // 在迴圈之外宣告
#pragma omp parallel for
for (int i = 0; i < 100; i++) {
temp = array[i];
array[i] = doSomething(temp);
}
可以通過以下兩種方法改正
// 1. 在迴圈內部宣告變數
#pragma omp parallel for
for (int i = 0; i < 100; i++) {
int temp = array[i];
array[i] = doSomething(temp);
}
// 2. 通過OpenMP指令說明私有變數
int temp;
#pragma omp parallel for private(temp)
for (int i = 0; i < 100; i++) {
temp = array[i];
array[i] = doSomething(temp);
}
Reductions
一種常見的迴圈就是累加變數，對此，OpenMP 有專門的語句
例如下面的程式：
int sum = 0;
for (int i = 0; i < 100; i++) {
sum += array[i]; // sum需要私有才能實現並行化，但是又必須是公有的才能產生正確結果
}
上面的這個程式裡，sum公有或者私有都不對，為了解決這個問題，OpenMP 提供了reduction語句；
int sum = 0;
#pragma omp parallel for reduction(+:sum)
for (int i = 0; i < 100; i++) {
sum += array[i];
}
內部實現中，OpenMP 為每個執行緒提供了私有的sum變數，當執行緒退出時，OpenMP 再把每個執行緒的部分和加在一起得到最終結果。
當然，OpenMP 不止能做累加，凡是累計運算都是可以的，如下表：
迴圈排程
負載均衡是多執行緒程式中對效能影響最大的因素了，只有實現了負載均衡才能保證所有的核心都是忙的，而不會出現空閒時間。如果沒有負載均衡, 有一些執行緒會遠遠早於其他執行緒結束, 導致處理器空閒浪費優化的可能.
在迴圈中，經常會由於每次迭代的相差時間較大和破壞負載平衡。通常可以通過檢查原始碼來發現迴圈的變動可能. 大多數情況下每次迭代可能會發現大概一致的時間，當這個條件不能滿足的時候，你可能能找到一個花費了大概一致時間的子集。例如, 有時候所有偶數迴圈花費了和所有奇數迴圈一樣的時間, 有時候可能前一半迴圈和後一半迴圈花費了相似的時間. 另一方面, 有時候你可能找不到花費相同時間的一組迴圈. 不論如何, 你應該把這些資訊提供給 OpenMP, 這樣才能讓 OpenMP 有更好的機會去優化迴圈.
預設情況下，OpenMP認為所有的迴圈迭代執行的時間都是一樣的，這就導致了OpenMP會把不同的迭代等分到不同的核心上，並且讓他們分佈的儘可能減小記憶體訪問衝突，這樣做是因為迴圈一般會線性地訪問記憶體, 所以把迴圈按照前一半後一半的方法分配可以最大程度的減少衝突. 然而對記憶體訪問來說這可能是最好的方法, 但是對於負載均衡可能並不是最好的方法, 而且反過來最好的負載均衡可能也會破壞記憶體訪問. 因此必須折衷考慮.
OpenMP 負載均衡使用下面的語法
其中kind可以是下面的這些型別, 而 chunk size 則必須是迴圈不變的正整數
例子
#pragma omp parallel for
for (int i = 0; i < numElements; i++) {
array[i] = initValue;
initValue++;
}
顯然這個迴圈裡就有了競態條件, 每個迴圈都依賴於 initValue 這個變數, 我們需要去掉它.
#pragma omp parallel for
for (int i = 0; i < numElements; i++) {
array[i] = initValue + i;
}
這樣就可以了, 因為現在我們沒有讓 initValue 去被依賴
所以, 對於一個迴圈來說, 應該儘可能地把 loop-variant 變數建立在 i 上.