大整数Comba和Karatsuba乘法的多核并行化研究
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:


Multi-Core Parallel of Large Integer Multiplication Comba and Karatsuba Algorithms
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 增强出版
  • |
  • 文章评论
    摘要:

    大整数运算广泛地应用于公钥加密算法、大规模科学计算中高精度浮点数运算类以及构建大特征值等领域,然而其大部分算法空间和时间开销都很大,尤其对于核心运算之一的大整数乘法,当数据达到一定规模时,超长的串行计算时间已成为制约算法应用的巨大瓶颈.近几年来,伴随着多核、众核芯片的迅猛发展,通过充分挖掘算法本身的并行度以利用并行处理器的强大计算能力,进而高效地提升算法性能,成为一种研究趋势.本文基于通用多核并行计算平台,研究了大整数乘法Comba及Karatsuba快速算法的并行化,提出了高效的多核并行算法.在算法实现及性能优化上,采用了OpenMP+SIMD的多级并行技术,使性能获得巨大提升.在性能测试上,我们使用优化的并行算法与原始串行算法进行对比试验,结果显示,8线程并行Comba算法和Karatsuba算法相比串行对应算法分别实现了5.85倍以及6.14倍的性能加速比提升.

    Abstract:

    The operations of large integers have been widely used among the fields of public-key encryption algorithms, the operations of floating-point data types of large-scale scientific computation and the construction of large eigenvalues and so on. However, most of the large integer arithmetic algorithms are space and time consuming especially for the large integer multiplication, one of the core large integer operations. When data reaches a certain scale, the overlong serial computing time has been the bottleneck of the applications of the large integer algorithms. Simultaneously, with the popularity of multi-core processors in the computer field in recent years, taking advantages of the parallelism of algorithms, it'll be a trend to parallelize applications to optimize their performance efficiently by using multithread programming to take full use of the powerful computing capability of parallel computers. Meanwhile, the paper did an in-depth study on the multi-core parallelization of fast algorithms of large integer multiplication Comba algorithm and Karatsuba algorithm using the OpenMP multithread programming technology and automatic vectorization technology about the SIMD model of the Intel C++ Compiler. Besides, the testing shows that the speedup of Comba algorithm with 8 threads reaches to 5.85, and Karatsuba algorithm with 8 threads reaches 6.14 at most.

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

蒋丽娟,刘芳芳,赵玉文,杨超,蔡颖.大整数Comba和Karatsuba乘法的多核并行化研究.计算机系统应用,2016,25(11):232-236

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2016-02-25
  • 最后修改日期:2016-03-24
  • 录用日期:
  • 在线发布日期: 2016-11-15
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号