インテル® C++ コンパイラー 19.0 デベロッパー・ガイドおよびリファレンス

競合状態の理解

インテル® Cilk™ Plus は古い機能 (非推奨) です。代わりに、OpenMP* またはインテル® TBB を使用してください。詳細は、「インテル® Cilk™ Plus の代わりに OpenMP* またはインテル® TBB を使用するためのアプリケーションの移行」 (英語) を参照してください。

データ競合

インテル® Cilk™ Plus は古い機能 (非推奨) です。代わりに、OpenMP* またはインテル® TBB を使用してください。詳細は、「インテル® Cilk™ Plus の代わりに OpenMP* またはインテル® TBB を使用するためのアプリケーションの移行」 (英語) を参照してください。

データ競合は、並列プログラムの問題の主な原因です。

決定性競合は、2 つの並列ストランドが同じメモリー位置にアクセスし、そのどちらかが書き込み操作を行うと発生します。プログラムの結果は、どちらのストランドが "競争に勝ち"、先にメモリーにアクセスするかによって異なります。

データ競合は、決定性競合の特殊なケースです。データ競合は、共通のロックを保持していない 2 つの並列ストランドが同じメモリー位置にアクセスし、そのどちらかが書き込み操作を行うと発生します。プログラムの結果は、どちらのストランドが "競争に勝ち"、先にメモリーにアクセスするかによって異なります。

並列アクセスがロックによって保護されている場合、データ競合は発生しません。ただし、ロックを使用するプログラムでは、決定性のある結果が得られないことがあります。ロックは、データ構造を保護して更新時に中間ステートから見えないようにすることで一貫性を保証しますが、決定性のある結果は保証しません。

例えば、次のようなプログラムについて考えてみます。

int a = 2; // 複数のスレッドがアクセス可能な変数を宣言

void Strand1()
{
   a = 1;
}

int Strand2()
{
   return a;
}

void Strand3()
{
   a = 2;
}
int main()
{
   int result;
   cilk_spawn Strand1();
   result = cilk_spawn Strand2();
   cilk_spawn Strand3();
   cilk_sync;
   std::cout << "a = " << a << ", result = "
             << result << std:endl;
}

Strand1()、Strand2()、Strand3() は並列で実行される可能性があるため、a と result の最終値は実行順序によって異なります。

Strand1() は Strand2() が a の値を読み取る前または後に書き込みを行う可能性があり、そのため Strand1() と Strand2() の間には読み取り/書き込み競合が存在します。

Strand3() は Strand1() が a の値を書き込む前または後に書き込みを行う可能性があり、そのため Strand3() と Strand1() の間には書き込み/書き込み競合が存在します。

データ競合によっては、害のないものもあります。つまり、競合が存在していても、プログラムの出力に影響しない場合があります。

次の簡単な例について考えてみます。

bool bFlag = false;
cilk_for (int i=0; i<N; ++i)
{
   if (some_condition()) bFlag = true;
}
if (bFlag) do_something();

このプログラムには、bFlag 変数に書き込み/書き込み競合があります。ただし、すべての書き込み操作は同じ値 (true) を書き込み、cilk_for ループの終了時に暗黙的に cilk_sync が行われるまで読み取り操作は行われません。

そのため、このデータ競合はプログラムの結果に影響を与えません。どのような順序でループの反復が実行されても、プログラムの結果は同じになります。

データ競合の解決

インテル® Cilk™ Plus は古い機能 (非推奨) です。代わりに、OpenMP* またはインテル® TBB を使用してください。詳細は、「インテル® Cilk™ Plus の代わりに OpenMP* またはインテル® TBB を使用するためのアプリケーションの移行」 (英語) を参照してください。

データ競合を解決する方法はいくつかあります。

プログラムの問題部分を修正する

データ競合は、プログラムロジックの問題です。例えば、ソートの再帰呼び出しで重複する領域を使用しており、並列で同じメモリー位置を参照している場合に、競合が発生します。この競合を解決するためには、アプリケーションを修正します。

グローバル変数の代わりにローカル変数を使用する

次のプログラムについて考えてみます。

#include <cilk/cilk.h>
#include <iostream>
const int IMAX=5;
const int JMAX=5;
int a[IMAX * JMAX];

int main()
{
   int idx;

   cilk_for (int i=0; i<IMAX; ++i)
   {
     for (int j=0; j<JMAX; ++j)
     {
        idx = i*JMAX + j; // 競合状態
        a[idx] = i+j;
      }
   }
   for (int i=0; i<IMAX*JMAX; ++i)
     std::cout << i << " " << a[i] <<std::endl;
   return 0;
}

このプログラムは、cilk_for ループで idx 変数に並列でアクセスするため、この変数で競合が発生します。idx はループの内側でしか使用されないため、idx をループ内のローカル変数にするだけで競合を解決できます。

int main()
{
// int idx;                  // グローバル変数を削除
   cilk_for (int i=0; i<IMAX; ++i)
   {
     for (int j=0; j<JMAX; ++j)
     {
       int idx = i*JMAX + j; // idx をローカルで宣言する
       a[idx] = i+j;
     }
    }
...
}

コードを再構築する

場合によっては、コードを少し変更するだけで競合を排除できます。前述のプログラムの場合、次のように変更するだけで、競合を解決することができます。

int main()
{
// int idx;                // グローバル変数を削除
   cilk_for (int i=0; i<IMAX; ++i)
   {
     for (int j=0; j<JMAX; ++j)
     {
//     idx = i*JMAX + j;    // idx を使用せずに
       a[i*JMAX + j] = i+j; // 必要に応じて計算を行う
      }
    }
...
}

アルゴリズムを変更する

最良のソリューションは、並列処理を競合の可能性がない計算だけに制限するように問題の切り分けを行うアルゴリズムを見つけることですが、これは容易ではなく実装不可能なこともあります。

レデューサーを使用する

レデューサーは、並列で安全に使用できる競合のないオブジェクトです。詳細は、「レデューサー」を参照してください。

ロックを使用する

ロックを使用して、データ競合を解決することもできます。このアプローチには、「ロックの使用について」で説明されている短所があります。ロックにはいくつかの種類があります。

次のプログラムでは、sum=sum+i で sum の読み取りと書き込みの両方を行っているため、sum で競合が発生します。

#include <cilk/cilk.h>

int main()
{
   int sum = 0;
   cilk_for (int i=0; i<10; ++i)
   {
      sum = sum + i;  // sum で競合が発生
    }
}

次のように、ロックを使用して競合を解決します。

#include <cilk/cilk.h>
#include <tbb/mutex.h>
#include <iostream>

int main()
{
   tbb::mutex mut;
   int sum = 0;
   cilk_for (int i=0; i<10; ++i)
   {
     mut.lock();
     sum = sum + i; // ロックで保護
     mut.unlock();
   }
   std::cout << "Sum is " << sum << std::endl;

return 0;
}

ここでは、一例としてロックを使用しています。通常、このような競合の解決にはレデューサーを使用したほうがよいでしょう。

親トピック: インテル® Cilk™ Plus