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

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

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

最良の結果を得るために、ループの個々の繰り返しで実行される作業が同じときは、システム上の異なるスレッド間に均等に作業を分割してください。この方法を静的スケジューリングといいます。

例 3-13 静的スケジューリング用の良いループ

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

静的スケジューリング (チャンクスケジューリングともいう) では、各スレッドは同じ回数の繰り返しを実行します。4 スレッドでは、各スレッドは 250 個の繰り返しを取得します。割り込みが発生せず、各スレッドが同じ速度で進行する場合、すべてのスレッドが同時に完了します。

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

各繰り返しで実行される作業が変化するときは、静的スケジューリングは通常、よい負荷バランスを実現しません。静的スケジューリングでは、すべてのスレッドが、同じ回数の繰り返しを処理します。マスタースレッドを除くすべてのスレッドは、実行を終了すると、次の並列部分が検出されるまで待つことになります。残りのプログラムの実行はマスタースレッドが行います。セルフスケジューリングでは、各スレッドは異なる小さなチャンクの繰り返しを取得し、割り当てられたチャンクの完了後、同じループからさらにチャンクを獲得しようとします。

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

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