Adding two integers parallely

Question

Suppose you have 2 unsigned integers of n digits given in two arrays a,b and you have p processors where each can add 2 digits and compute the carry if exists. Is it possible to compute a+b in time O(p+n/p)? I've been trying to divide the input to p intervals of (n/p) each but I don't know how to handle the carry.

Answer 1

I believe it is possible. I'm gonna assume n >= p and that your p processors are arranged in a shared-nothing architecture where the processors communicate via message passing.

If your digits aren't already distributed among the p processors but gathered at one master processor not taking part in the computation, you just split up a and b to create p blocks of contiguous digits, each, and send them to each of the processors. This takes message complexity O(p).

Then, each processor computes two sums for its block of digits, one sum under the assumption that it will receive carry 1 from its predecessor i.e. the processor that has the next block of less significant digits and the other assuming that the carry will be 0. It will also calculate its outgoing carry for each of the two scenarios. The computation is of time complexity O(ceil(n/p)), since each processor must hold an integral number of digits.

Of course, the processor that has the block of least significant digits will only have to compute one sum. As soon as it has done its computation, it sends its share of resulting digits back to the master and its outgoing carry to the processor holding the next block of more significant digits. The next processor decides upon which of the two result scenario has become true, sends the appropriate result digits to the master and its outgoing carry to the next processor. And so on.

This will take an additional p messages for the results and p-1 messages for the carries. So message complexity is still O(p). Time complexity will be O(p + ceil(n/p)) since the last processor will have to wait until p-2 of its predecessors have decided which of the two results to forward. If you assume that the n digits can be evenly distributed among the p processors (i.e. n is a multiple of p), you are fine with your proposed time complexity O(p + n/p).

This method of adding with calculating two possible results speculatively is very similar to how a Carry-select adder works.