This directory contains software generated as part of a joint project
involving ISIP and
High Performance Computing Laboratory (HPCL),
which does pioneering research in
Message Passing Interface (MPI)
standards. The main goals of this project were to test the performance
portability using object oriented concepts.
FFT's were a natural choice to test these concepts; the large number
of algorithms developed over the years for its efficient computation
give us a wide range of implementation choices. The ultimate goal of
this part of the project was a capability for coarse-grain
poly-algorithmic selection. For this reason we needed to analyze and
benchmark the algorithms based on a large set of criteria.
-
So what were the
algorithms
benchmarked?
-
Traditional benchmarking
has focused on computation speed or number of computations. In
our work we deviate from this mainly because advances in CPU
speeds and compilers in past decade or so have made the whole
process of computation highly
system dependent.
The
criteria used
are therefore quite comprehensive.
-
The software has a simple
command-line interface
-
The algorithms were
compared for computation speed
by running multiple iterations on a Pentium Pro 200MHz
processor and compiled using GCC. Since
memory usage
and computation times are well correlated in any algorithm
implementation it is worth seeing the relationship. As
expected, in most cases there exists an inverse relationship.
-
One of the most important results of the work is the bare-bone
comparison of the algorithms in terms of various mathematical
operation counts.
We have analyzed integer and floating point operations
separately since computation times for each of these operations
differ significantly on many CPUs.
-
Another very significant result is the
performance comparison
of various contemporary widely used CPUs. In many cases results
may be affected dramatically by the compilers in use. We
calibrated the
effect of GCC and MSVC++
on two algorithms FHT and SRFFT.
-
There were some
general conclusions
from this work as well as some
algorithm level conclusions
which are valuable and can be used effectively in the choice of
FFT algorithms.
-
You can find all this material in
the Master's presentation
on this work by Aravind Ganapathiraju, which sums it all in
great detail.
-
We also have a
detailed report
on this work.
-
Source code
generated from this work is available for public. Enjoy!!!!!
|