|
グスタフソンの法則（英: Gustafson's law、Gustafson-Barsis' law としても知られる）は、計算機工学における法則で、「十分に大きな規模の問題は、効率的に並列化して解くことができる」事を示すものである。グスタフソンの法則は、並列化によってプログラムが高速化できる限界を示したアムダールの法則と密接に関係している。本法則は、ジョン・グスタフソンによって1988年に初めて示された。 ''P'' がプロセッサの数であり、''S'' がSpeedup、''α'' がプロセスの並列化できない部分であるとすると、下記が成立する。 :''S''(''P'') = ''P'' − ''α'' · (''P'' − 1) グスタフソンの法則は、計算機の規模が大きくなると利用可能な計算能力を使い切るほど性能がスケールしないというアムダールの法則に欠けていた部分に対応するものである。グスタフソンの法則では、問題の規模が固定である、また並列プロセッサ上の計算の負荷が一定であるという仮定を取り除き、代わりに固定時間の概念を提唱し、これにより高速化がスケールすることを示した。 アムダールの法則は、作業負荷や問題の規模が一定であることに基づいている。すなわち、プログラムの直列的な部分は、計算機の規模（すなわちプロセッサ数）によらず変化しない。しかし、並列化可能な部分は n 個のプロセッサに平等に分配可能であるとする。アムダールの法則の影響により、研究機関は並列コンパイラを開発し、問題の直列的な部分を減らし、並列システム性能を上げようとするようになった。 ==グスタフソンの法則の実現== ''n'' を問題の大きさを示す量とする。 並列コンピュータ上でのプログラムの実行は、下記のように分解できる。 :''a''(''n'') + ''b''(''n'') = 1 ここで、''a'' は直列的な部分の割合で、''b'' は並列的な部分の割合である。ただしオーバーヘッドは無視する。 一方直列的なコンピュータでは ''p'' を並列化した際のプロセッサ数とすると、相対的な処理時間は ''a''(''n'') + ''p'' · ''b''(''n'') である。 すなわちSpeedupは、直列的な場合の ''a''(''n'') + ''b''(''n'') = 1 に対して並列化した場合には (''a''(''n'') + ''p'' · ''b''(''n'')) であるから :''S'' = ''a''(''n'') + ''p'' · (1 − ''a''(''n'')) となる。ここで ''a''(''n'') は直列的な部分の割合を示す関数である。 直列的な関数 ''a''(''n'') が問題の大きさ ''n'' によって減少すると仮定すると、Speedupは、''n'' が無限に大きくなれば希望通り''p'' に到達する。 グスタフソンの法則は、一見するとアムダールの法則の限界から並列コンピューティングを救い出すことができるように見える。 この違いは、グスタフソンの法則は膨大な数の並列計算機を用いても直列的な部分に与える影響はなく、したがってその部分の大きさは一定とみなせると考えるのに対し、アムダールの法則はプロセッサの数が増えるにしたがって直列的な部分の影響が増加するという考え方から生まれている。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「グスタフソンの法則」の詳細全文を読む スポンサード リンク
|