Fourier-Motzkin with non-linear symbolic constant coefficients

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.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2016

Author dc:creator

• Suriana, Patricia A

Advisor dc:contributor.advisor

• Saman P. Amarasinghe.

• Electrical Engineering and Computer Science.

Statement dc:rights

• 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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/106379

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/106379