
CMUCS00123
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS00123
Automated Formula Generation and performance Learning for the FFT
Bryan Singer, Manuela Veloso
January 2000
CMUCS00123.ps
CMUCS00123.pdf
Keywords: Machine learning, signal processing, FFT, performance
prediction, mathematical algorithms, application of neural networks,
OPAL
A single signal processing algorithm can be represented by many
different but mathematically equivalent formulas. When these
formulas are implemented in actual code, they often have very
different running times. Thus, an important problem is finding
a formula that implements the signal processing algorithm as
efficiently as possible. In this paper we present three major
results toward this goal:
(1) Different but mathematically equivalent formulas can be
generated automatically in a principled way,
(2) Simple features describing formulas can be used to distinguish
formulas with significantly different running times, and
(3) A function approximator can learn to accurately predict the
running time of a formula given a limited set of training data.
15 pages
