D. schedule 句

並列領域には、端に少なくとも 1 つのバリアがあり、その中にバリアが追加される場合があります。 各バリアで、チームの他のメンバーは最後のスレッドが到着するまで待機する必要があります。 この待機時間を最小限に抑えるには、すべてのスレッドが同時にバリアに到達するように、共有作業を分散する必要があります。 共有作業の一部が for コンストラクトに含まれている場合は、この目的で schedule 句を使用できます。

同じオブジェクトへの参照が繰り返し実行されている場合、for 構成要素のスケジュールの選択は主にメモリ システムの特性によって決定されます。これには、キャッシュの存在とサイズや、メモリ アクセス時間が一様であるかどうかなどが含まれます。 このような考慮事項では、ループの一部のスレッドに比較的少ない処理が割り当てられている場合でも、各スレッドが一連のループで配列の同じ要素セットを一貫して参照することをお勧めします。 この設定は、すべてのループに対して同じ境界を持つ static スケジュールを使用して行うことができます。 次の例では、2 番目のループの下限として 0 が使用されていますが、スケジュールが重要でない場合は k がより自然であると見なされています。

#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 句がある場合に、暗黙的な終了バリアまたは最も近い将来のバリアのいずれかに依存します。 スケジュールの種類ごとに、短い例として、スケジュールの種類が最適な選択であると考えられます。 各例の簡単な説明を次に示します。

static スケジュールは、単純なケースにも適しています。1つの for コンストラクトを含む並列領域で、各イテレーションは同じ量の作業を必要とします。

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

static スケジュールは、各スレッドが他のスレッドとほぼ同じ反復回数を取得するプロパティによって特徴付けられます。また、各スレッドは、割り当てられたイテレーションを個別に決定できます。 したがって、作業を分散するために同期は必要ありません。また、各反復処理に同じ作業量が必要な場合は、すべてのスレッドがほぼ同じ時間に完了する必要があります。

p スレッドのチームの場合は、切り上げ (n/p) を整数 q にします。これは、n = p * q&a を 0 <= r < p で満たします。 この例の static スケジュールの1つの実装では、最初の p-1 スレッドに q イテレーションを割り当て、最後のスレッドに q-r イテレーションを割り当てます。 もう 1 つの許容される実装では、最初の p-r スレッドに q イテレーションを割り当て、残りの r スレッドに対して q-1 イテレーションを割り当てます。 この例は、プログラムが特定の実装の詳細に依存しない理由を示しています。

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 スケジュールは、スレッドがさまざまなコンピューティング リソースを受け取る場合に便利です。これは、各イテレーションの作業量が変化するのとほとんど同じ効果があります。 同様に、動的スケジュールは、スレッドがさまざまなタイミングで for 構成要素に到達した場合にも役立ちます。ただし、このような場合は、guided スケジュールを使用することをお勧めします。

guided スケジュールは、各反復処理で同じ作業量が必要になるような for 構成要素で、スレッドが異なるタイミングで到着する可能性がある場合に適しています。 このような状況は、たとえば、 for コンストラクトの前に 1 つ以上のセクション、または nowait 句を使用して 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 = シーリング (n/p) イテレーションが割り当てられ、 n を n-q と p*k の大きな値に設定して、すべての反復が割り当てられるまで繰り返します。

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

異なるスケジュール間のトレードオフの例については、8 つのスレッド間で 1000 回のイテレーションを共有することを検討してください。 各イテレーションに一定量の作業があり、それを時間単位として使用しているとします。

すべてのスレッドが同時に開始すると、static スケジュールによって、コンストラクトは 125 単位で実行され、同期は行われません。 しかし、あるスレッドでは 100 ユニットの到着が遅延したとします。 その後、残りの 7 つのスレッドはバリアで 100 ユニットを待機し、コンストラクト全体の実行時間は 225 に増えます。

dynamic と guided の両方のスケジュールによって、バリアで2 ユニット以上待機しているスレッドがないことが保証されるため、遅延スレッドによって、コンストラクトの実行回数の増加はわずか 138 ユニットになり、同期による遅延によって増加する可能性があります。 このような遅延が無視されない場合、既定のチャンク サイズが 1 であると想定すると、dynamic の同期の数が 1000 であり、guided に対してはわずか 41 となることが重要になります。 チャンク サイズが 25 であると、dynamic と guided の両方が 150 ユニットで終了し、さらに必要な同期の遅延が発生します。これにより、数はそれぞれ 40 と 20 のみになります。