処理の20%を並列化できないなら、並列数を増やしても全体の高速化は5倍が上限（アムダールの法則）
同じ量の仕事について、並列化できる割合をp、同じ性能の実行資源の数をNとすると、理想的な高速化率は1 / ((1−p) + p/N)。逐次部分の速さが変わらず、並列化の追加費用を無視するモデルである。
用語
- アムダールの法則
- 固定した仕事の一部だけを高速化したとき、全体の高速化が残りの部分で制限される関係。ここでは並列数を増やす場合に適用する。
- 逐次部分
- 同時に分担できず、順番に実行する必要がある部分。式の割合は高速化前の実行時間を基準にする。
- 高速化率
- 元の完了時間を変更後の完了時間で割った倍率。100秒から25秒なら4倍。
- オーバーヘッド
- 仕事を分割・配布・同期・回収するための追加費用。並列数を増やすほど大きくなることもある。
図と例
- 1並列: 100 s
- 2並列: 60 s
- 4並列: 40 s
- 10並列: 28 s
計算例：逐次20秒＋並列化可能80秒、分担の偏りと追加費用はないとする。1並列100秒、2並列60秒、4並列40秒、10並列28秒。10並列での高速化率は100/28≒3.57倍。並列化できる80%という割合を、全体が80倍速くなる意味に取り違えない。
実際のサービス・製品では
LLNL HPC
LLNLの並列計算入門は、アムダールの法則と、仕事全体の大きさを固定する強スケーリングを説明する。通信・同期などの費用も、並列プログラムの設計項目として扱っている。
資料を読む
解説
バッチのワーカー数やCPUコア数を増やす前に、1実行の時間を分解する。全件読み込み、共有ロック、最終集計などの逐次部分を測り、並列部分の増設と逐次部分の改善を比べる。この式は固定量の1仕事の完了時間の見積もりなので、独立した要求をさばくシステム全体のスループットへそのまま適用しない。
1台で100秒かかる処理のうち、20秒は順番に実行する必要があり、残り80秒だけを均等に分担できるとする。2並列なら20＋80/2＝60秒、10並列なら20＋80/10＝28秒になる。並列数をどれだけ増やしても最初の20秒は残るため、全体の高速化率は100/20＝5倍へ近づくだけで、有限の並列数では5倍に届かない。これがアムダールの法則で、割合はコードの行数でなく、元の実行時間で測る。実際には分割・通信・同期のオーバーヘッドや仕事量の偏りがあり、このモデルどおりに速くなるとは限らない。入力サイズを増やす比較や、キャッシュに収まるなど単体性能まで変わる条件は、この固定仕事量モデルと分けて考える。
トレードオフ
- 並列部分の実行資源を増やす
- 得るもの：分担できる仕事の完了を早められる
- 払うもの：逐次部分は残り、資源費用と通信・同期の負担が増える
- 逐次部分の処理やアルゴリズムを改善する
- 得るもの：並列数を増やしても残る時間を短くできる
- 払うもの：依存関係の見直しや実装変更が必要で、改善できる量も処理による
さらに学ぶ
チェック
1実行100秒のうち逐次20秒、残り80秒は均等に分担できる。同じ性能の4並列にし、追加費用と偏りを無視すると完了時間は？
- 20秒
- 25秒
- 40秒
解答と解説
40秒
逐次20秒は変わらず、並列部分だけが80/4＝20秒になるので合計40秒。25秒は全処理を均等に4分割した場合、20秒は並列部分の時間が0へ近づく極限である。今回の高速化率は100/40＝2.5倍。