アムダールの法則

アムダールの法則とは

アムダールの法則（Amdahl’s Law） は、並列化による高速化の理論的上限を示す法則です。 プログラムのうち並列化できない部分（逐次部分）が全体の高速化を制約します。 逐次部分の割合を s、プロセッサ数を N としたとき、最大スピードアップは次の式で表されます。

Speedup(N) = 1 / (s + (1 - s) / N)

直感的な理解

処理時間の 10% が逐次部分の場合、残り 90% を無限に並列化しても最大スピードアップは 10 倍です。 逆に言えば、コード全体の 10% を 10 倍速くしても、全体の改善は約 9% にとどまります。 この法則は「最も遅い部分を特定し、そこを改善すべき」という優先順位付けの根拠になります。

逐次ボトルネックの特定

実システムでは、逐次ボトルネックは以下のような箇所に現れます。

• グローバルロック（GIL、データベースのテーブルロック）
• 共有キューへの直列アクセス
• 単一スレッドで処理されるイベントループ
• ディスク I/O やネットワーク呼び出し（並列化されていない場合）

プロファイリングでホットパスを特定し、そこが逐次的かどうかを判断することが改善の第一歩です。

Universal Scalability Law（USL）

USL（Universal Scalability Law） は Neil Gunther が提唱した、アムダールの法則を拡張したモデルです。 アムダールの法則は「並列化のオーバーヘッドはゼロ」と仮定しますが、USL はコヒーレンシ（一貫性維持）のコストを加味します。

Speedup(N) = N / (1 + σ(N-1) + κN(N-1))

σ は逐次部分の割合、κ はコヒーレンシペナルティです。 κ > 0 の場合、ある N を超えるとスループットが低下（レトログレード）します。 この現象は、ロック競合やキャッシュ無効化が増えるマルチスレッドシステムで典型的に観測されます。