SHF: Small: Run-Time Program Generation and Empirical Optimization

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

In programming computers, "knowledge is power" - the more that is known about the data on which a program is to operate, and the machine on which it is to execute, the greater the efficiency that can be obtained. However, programs are written to process all input data and run on many different machines. Run-time program generation (RTPG) is a technique in which the programmer writes a program whose purpose is to write another program at run time when the input data (or some part of it) and machine are known. This idea and its potential to produce dramatic efficiency improvements has been known for many years, but various technical problems have hampered its adoption. Recent software research and developments in computer hardware enable us to address those problems. This research develops tools and techniques for RTPG; applies them some important problems; and demonstrates the practicality of the technique. This work explores several critical problems in the application of RTPG. Most programs of practical interest operate on large data sets, which pose special challenges for RTPG. Further, since large data sets exacerbate the well-known problem of program generation cost, the PIs address that issue in several novel ways. The PIs design an object language for program generation that allows for compile-time preprocessing of fragments to facilitate run-time optimizations. The PIs design optimizations expressly for computer-generated programs (which have different characteristics from ordinary, programmer-written codes). Above all, the PIs employ the technique of auto-tuning, in which relevant characteristics of a target computer are determined at install time, and used to guide the run-time program generation process.