Stochastic search for signal processing algorithm optimization

ABSTRACT

This paper presents an evolutionary algorithm for searching for the optimal implementations of signal transforms and compares this approach against other search techniques. 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.

REFERENCES

• 1: {Auslander et al., 1996} L. Auslander, J. Johnson, and R. Johnson. Automatic implementation of FFT algorithms. Technical Report 96-01, Drexel University, 1996.
• 2: {Beauchamp, 1984} K. Beauchamp. Applications of Walsh and Related Functions. Academic Press, 1984.
• 3: Jeff Bilmes , Krste Asanovic , Chee-Whye Chin , Jim Demmel, Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology, Proceedings of the 11th international conference on Supercomputing, p.340-347, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263662]
• 4: Eric A. Brewer, High-level optimization via automated statistical modeling, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.80-91, July 19-21, 1995, Santa Barbara, California, United States
• 5: {Frigo and Johnson, 1998} M. Frigo and S. Johnson. FFTW: An adaptive software architecture for the FFT. In Proceedings of International Conference on Acoustics, Speech, and Signal Processing, volume 3, 1998.
• 6: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 7: {Haentjens, 2000} G. Haentjens. An investigation of Cooley-Tukey decompositions for the FFT. Master's thesis, ECE Dept., Carnegie Mellon University, 2000.
• 8: {Johnson and Burrus, 1983} H. Johnson and C. Burrus. The design of optimal DFT algorithms using dynamic programming. In IEEE Transactions on Acoustics, Speech, and Signal Processing, volume 31, 1983.
• 9: {Johnson and Püschel, 2000} J. Johnson and M. Püschel. In search of the optimal Walsh-Hadamard transform. In Proceedings of International Conference on Acoustics, Speech, and Signal Processing, 2000.
• 10: Michail G. Lagoudakis , Michael L. Littman, Algorithm Selection using Reinforcement Learning, Proceedings of the Seventeenth International Conference on Machine Learning, p.511-518, June 29-July 02, 2000
• 11: {Moura et al., 1998} J. Moura, J. Johnson, R. Johnson, D. Padua, V. Prasanna, and M. Veloso. SPIRAL: Portable Library of Optimized Signal Processing Algorithms, 1998. http://www.ece.cmu.edu/~spiral/.
• 12: Markus Püschel , Bryan Singer , Manuela M. Veloso , José M. F. Moura, Fast Automatic Generation of DSP Algorithms, Proceedings of the International Conference on Computational Sciences-Part I, p.97-106, May 28-30, 2001
• 13: K. R. Rao , P. Yip, Discrete cosine transform: algorithms, advantages, applications, Academic Press Professional, Inc., San Diego, CA, 1990
• 14: {Sepiashvili, 2000} D. Sepiashvili. Performance models and search methods for optimal FFT implementations. Master's thesis, ECE Dept., Carnegie Mellon University, 2000.
• 15: R. Clint Whaley , Jack J. Dongarra, Automatically tuned linear algebra software, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-27, November 07-13, 1998, San Jose, CA
• 16: Jianxin Xiong , Jeremy Johnson , Robert Johnson , David Padua, SPL: a language and compiler for DSP algorithms, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.298-308, June 2001, Snowbird, Utah, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Performance