| 本文已被：浏览 3301次 下载 7404次 |
码上扫一扫！ |
|
|
| 大整数乘法Schönhage-Strassen算法的多核并行化研究 |
|
赵玉文1, 刘芳芳1, 蒋丽娟1, 杨超1,2,3
|
|
1.中国科学院 软件研究所 并行软件与计算科学实验室, 北京 100190;2.计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190;3.北京大学 数学科学学院, 北京 100871
|
|
| 摘要: |
| 基于数论转换的Schönhage-Strassen算法（简称SSA）是目前实际应用中使用较多、速度较快的大整数乘法算法之一.首先对SSA算法原理进行了详细分析，然后从细粒度的角度对SSA算法在多核平台进行比较细致的并行优化.基于大整数运算开源库GMP实现了SSA算法并行化方案，并在Intel X86平台进行了验证和测试.经测试，8线程时的最大加速比可达到6.59，平均加速比6.41.在浪潮TS850服务器对并行方案的扩展性进行测试，实验结果表明：SSA算法并行方案具有良好的扩展性，最大加速比可达21.42. |
| 关键词: 大整数乘法 Schönhage-Strassen算法(SSA) 傅里叶变换 FFT 多核并行 |
| DOI：10.13328/j.cnki.jos.005308 |
| 分类号: |
| 基金项目:国家重点研发计划（2016YFB0200603）；国家自然科学基金（91530323） |
|
| Research on Large Integer Multiplication Schönhage-Strassen Algorithm's Multi-Core Parallelization |
|
ZHAO Yu-Wen1, LIU Fang-Fang1, JIANG Li-Juan1, YANG Chao1,2,3
|
|
1.Laboratory of Parallel Software and Computational Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;2.State Key Laboratory of Computer Science(Institute of Software, The Chinese Academy of Sciences), Beijing 100190, China;3.School of Mathematical Sciences, Peking University, Beijing 100871, China
|
| 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. |
| Key words: large integer multiplication Schönhage-Strassen algorithm (SSA) the Fourier transform FFT multi-core parallelization |
