###
Journal of Software:2018.29(12):3604-3613

大整数乘法Schönhage-Strassen算法的多核并行化研究
赵玉文,刘芳芳,蒋丽娟,杨超
(中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190;中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190;计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190;北京大学 数学科学学院, 北京 100871)
Research on Large Integer Multiplication Schönhage-Strassen Algorithm's Multi-Core Parallelization
ZHAO Yu-Wen,LIU Fang-Fang,JIANG Li-Juan,YANG Chao
(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;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
Chart / table
Reference
Similar Articles
Article :Browse 506   Download 626
Received:June 07, 2016    Revised:January 05, 2017
> 中文摘要: 基于数论转换的Schönhage-Strassen算法(简称SSA)是目前实际应用中使用较多、速度较快的大整数乘法算法之一.首先对SSA算法原理进行了详细分析,然后从细粒度的角度对SSA算法在多核平台进行比较细致的并行优化.基于大整数运算开源库GMP实现了SSA算法并行化方案,并在Intel X86平台进行了验证和测试.经测试,8线程时的最大加速比可达到6.59,平均加速比6.41.在浪潮TS850服务器对并行方案的扩展性进行测试,实验结果表明:SSA算法并行方案具有良好的扩展性,最大加速比可达21.42.
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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家重点研发计划(2016YFB0200603);国家自然科学基金(91530323) 国家重点研发计划(2016YFB0200603);国家自然科学基金(91530323)
Foundation items:National Key Research amd Development Program of China (2016YFB0200603); National Natural ScienceFoundation of China (91530323)
Reference text:

赵玉文,刘芳芳,蒋丽娟,杨超.大整数乘法Schönhage-Strassen算法的多核并行化研究.软件学报,2018,29(12):3604-3613

ZHAO Yu-Wen,LIU Fang-Fang,JIANG Li-Juan,YANG Chao.Research on Large Integer Multiplication Schönhage-Strassen Algorithm's Multi-Core Parallelization.Journal of Software,2018,29(12):3604-3613