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

ハイパースレッディング・テクノロジー対応のプロセッサーでその機能を活用し、パフォーマンスを最大限に引き出すには、アプリケーションを並列実行する必要があります。並列実行にはスレッドが必要です。アプリケーションのスレッド化は容易ではありませんが、OpenMP* を使用することによりプロセスを簡単にすることができます。OpenMP のプラグマを使用すると、ほとんどのループは簡単な 1 つの文でスレッド化できます。ここでは、OpenMP を使用してループを並列化する方法 (ワークシェアリング) について説明します。

ほとんどのループは、ループの直前にプラグマを 1 つ挿入することによってスレッド化することができます。また、詳細をコンパイラーと OpenMP に任せることにより、どのループをスレッド化すべきか、パフォーマンスを最大限に向上させるにはどのようにアルゴリズムを再編成すべきかといった決断により多くの時間をかけることができます。OpenMP は、hotspot (アプリケーションで最も時間のかかるループ) のスレッド化に使用されると、最大限のパフォーマンスを実現します。

次の例では、OpenMP の機能を活用する方法を説明します。以下のループは、32 ビットの RGB (赤、緑、青) ピクセルを 8 ビットのグレースケール・ピクセルに変換します。並列実行に必要なのは、ループの直前に挿入された 1 つのプラグマだけです。

#pragma omp parallel for

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

{

   pGrayScaleBitmap[i] = (unsigned BYTE)

            (pRGBBitmap[i].red * 0.299 +

             pRGBBitmap[i].green * 0.587 +

             pRGBBitmap[i].blue * 0.114);

}

最初に、この例ではワークシェアリングを使用しています。OpenMP では、スレッド間で作業を分配することをワークシェアリングと呼びます。この例のようにワークシェアリングを for 構造とともに使用した場合、ループの反復は複数のスレッドに振り分けられます。OpenMP は作成するスレッド数、および作成、同期、破棄で最良な方法を決定します。OpenMP では、ループのスレッド化において次の 5 つの制約があります。

これらの制約に合致しないループでも、制約に従うよう簡単に書き換えることができます。

コンパイルの基本

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

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

#ifdef _OPENMP

   fn();

#endif

簡単な例

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

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

例 1

// clip an array to 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 の平方根の表を生成します。

例 2

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 度プログラムが動作しても、すべての状態で動作するとは限りません。ハイパースレッディング・テクノロジーに対応したマシンや複数の物理プロセッサーを搭載したマシンなど、さまざまなマシンでプログラムをテストすると、競合状態を識別するのに役立ちます。

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

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

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

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

例: public 変数

// Variable temp is shared among all threads, so while one thread

// is reading variable temp another thread might be writing to it

#pragma omp parallel for

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

{

   temp = array[i];

   array[i] = do_something(temp);

}

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

例: private 変数

#pragma omp parallel for

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

{

   int temp; // variables declared within a parallel construct

             // are, by definition, private

   temp = array[i];

   array[i] = do_something(temp);

}

次の方法で、一時的な変数を作成することもできます。

例: private 変数 (代替バージョン)

#pragma omp parallel for private(temp)

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

{

   temp = array[i];

   array[i] = do_something(temp);

}

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

リダクション

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

sum = 0;

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

{

sum += array[i]; // this variable needs to be shared to generate

                 // the correct results, but private to avoid

                 // race conditions from parallel execution

}

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

sum = 0;

#pragma omp parallel for reduction(+:sum)

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

{

   sum += array[i];

}

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

次の表は、利用可能なリダクションと一時的な private 変数の初期変数 (演算識別値でもある) のリストです。

演算子

一時的な private 変数の初期化

+ (加算)

0

- (減算)

0

* (乗算)

1

& (ビット単位の AND (論理積))

~0

| (ビット単位の OR (論理和))

0

^ (ビット単位の XOR (排他的論理和))

0

&& (条件付き AND)

1

|| (条件付き OR)

0

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

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

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

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

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

次のように parallel 構造構文を使用して、OpenMP にループ・スケジューリングを行うよう指示します。

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

次の表のように、4 つの異なるループ・スケジューリングのタイプ (kind) を OpenMP に渡すことができます。オプションのパラメーター (chunk) は、ループ不変の正の整数でなければなりません。

タイプ (kind)

説明

static

ループを同じ大きさのチャンク、または (ループの反復数がスレッド数にチャンクサイズを掛けた値で割り切れない場合は) できるだけ同じ大きさのチャンクに分割します。デフォルトでは、チャンクサイズはループカウントをスレッド数で割った値です。

反復をインターリーブするにはチャンクを 1 に設定します。

dynamic

内部の作業キューを使用して、ループの反復のチャンク・サイズ・ブロックを各スレッドに渡します。スレッドが終了すると、作業キューの一番上からループの反復の次のブロックを取得します。

デフォルトでは、チャンクサイズは 1 です。このスケジューリングのヒントには余分なオーバーヘッドがかかるため、使用する際は注意してください。

guided

dynamic スケジューリングと同じですが、大きなチャンクサイズから開始して、徐々に小さくしていき、スレッドが作業キューから作業を取得するのにかかる時間を短縮します。オプションの chunk パラメーターは、使用するチャンクサイズの最小値を指定します。

デフォルトでは、チャンクサイズはループカウントをスレッド数で割った値とほぼ同じです。

runtime

OMP_SCHEDULE環境変数を使用して、3 つのループ・スケジューリングのどれを使用するのかを指定します。

OMP_SCHEDULE は、書式指定された文字列で、parallel 構造にそのまま出力されます。

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

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;