大整数乘法Sch?nhage-Strassen算法的多核并行化研究

作者：赵玉文; 刘芳芳; 蒋丽娟; 杨超^*

来源：软件学报, 2018, 29(12): 3604-3613.

DOI：10.13328/j.cnki.jos.005308

• 大整数乘法
• Sch?nhage-Strassen算法(SSA)
• 傅里叶变换
• FFT
• 多核并行

基于数论转换的Sch?nhage-Strassen算法(简称SSA)是目前实际应用中使用较多、速度较快的大整数乘法算法之一.首先对SSA算法原理进行了详细分析,然后从细粒度的角度对SSA算法在多核平台进行比较细致的并行优化.基于大整数运算开源库GMP实现了SSA算法并行化方案,并在Intel X86平台进行了验证和测试.经测试,8线程时的最大加速比可达到6.59,平均加速比6.41.在浪潮TS850服务器对并行方案的扩展性进行测试,实验结果表明:SSA算法并行方案具有良好的扩展性,最大加速比可达21.42.

• 单位
  中国科学院软件研究所; 北京大学; 计算机科学国家重点实验室