Linear analysis and optimization of stream programs
Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2006
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/29668 |
| _version_ | 1826198226384977920 |
|---|---|
| author | Lamb, Andrew Allinson, 1980- |
| author2 | Saman P. Amarasinghe. |
| author_facet | Saman P. Amarasinghe. Lamb, Andrew Allinson, 1980- |
| author_sort | Lamb, Andrew Allinson, 1980- |
| collection | MIT |
| description | Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003. |
| first_indexed | 2024-09-23T11:01:23Z |
| format | Thesis |
| id | mit-1721.1/29668 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:01:23Z |
| publishDate | 2006 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/296682019-04-10T15:04:26Z Linear analysis and optimization of stream programs Lamb, Andrew Allinson, 1980- Saman P. Amarasinghe. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003. Includes bibliographical references (p. 123-127). 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 handtuned 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, a specialized caching strategy to remove redundant computations, and a method 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 yields the maximal benefit. We have completed a fully-automatic implementation of the above techniques as part of the StreamIt compiler. Using a suite of benchmarks, we show that our optimizations remove, on average, 86% of the floating point instructions required. In addition, we demonstrate an average execution time decrease of 450% and an 800% decrease in the best case. by Andrew Allinson Lamb. M.Eng. 2006-03-24T16:13:25Z 2006-03-24T16:13:25Z 2003 2003 Thesis http://hdl.handle.net/1721.1/29668 53833477 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 127 p. 8392987 bytes 8392794 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Lamb, Andrew Allinson, 1980- Linear analysis and optimization of stream programs |
| title | Linear analysis and optimization of stream programs |
| title_full | Linear analysis and optimization of stream programs |
| title_fullStr | Linear analysis and optimization of stream programs |
| title_full_unstemmed | Linear analysis and optimization of stream programs |
| title_short | Linear analysis and optimization of stream programs |
| title_sort | linear analysis and optimization of stream programs |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/29668 |
| work_keys_str_mv | AT lambandrewallinson1980 linearanalysisandoptimizationofstreamprograms |