基于CUDA的快速大整数乘法

摘要

针对快速傅里叶变换下的快速大整数乘法，给出了一种基于CUDA架构的GPU并行化加速的实现方法。通过分析整数快速乘法中的每一步骤，分别给出各步骤的并行化实现方法，并采用数据压缩等策略，对算法进行优化。实验表明该方法有效地提高了算法效率，随着数据规模的增长，可获得18倍以上的加速比。%Concerning the fast large integer multiplication based on fast Fourier transform, a GPU parallel method based on CU-DA 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.