Project Abstract

Our project involves benchmarking the optimal algorithm  provided by the UHFFT[1] adaptive software library for computing the Fast Fourier Transform (FFT) of a vector X. The FFT of the vector X  of a sampled signal sequence is calculated by the matrix-vector product of the DFT_N transform matrix and the vector X_Nx1. We will consider the values of N where N is a product of two co-prime numbers i.e. if N = R.S, then gcd(R,S) = 1. The UHFFT library handles such values of N using the Prime Factor algorithm and and Rader's algorithm. The optimal execution plan provided by UHFFT will be fed in SPL language to SPIRAL[2] to determine the implementation performance of SPIRAL for that particular execution plan, thus benchmarking SPIRAL for algorithm chosen by UHFFT. We will also compare the execution times provided by the implementation by SPIRAL and by UHFFT for the same values of N. The comparison will be done in terms of MFlops/s and execution time of the algorithm for different processor architectures.

Both the libraries provide a fast computation of the DFT_N matrix by using the divide-and-conquer approach[3] of representing the DFT_N matrix as a product of structured sparse matrices. Several possible factorization permutations of the transform matrix give rise to several corresponding algorithms. The libraries employ intelligent search techniques to determine the best match between the algorithm structure and its implementation with respect to a given computing-architecture( e.g. compiler optimizations, architecture-specific optimization instruction set etc.). The way and the order in which this is determined is specific to the library.

UHFFT is an adaptive software library for Fast Fourier Transforms developed by the Department of Computer Science at the University of Houston. It provides for two possible search techniques for the best execution plan viz. an exhaustive search for the best execution time and the other that uses the information stored in two databases, the codelet database and the transform database.

SPIRAL is a software package developed by the collaborative effort of Carnegie Mellon University, Drexel University, University of Southern California and University of Illinois at Urbana Champagne. SPIRAL automates the process of optimization and platform adaptation of DSP algorithms including FFT. SPIRAL employs search techniques such as dynamic programming and genetic algorithms to find the best match between the algorithm and its implementation with respect to a given computing platform. SPIRAL takes in formulas using a special syntax known as the Signal Processing Language (SPL). It then uses its SPL compiler to translate the algorithm in a general purpose language such as C or Fortran. Thus, SPL and the SPL compiler automate the implementation of the FFT algorithm.

As we learn and understand the capabilities and working of the libraries better, we hope to add to the list of goals that we wish to accomplish.

[1] http://www.cs.uh.edu/~mirkovic/fft/fftdload.htm

[2] http://www.ece.cmu.edu/~spiral/

[3] Charles Van Loan, " Frontiers in Applied Mathematics - Computational Frameworks for the Fast Fourier Transform" SIAM, Philadelphia - 1992.

This project is part of the course requirements for the High Performance Computing course at Drexel University, Dept of Computer Science.