プロセッサやコアを二倍、四倍に増やせば、プログラムもそれだけ早く終わると期待しがちです。ところが実際に動かしてみると、体感速度の向上は期待を大きく下回ることがよくあります。並列化できない区間が全体の速度を制限するという洞察、それが「アムダールの法則(Amdahl’s Law)」です。
アムダールの法則とは、簡単に言えば「ある作業の一部だけを改善したり並列に実行したりするとき、全体のスピードアップの上限は、手を加えられなかった逐次実行区間によって決まる」という説明です。コンピュータ科学者のジーン・アムダール(Gene Amdahl)は、1967年のAFIPS春季合同コンピュータ会議で発表した論文「大規模な計算能力を実現するための単一プロセッサ方式の妥当性(Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities)」で、この議論を展開しました。
本資料では、アムダールの法則におけるスピードアップの意味から、逐次実行部分の割合が上限を決める仕組み、料理や組立ラインといった日常の例えとマルチコアの実情、そしてグスタフソンの法則との違いや使い方まで、順に見ていきます。
アムダールの法則が示す並列化の限界
スピードアップと逐次実行区間の意味
アムダールの法則は、もともと「システムの一部を改善したとき、全体の性能がどれだけ向上するか」を扱う一般原理であり、今日では並列コンピューティングの理論的なスピードアップを予測するために最もよく使われています。重要なのは、作業全体を一度に拡張するのではなく、並列化できる部分と、必ず順番に実行しなければならない部分に分けて考えることです。
全実行時間のうち並列化できる割合をp、プロセッサ（またはコア）の数をNとすると、理論的なスピードアップは1を((1-p) + p/N)で割った値になります。同じことを逐次実行部分の割合sで表すと、スピードアップは1を(s + (1-s)/N)で割った値です。Nが大きくなるほど並列実行区間の影響は小さくなりますが、逐次実行区間sはそのまま残ります。プロセッサを無限に増やしても、スピードアップは1/sを超えられません。
- スピードアップ(Speedup)：改善前の実行時間を改善後の実行時間で割った値です。
- 逐次実行部分の割合(Serial Fraction)：並列化できず、順番に処理しなければならない時間の割合です。
- 並列実行部分の割合(Parallel Fraction)：複数のプロセッサに分けて同時に実行できる時間の割合です。
なぜコアを増やしても体感速度はあまり上がらないのか
公式だけでは抽象的に感じられるかもしれませんが、よく取り上げられる上限を考えると直感的に理解できます。作業の半分しか並列化できなければ、コアをいくら増やしても全体のスピードアップは最大二倍にとどまります。並列化できる割合が95パーセントでも、理論上の上限は二十倍です。残りの5パーセントの逐次実行区間が、全体の速度を制限するからです。
(1) 収穫逓減が早く現れる
逐次実行区間の割合が同じなら、コアを2個から4個、8個へと増やすときの効果は、次第に小さくなります。並列実行区間がすでに短くなった後は、逐次実行区間がボトルネックになります。
(2) 通信や同期も逐次実行に近い
実際に処理をコアに分散すると、結果を集め、ロックをかけ、メモリの整合性を取る時間が発生します。このコストは公式の「完全な並列実行」という仮定には含まれていないため、体感上のスピードアップは理論値よりもさらに低くなりがちです。
(3) 一行のボトルネックが全体を左右する
ファイルの読み込み、初期化、最後の集計のような短い逐次実行コードでも、その割合が小さくなければ上限を大きく引き下げます。マルチコアCPUやGPUによる高速化を設計するときに、「どこを並列化するか」よりも先に「どこに逐次実行が残るか」を問う理由は、ここにあります。
料理と組立ラインで考える日常の例え
アムダールの法則は、コンピュータ以外でも同じ構造で現れます。十人の客のために夕食を準備する場面を考えてみましょう。野菜を切ったり炒めたりする作業は、手伝う人を増やせば速くなりますが、オーブンで焼く時間は人が多くても短くなりません。オーブンが逐次実行区間に当たるなら、人手をいくら増やしても、夕食の準備全体にかかる時間はその区間に制約されます。
工場の組立ラインも同様です。複数の工程で同時に部品を組み合わせても、最終検査や梱包が一列でしか進まなければ、その列の処理量が全体の速度を決めます。会議でも資料調査は分担できますが、決定を下すための一度の合意形成を並列に進めるのは困難です。
日常で確認したいポイント
- ボトルネック(Bottleneck)：最も遅い逐次実行区間が、全体の流れを支配します。
- 分担できる作業(Parallel Work)：独立して同時に進められる部分です。
- 調整作業(Coordination)：結果を集めて順序をそろえるコストも、体感速度を下げます。
グスタフソンの法則と併せて考える方法
アムダールの法則は、「問題の規模を固定したまま」プロセッサを増やす場合の上限を示します。一方、ジョン・グスタフソン(John Gustafson)が1988年前後にまとめたグスタフソンの法則(Gustafson’s Law)は、プロセッサが増えたら問題自体も大きくして、同じ時間でより多くの仕事をするという視点に立っています。決まった課題を早く終わらせる話と、より精密なシミュレーションを同じ期限内に実行する話では、問いが異なります。
(1) 規模が固定された問題にはアムダールの法則が鋭く切り込む
同じデータ・同じ解像度で「より速く」を目指すときは、逐次実行部分の割合を減らすことが鍵です。アルゴリズムを変更し、I/Oを減らし、不要な同期を取り除く設計がこれに当たります。
(2) 規模を拡大するときはグスタフソンの法則が力になる
気象計算や科学計算のように格子やサンプルを増やせる問題では、コアが増えるほど並列に処理する作業量も増え、実質的な効果が大きくなる可能性があります。
(3) 両者を対立させない
どちらかが誤った公式というよりも、「何を固定し、何を大きくするか」が異なるシナリオです。製品を作る際は、目標が遅延の短縮なのか、処理量や規模の拡大なのかをまず選び、その上で適した視点を使えばよいのです。
コア数の広告だけを見て期待を膨らませるよりも、自分たちの作業で逐次実行として残る区間がどこなのかを、まず測ってみる姿勢が大切です。並列化の成否を左右するのは、購入したコアの数よりも、分割できない時間をどれだけ減らしたかです。
アムダールの法則は、並列化できる部分だけを改善しても、全体のスピードアップの上限は逐次実行区間の割合によって決まるという原理です。コアを増やすことよりも、ボトルネックとなる逐次実行区間を見つけて短くすることのほうが、性能の限界により直接的に働きかけます。
プロセッサ数を考える前に、分割できない時間を測ってみること。それが、アムダールの法則を実務に生かす知恵の第一歩です。
