1、動(dòng)態(tài)設(shè)置并行循環(huán)的線程數(shù)量

在實(shí)際情況中，程序可能運(yùn)行在不同的機(jī)器 環(huán)境里，有些機(jī)器是雙核，有些機(jī)器是4核甚至更多核。并且未來(lái)硬件存在升級(jí)的可能，CPU核數(shù)會(huì)變得越來(lái)越多。如何根據(jù)機(jī)器硬件的不同來(lái)自動(dòng)設(shè)置合適的線 程數(shù)量就顯得很重要了，否則硬件升級(jí)后程序就得進(jìn)行修改，那將是一件很麻煩的事情。

比如剛開始在雙核系統(tǒng)中開發(fā)的軟件，線程數(shù)量缺省都設(shè)成2，那么當(dāng)機(jī)器升級(jí)到4核或8核以后，線程數(shù)量就不能滿足要求了，除非修改程序。

線程數(shù)量的設(shè)置除了要滿足機(jī)器硬件升級(jí)的可擴(kuò)展性外，還需要考慮程序的可擴(kuò)展性，當(dāng)程序運(yùn)算量增加或減少后，設(shè)置的線程數(shù)量仍然能夠滿足要求。顯然這也不能通過設(shè)置靜態(tài)的線程數(shù)量來(lái)解決。

在具體計(jì)算需要使用多少線程時(shí)，主要需要考慮以下兩點(diǎn)：

1）當(dāng)循環(huán)次數(shù)比較少時(shí)，如果分成過多數(shù)量的線程來(lái)執(zhí)行，可能會(huì)使得總運(yùn)行時(shí)間高于較少線程或一個(gè)線程執(zhí)行的情況。并且會(huì)增加能耗。

2）如果設(shè)置的線程數(shù)量遠(yuǎn)大于CPU核數(shù)的話，那么存在著大量的任務(wù)切換和調(diào)度等開銷，也會(huì)降低整體效率。

那么如何根據(jù)循環(huán)的次數(shù)和CPU核數(shù)來(lái)動(dòng)態(tài)地設(shè)置線程的數(shù)量呢？下面以一個(gè)例子來(lái)說明動(dòng)態(tài)設(shè)置線程數(shù)量的算法，假設(shè)一個(gè)需要?jiǎng)討B(tài)設(shè)置線程數(shù)的需求為：

1、 以多個(gè)線程運(yùn)行時(shí)的每個(gè)線程運(yùn)行的循環(huán)次數(shù)不低于4次

2、 總的運(yùn)行線程數(shù)最大不超過2倍CPU核數(shù)

下面代碼便是一個(gè)實(shí)現(xiàn)上述需求的動(dòng)態(tài)設(shè)置線程數(shù)量的例子

const int MIN_ITERATOR_NUM = 4; 
   int ncore = omp_get_num_procs(); //獲取執(zhí)行核的數(shù)量 
   int max_tn = n / MIN_ITERATOR_NUM; 
   int tn = max_tn > 2*ncore ? 2*ncore : max_tn; //tn表示要設(shè)置的線程數(shù)量 
#pragma omp parallel for if( tn > 1) num_threads(tn) 
     for ( i = 0; i < n; i++ ) 
     { 
         printf("Thread Id = %ld/n", omp_get_thread_num()); 
         //Do some work here 
     } 

在上面代碼中，根據(jù)每個(gè)線程運(yùn)行的循環(huán)次數(shù)不低于4次，先計(jì)算出最大可能的線程數(shù)max_tn，然后計(jì)算需要的線程數(shù)量tn，tn的值等于max_tn和2倍CPU核數(shù)中的較小值。

然后在parallel for構(gòu)造中使用if子句來(lái)判斷tn是否大于1，大于1時(shí)使用單個(gè)線程，否則使用tn個(gè)線程，，這樣就使得設(shè)置的線程數(shù)量滿足了需求中的條件。

比如在一個(gè)雙核CPU上，n=64，最終會(huì)以2倍CPU核數(shù)（4個(gè)）線程運(yùn)行，而不會(huì)以max_tn = 64/4＝16個(gè)線程運(yùn)行。

在實(shí)際情況中，當(dāng)然不能每個(gè)循環(huán)都象上面一樣寫幾行代碼來(lái)計(jì)算一遍，可以將其寫成一個(gè)獨(dú)立的功能函數(shù)如下：

const int g_ncore = omp_get_num_procs(); //獲取執(zhí)行核的數(shù)量 
  
/** 計(jì)算循環(huán)迭代需要的線程數(shù)量 
     根據(jù)循環(huán)迭代次數(shù)和CPU核數(shù)及一個(gè)線程最少需要的循環(huán)迭代次數(shù) 
     來(lái)計(jì)算出需要的線程數(shù)量，計(jì)算出的最大線程數(shù)量不超過CPU核數(shù) 
  
     @param   int n - 循環(huán)迭代次數(shù)   
     @param   int min_n - 單個(gè)線程需要的最少迭代次數(shù)    
     @return int - 線程數(shù)量     
*/ 
int dtn(int n, int min_n) 
{ 
   int max_tn = n / min_n; 
   int tn = max_tn > g_ncore ? g_ncore : max_tn; //tn表示要設(shè)置的線程數(shù)量 
   if ( tn < 1 ) 
   { 
        tn = 1; 
   } 
   return tn; 
} 
這樣每次并行化循環(huán)時(shí)就可以直接使用函數(shù)dtn()來(lái)獲取合適的線程數(shù)量，前面的代碼可以簡(jiǎn)寫成如下形式： 
#pragma omp parallel for num_threads(dtn(n, MIN_ITERATOR_NUM)) 
     for ( i = 0; i < n; i++ ) 
     { 
         printf("Thread Id = %ld/n", omp_get_thread_num()); 
         //Do some work here 
     } 

當(dāng)然具體設(shè)置多少線程要視情況而定的，一般情況下線程數(shù)量剛好等于CPU核數(shù)可以取得比較好的性能，因?yàn)榫€程數(shù)等于CPU核數(shù)時(shí)，每個(gè)核執(zhí)行一個(gè)任務(wù)，沒有任務(wù)切換開銷。

2、嵌套循環(huán)的并行化

在嵌套循環(huán)中，如果外層循環(huán)迭代次數(shù)較少時(shí)，如果將來(lái)CPU核數(shù)增加到一定程度時(shí)，創(chuàng)建的線程數(shù)將可能小于CPU核數(shù)。另外如果內(nèi)層循環(huán)存在負(fù)載平衡的情況下，很難調(diào)度外層循環(huán)使之達(dá)到負(fù)載平衡。

下面以矩陣乘法作為例子來(lái)講述如何將嵌套循環(huán)并行化，以滿足上述擴(kuò)展性和負(fù)載平衡需求。

   其實(shí)可以采用一個(gè)簡(jiǎn)單的方法將最外層循環(huán)和第2層循環(huán)合并成一個(gè)循環(huán)，下面便是采用合并循環(huán)后的并行實(shí)現(xiàn)。

void Parallel_Matrix_Multiply(int *a, int row_a, int col_a, 
                     int *b, int row_b,int col_b, 
                     int *c, int c_size ) 
{ 
    if ( col_a != row_b ) 
    { 
        return; 
    } 
  
    int i, j, k; 
    int index; 
    int border = row_a * col_b; 
  
    i = 0; 
    j = 0; 
#pragma omp parallel private(i,j,k) num_threads(dtn(border, 1)) 
    for ( index = 0; index < border; index++ ) 
    { 
        i = index / col_b; 
        j = index % col_b; 
  
        int row_i = i * col_a; 
        int row_c = i * col_b; 
  
        c[row_c+j] = 0; 
        for ( k = 0; k < row_b; k++ ) 
        { 
            c[row_c + j] += a[row_i+k] * b[k*col_b+j]; 
        } 
    } 
} 

從上面代碼可以看出，合并后的循環(huán)邊界border = row_a * col_b;即等于原來(lái)兩個(gè)循環(huán)邊界之積，然后在循環(huán)中計(jì)算出原來(lái)的外層循環(huán)和第2層循環(huán)的迭代變量i和j，采用除法和取余來(lái)求出i和j的值。

需要注意的是，上面求i和j的值必須要保證循環(huán)迭代的獨(dú)立性，即不能有循環(huán)迭代間的依賴關(guān)系。不能將求i和j值的過程優(yōu)化成如下的形式：

if ( j == col_b ) 
{ 
     j = 0; 
     i++; 
} 
// …… 此處代表實(shí)際的矩陣乘法代碼 
j++; 

上面這種優(yōu)化，省去了除法，效率高，但是只能在串行代碼中使用，因?yàn)樗嬖谘h(huán)迭代間的依賴關(guān)系，無(wú)法將其正確地并行化。

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