Automatically characterizing large scale program behavior

ABSTRACT

Understanding program behavior is at the foundation of computer architecture and program optimization. Many programs have wildly different behavior on even the very largest of scales (over the complete execution of the program). This realization has ramifications for many architectural and compiler techniques, from thread scheduling, to feedback directed optimizations, to the way programs are simulated. However, in order to take advantage of time-varying behavior, we must first develop the analytical tools necessary to automatically and efficiently analyze program behavior over large sections of execution.Our goal is to develop automatic techniques that are capable of finding and exploiting the Large Scale Behavior of programs (behavior seen over billions of instructions). The first step towards this goal is the development of a hardware independent metric that can concisely summarize the behavior of an arbitrary section of execution in a program. To this end we examine the use of Basic Block Vectors. We quantify the effectiveness of Basic Block Vectors in capturing program behavior across several different architectural metrics, explore the large scale behavior of several programs, and develop a set of algorithms based on clustering capable of analyzing this behavior. We then demonstrate an application of this technology to automatically determine where to simulate for a program to help guide computer architecture research.

REFERENCES

• 1: A. Ben-Dor, R. Shamir, and Z. Yakhini. Clustering gene expression patterns. Journal of Computational Biology, 6:281-297, 1999.
• 2: Christopher M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, Inc., New York, NY, 1995
• 3: D. C. Burger and T. M. Austin. The simplescalar tool set, version 2.0. Technical Report CS-TR-97-1342, University of Wisconsin, Madison, June 1997.
• 4: Thomas M. Conte , Mary Ann Hirsch , Kishore N. Menezes, Reducing State Loss For Effective Trace Sampling of Superscalar Processors, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.468-477, October 07-09, 1996
• 5: Sanjoy Dasgupta, Experiments with Random Projection, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.143-151, June 30-July 03, 2000
• 6: G. Hamerly and C. Elkan. Learning the k in k-means. Technical Report CS2002-0716, University of California, San Diego, 2002.
• 7: J. Haskins and K. Skadron. Minimal subset evaluation: Rapid warm-up for simulated hardware state. In Proceedings of the 2001 International Conference on Computer Design, September 2001.
• 8: Jr Haskins , K. Skadron, Memory Reference Reuse Latency: Accelerated Sampled Microarchitecture Simulation, University of Virginia, Charlottesville, VA, 2002
• 9: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 10: Jean-Michel Jolion , Peter Meer , Samira Bataouche, Robust Clustering with Applications in Computer Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.8, p.791-802, August 1991 [doi>10.1109/34.85669]
• 11: R. E. Kass and L. Wasserman. A reference Bayesian test for nested hypotheses and its relationship to the schwarz criterion. Journal of the American Statistical Association, 90(431):928-934, 1995.
• 12: A. KleinOsowski, J. Flynn, N. Meares, and D. Lilja. Adapting the spec 2000 benchmark suite for simulation-based computer architecture research. In Proceedings of the International Conference on Computer Design, September 2000.
• 13: Thierry Lafage , André Seznec, Choosing representative slices of program execution for microarchitecture simulations: a preliminary application to the data stream, Workload characterization of emerging computer applications, Kluwer Academic Publishers, Norwell, MA, 2001
• 14: J. MacQueen. Some methods for classification and analysis of multivariate observations. In L. M. LeCam and J. Neyman, editors, Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 281-297, Berkeley, CA, 1967. University of California Press.
• 15: Sébastien Nussbaum , James E. Smith, Modeling Superscalar Processors via Statistical Simulation, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.15-24, September 08-12, 2001
• 16: Mark Oskin , Frederic T. Chong , Matthew Farrens, HLS: combining statistical and symbolic simulation to guide microprocessor designs, Proceedings of the 27th annual international symposium on Computer architecture, p.71-82, June 2000, Vancouver, British Columbia, Canada
• 17: Dan Pelleg , Andrew W. Moore, X-means: Extending K-means with Efficient Estimation of the Number of Clusters, Proceedings of the Seventeenth International Conference on Machine Learning, p.727-734, June 29-July 02, 2000
• 18: T. Sherwood and B. Calder. Time varying behavior of programs. Technical Report UCSD-CS99-630, UC San Diego, August 1999.
• 19: Timothy Sherwood , Erez Perelman , Brad Calder, Basic Block Distribution Analysis to Find Periodic Behavior and Simulation Points in Applications, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.3-14, September 08-12, 2001
• 20: T. Sherwood, S. Sair, and B. Calder. Phase tracking and prediction. Technical Report CS2002-0710, UC San Diego, June 2002.
• 21: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 22: Oren Zamir , Oren Etzioni, Web document clustering: a feasibility demonstration, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.46-54, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290956]