Performance analysis of the parallel Karatsuba multiplication algorithm for distributed memory architectures

We present three parallel implementations of the Karatsuba algorithm for long integer multiplication on a distributed memory architecture and discuss the experimental results obtained on a Paragon computer. The first two implementations have both time complexity O(n) on n(log2 3) processors, but present different behavior for inputs of practical size. The third algorithm has complexity O(n log(2) n) on n processors, offering therefore better asymptotic efficiency. A refinement of the asymptotic analysis for the important case of a constant number of processors takes into account sequential parts of the algorithm and communications overhead. It is shown that the theoretically best speed-up and efficiency can be obtained with two of the algorithms for sufficient problem size. The experimental results confirm the analysis. (C) 1996 Academic Press Limited