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

• 作者: 刘芳芳 杨超 蒋丽娟 赵玉文
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 大整数乘法 Sch(o)nhage-Strassen算法(SSA) 傅里叶变换 FFT 多核并行
• 年，卷（期）: 2018,（12）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 3604-3613
• 页数: 10页
• 分类号: TP301
• 字数: 6112字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005308

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘芳芳	中国科学院软件研究所并行软件与计算科学实验室	13	88	4.0	9.0
2	蒋丽娟	中国科学院软件研究所并行软件与计算科学实验室	3	7	2.0	2.0
3	赵玉文	中国科学院软件研究所并行软件与计算科学实验室	4	123	2.0	4.0