Efficient Parallel GCD Algorithms for Multicore Shared Memory Architectures
Gihan Tharaka Pathirana, Sittampalam Sotheeswaran, Nagulan Ratnarajah · 2020
The greatest common divisor (GCD) is used for numerous applications in number theory, modular arithmetic, encryption algorithms such as RSA, random number generation, and solving linear Diophantine equations. High-performance algorithms, which are efficiently and accurately find the GCD of two integers and n (>2) integers, are needed in the modern world for many applications in science and engineering. Parallel hardware and parallel programming solve such emerging challenges that are not possible in a serial world. Modern desktop and laptop computers are equipped with multicore processors with shared memory architecture. In this paper, we develop novel efficient parallel n integers GCD algorithms for multicore shared memory architecture. The brute force, divide-and-conquer, linear recursive and finding minimum first techniques are adopted in our novel algorithms to reduce the size and the complexity of the n integers GCD problem. Various working models of OpenMP, such as the thread-centric, loop-centric and task-centric models are utilized, which promised a more natural way of exploiting and expressing regular and irregular algorithms. A comprehensive performance analysis applies to prove the efficiency of the proposed algorithms.