Discovering the Runtime Structure of Software with Probabilistic Generative Models

Modern computer systems have become so complex that understanding and predicting the performance of programs is a significant challenge. For instance, when designing microprocessor architectures, engineers must assess the trade-offs involved in allocating the on-die real estate (e.g., between the L1 cache, execution units, etc.) in order to achieve certain performance and power consumption targets. Typically, an experimental hardware architecture is emulated in software, which is extremely computationally inten-sive. Assessing the hardware’s runtime behavior, often referred to as its runtime profile and measured by cycles per instruction executed (CPI) or cache miss rate, requires cycle-accurate simulation at the functional level of the hard-ware. Consequently, researchers have resorted to picking portions of the program execution that are considered typical, called simulation points, and extrapolating from the detailed simulation of these points to the entire runtime profile. State-of-the-art algorithms attempt to strategically select a small set of simulation points that are characteristic of larger portions of program execution by exploiting the phase structure of a program. The idea underlying phase structure is that the execution dynamics of a large program can be understood in terms of a relatively small set of distinct patterns of program behavior. The execution trace is broken into short-duration intervals, and the goal is to assign a phase label to each interval such that the program behavior across all intervals with the same label is similar. Phases are determined from statistics that can be easily and quickly collected as the program executes at the instructio