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

• 作者: 刘芳芳 杨超 蒋丽娟 蔡颖 赵玉文
• 来源期刊: 计算机系统应用
• 关键词: 大整数运算 Comba算法 Karatsuba算法 OpenMP SIMD
• 年，卷（期）: 2016,（11）
• 所属期刊栏目: 研究开发
• 页码范围: 232-236
• 页数: 5页
• 字数: 4233字
• 语种: 中文
• DOI: 10.15888/j.cnki.csa.005408

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨超	中国科学院软件研究所	114	799	15.0	23.0
2	刘芳芳	中国科学院软件研究所	13	88	4.0	9.0
3	蔡颖	中国科学院软件研究所	2	3	1.0	1.0
4	蒋丽娟	中国科学院软件研究所	3	7	2.0	2.0
5	赵玉文	中国科学院软件研究所	4	123	2.0	4.0