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

並列ループの繰り返しを複数のスレッドに分散する作業を「ループのスケジューリング」といいます。速度を最大限に向上させるには、作業をスレッドに均等に分散することによって、オーバーヘッドがあまり発生しないようにすることが重要です。コンパイラは、異なる状況に合わせて、いくつかの種類のスケジューリングをすることができます。

3.6.1 静的 (チャンク) スケジューリング

ループの個々の繰り返しが実行する作業が同じである場合には、システムの複数のスレッドに均一に作業を分散すると効果があります。この方法を静的スケジューリングといいます。

例 3–13 静的スケジューリングに向いたループ

for (i=1; i < 1000; i++) {
    sum += a[i]*b[i];       /* S1 */
}

静的スケジューリング (チャンクスケジューリングともいう) では、各スレッドは同じ回数の繰り返しを実行します。たとえばスレッドの数が 4 であれば、前述の例では、各スレッドで 250 回の繰り返しが実行されます。割り込みが発生しないものと仮定し、各スレッドが同じ早さで作業を進行していくと、すべてのスレッドが同時に終了します。

3.6.2 セルフスケジューリング

各繰り返しで実行する作業が異なる場合、静的スケジューリングでは、一般に、よい負荷バランスを得ることができなくなります。静的スケジューリングでは、すべてのスレッドが、同じ回数の繰り返しを処理します。マスタースレッドを除くすべてのスレッドは、実行を終了すると、次の並列部分が検出されるまで待つことになります。残りのプログラムの実行はマスタースレッドが行います。セルフスケジューリングでは、各スレッドが異なる小さな繰り返しを処理し、割り当てられた処理が終了すると、同じループのさらに別の繰り返しを実行することになります。

3.6.3 ガイド付きセルフスケジューリング

ガイド付きセルフスケジューリング (Guided Self Scheduling、GSS) では、各スレッドは、連続した小数の繰り返しをいくつか受け持ちます。各繰り返しで作業量が異なるような場合には、GSS によって、負荷のバランスが保たれるようになります。