Automating the modeling and optimization of the performance of signal transforms

• Published in: IEEE transactions on signal processing 2002-08, Vol.50 (8), p.2003-2014
• Main Authors: Singer, B., Veloso, M.M.
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Artificial intelligence; Automation; Computer science; control theory; systems; Connectionism. Neural networks; Discrete Fourier transforms; Discrete transforms; Error analysis; Exact sciences and technology; Factorization; Fast Fourier transforms; Information, signal and communications theory; Mathematical methods; Mathematical models; Microprocessors; Neural networks; Optimization; Performance analysis; Searching; Signal analysis; Signal processing; Stochastic processes; Studies; Telecommunications and information theory; Training data; Transforms
• ISSN: 1053-587X; 1941-0476
• DOI: 10.1109/TSP.2002.800394

Fast implementations of discrete signal transforms, such as the discrete Fourier transform (DFT), the Walsh-Hadamard transform (WHT), and the discrete trigonometric transforms (DTTs), can be viewed as factorizations of their corresponding transformation matrices. A given signal transform can have many different factorizations, with each factorization represented by a unique but mathematically equivalent formula. When implemented in code, these formulas can have significantly different running times on the same processor, sometimes differing by an order of magnitude. Further, the optimal implementations on various processors are often different. Given this complexity, a crucial problem is automating the modeling and optimization of the performance of signal transform implementations. To enable computer modeling of signal processing performance, we have developed and analyzed more than 15 feature sets to describe formulas representing specific transforms. Using some of these features and a limited set of training data, we have successfully trained neural networks to learn to accurately predict performance of formulas with error rates less than 5%. In the direction of optimization, we have developed a new stochastic evolutionary algorithm known as STEER that finds fast implementations of a variety of signal transforms. STEER is able to optimize completely new transforms specified by a user. We present results that show that STEER can find discrete cosine transform formulas that are 10-20% faster than what a dynamic programming search finds.