アムダールの法則

提供: フリー百科事典『ウィキペディア（Wikipedia）』

アムダールの法則（アムダールのほうそく、Amdahl's law）は、システムの一部を改良したときに全体として期待できる性能向上の程度を知るための法則である。コンピュータ技術者ジーン・アムダールにより提唱された。並列コンピューティングの分野でよく使われ、複数のプロセッサを使ったときの理論上の性能向上の度合いを予測する。

[編集] 詳細

アムダールの法則を最も簡単に説明すると、「性能向上率を決定するのはプロセッサ数ではなくアルゴリズムである」ということになる。アルゴリズムは、これ以上並列化できないという地点に最終的に到達する。

アムダールの法則は収穫逓減の法則の実例でもある。あるコンピュータが処理の一部を100倍やそれ以上に高速化できたとしても、それによって影響を受ける部分が与えられたタスクの実行時間の12%でしかないとしたら、全体としては最大でも $\frac{1}{1 - 0.12} = 1.136$ 倍の性能にしかならない。

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

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

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

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

もう少し複雑な例を挙げる。あるタスクが4つの部分に分割されるとする。各部のタスク実行時間に占める割合は P1 = .11 (11%)、P2 = .18 (18%)、P3 = .23 (23%)、P4 = .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{.11}{1} + \frac{.18}{5} + \frac{.23}{20} + \frac{.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 を極限まで大きくした場合）。

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

$\frac{1}{F + (1-F)/N}$ .

N が無限大に近づく極限では、性能向上率は 1/F となる。実際、(1 − F)/N が Fに比べて十分に小さくなると、Nを増やしても性能が向上しなくなる（価格性能比が悪くなる）。

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

一般に、デスクトップ・コンピューティングはアムダールの法則のためにマルチプロセッシングが役に立たないと言われ、マルチコア化されたマイクロプロセッサの導入も疑問視されていたが、インテルは将来的にデスクトップのアプリケーションの並列化が進むとしてマルチコアの導入に積極的である。

[編集] アムダールの経験則

アムダールの経験則とは、コンピュータが一秒当たりに実行する命令数を X とすると、少なくとも X バイトのメモリと X バイト毎秒の入出力性能を必要とする、というものである。

[編集] 関連項目

[編集] 外部リンク

いずれも英文