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

同カテゴリーの次の記事

ガイド付き自動並列化 (GAP)

この記事は、インテル® ソフトウェア・ネットワークに掲載されている「More Work-Sharing with OpenMP*」(http://software.intel.com/en-us/articles/more-work-sharing-with-openmp/) の日本語参考訳です。


はじめに

OpenMP* には、ループの並列化を支援する非常に強力な指示文のセットが含まれています。あまり知られていませんが、OpenMP* はループだけではなくスレッドにも使用することができます。”parallel for” 構文では不十分な場合、プラグマ、構文、関数呼び出しを追加することでそれを補うことができます。

この記事は、経験豊富な C/C++ プログラマー向けに、OpenMP* を使ってアプリケーションのスレッドの生成、同期、終了を簡単に行う方法を紹介するシリーズ (全 3 つ) の 2 つ目です。

  • 1 つ目の記事「OpenMP* 入門」では、OpenMP* の最も一般的な機能である、ループのワークシェアを紹介します。
  • 2 つ目の記事「OpenMP* を使用したその他のワークシェア」では、ループ以外の並列化とその他の一般的な OpenMP* 機能の活用方法について説明します。
  • 最後の記事「高度な OpenMP* プログラミング」では、OpenMP* ランタイム・ライブラリーについて説明し、問題が発生した場合にアプリケーションをデバッグする方法も紹介します。

parallel 構文

このシリーズの 1 つ目の記事、「OpenMP* 入門」では、parallel for 指示句を使用して複数のスレッドにループ反復を分割する方法を説明しました。parallel for 指示句に遭遇すると、スレッドのチームが生成され、各スレッドにループ反復が分割されます。並列領域の最後でスレッドは休止し、次の並列セクションを待ちます。スレッドの生成とスレッドの休止により、多少のオーバーヘッドが発生します。しかし、次の例で示すように 2 つのループが隣接している場合、スレッドは休止する必要ありません。

#pragma omp parallel for 

for (i=0; i < x; i++)

fn1(); 

#pragma omp parallel for

// 不要なオーバーヘッド

for (i=0; i < y; i++) 

fn2();

このオーバーヘッドは、並列セクション内で作業を分割することで回避できます。次のコードは前のコードと機能的に同一ですが、並列セクションに入るオーバーヘッドが一度しかないため、より高速に実行されます。

#pragma omp parallel
{ 

#pragma omp for  

for (i=0; i < x; i++)  

   fn1();  

#pragma omp for    

for (i=0; i < y; i++)    

   fn2();

}

アプリケーションのパフォーマンスに重大な影響を与える部分 (hotspot) をすべて並列セクション内で実行するのが理想的です。ループのみで構成されるプログラムはほとんどないため、ほかの構文を使用してループ以外のコードを制御します。


sections 構文

sections 構文は、複数のスレッドにアプリケーションのコードブロック (セクション) を分割するように OpenMP* に指示します。次の例は、for ワークシェア構文と sections ワークシェア構文を使用しています。

#pragma omp parallel
{  

#pragma omp for    // for ワークシェア

for (i=0; i < x; i++)

   Fn1(); 

#pragma omp sections   // sections ワークシェア
{  

#pragma omp section   // セクション 1

   {    

   TaskA(); 

   }  

#pragma omp section   // セクション 2

   {  

   TaskB(); 

   } 

#pragma omp section   // セクション 3

   {  

   TaskC();  

   } 

}
}

上記の例では、まずスレッドのチームを作成してから、それらのスレッドにループ反復を分割します。ループが完了すると、各セクションがスレッドに分割されます。セクションはそれぞれ一度だけ実行されます。プログラムのセクションがスレッドよりも多い場合、スレッドが前のセクションを終了した後、残りのセクションが処理されます。ループ・スケジューリングとは異なり、スレッドがセクションを実行する方法、タイミング、順序は OpenMP* が完全に制御します。また、for 構文と同じ方法で private 節と reduction 節を使用して、共有またはプライベートにする変数を制御することができます。


barrier と nowait 指示句

barrier は、OpenMP* がスレッドの同期に使用する同期の一種です。並列セクションのすべてのスレッドが、barrier が指定された同じ位置に到達するまで、全スレッドは barrier で待機します。for ワークシェア構文では、特に意識することなく、暗黙の barrier が使用されています。ループの最後に、以降の作業を実行する前に、ループが完了するまですべてのスレッドを待つ暗黙の barrier が存在します。この barrier は、次のコードサンプルで示すように、nowait 節を指定することで排除できます。

#pragma omp parallel
{  

#pragma omp for nowait 

for (i=0; i < 100; i++) 

     compute_something();

#pragma omp for

for (j=0; j < 500; j++) 

     more_computations(); 

}

上記の例では、最初のループの完了をすべてのスレッドが待つことなく、最初のループを処理するスレッドが 2 つ目のループを直ちに継続して処理します。状況によっては、スレッドがアイドル状態になる時間を短くすることができるため、nowait 節は非常に効果的です。また、nowait 節を sections 構文とともに使用して暗黙の barrier を排除することもできます。

次に示すように、barrier 句の明示的な追加もサポートされています。

#pragma omp parallel  
{  

// 作業...

#pragma omp barrier 

// その他の作業...

}

この構文は、フレームバッファーを表示する前に更新する場合など、ほかの作業を行う前にすべてのスレッドがタスクを終了する必要がある場合に効果的です。


master と single 句

アプリケーションはループと並列セクションだけで構成される訳ではありません。特にオーバーヘッドを減らすために並列セクションをできるだけ大きくしている場合、並列領域内の 1 つのスレッドで 1 回だけ何らかの処理を実行する必要性が生じます。この条件を満たすため、OpenMP* には、並列セクション内に含まれているコードのシーケンスが 1 回だけ、1 つのスレッドで実行されるように指定する方法が用意されています。この場合、OpenMP* がコードを実行するスレッドを決定します。ただし、必要な場合は、マスタースレッドでのみコードを実行するように指定できます。以下に例を示します。

#pragma omp parallel  
{  

do_multiple_times();

// すべてのスレッドはこの関数を呼び出す 

#pragma omp for  

for (i=0; i < 100;i++)  

// ループは複数のスレッドに分割される 

   fn1();  

// ループの最後にある暗黙の barrier により  

// すべてのスレッドはここで同期される  

#pragma omp master 

fn_for_master_only();  

// マスタースレッドのみこの関数を呼び出す  

#pragma omp barrier

// マスタースレッド以外は、ここでマスタースレッドの到達を待つ
// マスタースレッドが到達したら、次の for 構文を実行

#pragma omp for nowait  

for (i=0; i < 100; i++)    

// ループは複数のスレッドに分割される 

   fn2();

// 上記のループには暗黙の barrier がないため、 

// スレッドはほかのスレッドを待たない。あるスレッド

// (おそらく上記のループで最初に完了したスレッド) 

// が下記のコードを継続して実行する。

#pragma omp single 

one_time_any_thread(); 

// 任意のスレッドが実行  

}

アトミック操作

コードを並列に実行する場合、共有メモリーの更新には同期が必要です。アトミック操作は、定義として割り込まれないことが保証されており、競合状態を回避するために共有メモリー領域を更新するステートメントに利用できます。下記のコード行で、開発者は変数がステートメントの実行中一定であることが重要であると判断しました。

a[i] += x; // 途中で割り込まれる可能性がある

個々のアセンブリー命令の実行は割り込まれませんが、C/C++ のような高水準言語のステートメントは割り込み可能な複数のアセンブリー命令に変換されます。上記の例では、a[i] の値は、値の読み取り、変数 x の追加、変数のメモリーへの書き込みのアセンブリー・ステートメントでそれぞれ変更されます。次の OpenMP* 構文は、ステートメントが割り込まれることなくアトミックに実行されます。

#pragma omp atomic a[i] += x; // atomic として定義されているため、割り込まれない

アトミック操作は、多重定義されていない演算における次の基本的な形式のいずれかになります。

Expr1++ ++expr1
Expr1-- --Expr1
Expr1 += expr2 Expr1 -= expr2
Expr1 *= expr2 Expr1 /= expr2
Expr1 <<= expr2 Expr1 >>= expr2
Expr1 &= expr2 Expr1 ^=expr2
Expr1 |= expr2

OpenMP* は、オペレーティング・システムおよびハードウェアの機能から、ステートメントを実装するために最も効率的な手法を選択します。


critical 句 (クリティカル・セクション)

クリティカル・セクションは、コードのブロックに対して複数のアクセスが行われることを防ぎます。スレッドがクリティカル・セクションに遭遇すると、ほかのスレッドがどのクリティカル・セクションにも入っていない場合のみ、クリティカル・セクションに入ります。次の例は名前のないクリティカル・セクションを使用しています。

#pragma omp critical
{
if (max < new_value)
   max = new_value
}

各スレッドは同じグローバル・クリティカル・セクションで事実上競合するので、グローバル、つまり無名のクリティカル・セクションはパフォーマンスに影響します。このため、OpenMP* には名前付きのクリティカル・セクションが用意されています。名前付きのクリティカル・セクションを利用すると、より細粒度の同期が可能になるため、特定のセクションでブロックが必要なスレッドだけがブロックされることになります。次の例は、前の例よりもパフォーマンスが向上します。

#pragma omp critical(maxvalue)
{
if (max < new_value)
    max = new_value
}

名前付きのクリティカル・セクションを利用すると、アプリケーションで複数のクリティカル・セクションを使用できるため、スレッドは一度に複数のクリティカル・セクションに入ることができます。ただし、入れ子のクリティカル・セクションに入ると、OpenMP* で検出できないデッドロックが発生する可能性があります。複数のクリティカル・セクションを使用する場合は、サブルーチンで隠れてしまう可能性があるクリティカル・セクションの調査に細心の注意を払うようにしてください。

firstprivate と lastprivate

データ属性を制御する OpenMP* 機能として、firstprivate 節と lastprivate 節があります。これらの節は、変数のグローバルな「マスター」コピーからプライベートな一時変数に (あるいは逆に) 値をコピーします。

firstprivate 節は、グローバル変数の値でプライベート変数の値を初期化するように OpenMP* に指示します。通常、一時的なプライベート変数には、コピーのオーバーヘッドを排除するため未定義の初期値が設定されます。lastprivate 節は、プライベート変数を破棄する前に、並列処理領域で最後に生成された変数の値をグローバル変数にコピーします。変数は firstprivate および lastprivate の両方で宣言することができます。

これらの節は通常、わずかなコード変更で使用せずに済みます。しかし、特定の状況では、これらの節は非常に便利です。例えば、次のコードはカラーイメージを白黒に変換します。

for (row=0; row < height; row++) 
{    

   for (col=0; col < width; col++) 
   {    

      pGray[col] = (BYTE) 

      (pRGB[row].red * 0.299 + 

      pRGB[row].green * 0.587 + 

      pRGB[row].blue * 0.114); 

   } 

   pGray += GrayStride; 

   pRGB += RGBStride;  

}

では、どのようにビットマップ内の正しい位置にポインターを移動すれば良いでしょうか。次のコードを使用すると、すべての反復のアドレス計算を行うことができます。

pDestLoc = pGray + col + row * GrayStride; 

pSrcLoc = pRGB + col + row * RGBStride;

ただし、このコードでは各ピクセルで余分な計算が行われます。代わりに、下記に示すように、firstprivate 節を一種の初期化として使用することができます。

BOOL FirstTime=TRUE; 

#pragma omp parallel for private (col) 

firstprivate(FirstTime, pGray, pRGB) 

for (row=0; row < height; row++)  
{  

   if (FirstTime == TRUE)  
   {    

      FirstTime = FALSE; 

      pRGB += (row * RGBStride); 

      pGray += (row * GrayStride); 

    } 

    for (col=0; col < width; col++)  
    {  

      pGray[col] = (BYTE) (pRGB[row].red * 0.299 + 

      pRGB[row].green * 0.587 +    

      pRGB[row].blue * 0.114);

    } 

    pGray += GrayStride;  

    pRGB += RGBStride;  

}

注意するべき例

質問: 次の 2 つのループを実行した場合の違いを説明してください。

ループ 1: (parallel for)

int i; 

#pragma omp parallel for  

for (i='a'; i < ='z'; i++) 

    printf ("%c", i);

ループ 2: (parallel のみ)

int i;  

#pragma omp parallel  

for (i='a'; i < ='z'; i++)    

   printf ("%c", i);

答え: このページの一番最後をご覧ください。


まとめ

OpenMP* には、アプリケーションのスレッド化に際し、プログラミングの労力を軽減するように設計された豊富な機能のセットが用意されています。この記事と (このシリーズの) 1 つ目の記事で説明されているテクニックを組み合わせることで、多くのアルゴリズムを並列化できるでしょう。


参考文献 (英語)

OpenMP* 仕様: http://www.openmp.org*

関連資料 (英語)
  • スレッド化ナレッジベース (http://software.intel.com/en-us/articles/all/1)
  • ポッドキャスト (http://software.intel.com/en-us/articles/podcasts)
コミュニティー/フォーラム (英語)
  • 並列化/マルチコア・コミュニティー (http://software.intel.com/en-us/multi-core/)
  • スレッド化ディスカッション・フォーラム (http://software.intel.com/en-us/forums/threading-on-intel-parallel-architectures/)

"注意するべき例" の答え

最初のループはアルファベットを 1 組出力します。2 つ目のループはアルファベットを出力しますが、出力する回数は不明です。変数 i がプライベートで宣言されていれば、スレッドごとにアルファベットを 1 組出力します。

コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください。

関連記事