# グスタフソンの法則 ## 定義 グスタフソンの法則(Gustafson's law)は、プロセッサ数 N に合わせて問題規模を拡大し、並列システム上の実行時間を一定に保つ設定での速度向上(拡大速度向上、scaled speedup)を与える式である。並列システム上で逐次部分に s、並列部分に p を費やす(s + p = 1)とき、同じ仕事を逐次機で行う時間は s + p×N なので、速度向上は N + (1 - N)×s となる。傾き 1 - N の直線であり、[[アムダールの法則]]が問題規模固定で与える 1/(s + p/N) よりも逐次割合 s に対して緩やかに低下する。式は E. Barsis(Sandia)の示唆による。(Source: [[@1988__CACM__Reevaluating Amdahl's law]]) 前提は、s を構成する要素(ベクトル起動、プログラムのロード、逐次のボトルネック、入出力)が問題規模に伸びず、並列部分だけが問題規模とともに線形に伸びることである。Sandia の 3 アプリケーションでは 1024 プロセッサで並列部分が 1023.9965〜1023.9969 倍に拡大し、1016〜1021 倍の速度向上が実測された。(Source: [[@1988__CACM__Reevaluating Amdahl's law]]) ## 未解決の問い - s が問題規模に対して一定という第一近似は、通信や入出力が規模とともに増える場合にどこまで成り立つか。 ## 未編纂の観察 ## 関連 - 概念: [[アムダールの法則]] / [[強スケーリングと弱スケーリング]] - ソース: [[@1988__CACM__Reevaluating Amdahl's law]] - エンティティ: [[John L. Gustafson]] ## 出典 - [[@1988__CACM__Reevaluating Amdahl's law]](拡大速度向上の式と実測)