Wavelet-based phase classification

Phase analysis has proven to be a useful method of summa-rizing the time-varying behavior of programs, with uses rang-ing from reducing simulation time to guiding run-time op-timizations. Although phase classification techniques based on basic block vectors have shown impressive accuracies on SPEC benchmarks, commercial programs remain a signifi-cant challenge due to their complex behaviors and multiple threads. Some behaviors, such as L2 cache misses, may have less correlation with the code and therefore are much harder to capture with basic block frequency vectors. Comparing the similarity of two or more intervals requires a good metric, one that is not only fast enough to analyze the full execution of the program, but that is also highly cor-related with important performance degrading events (such as L2 misses). We examine the use of many different in-terval similarity metrics and their uses for program phase analysis across a range of commercial applications and show that there is still significant room for improvement. To ad-dress this problem, we introduce a novel wavelet-based phase classification scheme that captures and compares images of memory behavior in two or more dimensions. Over a set of five commercial applications, we show that a wavelet-based scheme can strictly outperform a broad range of prior met-rics both in terms of accuracy and overhead