アムダールの法則とは？
アムダールの法則は、コンピュータアーキテクトのジーン・アムダール（Gene Amdahl）が1967年に提唱したもので、処理の一部だけしか並列化できない場合に得られる「理論上の最大スピードアップ」を予測する法則です。並列コンピューティングの基礎理論であり、プロセッサ・コア・スレッドを増やすことが本当に効果に見合うのかを技術者が判断する際の指針になります。最も重要なポイントは、並列化できない逐次（シリアル）処理の割合が全体の速度向上に上限を課すという点です。並列部分にいくらリソースを投入しても、この上限は超えられません。
この計算機の使い方
入力するのは次の2つの値です。1つ目はプログラムの並列化できる割合（複数のプロセッサに分散できる処理の比率）をパーセントで指定します。2つ目は並列部分の高速化倍率で、通常はその処理を実行するプロセッサ数やコア数に相当します。計算機は、全体のスピードアップ、並列部分の高速化が無限大だった場合の理論上の最大スピードアップ、そして並列効率を返します。
計算式の解説
計算式は
$$\text{Speedup} = \dfrac{1}{(1 - p) + \dfrac{p}{s}}$$です。ここで \(p\) は並列化できる割合（0〜1の値）、\(s\) はその部分に適用される高速化倍率を表します。\((1 - p)\) の項は、高速化できない逐次部分です。\(s\) を無限大に近づけていくと、スピードアップは \(\dfrac{1}{1 - p}\) に収束します。これが逐次部分によって決まる「越えられない上限」です。
計算例
たとえば、プログラムの90%が並列化可能（\(p = 0.9\)）で、8個のプロセッサで実行する（\(s = 8\)）場合を考えます。分母は
$$(1 - 0.9) + \frac{0.9}{8} = 0.1 + 0.1125 = 0.2125$$となり、スピードアップは
$$\frac{1}{0.2125} \approx 4.71\,\text{倍}$$になります。仮にプロセッサが無限にあっても、最大スピードアップは
$$\frac{1}{0.1} = 10\,\text{倍}$$にとどまります。わずか10%の逐次部分が、これほどまでに性能の上限を決めてしまうことがよく分かります。
結果の解釈
スピードアップ値は、\(s\)個のプロセッサで実行した場合のプログラムが、単一プロセッサでの実行と比べて何倍高速になるかを示しています。スピードアップ4×は、並列化されたワークロードが元の時間の4分の1で完了することを意味します。Amdahlの法則は固定サイズの問題を想定しているため、スピードアップは高速化できないシリアル分数\(1-p\)によって制限されます。
無限プロセッサの上限である\(1/(1-p)\)は、無制限のハードウェアで達成可能な最大スピードアップです。例えば、作業の95%が並列化可能である場合、上限は\(1/(1-0.95) = 20\times\)です。100万個のコアを使ってもこの20×を超えることはできません。これはプランニングにおいて最も重要な数値であり、追加プロセッサへの投資の上限を設定します。
並列効率はプロセッサの利用率を測定する指標であり、スピードアップをプロセッサ数で割った値で定義されます。\(\text{効率} = \text{スピードアップ}/s\)です。効率1.0（100%）は完全な線形スケーリングです。実際には、コアを追加するにつれて効率は低下します。例えば、90%並列化可能なコードを8コアで実行すると、スピードアップは4.71×となり、効率は\(4.71/8 \approx 59\%\)となります。追加された各コアは段々と有用な仕事をしなくなっていきます。
追加プロセッサの追加がもはや価値がなくなるのは、追加コアあたりの限界スピードアップがそのコストに相対して小さくなった場合と、効率が許容できるしきい値（実際には通常50～70%）を下回った場合です。スピードアップが上限に近づくと、さらなるハードウェアの追加はほぼ何ももたらしません。上限自体を上げるには、アルゴリズムのより多くの部分を並列化するか、同期とI/Oのオーバーヘッドを削減することによってシリアル分数を減らす必要があります。単により多くのコアを購入することではありません。また、Amdahlの法則は通信と調整のオーバーヘッドを無視しているため、現実のスピードアップはこれらの理論的最大値よりも通常は低いものです。
よくある質問（FAQ）
なぜプロセッサを2倍にしても速度は2倍にならないのですか？ 逐次部分はプロセッサ数に関係なく同じ速度でしか処理できないため、その処理時間が支配的なボトルネックになるからです。
並列効率とは何ですか？ スピードアップをプロセッサ数で割り、パーセントで表したものです。投入したリソースをどれだけ無駄なく活用できているかを示す指標です。
グスタフソンの法則とはどう違うのですか？ グスタフソンの法則は、問題のサイズがプロセッサ数に応じて拡大することを前提とします。固定された作業量を想定するアムダールの法則よりも、楽観的な見通しを示すことが多いのが特徴です。
