Logical reasoning for approximate and unreliable computation

Improving program performance and resilience are long-standing goals. Traditional approaches include a variety of transformation, compilation, and runtime techniques that share the common property that the resulting program has the same semantics as the original program. However, researchers have recently proposed a variety of new techniques that set aside this traditional restriction and instead exploit opportunities to change the semantics of programs to improve performance and resilience. Techniques include skipping portions of a program's computation, selecting different implementations of program's subcomputations, executing programs on unreliable hardware, and synthesizing values to enable programs to skip or execute through otherwise fatal errors. A major barrier to the acceptance these techniques in both the broader research community and in industrial practice is the challenge that the resulting programs may exhibit behaviors that differ from that of the original program, potentially jeopardizing the program's resilience, safety, and accuracy. This thesis presents the first general programming systems for precisely verifying and reasoning about the programs that result from these techniques. This thesis presents a programming language and program logic for verifying worst-case properties of a transformed program. Specifically the framework, enables verifying that a transformed program satisfies important assertions about its safety (e.g., that it does not access invalid memory) and accuracy (e.g., that it returns a result within a bounded distance of that of the original program). This thesis also presents a programming language and automated analysis for verifying a program's quantitative reliability - the probability the transformed program returns the same result as the original program - when executed on unreliable hardware. The results of this thesis, which include programming languages, program logics, program analysis, and applications thereof, present the first steps toward reaping the benefits of changing the semantics of programs in a beneficial yet principled way.

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

• Carbin, Michael (Michael James)

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/99813

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/99813