アムダールの法則｜並列計算と計算複雑性理論

ハードウェアの物理的な限界（エンジニアリング）から、計算理論による下界の特定について

並列計算と計算複雑性理論の系譜（1967〜1995）

1. 黎明期：物理リソースの限界と「直列の壁」

📌 アムダールの法則（Amdahl’s Law）

• 【原典】 Validity of the single processor approach to achieving large scale computing capabilities (1967)
• https://www3.cs.stonybrook.edu/~rezaul/Spring-2012/CSE613/reading/Amdahl-1967.pdf
• 【著者】 Gene M. Amdahl (ジーン・アムダール)
• 【核心】 「強スケーリング（タスクサイズ固定）」の思想。 プログラムの中にどれだけ最適化しても排除できない「直列処理の割合（1-p）」がある限り、いくらプロセッサ数（n）を増やしても、全体の加速比（Speedup）は頭打ちになる。シングルプロセッサの性能向上が最優先であると主張。

📌 グスタフソンの法則（Gustafson’s Law）

• 【原典】 Reevaluating Amdahl’s Law (1988)
• https://dl.acm.org/doi/epdf/10.1145/42411.42415
• 【著者】 John L. Gustafson (ジョン・グスタフソン)
• 【核心】 「弱スケーリング（実行時間固定）」の思想。 アムダールの「問題サイズ固定」という前提を破壊。「プロセッサが増えれば、人間はより大きな問題を解く（タスクサイズを拡大する）」ため、直列処理の割合は薄まり、性能はプロセッサ数に対して直線的（リニア）にスケールすると反論。

📌 サン・ニの法則（Sun-Ni’s Law）

• 【原典】 Another view on parallel speedup (1990) /
• http://intranet.di.unisa.it/~vitsca/SC-2011/DesignPrinciplesMulticoreProcessors/Sun1990.pdf
• Scalability of A-centric and G-centric parallel algorithms (1993)
• http://www.cs.iit.edu/~scs/psfiles/scalability94.pdf
• 【著者】 Xian-He Sun, Lionel M. Ni (シアンへ・サン、ライオネル・ニ)
• 【核心】 「メモリ制限下の加速比」の思想。 アムダール（A-centric）とグスタフソン（G-centric）を内包するメタ理論。プロセッサが増えれば「総メモリ容量」が増えるという現実に着目。メモリ限界までタスクを拡張した際、データ量（メモリ）の増加に対して計算量（ワークロード）が爆発的に増えるアルゴリズムでは、グスタフソンのリニア（直線）を超える超線形スケーリングが可能であることを証明。

2. 抽象化の時代：幾何学的構造としての「直列依存の証明」

📌 カルシュマー・ヴィグダーソンの定理（K-W Game）

• 【原典】 Monotone Circuits for Connectivity Require Super-Logarithmic Depth (1988/1990)
• https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/KW88/KW88.pdf
• 【著者】 Mauricio Karchmer, Avi Wigderson (アヴィ・ヴィグダーソン)
• 【核心】 「回路の深さ（Depth＝時間）＝ 通信複雑性（必要な情報交換）」の等価性を証明。 アムダールが言った「直列の壁」の正体を、抽象的な回路モデルにおける「どうしてもショートカットできない深さの下界（Lower Bound）」として数学的にサンプリング・証明。

📌 ラーズ・ヴィグダーソンの定理

• 【原典】 Monotone Circuit Complexity of Matching (1992) など
• https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/RAN/MATCHING/matching.pdf
• 【著者】 Ran Raz, Avi Wigderson (ラニ・ラズ、アヴィ・ヴィグダーソン)
• 【核心】 「本質的な並列化不可能（P完全）」の数学的証明。 最大マッチング問題などの複雑なタスクにおいて、どれだけ並列数（Size）を増やしても、入力サイズに比例した「ド直列なステップ（Depth）」が絶対に必要であることをアルゴリズムの幾何学的構造から宣告。

📌 KRW予想（Karchmer-Raz-Wigderson Conjecture）

• 【原典】 Super-logarithmic depth lower bounds via the direct sum in communication complexity (1995)
• https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/MAURICIO/COMPOSITION/JOURNAL/final.pdf
• 【著者】 M. Karchmer, R. Raz, A. Wigderson
• 【核心】 「直列依存の増幅（合成）」に関する未解決予想。 直列の壁（Depth）を持つタスク同士を結合させると、その直列依存性は隠蔽できず、単純な「足し算（直和）」で増幅するという理論。構造の工夫（ハック）による一括並列化（ショートカット）の不可能性を提示。

3. 現代の最前線：この宇宙で最も硬い「最重要直列構造」の攻略

📌 分散・並列SATソルバー（Distributed SAT Solving）

• 【現代の戦場】 計算理論の頂点である「NP完全問題（SAT）」の分散処理。
• 【数理の交錯】 SATという「本質的に超直列な依存関係（探索木）」に対し、現代のアーキテクチャは数千台のノード（Size）を投入して力技で時間を縮めようとしている（ポートフォリオ方式 / 領域分割方式）。
• 【本当のボトルネック】 分散処理を進めると、ノード間で「教訓（学習節）」を共有するための通信が発生する。ここでまさにアヴィ・ヴィグダーソンの「通信複雑性」の壁が現実化し、通信のオーバーヘッドという「新たな直列の壁（アムダールの呪い）」と戦うことになる。

💡 系譜

【エンジニアリング（物理の壁）】
アムダール / グスタフソン / サン・ニ
「サーバーやメモリをどう増やせば、処理はスケールするか？」
      │
      ▼ 翻訳・抽象化
【計算複雑性理論（数学の宿命）】
アヴィ・ヴィグダーソン（回路計算量 / 通信複雑性 / KRW予想）
「それはリソースの有無ではなく、タスクの構造自体に埋め込まれた『通信の壁（直列依存）』である」
      │
      ▼ 実装・適用
【P vs NP】
分散SATソルバー 
「宇宙で最も硬い直列構造（NP完全/SAT）を、通信ボトルネックを最小化した分散アルゴリズムで攻略する」

人、資本（資本政策）、ハードウェアといった「Size（横幅）」をいくら拡大しても、システムや組織の構造に「情報の非対称性」や「承認リレー」といったアヴィの通信ゲーム（直列依存）が埋め込まれている限り、「Depth（実行時間・成長スピード）」は1ミリも縮まらない。

資本やリソースを投下すべき唯一の対象は、Sizeの拡大ではなく、直列依存をパージし、並列可能なアルゴリズムへと構造そのものを書き換えることである。（ただしそう理想的にはいかない）