グスタフソンの法則
n を問題の大きさを示す量とする。
並列コンピュータ上でのプログラムの実行は、下記のように分解できる。
a ( n ) + b ( n ) = 1 {\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)) であるから
S = a ( n ) + p ( 1 − a ( n ) ) {\displaystyle S=a(n)+p(1-a(n))}
となる。ここで a(n) は直列的な部分の割合を示す関数である。
直列的な関数 a(n) が問題の大きさ n によって減少すると仮定すると、Speedupは、n が無限に大きくなれば希望通りp に到達する。
グスタフソンの法則は、一見するとアムダールの法則の限界から並列コンピューティングを救い出すことができるように見える。
この違いは、グスタフソンの法則は膨大な数の並列計算機を用いても直列的な部分に与える影響はなく、したがってその部分の大きさは一定とみなせると考えるのに対し、アムダールの法則はプロセッサの数が増えるにしたがって直列的な部分の影響が増加するという考え方から生まれている。