HIGH PRECISION INTEGER ADDITION, SUBTRACTION AND MULTIPLICATION WITH A GRAPHICS PROCESSING UNIT

摘要

In this paper we evaluate the potential for using an NVIDIA graphics processing unitn(GPU) to accelerate high precision integer multiplication, addition, and subtraction. Thenreported peak vector performance for a typical GPU appears to offer good potential fornaccelerating such a computation. Because of limitations in the on-chip memory, the highncost of kernel launches, and the nature of the architecture’s support for parallelism, wenused a hybrid algorithmic approach to obtain good performance on multiplication. Onnthe GPU itself we adapt the Strassen FFT algorithm to multiply 32KB chunks, while onnthe CPU we adapt the Karatsuba divide-and-conquer approach to optimize applicationnof the GPU’s partial multiplies, which are viewed as “digits” by our implementation ofnKaratsuba. Even with this approach, the result is at best a factor of three increase innperformance, compared with using the GMP package on a 64-bit CPU at a comparablentechnology node. Our implementations of addition and subtraction achieve up to a factornof eight improvement. We identify the issues that limit performance and discuss the likelynimpact of planned advances in GPU architecture.