并行计算定律:Amdahl定律与Gustafson定律的异同性讨论

首先,这两个定律都定义了加速比这个概念,我们定义T1是该程序在单核处理器上串行执行的时间,Tn是该程序在n核处理器上做过并行优化后执行的时间,那么加速比定义如下:

加速比\xlongequal{def}\frac{T_1}{T_n}

对于Amdahl定律来说:定义F为程序的串行比例,即F表示程序在串行执行状态下不可并行化的代码的执行时间占总代码的执行时间。

则推导如下:

T_n=T_1(F+\frac{1}{n}(1-F))

显然,这个式子分为两部分: T_1F 表示不可并行化的代码执行时间, T_1*\frac{1}{n}(1-F) 表示可并行化的代码在n核处理器上的执行时间。

进一步推导:

加速比\xlongequal{def}\frac{T_1}{T_n}=\frac{T_1}{T_1(F+\frac{1}{n}(1-F))}=\frac{1}{F+\frac{1}{n}(1-F)}

显然,根据这个公式可以得出以下结论:

1、若处理器数量趋近无穷,则 加速比\xlongequal[n\rightarrow\infty]{def}\frac{1}{F} ,这也就是并行化的优化比上限。

2、若处理器数量为1,则 加速比\xlongequal[n=1]{def}1 ,这也就是串行执行的状态。

而对于Gustafson定律而言:定义程序的串行部分的执行时间为a,而程序的并行部分在达到最大并行化的前提下的执行时间为b。

则串行化的执行时间为: T_n=a+nb ,其中n表示该任务分解到n核CPU上可以达到最大并行化。

这里定义串行比例 F=\frac{a}{a+b}

加速比=\frac{a+nb}{a+b}=\frac{a}{a+b}+\frac{nb}{a+b}=F+n-nF=n-F(n-1)

在这个公式中,我们似乎能得到一个结论:处理器的数量越多,则加速比越大,这似乎和Amdahl定律矛盾,但事实上,这里的n是受F限制的,或者说是受任务最大分解能力的限制,不可能达到无穷大,而且事实上,Amdahl定律和Gustafson定律是等价的。

我们根据Amdahl定律中的F定义并利用Gustafson定律中的符号可知: F=\frac{a}{a+nb}

则我们将该式代入Amdahl定律原式:

\frac{1}{F+\frac{1}{n}(1-F)}=\frac{1}{\frac{a}{a+nb}+\frac{1}{n}(1-\frac{a}{a+nb})}
=\frac{(a+nb)n}{an+(a+nb)(a-\frac{a}{a+nb})}
=\frac{(a+nb)n}{a+a+nb-a}
=\frac{(a+nb)n}{(a+b)n}
=\frac{a+nb}{a+b}

这显然就是Gustafson推导时一开始的形式,因此这两个定律实际上是等价的。
可以观察到:当程序完全不可并行化时,两个公式中的F为0,如果可完全并行化,则F都为1,在这种极端情况下,两公式的结果都完全一致。

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据