プログラムのうち並列化できる部分の割合と、使うプロセッサ(コア)の数を入れると、全体がどれだけ速くなるかをアムダールの法則で計算します。問題の大きさを固定したときの限界と、プロセッサの数に合わせて問題を大きくするグスタフソンの法則の見方を、対数目盛のグラフで並べて比べられます。
細い破線は理想的な速度向上(N倍)、青い線はアムダールの法則、緑の線はグスタフソンの法則です。両軸とも対数目盛です。通信や同期、負荷の偏りによるオーバーヘッドは含めていないため、実際の速度向上はこれより小さくなるのが普通です。
ほかの入力は今の値のまま、選んだ入力だけを今の値の1/4〜4倍の範囲で変えたときの結果です。赤い点が今の値です。
1台のプロセッサでの実行時間を1とし、そのうち並列化できる部分の割合をpとします。プロセッサをN台使うと並列部分の時間は p/N に縮みますが、並列化できない逐次部分 (1 − p) はそのまま残ります。そのため速度向上率は S = 1/((1 − p) + p/N) です。Nをいくら大きくしても逐次部分は消えないので、上限は 1/(1 − p) になります。既定値の p = 95%、N = 16 では S ≈ 9.14倍で、上限は20倍です。わずか5%の逐次部分が、到達できる速さを決めてしまいます。
並列効率は E = S/N で、プロセッサ1台あたりがどれだけ有効に働いているかを表します。既定値では 9.14 ÷ 16 ≈ 57.1% で、プロセッサの能力の4割以上は実質的に遊んでいることになります。グラフでは、Nが小さいうちは青い線が破線(理想のN倍)に沿っていますが、やがて離れて、上限に向かって水平になります。p = 95% のまま N = 64 にすると S ≈ 15.4倍で、効率は約24%まで下がります。効率が急に落ち始めるあたりが、コストに見合うプロセッサ数の目安です。
アムダールの法則は、問題の大きさを固定してプロセッサを増やす「強いスケーリング」を考えます。これに対してグスタフソンの法則は、プロセッサを増やしたぶん問題を大きくして同じ時間で解く「弱いスケーリング」を考え、S = (1 − p) + p·N となります。シミュレーションの格子を細かくするように、問題を大きくすると並列部分だけが増えるため、ほぼNに比例した効果が得られます。ただし、この式のpはN台で実行したときの時間に占める割合で、アムダールの法則のpとは定義が違う点に注意してください。
実際のプログラムでは、スレッドの起動、データの通信、ロックやバリア同期の待ち、負荷の偏りなどが加わるため、速度向上はアムダールの法則の値よりさらに小さくなります。コアを増やすより先に逐次部分を減らすほうが効くことも多く、プロファイラで時間のかかる部分を確かめてから並列化するのが基本です。GPUでも、ホストとの間のデータ転送やカーネルの起動が逐次部分として効いてきます。チップ設計で少数の高性能なコアと多数の小さなコアを組み合わせるのも、逐次部分と並列部分の両方を速くするためです。
正解：B. 1.6倍
改善後の時間は、速くしない残りの50%(0.5)と、4倍速くした50%(0.5÷4=0.125)の合計で0.625になります。速度向上率は1÷0.625=1.6倍です。速くした部分をどれだけ速くしても、残りの50%はそのまま残るので、全体は最大でも2倍にしかなりません。全体を大きく速くするには、時間を多く占める部分を見つけて改善する必要があります。
正解：A. 時間を多く使っている部分(よくある場合)を速くすることを優先する
全体の1%しか使っていない部分を無限に速くしても、全体は約1%しか速くなりません。一方、80%を使っている部分を2倍速くすれば、全体は約1.7倍になります。そのため、まずプロファイラなどで時間を多く使っている部分を見つけ、そこから改善するのが基本です。「よくある場合を速くせよ」は、コンピュータの設計でも繰り返し使われる原則です。
アムダールの法則では、上限は 1/(1 − 0.9) = 10倍です。プロセッサを16台使っても 1/(0.1 + 0.9/16) = 6.4倍にとどまり、並列効率は40%です。残りの10%の逐次部分を減らさない限り、10倍を超えることはありません。
矛盾していません。アムダールの法則は問題の大きさを固定した強いスケーリング、グスタフソンの法則は問題をプロセッサの数に合わせて大きくする弱いスケーリングを扱っており、前提が違います。同じ問題を速く解きたいのか、同じ時間でより大きな問題を解きたいのかで、使う見方を選びます。
あります。プロセッサを増やすと1台あたりのデータが減ってキャッシュに収まるようになり、メモリアクセスが速くなる場合などに、超線形(スーパーリニア)な速度向上が見られます。アムダールの法則は、こうした効果を含まないモデルです。