Four Easy Ways to a Faster FFT |
| |
Authors: | Lenore R Mullin Sharon G Small |
| |
Institution: | (1) Computer Science Department, University at Albany, SUNY, Albany, NY, 12222, U.S.A.;(2) NY 12222, U.S.A. |
| |
Abstract: | The Fast Fourier Transform (FFT) was named one of the Top Ten algorithms of the 20th century , and continues to be a focus of current research. A problem with currently used FFT packages is that they require large, finely tuned, machine specific libraries, produced by highly skilled software developers. Therefore, these packages fail to perform well across a variety of architectures. Furthermore, many need to run repeated experiments in order to re-program their code to its optimal performance based on a given machine's underlying hardware. Finally, it is difficult to know which radix to use given a particular vector size and machine configuration. We propose the use of monolithic array analysis as a way to remove the constraints imposed on performance by a machine's underlying hardware, by pre-optimizing array access patterns. In doing this we arrive at a single optimized program. We have achieved up to a 99.6% increase in performance, and the ability to run vectors up to 8 388 608 elements larger, on our experimental platforms. Preliminary experiments indicate different radices perform better relative to a machine's underlying architecture. |
| |
Keywords: | performance analysis and evaluation signal and image processing FFT array algebra linear transformations radix n MOA Psi calculus shape polymorphism shapes |
本文献已被 SpringerLink 等数据库收录! |
|