integer-arithmetic - 并行添加两个整数

Question

假设您在两个数组 a,b 中给出了 2 个 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 条消息作为结果和 p-1 条消息作为进位。所以消息复杂度仍然是O(p). 时间复杂度将是O(p + ceil(n/p))因为最后一个处理器必须等到p-2其前任处理器决定转发两个结果中的哪一个。如果您假设 n 位可以均匀地分布在 p 个处理器之间（即 n 是 p 的倍数），那么您建议的时间复杂度就可以了O(p + n/p)。

这种通过推测计算两个可能结果的相加方法与进位选择加法器的工作方式非常相似。