OpenMP 心得 (四) Loop Construct

OpenMP 的 work-sharing constructs 共有四種，分別是 loop construct、sections construct、single construct、以及 Fortran 語言專有的 workshare construct。它們的功用是分配 parallel construct 所產生的多執行緒去平行執行程式，其中最常被使用的是前兩個構造 loop construct 與 sections construct，本篇文章我們將先介紹用於平行迴圈結構的 loop construct。

Loop Construct 的基本知識
在一般數值運算中可能會出現迭代次數非常多的迴圈結構，如果可以將這類迴圈分割給多個處理器去平行執行就能省下不少的執行時間。但並非所有的迴圈結構都可以被平行化，基本上可以被平行化的迴圈至少要滿足以下的限制：

• 迴圈的迭代次數必須是可數的，且有明確的整數型態初始值與終止條件，每次步進的增減幅度也必須是固定的整數。
• 迴圈中每個被切割出來的部份在運算上必須是獨立地，即計算過程中不需要用到其它部分所產生的資訊，並且執行各個部分可以不必按照順序。
• 迴圈內不能有跳出迴圈的敘述。

第一個限制是因為 loop construct 分割迴圈的方法是將迴圈的總迭代次數切割成數個段落，讓各個執行緒負責去執行其中的一段迭代計算，所以分割前必須知道迴圈的迭代次數、起迄點、以及步進幅度等資訊。在 C/C++ 中滿足這個條件的迴圈結構只有 for 迴圈，其它像是 while 以及 do-while 這類無法預期迭代次數的迴圈結構就不能被 OpenMP 平行化；同樣地，在 Fortran 中也只有 do 迴圈可以被平行化，而 while 與 do-until 迴圈就不行。

第二個限制不單應用於 loop construct，凡是所有可以被平行化的程式都必須遵守這項條件。其原因在於被分割處理的部份如果需要用到其它部份的計算結果，那麼就會產生執行順序上的問題而無法同時平行處理每個部分。以 Loop construct 而言，construct 內的每個執行緒會分配到迴圈計算中一部分的迭代範圍，這些範圍內的敘述都必須是獨立的且可無關順序地被執行，例如下面的敘述就滿足這個條件：

a[i] = b[i] + c[i] + 12345

其中 i 代表迴圈目前的步進值。而非獨立的敘述例子如下：

a[i] = a[i-1] + b[i]

在這個例子中求 a[i] 的值需要用到前一個迭代的結果 a[i-1]，如果迴圈中有類似這樣的敘述就不能被 OpenMP 正確地平行化。

第三個限制是 OpenMP 需要用在有良好結構化的程式碼 (well-structured program) 中。所謂良好結構化的程式碼是指由數個可執行的敘述所組成的程式區塊，且進出此區塊的路徑都只能是單一點。一般迴圈結構的離開點只有一個，就是當滿足迴圈的終止條件時便可離開。但若迴圈內有出現 goto、break 之類的敘述，則可以離開迴圈的路徑就不只一條，如此便不能滿足 OpenMP 對良好結構化程式的需求。不過也不是所有跳轉與終止迴圈的敘述都不能用，像是 goto 敘述的跳轉範圍如果限制在該迴圈內則沒有問題；另外 C/C++ 的 exit 函式或 Fortran 的 stop 敘述也允許出現在迴圈之中，因為它們不僅終止迴圈，還終止整個程式。

Loop construct 在 C/C++ 是使用關鍵字 for 來建構，其語法如下：

//--C/C++
#pragma omp for [clause[[,] clause] ... ]
for-loops

其中 for-loop 的型式必須是

for(init-expr; var relop b; incr-expr)
    structured-block

其中 init-expr 所設定的計數變數 var 必須是整數型態或是指標，在 C++ 中還允許是 random access iterator 型態的變數；迴圈終止條件的 b 變數必須是整數型態，而判斷用的關係運算子 relop 限定為 <、<=、>、以及 >= 四種之一；在 incr-expr 遞增減計數變數 var 的值必須是整數，計算上可以使用 ++、--、+=、-= 等運算子。

Fortran 是以關鍵字 do 來建構 loop construct，其語法如下：

c--Fortran
!$omp do [clause[[,] clause ...]
do-loops
[!$omp end do [nowait]]

Fortran 最後的 !$ omp end do 可以不用加，如果不加則編輯器會自動以 do-loop 的結尾作為 construct 的結束點。但我們建議是加上它，這麼做除了能讓程式比較好解讀外，也可以維持程式碼編寫上的一致性。出現在 Fortarn 結束 loop construct 敘述的 nowait clause 是用來移除 work-sharing construct 結束位置的隱性執行緒同步點，在 C/C++ 使用 nowait clause 則是如同其它 clauses 一樣是放在 work-sharing construct 的開頭敘述中。

迴圈的切割方式
整個 loop construct 的動作流程可以用下圖來表示：

圖中示意一個原本序列執行的迴圈結構被平行化後的結果。從圖示可以看出 loop construct 是被包含在 parallel construct 之中，執行緒乃由 parallel directive 所產生，然後再經 loop directive 去分配各執行緒需要執行的迴圈迭代數量與範圍。每個執行緒負責的迴圈迭代範圍要如何分配是由 schedule clause 所控制，它的語法為

schedule(kind [,chunk_size])

其中 kind 決定分割的方式，而 chunk_size 決定每個分割部分所包含的迭代步數量。可以選擇的 kind 種類有 static、dynamic、guided、以及 runtime 四種，如果在建構 loop construct 時未加入 schedule clause 則大部分的編譯器會以 schedule(static) 作為分割迴圈的預設方式。使用 static 分割迴圈若不指定 chunk_size 則會依參與運算的執行緒數目將總迭代步數進行均分，低編號的執行緒將分配到低計數值區域的迭代範圍。因每個執行緒執行的迭代步數量都必須是整數，所以有可能發生總迭代次數不能被執行緒數目整除的情況，這種情況可分為兩種：一是有一段切割部分的執行步數量較其它部分為多，在此情況下系統會讓主執行緒 (TID = 0) 負責這段比較多的部份，例如上圖顯示的執行緒分配方式即屬此類，藍色箭條線為主執行緒；另一種情況是有一個部分的步數量較少，這時系統會將此部分交由最後一個執行緒 (TID 編號最大者) 來執行。按照 OpenMP 3.0 的規格，static 的切割方式會讓每個執行緒至少都分配到一個迭代步數，但實際的狀況可能依使用的編譯器而有不同，譬如筆者使用的平臺 (OS：Centos 5.5，C compiler：gcc 4.1.2) 在 9 個迴圈迭代步數使用 4 個執行緒做平行計算時會出現前三個執行緒各分到三個迭代步數而最後一個執行緒 (TID = 3) 卻被閒置的情況。因為關於如何使用 schedule 牽涉到負載平衡 (load balancing) 的議題，如果繼續在這裡討論會讓這篇文章過於龐大與繁雜，未避免離題過遠我們計畫之後再以專文來介紹 schedule clause，目前讀者只要先知道它預設的 static 分配策略即可。

程式實例
在了解 loop construct 的作用與語法後，接下來我們以一個實際的程式範例來解說如何使用它。首先來看未平行化前的程式原樣：

//--Program: simple_loop.c
//--A Simple Loop Demo
//--Written by AAZ

#include <stdio.h>
#include <omp.h>

#define N 12

int main()
{
    int a[N], b[N], c[N];
    int i;
    for (i = 0; i < N; i++) {
        a[i] = i;
        b[i] = 2*i;
        c[i] = a[i] + b[i];
        printf("c[%d] = %d\n", i, c[i]);
    }
    return 0;
}

這個程式很簡單，只是用一個迴圈來設定三個陣列變數的元素初始值，並印出其中一個陣列的所有元素值：

使用 loop construct 平行迴圈的程式碼如下：

//--Program: simple_loop_construct.c
//--Example of OMP Loop Construct
//--Written by AAZ

#include <stdio.h>
#include <omp.h>

#define N 12

int main()
{
    int a[N], b[N], c[N];
    int i, tid, nthreads;

    #pragma omp parallel private(tid)
    {
    tid = omp_get_thread_num();
    nthreads = omp_get_num_threads();
    printf("Threads = %d\n", nthreads);
    #pragma omp for 
    for (i = 0; i < N; i++) {
        a[i] = i;
        b[i] = 2*i;
        c[i] = a[i] + b[i];
        printf("Thread %d: c[%d] = %d\n", tid, i, c[i]);
        }
    }
    return 0;
}

在程式中我們使用兩個 OpenMP 函式來取得一些平行運算的資訊，其中取得執行緒編號的 omp_get_thread_num() 函式在之前已經介紹過了，另一個 omp_get_num_threads() 的作用是回傳在平行區域中參與運算的執行緒數目，如果我們在執行程式前有設定環境變數 OMP_NUM_THREADS 則 omp_get_num_threads 會回傳 OMP_NUM_THREADS 的值。在 parallel directive 我們宣告 tid 變數為執行緒所私有，但在整個平行運算過程中還有一個變數也必須是執行緒所私有的，那就是迴圈的計數變數 i。原因在於每個執行緒會被分配到不同的迭代範圍，如果它們都共用一個 i 變數來計數目前的迭代位置，則會發生記錄錯亂的情形。舉例來說 A 執行緒在判斷是否繼續進行下一輪迭代所用的計數值 i 可能剛被 B 執行緒更新過，而這個剛更新過的 i 值是不會落在 A 執行緒應該執行的迭代範圍內，於是可能造成 A 執行緒迭代終止或在下一輪計算中參照到錯誤的 i 值。對程序而言保持每個執行緒的迴圈計數值私有化是非常重要的事，因此預設上 OpenMP 會將 loop construct 的迴圈計數變數自動定義成私有的，即便我們未在 for/do directive 中以 private clause 明確地宣告它的存取屬性。程式的執行結果如下：

我們使用四個執行緒來執行這個程式，因此可以從圖中看到每個執行緒各分配到 3 個迭代步數。再提醒一次，程式在平行執行時各執行緒完成工作的順序與時間是不定的，這個程式由執行緒輸出訊息的順序不會每次運算都一樣。另外可以看到 Threads = 4 的訊息出現四次，這是因為列印這個訊息的敘述是放在介於 parallel directive 與 for directive 之間，所以每個執行緒都會執行一次，也由於在此敘述之後並沒有設定 barrier 之類的執行緒同步點，是故每個執行緒印出執行緒數目後就徑自去執行本身被分配到的迴圈工作，不會等待其它的執行緒。其實輸出參與平行運算的執行緒數目資訊只要交由其中一個執行緒去做就夠了，沒必要輸出 4 次。像這類在平行處理過程中只需要一個執行緒執行的工作可以使用 single construct 或 master construct 來處理，有關這兩個 constructs 的用法將留待以後再做介紹。底下為示範程式的 Fortran 版本與執行結果：

c--Program: simple_loop_construct.f
c--Example of OMP Loop Construct
c--Written by AAZ

      program main
      use omp_lib
      parameter (n = 12)
      integer a(n), b(n), c(n)
      integer tid, threads

!$OMP PARALLEL PRIVATE(tid)
      tid = omp_get_thread_num()
      nthreads = omp_get_num_threads()
      write(*,100)"Threads = ", nthreads
  100 format (A, I1)
!$OMP DO
      do i = 1, 12, 1
          a(i) = i
          b(i) = 2*i
          c(i) = a(i) + b(i)
          write(*,200)"Thread ", tid, ": c[", i, "] = ", c(i)
  200     format (A, I1, A, I2, A, I2)
       end do
!$OMP END DO
!$OMP END PARALLEL 

      stop
      end program main

複合結構 (Combined Parallel Work-sharing Constructs)
在 OpenMP 中，如果一個 parallel construct 內除了一個 work-sharing construct 外就沒有任何其它的程式敘述，則可以將這個兩個 constructs 合併起來成為一個複合結構，稱作 combined parallel work-sharing construct。例如我們上面的範例中 parallel construct 內只有一個 loop construct，只要將 parallel directive 宣告行與 for directive 宣告行之間的程式碼移除就可以將它們合併成複合結構。在 C/C++ 中平行迴圈複合結構 (parallel loop construct) 的語法如下：

//--C/C++
#pragma omp parallel for [clause[[,] clause] ... ]
for-loop

在 Fortran 的使用語法如下：

c--Fortran
!$omp parallel do [clause[[,] clause ...]
do-loop
[!$omp end parallel do]

複合結構是 OpenMP 唯一會在 construct 宣告敘述行中同時出現兩個 directive 關鍵字的結構，將 parallel construct 與 work-sharing constructs 結合起來的最大好處大概是讓程式平行區域的宣告變得比較簡潔且讓程式意圖更加地明確易懂。使用複合結構也能稍微增加點程式的運算效率，例如以編譯器處理使用複合結構的程式碼跟處理使用兩個分開的 parallel 結構與 work-sharing 結構的程式碼來講，前者就比後者少設定一個隱性的執行緒同步點，少了一道關卡程式自然跑起來就快一點，不過以現今 CPU 的處理速度來看，這個加速效益其實是微不足道。複合結構的使用限制條件如下：

• Work-sharing constructs 中只有 loop construct、sections construct、以及 Fortran 專有的 workshare construct 可以與 parallel construct 結合成複合結構。
• 複合結構內只能有一個 work-sharing construct 存在，且結構內所有需要被平行執行的程式敘述都必須被包含在 work-sharing construct 中。
• 如果要在複合結構加上 clause 必須要注意到這個 clause 是否同時支援 parallel construct 與被合併的 work-sharing construct，且 clause 操控平行化的行為必須與這兩個 construct 無關，亦即不需指定這個 clause 作用的對象是 parallel construct 或 work-sharing construct。

之前 C 語言的範例改編成使用複合結構的程式碼如下，Fortran 的部份就不再列出：

//--Program: simple_parallel_for_construct.c
//--Example of OMP Parallel-For Construct
//--Written by AAZ

#include <stdio.h>
#include <omp.h>

#define N 12

int main()
{
    int a[N], b[N], c[N];
    int i, tid, nthreads;

    #pragma omp parallel for private(tid)
    for (i = 0; i < N; i++) {
        a[i] = i;
        b[i] = 2*i;
        c[i] = a[i] + b[i];
        tid = omp_get_thread_num();
        printf("Thread %d: c[%d] = %d\n", tid, i, c[i]);
        } 
    return 0;
}

注意我們已將原本位於 parallel directive 與 for directive 之間的程式碼做了些調整：移除取得執行緒數目的敘述，並將取得執行緒編號的敘述移到迴圈之中。程式執行結果如下圖所示：

本章總結：

• Loop construct 用於平行 C/C++ 的 for 迴圈或 Fortran 的 do 迴圈。
• 可以被平行化的迴圈必須有明確的迭代起迄範圍以及整數型態的步進值。
• 迴圈被切割的各個部份在執行時必須是與迭代順序無關的，且迴圈內不能出現跳脫迴圈的敘述。
• 要取得在平行區域間參與運算的執行緒數量可以使用 omp_get_num_threads 函式。如果有設定環境變數 OMP_NUM_THREADS，則 omp_get_num_threads() 會傳回該變數的設定值。
• 迴圈被切割的方式可以使用 schedule clause 來控制，如果不在 for/do directive 中明白指定，則大部份的編譯器預設上會使用 schedule(static) 的方式來分配每個執行緒所負責的迴圈迭代範圍。
• 如果 parallel construct 內只有一個 work-sharing construct，此外也沒有其它的程式敘述，則除了 single construct 外其它的 work-sharing construct 都可以與 parallel construct 合併成一個 combined work-sharing construct。
• 只有同時支援 parallel construct 與 work-sharing constructs 且不需指明所作用的 construct 對象為誰的 clauses 才能被用在 combined parallel work-sharing constructs 的建構上。
• 使用 nowait clause 可以移除 work-sharing constructs 結束處的隱性執行緒同步點。C/C++ 的 nowait clause 是加在 construct 開頭宣告行，而 Fortran 則是放在 construct 結束的宣告行中。

有關 loop construct 的介紹就到此為止，請記住這只是非常簡單的介紹，目的是讓讀者對 loop construct 建立起大略的圖像與基本運用能力。如果想要了解更多的細節與使用方法除了 OpenMP 的規格書外，我建議去看 Using OpenMP 這本書 (B. Chapman, G. Jost, R. van der Pas, Using OpenMP: Portable Shared Memory Parallel Programming)，這兩份文件是我學習 OpenMP 與撰寫此系列文章非常重要的參考資料。在下一篇文章我們將介紹另一個相當重要，用於平行處理程式中個別獨立任務的 work-sharing construct：sections construct。

(發佈日期：2011/04/09 by AAZ)