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

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

#ifdef _OPENMP

   fn();

#endif

簡単な例

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

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

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

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 は、プライベートでなければなりません。

// 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 はプライベート・メモリーとして宣言されているため、問題が解決されています。

#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);

>}

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

#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]; // 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 のグローバルコピーに格納します。

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

演算子

一時的なプライベート変数の初期化

+ (加算)

0

- (減算)

0

* (乗算)

1

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

~0

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

0

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

0

&& (条件付き AND)

1

|| (条件付き OR)

0

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

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

負荷のバランス (スレッド間における作業の等分割) は、並列アプリケーションのパフォーマンスにおいて重要な属性の 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 パラメーターは、使用するチャンクサイズの最小値を指定します。

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

auto

schedule (auto) が指定されると、スケジューリングに関する決定はコンパイラーが行います。チーム内のスレッドへの反復のマッピングはコンパイラーが選択します。

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;

タスクモデル

インテル® コンパイラーによって実装されるタスクモデルは、OpenMP* でより広範囲のアプリケーションを並列化できるようにします。タスクに使用される宣言子は次のとおりです。

#pragma omp task [clause[[,] clause] ...] new-line

      structured-block

clause は次のいずれかです。

 

#pragma omp taskwait new-line

#pragma omp task 宣言子は、次のように明示的にタスク領域を定義します。

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;

      }

    }

  }

}

タスク領域のバインド・スレッド・セットは、現在の並列チームです。タスク領域は、最内の囲まれた PARALLEL 領域にバインドします。スレッドがタスク構造に到達すると、その構造内で囲まれた構造化ブロックからタスクが生成されます。到達スレッドは、ただちにタスクを実行するか、または実行を保留します。タスク構造は、外側のタスクの中に入れ子されることがありますが、内側タスクのタスク領域は、外側タスクのタスク領域の一部ではありません。

使用される節

TASK 宣言子には、オプションで指定した節をカンマ区切りのリストで指定できます。タスクのデータ環境は、タスク構造上のデータ共有属性節と適用されるデフォルトに従って作成されます。これらの節は前のセクションで示しています。次の例は、1 つのスレッドで N タスクを生成し、それらのタスクを並列チーム内のスレッド群で実行する方法を示しています。

#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));

        }

     }

  }

}

タスク・スケジューリング

スレッドがタスク・スケジューリング・ポイントに到達すると、タスクスイッチを実行し、現在のチームにバインドされている異なるタスクの実行を開始するか、または再開します。タスク・スケジューリング・ポイントは次の場所で暗黙的に指定されます。

スレッドがタスク・スケジューリング・ポイントに到達すると、次のいずれかを行います。

上記の選択肢が複数存在する場合は、どれが選択されるかは不明です。

タスク・スケジューリングの制約


  1. if 式が false に評価される if 節を含む構文の明示的タスクは、タスク生成後ただちに実行されます。

  2. 新しいタイドなタスクのほかのスケジューリングは、現在、スレッドにタイドされ、またバリア領域で中断されていないタスク領域セットにより制約されます。このセットが空の場合は、任意の新しいタスクがスケジューリングされます。そうでない場合は、新しいタイドなタスクは、セット内の各タスクの子孫である場合のみスケジューリングされます。タスク・スケジューリングについてその他の仮定に基づくプログラムは規格に準拠していません。

Note icon

タスク・スケジューリング・ポイントは、動的にタスク領域をパーツに分割します。それぞれのパーツは、開始から終了まで割り込まれることなく実行されます。同じタスク領域の各パーツは、検出された順に実行されます。タスクの同期化構造がない場合、スレッドが異なるスケジュールのタスクを実行する順番は不定です。

正しいプログラムは、上記の規則に沿った、考えられるすべてのスケジューリング・シーケンスで正常かつ一貫した動作を行わなければなりません。

TASKWAIT プラグマ

TASKWAIT プラグマは、現在のタスクが開始してから生成された子タスクの完了時点で待機するように指定します。taskwait 領域は現在のタスク領域にバインドします。taskwait 領域のバインドするスレッドセットは、検出したスレッドです。

taskwait 領域には、現在のタスク領域に暗黙的なタスク・スケジューリング・ポイントが含まれます。現在のタスク領域は、taskwait 領域の前に生成された子タスクの実行がすべて完了するまで、タスク・スケジューリング・ポイントで一時停止します。

#pragma omp task

{ ...

  #pragma omp task

  { do_work1(); }

  #pragma omp task

  {  ...

   #pragma omp task

     {  do_work2(); }

       ...

     }

     #pragma omp taskwait

     ...

}

これらの宣言子についての詳細は、「OpenMP* C++ Compiler Directives」(英語) を参照してください。