# Reevaluating Amdahl's law > [!abstract] 概要 > 著者の所属する Sandia 国立研究所は、超並列処理の研究を進めている。 > 超並列処理の実現可能性には強い懐疑論があり、その中心は Gene Amdahl が 1967 年に提示した議論である。 > 直列に実行される仕事の割合 s が小さくても、無限個の並列プロセッサで得られる最大速度向上は 1/s にとどまる、という議論である。 > 1024 プロセッサ システムの実測結果により、アムダールの 1967 年の議論の前提は、現在の超並列アンサンブル並列のやり方には不適切であることが示された。 ## 論文情報 - 著者: John L. Gustafson(Sandia National Laboratories) - 媒体: Communications of the ACM, Vol. 31, No. 5, pp. 532-533(1988 年 5 月)。Technical Note - 参照する実測の詳細: Benner, Gustafson, Montry, SAND 88-0317(Sandia, 1988 年 2 月) - 原本: [[.raw/papers/Reevaluating-Amdahls-law.pdf]] ## 概要 アムダールの法則は問題規模を固定した速度向上の上限を与えるが、実際の科学計算では問題規模が台数に合わせて拡大する。実行時間を一定とみなして逐次部分と並列部分を測り直すと、速度向上は N + (1 - N)×s という緩やかな直線になり、1024 プロセッサで 1000 倍超が実測された。本論文は後に[[グスタフソンの法則]](拡大速度向上)と呼ばれる考え方の出発点である。 ## 問題設定 当時、超並列処理には強い懐疑があり、その根拠はアムダールの法則であった。N をプロセッサ数、s を逐次機で逐次部分に費やす時間、p を逐次機で並列化可能部分に費やす時間とし、s + p = 1 と正規化すると、速度向上は次式になる。 Speedup = (s + p)/(s + p/N) = 1/(s + p/N) N = 1024 のとき、この関数は s = 0 付近で非常に急峻である(傾きはおよそ -N²)。したがって 100 倍の速度向上が得られる問題はごく少数だと結論される。 ![[Reevaluating-Amdahls-law/fig01-amdahl-speedup.png]] Figure 1 は N = 1024 での逐次割合と速度向上の関係を示す。図中には曲線に沿って 288 倍、167 倍、91 倍、63 倍、48 倍、31 倍、24 倍の値が注記され、横軸の目盛では 2% で 48 倍、3% で 31 倍、4% で 24 倍に対応する。s が数 % あるだけで曲線は 1 に貼り付く。 一方、Sandia の実用 3 アプリケーション(s = 0.4〜0.8%)では、1024 プロセッサのハイパーキューブで前例がないと著者が考える速度向上を得た。梁の応力解析(共役勾配法)が 1021 倍、バッフル付き表面波のシミュレーション(陽的有限差分)が 1020 倍、流束補正輸送法による不安定流体流れが 1016 倍である。アムダールの議論がこれと合わない理由が問いである。 ## 提案手法 著者は式と図に共通する暗黙の仮定、すなわち p が N と独立であるという仮定を批判する。固定規模の問題を様々な台数で動かすのは学術研究の場面に限られる。実際には問題規模は台数に合わせて拡大する。より強力なプロセッサが与えられれば問題はそれを使い切るまで大きくなる。格子解像度、時間ステップ数、差分演算子の複雑さなどは利用者が制御でき、望みの実行時間に収まるよう調整される。したがって、問題規模ではなく実行時間を一定と仮定するほうが現実に近い。 第一近似として、プログラムのうち並列またはベクトル化される部分が問題規模とともに拡大する。ベクトル起動、プログラムのロード、逐次のボトルネック、入出力といった s を構成する時間は、問題規模に比例して伸びない。自由度を 2 倍にすればプロセッサも 2 倍にするので、並列に処理できる仕事量はプロセッサ数にほぼ線形に比例する。3 アプリケーションで並列部分の拡大倍率を測ると 1023.9969、1023.9965、1023.9965 であった(N = 1024)。 s と p を並列システム上で費やした逐次時間・並列時間とすると、逐次機が同じ仕事に要する時間は s + p×N である。E. Barsis(Sandia)の示唆によるアムダールの法則の代替は次式である。 Scaled speedup = (s + p×N)/(s + p) = s + p×N = N + (1 - N)×s これは傾き 1 - N の単なる直線であり、図 1 の急峻な曲線に比べて傾きがはるかに緩い。したがって効率的な並列性能はアムダールの枠組みが示唆するより達成しやすい。 ![[Reevaluating-Amdahls-law/fig02a-fixed-size-model.png]] Figure 2a は固定規模モデルである。逐次機での所要時間 1 = s + p に対し、並列機では s + p/N になる。 ![[Reevaluating-Amdahls-law/fig02b-scaled-size-model.png]] Figure 2b は拡大規模モデルである。並列機での所要時間を 1(= s + p)に固定し、同じ仕事を逐次機で仮想的に行うと s + N×p かかる。 ## 新規性 - 速度向上の議論の基準を「問題規模一定」から「実行時間一定」へ置き換え、逐次割合 s を並列機上の実測時間の割合として定義し直した点。 - 並列部分が問題規模とともに伸びるという観察を、実測(拡大倍率 1023.9965 前後)で裏づけた点。 - 実測の裏づけとして、当時前例のない 1000 倍級の速度向上を 3 種の実用計算で示した点。 ## 実験設定 - 環境: Sandia の 1024 プロセッサ ハイパーキューブ。 - 対象: 梁の応力解析(共役勾配法)、バッフル付き表面波シミュレーション(陽的有限差分)、不安定流体流れ(流束補正輸送法)の 3 アプリケーション。 - 逐次割合: s = 0.4〜0.8%。 - 詳細は SAND 88-0317 に譲られ、本論文には実験手順の記述はない。 ## 実験結果 | アプリケーション | 速度向上(1024 プロセッサ) | 並列部分の拡大倍率 | |---|---|---| | 梁の応力解析(共役勾配法) | 1021 | 1023.9969 | | バッフル付き表面波(陽的有限差分) | 1020 | 1023.9965 | | 不安定流体流れ(流束補正輸送法) | 1016 | 1023.9965 | 本文は 3 つの速度向上と 3 つの拡大倍率の対応順を明記していない。上表は本文に現れる順序で並べたものであり、行ごとの対応は本文からは断定できない。速度向上は、拡大した問題を逐次機で走らせた場合の時間を基準にする量である(図 2b の仮想的な逐次実行)。 ## 考察 - 著者は、超並列処理に対する研究コミュニティの「心理的障壁」がアムダールの式の誤用に由来すると主張する。速度向上は、問題規模を台数に合わせて拡大して測るべきで、規模を固定して測るべきではない。 - 今後、より広い範囲のアプリケーションと、さらに大きな N へ成功を拡張する見込みを述べる。 - 位置づけ: 固定規模の上限(アムダール)と拡大規模の直線(本論文)は、同じ s と p を異なる基準で見た 2 つの量である。後者は[[強スケーリングと弱スケーリング]]における弱スケーリングの速度向上指標に対応する。[[アムダールの法則]]の原論文は [[@1967__AFIPS SJCC__Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities]] である。 ## 強み / 弱点・課題 - 強み: 1 ページ強の式と 2 枚の図で前提の違いを示し、実測値で反証している。s を並列機上の実測時間で定義するため、計測と直結する。 - 弱点・課題: 問題規模を拡大する前提がメモリ容量や通信量の増加を無視している点は、本文では検討されない。s を規模に対して一定とする第一近似も、入出力や大域通信が規模とともに伸びる場合には成り立たない。上記の実測値の内訳は SAND 88-0317 に依存し、本論文だけでは再現できない。