An HMM Applied to Semi-Online Program Phase Analysis

Phase detection aims to identify the principle movements of a program by discovering the sections of a program’s execution that are similar. Phase prediction actively anticipates program operation. This information provides knowledge of a program’s behavioral patterns, which can then be used for analysis and optimization. We present two novel approaches to the problem of phase detection and prediction: a Vector Quantized hidden Markov model (VQ-HMM) and a Continuous Density hidden Markov model (CD-HMM). The performance of the models on the datasets varied widely. At their best, some models (defined by a set of model parameters) fit the data almost perfectly (> 90%), but when re-trained, could not consistently duplicate these results. However, certain parameter sets consistently produced models that reduced error by one fifth relative to a naïve model. The VQ-HMM performed better than the CD-HMM, but comparable to simple K-means clustering. In general, model performance is highly dependent on the disparit