vecpar.fe.up.pt/2006  vecpar2006@fe.up.pt  
A Rewriting System for the Vectorization of Signal Transforms
Franz Franchetti (Carnegie Mellon University)Yevgen Voronenko (Carnegie Mellon University) Markus Püschel (Carnegie Mellon University) Abstract:
We present a rewriting system that automatically vectorizes signal
transform algorithms at a high level of abstraction. The input to the
system is a transform algorithm given as a formula in the wellknown
Kronecker product formalism. The output is a "vectorized" formula,
which means it consists exclusively of constructs that can be directly mapped into short vector code. This approach obviates compiler vectorization, which is known to be limited in this domain. We included the formula vectorization into the Spiral program generator for signal transforms, which enables us to generate vectorized code and optimize through search over alternative algorithms. Benchmarks for the discrete Fourier transform (DFT) show that our generated floatingpoint code is competitive with and that our fixedpoint code clearly outperforms
the best available libraries.
Keywords:
Numerical Methods (Linear algebra), Parallel and Distributed Computing


Rio de Janeiro  Brazil  2006  July  10 11 12 13 