Accuracy-aware optimization of approximate programs

Many modern applications (such as multimedia processing, machine learning, and big-data analytics) exhibit a natural tradeoff between the accuracy of the results they produce and the application's execution time or energy consumption. These applications allow us to investigate new, more aggressive optimization approaches. This dissertation presents a foundation of program optimization systems that expose and profitably exploit tradeoffs between the accuracy of the results that the program produces and the time and energy required to produce those results. These systems apply accuracy-aware program transformations that intentionally change the semantics of optimized programs. A key challenge to applying accuracy-aware transformations is understanding the uncertainty that the transformations introduce into the program's execution. To address this challenge, this dissertation presents program analysis techniques that quantify the uncertainty introduced by program transformations. First, this dissertation identifies the properties of subcomputations that are amenable to loop perforation (an accuracy-aware transformation that skips loop iterations). Second, it presents how static analysis can derive expressions that characterize the frequency and magnitude of errors. Third, it presents a system that automatically applies accuracy-aware transformations by formulating accuracy-aware program optimization as standard mathematical optimization problems. The experimental results show that accuracy-aware transformations can help uncover significant performance and energy improvements with acceptable accuracy losses.

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

2015

Author dc:creator

• Misailović, Saša

Advisor dc:contributor.advisor

• Martin C. Rinard.

• 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/101577

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/101577