performance - 并行与串行的效率和加速

Question

目前，我正在阅读我的教授在类里面分发的指南。学习指南不是作业，只是了解考试内容。我已经完成了除 1 个问题之外的所有问题，希望有人能帮助我。

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

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

Answer 1

评论和第一个答案都可以帮助您解决恒定的并行计算时间，但这与解决恒定的效率略有不同。

如上所述，并行效率取决于您如何有效地利用多个处理器。 100% 的效率意味着您从使用 p 个处理器中获得了 p 倍的加速；所以效率是根据每个处理器的加速来定义的:

因此，如果您将处理器数量增加一个因子 k 并将问题大小增加一个因子 k'，那么现在您要考虑恒定效率。

让我们首先在没有涉及 log(p) 的“并行开销”项的情况下执行此操作:

例如，效率始终为 1，因此当您改变处理器数量时，您不需要对问题的大小做任何事情。

但是因为有一些开销，为了保持效率，您需要在扩展时解决更大的问题。有了开销项，你得到

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

另请注意，您必须增加问题大小的数量总是至少比您增加处理器数量的因素多一点。

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