###
计算机系统应用英文版:2016,25(11):232-236
本文二维码信息
码上扫一扫!
大整数Comba和Karatsuba乘法的多核并行化研究
(中国科学院 软件研究所, 北京 100190)
Multi-Core Parallel of Large Integer Multiplication Comba and Karatsuba Algorithms
(Institute of Software, Chinese Academy of Sciences, Beijing 100190, China)
摘要
图/表
参考文献
相似文献
本文已被:浏览 2076次   下载 2406
Received:February 25, 2016    Revised:March 24, 2016
中文摘要: 大整数运算广泛地应用于公钥加密算法、大规模科学计算中高精度浮点数运算类以及构建大特征值等领域,然而其大部分算法空间和时间开销都很大,尤其对于核心运算之一的大整数乘法,当数据达到一定规模时,超长的串行计算时间已成为制约算法应用的巨大瓶颈.近几年来,伴随着多核、众核芯片的迅猛发展,通过充分挖掘算法本身的并行度以利用并行处理器的强大计算能力,进而高效地提升算法性能,成为一种研究趋势.本文基于通用多核并行计算平台,研究了大整数乘法Comba及Karatsuba快速算法的并行化,提出了高效的多核并行算法.在算法实现及性能优化上,采用了OpenMP+SIMD的多级并行技术,使性能获得巨大提升.在性能测试上,我们使用优化的并行算法与原始串行算法进行对比试验,结果显示,8线程并行Comba算法和Karatsuba算法相比串行对应算法分别实现了5.85倍以及6.14倍的性能加速比提升.
中文关键词: 大整数运算  Comba算法  Karatsuba算法  OpenMP  SIMD
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
JIANG Li-Juan,LIU Fang-Fang,ZHAO Yu-Wen,YANG Chao,CAI Ying.Multi-Core Parallel of Large Integer Multiplication Comba and Karatsuba Algorithms.COMPUTER SYSTEMS APPLICATIONS,2016,25(11):232-236