Automating the modeling and optimization of the performance of signal transforms

Abstract

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.