アムダールの法則とグスタフソンの法則
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/07/25 13:20 UTC 版)
「並列計算」の記事における「アムダールの法則とグスタフソンの法則」の解説
並列計算のプラットフォームにおけるアルゴリズムの性能は、そのアルゴリズムをどれだけ並列化できるかに依存する。そのため、1960年代にジーン・アムダールが定式化したアムダールの法則が重要となってくる。それによると、プログラムの中の並列化できない部分が並列化による性能向上を制限する。大規模な工学的問題や数学問題には、一般に並列化可能な部分と並列化不可能な部分(逐次実行部分)がある。アムダールの法則によれば、以下のような関係が成り立つ。 S = 1 ( 1 − P ) {\displaystyle S={\frac {1}{(1-P)}}} ここで、Sはプログラムの性能向上率(逐次実行版での実行時間を1としたときの倍率)、Pは並列化可能な部分の比率である。逐次実行部分がプログラムの実行時間の10%を占めている場合、性能向上は10倍となり、それ以上の多くの計算ノードを追加しても意味はない。これにより、並列実行ユニットを追加して意味のある個数の上限が得られる。 グスタフソンの法則は、アムダールの法則とも密接に関連する計算機工学における法則である。グスタフソンの法則は以下の式で表される。 S ( P ) = P − α ( P − 1 ) {\displaystyle \displaystyle S(P)=P-\alpha (P-1)} ここで、Pはプロセッサ数、Sは性能向上、 α {\displaystyle \alpha } は処理の並列化できない部分である。アムダールの法則では問題のサイズが固定であり、逐次実行部分はプロセッサ数に依存しないと仮定されている。一方、グスタフソンの法則ではそのような仮定がない。
※この「アムダールの法則とグスタフソンの法則」の解説は、「並列計算」の解説の一部です。
「アムダールの法則とグスタフソンの法則」を含む「並列計算」の記事については、「並列計算」の概要を参照ください。
- アムダールの法則とグスタフソンの法則のページへのリンク