OpenMP* を使用したワークシェア

コンパイルの基本

OpenMP* プラグマを使用するには、OpenMP* 互換コンパイラーとスレッドセーフ・ライブラリーが必要です。[Q]openmp オプションを追加すると、OpenMP* プラグマに注意し、スレッドを挿入するようにコンパイラーに指示します。[Q]openmp オプションを省略すると、コンパイラーは OpenMP* プラグマを無視します。つまり、ソースコードを変更することなく、シングルスレッド・バージョンを簡単に生成することができます。

条件付きコンパイルでは、コンパイラーは _OPENMP マクロを定義します。必要に応じて、次の例のようにこのマクロをテストすることができます。

#ifdef _OPENMP
   fn(); 
#endif

簡単な例

次の例では、OpenMP* の使用がどの程度簡単かを示します。通常、その他の問題に対処する必要がありますが、これらの例では基本的な使用について説明します。

例 1 のループは、配列の値を 0 ～ 255 の範囲に限定します。

// 配列の値を 0 <= x <= 255 の範囲に限定
for (i=0; i < numElements; i++) {
  if (array[i] < 0)
  array[i] = 0;
  else if (array[i] > 255)
    array[i] = 255; 
}

この例は、OpenMP* プラグマを使用してスレッド化することができます。プラグマをループの直前に挿入します。

#pragma omp parallel for 
for (i=0; i < numElements; i++) {
  if (array[i] < 0)
  array[i] = 0;
  else if (array[i] > 255)
    array[i] = 255; 
}

例 2 のループは、0 ～ 100 の平方根の表を生成します。

double value; 
double roots[100]; 
for (value = 0.0; value < 100.0; value ++) { roots[(int)value] = sqrt(value); }

ループ変数を符号付き整数または符号なし整数に変更し、#pragma omp parallel プラグマを挿入して、ループをスレッド化します。

int value; 
double roots[100]; 
#pragma omp parallel for 
for (value = 0; value < 100; value ++) { roots[value] = sqrt((double)value); }

データ依存と競合状態の回避

ループが (前述の) 5 つのループ制約をすべて満たし、コンパイラーがループをスレッド化しても、データ依存が原因でループが正しく動作しない場合があります。

データ依存は、ループの異なる反復 (厳密には、異なるスレッドで実行するループの反復) が共有メモリーの同じ位置の読み取りまたは書き込みを行った場合に発生します。階乗を計算する次の例について考えてみます。

// Each loop iteration writes a value that a different iteration reads. 
#pragma omp parallel for 
for (i=2; i < 10; i++) { factorial[i] = i * factorial[i-1]; }

コンパイラーはこのループのスレッド化を試みますが、ループの少なくとも 1 つの反復が異なる反復に対してデータ依存しているため、スレッド化は実行に失敗します。このような状態を競合状態と呼びます。競合状態は、共有リソース (メモリーなど) と並列実行を使用した場合にのみ発生します。この問題を解決するには、ループを書き換えるか、競合状態のない別のアルゴリズムを使用します。

システムやケースによっては競合が発生せず、プログラムが正しく動作するため、競合状態を検出するのは困難です。1 度プログラムが動作しても、常に動作するとは限りません。インテル® ハイパースレッディング (HT) テクノロジーに対応したマシンや複数の物理プロセッサーを搭載したマシンなど、さまざまなマシンでプログラムをテストすると、競合状態を識別するのに役立ちます。

従来のデバッガーでは、1 つのスレッドが競合を停止してもその間、他のスレッドは継続的かつ著しくランタイム動作を変更するため、競合状態の検出には役立ちません。競合状態の検出には、スレッド・チェック・ツールが役立ちます。

共有データとプライベート・データの管理

(実際のアプリケーションでは) ほぼすべてのループがメモリーからの読み取り、またはメモリーへの書き出しを行います。開発者は、どのメモリーをスレッド間で共有し、どのメモリーをプライベートとして保持するのかをコンパイラーに指示する必要があります。メモリーが共有の場合、すべてのスレッドが同じメモリーの場所にアクセスします。メモリーがプライベートの場合、メモリーにアクセスするために、スレッドごとに個別の変数 (プライベート・コピー) が作成されます。ループの最後にプライベート・コピーは破棄されます。デフォルトでは、プライベートなループ変数を除き、すべての変数は共有されます。

プライベートとしてメモリーを宣言するには、2 つの方法があります。

• static キーワードを指定しないで、変数をループの内側 (parallel OpenMP* プラグマの内側) で宣言します。

• OpenMP* プラグマで private 節を指定します。

次の例では、変数 temp が共有であるためにループは正しく動作しません。これはプライベートにすべきです。

// 変数 temp はすべてのスレッドによって共有されるため、あるスレッドが
// 変数 temp を読み取り中に別のスレッドが書き込む可能性がある
#pragma omp parallel for 
for (i=0; i < 100; i++) {
  temp = array[i];
  array[i] = do_something(temp); 
}

次の 2 つの例では、変数 temp はプライベート・メモリーとして宣言されているため、問題が解決されています。

#pragma omp parallel for 
for (i=0; i < 100; i++) {
  int temp; // 並列構造内で変数された宣言はプライベート
  temp = array[i];
  array[i] = do_something(temp); 
}

次の方法で、temp 変数を作成することもできます。

#pragma omp parallel for private(temp) 
for (i=0; i < 100; i++) {
  temp = array[i];
  array[i] = do_something(temp); 
}

OpenMP* を使用してループを並列化する際は、すべてのメモリー参照 (呼び出された関数による参照を含む) を慎重に検証することを推奨します。並列構造内で宣言された変数は、static 宣言子を使用して宣言されている場合を除き (static 変数はスタックに割り当てられないため)、プライベートとして定義されます。

リダクション

値を累積するループは一般的ですが、OpenMP* ではこのようなループ専用の節を用意しています。整数の配列の合計を計算する次のループについて考えてみます。

sum = 0; 
for (i=0; i < 100; i++) { 
  sum += array[i]; // この変数は、正しい結果を生成するため
                   // 共有されなければならないが、並列実行による
                   // 競合状態を回避するため、プライベートにする必要がある
}

上記のループでは、変数 sum は正しい結果を生成するために共有する必要があります。また、複数のスレッドによるアクセスを許可するためにプライベートにする必要もあります。OpenMP* は、ループの 1 つ以上の変数の演算リダクションを効率的に結合する reduction 節を提供します。次の例では、ループで reduction 節を使用して正しい結果を生成する方法を説明します。

sum = 0; 
#pragma omp parallel for reduction(+:sum) 
for (i=0; i < 100; i++) { sum += array[i]; }

上記の例では、リダクションは各スレッドに対して変数 sum のプライベート・コピーを用意し、スレッドの終了時に値を加算して、その結果を変数 sum のグローバルコピーに格納します。

次の表は、利用可能なリダクション操作とその初期値 (演算識別値でもある) のリストです。

並列構造で変数とリダクションをカンマ区切りで指定することによって、ループで複数の演算子を使用することもできます。リダクション変数は、次の要件を満たしている必要があります。

• 1 つの REDUCTION でリストできる

• 定数として宣言できない

• 並列構造ではプライベートとして宣言できない

負荷バランスとループ・スケジュール

負荷バランス (スレッド間における作業の等分割) は、並列アプリケーションのパフォーマンスにおいて重要な要素の 1 つです。負荷バランスが良いと、稼働率が上がり、プロセッサーはほとんどの場合ビジーとなります。負荷のバランスが悪いと、一部のスレッドは他よりも著しく速く完了し、プロセッサーのリソースがアイドル状態のまま、パフォーマンスが無駄になります。

ループ構造内の負荷の不均衡は、ループの反復における実行時間の変化が原因でよく発生します。通常、ループの反復における実行時間の変化は、ソースコードを検証することによって容易に確認することができます。ほとんどの場合、ループの反復は一定の時間を消費します。そうでない場合、消費時間が類似している反復のセットを見つけられることがあります。例えば、すべての偶数反復とすべての奇数反復の消費時間が同程度の場合があります。同様に、ループの前半と後半の消費時間が同程度の場合もあります。逆に、一定の実行時間をもつ反復を見つけられないこともあります。どのような場合でも、このループ・スケジュールの補足情報を OpenMP* に渡します。これは、最適な負荷のバランスをとるようにループの反復をスレッド (そしてプロセッサー) に振り分ける際に役立ちます。

ループのすべての反復にほぼ同じ時間がかかることが分かっている場合は、OpenMP* の schedule 節を使用し、異なるスケジュール・ポリシーによってループの反復をスレッド間で等分します。さらに、大きなチャンクの使用によりフォルス・シェアリングが発生し、メモリー競合を引き起こす可能性を最小限に抑える必要があります。一般的にループはシーケンシャルにメモリーにアクセスするため、ループを大きな固まりに (2 つのスレッドを使用する場合では、前半と後半というように) 分割すると、メモリーの重複 (オーバーラッピング) の可能性を最小限に抑えることができます。これは、メモリーアクセスの問題に対しては最良の解決策であるかもしれませんが、負荷バランスに対してはそうではないかもしれません。また逆に、負荷バランスに対して最良の解決策が、メモリーのパフォーマンスに対してもそうであるとは限りません。パフォーマンスを測定し、最良の方法を探して、メモリーの使用と負荷のバランスの両方に最適な方法を見つける必要があります。

parallel for 構文を使用して、次のように OpenMP* ランタイムにループをスケジュールするように指示します。

#pragma omp parallel for schedule(kind [, chunk size])

次の表のように、4 つの異なるループ・スケジュールのタイプ (kind) を OpenMP* ランタイムに渡すことができます。オプションの引数 (chunk) は、正の整数で指定します。

次のループの並列化を行うとします。

for (i=0; i < NumElements; i++) {
   array[i] = StartVal;
   StartVal++; 
}

ループにはデータ依存が含まれているため、コードを変更せずには並列化できません。次の新しいループでは、同じように配列に格納しますが、データ依存がありません。新しいループは、コンパイラーにより生成される SIMD 命令を使用することでメリットが得られます。

#pragma omp parallel for
for (i=0; i < NumElements; i++) 
{ 
     array[i] = StartVal + i; 
}

変数 StartVal の値は増分されないため、これらのコードは全く同じではありません。このため、並列ループが終了すると、変数の値はシリアルバージョンのそれとは異なります。ループの後で StartVal の値が必要な場合は、次のように文を追加する必要があります。

// This works and is identical to the serial version. 
#pragma omp parallel for 
for (i=0; i < NumElements; i++) 
{ 
     array[i] = StartVal + i; 
} 
StartVal += NumElements;

OpenMP* タスクモデル

OpenMP タスクモデルは、より広範囲のアプリケーションを並列化できるようにします。タスクにはいくつかの OpenMP* プラグマを使用できます。

void test1(LIST *head) {
  #pragma intel omp parallel shared(head) 
  {
    #pragma omp single 
     {
      LIST *p = head; 
      while (p != NULL) {
        #pragma omp task firstprivate(p) 
        { 
          do_work1(p); 
        }
        p = p->next;
     }
    }
  }

#pragma omp parallel shared(data)
{  
  #pragma omp single private(i)
  {
    for (i=0, i<N; i++) 
    {
      #pragma omp task firstprivate(i shared(data)
      {
        do_work(data(i)); 
      }
    }
  } 
}

#pragma omp task
{ 
  ...
  #pragma omp task
  {
    do_work1();
  }
  #pragma omp task
  {  
    ...
    #pragma omp task 
    {
      do_work2(); 
    }
    ...
  }
  #pragma omp taskwait
  ... 
}