Abstract only: SPIRAL-generated modular FFTs

Abstract

In this poster we present the use of the SPIRAL system (www.spiral.net) to generate code for modular Fast Fourier Transforms (FFTs). SPIRAL is a library generation system that automatically generates platform-tuned implementations of digital signal processing algorithms with an emphasis on fast transforms. Currently, SPRIAL can generate highly optimized fixed point and floating-point FFTs for a variety of platforms including vectorization, multi-threaded and distributed memory parallelization. The code produced is competitive with the best available code for these platforms and SPIRAL is used by Intel for its IPP (Intel Performance Primitives) and MKL (Math kernel Library) libraries.

The SPIRAL system uses a mathematical framework for representing and deriving algorithms. Algorithms are derived using rewrite rules and additional rules are used to symbolically manipulate algorithms into forms that take advantage of the underlying hardware. A search engine with a feedback loop is used to tune implementations to particular platforms. New transforms are added by introducing new symbols and their definition and new algorithms can be generated by adding new rules.

We extended SPIRAL to generate algorithms for FFT computation over finite fields. This addition required adding a new data type, several new rules and a new transform (ModDFT) definition. In addition, the unparser (where code is generated) was extended so that it can generate scalar and vectorized code for modular arithmetic. With these enhancements, the SPRIAL machinery can be applied to modular transforms that are of interest to the computer algebra community. This provides a framework for systematically optimizing these transforms, utilizing vector and parallel computation, and for automatically tuning them to different platforms. In this poster we present preliminary results from this exploration. We show that the code generated by SPIRAL, with improved cache locality and vectorization, is approximately ten times faster than the modular FFT code in the modpn library.

Index Terms

• Computing methodologies

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

      • Algebraic algorithms

• Mathematics of computing

  • Mathematical analysis

    • Functional analysis

      • Approximation

    • Numerical analysis

      • Computation of transforms

      • Computations in finite fields

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis