グスタフソンの法則
グスタフソンの法則(英: Gustafson's law、Gustafson-Barsis' law としても知られる)は、計算機工学における法則で、「十分に大きな規模の問題は、効率的に並列化して解くことができる」事を示すものである。グスタフソンの法則は、並列化によってプログラムが高速化できる限界を示したアムダールの法則と密接に関係している。本法則は、ジョン・グスタフソンによって1988年に初めて示された。
P がプロセッサの数であり、S がSpeedup、α がプロセスの並列化できない部分であるとすると、下記が成立する。
S ( P ) = P − α ( P − 1 ) {\displaystyle S(P)=P-\alpha (P-1)}
グスタフソンの法則は、計算機の規模が大きくなると利用可能な計算能力を使い切るほど性能がスケールしないというアムダールの法則に欠けていた部分に対応するものである。グスタフソンの法則では、問題の規模が固定である、また並列プロセッサ上の計算の負荷が一定であるという仮定を取り除き、代わりに固定時間の概念を提唱し、これにより高速化がスケールすることを示した。
アムダールの法則は、作業負荷や問題の規模が一定であることに基づいている。すなわち、プログラムの直列的な部分は、計算機の規模(すなわちプロセッサ数)によらず変化しない。しかし、並列化可能な部分は n 個のプロセッサに平等に分配可能であるとする。アムダールの法則の影響により、研究機関は並列コンパイラを開発し、問題の直列的な部分を減らし、並列システム性能を上げようとするようになった。