前綴和計(jì)算在并行計(jì)算中很有用，因?yàn)樵谔幚碡?fù)載平衡問(wèn)題時(shí)，經(jīng)常需要將若干段數(shù)據(jù)重新平分，計(jì)算前綴和通常是一種有效的將數(shù)據(jù)平分的方法。例如在并行基數(shù)排序中，就會(huì)用到了前綴和的計(jì)算。而下面先看看單線程環(huán)境中的串行前綴和計(jì)算。

1、串行前綴和的計(jì)算

如果給定一個(gè)數(shù)列a[n]，令S[k] ＝ a[0]+a[1]+...+a[k]，（k = 0, 1, 2…n-1），數(shù)列S[k]即為數(shù)列a[n]的前綴和。例如下面一列數(shù)據(jù)：

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;

前綴和的計(jì)算非常簡(jiǎn)單，一般地，可以用下面的函數(shù)來(lái)進(jìn)行串行前綴和的計(jì)算：

/**   串行前綴和計(jì)算函數(shù) 
 
  
 
       @param  T * pInput - 輸入數(shù)據(jù)  
 
       @param  T *pOutput - 輸出數(shù)據(jù)（前綴和）    
 
       @param  int nLen - 輸入數(shù)據(jù)長(zhǎng)度      
 
       @return  void - 無(wú) 
 
*/ 
 
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]; 
 
    } 
 
} 

在上面的串行前綴和計(jì)算代碼中可以看出，每次循環(huán)都依賴于上一次循環(huán)的結(jié)果，因此無(wú)法直接對(duì)循環(huán)進(jìn)行并行化，要進(jìn)行并行化則必須修改計(jì)算方法，下面就來(lái)看如何進(jìn)行并行前綴和的計(jì)算。

2、并行前綴和的計(jì)算

前綴和的并行計(jì)算方法有許多種，David Callahan的論文“Recognizing and Parallelizing Bounded Recurrences”中給出了一種適合共享存儲(chǔ)多處理器系統(tǒng)中的有界遞歸計(jì)算的通用方法，前綴和計(jì)算屬于有界遞歸計(jì)算的一個(gè)特例。下面先以一個(gè)實(shí)例來(lái)講解整個(gè)并行計(jì)算的過(guò)程：

例：假設(shè)有4個(gè)處理器要計(jì)算16個(gè)整數(shù)的前綴和，這16個(gè)整數(shù)如下：

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16

第1步，先將上面數(shù)據(jù)平分成4組，每個(gè)處理器各計(jì)算一組數(shù)據(jù)的前綴和，如下所示：

（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步，選取每組數(shù)據(jù)的***一個(gè)數(shù)據(jù)，對(duì)這幾個(gè)數(shù)據(jù)計(jì)算前綴和，如下所示：

（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）

經(jīng)過(guò)這步的計(jì)算后，可以很容易發(fā)現(xiàn)，每組的***一個(gè)數(shù)據(jù)的值已經(jīng)變成了原始數(shù)據(jù)在它所處位置之前（包含本位置）的所有數(shù)據(jù)的和。例如：

36 ＝ 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8

78 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12

第3步：從第2組數(shù)開(kāi)始，將每組中的數(shù)（除***一個(gè)數(shù)外）加上它的前一組數(shù)的***一個(gè)數(shù)，即可得到所有數(shù)的前綴和。如下所示：

 (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）

從上面的計(jì)算過(guò)程可以看出，第1步和第3步都是很容易進(jìn)行并行化計(jì)算，第2步中，由于計(jì)算量非常小，用串行計(jì)算即可，下面給出上面處理過(guò)程的代碼實(shí)現(xiàn)：

#define  MIN_PRARLLEL_PREFIXSUM_COUNT    8192 
 
  
 
/**   并行前綴和計(jì)算函數(shù) 
 
  
 
       @param  T * pInput - 輸入數(shù)據(jù)  
 
       @param  T *pOutput - 輸出數(shù)據(jù)（前綴和）    
 
       @param  int nLen - 輸入數(shù)據(jù)長(zhǎng)度      
 
       @return  void - 無(wú) 
 
*/ 
 
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; 
 
} 

從上面并行前綴和的計(jì)算過(guò)程可以看出，它的計(jì)算量比串行前綴和的計(jì)算增加了差不多一倍，如果考慮程序中的實(shí)際開(kāi)銷，計(jì)算增加量還不止一倍。因此在雙核CPU機(jī)器上，使用并行前綴和計(jì)算沒(méi)有任何意義，只有在超過(guò)4核CPU機(jī)器上，它才有實(shí)用價(jià)值。

Parallel_PrefixSum()函數(shù)中，先是判斷CPU核數(shù)是否小于4，并且判斷了計(jì)算量是否不足，如果兩個(gè)判斷條件中有任何一個(gè)滿足，則調(diào)用串行前綴核計(jì)算函數(shù)進(jìn)行計(jì)算，然后才進(jìn)行并行前綴和的計(jì)算。在并行計(jì)算時(shí)只是簡(jiǎn)單地將計(jì)算平攤到各個(gè)CPU上，沒(méi)有考慮CPU核數(shù)較多情況下計(jì)算量平攤到各個(gè)CPU核上，線程粒度過(guò)小的問(wèn)題，主要是為了不使代碼看起來(lái)過(guò)于繁瑣。如有需要可以修改成自動(dòng)計(jì)算出最合適的線程數(shù)量（可能小于CPU核數(shù)），然后并行計(jì)算時(shí)使用相應(yīng)的線程數(shù)量即可。

原文鏈接：http://blog.csdn.net/drzhouweiming/article/details/3164974