Amdahlの法則 並列加速と効率計算

Amdahlの法則は、計算機アーキテクトの Gene Amdahl が 1967 年に提唱したもので、計算を複数のプロセッサに分散したときに得られる理論上の高速化を表します。これは並列計算において最も重要かつ広く引用される原則の一つであり、プロセッサをいくら増やしても得られる性能向上には厳しい上限があることを示します。 この法則は、実世界のプログラムが 2 つの部分から成るという単純な観察から始まります。1 つは本質的に逐次的で、各ステップが前の結果に依存するため順番に実行しなければなりません。もう 1 つは並列化可能で、独立したタスクに分割して複数プロセッサで同時に実行できます。Amdahlの法則は、この 2 つの関係を数式化したものです。 式は S(n) = 1 / (p + (1 − p) / n) です。S は加速比、p は逐次実行しなければならない割合（0〜1）、n はプロセッサ数、(1 − p) は並列化可能な割合を表します。n が無限大に近づくと、(1 − p) / n は 0 に近づき、加速比は 1/p に近づきます。これが理論上の最大加速比です。この上限は逐次割合だけで決まり、どれだけプロセッサを使っても超えられません。 影響は大きいです。プログラムの 10% が逐次的なら（p = 0.1）、どれだけプロセッサを増やしても最大加速比は 1/0.1 = 10× です。逐次部分が 20% なら最大は 5×、50% なら最大は 2× です。ある点を超えると、プロセッサを増やしても逓減効果しか得られません。逐次部分がボトルネックになるからです。これは「Amdahlの壁」と呼ばれることもあります。 具体例を見てみましょう。単一コアで 3,600 秒かかるプログラムがあり、そのうち 80% は並列化可能だとします（p = 0.2）。8 個のプロセッサを使うと、加速比は S(8) = 1 / (0.2 + 0.8/8) = 1 / (0.2 + 0.1) = 1 / 0.3 = 3.33× です。並列実行時間は 3600 / 3.33 = 1080 秒です。16 個のプロセッサなら S(16) = 1 / (0.2 + 0.8/16) = 1 / (0.2 + 0.05) = 4× で、時間は 900 秒になります。8 から 16 に倍増しても性能向上は 20% にとどまります。逐次 20% が全体を支配するためです。 並列効率は、加速比をプロセッサ数で割り、百分率で表したものです。E = S(n)/n × 100% で表されます。これは各プロセッサがどれだけ有効に使われているかを示します。100% の効率は、各プロセッサが完全に活用されている理想状態です。実際には、逐次部分のためにプロセッサ時間が無駄になるので、プロセッサ数が増えるほど効率は下がります。効率が 50% を下回ると、追加のプロセッサにかかるハードウェアコストのほうが、節約できる時間より大きくなります。 Amdahlの法則は、逐次割合 p が問題サイズに依存せず一定だと仮定します。これに対して Gustafson の法則（1988）は補完的な視点を与えます。問題サイズが大きくなると、より多くの作業が並列化可能になり、プロセッサ数が増えても効率は高く保たれます。2 つの法則を合わせると、並列スケーリングの全体像が見えてきます。Amdahlの法則は悲観的ですが固定サイズの問題を正確に表し、Gustafson の法則は楽観的で、問題サイズがプロセッサ数とともに増える場合に適用されます。 Amdahlの法則の実用例には、CPU/GPU アーキテクチャ設計、クラウド資源の割り当て、高性能計算のアルゴリズム分析、既存システムにプロセッサを追加したときの投資対効果の見積もりなどがあります。計算の逐次割合を見つけて減らすこと——より良いアルゴリズム、同期オーバーヘッドの削減、データ構造の再設計など——が、Amdahlの壁を押し上げる最も効果的な方法です。