Wavelet-based phase classification

ABSTRACT

Phase analysis has proven to be a useful method of summarizing the time-varying behavior of programs, with uses ranging from reducing simulation time to guiding run-time optimizations. Although phase classification techniques based on basic block vectors have shown impressive accuracies on SPEC benchmarks, commercial programs remain a significant 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 correlated with important performance degrading events (such as L2 misses). We examine the use of many different interval 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 address 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 metrics both in terms of accuracy and overhead.

REFERENCES

• 1: Ronald D. Barnes , Erik M. Nystrom , Matthew C. Merten , Wen-mei W. Hwu, Vacuum packing: extracting hardware-detected program phases for post-link optimization, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 2: C.H. Chen and G.G. Lee. Image segmentation using multiresolution wavelet analysis and expectation-maximization (EM) algorithm for digital mammography. International Journal of Imaging Systems and Technology, 8(5):491--504, 1997.
• 3: Abhinav Das , Jiwei Lu , Wei-Chung Hsu, Region Monitoring for Local Phase Detection in Dynamic Optimization Systems, Proceedings of the International Symposium on Code Generation and Optimization, p.124-134, March 26-29, 2006 [doi>10.1109/CGO.2006.39]
• 4: A. Dhodapkar and J. E. Smith. Dynamic microarchitecture adaptation via co-designed virtual machines. In International Solid State Circuits Conference, February 2002.
• 5: Ashutosh S. Dhodapkar , James E. Smith, Managing multi-configuration hardware via dynamic working set analysis, Proceedings of the 29th annual international symposium on Computer architecture, p.233, May 25-29, 2002, Anchorage, Alaska
• 6: Steve Dropsho , Alper Buyuktosunoglu , Rajeev Balasubramonian , David H. Albonesi , Sandhya Dwarkadas , Greg Semeraro , Grigorios Magklis , Michael L. Scott, Integrating Adaptive On-Chip Storage Structures for Reduced Dynamic Power, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.141, September 22-25, 2002
• 7: Evelyn Duesterwald , Calin Cascaval , Sandhya Dwarkadas, Characterizing and Predicting Program Behavior and its Variability, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.220, September 27-October 01, 2003
• 8: Lieven Eeckhout, John Sampson, and Brad Calder. Exploiting program microarchitecture independent characteristics and phase behavior for reduced benchmark suite simulation. In IEEE International Symposium on Workload Characterization (IISWC'05), Austin, TX, USA, October 6--8 2005.
• 9: Julinda Gllavata , Ralph Ewerth , Bernd Freisleben, Text Detection in Images Based on Unsupervised Classification of High-Frequency Wavelet Coefficients, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 1, p.425-428, August 23-26, 2004 [doi>10.1109/ICPR.2004.896]
• 10: Greg Hamerly, Erez Perelman, Jeremy Lau, and Brad Calder. SimPoint 3.0: Faster and more flexible program analysis. In Workshop on Modeling, Benchmarking, and Simulation, June 2005.
• 11: C. Isci and M. Martonosi. Identifying program power phase behavior using power vectors. In Workshop on Workload Characterization, September 2003.
• 12: Canturk Isci , Margaret Martonosi, Runtime Power Monitoring in High-End Processors: Methodology and Empirical Data, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.93, December 03-05, 2003
• 13: Charles E. Jacobs , Adam Finkelstein , David H. Salesin, Fast multiresolution image querying, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.277-286, September 1995 [doi>10.1145/218380.218454]
• 14: Jeremy Lau, Jack Sampson, Erez Perelman, Greg Hamerly, and Brad Calder. The strong correlation between code signatures and performance. In IEEE International Symposium on Performance Analysis of Systems and Software, March 2005.
• 15: J. Lau , S. Schoemackers , B. Calder, Structures for phase classification, Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, p.57-67, March 10-12, 2004
• 16: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 17: Priya Nagpurkar , Chandra Krintz , Timothy Sherwood, Phase-Aware Remote Profiling, Proceedings of the international symposium on Code generation and optimization, p.191-202, March 20-23, 2005 [doi>10.1109/CGO.2005.26]
• 18: Cristiano Pereira , Jeremy Lau , Brad Calder , Rajesh Gupta, Dynamic phase analysis for cycle-close trace generation, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084913]
• 19: Steven P. Reiss, Dynamic detection and visualization of software phases, Proceedings of the third international workshop on Dynamic analysis, p.1-6, May 17-17, 2005, St. Louis, Missouri
• 20: E. Salari and Z. Ling. Texture segmentation using hierarchical wavelet decomposition. Pattern Recognition, 28:1819--1824, Dec 1995.
• 21: Xipeng Shen , Yutao Zhong , Chen Ding, Locality phase prediction, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 22: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 23: Timothy Sherwood, Erez Perelman, Greg Hamerly, Suleyman Sair, and Brad Calder. Discovering and exploiting program phases. IEEE Micro, 23(6):84--93, Nov-Dec 2003.
• 24: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 25: Ram Srinivasan, Jeanine Cook, and Shaun Cooper. Fast, accurate microarchitecture simulation using statistical phase detection. In IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS'05), Austin, TX, USA, March 2005.
• 26: Eric J. Stollnitz , Tony D. DeRose , David H. Salesin, Wavelets for Computer Graphics: A Primer, Part 1, IEEE Computer Graphics and Applications, v.15 n.3, p.76-84, May 1995 [doi>10.1109/38.376616 ]
• 27: Michail Vlachos, Jessica Lin, Eamonn Keogh, and Dimitrios Gunopulos. A wavelet-based anytime algorithm for k-means clustering of time series. In Workshop on Clustering High Dimensional Data and its Applications, San Francisco, CA, May 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Measurement, Performance

Keywords:
optimization, phase analysis, phase classification, phases, program behavior, wavelets