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。

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