Paper Info
Title
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.
Year
DOI
Venue
2010
10.1145/1838599.1838616
ACM Comm. Computer Algebra
Keywords
Field
DocType
new data type,new rule,available code,modular fast fourier transforms,modular arithmetic,new algorithm,spiral-generated modular ffts,spiral system,vectorized code,new symbol,modular fft code,search engine,computer algebra,parallel computer,data type,floating point,generic algorithm,distributed memory,code generation,feedback loop,fixed point,digital signal processing,fast fourier transform,finite field
Kernel (linear algebra),Discrete mathematics,Modular arithmetic,Parallel computing,Symbolic computation,Distributed memory,Algorithm,Vectorization (mathematics),Data type,Fast Fourier transform,Modular design,Mathematics
Journal
Volume
Issue
Citations 
44
1/2
0
PageRank 
References 
Authors
0.34
0
6
Name
Order
Citations
PageRank
Lingchuan Meng1162.90
Jeremy Johnson2194.51
Franz Franchetti397488.39
Yevgen Voronenko423917.54
Marc Moreno Maza571767.29
Yuzhen Xie611411.96