アムダールの法則

performance

並行処理を書いているときに見つけたのでまとめ。

アムダールの法則とは、

並列性を追加して得られるスピードアップは、プログラムがどの程度並列に実行されるかに依存する。

というもの。一般式は以下。

\displaystyle{ S(N)= \frac{1}{(1−P)+P/N} }
  • P: 並列化できる割合
  • N: N個のプロセッサ

以下のグラフだとparallel positionがP、横軸がN、縦軸がSとなる。

具体例

ある処理をマルチスレッドで並行化し、速度向上を目指したいとする。

並列化できる処理部分は全体の50%とし、スレッド数を増やすことで高速化したい場合、アムダールの法則によればたかだか8スレッド程度で高速化は限界を迎える。

適応例

以下のような場合はアムダールの法則が適応できる。

  • マルチスレッドによる速度向上率の予想
  • スケールアウトによるパフォーマンス向上率
  • マルチコアプロセッサーの性能速度予想

要所

P(並列化できる割合)を増やすことに務めると並列化の効果を得られやすい。

参考