アムダールの法則
並列実行によって期待できる高速化の限度を示す式
ある処理システムにおいて、
$ r \in (0,1):並列化可能な箇所の割合
$ n \in \N: 並列実行に使うプロセッサ数
$ E = \frac{1}{1-r+r/n}
ざっくり証明
並列化を導入する前の処理時間を$ 1としよう。
一方、並列化を導入した場合、
割合$ rだけの処理が、並列処理に置き換えられる。
理想的には、一つのプロセッサが行うべき仕事量は$ rから$ r/nへ減少する。
よって、並列化前に対して、並列化後の処理時間は$ 1 - r + r/nと表現できる。