Fourier-Motzkin with non-linear symbolic constant coefficients
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2017
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/106379 |
| _version_ | 1826215317947285504 |
|---|---|
| author | Suriana, Patricia A |
| author2 | Saman P. Amarasinghe. |
| author_facet | Saman P. Amarasinghe. Suriana, Patricia A |
| author_sort | Suriana, Patricia A |
| collection | MIT |
| description | Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. |
| first_indexed | 2024-09-23T16:23:35Z |
| format | Thesis |
| id | mit-1721.1/106379 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:23:35Z |
| publishDate | 2017 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1063792019-04-10T12:50:26Z Fourier-Motzkin with non-linear symbolic constant coefficients Suriana, Patricia A Saman P. Amarasinghe. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 57-58). The polyhedral framework is an elegant and useful system for reasoning about loop nests in programs, and is commonly used to perform complex loop transformations such as tiling and parallelization. However, several critical transformations introduce non-linear inequalities during code generation, which present difficulties for the polyhedral model. Proposals for extending the framework to deal with non-linear inequalities have generally been complex and are not used in current code generators. We propose a simple extension to Fourier-Motzkin elimination that deals with the specific case of non-linearity arising from symbolic constant coefficients, and show that this enables the polyhedral framework to deal with important cases that commonly occur in code generation. We build a framework, called NFM, that implements the extension and integrate the new system into Halide, an open-source domain-specific language compiler for image processing [13], which provides a more robust framework to perform computation on iteration domain such as merge, intersection, etc., and provides Halide a unified framework to perform more complex optimization schemes, such as diamond tiling. by Patricia A. Suriana. M. Eng. 2017-01-12T18:18:25Z 2017-01-12T18:18:25Z 2016 2016 Thesis http://hdl.handle.net/1721.1/106379 967656411 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 58 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Suriana, Patricia A Fourier-Motzkin with non-linear symbolic constant coefficients |
| title | Fourier-Motzkin with non-linear symbolic constant coefficients |
| title_full | Fourier-Motzkin with non-linear symbolic constant coefficients |
| title_fullStr | Fourier-Motzkin with non-linear symbolic constant coefficients |
| title_full_unstemmed | Fourier-Motzkin with non-linear symbolic constant coefficients |
| title_short | Fourier-Motzkin with non-linear symbolic constant coefficients |
| title_sort | fourier motzkin with non linear symbolic constant coefficients |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/106379 |
| work_keys_str_mv | AT surianapatriciaa fouriermotzkinwithnonlinearsymbolicconstantcoefficients |