Loop Construct

程式中可能出現迭代次數非常多的迴圈結構,如果可以將這類迴圈平行執行就能省下不少的執行時間,但並非所有的迴圈結構都可以被平行化,基本上可以被平行化的迴圈至少要滿足以下的限制:

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

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

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

a[i] = b[i] + c[i] + 1;

下面的敘述計算需要上個迭代的結果,因此無法用OpenMP進行平行化:

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

第三個限制是迴圈內不能有goto、break之類的敘述,一般迴圈只要滿足終止條件時便可離開,但若迴圈內有goto、break,則可以離開迴圈的路徑就不只一條,就不能滿足OpenMP對結構化程式的要求,不過如果goto的跳轉範圍限制在迴圈內則沒有問題。


下圖為loop construct的運作概念,由parallel directive新增執行緒,接著由loop directive切割迴圈工作,等每個執行緒工作都完成之後,再進行join步驟離開平行運算區域。

Loop Construct


以下我們示範loop construct的使用方式,將迴圈進行切割後,賦值並印出陣列的值,由結果可看出每個執行緒皆執行迴圈一部份的工作:

#include <cstdio>
#include <cstdlib>
#include <omp.h>

int main(){
    int a[12];
    int i, tid, nthreads;

    #pragma omp parallel private(tid)
    {
        tid = omp_get_thread_num();

        #pragma omp for 
        for(i=0; i<12; i++){
            a[i] = i;
            printf("Thread %d: a[%d] = %d\n", tid, i, a[i]);
        }
    }

    system("PAUSE");
    return 0;
}

Loop Construct


在OpenMP中,如果一個parallel construct內除了一個work-sharing construct外就沒有其它的程式敘述,則可以將這個兩個constructs合併起來成為一個複合結構。例如上面的例子,parallel construct內只有一個loop construct,所以可以將它們合併成複合結構,好處是讓平行區域的宣告變得比較簡潔,然後複合結構執行緒少了一個同步點,跑起來稍快一點,不過以CPU的處理速度來看,這個加速效益其實微不足道,以下我們將上述例子改成複合結構:

#include <cstdio>
#include <cstdlib>
#include <omp.h>

int main(){
    int a[12];
    int i, tid, nthreads;

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

    system("PAUSE");
    return 0;
}

回到首頁

回到OpenMP教學


參考資料:

aaz 的記憶倉庫