日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

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

成都創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供張灣網(wǎng)站建設(shè)、張灣做網(wǎng)站、張灣網(wǎng)站設(shè)計、張灣網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計與制作、張灣企業(yè)網(wǎng)站模板建站服務(wù)，10年張灣做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。

1、串行前綴和的計算

如果給定一個數(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;

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

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

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

2、并行前綴和的計算

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

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

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

第1步，先將上面數(shù)據(jù)平分成4組，每個處理器各計算一組數(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ù)的***一個數(shù)據(jù)，對這幾個數(shù)據(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)過這步的計算后，可以很容易發(fā)現(xiàn)，每組的***一個數(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ù)開始，將每組中的數(shù)（除***一個數(shù)外）加上它的前一組數(shù)的***一個數(shù)，即可得到所有數(shù)的前綴和。如下所示：

(1 3 610) (5+10 11+10 18+1036)(9+36 19+36 30+3678)  (13+78 27+78 42+78136）

(1  3  6 10)  (15  21  28 36)  (45  55  66 78)  (91  105  120 136）

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

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

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

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

標(biāo)題名稱：多核中的并行前綴和計算
當(dāng)前鏈接：http://www.5511xx.com/article/djoocec.html