並列計算の理論限界（アムダール則とグスタフソン則）

「コアを倍にすれば倍速」が成り立たない理由

並列化の出発点は、ある作業を複数のコアで同時に進めれば時間が短くなる、という直観です。しかし実際の処理は、どうしても一直線にしか実行できない逐次部分（初期化、I/O、結果の集約、依存のある計算など）を含みます。並列化できるのはそれ以外の部分だけです。ここに、コア数をいくら増やしても破れない理論的な上限が生まれます。

まず全体の仕事を割合で分解します。逐次にしか実行できない割合を s、並列化できる割合を p とすると、定義から s + p = 1 です。1コアでの実行時間を 1 と正規化します。

1コアの時間 = s + p = 1

並列化可能部分 p を N 個のコアで完全に等分できたとすると、その部分の実行時間は p / N に縮みます。逐次部分 s は何コアあっても縮みません。なぜなら、定義上それは同時に実行できないからです。

アムダール則: 固定サイズ問題の天井

N コアでの実行時間は、縮まない逐次部分と、N 分の1に縮む並列部分の和になります。

T(N) = s + p / N

高速化率（スピードアップ）S(N) は、1コア時間をこの N コア時間で割った比です。p = 1 − s を代入すると、アムダール則の標準形が得られます。

S(N) = 1 / T(N) = 1 / (s + (1 − s) / N)

ここで N を無限大に飛ばすと、(1 − s) / N は 0 に収束し、分母には s だけが残ります。

lim[N→∞] S(N) = 1 / s

これが核心です。逐次部分が全体の 5%（s = 0.05）あるだけで、コアを無限に積んでも高速化は最大 20倍 で頭打ちになります。s = 0.1 なら上限はわずか 10倍。逐次部分の割合が、並列化で得られる利得の天井を直接決めるのです。計算量記法に不安があれば計算量と Big-O 記法を先に押さえておくと、この比の議論が読みやすくなります。

表が示すのは、逐次部分が 10% を超えると、コアを 256 まで増やしても理論上限の 10倍 にほぼ達してしまい、それ以上のコアは無駄になるという現実です。投資の早い段階で収穫逓減が始まります。

グスタフソン則: 規模を広げれば天井は動く

アムダール則の悲観は「問題サイズが固定」という前提から来ています。しかし実務でコアを増やす動機は、多くの場合「同じ問題を速く」ではなく「より大きな問題を同じ時間で」です。気象シミュレーションも機械学習の学習も、計算資源が増えれば格子を細かく、データを多く投入します。この視点に立つのがグスタフソン則です。

グスタフソンは基準を逆転させます。固定するのは1コア時間ではなく、N コアで実際にかかる時間のほうです。N コアでの実行時間を 1 に正規化し、その内訳を逐次割合 s' と並列割合 p' = 1 − s' とします。

N コアの時間 = s' + p' = 1

この同じ仕事を1コアでやり直したらどれだけかかるか、を考えます。逐次部分 s' はそのまま s'。一方、並列部分 p' は N コアで処理していた量なので、1コアでは N 倍の時間がかかります。

1コアの時間 = s' + N · p'

高速化率はこの比なので、グスタフソン則の標準形になります。

S(N) = s' + N · (1 − s') = N − s' · (N − 1)

これは N の一次関数です。傾きは (1 − s') で、上限がありません。逐次割合 s' = 0.05 でも S(N) = N − 0.05(N − 1) = 0.95N + 0.05 となり、1024 コアなら約 973倍。アムダール則なら 20倍 で頭打ちだった同じ 5% が、規模拡大を許せばコア数にほぼ比例して伸びます。

（上の表の1行目は読み替えで、固定対象が逆になっている点が両則の出発点の違いです。）

スケーラビリティ設計への落とし込み

二つの則から導ける実務指針は明快です。第一に、逐次部分 s の削減は常に効く。アムダールの上限 1/s を押し上げるのも、グスタフソンの傾き (1 − s') を立てるのも、結局は逐次割合を下げることだからです。並列度を上げる前に、まず逐次のボトルネック――グローバルロック、シリアルな初期化、全体集約――を疑います。ここでロックフリー・ウェイトフリーとCAS命令のような技法が、見かけ上の逐次区間（クリティカルセクション）そのものを縮める武器になります。

第二に、スケーリングの種類を見極めること。バッチ集計のように仕事量が決まっている処理は強スケーリングなのでアムダールの天井を直視し、コア追加の費用対効果を冷静に見積もります。逆に、より高精度・大規模を狙える処理は弱スケーリングとして設計し、コア増に合わせて問題規模を伸ばすことで線形に近い利得を引き出します。

まとめ: 二つの天井を使い分ける

アムダール則は「逐次部分が 1/s という天井を決める」と固定サイズ問題の限界を厳しく突きつけ、グスタフソン則は「規模を広げれば高速化はコア数に比例する」と可変サイズの希望を示します。両者は固定する対象が違うだけの同じ世界の別の切り口で、共通の結論は逐次割合を削れ。並列化を検討するときは、まず自分の問題が強スケーリングか弱スケーリングかを判定し、対応する式に s を入れて天井を見積もる――この一手が、報われない並列投資を避ける最短路です。