D. schedule 句の使用

1 つの並行領域には、末尾に最低でも 1 つのバリアが存在し、さらに追加のバリアが含まれている場合があります。各バリアにおいて、チームの各メンバは、最後のスレッドがバリアに到達するまで待機する必要があります。この待機時間をできるだけ短くするには、すべてのスレッドがバリアにほぼ同時に到着できるように共有作業を分散する必要があります。この共有作業が for コンストラクトに含まれている場合、schedule 句を使用することでこの目的を達成できます。

同じオブジェクトへの参照が繰り返される場合、for コンストラクトに対するスケジュールの選択は、キャッシュの有無とサイズ、およびメモリ アクセス時間を均一にするかしないかなど、主にメモリ システムの特性によって決定される場合があります。このような考慮事項により、スレッドによっては、ループ内で割り当てられる作業量が少なくなる場合があっても、各スレッドに、一連のループで、ある配列の同じ要素セットを一貫して参照させることが必要になる場合があります。これは、static スケジュールを使用して、すべてのループに対して同じ範囲を設定することにより行うことができます。次の例では、2 番目のループにおいて、このスケジュールが重要でない場合に k の方が自然であっても、0 が下限になっていることに注意してください。

#pragma omp parallel
{
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    a[i] = work1(i);
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    if(i>=k) a[i] += work2(i);
}

以下の残りの例では、メモリ アクセスが重要事項ではなく、特に明記されていなければ、すべてのスレッドが比較可能な計算リソースを受け取ることを前提としています。これらの場合、for コンストラクトのスケジュールの選択は、一番近い前のバリアと、末尾に存在する暗黙的なバリアまたは、nowait 句がある場合であれば一番近い後続のバリア間で実行されるすべての共有作業に依存します。スケジュールの各タイプについて、そのタイプが最適な選択であることを示す簡単な例を示します。各例の後に簡単な説明も付記します。

各反復処理が、同じ作業量を必要とする単一の for コンストラクトが含まれる並行領域という最も簡単な例についても static スケジュールが適しています。

#pragma omp parallel for schedule(static)
for(i=0; i<n; i++) {
  invariant_amount_of_work(i);
}

static スケジュールには、各スレッドが他のスレッドとほぼ同じ反復回数を取得し、各スレッドが割り当てられる反復処理を独立して解決できるという特徴があります。したがって、作業を分散するのに同期は必要なく、各反復処理が同じ作業量であるという前提の下、すべてのスレッドがほぼ同じタイミングで終了します。

p スレッドで構成されるチームについて、ceiling(n/p) が整数 q であるとします。このとき、n = p*q - r、0 <= r < p が成り立ちます。この例の static スケジュールのある実装では、q 回を最初の p–1 スレッドに割り当て、q-r 回を最後のスレッドに割り当てます。別の実装では、q 回を最初の p-r スレッドに割り当て、q-1 回を残りの r スレッドに割り当てるものもあります。これは、プログラムが特定の実装に依存すべきではないことを示す一例です。

dynamic スケジュールは、各反復処理における作業量が可変または予測不能である for コンストラクトに適しています。

#pragma omp parallel for schedule(dynamic)
  for(i=0; i<n; i++) {
    unpredictable_amount_of_work(i);
}

dynamic スケジュールには、どのスレッドも、別のスレッドがその最後の反復処理を実行するより長くはバリアで待機しないという特徴があります。これは、反復処理が一度に 1 つずつ使用できるようになったスレッドに割り当てられ、各割り当てに対して同期が存在することを必要とします。同期のオーバーヘッドは、1 より大きい最小チャンク サイズ k を指定することにより削減できます。これにより、スレッドは、残りの反復回数が k より少なくなるまで、一度に k ずつ割り当てられます。これにより、どのスレッドも、別のスレッドがその最後のチャンクである最大 k 回の反復処理を実行するより長くはバリアで待機しないことが保証されます。

dynamic スケジュールは、スレッドが可変の計算リソースを受け取る場合に便利です。その影響は、各反復処理の作業量が可変である場合とほぼ同じです。また、dynamic スケジュールは、スレッドが for コンストラクトにさまざまなタイミングで到着する場合にも便利です。ただし、これらの場合については、guided スケジュールの方が適している場合もあります。

guided スケジュールは、各反復処理で同じ作業量が求められる for コンストラクトにスレッドがさまざまなタイミングで到着する場合に適しています。これは、たとえば、for コンストラクトの前に nowait 句の付いた 1 つ以上の sections コンストラクトまたは for コンストラクトがある場合などです。

#pragma omp parallel
{
  #pragma omp sections nowait
  {
    // ...
  }
  #pragma omp for schedule(guided)
  for(i=0; i<n; i++) {
    invariant_amount_of_work(i);
  }
}

dynamic スケジュールと同様、guided スケジュールでは、どのスレッドも、別のスレッドがその最後の反復処理、またはチャンク サイズとして k が指定されている場合は最後の k 回分の反復処理を実行するより長くはバリアで待機しないことを保証します。これらのスケジュールの中でも、guided スケジュールは、同期を最も必要としないことを特徴とします。チャンク サイズが k の場合、通常の実装であれば、q = ceiling(n/p) 回を最初の使用可能なスレッドに割り当て、n を n-q と p*k の大きい方に設定し、すべての反復処理が割り当てられるまでこれを繰り返します。

最適なスケジュールの選択が、これらの例のように明確ではない場合、runtime スケジュールを使用することにより、プログラムを変更したり再コンパイルしたりしないで、さまざまなスケジュールやチャンク サイズに対応できます。また、最適なスケジュールが、プログラムに適用される入力データに (なんらかの予測可能な方法で) 依存する場合にもこのタイプは便利です。

どのスケジュール タイプが適しているか考える際、1,000 回の反復処理を 8 スレッドで共有する場合について考えてみてください。各反復処理における作業量が固定であると仮定し、これを時間単位として使用します。

すべてのスレッドが同時に開始した場合、static スケジュールでは、そのコンストラクトは同期なしの 125 単位で実行されます。このとき、1 つのスレッドで 100 単位の到着が遅れる場合を考えてみます。残りの 7 つのスレッドはバリアで 100 単位分待機することになるので、コンストラクト全体の実行時間は 225 に増加します。

dynamic スケジュールと guided スケジュールでは、どのスレッドもバリアで 2 単位以上は待機しないことになるので、遅延のスレッドが起こった場合でも、コンストラクトの実行時間は 138 単位にしか増加しません。ただし、これに同期処理から発生する遅延分も加算されます。この遅延が無視できない場合、チャンク サイズが既定値の 1 であれば、dynamic では同期数が 1000 であるのに比べ、guided では 41 で済むことに大きな意味が出てきます。チャンク サイズが 25 であれば、dynamic と guided は両方とも 150 単位で終了し、それぞれ必要な同期数 40 と 20 のみによる遅延が加算されます。