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

在计算机编程中，“知识就是力量”--对程序运行的数据和执行程序的机器了解得越多，就能获得越高的效率。 然而，程序被编写来处理所有输入数据，并在许多不同的机器上运行。 运行时程序生成（RTPG）是一种技术，在这种技术中，程序员编写一个程序，其目的是在运行时编写另一个程序，当输入数据（或其某些部分）和机器已知时。 这个想法及其产生巨大效率提高的潜力已经知道很多年了，但是各种技术问题阻碍了它的采用。 最近的软件研究和计算机硬件的发展使我们能够解决这些问题。 本研究开发了RTPG的工具和技术，应用了RTPG的一些重要问题，并论证了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.