アムダールの法則

コンピュータアーキテクチャにおいて、アムダールの法則（またはアムダールの議論^[1]）は、システムにリソースを追加するとタスクをどれだけ速く完了できるかを示す式です。

この法律は次のように述べられます。

「システムの単一部分を最適化することによって得られる全体的なパフォーマンスの向上は、改善された部分が実際に使用される時間の割合によって制限されます」^[2]

これはコンピュータ科学者の ジーン・アムダールにちなんで名付けられ、 1967 年にアメリカ情報処理学会連合(AFIPS) の春季合同コンピュータ会議で発表されました。

アムダールの法則は、複数のプロセッサを使用した場合の理論的な高速化を予測するために、並列コンピューティングでよく使用されます。

アムダールの法則の文脈では、スピードアップは次のように定義される。^[3]

${\displaystyle {\text{スピードアップ}}={\frac {\text{強化を適用した場合のタスク全体のパフォーマンス（または実行時間）}}{\text{強化を適用しない場合の同じタスクのパフォーマンス（実行時間）}}}}$

アムダールの法則は次のように定式化できる。^[4]

${\displaystyle {\text{スピードアップ}}_{\text{全体}}={\frac {1}{(1-{\text{時間}}_{\text{最適化}})+{\frac {{\text{時間}}_{\text{最適化}}}{{\text{スピードアップ}}_{\text{最適化}}}}}}}$

どこ

• ${\displaystyle {\text{スピードアップ}}_{\text{全体}}}$プログラム全体のスピードアップを表す
• ${\displaystyle {\text{時間}}_{\text{最適化}}}$並列処理が使用されているコードに費やされた時間を表す
• ${\displaystyle {\text{スピードアップ}}_{\text{最適化}}}$改善の程度を表す

は、予想よりもはるかに低いことがよくあります。たとえば、プログラマが合計実行時間の 10% を占めるコード部分 (つまり0.10) を拡張して10,000 の を達成した場合、 は 1.11 になり、プログラム全体の高速化は 11% しか改善されません。したがって、1 つのセクションで大幅な改善があったとしても、全体的なメリットは非常に小さいものです。別の例では、プログラマが実行時間の 99% を占めるセクション (つまり0.99) を高速化係数 100 (つまり100) で最適化した場合、 は50 にしか達しません。これは、改善されなかった残りの 1% の実行時間のために、潜在的なパフォーマンス向上の半分 (実行時間の 100% がカバーされれば 100 に達する) が失われていることを示しています。^[4]${\displaystyle {\text{スピードアップ}}_{\text{全体}}}$${\displaystyle {\text{時間}}_{\text{最適化}}}$${\displaystyle {\text{スピードアップ}}_{\text{最適化}}}$${\displaystyle {\text{スピードアップ}}_{\text{全体}}}$${\displaystyle {\text{時間}}_{\text{最適化}}}$${\displaystyle {\text{スピードアップ}}_{\text{最適化}}}$${\displaystyle {\text{スピードアップ}}_{\text{全体}}}$${\displaystyle {\text{スピードアップ}}_{\text{全体}}}$

アムダールの法則の意味は以下の通りである: ^{[5] [6]}

• タスクの並列化可能な部分と並列化不可能な部分の両方を改善する努力のバランスを取り、全体的なパフォーマンスを最大限に向上させます。
• 収穫逓減: プロセッサを追加すると、収穫逓減が発生します。ある一定のポイントを超えると、プロセッサを追加しても速度は大幅に向上しません。
• スピードアップの制限: プロセッサの数が多くても、タスクの一部が並列化できないため、タスクを完了できる速度には限界があります。

アムダールの法則の限界は以下の通りである: ^{[7] [3] [8]}

• 固定ワークロードの想定: アムダールの法則では、ワークロードは一定であると想定しています。並列処理の有効性に影響を与える可能性のある動的なワークロードや増加するワークロードは考慮されていません。
• オーバーヘッドの無視：アムダールの法則は、調整、同期、プロセス間通信、並行性制御など、並行性に関連するオーバーヘッドを無視します。特に、複数のスレッドまたはプロセスからのデータをマージすると、競合解決、データの一貫性、バージョン管理、同期のために大きなオーバーヘッドが発生します。 ^[9]
• 外的要因の無視:アムダールの法則は、データの永続性、I/O 操作、メモリ アクセスのオーバーヘッドなどの外的要因を無視して計算の並列処理を扱い、理想的な条件を想定しています。
• スケーラビリティの問題: 並列処理による高速化の限界を強調していますが、プロセッサの追加にかかるコストや複雑さなどの実用的なスケーラビリティの問題には対処していません。
• 並列化できない作業: アムダールの法則は、タスクの並列化できない部分をボトルネックとして強調しますが、この部分を削減または最適化するための解決策は提供しません。
• 同種のプロセッサを想定: すべてのプロセッサが同一であり、速度向上に等しく貢献すると想定しますが、異種コンピューティング環境ではそうならない可能性があります。

アムダールの法則は、問題のサイズが固定されている場合にのみ適用されます。実際には、より多くの計算リソースが利用可能になると、それらはより大きな問題（より大きなデータセット）に使用される傾向があり、並列化可能な部分に費やされる時間は、本質的に逐次的な作業よりもはるかに速く増加することがよくあります。この場合、グスタフソンの法則は、並列パフォーマンスについて、それほど悲観的ではなく、より現実的な評価を与えます。^[10]

ニール・J・ガンサーによって開発されたユニバーサルスケーラビリティ法則（USL）は、アムダールの法則を拡張し、プロセス間通信による追加のオーバーヘッドを考慮しています。USLは、競合や一貫性などのパラメータに基づいてスケーラビリティを定量化します。^[11]

初期の類似システムと比較してリソースが改善されたシステムによって実行されるタスクは、次の 2 つの部分に分割できます。

• システムのリソースの改善による恩恵を受けない部分。
• システムのリソースの改善によって恩恵を受ける部分。

例として、ファイルを処理するコンピュータ プログラムがあります。そのプログラムの一部は、ディスクのディレクトリをスキャンし、メモリ内にファイルのリストを作成します。その後、プログラムの別の部分は、各ファイルを別のスレッドに渡して処理します。ディレクトリをスキャンしてファイル リストを作成する部分は並列コンピュータで高速化できませんが、ファイルを処理する部分は高速化できます。

システムのリソースを改善する前のタスク全体の実行時間は と表されます。これには、リソースの改善による恩恵を受けない部分の実行時間と、恩恵を受ける部分の実行時間が含まれます。リソースの改善による恩恵を受けるタスクの実行時間の割合は と表されます。したがって、恩恵を受けない部分に関する割合は です。次に、 ${\displaystyle T}$${\displaystyle p}$${\displaystyle 1-p}$

${\displaystyle T=(1-p)T+pT.}$

リソースの改善後の係数によって加速されるのは、リソースの改善の恩恵を受ける部分の実行です。その結果、リソースの改善の恩恵を受けない部分の実行時間は変わりませんが、リソースの改善の恩恵を受ける部分の実行時間は次のように変わります。 ${\displaystyle s}$

${\displaystyle {\frac {p}{s}}T.}$

リソースの改善後のタスク全体の 理論的な実行時間は次のようになります。${\displaystyle T(s)}$

${\displaystyle T(s)=(1-p)T+{\frac {p}{s}}T.}$

アムダールの法則は、固定された作業負荷でのタスク全体の実行のレイテンシの理論的な高速化を示し、 ${\displaystyle W}$

${\displaystyle S_{\text{latency}}(s)={\frac {TW}{T(s)W}}={\frac {T}{T(s)}}={\frac {1}{1-p+{\frac {p}{s}}}}.}$

実行時間の 30% が高速化の対象になる場合、p は0.3 になります。改善によって影響を受ける部分が 2 倍高速化する場合、s は2 になります。アムダールの法則によれば、改善を適用した場合の全体的な高速化は次のようになります。

${\displaystyle S_{\text{latency}}={\frac {1}{1-p+{\frac {p}{s}}}}={\frac {1}{1-0.3+{\frac {0.3}{2}}}}=1.18.}$

たとえば、連続タスクが 4 つの連続する部分に分割され、実行時間の割合がそれぞれp 1 = 0.11、p 2 = 0.18、p 3 = 0.23、p 4 = 0.48であるとします。この場合、最初の部分は高速化されないためs 1 = 1、2 番目の部分は 5 倍高速化されるためs 2 = 5、3 番目の部分は 20 倍高速化されるためs 3 = 20、4 番目の部分は 1.6 倍高速化されるためs 4 = 1.6 となります。アムダールの法則を使用すると、全体的な高速化は次のようになります。

${\displaystyle S_{\text{latency}}={\frac {1}{{\frac {p1}{s1}}+{\frac {p2}{s2}}+{\frac {p3}{s3}}+{\frac {p4}{s4}}}}={\frac {1}{{\frac {0.11}{1}}+{\frac {0.18}{5}}+{\frac {0.23}{20}}+{\frac {0.48}{1.6}}}}=2.19.}$

2 番目と 3 番目の部分でそれぞれ 5 倍と 20 倍の高速化が全体の高速化にほとんど影響を及ぼさず、4 番目の部分 (実行時間の 48%) がわずか 1.6 倍しか高速化されていないことに注目してください。

例えば、T _A = 3秒、T _B = 1秒の2つの部分AとBからなるシリアルプログラムの場合、

• 部品Bを5倍速く実行する場合、つまりs = 5、p = T _B /( T _A + T _B ) = 0.25の場合、$${\displaystyle S_{\text{latency}}={\frac {1}{1-0.25+{\frac {0.25}{5}}}}=1.25;}$$
• 部品Aを2倍速く実行する場合、つまりs = 2、p = T _A /( T _A + T _B ) = 0.75の場合、$${\displaystyle S_{\text{latency}}={\frac {1}{1-0.75+{\frac {0.75}{2}}}}=1.60.}$$

したがって、部品Aを2倍速く実行することは、部品Bを5倍速く実行することよりも優れています。速度の向上率は次のように計算できます。

${\displaystyle {\text{percentage improvement}}=100\left(1-{\frac {1}{S_{\text{latency}}}}\right).}$

• 部分A を2 倍に改善すると、プログラム全体の速度が 1.60 倍になり、元の計算よりも 37.5% 高速になります。
• ただし、おそらくより多くの労力を必要とする部分B を5 倍に改善しても、全体的な速度向上率は 1.25 倍にしかならず、速度は 20% しか上がりません。

並列化不可能な部分が 倍に最適化されると、 ${\displaystyle O}$

${\displaystyle T(O,s)=(1-p){\frac {T}{O}}+{\frac {p}{s}}T.}$

アムダールの法則によれば、並列処理による高速化は次のように表される。

${\displaystyle S_{\text{latency}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac {1}{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}.}$

のとき、 となり、並列化不可能な部分が最適化された後の実行時間に対して高速化が測定されることを意味します。 ${\displaystyle s=1}$${\displaystyle S_{\text{latency}}(O,s)=1}$

いつ 、 ${\displaystyle s=\infty }$

${\displaystyle S_{\text{latency}}(O,\infty )={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac {1}{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}=1+{\frac {p}{1-p}}O.}$

、かつの場合 、次のようになります。 ${\displaystyle 1-p=0.4}$${\displaystyle O=2}$${\displaystyle s=5}$

${\displaystyle S_{\text{latency}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {{0.4}{\frac {1}{2}}+0.6}{{\frac {0.4}{2}}+{\frac {0.6}{5}}}}=2.5.}$

次に、並列化不可能な部分が 倍に減少し、並列化可能な部分がそれに応じて増加する場合を考える。 ${\displaystyle O'}$

${\displaystyle T'(O',s)={\frac {1-p}{O'}}T+\left(1-{\frac {1-p}{O'}}\right){\frac {T}{s}}.}$

アムダールの法則によれば、並列処理による高速化は次のように表される。

${\displaystyle S'_{\text{latency}}(O',s)={\frac {T'(O')}{T'(O',s)}}={\frac {1}{{\frac {1-p}{O'}}+\left(1-{\frac {1-p}{O'}}\right){\frac {1}{s}}}}.}$

アムダールの法則は、収穫逓減の法則と混同されることが多いですが、収穫逓減の法則が実証されるのは、アムダールの法則を適用した特殊なケースのみです。改善対象を最適に選択すると (達成されるスピードアップの観点から)、改善するにつれて改善が単調に減少します。ただし、最適でないコンポーネントを改善してから、より最適なコンポーネントの改善に進むという非最適な選択をすると、収益の増加が見られます。一部の改善が他の改善よりも困難であったり、開発に長い時間を要する場合、この意味で「非最適」な順序でシステムを改善することが合理的であることが多いことに注意してください。

マシンにプロセッサを追加することでどのような利益が得られるかを考えるとき、つまり、利用可能なすべてのプロセッサをその能力まで使用する固定サイズの計算を実行する場合、アムダールの法則は収穫逓減の法則を表します。システムに新しいプロセッサを追加するたびに、以前のプロセッサよりも使用可能な電力が少なくなります。プロセッサの数を 2 倍にするたびに、合計スループットが 1/(1 −  p ) の限界に近づくため、スピードアップ率は減少します。

この分析では、メモリ帯域幅や I/O 帯域幅などの他の潜在的なボトルネックは考慮されません。これらのリソースがプロセッサの数に応じて拡張されない場合、プロセッサを追加するだけでは、さらに低いリターンしか得られません。

アムダールの法則から、シリアル部分と並列部分の両方を持つ実際のアプリケーションを高速化するには、異種コンピューティング技術が必要であることが示唆されます。^[12]異種性のより一般的な表現（正規形異種性と呼ばれる）に基づく新しい高速化およびエネルギー消費モデルがあり、さまざまな異種マルチコアアーキテクチャをサポートしています。これらのモデリング方法は、システムの電力効率とパフォーマンスの範囲を予測することを目的としており、ハードウェアおよびシステムソフトウェアレベルでの研究開発を促進します。^{[13] [14]}

• グスタフソンの法則
• 計算スケーラビリティの普遍法則
• 並列アルゴリズムの分析
• クリティカルパス法
• ムーアの法則

• Amdahl, Gene M. (1967)。「大規模コンピューティング機能を実現するためのシングルプロセッサアプローチの有効性」(PDF)。AFIPSカンファレンス プロシーディングス(30): 483–485。doi :10.1145/1465482.1465560。S2CID  195607370。

ウィキメディア・コモンズには、アムダールの法則に関連するメディアがあります。

• ジーン・M・アムダール（1989）、ジーン・M・アムダールとの口述歴史インタビュー、ミネソタ大学チャールズ・バベッジ研究所、hdl：11299/104341アムダールはウィスコンシン大学での大学院時代の研究とWISCの設計について語ります。STRETCH、IBM 701、IBM 704など、IBM の複数のコンピュータの設計における役割について語ります。ナサニエル ロチェスターとの仕事と IBM の設計プロセス管理について語ります。ラモ ウッドリッジ、エアロニュートロニック、およびコンピュータ サイエンス コーポレーションとの仕事について言及します。
• 「アムダールの法則」ジョエル・F・クライン著、Wolfram Demonstrations Project (2007)
• マルチコア時代のアムダールの法則 (2008 年 7 月)