CMU-CS-01-37
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-01-137

Stochastic Search for Signal Processing Algorithm Optimization

Bryan Singer, Manuela Veloso

May 2001

CMU-CS-01-137.ps
CMU-CS-01-137.pdf


Keywords: Evolutionary algorithms, signal processing, performance optimization, genertic algorithms


Many difficult problems can be viewed as search problems. However, given a new task with an embedded search problem, it is challenging to state and find a truly effective search approach. In this paper, we address the complex task of signal processing optimization. We first introduce and discuss the complexities of this domain. In general, a single signal processing algorithm can be represented by a very large number of different but mathematically equivalent formulas. When these formulas are implemented in actual code, unfortunately their running times differ significantly. Signal processing algorithm optimization aims at finding the fastest formula. We present a new approach that successfully solves this problem, using an evolutionary stochastic search algorithm, STEER, to search through the very large space of formulas. We empirically compare STEER against other search methods, showing that it notably can find faster formulas while still only timing a very small portion of the search space.

13 pages


Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu