大整数Comba和Karatsuba乘法的多核并行化研究  

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

作　　者：蒋丽娟[1] 刘芳芳[1] 赵玉文[1] 杨超[1] 蔡颖[1] JIANG Li-Juan LIU Fang-Fang ZHAO Yu-Wen YANG Chao CAI Ying(Institute of Software, Chinese Academy of Sciences, Beijing 100190, China)

机构地区：[1]中国科学院软件研究所,北京100190

出　　处：《计算机系统应用》2016年第11期232-236,共5页Computer Systems & Applications

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]