最終更新: 2026-06-29

グスタフソンの法則

グスタフソンの法則は、問題のサイズがプロセッサ数とともに大きくなるときの並列プログラムの高速化率を見積もる。これはアムダールの法則が問うスケーリングの問題を捉え直したものである。ワークロードを固定して実行を短縮するのではなく、時間の予算を固定し、より大きなマシンがどれだけ多くの作業を完了できるかを問う。本計算では、実行のうち並列化可能な割合とプロセッサ数から、スケール高速化率と並列効率を求める。

固定された作業ではなく固定された時間

より大きなクラスタを導入するとき、実務家は同じジョブを速く実行するのではなく、同じ時間でより大きなジョブを実行することが多い。気象モデルはより細かい格子へ移り、レンダラはより多くのフレームを生成し、学習の実行はより多くのデータを取り込む。この状況では、作業の並列部分が追加したプロセッサを満たすように拡大する一方、逐次的なオーバーヘッド（起動、調整、最終的な集約）はほぼ一定のまま残る。

グスタフソンの法則はこれを捉える。$p$ を並列システム上で測定した実行時間のうち並列作業の割合、$1 - p$ をすべてのプロセッサが共有する逐次部分の割合とする。$N$ 個のプロセッサでのスケール高速化率は次のとおりである。

$S = (1 - p) + p \cdot N$

並列項が $N$ に比例して大きくなるため、予測される高速化率は上限に頭打ちになるのではなく、プロセッサを追加するにつれて上昇し続ける。

計算例

16 プロセッサのシステム上で実行の 95% が並列作業であるとする。スケール高速化率は次のとおりである。

すなわち 16 プロセッサのシステムは、同じ実時間で 1 個のプロセッサの約 15.25 倍の作業を完了し、並列効率は $15.25 / 16 \approx 95\%$ となる。これを固定サイズの見方と対比すると、同じ 95% の並列化可能な割合では、16 プロセッサでの高速化率は約 9.1 倍に、極限でも 20 倍に制限される。

強スケーリングと弱スケーリング

2 つの法則の違いは、強スケーリングと弱スケーリングの違いである。強スケーリング、すなわち アムダールの法則の計算 の領域は、問題を固定したまま保ち、逐次部分の割合によって制限される。弱スケーリング、すなわちグスタフソンの法則の領域は、ハードウェアとともに問題を大きくし、ほぼ線形にスケールする。どちらの法則も普遍的に正しいわけではない。適切な選択は、ワークロードが固定なのか、与えた資源を使い切るように拡大するのかによって決まる。

並列化可能な割合はスケールされたシステム上で測定され、問題のサイズに依存するため、結果は正確な保証ではなく、期待される挙動の見積もりとして扱う。グスタフソンとアムダールの両方の仮定で高速化率を見積もると、起こりうる範囲を挟み込むことができる。