Category: 法則
Type: 並列計算とシステム拡張の法則
Origin: Gene Amdahl、AFIPS Spring Joint Computer Conference（1967）
Also known as: アムダール限界；固定サイズ加速上限；強スケーリングの天井
Type: 並列計算とシステム拡張の法則
Origin: Gene Amdahl、AFIPS Spring Joint Computer Conference（1967）
Also known as: アムダール限界；固定サイズ加速上限；強スケーリングの天井
先に答えると — アムダールの法則（Amdahl’s Law）は、並列資源から得られる加速が、直列のまま残る作業部分に上限を置かれる、という法則です。固定ジョブの5%が直列なら、プロセッサが無限でも全体加速は20倍を超えません。実務では、並列を増やす前に直列ボトルネックを縮めます。
アムダールの法則とは
アムダールの法則は、問題サイズを固定したとき、システム全体の加速が並列化できない作業の割合に制限される、という規則です。高い並列処理レートを達成する努力は、ほぼ同程度の逐次処理レートの達成を伴わなければ無駄になる。Gene Amdahl の1967年の主張は率直でした。不規則性と協調オーバーヘッドのある実ワークロードでは、直列の残りがやがて支配します。現代の式では、固定ジョブの割合 p が N プロセッサで並列実行でき（1 − p は直列のまま）、N が増えると加速は N ではなく 1 / (1 − p) に近づきます。
アムダールの法則を3つの深さで理解する
- Beginner: タスクの一部だけを速くしても、全体を無限に速くはできない。
- Practitioner: まず直列割合を測る。コア・ワーカー・サーバを増やす前に、その経路を最適化する。
- Advanced: アムダールを固定作業の強スケーリング上界として扱い、利用者が容量に合わせて仕事を増やすときは Gustafson 型の弱スケーリング視点に切り替える。
起源
計算機アーキテクトの Gene Amdahl（当時 IBM）は、1967年の AFIPS Spring Joint Computer Conference で “Validity of the single processor approach to achieving large scale computing capabilities” を発表しました。短い論文に有名な方程式はありませんでしたが、不規則な実問題では逐次作業と協調オーバーヘッドが残るため、マルチプロセッサがピーク性能を出しにくいと論じました。 後の教育は、馴染みの限界式に蒸留しました。固定問題サイズでは加速 S(N) = 1 / ((1 − p) + p/N)。教室の数字は天井を鮮やかにします——p = 0.95 なら無限 N の限界は20倍、64プロセッサではおよそ15倍であり、64倍ではありません。 1988年、John Gustafson（Sandia National Laboratories での仕事）は “Reevaluating Amdahl’s Law” で議論を再構成しました。科学者はしばしばマシン規模に合わせて問題を拡大し、実行時間をほぼ一定に保ちます。1024プロセッサ系で Sandia は3つの応用について約1020–1022のスケール加速を報告しました——並列作業が N とともに増えるとほぼ線形です。これは固定ジョブのアムダールを否定せず、「同じ仕事をより短時間で」から「より大きな仕事を同程度の時間で」へ問いを変えます。要点
アムダールの法則は、加速がどこから来てどこから来ないかの予算ツールです。追加プロセッサは収穫逓減を示す
増えたコアは並列スライスだけを助けます。N が上がるとリターンは 1/(1 − p) へ縮み、固定負荷下の一種の収穫逓減です。
応用場面
「もっと並列を足せばいい」と提案され、直列割合が名指しされないときに使います。ソフトウェア性能
ホットパスをマルチスレッド化する前に、壁時計時間のうち単一スレッド I/O、GC 停止、ロック競合が占める割合を見積もる。
クラウドと容量計画
リクエストパイプラインをモデル化する。認証や共有 DB 書き込みが直列なら、その段を再設計するまで水平ポッドは頭打ちになる。
チームとプロセス設計
一人の承認者や一つの統合ゲートを直列割合として扱う。他所に人を増やしても、エンドツーエンドの周期はその上限を超えられない（ブルックスの法則は協調コストの親戚）。
学習と個人のワークフロー
読書は並列化できても、「決めて書く」ブロックは直列のまま。タブを増やしても、止まった意思決定は破れない。
事例
アムダールの固定サイズ数学と Gustafson の Sandia 結果は、法則がいつ効くかを示します。バッチジョブの95%が並列化可能だとします。アムダールの法則では、無限プロセッサでも同一ジョブの加速は20倍を超えず、64プロセッサでは約15.4倍です。これが強スケーリングの話です。同じ仕事、より短い時間への期待、直列の残りが勝つ。 1988年、Gustafson らは Sandia の1024プロセッサ・ハイパーキューブで3つの科学応用（梁の応力解析や流体系ワークロードを含む）の結果を報告しました。スケール加速はおよそ1021、1020、1022——プロセッサ数に近い——でした。研究者が問題を拡大（例：より細かい格子）し、並列作業がマシンとともに増え、直列オーバーヘッドが相対的に小さく保たれたためです。教訓は明確です。アムダールの法則は固定サイズ加速を正しく上限づけます。大規模並列マシンを科学計算から禁じる禁令として使うのは誤用です。目標に合う指標を選ぶ——同じ仕事をより速く終えるか、同程度の時間でより大きな仕事を終えるか。限界と失敗パターン
アムダールの法則は、問題が固定で、作業が直列と完全並列に理想分割できると仮定します。実システムには通信、負荷不均衡、メモリ帯域の限界があり、達成加速は式より悪くなり得ます。 画像解像度、シミュレーション精度、バッチ量など、容量とともに有用に増やせる負荷では、却下の道具として失敗します。その場合、固定サイズ加速が控えめでも弱スケーリングは大きな価値を届け得ます。 よくある誤用は、p を測らずに無限 N の天井を引用して並列投資を拒むことです。直列割合が0.5%なら天井は200倍です。そのとき法則は並列を支持し、反対しません。よくある誤解
正しい使い方には、式・スケーリング目標・近隣の法則を分ける必要があります。アムダールの法則は並列が無意味だという意味だ
アムダールの法則は並列が無意味だという意味だ
いいえ。固定作業ではリターンが直列割合に縛られる、という意味です。高い p なら十分な並列投資は正当化されます。
Gustafson の法則がアムダールを否定する
Gustafson の法則がアムダールを否定する
いいえ。固定問題サイズと拡大問題サイズという異なる問いに答えています。それぞれの領域で両立し得ます。
CPU コアにしか当てはまらない
CPU コアにしか当てはまらない
いいえ。ネットワーク集約、単一ライターのストア、人のレビューなど、並列化できない段を持つ系は同じ天井ロジックに従います。
関連概念
これらのページは、アムダールの法則をハードウェア動向・チーム拡張・リターン曲線の中に位置づけます。ムーアの法則
ハードウェア密度の動向は容量を上げるが、それ自体では直列ボトルネックを消さない。
ブルックスの法則
人を増やすと協調コストが増え得る——納期を引きずる別種の直列的負荷。
収穫逓減
制約要因が支配すると、追加投入の利得は小さくなる。
ヴィルトの法則
ソフトウェア複雑性は、チップが届けるより速くハードウェア利得を使い果たし得る。
ホフスタッターの法則
複雑な仕事は、そう予想していても予想より長くかかる。
メトカーフの法則
ネットワーク価値は接続とともに増える——物語が直列割合ではなく成長のときの対照。