Amdahlの法則とGustafsonの法則 ─ 並列化の上限と弱スケーリング

なぜコアを増やしても速くならないのか

マルチコアCPUやGPUの大量スレッドを投入すれば計算は速くなる、と期待しがちです。しかし実際は、コア数を2倍にしても処理時間は半分にならないことがほとんどです。その上限を最初に数式で示したのが Amdahlの法則（1967） です。

鍵は、どんなプログラムにも並列化できない逐次部分が残るという事実です。初期化、入出力、リダクションの最終集約、依存のある前処理などは、コアを増やしても短縮できません。プログラム全体の実行時間を1とし、そのうち並列化可能な割合を p、逐次のままの割合を 1-p とすると、N 個のコアで実行したときの高速化（スピードアップ）は次で表せます。

Amdahlの法則（強スケーリング）
                 1
S(N) = ─────────────────────
        (1 - p) + p / N

S(N)  : N コアでの高速化（逐次=1）
p     : 並列化可能な割合（0〜1）
1 - p : 逐次部分の割合
N     : コア数（処理要素数）

並列部分 p はコア数 N で割れて縮みますが、逐次部分 1-p はどれだけ N を増やしても残り続けます。これが律速になります。

Amdahlの上限 ─ 高速化は頭打ちになる

N を無限大に飛ばすと、p/N の項は 0 に近づき、高速化は次の値に収束します。

lim S(N) = 1 / (1 - p)   （N → ∞）

つまり到達できる最大の高速化は逐次部分の逆数で決まり、コア数では決まりません。逐次が5%（p=0.95）なら、コアを何千個積んでも理論上限は20倍止まりです。逐次が1%でも上限100倍です。具体的な数値で頭打ちを見ると衝撃があります。

p=0.95 のとき、16コアで9.1倍まで伸びても、256コア（16倍のコア）にして得られるのは18.6倍。コアを16倍にしても高速化は約2倍にしかならず、追加した240コアはほとんど遊んでいます。

Gustafsonの法則 ─ 問題規模を増やすという反論

Amdahlの法則は悲観的に見えますが、暗黙の前提があります。それは問題規模を固定したままコアを増やすこと。これを 強スケーリング（strong scaling） と呼びます。

しかし現実の高性能計算では、コアが増えれば「より大きな問題」を解こうとします。気象シミュレーションなら解像度を上げ、機械学習ならバッチやモデルを大きくする。Gustafsonの法則（1988） はこの観点に立ち、「並列部分は問題規模に比例して増え、逐次部分（初期化など）は規模が増えてもほぼ一定」とモデル化します。N コアで実行する規模の問題を1コアで解いたと仮定したときの高速化は次です。

Gustafsonの法則（弱スケーリング）
S(N) = (1 - p) + p × N

p     : 並列実行に費やされる時間割合（N コア実行時の計測）
1 - p : 逐次に費やされる時間割合
N     : コア数

この式は N に対してほぼ線形に伸び、頭打ちがありません。逐次割合 1-p=0.05、N=256 なら高速化は 0.05 + 0.95×256 ＝ 約243倍。Amdahlの上限20倍とはまるで違う結論です。コア数を増やすぶん問題も大きくする運用を 弱スケーリング（weak scaling） と呼びます。

強スケーリングと弱スケーリングの判定

実機で性能を評価するときは、この2つを混同しないことが決定的に重要です。測定の設計が変わります。

弱スケーリングの理想は「コアが2倍・問題が2倍でも、実行時間は変わらない」ことです。実行時間が伸びていくなら、それは逐次部分やデータ移動が規模に応じて増えている兆候です。

通信オーバーヘッドと実効並列効率

理想化された2法則には、実機の最大の敵が含まれていません。通信・同期のオーバーヘッドです。コアを増やすと、データ分配・境界交換・コア間のコヒーレンス・バリア同期のコストが増えます。これは並列部分に上乗せされる「並列化したからこそ発生する仕事」で、コア数とともに増大することが多い。

オーバーヘッドを O(N) として高速化を書き直すと、Amdahl式は次のように補正されます。

S(N) = 1 / ( (1 - p) + p/N + O(N) )

O(N) : 通信・同期に費やす時間割合（N とともに増えがち）

O(N) が N の増加で大きくなると、ある点で S(N) は増えるどころか減少に転じることすらあります。コアを足しすぎると遅くなる、という現象です。この振る舞いを定量化するのが並列効率（parallel efficiency） です。

並列効率 E(N) = S(N) / N

E(N) = 1   : 理想（リニアスケーリング、コアぶん完全に速くなる）
E(N) < 1   : 通信・逐次部分による損失

効率は「投入したコアがどれだけ無駄なく働いたか」を表します。E=1 が理想、現実は N の増加とともに E が 1 を下回って低下します。逐次が5%・オーバーヘッドなしの理想でも、256コアでの効率は18.6÷256 ＝ 約7.3%にまで落ちます。

なぜ逐次部分は消えないのか

逐次部分が残る理由は、アルゴリズムのデータ依存にあります。総和（リダクション）の最終集約、再帰的な前段の結果を使う処理、入出力のように本質的に順序付けられた操作は、並列化しても必ずどこかで合流点（バリア）を持ちます。キャッシュ階層を通じた共有データへのアクセス競合も、実質的な逐次化を生みます。複数コアが同じキャッシュラインを書き換え合えば、コヒーレンスプロトコルがアクセスを直列化するためです。

だからこそ最適化の優先順位は、第一に逐次部分そのものをアルゴリズムで削る（依存を断つ、リダクションを木構造で並列化する）、第二に通信を減らす（データ局所性を高め、同期回数を削る）、第三にコア数を増やす、の順になります。順序を逆にすると、Amdahlの壁に早々に突き当たります。

まとめ

• Amdahlの法則は問題規模固定の強スケーリングを表し、高速化は 1 / ((1-p) + p/N)、上限は逐次部分の逆数 1/(1-p) でコア数では決まらない。
• Gustafsonの法則は問題規模をコア数に比例させる弱スケーリングを表し、スケールド高速化は (1-p) + p×N とほぼ線形に伸びる。両者は対立せず、固定サイズの締切短縮か規模拡大かで使い分ける。
• 実機では通信・同期オーバーヘッド O(N) が並列部分に上乗せされ、コアを増やしすぎると高速化が頭打ち・減少する。
• 並列効率 E(N) = S(N)/N はコア増で低下する。最適化は「逐次部分を削る→通信を減らす→コアを増やす」の順が定石。

突き詰めれば、並列化の上限を決めるのはコア数ではなくアルゴリズムに残る逐次性とデータ移動です。ハードウェアの並列性を引き出す鍵は、ここを削ることに尽きます。