多核中的并行前綴和計算
前綴和計算在并行計算中很有用，因為在處理負載平衡問題時，經常需要將若干段數據重新平分，計算前綴和通常是一種有效的將數據平分的方法。例如在并行基數排序中，就會用到了前綴和的計算。而下面先看看單線程環境中的串行前綴和計算。
1、串行前綴和的計算
如果給定一個數列a[n]，令S[k] ＝ a[0]+a[1]+...+a[k]，（k = 0, 1, 2…n-1），數列S[k]即為數列a[n]的前綴和。例如下面一列數據：
a[4] = {1, 2, 3, 4};
其前綴和為
S[0] = a[0] = 1;
S[1] = a[0] + a[1] = 1+ 2 = 3;
S[2] = a[0] + a[1] + a[2] = 1 + 2 + 3 = 6;
S[3] = a[0] + a[1] + a[2] + a[3] = 1 + 2 + 3 + 4 = 10;
前綴和的計算非常簡單，一般地，可以用下面的函數來進行串行前綴和的計算：
- /** 串行前綴和計算函數
- @param T * pInput - 輸入數據
- @param T *pOutput - 輸出數據（前綴和）
- @param int nLen - 輸入數據長度
- @return void - 無
- */
- template <class T>
- void Sequential_PrefixSum(T * pInput, T *pOutput, int nLen)
- {
- int i;
- pOutput[0] = pInput[0];
- for ( i = 1; i < nLen; i++ )
- {
- pOutput[i] = pInput[i] + pOutput[i-1];
- }
- }
在上面的串行前綴和計算代碼中可以看出，每次循環都依賴于上一次循環的結果，因此無法直接對循環進行并行化，要進行并行化則必須修改計算方法，下面就來看如何進行并行前綴和的計算。
2、并行前綴和的計算
前綴和的并行計算方法有許多種，David Callahan的論文“Recognizing and Parallelizing Bounded Recurrences”中給出了一種適合共享存儲多處理器系統中的有界遞歸計算的通用方法，前綴和計算屬于有界遞歸計算的一個特例。下面先以一個實例來講解整個并行計算的過程：
例：假設有4個處理器要計算16個整數的前綴和，這16個整數如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
第1步，先將上面數據平分成4組，每個處理器各計算一組數據的前綴和，如下所示：
（1 2 3 4） （5 6 7 8） （9 10 11 12） （13 14 15 16）
（1 3 6 10） （5 11 18 26） （9 19 30 42） （13 27 42 58）
第2步，選取每組數據的***一個數據，對這幾個數據計算前綴和，如下所示：
（1 3 6 10） （5 11 18 26） （9 19 30 42） （13 27 42 58）
（1 3 6 10） （5 11 18 36） （9 19 30 78） （13 27 42 136）
經過這步的計算后，可以很容易發現，每組的***一個數據的值已經變成了原始數據在它所處位置之前（包含本位置）的所有數據的和。例如：
36 ＝ 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8
78 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12
第3步：從第2組數開始，將每組中的數（除***一個數外）加上它的前一組數的***一個數，即可得到所有數的前綴和。如下所示：
(1 3 6 10) (5+10 11+10 18+10 36) (9+36 19+36 30+36 78) (13+78 27+78 42+78 136）
(1 3 6 10) (15 21 28 36) (45 55 66 78) (91 105 120 136）
從上面的計算過程可以看出，第1步和第3步都是很容易進行并行化計算，第2步中，由于計算量非常小，用串行計算即可，下面給出上面處理過程的代碼實現：
- #define MIN_PRARLLEL_PREFIXSUM_COUNT 8192
- /** 并行前綴和計算函數
- @param T * pInput - 輸入數據
- @param T *pOutput - 輸出數據（前綴和）
- @param int nLen - 輸入數據長度
- @return void - 無
- */
- template<class T>
- void Parallel_PrefixSum(T * pInput, T *pOutput, int nLen)
- {
- int i;
- int nCore = omp_get_num_procs();
- if ( nCore < 4 || nLen < MIN_PRARLLEL_PREFIXSUM_COUNT )
- {
- Sequential_PrefixSum(pInput, pOutput, nLen);
- return;
- }
- int nStep = nLen / nCore;
- if ( nStep * nCore < nLen )
- {
- nStep += 1;
- }
- #pragma omp parallel for num_threads(nCore)
- for ( i = 0; i < nCore; i++ )
- {
- int k;
- int nStart = i * nStep;
- int nEnd = (i+1) * nStep;
- if ( nEnd > nLen )
- {
- nEnd = nLen;
- }
- pOutput[nStart] = pInput[nStart];
- for ( k = nStart+1; k < nEnd; k++ )
- {
- pOutput[k] = pInput[k] + pOutput[k-1];
- }
- }
- for ( i = 2; i < nCore; i++ )
- {
- pOutput[i * nStep - 1] += pOutput[(i-1) * nStep - 1];
- }
- pOutput[nLen-1] += pOutput[(nCore-1)*nStep - 1];
- #pragma omp parallel for num_threads(nCore-1)
- for ( i = 1; i < nCore; i++ )
- {
- int k;
- int nStart = i * nStep;
- int nEnd = (i+1) * nStep - 1;
- if ( nEnd >= nLen )
- {
- nEnd = nLen - 1;
- }
- for ( k = nStart; k < nEnd; k++ )
- {
- pOutput[k] += pOutput[nStart-1];
- }
- }
- return;
- }
從上面并行前綴和的計算過程可以看出，它的計算量比串行前綴和的計算增加了差不多一倍，如果考慮程序中的實際開銷，計算增加量還不止一倍。因此在雙核CPU機器上，使用并行前綴和計算沒有任何意義，只有在超過4核CPU機器上，它才有實用價值。
Parallel_PrefixSum()函數中，先是判斷CPU核數是否小于4，并且判斷了計算量是否不足，如果兩個判斷條件中有任何一個滿足，則調用串行前綴核計算函數進行計算，然后才進行并行前綴和的計算。在并行計算時只是簡單地將計算平攤到各個CPU上，沒有考慮CPU核數較多情況下計算量平攤到各個CPU核上，線程粒度過小的問題，主要是為了不使代碼看起來過于繁瑣。如有需要可以修改成自動計算出最合適的線程數量（可能小于CPU核數），然后并行計算時使用相應的線程數量即可。
原文鏈接：http://blog.csdn.net/drzhouweiming/article/details/3164974
