Special Issue — International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2009)No Access

BALANCED DENSE POLYNOMIAL MULTIPLICATION ON MULTI-CORES

MARC MORENO MAZA

Ontario Research Centre for Computer Algebra, University of Western Ontario, London Ontario, N6A 5B7, Canada

Search for more papers by this author

and

YUZHEN XIE

Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge Massachusetts, MA 02139, USA

Search for more papers by this author

https://doi.org/10.1142/S0129054111008556Cited by:11 (Source: Crossref)

Abstract

In symbolic computation, polynomial multiplication is a fundamental operation akin to matrix multiplication in numerical computation. We present efficient implementation strategies for FFT-based dense polynomial multiplication targeting multi-cores. We show that balanced input data can maximize parallel speedup and minimize cache complexity for bivariate multiplication. However, unbalanced input data, which are common in symbolic computation, are challenging. We provide efficient techniques, that we call contraction and extension, to reduce multivariate (and univariate) multiplication to balanced bivariate multiplication. Our implementation in Cilk++ demonstrates good speedup on multi-cores.

Keywords:

References

E. Beckeret al., The shape of the shape lemma, Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC) '94 (1994) pp. 129–133. Google Scholar
R. D. Blumofe and C. E. Leiserson , Scheduling multithreaded computations by work stealing , IEEE Conference on Foundations of Computer Science '94 . Google Scholar
J. Cooley and J. Tukey, Math. of Comp. 19, 297 (1965), DOI: 10.1090/S0025-5718-1965-0178586-1. Crossref, Web of Science, Google Scholar
M. Frigo and S. G. Johnson, Proc. of the IEEE 93(2), 216 (2005), DOI: 10.1109/JPROC.2004.840301. Crossref, Web of Science, Google Scholar
M. Frigoet al., Cache-oblivious algorithms, Annual Symposium on Foundations of Computer Science' 99 pp. 285–297. Google Scholar
M. Frigo , C. E. Leiserson and K. H. Randall , The implementation of the Cilk-5 multithreaded language , ACM SIGPLAN . Google Scholar
J. Gathen and J. Gerhard , Modern Computer Algebra ( Cambridge Univ. Press , 1999 ) . Google Scholar
J. Hoeven, The Truncated Fourier Transform and applications, Proc. of ISSAC'04 (2004) pp. 290–296. Google Scholar
Cilk Arts Inc. Cilk++ , http://www.cilk.com/ . Google Scholar
Intel Corporation. VTune Performance Analyzer , http://www.intel.com/ . Google Scholar
X. Li et al. , The modpn library: Bringing fast polynomial arithmetic into Maple , Proc. of Milestones of Computer Algebra '08 . Google Scholar
X. Li, M. Moreno Maza and É. Schost, Fast arithmetic for triangular sets: From theory to practice, Proc. of ISSAC'07 (2007) pp. 269–276. Google Scholar
LinBox Project , http://www.linalg.org/ . Google Scholar
MAGMA Project , http://magma.maths.usyd.edu.au/magma/ . Google Scholar
P. L. Montgomery, Math. of Comp. 44(170), 519 (1985), DOI: 10.1090/S0025-5718-1985-0777282-X. Crossref, Web of Science, Google Scholar
M. Moreno Maza and Y. Xie, FFT-based dense polynomial arithmetic on multicores, High Performance Computing Symposium (HPCS) 2009, LNCS 5976, eds. D. J. K. Mewhortet al. (Springer-Verlag Berlin, Heidelberg, 2010) pp. 378–399. Google Scholar
NTL. The Number Theory Library , http://www.shoup.net/ntl . Google Scholar