algorithm - 如何确定最有效的并行加法算法？

Question

在问了另一个关于 MapReduce 算法的问题后，我开始思考如何确定使用并行处理得出 n 个值的总和的最有效方法。问题可以简化如下:

假设我有 n 个处理器，每个处理器都有一个整数。我想尽快确定整数的总和。

现在我可以让每个处理器 2,..,n 将其整数传递给处理器 1。然后处理器 1 依次将每个数字相加以产生结果。这意味着 n - 1 次数据传递，但这些都可以并行发生。接下来是 n - 1 个加法运算，按顺序发生。

或者，我可以让每个奇数编号的处理器将其整数传递给下一个偶数编号的处理器(为了论证，我们假设 n 是偶数)。然后，每个偶数编号的处理器并行执行一个加法运算，将自己的编号添加到刚刚传递给它的编号。然后我们最终得到 1/2 n 个整数相加。然后我们可以使用之前的方法来添加剩余的值。

当然，还有很多其他方法可以做到这一点。我如何确定哪个最有效？我怀疑这取决于加法运算与传递整数的相对成本(在现实生活中，想想 CPU 与网络速度)，并且可能还取决于 n 的大小。毕竟，如果 n 非常大，那么为了将 n 减半而增加一个额外的网络跃点可能是值得的，即使每次增加都相对便宜。

Answer 1

这与其说是一个答案，不如说是一个评论，但是那个小盒子太狭窄了......

定义最有效。您关心理论效率还是实践速度？

我认为您在问自己正确的问题，而且您似乎已经意识到，如果您有 100,000 个处理器，每个处理器都有 1 个整数，那么关键资源是通信速度而不是计算速度。对于您设计的以 N 处理器开始对 N 整数求和的任何方案，请记住，通信时间将不是由带宽(发送 1 个整数的时间)决定，而是由延迟(发送 0 大小消息的时间)。出于最实际的目的，我希望这个问题能够扼杀你的奇思妙想。

还有一个问题:整数从何而来？如果它们起源于一个进程(或)并分发给另一个 N-1，您几乎可以肯定，发送它们所浪费的时间比第一个进程(或)计算和。如果整数可能起源于每个处理器上运行的进程的结果，那么无论(低)效率如何，您都必须进行某种归约并支付通信成本。

在实践中，当 N 为比 p 大得多。要在您的并行计算机上计算出您的数字，没有什么可以替代实验。