データ競合の解決

インテル® 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; // 必要に応じて計算を行う
      }
    }
...
}

アルゴリズムを変更する

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

レデューサーを使用する

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

ロックを使用する

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

• インテル® スレッディング・ビルディング・ブロック・ライブラリーの tbb::mutex オブジェクト
• Windows*、Linux*、macOS* オペレーティング・システムのシステムロック
• 読み取り-変更-書き込みという一連の命令を保護するための効率的で存続期間の短いロックであるアトミック命令

次のプログラムでは、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;
}

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