アムダールの法則

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
複数のプロセッサを使って並列計算してプログラムの高速化を図る場合、そのプログラムの逐次的部分に制限を受ける。例えばプログラムの95%を並列化できたとしても、どれだけプロセッサ数を増やしても図で示したように20倍以上には高速化しない。

アムダールの法則(アムダールのほうそく、Amdahl's law)は、システムの一部を改良したときに全体として期待できる性能向上の程度を知るための法則である。コンピュータ技術者ジーン・アムダールにちなんで名付けられた。並列計算の分野において、複数のプロセッサを使ったときの理論上の性能向上の限界を予測するのによく使われる。Amdahl's argument(アムダールの主張)という呼称もある[1]

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

詳細[編集]

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

より技術的に解説すると、この法則は、ある計算のうち高速化によって影響を受ける部分の割合 P とその性能向上率 S から、全体として達成可能な性能向上率を求めるものである。例えば、ある改良が計算全体の 30% に影響する場合、P は 0.3 である。また、その部分が2倍に高速化されるなら S は 2 である。アムダールの法則によれば、全体としての性能向上は次の式で表される。

\frac{1}{(1 - P) + \frac{P}{S}}.

従来の計算時間を 1 とする。改良されたプログラムの計算時間は、改良と関係しない部分の計算時間(1 − P)と改良された部分の計算時間(P/S)の合計となる。全体の性能向上率は、従来の計算時間を改良されたプログラムの計算時間で割ったものであり、上の式はそれを表している。

もう少し複雑な例を挙げる。あるタスクが4つの部分に分割されるとする。各部のタスク実行時間に占める割合は P1 = 0.11 (11%)、P2 = 0.18 (18%)、P3 = 0.23 (23%)、P4 = 0.48 (48%) で、全部を合計すると 100% になる。そこで、各部分に独自の改良を施す。P1 は改良しないので S1 = 1 (100%)、P2 は5倍に性能向上したので S2 = 5 (500%)、同様に S3 = 20 (2000%)、S4 = 1.6 (160%) とする。改良されたタスクの実行時間は \frac{P1}{S1} + \frac{P2}{S2} + \frac{P3}{S3} + \frac{P4}{S4} であるから、これに代入すると

{\frac{0.11}{1} + \frac{0.18}{5} + \frac{0.23}{20} + \frac{0.48}{1.6}} = .4575

となり、オリジナルの半分弱の時間ということがわかる。従って、性能向上率は \frac{1}{.4575} = 2.186 と約2倍以上になる。注意すべきは、20倍とか5倍といった改良を施しても、システム全体としてはあまり効果が出ない点である。これは、P4 が元々実行時間の約半分を占めていて、S4 が 1.6 という点と P1 が全く改良されていない点が影響している。

並列化[編集]

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

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

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

N無限大に近づく極限では、性能向上率は 1 / (1 − P) となる。実際、(1 − P) の並列化不可能な成分がどれほど小さくとも N が大きくなれば価格性能比は急激に低下していく。

例として、P が90%ならば (1 − P) は 10% となり、N をどれだけ大きくしても性能向上は1プロセッサの10倍までで頭打ちとなる。このため、並列計算が有効であるのは、プロセッサ数が少ない場合か、適応領域の問題の P の値が極めて大きい場合(embarrassingly parallel 問題と呼ぶ)に限られる。並列計算のプログラミング技法の多くは、(1 – P) を可能な限り小さくするためのものである。

特定のプロセッサ数 (NP) での実測高速化係数 (SU) すなわち1プロセッサの何倍の性能かという値を使えば、P すなわち並列化可能部分の割合は次のように推定できる。

P_\text{estimated} = \frac{\frac{1}{SU} - 1}{\frac{1}{NP} - 1}

このように推定した P をアムダールの法則の式に適用すれば、異なるプロセッサ数での高速化の度合いが推定できる。

80%の性能を出すのに必要な並列度
コア数 順次実行部分の実行時間の割合
2 25.0%
4 8.3%
6 5.0%
8 3.6%
12 2.3%
16 1.7%
32 0.8%
64 0.4%

収穫逓減の法則との関係[編集]

アムダールの法則は収穫逓減の法則と組み合わせて述べられることが多いが、アムダールの法則を適用した特殊な例のみが「収穫逓減の法則」を示す。最初から(性能向上の観点で)最適な実装をしていく場合、改良に対して得られる性能向上は単調減少していく。しかし最適でない改良なら、さらなる改良を施すことで新たな性能向上が得られる場合もある。一般にシステムの改良は困難を伴う場合や時間がかかる場合があり、必ずしも常に最善の改良を行えるわけではない。

プロセッサを追加するとそれに対応して並列化して動作するプログラムがあるとする。そのようなプログラムで解くべき問題の大きさが固定の場合に、プロセッサを追加して性能向上を図ろうとしたとき、アムダールの法則は収穫逓減の法則と同じことを表す。プロセッサを追加する度に、それによって得られる性能向上の度合いは減っていく。プロセッサを倍増させたときの性能向上比率は減少していき、最終的には \scriptstyle 1 / (1 \,-\, P) へと近づいていく。

ここでは、メモリ帯域幅やI/O帯域幅といったボトルネックの可能性を考慮していない。それらがプロセッサ数に比例して拡大しないなら、収穫逓減の傾向がさらに強まることになる。

逐次的プログラムの高速化[編集]

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

ある逐次的プログラムを改良したときの最大高速化係数は、そのプログラムの一部を p 倍に高速化した場合、次の不等式で表される。

\text{maximum speedup } \le \frac{p}{1 + f \cdot (p - 1)}

ここで \scriptstyle f (\scriptstyle 0 \;<\; f \;<\; 1) は、改良した部分の(改良以前の)所要時間の割合である。例えば(右図参照)、

  • B を5倍に高速化した場合 (\scriptstyle p \;=\; 5)、\scriptstyle t_A \;=\; 3\scriptstyle t_B \;=\; 1\scriptstyle f \;=\; t_A / (t_A \,+\, t_B) \;=\; 0.75 とすると、
    \text{maximum speedup } \le \frac{5}{1 + 0.75 \cdot (5 - 1)} = 1.25
  • A を2倍に高速化した場合 (\scriptstyle p \;=\; 2)、\scriptstyle t_B \;=\; 1\scriptstyle t_A \;=\; 3\scriptstyle f \;=\; t_B / (t_A \,+\, t_B) \;=\; 0.25 とすると、
    \text{maximum speedup } \le \frac{2}{1 + 0.25 \cdot (2 - 1)} = 1.60

となる。したがって、Aを2倍に高速化した方がBを5倍に高速化するよりもよい結果となる。性能向上をパーセントで表す場合、次のように計算できる。

\text{percentage improvement} = \left(1 - \frac{1}{\text{speedup factor}}\right) \cdot 100
  • Aを2倍に高速化すると、プログラム全体は1.6倍に高速化し、オリジナルから37.5%の性能向上となる。
  • しかし、Bを5倍に高速化しても、全体としては1.25倍の高速化でしかなく、20%しか性能向上しない。

グスタフソンの法則との関係[編集]

1988年、ジョン・グスタフソン英語版グスタフソンの法則と呼ばれることを指摘した。すなわち人々が関心を持っているのは、アムダールの法則で示されるように既に解かれた問題をより高速に解くことではなく、より大きな問題を(可能な限り正確な近似で)それなりの時間内に解くことだ、という点である。並列化できない部分が固定あるいは、問題の大きさの増大に対して非常にゆっくり増大する場合(例えば、O(log n))、解ける問題の大きさはプロセッサの追加に比例して増大していく。

脚注[編集]

  1. ^ Rodgers 1985, p. 226

参考文献[編集]

関連項目[編集]

外部リンク[編集]