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

介绍

Amdahl’s law(阿姆达尔定律) 由计算机科学家 Gene Amdahl 在 1967 年提出,旨在用公式描述在并行计算中,多核处理器理论上能够提高多少倍速度,公式如下:
S=11a+an
S 为 speedup,代表全局加速倍速(原来总时间/ 加速后总时间),a 为并行计算所占比例(可以并行计算代码量 / 总代码量),n 为并行节点处理个数,可以理解为 CPU 的核心数,这里先简要介绍下,后面会详细说明并且推导。

前置说明

Fraction enhanced

Fraction enhanced 顾名思义是部分提高。例如我的程序总共有 100 行代码,其中 50 行是可以通过并行计算的,那么这 50 行代码就是 Fraction enhanced 。但是实际上 Fraction enhanced 是一个比例数值,是并行计算代码 / 总代码量
Fraction enhanced=parallel codetotal code
例如上面的例子,Fraction enhanced=50/100=0.5 ,由此我们可以发现,Fraction enhanced 的值永远小于 1

Speedup enhanced

Speedup enhanced=Old execution timeNew execution time

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

带入 Amdahl’s law

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

Speedup enhanced 为什么可以代替 n

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

带入后公示得: S=Old total execution timeNew total execution time=11Fractionenhanced+Fractionenhanced/Speedupenhanced

证明

  • S 为我们所需要的结果,全局提速倍速
  • Old total execution time (原来系统执行总时间)为 T
  • New total execution time (加速后系统执行总时间)为 T
  • 系统中并行代码块(指能够通过并行计算加速的代码块)原来执行时间为 t
  • 系统中并行代码块(指能够通过并行计算加速的代码块)加速后执行时间为 t
  • 系统中串行代码块(指不能通过并行计算加速的代码块)执行时间为 tn
  • Fractionenhancedf
  • Speedupenhanceds

S=TTT=tn+tT=tn+tf=tT=ttn+ts=ttfs=ttn+t÷tt=ttn+t

带入公式得: S=TT=tn+ttn+t=1(tn+t)/(tn+t)=11ttn+t+ttn+t=11f+fs=11Fractionenhanced+Fractionenhanced/Speedupenhanced=11a+an

证明完毕!

总结

让我们回到最初的公式
S=11a+an
a 为并行计算所占比例,n 为并行节点处理个数。当 a=0 时(即只有串行没有并行),无论 n 为多少,加速比 S 均为 1。当 n+ ,当 cpu 核心数无限增多的时候,极限加速比 S=1/(1a) 。例如若并行代码有 75%,极限加速比不能超出 4。

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

参考资料

阿姆达尔定律

Computer Organization | Amdahl’s law and its proof

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

原创文章,作者:Smith,如若转载,请注明出处:https://www.inlighting.org/archives/amdahls-law-and-its-proof

打赏 微信扫一扫 微信扫一扫
SmithSmith
上一篇 2020年10月13日 下午1:13
下一篇 2021年6月10日 下午1:50

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注


评论列表(2条)

  • Genson
    Genson 2023年11月6日 下午12:02

    你好,请教一下,文章中的公式是如何正常显示的?