3.5.1 アムダールの法則

決まったサイズの問題の処理速度の向上度は、一般にアムダールの法則によって予測されます。アムダールの法則は単純に、特定の問題に対して並列化がもたらす速度の向上は、問題の逐次処理部分によって制限されると説明しています。次の式は、逐次処理領域で費やされる時間の割合が F であり、時間のうち残りの割合が P 個のプロセッサの間で一様に費やされる状況における問題の速度向上について説明します。この式からわかるように、式の 2 番目の項の値がゼロになると、値が決まっている 1 番目の項によって全体的な速度の向上度が制限されます。

次の図に、この概念を示します。灰色の部分がプログラム中の逐次処理部分を表現しています。この部分は 1、2、4、8 プロセッサ各々の場合で一定であるのに対し、斜線部分がプログラムの並列処理部分で、複数のプロセッサ間で一様に分割され、処理時間が短くなっています。

図 3–3 固定された問題の処理速度の向上

プロセッサの数が増加するにつれ、各プログラムの並列処理部分の所要時間は減少していますが、各プログラムの逐次処理部分は同じままです。

ただし実際には、複数のプロセッサに作業を分散し通信するためのオーバーヘッドが存在します。このようなオーバーヘッドは、プロセッサの数に対して一定であったり、そうでなかったりします。

次の図には、プログラムに逐次処理部分がそれぞれ 0%、2%、5%、10% 含まれる場合の理想的な速度向上が示されています。この図では、オーバーヘッドは想定されていません。

図 3–4 アムダールの法則による処理速度向上の曲線

グラフは、オーバーヘッドがないと想定した場合、0%、2%、5%、および 10% の逐次処理部分を含むプログラムでの理想的な速度向上を示しています。横軸はプロセッサの数、縦軸は速度を表しています。

3.5.1.1 オーバーヘッド

モデルにオーバーヘッドの影響を取り入れると、速度向上の曲線は大幅に変わります。ここでは、説明上 2 つの部分、つまり、プロセッサの数には無関係な固定部分と、使用されるプロセッサの 2 乗で増加する可変部分から成るオーバーヘッドを想定します。

S 分の 1 は、{F プラス (1 マイナス P 分の F) プラス K1 プラス K2 P 二乗} 分の 1 に等しいです。

この式で K₁ と K₂ は一定の係数です。この仮定では、速度向上の曲線は次の図のようになります。この場合、速度の向上にピーク点があることに注目してください。ある点を越えると、プロセッサを増加させてもパフォーマンスが下がり始めます。

図 3–5 オーバーヘッドがある場合の速度向上の曲線

グラフは、すべてのプログラムで 5 プロセッサのときにもっとも処理速度が早く、8 プロセッサまで増えると徐々に遅くなることを示しています。横軸はプロセッサの数、縦軸は速度を表しています。

3.5.1.2 ガスタフソンの法則

アムダールの法則では、実際の問題を並列化するときの速度向上の効果を正しく予測できません。プログラムの逐次処理部分に費やされる時間の割合は、問題のサイズに依存することがあります。つまり、問題のサイズが増加すると、速度向上の可能性が大きくなる場合があります。例を使って説明します。

例 3–12 問題サイズの拡大により速度向上の可能性が大きくなることがある

/*
* initialize the arrays
*/
for (i=0; i < n; i++) {
    for (j=0; j < n; j++) {
            a[i][j] = 0.0;
            b[i][j] = ...
            c[i][j] = ...
    }
}
/*
* matrix multiply
*/
for (i=0; i < n; i++) {
    for(j=0; j < n; j++) {
            for (k=0; k < n; k++) {
                a[i][j] = b[i][k]*c[k][j];
            }
    }
}

理想的にオーバーヘッドがゼロで、2 番目に入れ子にされたループが並列に実行されると仮定すると、問題のサイズが小さい場合 (すなわち n の値が小さい) と、プログラムの順次実行部分と並列実行部分の大きさがそれほど違わないことがわかります。ところが、n が大きくなると、並列実行部分に費やされる時間が順次実行の部分に対するものよりも早い勢いで大きくなります。この問題の場合は、問題のサイズが大きくなるにつれてプロセッサの数を増やす方法が有効です。