並行添加兩個整數

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的工作方式非常相似。