データ競合

OpenMP* 並列領域のデータ使用パターンでデータ競合が発生しています。

適切な同期処理がされずに同じメモリー位置に 2 つのスレッドがアクセスするとデータ競合が発生します。そのため、プログラムを並列モードで実行すると非決定的な結果をもたらします。OpenMP* では、異なるスレッドに異なるループ反復を割り当てることにより、ループが並列化されます。この手法では、ループの反復はどの順番でも実行できるよう独立している必要があります。

競合状態が発生する原因はいくつもあります。最も単純なものは、並列領域の共有変数に書き込みを行うことです。この場合、変数の最終値はどの反復が最後に書き込みを行ったかによります。シーケンシャル・モードでは、これは常に最後の反復ですが、並列モードでは保証されません。

別の一般的な原因として、ループ運搬データ依存と呼ばれるものがあります。これは、1 つのループ反復で書き込まれた値が別の反復で読み書きされることを指します。つまり、ループ反復でその反復で書き込みを行っていない変数が読み取られます。通常、これは配列のインデックス付けが適切でない場合に発生します。例えば、"x" がループカウンターで "a" が配列の場合、"a[x]" の値はそれぞれのループ反復で異なります。そのため、ループ運搬の依存性はなく、ループは "a[x]" を書き込むことができます。ただし、そのループで "a[x+1]" の読み書きも行う場合は、1 つのループ反復の "a[x]" が次の反復の "a[x + 1]" と同じであるため、ループ運搬依存が発生します。

競合状態にはさまざまな解決方法があり、最良の解決方法を決定するのは開発者次第です。すべてのシーケンシャルなアルゴリズムが並列で実行あるいは、並列化できるわけではありません。場合によっては、アルゴリズムを変更することで、別の方法で作業単位をグループ化して並列化できるようにすることが可能です。

アルゴリズムの変更のほか、データ競合状態を解決するには 2 つの主な方法があります。最初の解決方法は copy-in、copy-out、つまり "プライベート化" アプローチです。これは、各スレッドが共有変数をスレッド・プライベート変数にコピーします。各スレッドは、その後、干渉の懸念なく、スレッド・プライベート変数の読み書きを行うことができます。並列領域の最後で、プライベート・コピーを共有変数に結合して戻すことができます。OpenMP* は、REDUCTION、PRIVATE、THREADPRIVATE、FIRSTPRIVATE、LASTPRIVATE などの多くのデータ共有構造をサポートしています。

copy-in、copy-out 手法はあらゆる状況で効果があるわけでありません。OpenMP* REDUCATION 節では、各スレッド・プライベート変数を結合して共有変数に戻すためのいくつかの方法を提供しています。例えば、すべてを加算したり、または最大値/最小値を計算したりすることができます。copy-out で適切に値を結合するために必要なアルゴリズムが規則的でない場合は、これらの OpenMP* 機能を使用できないことがあります。

最後の手法は、同期化を採用して、変数が正しい順番でアクセスされるようにする方法です。これは、スレッドが並列で自由に実行できなくなり、実行待機に時間を費やさなければならなくなるため、パフォーマンスに影響があります。例えば、ORDERED 構造を使用して、並列ループ部分を厳密な反復順で実行するように制限することが可能です。

ループを 2 つに分割することにより、データ依存が解決される場合もあります。例えば、"x" がループカウンターで配列 "a" にアクセスするループがあるとします。ループには、"a[x]" に代入する文と、その後で "a[x - 1]" から読み取る文があります。並列モードでは、"i-1" 番目のループ反復が "i" 番目の反復の前に終了する保証はないため、データ競合が発生します。ただし、2 番目の文を別のループに移動できれば、この問題は解決できます。

ID

問題箇所

説明

2-N

不正なメモリーアクセス

競合状態の原因となった変数の読み取り/書き込みが行われた場所


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

void do_work1()
{
    int i, sum = 0;
    int a[100]; 

    for (i = 1; i < 100; i++) {
       a[i] = i;
    }
 
// The loop-carried data dependency on "a" in the following loop
// means the iterations cannot be run safely in parallel.
// In sequential mode, the i-th array element is only modified
// in the i-th iteration.  Therefore "a[i + 1]" is never modified
// by a previous loop iteration, and will contain the value
// assigned earlier: "i + 1".  This is not true in parallel mode.
// For example, suppose the i = 10 iteration runs before the
// i = 9 iteration.  Then the statement a[i] = a[i] + 1; in
// iteration 10 will set a[10] to 11 before the statement
// sum = sum + a[i + 1] in iteration 9 is executed.
// When it is, it will add 11 to sum instead of 10.
// This is not what happens in sequential mode.
        
#pragma omp parallel for reduction(+:sum)
    for (i = 1; i < 99; i++) {
        a[i] = a[i] + 1;
        sum = sum + a[i + 1];
    }

    printf("%d\n", sum); 
}

void do_work2()
{
    int i, sum = 0;
    int a[100], b[100];

    for (i = 1; i < 100; i++) {
        a[i] = i;
        b[i] = 100 - i;
    }

// The following loop demonstrates a "possible" data dependency.
//
// A data dependency exists if the same element of an array
// is written on one loop iteration and read on another or
// written on two different loop iterations.  This loop writes
// the "a[i]-th" element of "b" and reads the "i-th" element.
// Therefore a write-write dependency exists if and only if
// "a[i]" in one iteration is equal to "a[i]" in another iteration.
// A read-write dependency exists if and only if "a[i]" in one
// iteration is equal to "i" in another iteration.
//
// These facts are hard to determine statically so a "possible data
// dependency error will be issued.  In this program this is a
// false positive because the previous loop sets "a[i]" equal to "i".
// Therefore "a[i]" has a different value on every iteration so no
// write-write dependency.  Also "a[i]" and "i" have different values on
// different loop iterations so no read-write dependency exists either.

#pragma omp parallel for reduction(+:sum)
    for (i = 1; i < 100; i++) {
        b[a[i]] = i;
        sum = sum + b[i];
    }
    printf("%d\n", sum);
}

int main(int argc, char **argv)
{
    do_work1();
    do_work2();
    return 0;
}
        

© 2010 Intel Corporation. 無断での引用、転載を禁じます。