OpenMP基礎----以圖像進行中的問題為例

    OpenMP2.5規範中，對于可以多線程執行的循環有如下5點限制：

1.循環語句中的循環變量必須是有符号整形，如果是無符号整形就無法使用，OpenMP3.0中取消了這個限制

2.循環語句中的比較操作必須是這樣的樣式：loop_variable <,<=,>,>=loop_invariant_interger

3.循環語句中必須是整數加，整數減，加減的數值必須是循環不變量

4.如果比較操作是《，《=，那麼循環變量的值在每次疊代時候必須增加，反之亦然

5.循環必須是單入口，單出口，内部沒有跳轉語句

将循環多線程化所面臨的挑戰

1.循環疊代相關

因為OpenMP編譯指導是對編譯器發出的指令，是以編譯器會将該循環編譯成多線程代碼，但由于循環疊代相關的存在，多線程代碼将不能成功執行。

2.資料競争

3.資料相關（以下假設為語句S2與語句S1存在資料相關）：

相關的種類（相關不等于循環疊代相關）：

1）流相關：S1先寫某一存儲單元，而後S2又讀該單元

2）輸出相關：兩個語句寫同一存儲單元

3）反相關：一個語句先讀一單元，然後另一語句寫該單元

相關産生的方式：

1）S1在循環的一次疊代中通路存儲單元L，S2在随後的一次疊代中通路L（是循環疊代相關）

2）S1和S2在同一循環疊代中通路同一存儲單元L，但S1的執行在S2之前。（非循環疊代相關）

資料競争：

      資料競争可能是由于輸出相關引起的，編譯器不會進行資料競争的檢測，Intel線程檢測器可以檢測資料競争。

用類似于互斥量的機制進行私有化和同步，可以消除資料競争。

#pragma omp parallel for private(x)

       for(i=0;i<80;i++)

       {

         x=sin(i);

         if(x>0.6)x=0.6;

         printf("sin(%d)=%f\n",i,x); 

       }

6.

管理共享資料和私有資料：

private:每個線程都擁有該變量的一個單獨的副本，可以私有的通路

         1）private：說明清單中的每個變量對于每個線程都應該有一個私有副本。這個私有副本用變量的預設值進行初始化

         2）firstprivate:見13資料的Copy-in 和Copy-out

         3）lastprivate:見13資料的Copy-in 和Copy-out

         4）reduction:

         5）threadprivate:指定由每個線程私有的全局變量

有三種方法聲明存儲單元為私有：

         1）使用private,firstprivate,lastprivate,reduction子句

         2）使用threadprivate

         3）在循環内聲明變量，并且不使用static關鍵字

shared:所有線程都能夠通路該單元，并行區域内使用共享變量時，如果存在寫操作，必須對共享變量加以保護

default:并行區中所有變量都是共享的，除下列三種情況下：

          1）在parallel for循環中，循環索引時私有的。

          2）并行區中的局部變量是私有的

          3）所有在private,firstprivate,lastprivate,reduction子句中列出的變量是私有的

7.

循環排程與分塊

     為了提供一種簡單的方法以便能夠在多個處理器之間調節工作負載，OpenMP給出了四種排程方案：

static,dynamic,runtime,guided.

     預設情況下，OpenMP采用靜态平均排程政策，但是可以通過調用schedule(kind[,chunksize])子句提供循環排程資訊

如：#pragma omp for schedule (kind[,chunk-size])   //chunk-size為塊大小

guided根據環境變量裡的設定來進行對前三種的排程

在windows環境中，可以在”系統屬性|進階|環境變量”對話框中進行設定環境變量。

8.

有效地使用歸約：

sum=0;

for(k=0;k<100;k++)

{

    sum=sum+func(k);

}

     為了完成這種形式的循環計算，其中的操作必須滿足算術結合律和交換律，同時sum是共享的，這樣循環内部都可以加給這個變量，同時又必須是私有的，以避免在相加時的資料競争。

reduction子句可以用來有效地合并一個循環中某些關于一個或多個變量的滿足結合律的算術歸約操作。reduction子句主要用來對一個或多個參數條目指定一個操作符，每個線程将建立參數條目的一個私有拷貝，在區域的結束處，将用私有拷貝的值通過指定的運作符運算，原始的參數條目被運算結果的值更新。

#pragma omp parallel for reduction(+:sum)

9.

降低線程開銷：當編譯器生成的線程被執行時，循環的疊代将被配置設定給該線程，在并行區的最後，所有的線程都被挂起，等待共同進入下一個并行區、循環或結構化塊。

              如果并行區域、循環或結構化塊是相鄰的，那麼挂起和恢複線程的開銷就是沒必要的。

舉例如下：

                #pragma omp parallel //并行區内

                {

                   #pragma omp for // 任務配置設定for循環

                          for(k=0;k<m;k++){

                               fun1(k);

                           }

                   #pragma omp for

                               fun2(k);

                }

10.任務配置設定區：

     現實中應用程式的所有性能敏感的部分不是都在一個并行區域内執行，是以OpenMP用任務配置設定區這種結構來處理非循環代碼。

任務配置設定區可以指導OpenMP編譯器和運作時庫将應用程式中标示出的結構化塊配置設定到用于執行并行區域的一組線程上。

              #pragma omp parallel //并行區内

                   #pragma omp sections private(y,z)

                     {

                           #pragme omp section//任務配置設定section

                               {y=sectionA(x);}

                           #pragme omp section

                               {z=sectionB(x);}

                     }                   

11.

使用Barrier和Nowait:

      栅障（Barrier）是OpenMP用于線程同步的一種方法。線程遇到栅障是必須等待，直到并行區中的所有線程都到達同一點。

注意：在任務配置設定for循環和任務配置設定section結構中，我們已經隐含了栅障，在parallel,for,sections,single結構的最後，也會有一個隐式的栅障。

隐式的栅障會使線程等到所有的線程繼續完成目前的循環、結構化塊或并行區，再繼續執行後面的工作。可以使用nowait去掉這個隐式的栅障

去掉隐式栅障，例如：

                   #pragma omp for nowait // 任務配置設定for循環

     因為第一個 任務配置設定for循環和第二個任務配置設定section代碼塊之間不存在資料相關。

加上顯示栅障，例如：

                              #pragma omp parallel shared(x,y,z) num_threads(2)//使用的線程數為2

                               {

                                   int tid=omp_get_thread_num();

                                   if(tid==0)

                                       y=fun1();//第一個線程得到y

                                   else 

                                        z=fun2();//第二個線程得到z

                                   #pragma omp barrier //顯示加上栅障，保證y和z在使用前已有值

                                   #pragma omp for

                                           for(k=0;k<100;k++)

                                                   x[k]=y+z;

                               }

12.

單線程和多線程交錯執行：

      當開發人員為了減少開銷而把并行區設定的很大時，有些代碼很可能隻執行一次，并且由一個線程執行，這樣單線程和多線程需要交錯執行

               #pragma omp parallel //并行區

              {

                    int tid=omp_get_thread_num();//每個線程都調用這個函數，得到線程号

                     //這個循環被劃分到多個線程上進行

                      #pragma omp for nowait

                      for(k=0;k<100;k++)

                            x[k]=fun1(tid);//這個循環的結束處不存在使所有線程進行同步的隐式栅障

                    #pragma omp master

                      y=fn_input_only(); //隻有主線程會調用這個函數

                    #pragma omp barrier   //添加一個顯示的栅障對所有的線程同步，進而確定x[0-99]和y處于就緒狀态

                     //這個循環也被劃分到多個線程上進行

                    #pragma omp for nowait

                         x[k]=y+fn2(x[k]); //這個線程沒有栅障，是以不會互相等待

                     //一旦某個線程執行完上面的代碼，不需要等待就可以馬上執行下面的代碼

                     #pragma omp single //注意：single後面意味着有隐式barrier

                     fn_single_print(y);

                      //所有的線程在執行下面的函數前會進行同步

                     #pragma omp master

                     fn_print_array(x);//隻有主線程會調用這個函數

              } 

13.

資料的Copy-in 和Copy-out:

      在并行化一個程式的時候，一般都必須考慮如何将私有變量的初值複制進來（Copy-in ），以初始化線程組中各個線程的私有副本。

在并行區的最後，還要将最後一次疊代/結構化塊中計算出的私有變量複制出來（Copy-out），複制到主線程中的原始變量中。

firstprivate:使用變量在主線程的值對其在每個線程的對應私有變量進行初始化。一般來說，臨時私有變量的初值是未定義的。

lastprivate:可以将最後一次疊代/結構化塊中計算出來的私有變量複制出來，複制到主線程對應的變量中，一個變量可以同時用firstprivate和lastprivate來聲明。

copyin:将主線程的threadprivate變量的值複制到執行并行區的每個線程的threadprivate變量中。

copyprivate:使用一個私有變量将某一個值從一個成員線程廣播到執行并行區的其他線程。該子句可以關聯single結構(用于single指令中的指定變量為多個線程的共享變量)，在所有的線程都離開該結構中的同步點之前，廣播操作就已經完成。

14.

保護共享變量的更新操作：

     OpenMP支援critical和atomic編譯指導，可以用于保護共享變量的更新，避免資料競争。包含在某個臨界段且由atomic編譯指導所标記的代碼塊可能隻由一個線程執行。

例如：#pragma omp critical

　　　{

              if(max<new_value) max=new_value;

         }

15.

OpenMP庫函數（#include <omp.h>）：

int omp_get_num_threads(void); //擷取目前使用的線程個數

int omp_set_num_threads(int NumThreads);//設定要使用的線程個數

int omp_get_thread_num(void);//傳回目前線程号

int omp_get_num_procs(void);//傳回可用的處理核個數

下面我們來看一個具體的應用例，從硬碟讀入兩幅圖像，對這兩幅圖像分别提取特征點，特征點比對，最後将圖像與比對特征點畫出來。了解該例子需要一些圖像處理的基本知識，我不在此詳細介紹。另外，編譯該例需要opencv，我用的版本是2.3.1，關于opencv的安裝與配置也不在此介紹。我們首先來看傳統串行程式設計的方式。

<a target="_blank"></a>

很明顯，讀入圖像，提取特征點與特征描述子這部分可以改為并行執行，修改如下：

兩種執行方式做比較，時間為：2.343秒v.s. 1.2441秒

在上面代碼中，為了改成适合#pragma omp parallel for執行的方式，我們用了STL的vector來分别存放兩幅圖像、特征點與特征描述子，但在某些情況下，變量可能不适合放在vector裡，此時應該怎麼辦呢？這就要用到openMP的另一個工具，section，代碼如下：

上面代碼中，我們首先用#pragma omp parallel sections将要并行執行的内容括起來，在它裡面，用了兩個#pragma omp section，每個裡面執行了圖像讀取、特征點與特征描述子提取。将其簡化為僞代碼形式即為：

意思是：parallel sections裡面的内容要并行執行，具體分工上，每個線程執行其中的一個section，如果section數大于線程數，那麼就等某線程執行完它的section後，再繼續執行剩下的section。在時間上，這種方式與人為用vector構造for循環的方式差不多，但無疑該種方式更友善，而且在單核機器上或沒有開啟openMP的編譯器上，該種方式不需任何改動即可正确編譯，并按照單核串行方式執行。

以上分享了這兩天關于openMP的一點學習體會，其中難免有錯誤，歡迎指正。另外的一點疑問是，看到各種openMP教程裡經常用到private,shared等來修飾變量，這些修飾符的意義和作用我大緻明白，但在我上面所有例子中，不加這些修飾符似乎并不影響運作結果，不知道這裡面有哪些講究。

在寫上文的過程中，參考了包括以下兩個網址在内的多個地方的資源，不再一 一列出，在此一并表示感謝。

http://blog.csdn.net/drzhouweiming/article/details/4093624

http://software.intel.com/zh-cn/articles/more-work-sharing-with-openmp

OpenMP嵌套并行：

<a target="_blank" href="http://blog.csdn.net/zhuxianjianqi/article/details/8287937">http://blog.csdn.net/zhuxianjianqi/article/details/8287937</a>

一些優秀部落格的加速例子：

<a target="_blank" href="http://www.cnblogs.com/LBSer/p/4604754.html">http://www.cnblogs.com/LBSer/p/4604754.html</a>

<a target="_blank" href="http://www.cnblogs.com/louyihang-loves-baiyan/p/4913164.html">http://www.cnblogs.com/louyihang-loves-baiyan/p/4913164.html</a>

參考文獻：

<a target="_blank" href="http://www.cnblogs.com/yangyangcv/archive/2012/03/23/2413335.html">http://www.cnblogs.com/yangyangcv/archive/2012/03/23/2413335.html</a>