High Precision Integer Addition, Subtraction and Multiplication with a Graphics Processing Unit
High Precision Integer Addition, Subtraction and Multiplication with a Graphics Processing Unit
复制标题
使用图形处理单元进行高精度整数加法、减法和乘法
DOI：
10.1142/s0129626410000259
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
C. Weems
中科院分区：
文献类型：
--
作者：
Niall Emmart;C. Weems
在本文中，我们评估了使用NVIDIA图形处理单元（GPU）加速高精度整数乘法，加法和减法的潜力。报告的典型GPU的峰向量性能似乎为加速这种计算提供了良好的潜力。由于片上内存的局限性，内核的高成本以及对并行性支持的性质的性质，我们使用了混合算法方法来获得繁殖方面的良好性能。在GPU本身上，我们将Strassen FFT算法适应32KB块的繁殖，而在CPU上，我们适应了Karatsuba分隔和串扰方法，以优化GPU的局部乘积应用，通过我们的Karatsuba实施，它们被视为“ Digits” 。即使采用这种方法，与在可比技术节点上使用64位CPU上使用GMP软件包相比，其性能的最多只有三倍的性能。我们的加法和减法实施实现了八倍的改进。我们确定了限制性能的问题，并讨论了计划进步在GPU体系结构中的可能影响。
In this paper we evaluate the potential for using an NVIDIA graphics processing unit (GPU) to accelerate high precision integer multiplication, addition, and subtraction. The reported peak vector performance for a typical GPU appears to offer good potential for accelerating such a computation. Because of limitations in the on-chip memory, the high cost of kernel launches, and the nature of the architecture's support for parallelism, we used a hybrid algorithmic approach to obtain good performance on multiplication. On the GPU itself we adapt the Strassen FFT algorithm to multiply 32KB chunks, while on the CPU we adapt the Karatsuba divide-and-conquer approach to optimize application of the GPU's partial multiplies, which are viewed as "digits" by our implementation of Karatsuba. Even with this approach, the result is at best a factor of three increase in performance, compared with using the GMP package on a 64-bit CPU at a comparable technology node. Our implementations of addition and subtraction achieve up to a factor of eight improvement. We identify the issues that limit performance and discuss the likely impact of planned advances in GPU architecture.