3.5.1.2 ガスタフソンの法則

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

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

/*
* 配列を初期化
*/
for (i=0; i < n; i++) {
    for (j=0; j < n; j++) {
            a[i][j] = 0.0;
            b[i][j] = ...
            c[i][j] = ...
    }
}
/*
* 行列の積を求める
*/
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 が大きくなると、並列実行部分に費やされる時間が順次実行の部分に対するものよりも早い勢いで大きくなります。この問題の場合は、問題のサイズが大きくなるにつれてプロセッサの数を増やす方法が有効です。