性能の評価とアムダールの法則

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：CPUと命令実行・メモリ階層とキャッシュ　|　関連：並行性のパターン

要点（BLUF）

「クロックが速い＝速い」は誤り。CPUの実行時間は CPU時間 = 命令数(IC) × CPI × クロック周期 の3要素で決まる。どれか1つだけ見ると判断を誤る。
アムダールの法則：一部分だけ高速化しても、全体の改善は「高速化できない部分」に頭打ちにされる。95%を無限に速くしても全体は最大20倍まで。
だから最適化は「一番時間を食っている所」から手を付ける。並列化（並行性のパターン）にも理論上限がある。

概念 ── 「速い」を分解する

2台のCPUのどちらが速いか。クロック周波数（GHz）を比べたくなりますが、それだけでは決まりません。実際の実行時間こそが速さで、それは次のように分解できます（P&HのCPU性能式）。

\text{CPU時間} = \underbrace{\text{命令数(IC)}}_{\text{プログラムとコンパイラ}} \times \underbrace{\text{CPI}}_{\text{命令あたりのクロック数}} \times \underbrace{\text{クロック周期}}_{\text{1クロックの長さ}}

命令数（IC）：そのプログラムを実行するのに必要な機械語命令の総数。アルゴリズム・コンパイラで変わる。
CPI（Cycles Per Instruction）：1命令あたり平均何クロックかかるか。命令の種類・パイプライン効率・キャッシュミス（メモリ階層とキャッシュ）で変わる。
クロック周期：1クロックの時間（周波数の逆数）。3GHzなら約0.33ns。

要するに速さは「やる仕事量（IC）×1ステップの重さ（CPI）×1ステップの時間（周期）」。3つの掛け算なので、1つだけ改善しても他が悪ければ帳消しになります。

仕組み ── クロックだけでは決まらない

具体例で確かめます（[[#対応ラボ]] の 01-05_performance_amdahl.py）。命令数を10億として、CPIを変えるとどうなるか。

IC, cycle = 1_000_000_000, 1/3.0e9   # 命令数10億、3GHz
for cpi in (1.0, 1.5, 2.0):
    print(f"CPI={cpi:.1f} -> CPU時間 = {IC*cpi*cycle*1000:.2f} ms")

実行結果（実機）:

CPI=1.0 -> CPU時間 = 333.33 ms
CPI=1.5 -> CPU時間 = 500.00 ms
CPI=2.0 -> CPU時間 = 666.67 ms

CPIが2倍なら時間も2倍。では「クロックが速いCPU」と「CPIが小さいCPU」のどちらが勝つか。

tA = IC * 2.0 * (1/3.0e9)   # A: 3GHz だが CPI 2.0
tB = IC * 1.0 * (1/2.0e9)   # B: 2GHz だが CPI 1.0

実行結果（実機）:

A(3GHz,CPI2.0): 666.67 ms / B(2GHz,CPI1.0): 500.00 ms
速いのは: B (クロックだけでは決まらない)

クロックが遅いBの方が速い。CPIが効いたからです。CPUのカタログ値（GHz）だけで性能を語れない理由がこれです。

仕組み ── アムダールの法則

最適化や並列化を考えるとき、決定的に重要なのが アムダールの法則。「プログラムのうち割合 p の部分を s 倍速くできるとき、全体の高速化倍率は」

\text{全体の高速化} = \frac{1}{(1-p) + \dfrac{p}{s}}

ポイントは、s を無限に大きくしても、分母の (1-p)（高速化できない部分）が残ること。

def amdahl(p, s):
    return 1.0 / ((1.0 - p) + p / s)
# プログラムの95%を高速化できる場合
for s in (2, 10, 100, 1_000_000):
    print(f"その部分を {s} 倍 -> 全体は {amdahl(0.95, s):.2f} 倍")

実行結果（実機）:

その部分を 2 倍 -> 全体は 1.90 倍
その部分を 10 倍 -> 全体は 6.90 倍
その部分を 100 倍 -> 全体は 16.81 倍
その部分を 無限大 倍 -> 全体は 20.00 倍

95%を無限に速くしても、全体はたった20倍で頭打ち。残り5%が律速になるからです。「高速化できる部分」より「できない部分」が天井を決めるのです。

これは並列化（マルチコア）でも同じ。並列化できる割合がわかれば、コア数を無限に増やしたときの理論上限が読めます。

並列化可能 50% -> どれだけコアを増やしても上限 2.0 倍
並列化可能 90% -> どれだけコアを増やしても上限 10.0 倍
並列化可能 95% -> どれだけコアを増やしても上限 20.0 倍
並列化可能 99% -> どれだけコアを増やしても上限 100.0 倍

逐次部分（並列化できない部分）が1%でも残れば、上限は100倍。これが並行処理（並行性のパターン）の「コアを増やしても比例して速くならない」現実の根拠です。

仕組みの直観 ── なぜこの設計か（なぜこの法則が効くか）

性能を3要素に分ける理由：最適化の打ち手がどこに効くかを切り分けられる。アルゴリズム改善はIC、命令選択やキャッシュ最適化はCPI、プロセス微細化はクロック。混ぜて議論すると判断を誤る。
アムダールが教える戦略：「一番時間を食っている部分（大きい p）から手を付けよ」。1%の部分を1000倍にしても無意味。プロファイラでホットスポットを特定するのはこのため。
並列化の限界：逐次部分（依存・同期・通信）が残る限り、スケールには天井がある。だから「並列化しやすい問題設計」自体が価値を持つ。

⚠️ よくある誤解・落とし穴

「GHzが高いほど速い」→ CPIと命令数次第で逆転する（上の実機例）。
「コアを2倍にすれば2倍速い」→ アムダールの上限がある。逐次部分が支配する。
「とにかく最適化すれば速くなる」→ 時間を食っていない部分を最適化しても全体は動かない。まず測る（プロファイル）。
「キャッシュミスは性能式と無関係」→ ミスはCPIを押し上げる。メモリ階層とキャッシュのAMATが性能式に効いてくる。

対応ラボ

cs-foundations-study/labs/01-05_performance_amdahl.py（実行して上記の値を確認済み）。

確認できること：CPU性能式の3要素、クロックとCPIの逆転、アムダールの頭打ち、並列化の理論上限