Andrew A. Lamb
Saman Amarasinghe
ABSTRACT
As more complex DSP algorithms are realized in practice, there is an increasing need for high-level stream abstractions that can be compiled without sacrificing efficiency. Toward this end, we present a set of aggressive optimizations that target linear sections of a stream program. Our input language is StreamIt, which represents programs as a hierarchical graph of autonomous filters. A filter is linear if each of its outputs can be represented as an affine combination of its inputs. Linearity is common in DSP components; examples include FIR filters, expanders, compressors, FFTs and DCTs.We demonstrate that several algorithmic transformations, traditionally hand-tuned by DSP experts, can be completely automated by the compiler. First, we present a linear extraction analysis that automatically detects linear filters from the C-like code in their work function. Then, we give a procedure for combining adjacent linear filters into a single filter, as well as for translating a linear filter to operate in the frequency domain. We also present an optimization selection algorithm, which finds the sequence of combination and frequency transformations that will give the maximal benefit.We have completed a fully-automatic implementation of the above techniques as part of the StreamIt compiler, and we demonstrate a 450% performance improvement over our benchmark suite.
- V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: A transparent dynamic optimization system. In PLDI, 1999. Google Scholar
Digital Library
- P. Cousot and N. Halbwachs. Automatic discovery of linear restraints among variables of a program. In POPL, 1978. Google ScholarDigital Library
- M. M. Covell. An Algorithm Design Environment for Signal Processing. PhD thesis, MIT, 1989.Google Scholar
- S. Egner, J. Johnson, D. Padua, M. Püschel, and J. Xiong. Automatic derivation and implementation of signal processing algorithms. SIGSAM Bulletin, 35(2):1--19, 2001. Google ScholarDigital Library
- M. Frigo. A Fast Fourier Transform Compiler. In PLDI, 1999. Google ScholarDigital Library
- M. Gordon. A stream-aware compiler for communication-exposed architectures. Master's thesis, MIT Laboratory for Computer Science, August 2002. Google ScholarDigital Library
- M. Gordon, W. Thies, M. Karczmarek, J. Lin, A. S. Meli, A. A. Lamb, C. Leger, J. Wong, H. Hoffmann, D. Maze, and S. Amarasinghe. A Stream Compiler for Communication-Exposed Architectures. ASPLOS, 2002. Google ScholarDigital Library
- J. Johnson, R. W. Johnson, D. A. Padua, and J. Xiong. SPIRAL Home Page. http://www.ece.cmu.edu/˜spiral/.Google Scholar
- J. Johnson, R. W. Johnson, D. A. Padua, and J. Xiong. Searching for the best FFT formulas with the SPL compiler. LNCS, 2017, 2001. Google ScholarDigital Library
- M. A. Karczmarek. Constrained and phased scheduling of synchronous data flow graphs for the streamit language. Master's thesis, MIT LCS, October 2002.Google Scholar
- M. Karr. Affine relationships among variables of a program. Acta Informatica, pages 133--155, 1976.Google ScholarDigital Library
- J. Lebak. Polymorphous Computing Architecture (PCA) Example Applications and Description. External Report, Lincoln Laboratory, Mass. Inst. of Technology, 2001.Google Scholar
- M.B. Taylor et. al . The raw microprocessor: a computational fabric for software circuits and general-purpose programs. IEEE Micro, 22(2):25--35, March/April 2002. Google ScholarDigital Library
- A. V. Oppenheim and S. H. Nawab, editors. Symbolic and Knowledge-Based Signal Processing. Prentice Hall, 1992. Google ScholarDigital Library
- A. V. Oppenheim, R. W. Shafer, and J. R. Buck. Discrete-Time Signal Processing. Prentice Hall, second edition, 1999. Google ScholarDigital Library
- S. Ryan. Linear data flow analysis. ACM SIGPLAN Notices, 27(4):59--67, 1992. Google ScholarDigital Library
- R. Stephens. A Survey of Stream Processing. Acta Informatica, 34(7), 1997.Google ScholarCross Ref
- Texas Instruments. TMS320C54x DSP Reference Set, volume 2: Mnemonic Instruction Set. 2001.Google Scholar
- W. Thies, M. Karczmarek, and S. Amarasinghe. StreamIt: A Language for Streaming Applications. In Proc. of the Int. Conf. on Compiler Construction (CC), 2002. Google ScholarDigital Library
- R. C. Whaley, A. Petitet, and J. J. Dongarra. Automated empirical optimizations of software and the ATLAS project. Parallel Computing, 27(1--2):3--35, 2001.Google Scholar
- J. Xiong. Automatic Optimization of DSP Algorithms. PhD thesis, Univ. of Illinois at Urbana-Champaign, 2001. Google ScholarDigital Library
- J. Xiong, J. Johnson, R. W. Johnson, and D. A. Padua. SPL: A language and compiler for DSP algorithms. In PLDI, 2001. Google ScholarDigital Library
Index Terms
- Linear analysis and optimization of stream programs
Recommendations
Linear analysis and optimization of stream programs
As more complex DSP algorithms are realized in practice, there is an increasing need for high-level stream abstractions that can be compiled without sacrificing efficiency. Toward this end, we present a set of aggressive optimizations that target linear ...
Optimizing stream programs using linear state space analysis
CASES '05: Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systemsDigital Signal Processing (DSP) is becoming increasingly widespread in portable devices. Due to harsh constraints on power, latency, and throughput in embedded environments, developers often appeal to signal processing experts to hand-optimize ...
Phased scheduling of stream programs
LCTES '03: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systemsAs embedded DSP applications become more complex, it is increasingly important to provide high-level stream abstractions that can be compiled without sacrificing efficiency. In this paper, we describe scheduler support for StreamIt, a high-level ...
Comments