大整数乘法Schönhage-Strassen算法的多核并行化研究
作者:
作者单位:

作者简介:

赵玉文(1987-),女,河北唐山人,助理研究员,CCF专业会员,主要研究领域为高性能扩展数学库,并行计算;刘芳芳(1982-),女,高级工程师,CCF专业会员,主要研究领域为高性能扩展数学库,稀疏迭代解法器,异构众核并行;蒋丽娟(1990-),女,本科生,CCF学生会员,主要研究领域为并行计算;杨超(1979-),男,博士,教授,博士生导师,主要研究领域为高性能计算,科学与工程计算.

通讯作者:

杨超,E-mail:chao_yang@pku.edu.cn

中图分类号:

基金项目:

国家重点研发计划(2016YFB0200603);国家自然科学基金(91530323)


Research on Large Integer Multiplication Schönhage-Strassen Algorithm's Multi-Core Parallelization
Author:
Affiliation:

Fund Project:

National Key Research amd Development Program of China (2016YFB0200603); National Natural ScienceFoundation of China (91530323)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    基于数论转换的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.

    参考文献
    相似文献
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2016-06-07
  • 最后修改日期:2017-01-05
  • 录用日期:
  • 在线发布日期: 2018-12-05
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号