グスタフソンの法則

グスタフソンの法則とは

グスタフソンの法則（Gustafson's law）は、計算機工学における重要な法則の一つで、「十分に大きな規模の問題は、効率的に並列化して解くことができる」という考え方を示します。この法則は、アムダールの法則が指摘する並列化の限界に対し、問題規模の拡大を考慮することで、より大規模な問題に対する並列計算の有効性を示唆します。

法則の概要

グスタフソンの法則は、並列計算におけるスケーラビリティの可能性に着目し、問題規模が大きくなるにつれて、並列化による高速化効果がより顕著になることを示しています。この法則は、以下の数式で表されます。

math
S(P) = P - α(P - 1)


ここで、`S(P)` はプロセッサ数`P`におけるスピードアップ、`α` はプログラムの並列化できない部分の割合を表します。

アムダールの法則との違い

アムダールの法則は、プログラムの直列的な部分がボトルネックとなり、並列化による高速化には限界があるという考え方を示します。一方、グスタフソンの法則は、問題規模を固定せず、むしろ問題規模が大きくなるにつれて並列化の有効性が高まるという考え方に基づいています。つまり、アムダールの法則は、固定された問題に対する高速化の限界を示すのに対し、グスタフソンの法則は、問題規模の拡大に伴う並列化の可能性を示唆しています。

法則の実現

グスタフソンの法則では、問題の規模を`n`としたとき、プログラムの実行時間を直列部分`a(n)`と並列部分`b(n)`に分解します。このとき、全体の実行時間は`a(n) + b(n) = 1`となります。

並列計算機の場合、プロセッサ数を`p`とすると、相対的な処理時間は`a(n) + p b(n)`となります。したがって、スピードアップは次のようになります。

math
S = a(n) + p(1 - a(n))


ここで、`a(n)`は問題のサイズ`n`に対する直列部分の割合を示す関数です。`a(n)`が`n`の増加とともに減少すると仮定すると、`n`が無限に大きくなるにつれてスピードアップはプロセッサ数`p`に近づきます。

2つの法則の考え方の比喩

アムダールの法則:
料理の例で考えると、スープを作る過程において、材料を切る作業は並列化できますが、スープを煮込む作業は並列化できません。そのため、いくら多くの人が材料を切る作業をしても、スープを煮込む時間（直列部分）が全体の時間を制限します。
グスタフソンの法則:
同じく料理の例で、並列化できる作業の量を増やし、全体的に料理を作る量を増やしていくと、並列化の効果を最大限に発揮できるという考え方です。つまり、より多くの人数でより多くの料理を作ることで、全体の効率を上げられます。

法則の限界

グスタフソンの法則は、並列計算の可能性を示す一方で、以下のような限界も持ち合わせています。

本質的に大規模データを持たない問題:
一部の問題は、データの性質上、大規模にスケールすることが難しい場合があります。
非線形アルゴリズム:
アルゴリズムによっては、並列化によって得られる速度向上効果が限定的な場合があります。

まとめ

グスタフソンの法則は、並列計算の可能性を追求する上で、重要な指針となる法則です。アムダールの法則と合わせて理解することで、より効率的な並列計算システムの開発に役立つでしょう。この法則は、大規模な問題を効率的に解決するための並列計算アプローチの可能性を示唆しています。並列コンピューティングの発展と同時に、グスタフソンの法則が示すスケーラビリティの重要性は、今後ますます高まっていくと考えられます。

関連項目

アムダールの法則

外部リンク

Reevaluating Amdahl's Law - ジョン・グスタフソンが自身の法則を初めて発表した論文
Type Architectures, Shared Memory, and The Corrolary of Modest Potential

もう一度検索