Automating the Modeling and Optimization of the Performance of Signal Processing Algorithms

automatic performance tuning Many applications require fast implementations of signal processing algo-rithms to analyze data in real time or to effectively process many large data sets. Fast implementations of a signal transform need to take advantage of structure in the transformation matrix to factor the transform into a prod-uct of structured matrices. These factorizations compute the transform with fewer operations than the naïve implementation of matrix multiplication. Sig-nal transforms can have a vast number of factorizations, with each factorization of a single transform represented by a unique but mathematically equivalent formula. Interestingly, when implemented in code, these formulas can have sig-nificantly different runtimes on the same processor, sometimes differing by an order of magnitude. Further, the optimal implementations differ significantly between processors. Therefore, determining which formula is the most efficient for a particular processor is of great interest