アムダールの法則

ウィキペディア

アムダールの法則

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/27 01:44 UTC 版)

複数のプロセッサを使って並列計算してプログラムの高速化を図る場合、そのプログラムの逐次的部分は、制限を受ける。例えば、仮にプログラムの95%を並列化できたとしても、残りの部分である5%は並列処理ができないため、どれだけプロセッサ数を増やしたとしても、図で示したように20倍以上には高速化しない。

アムダールの法則（アムダールのほうそく、英語: Amdahl's law）は、ある計算機システムとその対象とする計算についてのモデルにおいて、その計算機の並列度を上げた場合に、並列化できない部分の存在、特にその割合が「ボトルネック」となることを示した法則である。コンピュータ・アーキテクトのジーン・アムダールが主張したものであり、アムダールの主張（アムダールのしゅちょう、英語: Amdahl's argument）という呼称もある。

複数のプロセッサを使い並列計算によってプログラムの高速化を図る場合、そのプログラムの中で逐次的に実行しなければならない部分の時間によって、高速化が制限される。例えば、1プロセッサでは20時間かかる問題があり、そのプログラムのうち、合計で1時間分が並列処理できないとする。この場合、19時間分（95%）は並列処理できるが、どれだけプロセッサを追加したとしても、最小実行時間は並列処理できない部分にかかる1時間（5%）より短くならない。

詳細

アムダールの法則は、並列化しても問題の大きさが変化しないという前提と、問題には並列化できない部分があるという前提の上で、逐次的アルゴリズムとそれに対応したアルゴリズムの並列化実装によって期待できる高速化の関係をモデル化したものである。例えば、ある大きさの問題をあるアルゴリズムを並列化実装したもので実行した場合、問題の12%を並列化によって好きなように高速化できるとする（残り88%は並列化できない処理である）。アムダールの法則によれば、このときの並列化していない実装と比較した並列化版による高速化は最大でも ${\frac {1}{1-0.12}}=1.136$

並列コンピューティングで複数のプロセッサを使って性能向上を図る場合、対象プログラムの並列化できない部分の割合に大きく左右される。例えば、プログラムの半分(0.5)が並列実行できない場合、理論上の性能向上限界は 2 となる（1/(0.5+(1-0.5)/N) で N を極限まで大きくした場合）。

プログラムの並列化できる部分の実行時間の割合を P としたとき、並列化不可能な部分は (1 − P)であり、N個のプロセッサを使ったときの全体の性能向上率は次の式で表される。

${\displaystyle S(N)={\frac {1}{(1-P)+{\frac {P}{N}}}}}$

タスクが独立した二つの部分 A と B から構成されている。B は計算時間の約25%を占めている。がんばって B を改良して5倍の性能にしても、全体としての性能向上は少しでしかない。逆に A を2倍の性能に改良した方が全体性能はより向上する。