TL;DR
十分に大きな規模の問題は、効率的に並列化して解くことができる、という法則。1988 年に John L. Gustafson と Edwin H. Barsis が提唱した。
仕組み
この法則はアムダールの法則に対して次の 2 点で反論している。
- 多くの資源が使えるとき、問題の大きさは変わる。 大量の資源を持っていて、半分の資源を使ってもパフォーマンスが変わらないと分かれば、余った資源を別のことに割り当てられる
- 問題のサイズを大きくしても、問題の並列化できない部分は、通常はサイズに比例して増えない
この 2 点を踏まえると、速度は使える並列資源の量に対して線形に伸びる。分かりやすく言えば、余分な資源を使い続ける方法さえ見つければ、逐次処理の部分に制限されずに性能を上げ続けられる。
注意点
この考え方は、逐次処理の部分が一定であることを前提にしている。Gustafson によれば、多くの種類のプログラムではこの部分は一定である。