基于CUDA的快速大整数乘法

计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (16): 221-224.

基于CUDA的快速大整数乘法

许亮1，王震2

1.湖南第一师范学院信息科学与工程系，长沙 410205
2.湖南大学嵌入式与网络计算湖南省重点实验室，长沙 410082

出版日期:2013-08-15 发布日期:2013-08-15

Fast large integer multiplication based on CUDA

XU Liang1, WANG Zhen2

1.Department of Information Science & Engineering, Hunan First Normal University, Changsha 410205, China
2.Key Laboratory for Embedded and Network Computing of Hunan Province, Hunan University, Changsha 410082, China

Online:2013-08-15 Published:2013-08-15

摘要/Abstract

摘要： 针对快速傅里叶变换下的快速大整数乘法，给出了一种基于CUDA架构的GPU并行化加速的实现方法。通过分析整数快速乘法中的每一步骤，分别给出各步骤的并行化实现方法，并采用数据压缩等策略，对算法进行优化。实验表明该方法有效地提高了算法效率，随着数据规模的增长，可获得18倍以上的加速比。

关键词: 图形处理单元, 统一计算设备架构, 大整数乘法, 快速傅里叶变换

Abstract: Concerning the fast large integer multiplication based on fast Fourier transform, a GPU parallel method based on CUDA architecture is proposed. By each steps in the fast large integer multiplication, parallel implementation is given respectively. Then the algorithm is optimized through data compression. Experiments result show that the method improves the efficiency of the algorithm, and can reach more than 18 times speedup ratio with the increase of data scale.

Key words: Graphics Processor Units（GPU）, Compute Unified Device Architecture（CUDA）, large integer multiplication, Fast Fourier Transformation（FFT）

许亮1，王震2. 基于CUDA的快速大整数乘法[J]. 计算机工程与应用, 2013, 49(16): 221-224.

XU Liang1, WANG Zhen2. Fast large integer multiplication based on CUDA[J]. Computer Engineering and Applications, 2013, 49(16): 221-224.

[1]	张宾，张正强，王洪凯. 基于GPU加速的锥束CT重建算法研究[J]. 计算机工程与应用, 2019, 55(4): 208-213.
[2]	刘锦怡1，张乐1，2，胡海波1，2，朱贺3. 强鲁棒性的可穿戴传感器的人体动作识别方法[J]. 计算机工程与应用, 2017, 53(4): 176-183.
[3]	彭自然1，王国军1，2. 基于MPSoC平台小波变换并行算法研究[J]. 计算机工程与应用, 2017, 53(4): 33-38.
[4]	李玲，罗正平，杨天奇. 能量图空间分解法和DSW相结合的步态识别[J]. 计算机工程与应用, 2016, 52(3): 127-132.
[5]	李正夫1，2，王希诚3，李克秋1，姚翔3，董悦丽2. CUDA平台下信息熵多种群遗传算法设计[J]. 计算机工程与应用, 2016, 52(1): 12-16.
[6]	仲济源，梅魁志，温哲西. GIST特征提取的异构并发流计算实现[J]. 计算机工程与应用, 2015, 51(6): 139-144.
[7]	董丽丽，董玮，张翔. 利用CUDA提高内存数据聚类效能的研究[J]. 计算机工程与应用, 2015, 51(22): 243-251.
[8]	张烈1，冯燕1，李琳2. 频域选择性压缩采样的数字预失真计算优化[J]. 计算机工程与应用, 2015, 51(20): 102-106.
[9]	褚晶辉，王亚琦，吕卫. 基于ParaViewWeb架构的GPU高性能运算实现[J]. 计算机工程与应用, 2015, 51(11): 150-153.
[10]	赵家威，房九龄，苏明. Legendre序列快速生成的CUDA实现[J]. 计算机工程与应用, 2014, 50(8): 66-71.
[11]	陈华，史悦戎. 基于GPU的重启PGMRES并行算法研究[J]. 计算机工程与应用, 2014, 50(7): 35-40.
[12]	王冬格，周晓方. 改进的高基CORDIC算法及其在FFT中的应用[J]. 计算机工程与应用, 2014, 50(7): 41-45.
[13]	蔡云龙，肖素梅，齐龙. 基于GPU的加锁并行化非结构网格生成方法研究[J]. 计算机工程与应用, 2014, 50(6): 56-60.
[14]	田旺兰，李加升. 改进运用深度置信网络的语音端点检测方法[J]. 计算机工程与应用, 2014, 50(20): 207-210.
[15]	毛庆，李顺东. 快速傅里叶变换乘法的性能研究[J]. 计算机工程与应用, 2014, 50(19): 16-19.