アムダールの法則
アムダールの法則は、並列化しても問題の大きさが変化しないという前提と、問題には並列化できない部分があるという前提の上で、逐次的アルゴリズムとそれに対応したアルゴリズムの並列化実装によって期待できる高速化の関係をモデル化したものである。例えば、ある大きさの問題をあるアルゴリズムを並列化実装したもので実行した場合、問題の12%を並列化によって好きなように高速化できるとする(残り88%は並列化できない処理である)。アムダールの法則によれば、このときの並列化していない実装と比較した並列化版による高速化は最大でも 1 1 − 0.12 = 1.136 {\displaystyle {\frac {1}{1-0.12}}=1.136} 倍にしかならない。
より技術的に解説すると、この法則は、ある計算のうち高速化によって影響を受ける部分の割合 P とその性能向上率 S から、全体として達成可能な性能向上率を求めるものである。例えば、ある改良が計算全体の 30% に影響する場合、P は 0.3 である。また、その部分が2倍に高速化されるなら S は 2 である。アムダールの法則によれば、全体としての性能向上は次の式で表される。
1 ( 1 − P ) + P S {\displaystyle {\frac {1}{(1-P)+{\frac {P}{S}}}}} .
従来の計算時間を 1 とする。改良されたプログラムの計算時間は、改良と関係しない部分の計算時間(1 − P)と改良された部分の計算時間(P/S)の合計となる。全体の性能向上率は、従来の計算時間を改良されたプログラムの計算時間で割ったものであり、上の式はそれを表している。
もう少し複雑な例を挙げる。