Automatically characterizing large scale program behavior
Timothy Sherwood, Erez Perelman, Greg Hamerly et al. · ACM SIGPLAN Notices · 2002
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.
Cited by 105 works. doi:10.1145/605432.605403
Authors
References
- Some methods for classification and analysis of multivariate observations
- Neural Networks for Pattern Recognition
- Data clustering
- Proceedings of the fifth Berkeley symposium on mathematical statistics and probability.
- ATOM
- X-means: Extending K-means with Efficient Estimation of the Number of Clusters
- Clustering Gene Expression Patterns
- A Reference Bayesian Test for Nested Hypotheses and its Relationship to the Schwarz Criterion
- Web document clustering
- Robust clustering with applications in computer vision