Discovering the Runtime Structure of Software with Probabilistic Generative Models Scott Richardson, Michael Otte, Michael C. Mozer, Amer Diwan, Daniel A. Connors Proceedings of the 2007 International Symposium on Neural Information Processing Systems Workshop for Statistical Learning Techniques for Solving Systems Problems (MLSys) December, 2007. 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. We thus consider a class of dynamical probabilistic models that explicitly captures the sequential structure of the program's basic block vector (BBV). Our expectation is that by modeling the sequential structure, we will obtain a more faithful representation of program execution phases, and consequently, will better estimate the program's runtime profile. We explore hidden Markov models, in which the observation at each time step corresponds to a BBV, and the hidden state corresponds to the program's latent phase. We explore two alternatives for the emission distribution: a multinomial and a Gaussian. We also explore a range of techniques for reducing the dimensionality of the basic-block vectors, picking simulation points, and estimating a particular profile metric given the simulation points. [ PDF ]