并行添加两个整数

Question

假设您有两个无符号整数（在两个数组a，b中给出n个数字），并且您有p个处理器，每个处理器可以添加2个数字并计算进位（如果存在）。是否有可能在时间O（p + n/p）上计算a + b？我一直试图将输入分为每个（n/p）的p个区间，但我不知道如何处理进位。

Answer 1

我相信这是可能的。我会假设n >= p，并且您的p处理器被安排在一个无共享架构中，处理器通过消息传递进行通信。

如果你的数字还没有分布在p个处理器中，而是聚集在一个不参与计算的主处理器上，你只需分割a和b来创建p个连续数字的块，然后将它们发送给每个处理器。这需要消息复杂度O(p)。

然后，每个处理器计算其数字块的两个和，假设其将从其前身接收进位1，即具有下一个较低有效位数的块的处理器，并且另一个假设进位将为0.它还将计算其两种情况下每种情况下的传出运载量。计算时间复杂度为O(ceil(n/p))，因为每个处理器必须保存一个整数位数。

当然，具有最低有效位数的块的处理器只需要计算一个和。一旦它完成了计算，它就会将其所得数字的份额发送回主设备，并将其传出到携带下一个更高有效位数块的处理器。下一个处理器决定两个结果场景中的哪一个变为真，将合适的结果数字发送给主设备，并将其输出传送给下一个处理器。等等。

这将为结果和p-1消息携带进一步的p消息。所以消息的复杂性仍然是O(p)。时间复杂度将为O(p + ceil(n/p))，因为最后的处理器将不得不等待其前身的p-2决定要转发两个结果中的哪一个。如果你假设n个数字可以在p个处理器中均匀分布（即n是p的倍数），那么你的建议时间复杂度为O(p + n/p)就可以了。

这种通过推测计算两个可能结果进行相加的方法与Carry-select adder的工作方式非常相似。