並列処理の性能法則(アムダールの法則・グスタフソンの法則)
1. 概要
A. 定義
アムダールの法則(Amdahl's Law) は、作業の全体規模を固定したままプロセッサ数を増やすとき、得られる性能向上(speedup)が 直列でしか実行できない部分の割合によって上限が決まる とする法則であり、グスタフソンの法則(Gustafson's Law, Gustafson–Barsis) は、プロセッサが増えれば 処理する問題の規模も一緒に拡大する と仮定したとき、性能向上がプロセッサ数にほぼ比例して拡張しうることを示す法則である。両法則は同じ並列システムを、それぞれ「固定された仕事をどれだけ速く終えるか(strong scaling)」と「同じ時間でどれだけ多くの仕事をするか(weak scaling)」の観点から説明する。
並列処理の核心的な問いは単純である。「プロセッサ(コア)をN倍に増やせば性能もN倍になるのか」。直感的にはそうなるべきに思えるが、現実は異なる。どんなプログラムにも、順序を守って一つずつ処理するしかない 直列区間(serial section) — 初期化、入出力、クリティカルセクション、結果のマージなど — が存在し、この区間はプロセッサをいくら増やしても速くならない。アムダールの法則はまさにこの直列区間が全体の性能向上の「天井」を作ることを、グスタフソンの法則は問題規模を拡大すればその天井を事実上押し上げられることを、定量的に示す。
この二つの法則は互いに矛盾するものではなく、仮定が異なる相互補完的なモデル である。アムダールは「仕事の量を固定」し、グスタフソンは「時間を固定(仕事の量を拡張)」する。どちらが正しいかではなく、自分のワークロードがどのシナリオに該当するかを見極めることが並列設計の出発点である。技術士の観点では、これらの法則はマルチコアCPU、GPUアクセラレーション、大規模分散学習、ビッグデータ処理の投資対効果(ROI)と拡張限界を予測する 容量見積もり・アーキテクチャ意思決定の基本ツール として用いられる。
B. 登場背景と必要性
アムダールの法則は1967年、Gene Amdahlが単一高速プロセッサと多数の低速プロセッサの経済性を比較する文脈で提示した。当時は並列計算機の有用性に対する楽観論が広まっていたが、Amdahlは「プログラムの相当部分が本質的に直列であるなら、並列化の利得は限定的だ」という冷静な上限を示し、並列化投資に対する現実的な基準を打ち立てた。その後、ムーアの法則が限界に突き当たり、クロック速度の向上ではなく コア数の増加(マルチコア) で性能を引き上げる時代が到来すると、アムダールの法則は「コアを増やしてもなぜ期待どおり速くならないのか」を説明する中核的ツールとして再評価された。
一方、1988年にJohn Gustafsonは、サンディア国立研究所の1024プロセッサのハイパーキューブで実際の科学計算を並列化する中で、アムダールの悲観的予測とは異なる現象を観察した。プロセッサを増やすとき、人々は同じ問題をより速く解くよりも、より大きな問題(より細かい格子、より長いシミュレーション) を同じ時間内に解く形で資源を活用するというものだった。すなわち直列割合は問題規模が大きくなるほど相対的に小さくなるため、実際のHPCではプロセッサ数にほぼ比例する拡張が観測された。この洞察が大規模並列スーパーコンピューティングの妥当性を裏づけた。今日、数千枚のGPUで巨大言語モデル(LLM)を学習したり、数万コアで気象・流体シミュレーションを回したりできるのはグスタフソン的拡張が成立するためであり、逆に応答時間が重要なオンラインサービスの単一リクエスト処理にはアムダール的限界がそのまま適用される。
2. アムダールの法則 — 固定作業量(Strong Scaling)
アムダールの法則は「全体の仕事量を固定」する。プログラム実行時間を並列化可能割合 p(0≤p≤1)と直列割合 1-p に分けると、プロセッサN個を投入したときの性能向上は次のとおりである。
Speedup(N) = 1 / ( (1 − p) + p/N )、そして N → ∞ ならば 最大性能向上 = 1 / (1 − p)
下の構造図は、全体作業が直列区間と並列区間に分解され、並列区間のみがN個の処理機に分散されるアムダールモデルの全体構造を示す。直列区間は分散されずそのまま残り、全体時間の下限を作る。
flowchart TB
JOB["固定された全体作業<br/>(実行時間 1)"]
JOB --> SER["直列区間 (1−p)<br/>プロセッサを増やしても不変"]
JOB --> PAR["並列区間 p<br/>N個に分割可能"]
PAR --> P0["処理機 0<br/>(p/N)"]
PAR --> P1["処理機 1<br/>(p/N)"]
PAR --> Pn["処理機 N−1<br/>(p/N)"]
SER --> OUT["総実行時間<br/>(1−p) + p/N"]
P0 --> OUT
P1 --> OUT
Pn --> OUT
style SER fill:#fce8e6,stroke:#d93025,stroke-width:2px
style PAR fill:#e6f4ea,stroke:#188038,stroke-width:2px
style OUT fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
A. 直列区間が作る天井
アムダールの法則が伝える最も強力なメッセージは、「並列化不可能な部分がわずかにあるだけで全体の拡張性が急激に制限される」という点である。たとえば全体の95%を完全に並列化しても(p=0.95)、直列5%が残れば、プロセッサを無限に増やしても最大性能向上は 1/(1−0.95)=20倍 に縛られる。プロセッサが20個を超えると追加投入はほとんど効果がなく、1,000個入れても約19.6倍にとどまる。これは「直列5%」という小さな値が全体拡張の運命を決定することを意味する。
B. 数値で見る収穫逓減
具体的に p=0.90の作業を見よう。N=2なら 1/(0.1+0.45)=約1.82倍、N=4なら 1/(0.1+0.225)=約3.08倍、N=8なら約4.71倍、N=16なら約6.40倍、N=∞なら10倍が上限である。プロセッサを2倍ずつ増やしても性能向上の幅は次第に小さくなる 収穫逓減(diminishing returns) が顕著である。下の表は直列割合に応じた理論上限を整理したものである。
| 並列化割合 p | 直列割合 1−p | 最大性能向上(N→∞) | N=16のとき |
|---|---|---|---|
| 0.50 | 0.50 | 2倍 | 約1.88倍 |
| 0.90 | 0.10 | 10倍 | 約6.40倍 |
| 0.95 | 0.05 | 20倍 | 約9.14倍 |
| 0.99 | 0.01 | 100倍 | 約13.9倍 |
C. 実務的含意
アムダールの法則は「並列化を増やすよりも直列区間を減らすほうが重要でありうる」という最適化の優先順位を教える。データベーストランザクションのコミット直列化、ロック競合、グローバルカウンタ、単一ログファイルへの逐次書き込みなどは典型的な直列ボトルネックであり、これらをシャーディング・ロックフリーデータ構造・バッチ処理で減らさなければコア増設は金の無駄になる。実際、あるOLTPシステムでCPUを8コアから32コアへ4倍に増やしたが処理量が1.6倍にとどまった事例があり、これはコネクションプールとコミット経路の直列区間が p≈0.8水準だったため、N=32の理論上限(約4.7倍)にも届かなかった典型的なアムダール現象であった。
同じ観点はソフトウェアプロファイリングにも直接適用される。アムダールの法則は「全体で大きな比重を占める部分を先に最適化せよ」という原則の数学的根拠でもある。全体実行時間の5%を占める関数を10倍速くしても全体は約4.5%しか減らないが、60%を占める関数を2倍にするだけで全体が30%減る。並列化であれアルゴリズム改善であれ、投資効果は常に「改善対象が全体で占める比重」によって制限されるというのがアムダールの普遍的教訓である。
3. グスタフソンの法則 — 固定時間(Weak Scaling)
グスタフソンの法則は観点を反転させる。「時間を固定」し、プロセッサがN倍なら処理する問題規模も拡大すると見る。並列実行時間を基準に直列割合を s、並列割合を 1−s とするとき、scaled speedup は次のとおりである。
Speedup(N) = s + (1 − s)·N = N − s·(N − 1)
ここで s は「並列実行基準」の直列割合であるという点がアムダールと異なる。下の図は、プロセッサを増やすときアムダール(作業量固定→時間短縮)とグスタフソン(時間固定→作業量拡張)が資源を使う方式がどう分かれるかをプロセスの観点から比較する。
flowchart LR
START["プロセッサをN倍に増設"] --> Q{"何を固定するか?"}
Q -->|"作業量固定"| A1["Amdahl: 同じ仕事を<br/>より速く"]
A1 --> A2["直列区間の比重が増加<br/>→ 性能向上が飽和"]
A2 --> A3["上限 1/(1−p)"]
Q -->|"時間固定"| G1["Gustafson: 同じ時間に<br/>より大きな仕事"]
G1 --> G2["問題拡大で並列区間の<br/>相対比重が増加"]
G2 --> G3["性能向上 ≈ N に<br/>ほぼ線形に拡張"]
style A3 fill:#fce8e6,stroke:#d93025,stroke-width:2px
style G3 fill:#e6f4ea,stroke:#188038,stroke-width:2px
A. 直列割合が相対的に小さくなる原理
科学計算では、直列作業(初期化・入出力)の絶対時間は問題規模が大きくなってもほぼ一定である一方、並列作業(格子計算・行列演算)の量は問題規模に比例して激増する。したがって問題を拡大するほど全体に占める直列の 割合 は小さくなり、アムダールが仮定した「固定された直列割合」はもはや維持されない。たとえば格子解像度を2倍に高めると計算量は数倍に増えるがファイルを開く時間はそのままなので、直列割合が10%から2%へ下がるといった具合である。これが1,024プロセッサでも線形に近い拡張が観測された理由である。
B. 数値で見る線形拡張
s=0.05(並列基準で直列5%)のとき、グスタフソンの性能向上はN=16なら 0.05+0.95×16=約15.25倍、N=1,024なら約972.9倍に達する。同じ直列5%でもアムダールが最大20倍に縛られるのと極めて対照的である。核心は「何を測るか」である。アムダールは 同一問題の応答時間短縮 を、グスタフソンは 同一時間内の処理規模(throughput・問題規模) を測る。
C. 適用領域
グスタフソン的拡張が成立する代表的事例は、HPCシミュレーション(気象・流体・構造解析)、大規模ディープラーニング学習(バッチ・データ並列)、モンテカルロシミュレーションのように「資源が増えればより精密・大規模に解きたい」問題である。逆に単一ユーザーリクエストの応答時間、固定サイズバッチの締め切りのように「仕事の量が固定」された問題にはアムダール的限界がそのまま適用される。したがって設計者は「我々のワークロードはより速く(strong)を望むのか、より多く(weak)を望むのか」をまず定義しなければならない。
4. 二つの法則の比較
二つの法則の違いは「誤りと正しさ」ではなく、問題設定の違い に由来する。アムダールは固定作業量(strong scaling)、グスタフソンは拡張作業量(weak scaling)を前提とし、それぞれが狙う現実問題とそこから出てくる実務的結論が異なる。
| 区分 | アムダールの法則 | グスタフソンの法則 |
|---|---|---|
| 固定対象 | 作業量(問題規模) | 実行時間 |
| スケーリング種別 | Strong scaling | Weak scaling |
| 性能向上式 | 1/((1−p)+p/N) | s+(1−s)·N |
| N→∞の挙動 | 上限 1/(1−p) で飽和 | Nに比例して線形増加 |
| 測定指標 | 応答時間短縮 | 処理規模・処理量 |
| 適合事例 | オンライントランザクション、固定バッチ | HPCシミュレーション、大規模学習 |
表の違いが生じる根本理由は、直列割合を定数と見るか、問題規模の関数と見るか にある。アムダールは直列割合を定数とするため、Nが大きくなると p/N が0に収束して直列項だけが残り、ゆえに飽和する。グスタフソンは問題を拡大すれば並列作業の絶対量が増えて直列割合が減少すると見るため飽和が起きない。実務的含意は明確である。応答遅延を減らす投資(単一クエリの高速化)ならアムダールの天井を先に計算して過剰増設を避けねばならず、処理容量を拡大する投資(より大きなモデル・より多くのユーザー)ならグスタフソン的拡張を前提に水平拡張を設計しつつ、通信・同期コストが新たなボトルネックにならないかを併せて見なければならない。
具体的事例として、推薦システムの夜間バッチ学習を見よう。データが固定された昨日のログなら(strong)、GPUを2枚→8枚に増やしても前処理・チェックポイント保存の直列区間のためアムダールの上限に掛かり、4倍ではなく2.5倍の短縮にとどまる。しかし運用チームが「同じ4時間でより多くの特徴量とより大きな埋め込みを学習」するよう目標を変えれば(weak)、同じ8枚でほぼ線形にモデル規模を拡大できる。同じハードウェアでも目標設定次第で二つのうちどちらの曲線に乗るかが変わる。
5. 深掘り:普遍スケーラビリティ法則(USL)と最新動向
アムダール・グスタフソンは通信・同期コストを無視した理想化モデルという限界がある。現実ではプロセッサが増えるほど共有資源の競合(contention)とデータ一貫性維持のための相互通信(coherency)が増加し、ある地点を超えると性能がむしろ 減少(retrograde) することもある。Neil Guntherの 普遍スケーラビリティ法則(USL, Universal Scalability Law) はこれを二つの罰則項でモデル化する。
C(N) = N / ( 1 + α·(N − 1) + β·N·(N − 1) ) — α:競合(直列化)、β:一貫性(相互通信)係数
ここで β=0 ならUSLはアムダールの法則に還元され、β が0でなければ性能曲線が特定の頂点(peak concurrency)以降に下落する現実的挙動を説明する。USLは少数の負荷測定点(複数のスレッド数での処理量)からα・βを回帰推定し、「我々のシステムは何個のノード/コアまで増やせば利得があるのか」という容量見積もりの問いに定量的な答えを与える。すなわちアムダールが上限を、グスタフソンが拡張可能性を語るなら、USLは 競合・通信コストまで含めた現実的な最適同時実行数 を指し示す。
具体的な数値で見ると、ある分散集計作業をSparkクラスタで10ノード→40ノードへ4倍に増やしたとき処理量が3.9倍まで線形に近く上がり(グスタフソン区間)、80ノードではシャッフルネットワーク競合のためむしろ7.2倍水準で頂点を打ち、100ノードで7.0倍に折れる現象が現れる。この逆転区間はアムダール・グスタフソンだけでは説明されず、USLの β 項でのみ捉えられる。したがって「ノードをもっと入れれば必ず速くなる」という仮定は危険であり、測定で頂点同時実行数を見つけ、それ以上はアルゴリズム・通信構造を変えねばならないという結論になる。
最新動向において、これらの法則はAI・データセンター規模拡張の設計言語となった。数千枚のGPUでLLMを学習するとき、データ・テンソル・パイプライン並列化はグスタフソン的拡張を狙うが、オールリデュース(all-reduce)集合通信がUSLの β 項のように作用し、一定規模を超えると通信がボトルネックになる。そのためNVLink・InfiniBand・RoCEのような高速インターコネクトと、通信・演算のオーバーラップ、勾配圧縮が核心課題となる。Apache Sparkのシャッフル、分散データベースの合意(consensus)も同じ構造で、競合・通信コストが線形拡張を折る地点を作る。結局、現代の分散システム設計は「並列区間を増やし(グスタフソン)、直列・競合・通信を減らす(アムダール・USL)」の二軸の同時最適化に収束する。
6. 考慮事項と示唆
技術士の観点では、これらの法則は単なる公式ではなく、並列・分散投資の妥当性と限界を判断する意思決定フレーム として活用すべきであり、次のような戦略的示唆を持つ。
適用戦略 — ワークロード種別の事前判別:増設投資に先立ち、対象ワークロードが応答時間短縮型(strong、アムダール)か処理規模拡張型(weak、グスタフソン)かをまず分類すべきである。前者は直列割合
pを測定して理論上限を計算し、その範囲内で適正なコア数を定め、後者は問題拡大と水平拡張を前提に通信アーキテクチャを先に設計する。トレードオフ — 直列縮小対並列拡大:アムダールの法則は「並列化を増やすよりも直列ボトルネックを無くすほうが大きな利得」でありうることを示唆する。ロック競合・グローバル資源・逐次I/Oをシャーディング・ロックフリー・バッチで除去するリファクタリングと、コア・ノード増設のどちらに投資するかを費用対効果で比較せねばならない。過剰増設は収穫逓減区間でTCOだけを膨らませる。
現実コストの反映(USL):理想化されたアムダール・グスタフソンだけを信じると通信・同期コストを過小評価し、「入れるほど遅くなる」罠に陥る。小規模負荷試験でα・βを推定して最適同時実行数(peak)を見積もり、その地点を超える拡張はインターコネクト改善やアルゴリズム変更なしには効果がないことを意思決定に反映すべきである。
展望と連携技術 — 異機種・大規模アクセラレーション:GPU・NPU・TPUなどのアクセラレータ、CXLベースのメモリ拡張、超高速インターコネクトが普及するにつれ、並列性能のボトルネックは「演算」から「データ移動と同期」へ移っている。通信・演算のオーバーラップ、集合通信最適化、データ局所性(NUMA・トポロジ対応配置)が三つの法則の実務的延長線であり、巨大モデル学習・リアルタイム推論のコスト・電力効率を左右する中核能力として定着する見通しである。
ガバナンス・運用の観点:スケーラビリティは一度きりのベンチマークではなく継続的な観測対象である。処理量-同時実行数曲線を常時測定して性能リグレッションを早期に捕捉し、ハードウェア世代交代・トポロジ変化の際にα・βを再推定する容量管理プロセスを運用に内在化してこそ、投資対効果を持続的に保証できる。
参考資料
- G. M. Amdahl, "Validity of the single processor approach to achieving large scale computing capabilities" (1967) — https://doi.org/10.1145/1465482.1465560
- J. L. Gustafson, "Reevaluating Amdahl's Law", CACM (1988) — https://doi.org/10.1145/42411.42415
- Neil J. Gunther, "Universal Scalability Law" — https://en.wikipedia.org/wiki/Neil_J._Gunther
- USL R package (vignette/manual) — https://cran.r-project.org/web/packages/usl/vignettes/usl.pdf
一言まとめ: アムダールの法則は作業量を固定したとき直列割合が性能向上の上限(1/(1−p))を定めるstrong scalingを、グスタフソンの法則は問題規模を一緒に拡大すれば性能がプロセッサ数にほぼ線形に拡張するweak scalingを説明し、USLは競合・通信コストまで反映して現実的な最適同時実行数を指し示す相互補完的な並列処理の性能法則である。