Amdahl’s law (阿姆达尔定律)的演化和思考

G.M.Amdahl在1967年提出了Amdahl’s law,针对并行处理的scalability给出了一个模型,指出使用并行处理的提速由问题的可并行的部分所决定。这个模型为并行计算系统的设计者提供了指导。

其形式如下:

f为问题中可被并行处理的部分的比例,m为并行处理机的数量,Speedup为并行后相比串行时的提速。

Amdahl’s law表明在问题的可并行部分不大时,增加处理机的数量并不能显著地加快解决问题的时间。这让计算机界产生了悲观的情绪,有人认为搞多处理器的机器没什么前途。但是,Amdahl’s law忽略了一些重要的事实。Amdahl’s law是一个fixed-size model,就是要解决的问题的大小是固定的,可并行化的比例是固定的。而在实际中,我们不会用1000个处理机来处理一个小问题,当我们的计算能力的总和增加之后,可以也应该去解决更大的问题。当问题更大的时候,通常情况下,这个问题也有更大的可能被分为可并行化的小问题(或者说处理多个相互独立的问题),也就意味着f更大(更接近1),能得到更大的Speedup。

直到1988年,Gustafson提出了一个fixed-time model,也即Gustafson’s Law,人们对重拾对大规模并行计算的信心。Gustafson’s Law可表示为以下公式:

对一个在单处理机上的工作w,我们将其扩大到m个核上,scaled workload为w’=(1-f)w+fmw。对在串行条件下对w’的处理时间比上在并行条件下对w’的处理时间即为Speedup。在这个模型中,问题的规模是可以被扩大(scale)的。从这个公式可以看到,f固定时,speedup显线性增长。

在1990年,Sun and Ni提出了memory-bounded model,即Sun and Ni’s law。形式如下:

在这个模型下,workload被scale的方式不同,workload跟随着memory的增长而以某种方式增加(G(n))。在这个模型里,Speedup也随处理机的数量的增长而线性增长,而且比Gustafson’s Law的增长情况更乐观。

其实,这几个模型其实在本质上是一致的,并没有冲突,那为什么Speedup会有那么大的不同呢?这是因为处理机的使用率。当workload被scale,而不是fix时,增加的处理机就会有事可做,保持一个比较高的使用率。也就是这些computing capacity没有被浪费掉。如果没有被浪费掉,这些computing capacity就在一定的时间多完成了一些工作,完成整个工作的时间就缩短了。所以,Speedup就变大了。

结论是,多搞些处理机是没错的,但是要有具有好的scalability的系统支持,以提高处理机的使用率。

For more about Amdahl’s law, visit

http://en.wikipedia.org/wiki/Amdahl’s_law

1 Comment Amdahl’s law (阿姆达尔定律)的演化和思考

  1. Pingback: [转]Amdahl’s law (阿姆达尔定律)的演化和思考 | 旁门左道

发表评论

电子邮件地址不会被公开。 必填项已用*标注