Stochastic Search for Signal Processing Algorithm Optimization
Abstract
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, the authors address the complex task of signal processing optimization. They 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. Unfortunately, when these formulas are implemented in actual code, their running times differ significantly. Signal processing algorithm optimization aims at finding the fastest formula. The authors present a new approach that successfully solves this problem using an evolutionary stochastic search algorithm, Split Tree Evolution for Efficient Runtimes (STEER), to search through the very large space of formulas. They empirically compare STEER against other search methods, including dynamic programming, exhaustive search, and random search, and show that STEER can find faster formulas while still only timing a very small portion of the search space.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 2001
- Accession Number
- ADA458509
Entities
People
- Bryan Singer
- Manuela M. Veloso
Organizations
- Carnegie Mellon University