グスタフソンの法則

グスタフソンの法則（英: Gustafson's law、Gustafson-Barsis' law としても知られる）は、計算機工学における法則で、「十分に大きな規模の問題は、効率的に並列化して解くことができる」事を示すものである。グスタフソンの法則は、並列化によってプログラムが高速化できる限界を示したアムダールの法則と密接に関係している。本法則は、ジョン・グスタフソンによって1988年に初めて示された。

P がプロセッサの数であり、S がSpeedup、α がプロセスの並列化できない部分であるとすると、下記が成立する。

$S(P)=P-\alpha (P-1)$

グスタフソンの法則は、計算機の規模が大きくなると利用可能な計算能力を使い切るほど性能がスケールしないというアムダールの法則に欠けていた部分に対応するものである。グスタフソンの法則では、問題の規模が固定である、また並列プロセッサ上の計算の負荷が一定であるという仮定を取り除き、代わりに固定時間の概念を提唱し、これにより高速化がスケールすることを示した。

アムダールの法則は、作業負荷や問題の規模が一定であることに基づいている。すなわち、プログラムの直列的な部分は、計算機の規模（すなわちプロセッサ数）によらず変化しない。しかし、並列化可能な部分は n 個のプロセッサに平等に分配可能であるとする。アムダールの法則の影響により、研究機関は並列コンパイラを開発し、問題の直列的な部分を減らし、並列システム性能を上げようとするようになった。

グスタフソンの法則の実現

n を問題の大きさを示す量とする。

並列コンピュータ上でのプログラムの実行は、下記のように分解できる。

$a(n)+b(n)=1$

ここで、a は直列的な部分の割合で、b は並列的な部分の割合である。ただしオーバーヘッドは無視する。

一方直列的なコンピュータでは p を並列化した際のプロセッサ数とすると、相対的な処理時間は a(n) + p · b(n) である。

すなわちSpeedupは、直列的な場合の a(n) + b(n) = 1 に対して並列化した場合には (a(n) + p · b(n)) であるから

$S=a(n)+p(1-a(n))$

となる。ここで a(n) は直列的な部分の割合を示す関数である。

直列的な関数 a(n) が問題の大きさ n によって減少すると仮定すると、Speedupは、n が無限に大きくなれば希望通りp に到達する。

グスタフソンの法則は、一見するとアムダールの法則の限界から並列コンピューティングを救い出すことができるように見える。

この違いは、グスタフソンの法則は膨大な数の並列計算機を用いても直列的な部分に与える影響はなく、したがってその部分の大きさは一定とみなせると考えるのに対し、アムダールの法則はプロセッサの数が増えるにしたがって直列的な部分の影響が増加するという考え方から生まれている。

二つの法則の考え方を示した比喩

アムダールの法則の示すところは下記のように喩えられる:

「

60マイル離れた二つの都市を車で移動しており、既に 30 mph で1時間かけ、半分の距離を走行してきたとする（直列実行時間）。後半どれだけ速く走ることができたとしても、既に1時間走行しており、全体で60マイルしか距離がなく、到着までに平均速度 90 mph を達成することは不可能である。無限の速度で走行し一瞬で到着しても、60 mph にしかならない。

」

一方グスタフソンの法則は下記のように喩えられる:

「

一台の自動車を 90 mph 以下で運転してきたとする。十分な時間と距離（残りの計算）があれば、既に運転してきた時間・距離によらず、車の平均速度を最終的に 90 mph に到達させることができる。例えば、すでに 1時間 30 mphで運転したとすると、あと2時間 120 mph で運転するか、あと1時間 150 mphで走行すれば、90 mph に到達することができる。

」

グスタフソンの法則の限界

解決する問題によっては本質的に大規模なデータセットを持たないものがある。例えば、世界中の人間に対して一つずつ存在するデータを処理するような問題は、年間に数パーセントしか大きくならない。

非線形のアルゴリズムは、グスタフソンの法則によって「明らかに」なる並列性をうまく活かす事ができない場合がある。Snyder は、O(N³) のアルゴリズムでは並列性を二倍にしても問題の大きさを 9% 増加させられるだけだと指摘している。したがって、非常に高い並列性を実現したとしても、もともとの並列化の度合いが少ない方法に対してあまり利点がない可能性がある。しかし実際には、特にクラスタや Condor のような分散コンピュータを用いることで、大きな進歩が達成されてきている。

外部リンク

• Reevaluating Amdahl's Law - the paper in which John Gustafson first described his Law. Originally published in Communications of the ACM 31(5), 1988. pp. 532-533
• [1] -- Lawrence Snyder, "Type Architectures, Shared Memory, and The Corrolary of Modest Potential"