微信服务号

微信订阅号

2025-4-24- 10
Home > Archive>Volume 29, Issue 12, 2018 >3604-3613. DOI:10.13328/j.cnki.jos.005308
PDF HTML XML Export Cite reminder
Research on Large Integer Multiplication Schönhage-Strassen Algorithm's Multi-Core Parallelization
Author:
Affiliation:

Fund Project:

National Key Research amd Development Program of China (2016YFB0200603); National Natural ScienceFoundation of China (91530323)

  • Article
    • | |
  • Metrics
    • |
  • Reference [31]
    • |
  • Related [20]
    • | | |
  • Comments
    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.

    Reference
    [1] Sang B. Research and fast implementation of large integers multiplication algorithm[MS. Thesis]. Guangzhou:South China University of Technology, 2012(in Chinese with English abstract).
    [2] Karatsuba A, Ofman Y. Multiplication of multidigit numbers on automata. Soviet Physics-Doklady, 1963,7:595-596.
    [3] Toom AL. The complexity of a scheme of functional elements realizing the multiplication of ISSntegers. Soviet Mathematics Doklady, 1963,3:714-716.
    [4] Cooley JW, Tukey JW. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 1965,19:297-301.
    [5] Schönhage A, Strassen V. Schnelle multiplikation großer zahlen. Computing, 1971,7(3-4):281-292.
    [6] Gaudry P, Kruppa A, Zimmermann P. A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm. In:Proc. of the 2007 Int'l Symp. on Symbolic and Algebraic Computation. ACM Press, 2007. 167-174.
    [7] Sze TW. Schönhage-Strassen algorithm with MapReduce for multiplying terabit integers. In:Proc. of the 2011 Int'l Workshop on Symbolic-Numeric Computation. ACM Press, 2012. 54-62.
    [8] Fürer M. Faster integer multiplication. In:Proc. of the 39th ACM Symp. on Theory of Computing. 2007. 57-66.
    [9] Fürer M. Faster integer multiplication. SIAM Journal on Computing, 2009,39(3):979-1005.
    [10] Keliris A, Maniatakos M. Investigating large integer arithmetic on Intel Xeon Phi SIMD extensions. In:Proc. of the 9th Int'l Conf. on Design & Technology of Integrated Systems in Nanoscale Era (DTIS 2014). Santorini:IEEE, 2014. 1-6.
    [11] Tembhurne JV, Sathe SR. Performance evaluation of long integer multiplication using OpenMP and MPI on shared memory architecture. In:Proc. of the 20147th Int'l Conf. on Contemporary Computing (IC3). IEEE, 2014. 283-288.
    [12] Jebelean T. Using the parallel karatsuba algorithm for long integer multiplication and division. In:Proc. of the Euro-Par'97 Parallel Processing. Berlin, Heidelberg:Springer-Verlag, 1997. 1169-1172.
    [13] Mansouri F. On the parallelization of integer polynomial multiplication[MS. Thesis]. University of Western Ontario, 2014.
    [14] Xu L, Wang Z. Fast large integer multiplication based on CUDA. Computer Engineering and Applications, 2013,49(16):221-225(in Chinese with English abstract).
    [15] Chmielowiec A. Fast, parallel algorithm for multiplying polynomials with integer coefficients. In:Proc. of the World Congress on Engineering. 2012.
    [16] Emeliyanenko P. Efficient multiplication of polynomials on graphics hardware. In:Proc. of the Advanced on Parallel Processing Technologies. Berlin, Heidelberg:Springer-Verlag, 2009. 134-149.
    [17] Emmart N, Weems C. High precision integer multiplication with a graphics processing unit. In:Proc. of the 2010 IEEE Int'l Symp. on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW). IEEE, 2010. 1-6.
    [18] Emmart N, Weems C. High precision integer multiplication with a GPU. In:Proc. of the 2011 IEEE Int'l Symp. on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW). IEEE, 2011. 1781-1787.
    [19] Doroz Y, Ozturk E, Sunar B. Evaluating the hardware performance of a million-bit multiplier. In:Proc. of the 2013 Euromicro Conf. on Digital System Design (DSD). IEEE, 2013. 955-962.
    [20] Jiang CJ, Jiang Y. Fast Fourier Transform and C Procedures. Hefei:University of Science and Technology of China Press, 2004. (in Chinese).
    [21] Nussbaumer HJ. Fast polynomial transform algorithms for digital convolution. IEEE Trans. on Acoustics, Speech, and Signal Processing, 1980,28(2):205-215.
    [22] Hu GS. Digital Signal Processing:Theory, Arithmetic and Realization. 2nd ed., Beijing:Tsinghua University Press, 2003. (in Chinese).
    [23] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 3rd ed., Cambridge:The MIT Press, 2009. 900-905.
    [24] Proakis JG, Rader CM, Ling F, Nikias CL, Moonen M, Proudler IK. Algorithms for Statistical Signal Processing. London:Prentice Hall, 2002. 63-67.
    [25] Crandall R, Fagin B. Discrete weighted transforms and large-integer arithmetic. Mathematics of Computation, 1994,62(205):305-324.
    [26] Amdahl GM. Validity of the single processor approach to achieving large scale computing capabilities. In:Proc. of the Spring Joint Computer Conf. ACM Press, 1967. 483-485.
    附中文参考文献:
    [1] 桑波.大整数乘法算法的研究与快速实现[硕士学位论文].广州:华南理工大学,2012.
    [14] 许亮,王震.基于CUDA的快速大整数乘法.计算机工程与应用,2013,49(16):221-225.
    [20] 蒋长锦,蒋勇.快速傅里叶变换及其C程序.合肥:中国科学技术大学出版社,2004.
    [22] 胡广书.数字信号处理:理论、算法与实现.第2版,北京:清华大学出版社,2003.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

赵玉文,刘芳芳,蒋丽娟,杨超.大整数乘法Schönhage-Strassen算法的多核并行化研究.软件学报,2018,29(12):3604-3613

Copy
Share
Article Metrics
  • Abstract:2478
  • PDF: 5500
  • HTML: 1830
  • Cited by: 0
History
  • Received:June 07,2016
  • Revised:January 05,2017
  • Online: December 05,2018
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2038008Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063