逐次的プログラムの高速化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/11 05:35 UTC 版)
「アムダールの法則」の記事における「逐次的プログラムの高速化」の解説
ある逐次的プログラムを改良したときの最大高速化係数は、そのプログラムの一部を p {\displaystyle p} 倍に高速化した場合、次の不等式で表される。 maximum speedup ≤ p 1 + f ⋅ ( p − 1 ) {\displaystyle {\text{maximum speedup }}\leq {\frac {p}{1+f\cdot (p-1)}}} ここで f {\displaystyle \scriptstyle f} ( 0 < f < 1 {\displaystyle \scriptstyle 0\;<\;f\;<\;1} ) は、改良した部分の（改良以前の）所要時間の割合である。例えば（右図参照）、 B を5倍に高速化した場合 ( p = 5 {\displaystyle \scriptstyle p\;=\;5} )、 t A = 3 {\displaystyle \scriptstyle t_{A}\;=\;3} 、 t B = 1 {\displaystyle \scriptstyle t_{B}\;=\;1} 、 f = t A / ( t A + t B ) = 0.75 {\displaystyle \scriptstyle f\;=\;t_{A}/(t_{A}\,+\,t_{B})\;=\;0.75} とすると、 maximum speedup ≤ 5 1 + 0.75 ⋅ ( 5 − 1 ) = 1.25 {\displaystyle {\text{maximum speedup }}\leq {\frac {5}{1+0.75\cdot (5-1)}}=1.25} A を2倍に高速化した場合 ( p = 2 {\displaystyle \scriptstyle p\;=\;2} )、 t B = 1 {\displaystyle \scriptstyle t_{B}\;=\;1} 、 t A = 3 {\displaystyle \scriptstyle t_{A}\;=\;3} 、 f = t B / ( t A + t B ) = 0.25 {\displaystyle \scriptstyle f\;=\;t_{B}/(t_{A}\,+\,t_{B})\;=\;0.25} とすると、 maximum speedup ≤ 2 1 + 0.25 ⋅ ( 2 − 1 ) = 1.60 {\displaystyle {\text{maximum speedup }}\leq {\frac {2}{1+0.25\cdot (2-1)}}=1.60} となる。したがって、Aを2倍に高速化した方がBを5倍に高速化するよりもよい結果となる。性能向上をパーセントで表す場合、次のように計算できる。 percentage improvement = ( 1 − 1 speedup factor ) ⋅ 100 {\displaystyle {\text{percentage improvement}}=\left(1-{\frac {1}{\text{speedup factor}}}\right)\cdot 100} Aを2倍に高速化すると、プログラム全体は1.6倍に高速化し、オリジナルから37.5%の性能向上となる。 しかし、Bを5倍に高速化しても、全体としては1.25倍の高速化でしかなく、20%しか性能向上しない。
※この「逐次的プログラムの高速化」の解説は、「アムダールの法則」の解説の一部です。
「逐次的プログラムの高速化」を含む「アムダールの法則」の記事については、「アムダールの法則」の概要を参照ください。
- 逐次的プログラムの高速化のページへのリンク
