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.
Runtime specialization optimizes programs based on partial information available only at runtime. It is applicable when some input data is used repeatedly while other input data varies. This technique has the potential of generating highly efficient codes. In this project, we have explored the potential for obtaining speedups for sparse matrix-dense vector multiplication using runtime specialization, in the case where a single matrix is to be multiplied by many vectors. We experiment with five methods involving runtime specialization, comparing them to state of the art methods that do not, such as INTEL MKL library. Our experiments using matrices from the Matrix Market and Florida collections and running on different architectures show that in most cases the specialized code runs faster than any version without specialization, between 1.46 to 1.78 on the average for 23 matrices and five different platforms. Among the evaluated methods, we have found that one of our methods can produce significant speedups when the number of distinct values is small. This is important, as this can be common in matrices that are derived from graphs. We have also found that the best method depends on the matrix and machine, as no method is the best for all matrices and machines. Thus, we have identified the main input characteristics that impact the performance and used machine learning techniques to predict among all the methods the one that will deliver the highest performance. We can also generate at runtime codes that ran as fast or sometimes even faster than the codes generated using an offline compiler, although in this case the matrix has to run for enough iterations to amortize the cost of runtime code generation. Overall, those matrices where the location of non-zeros is known way ahead of time can directly benefit from our results. For matrices whose shape is only known at runtime, our machine learning techniques together with runtime code generation will be useful if run for enough iterations.
