Performance Analysis of the Parallel Karatsuba Multiplication Algorithm for Distributed Memory Architectures

✍ Scribed by GIOVANNI CESARI; ROMAN MAEDER

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 447 KB
• Volume: 21
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1996.0026

✦ Synopsis

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 log 2 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.