并行与串行的效率和加速

Question

目前,我正在读一本研究,这是我教授在课堂上发表的指南.学习指南不是作业,只是知道在考试中会发生什么.我已经完成了除1个问题之外的所有问题,希望有人可以帮助我.

这是一个问题:假设Tserial = n和Tparallel = n/p + log2(p),其中时间以毫秒为单位,p是进程数.如果我们将p增加k倍,找到一个公式,我们需要增加多少n才能保持恒定的效率.如果我们将进程数量从8增加到16,我们应该增加多少？并行程序是否可扩展？

任何帮助理解这一点将不胜感激.

Answer 1

无论是评论和你解决恒定的并行计算时间的第一个答案的帮助,但是这是不是解决了恒定的效率有点不同.

如上所述,并行效率的定义是您使用多个处理器的效率.100%的效率意味着你使用p处理器获得了加速的因素; 所以效率是根据每个处理器的加速来定义的:

所以现在你要考虑恒定的效率,如果你被一个因子k和问题的规模由因子k"增加处理器数量.

让我们首先做这个没有涉及log(p)的"并行开销"术语:

例如,效率永远是1,所以你改变处理器的数量,你不需要做任何的问题大小.

但是因为有一些开销,为了提高效率,你需要在扩展时解决更大的问题.随着开销期限,你得到

让我们看看这里的渐近 - 如果你已经处于无限数量的处理器,那么你的效率已经达到零(因为每个处理器的工作量为零,但是无限的开销),所以你可以保持问题大小不变; 效率将保持不变.另一方面,您永远无法将问题大小增加到足以重新获得p = 1时的并行效率; 这是100%,你所做的任何事情都必然会因为开销而减少.

另请注意,增加问题大小所需的数量总是至少比增加处理器数量的因素多一点.

在您正在查看的特定情况下,p = 8,k = 2,您需要将问题大小增加2 + 2/3.

Answer 2

希望这项工作是正确的。

例如，如果 Tserial = 10ms，在理想情况下（效率为 100%），如果您使用 2 个进程进行并行处理，则 Tparallel（理想）为 10ms/2 = 5ms

不幸的是，任何并行处理都会产生处理开销来管理分布在处理器之间的工作。

在这种情况下，管理开销所需时间的公式为 log2(p)。因此，如果您有 2 个处理器且 Tserial = 10ms，则 Tparallel 变为 5ms + log2(2) = 6ms

使用上面的例子，我们假设“恒定效率”意味着如果我们将 p 增加 k 倍，我们需要增加 Tserial 即 n 多少才能使 Tparallel 仍然是 6ms

设 a = 增加 n 的因子

n/p + log2(p) = na/pk + log2(pk)

n/p + log2(p) = na/pk + log2(p) + log2(k)

n/p = na/pk + log2(k)

nk - na = pk log2(k)

ka = (pk log2(k)) / n

a = k - [(pk log2(k)) / n]

如果 p = 8 且 k = 2

a = 2 - [(16 log2(2)) / n] a = 2 - (16/n)

在这种情况下，并行程序是可扩展的，因为如果处理器数量加倍，它可以处理几乎双倍的工作负载。提供 n >> 16