アムダールの法則とは？

アムダールの法則の意味

処理の一部しか高速化・並列化できない場合、全体の性能向上には上限があることを示す法則。並列化できない割合をsとすると、プロセッサをいくら増やしても速度向上比は1/sを超えられない。投資判断の根拠になる。

アムダールの法則の具体例

全処理の20%が逐次処理なら、CPUを無限に増やしても最大5倍にしかならない。8CPUでの速度向上比は1/(0.2＋0.8/8)＝約3.3倍。台数を倍にしても効果が頭打ちになる理由がこの式で説明できる。

アムダールの法則は試験でどう引っ掛けられる？

分母は「逐次部分＋並列部分÷台数」。逐次部分を割ってしまう誤りが多い。またこの法則は問題規模を固定した場合の話で、規模も一緒に大きくする場合はグスタフソンの法則で評価する。

アムダールの法則と関連する用語

• 疎結合マルチプロセッサと密結合マルチプロセッサ
• スーパースカラとマルチコア
• ベンチマークとキャパシティプランニング

アムダールの法則が出た過去問

• プロセッサ数と、計算処理におけるプロセスの並列化が可能な部分の割合とが、性能向上へ及ぼす影響に関する記述のうち、アムダールの法則に基づいたものはどれか。

  正解：並列化できない計算処理がある場合、速度向上比は、プロセッサ数を増やしてもある水準に漸近的に近づく。

  要点：アムダールの法則は逐次部分が速度向上の上限を決める

  アムダールの法則は、処理全体のうち並列化できない部分が残る限り、プロセッサ数をいくら増やしても速度向上比はその逐次部分が決める上限に頭打ちになる、という関係を示す。例えば逐次部分が全体の1割あれば、理論上の速度向上は10倍までしか伸びない。プロセッサ数を増やす投資の効果を見積もる際の基本となる法則である。

  出典：令和4年度 春期 応用情報技術者試験 午前 問12（IPA）

• 1台のCPUの性能を1とするとき、そのCPUをn台用いたマルチプロセッサの性能Pが、 P = n / (1+(n-1)a) で表されるとする。ここで、aはオーバ…

  正解：10

  要点：オーバーヘッドaがあると並列性能の上限は1/aで頭打ちになる

  P = n/(1+(n-1)a) の分母を展開すると 1-a+an となり、nを無限大にすると分子分母のnの項が支配的になってPは1/aに近づく。a=0.1なので上限は1/0.1＝10である。これはアムダールの法則が示す、並列化できない部分が全体の性能向上を頭打ちにする現象を表している。

  出典：令和6年度 春期 応用情報技術者試験 午前 問14（IPA）

• マルチプロセッサによる並列処理で得られる高速化率（単一プロセッサのときと比べた倍率）Eを，次の式によって評価する。r=0.9のアプリケーションの高速化率がr=0…

  正解：6

  要点：アムダールの法則E=1/(1-r+r/n)に代入して連立を解く

  アムダールの法則の式にr=0.9とr=0.3を代入すると、高速化率はそれぞれ1/(0.1+0.9/n)と1/(0.7+0.3/n)になる。前者が後者の3倍という条件は、0.7+0.3/n＝3×(0.1+0.9/n)と書ける。展開すると0.7+0.3/n＝0.3+2.7/nとなり、0.4＝2.4/nからn＝6台と求まる。

  出典：令和7年度 春期 応用情報技術者試験 午前 問11（IPA）