首页 | 本学科首页   官方微博 | 高级检索  
     

大整数乘法Schönhage-Strassen算法的多核并行化研究
引用本文:赵玉文,刘芳芳,蒋丽娟,杨超.大整数乘法Schönhage-Strassen算法的多核并行化研究[J].软件学报,2018,29(12):3604-3613.
作者姓名:赵玉文  刘芳芳  蒋丽娟  杨超
作者单位:中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190,中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190,中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190,中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190;计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190;北京大学 数学科学学院, 北京 100871
基金项目:国家重点研发计划(2016YFB0200603);国家自然科学基金(91530323)
摘    要:基于数论转换的Schönhage-Strassen算法(简称SSA)是目前实际应用中使用较多、速度较快的大整数乘法算法之一.首先对SSA算法原理进行了详细分析,然后从细粒度的角度对SSA算法在多核平台进行比较细致的并行优化.基于大整数运算开源库GMP实现了SSA算法并行化方案,并在Intel X86平台进行了验证和测试.经测试,8线程时的最大加速比可达到6.59,平均加速比6.41.在浪潮TS850服务器对并行方案的扩展性进行测试,实验结果表明:SSA算法并行方案具有良好的扩展性,最大加速比可达21.42.

关 键 词:大整数乘法  Schönhage-Strassen算法(SSA)  傅里叶变换  FFT  多核并行
收稿时间:2016/6/7 0:00:00
修稿时间:2017/1/5 0:00:00

Research on Large Integer Multiplication Schönhage-Strassen Algorithm's Multi-Core Parallelization
ZHAO Yu-Wen,LIU Fang-Fang,JIANG Li-Juan and YANG Chao.Research on Large Integer Multiplication Schönhage-Strassen Algorithm''s Multi-Core Parallelization[J].Journal of Software,2018,29(12):3604-3613.
Authors:ZHAO Yu-Wen  LIU Fang-Fang  JIANG Li-Juan and YANG Chao
Affiliation:Laboratory of Parallel Software and Computational Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China,Laboratory of Parallel Software and Computational Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China,Laboratory of Parallel Software and Computational Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China and Laboratory of Parallel Software and Computational Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;State Key Laboratory of Computer Science(Institute of Software, The Chinese Academy of Sciences), Beijing 100190, China;School of Mathematical Sciences, Peking University, Beijing 100871, China
Abstract:Schönhage-Strassen algorithm (SSA) based on the number-theoretic transform is one of the faster large integer multiplication algorithms widely used in the practical applications at present. Firstly in this paper, the principle of the SSA algorithm is introduced in detail. Then, parallel optimization is applied to SSA algorithm from a fine-grained perspective in the multi-core platform. The parallel SSA algorithm is implemented based on the open source library of large integer arithmetic algorithm GMP, and its correctness and performance is validated in the Intel X86 platform. The maximum speedup can reach 6.59 and the average speedup is 6.41 by 8 threads. The scalability of the parallel SSA algorithm is tested on the Inspur TS850, and experimental results show that it has good scalability and the maximum speedup can reach 21.42.
Keywords:large integer multiplication  Schönhage-Strassen algorithm (SSA)  the Fourier transform  FFT  multi-core parallelization
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号