Amdahl’s law(阿姆达尔定律)公式推导与思考

1. 介绍

Amdahl’s law(阿姆达尔定律) 由计算机科学家 Gene Amdahl 在 1967 年提出,旨在用公式描述在并行计算中,多核处理器理论上能够提高多少倍速度,公式如下:

$$
S=\frac{1}{1-a+\frac{a}{n}}
$$

$S$ 为 speedup,代表全局加速倍速(原来总时间/ 加速后总时间),$a$ 为并行计算所占比例(可以并行计算代码量 / 总代码量),$n$ 为并行节点处理个数,可以理解为 CPU 的核心数,这里先简要介绍下,后面会详细说明并且推导。

2. 前置说明

2.1 Fraction enhanced

Fraction enhanced 顾名思义是部分提高。例如我的程序总共有 100 行代码,其中 50 行是可以通过并行计算的,那么这 50 行代码就是 Fraction enhanced 。但是实际上 Fraction enhanced 是一个比例数值,是并行计算代码 / 总代码量

$$
Fraction\ enhanced=\frac{parallel\ code}{total\ code}
$$

例如上面的例子,$Fraction\ enhanced = 50/100=0.5$ ,由此我们可以发现,Fraction enhanced 的值永远小于 1

2.2 Speedup enhanced

$$
Speedup\ enhanced=\frac{Old\ execution\ time}{New\ execution\ time}
$$

如上面公式所得,Speedup enhanced 等于 原有运行时间 / 并行计算加速后的时间 。例如系统原来串行计算需要 6 秒,加速后只需要 3 秒,那么 $Speed\ enhanced=6/3=2$ 。由此可知 Speedup enhanced 的值永远大于 1

2.3 带入 Amdahl’s law

我们分别把 Fraction enhancedSpeedup enhanced 带入 Amdahl’s lawFraction enhanced 对应公式中的 $a$ ,即并行计算所占比例。Speedup enhanced 对应 $n$ ,即并行节点处理个数。

Speedup enhanced 为什么可以代替 $n$ ?

这里大家可能有一点疑问,Speedup enhanced 明明是 未加速前时间 / 加速后的时间,为什么就可以代表并行节点处理个数。在理论上,单核处理器处理一个任务需要 100 秒,那么双核处理它应该需要 50 秒。时间上它提速了 2 倍, cpu 个数上它也提升了 2 倍,故两个可以替换。

$$
\begin{aligned} Speedup\ enhanced&=\frac{Old\ execution\ time}{New\ execution\ time} \\ &=\frac{100}{50}=2 \\ &=\frac{New\ cpu\ cores}{Old\ cpu\ cores} \\ &=\frac{2}{1}=2 \end{aligned}
$$

带入后公示得:

$$
\begin{aligned} S&=\frac{Old\ total\ execution\ time}{New\ total\ execution\ time}\\ &=\frac{1}{{1-Fraction_{enhanced}}+Fraction_{enhanced}/Speedup_{enhanced}}\\ \end{aligned}
$$

3. 证明

  • $S$ 为我们所需要的结果,全局提速倍速
  • $Old\ total\ execution\ time$ (原来系统执行总时间)为 $T$
  • $New\ total\ execution\ time$ (加速后系统执行总时间)为 $T’$
  • 系统中并行代码块(指能够通过并行计算加速的代码块)原来执行时间为 $t$
  • 系统中并行代码块(指能够通过并行计算加速的代码块)加速后执行时间为 $t’$
  • 系统中串行代码块(指不能通过并行计算加速的代码块)执行时间为 $t_n$
  • $Fraction_{enhanced}$ 为 $f’$
  • $Speedup_{enhanced}$ 为 $s’$

$$
S=\frac{T}{T’}
$$

$$
T=t_n+t
$$

$$
T’=t_n+t’
$$

$$
f’ = \frac{t}{T}=\frac{t}{t_n+t}
$$

$$
s’=\frac{t}{t’}
$$

$$
\frac{f’}{s’}=\frac{t}{t_n+t} \div \frac{t}{t’}=\frac{t’}{t_n+t}
$$

带入公式得:

$$
\begin{aligned} S&=\frac{T}{T’}\\ &=\frac{t_n+t}{t_n+t’}\\ &=\frac{1}{(t_n+t’)/(t_n+t)}\\ &=\frac{1}{1-\frac{t}{t_n+t}+\frac{t’}{t_n+t}}\\ &=\frac{1}{1-f’+\frac{f’}{s’}}\\ &=\frac{1}{{1-Fraction_{enhanced}}+Fraction_{enhanced}/Speedup_{enhanced}}\\ &=\frac{1}{1-a+\frac{a}{n}} \end{aligned}
$$

证明完毕!

4. 总结

让我们回到最初的公式

$$
S=\frac{1}{1-a+\frac{a}{n}}
$$

$a$ 为并行计算所占比例,$n$ 为并行节点处理个数。当 $a=0$ 时(即只有串行没有并行),无论 $n$ 为多少,加速比 $S$ 均为 1。当 $n \rightarrow +\infty$ ,当 cpu 核心数无限增多的时候,极限加速比 $S=1/(1-a)$ 。例如若并行代码有 75%,极限加速比不能超出 4。

由此我们可知,在并行系统中一味的增加运算资源,并不能永远成倍的提升系统整体性能。

5. 参考资料

阿姆达尔定律

Computer Organization | Amdahl’s law and its proof

理解性能提升By阿姆达尔定律(Amdahl’s law)

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇