Generating Symmetric FFT Algorithms
Jeremy Johnson, Drexel University, Philadelphia, USA
Friday, November 3, 2006, at U. of Western Ontario.
Abstract:
This talk is centered around two challanges for symbolic mathematical
software and is organized into two parts. The first challenge is to use
mathematical structure and symbolic mathematical computation to generate
high-performance code - the challenge is to produce adaptable code that is
competetive with highly tuned vendor implementations.
The second challenge is to provide a high-level interface where mathematical
algorithms, denoted in the appropriate mathematical abstraction, are easily
specified and the details automatically derived.
The first part presents an overview of the SPIRAL system (www.spiral.net)
for generating, optimizing, and automatically adapting to different
platforms high-performance implementations of fast signal transforms such as
the Fast Fourier Transform (FFT), discrete trigonometric transforms, fast
wavelet transform, and filtering. Algorithms are represented as
mathematical formulas and algorithms are derived and manipulated using
rewrite rules. The selection of algorithm and implementation strategy are
guided by a feedback loop which uses intelligent search to find the best
implementation on a given platform. Performance data for the FFT is shown
illustrating that the code generated is competitive with vendor supplied
code (Intel's MKL and IPP libraries) and alternative approaches such as
FFTW. In cases where the vendor was unable to spend sufficient time tuning,
the SPIRAL generated code is significantly faster.
The second part presents a new algorithm, generalizing the real FFT, for
computing the multi-dimensional discrete Fourier transform of an input
vector having symmetric data. The algorithm uses a divide and conquer
approach similar to the standard FFT, but improves the constant by avoiding
the redundant computation presented by the symmetric data. This algorithm
is most naturally stated and derived abstractly using FFTs of finite Abelian
groups. The symmetries of a function defined on the group A, are described
by a subgroup of the semi-direct product of the automorphism group of A and
the Heisenberg group of A, and the algorithm is obtained from the action of
the affine part of this group
on the indexing set given by A. This level of abstraction makes the
algorithm easy to describe and derive, but difficult to implement due to the
many details the abstraction hides. We present, preliminary software,
written in the computer algebra system GAP, designed to build on top of
SPIRAL, for generating concrete symmetric FFT algorithms, described by
matrix factorizations, from the abstract formulation.
Bio:
Jeremy R. Johnson joined Drexel University in 1991 after receiving his
Ph.D. in Computer and Information Science from the Ohio State
University. He obtained a B.A. in Mathematics (with honors) from the
University of Wisconsin at Madison in 1985 and an M.S. in computer and
information science from the University of Delaware in 1988.
He is currently serving as Department Head for the Department of
Computer Science and holds a joint appointment in the Department of
Electrical and Computer Engineering. He has held visiting positions in
the Department of Electrical and Computer Engineering at Carnegie
Mellon University and the Research Institute for Symbolic Computation
in Linz Austria.
Dr. Johnson's research interests include algebraic algorithms,
computer algebra systems, problem solving environments, programming
languages and compilers, high performance computing, hardware
generation, and automated performance tuning. He is currently working
on SPIRAL, a joint research project with Carnegie Mellon University
and the University of Illinois at Urbana-Champaign, funded by DARPA
and NSF, to develop techniques to automatically implement and optimize
signal processing algorithms. He co-edited a special issue of the
Journal of Symbolic Computation devoted to Computer Algebra and Signal
Processing, and is a member of the editorial board of the Journal of
Applicable Algebra in Engineering, Communication and Computing. He is
co-director, with Prawat Nagvajara of the Application Specific
Computing Research Group with application projects in signal
processing and power systems. He is also co-director, with Bruce Char
and Werner Krandick, of the Applied Symbolic Computing (ASYM) Research
Group.
|