我正在嘗試使用 OpenMP 并行化以下基數排序演算法 C 代碼，但我對使用 OpenMP 子句有一些疑問。特別是，有一些回圈我懷疑它們是否可以并行化。
這是我正在處理的代碼：
unsigned getMax(size_t n, unsigned arr[n]) {
unsigned mx = arr[0];
unsigned i;
#pragma omp parallel for reduction(max:mx) private(i)
for (i = 1; i < n; i )
if (arr[i] > mx)
mx = arr[i];
return mx;
}
void countSort(size_t n, unsigned arr[n], unsigned exp) {
unsigned output[n]; // output array
int i, count[10] = { 0 };
// Store count of occurrences in count[]
#pragma omp parallel for private(i)
for (i = 0; i < n; i ) {
#pragma omp atomic
count[(arr[i] / exp) % 10] ; }
for (i = 1; i < 10; i )
count[i] = count[i - 1];
// Build the output array
#pragma omp parallel for private(i)
for (i = (int) n - 1; i >= 0; i--) {
#pragma omp atomic write
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
#pragma omp parallel for private(i)
for (i = 0; i < n; i )
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using Radix Sort
void radixsort(size_t n, unsigned arr[n], int threads) {
omp_set_num_threads(threads);
unsigned m = getMax(n, arr);
unsigned exp;
for (exp = 1; m / exp > 0; exp *= 10)
countSort(n, arr, exp);
}
特別是，我不確定for像下面這樣的回圈是否可以并行化：
for (i = 1; i < 10; i )
count[i] = count[i - 1];
#pragma omp parallel for private(i)
for (i = (int) n - 1; i >= 0; i--) {
#pragma omp atomic write
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
我正在尋求有關我應該使用的特定 OMP 條款的幫助；也歡迎對顯示的代碼提出其他意見。
uj5u.com熱心網友回復：
首先，要并行化代碼需要合理的作業量，否則并行開銷大于并行化帶來的收益。在您的示例中絕對是這種情況，因為您output在堆疊上創建陣列（因此它不能足夠大）。對您的代碼的評論：
您在問題中提到的兩個回圈都取決于執行順序，因此它們無法輕松/高效地并行化。另請注意，
count訪問陣列時存在競爭條件。如果您選擇的底數是 2 (
2^k)的冪，則可以擺脫昂貴的整數除法，而可以改用快速按位/移位運算子。始終在所需的最小范圍內定義變數。所以代替
unsigned i;
#pragma omp parallel for reduction(max:mx) private(i)
for (i = 1; i < n; i ) ....
以下代碼是首選：
#pragma omp parallel for reduction(max:mx)
for (unsigned i = 1; i < n; i ) ....
要復制您的陣列，
memcpy可以使用：memcpy(arr,output,n*sizeof(output[0]))在這個回圈中
#pragma omp parallel for private(i)
for (i = 0; i < n; i ) {
#pragma omp atomic
count[(arr[i] / exp) % 10] ; }
您可以使用減少而不是原子操作：
#pragma omp parallel for private(i) reduction( :count[10])
for (i = 0; i < n; i ) {
count[(arr[i] / exp) % 10] ; }
uj5u.com熱心網友回復：
如果拆分資料，基數排序可以并行化。一種方法是對第一遍使用最高有效數字基數排序，以創建多個邏輯箱。例如，如果使用基數 256 (2^8)，您最終會得到 256 個 bin，然后基數排序可以根據系統上的邏輯核心數并行排序。使用 4 個內核，您可以一次對 4 個 bin 進行排序。這依賴于最高有效數字的某種均勻分布，因此 bin 的大小有些相等。
嘗試優化第一遍可能無濟于事，因為您需要原子讀|寫才能更新 bin 索引，并且隨機訪問寫入目標陣列中的任何位置都會產生快取沖突。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/352651.html