主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第9期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
赵玉文,刘芳芳,蒋丽娟,杨超.大整数乘法Schönhage-Strassen算法的多核并行化研究.软件学报,2018,29(12):3604-3613
大整数乘法Schönhage-Strassen算法的多核并行化研究
Research on Large Integer Multiplication Schönhage-Strassen Algorithm's Multi-Core Parallelization
投稿时间:2016-06-07  修订日期:2017-01-05
DOI:10.13328/j.cnki.jos.005308
中文关键词:  大整数乘法  Schönhage-Strassen算法(SSA)  傅里叶变换  FFT  多核并行
英文关键词:large integer multiplication  Schönhage-Strassen algorithm (SSA)  the Fourier transform  FFT  multi-core parallelization
基金项目:国家重点研发计划(2016YFB0200603);国家自然科学基金(91530323)
作者单位E-mail
赵玉文 中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190  
刘芳芳 中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190  
蒋丽娟 中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190  
杨超 中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190
计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190
北京大学 数学科学学院, 北京 100871 
chao_yang@pku.edu.cn 
摘要点击次数: 1055
全文下载次数: 953
中文摘要:
      基于数论转换的Schönhage-Strassen算法(简称SSA)是目前实际应用中使用较多、速度较快的大整数乘法算法之一.首先对SSA算法原理进行了详细分析,然后从细粒度的角度对SSA算法在多核平台进行比较细致的并行优化.基于大整数运算开源库GMP实现了SSA算法并行化方案,并在Intel X86平台进行了验证和测试.经测试,8线程时的最大加速比可达到6.59,平均加速比6.41.在浪潮TS850服务器对并行方案的扩展性进行测试,实验结果表明:SSA算法并行方案具有良好的扩展性,最大加速比可达21.42.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利