グスタフソンの法則

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "グスタフソンの法則" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2024年9月)

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

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

${\displaystyle S(P)=P-\alpha (P-1)}$

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

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

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

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

${\displaystyle a(n)+b(n)=1}$

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

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

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

${\displaystyle S=a(n)+p(1-a(n))}$

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

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

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

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

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

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

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

非線形のアルゴリズムは、グスタフソンの法則によって「明らかに」なる並列性をうまく活かす事ができない場合がある。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"