GPU implementation of arithmetic for very large integers

Abstract

Arithmetic operations on very large integers are used in many applications such as computer algebra, computational number theory and public key cryptography. A drawback is that most computers are typically built with a word size of 32 or 64 bits, which means that a machine register can only hold integers up to a maximum value of 2^64-1 for unsigned numbers. A solution is to use multi-precision arithmetic libraries, which allows numbers of any size. However, increasing the size of the numbers, increases the amount of work required to perform arithmetic on them, thus CPUs may struggle to keep up with the complexity of these computations. Graphics Processing Units (GPUs) can be used to offload some of the work from the CPU, and have been found useful in high-performance computing due to their massively parallel architecture of hundreds to thousands of arithmetic units. In this project, a parallel version of the addition, subtraction and multiplication operations for large numbers were implemented on a GPU. The addition was implemented using the prefix parallel technique which is used on a smaller scale in the carry-lookahead adder. This technique offers greater efficiency when executed on a large number of processors. For the multiplication, a warp-synchronous approach was adopted, taking advantage of how the thread grouping is done in the GPU. For multiplications of even larger numbers, the Karatsuba algorithm was chosen. The parallel implementation was tested on an NVIDIA GeForce GTX 1050 and compared with the GNU Multiple Precision Library, which runs on a CPU. For numbers of 2^30 bits, a speed-up of 1.7 was achieved for the addition operation. Furthermore, the multiplication operation achieved up to 2.6 speed-up for 1024-bit numbers when fully utilizing the GPU.