×

Automatic parallel library generation for general-size modular FFT algorithms. (English) Zbl 1412.68307

Gerdt, Vladimir P. (ed.) et al., Computer algebra in scientific computing. 15th international workshop, CASC 2013, Berlin, Germany, September 9–13, 2013. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8136, 243-256 (2013).
Summary: This paper presents the automatic library generation for modular FFT algorithms with arbitrary input sizes. We show how to represent the transform and its algorithms at a high abstraction level. Symbolic manipulations and code optimizations that use rewriting systems can then be systematically applied to generate a library with recursive function closure. The generated library is automatically optimized for the target computing platforms, and is intended to support modular algorithms for multivariate polynomial computations in the modpn library used by Maple. The resulting scalar and vector codes provide comparable speedup to the fixed-size code presented in [the first author et al., “Spiral-generated modular FFT algorithms”, in: Proceedings of the 4th international workshop on parallel symbolic computation, PASCO 2010. New York, NY: Association for Computing Machinery (ACM). 169–170 (2010; doi:10.1145/1837210.1837235)], which is an order of magnitude faster over the hand-tuned modpn library. Thread-level parallelism has also been utilized by the generated library and delivers additional speedup.
For the entire collection see [Zbl 1291.68021].

MSC:

68W30 Symbolic computation and algebraic computation
65T50 Numerical methods for discrete and fast Fourier transforms
68W10 Parallel algorithms in computer science

Software:

Maple; SPIRAL; modpn; FFTW
PDFBibTeX XMLCite
Full Text: DOI