[解決済み】openmpのcollapse句を理解する

質問内容

OpenMPのコードでcollapse節があるものに出会いましたが、これは私にとって新しいものでした。その意味を理解しようとしているのですが、その意味を完全に把握できていないようです。私が見つけた1つの定義は以下の通りです。

COLLAPSE : ネストされたループのうち、いくつのループを1つの大きな反復空間に畳み込み、スケジュール節に従って分割するかを指定する。関連するすべてのループの反復処理の順次実行により、折りたたまれた反復処理空間での反復処理の順序が決定される。

その意味が分かったような気がしたので、以下の簡単なプログラムを試してみました。

int i, j;
#pragma omp parallel for num_threads(2) private(j)
for (i = 0; i < 4; i++)
    for (j = 0; j <= i; j++)
        printf("%d %d %d\n", i, j, omp_get_thread_num());

どの製品

0 0 0
1 0 0
1 1 0
2 0 0
2 1 0
2 2 1
3 0 1
3 1 1
3 2 1
3 3 1

その後、私は collapse(2) 節があります。最初の2つの列で同じ結果になると思っていたのですが、今では同じ数の 0 と 1 を最後のカラムに追加しました。 しかし、私は

0 0 0
1 0 0
2 0 1
3 0 1

そこで質問なのですが。

1. 私のコードでは何が起こっているのでしょうか？
2. どのような場合に collapse ?
3. を使用した場合との違いを示す例を示してもらえますか？ collapse を使うか使わないか？

解決方法は？

あなたのコードの問題は、内側のループの反復が外側のループに依存していることです。OpenMPの仕様によると、バインディングのセクションの記述と collapse 節があります。

関連するループの実行により、計算のために使用される値が変更された場合。 の反復回数は、その動作は不定です。

そうでない場合、例えば正方形ループの場合、collapseを使用することができます。

#pragma omp parallel for private(j) collapse(2)
for (i = 0; i < 4; i++)
    for (j = 0; j < 100; j++)

実際、これはcollapseを使用する際の良い例です。外側のループは4回しか反復していません。もし4つ以上のスレッドがあれば、そのうちのいくつかは無駄になります。しかし、collapseを使用すると、スレッドの数よりもはるかに多い400の反復処理にスレッドを振り分けることができます。collapseを使うもう一つの理由は、負荷がうまく分散されていない場合です。もし、4回の反復処理しか行わず、4回目の反復処理にほとんどの時間を費やした場合、他のスレッドは待機します。しかし、400回の反復処理を行えば、負荷はよりよく分散されるはずです。

上記のコードに対して、手でループを融合させるには、次のようにします。

#pragma omp parallel for
for(int n=0; n<4*100; n++) {
    int i = n/100; int j=n%100;

これ は、三重に融合されたループを手作業で融合する方法を示す例である。

最後に ここで は、三角形のループを融合させる方法を示す例です。 collapse は定義されていません。

OP問題の三角ループに矩形ループをマッピングした解答を紹介します。これを利用して、OPの三角ループを融合させることができます。

//int n = 4;
for(int k=0; k<n*(n+1)/2; k++) {
    int i = k/(n+1), j = k%(n+1);
    if(j>i) i = n - i -1, j = n - j;
    printf("(%d,%d)\n", i,j);
}

これは、どのような値のnに対しても有効です。

OPの質問に対するマップは次のようになります。

(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),
(3,0), (3,1), (3,2), (3,3),

になります。

(0,0), (3,3), (3,2), (3,1), (3,0),
(1,0), (1,1), (2,2), (2,1), (2,0),

nの奇数値では、マップは正確な長方形ではありませんが、式はまだ動作します。

例えば、n = 3 は次のようにマッピングされます。

(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),

になります。

(0,0), (2,2), (2,1), (2,0),
(1,0), (1,1),

以下は、これをテストするためのコードです。

#include <stdio.h>
int main(void) {
    int n = 4;
    for(int i=0; i<n; i++) {
        for(int j=0; j<=i; j++) {
            printf("(%d,%d)\n", i,j);
        }
    }
    puts("");
    for(int k=0; k<n*(n+1)/2; k++) {
        int i = k/(n+1), j = k%(n+1);
        if(j>i) i = n - i - 1, j = n - j;
        printf("(%d,%d)\n", i,j);
    }
}