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

在计算机编程中，“知识就是力量”--对要运行程序的数据和要执行程序的机器了解得越多，所能获得的效率就越高。然而，编写程序是为了处理所有输入数据，并在许多不同的机器上运行。运行时程序生成(RTPG)是程序员编写程序的一种技术，该程序的目的是在输入数据(或其中的某一部分)和机器已知的情况下在运行时编写另一个程序。这一想法及其产生显著效率改进的潜力多年来已为人所知，但各种技术问题阻碍了它的采用。最近的软件研究和计算机硬件的发展使我们能够解决这些问题。本研究开发了RTPG的工具和技术，并将其应用于一些重要的问题，并论证了该技术的实用性。大多数有实际意义的程序都是在大数据集上运行的，这对RTPG提出了特殊的挑战。此外，由于大型数据集加剧了众所周知的程序生成成本问题，PI以几种新颖的方式解决了这个问题。PI设计了一种用于程序生成的对象语言，该语言允许对片段进行编译时的预处理，以促进运行时优化。PI专门为计算机生成的程序(与普通的程序员编写的代码具有不同的特征)设计优化。最重要的是，PI采用自动调整技术，其中在安装时确定目标计算机的相关特性，并使用该技术来指导运行时程序生成过程。

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.