Gustafson 定律
Overview
Gustafson 定律(Gustafson’s law)阐述了数据并行带来的影响。Gustafson 定律是由 John L. Gustafson 在1988年提出的。是并行计算领域除了 Amdahl 定律之后又一个重要定律。
Introduction
Amdahl 定律有一个重要前提,就是处理的数据集大小是固定的,但是这在大数据计算的领域里,这个假设并不经常能达到,因为人们总是会为了在短时间内处理更多的数据,而为了达到目的,往往会在计算集群增加更多的处理器。
Gustafson 定律的提出,始于 Gustafson 实验室的一个实验,在一个拥有1024个处理器的计算机,观察到了超线性加速比,分别获得了1021x/1020x/1016x的加速比,如果按照 Amdahl 定律,1024核,早就在某处歇菜了,哪里来1000x以上的加速。
1021 for beam stress analysis using conjugate gradients, 1020 for baffled surface wave simulation using explicit finite differences, and 1016 for unstable fluid flow using flux-corrected transport.
现在看看这个下面这个图,可以理解一下,数据规模和处理器个数以及时间的关系。
解读一下这个图,为了达到随着数据规模 增大,所用到的处理器 也成倍增加。所以加速比,可以用相同时间处理的数据量来衡量,用下面的公式表示。
下面的公式,说明在一台机器里,串行代码的比例 ,其实就是串行代码运行的时间 和串行以及并行代码运行时间的和 的比值。
经过换元,加速比公式可以换成下面那种形式。
又知道并行代码所占的比例 是 和串行以及并行代码运行时间的和 的比值。
又来换元了,所以加速比的公式简化成下面的样子。
已知 是固定的,那么加速比 就会向 渐近。
Summary
Gustafson 认为,串行部分代码比例固定的前提加,加速比会随着处理器个数增加而增加。需要注意下图 表示串行代码的部分,可以见到,随着串行部分代码的增加,加速比越来越弱鸡。
所以 Gustafson 的意思就是说,如果你代码里少点串行的部分,你的代码可以在多核环境下起飞(当然也不是没有限制)。