最終更新: 2026-06-29

アムダールの法則

アムダールの法則は、固定された作業の一部を複数のプロセッサで並列実行したとき、その作業がどれだけ速くなるかを予測する。これは、ソフトウェアをより多くのコアへスケールさせるときに技術者が必ず直面する問いに答える。すなわち、作業の一部しか並列化できない場合、現実的な高速化率はどれくらいで、ハードウェアの追加がどこで効かなくなるのか、という問いである。本計算では、並列化可能な作業の割合とプロセッサ数から、得られる高速化率、理論上の上限、並列効率を求める。

逐次部分というボトルネック

ほとんどのプログラムは複数種類の作業が混在している。ループの独立した反復、別々の画像タイルのレンダリング、異なるレコードの処理といった部分は、同時に実行できる。一方、設定ファイルの読み込み、他のすべてが依存するデータ構造の構築、最後の集約処理といった部分は、順番に実行しなければならない。逐次部分はプロセッサを追加しても加速できないため、全体の実行時間に下限を設ける。

アムダールの法則はこれを正確に表す。$p$ を元の実行時間のうち並列化可能な割合、$1 - p$ を逐次部分の割合とする。$N$ 個のプロセッサを使うと、並列部分は元の時間の $p/N$ で終わるが、逐次部分は依然として $1 - p$ かかる。全体の高速化率は、元の時間を新しい時間で割った値である。

$S = \dfrac{1}{(1 - p) + \dfrac{p}{N}}$

上限

$N$ が大きくなると $p/N$ の項はゼロに近づくが、逐次部分の項 $1 - p$ はそのまま残る。極限をとると、プログラムが到達しうる最大の高速化率が得られる。

$S_{\max} = \dfrac{1}{1 - p}$

並列化可能な割合が 95% のプログラムは、どれだけプロセッサを投入しても 20 倍を超えることはない。並列化可能な割合が 50% のプログラムは 2 倍が上限である。これが、単にコアを増やすのではなく、逐次部分の割合を減らすことのほうがしばしば効果の大きい最適化となる理由である。

計算例

ある処理の 95% が並列化可能で、それを 16 個のプロセッサで実行するとする。高速化率は次のとおりである。

すなわち 16 個のプロセッサで得られる高速化率は約 9.1 倍であり、理想的な 16 倍には大きく及ばない。ここでの理論上の上限は $1/0.05 = 20\times$ で、並列効率は $9.14/16 \approx 57\%$ となる。追加した計算能力のほぼ半分が逐次部分というボトルネックに失われていることを意味する。

効率が重要な理由

並列効率 $E = S / N$ は、追加したプロセッサがどれだけ有効に使われているかを表す。効率が 100% に近ければほぼ線形にスケールしており、$N$ を増やすにつれて効率が急速に低下するなら、逐次部分が支配的でハードウェアの追加が割に合わないことを示している。アムダールの法則は強スケーリング、すなわち固定されたワークロードをより多くのプロセッサで処理する状況を記述する。ワークロード自体がハードウェアとともに大きくなる場合には、より楽観的な グスタフソンの法則の計算 が代わりに当てはまる。

並列化可能な割合は推定値として扱う。通常はプロファイリングで測定され、問題のサイズやハードウェアによってしばしば変動するため、予測される高速化率は保証ではなく、期待される挙動の目安である。