jmlr jmlr2006 jmlr2006-94 jmlr2006-94-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Greg Hamerly, Erez Perelman, Jeremy Lau, Brad Calder, Timothy Sherwood
Abstract: An essential step in designing a new computer architecture is the careful examination of different design options. It is critical that computer architects have efficient means by which they may estimate the impact of various design options on the overall machine. This task is complicated by the fact that different programs, and even different parts of the same program, may have distinct behaviors that interact with the hardware in different ways. Researchers use very detailed simulators to estimate processor performance, which models every cycle of an executing program. Unfortunately, simulating every cycle of a real program can take weeks or months. To address this problem we have created a tool called SimPoint that uses data clustering algorithms from machine learning to automatically find repetitive patterns in a program’s execution. By simulating one representative of each repetitive behavior pattern, simulation time can be reduced to minutes instead of weeks for standard benchmark programs, with very little cost in terms of accuracy. We describe this important problem, the data representation and preprocessing methods used by SimPoint, the clustering algorithm at the core of SimPoint, and we evaluate different options for tuning SimPoint. Keywords: k-means, random projection, Bayesian information criterion, simulation, SimPoint
D. Achlioptas. Database-friendly random projections. In PODS ’01: Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 274–281, New York, NY, USA, 2001. ACM Press. ISBN 1-58113-361-8. H. Akaike. A new look at the statistical model identification. IEEE Transactions on Automatic Control, 19: 716–723, 1974. M. Annavaram, R. Rakvic, M. Polito, J. Bouguet, R. Hankins, and B. Davies. The fuzzy correlation between code and performance predictability. In International Symposium on Microarchitecture, December 2004. R. E. Bellman. Adaptive Control Processes. Princeton University Press, 1961. M. Van Biesbrouck, L. Eeckhout, and B. Calder. Efficient sampling startup for uniprocessor and simultaneous multithreading simulation. In International Conference on High Performance Embedded Architectures and Compilers, November 2005. M. Van Biesbrouck, T. Sherwood, and B. Calder. A co-phase matrix to guide simultaneous multithreading simulation. In IEEE International Symposium on Performance Analysis of Systems and Software, March 2004. 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. D. Cheng, A. Gersho, B. Ramamurthi, and Y. Shoham. Fast search algorithms for vector quantization and pattern matching. Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, pages 9.11.1–9.11.4, 1984. S. Dasgupta. Experiments with random projection. In Uncertainty in Artificial Intelligence: Proceedings of the Sixteenth Conference (UAI-2000), pages 143–151, 2000. S. Dasgupta. How fast is k-means? In COLT, page 735, 2003. 376 U SING M ACHINE L EARNING TO G UIDE A RCHITECTURE S IMULATION C. Elkan. Using the triangle inequality to accelerate k-means. In ICML, pages 147–153, 2003. F. Farnstrom, J. Lewis, and C. Elkan. Scalability for clustering algorithms revisited. SIGKDD Explor. Newsl., 2(1):51–57, 2000. U. Fayyad, C. Reina, and P. Bradley. Initialization of iterative refinement clustering algorithms. In Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining (KDD), pages 194–198. AAAI Press, 1998. T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38: 293–306, 1985. G. Hamerly and C. Elkan. Learning the k in k-means. In Advances in NIPS, 2003. G. Hamerly, E. Perelman, and B. Calder. Comparing multinomial and k-means clustering for SimPoint. In Proceedings of the 2006 IEEE International Symposium on Performance Analysis of Systems and Software, 2006. D. Hochbaum and D. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180–184, 1985. P. Indyk, A. Amir, A. Efrat, and H H. Samet. Efficient algorithms and regular data structures for dilation, location and proximity problems. In Proceedings of the Annual Symposium on Foundations of Computer Science, pages 160–170, 1999. J. Lau, E. Perelman, and B. Calder. Selecting software phase markers with code structure analysis. In Proceedings of the International Symposium on Code Generation and Optimization, March 2006. J. Lau, E. Perelman, G. Hamerly, T. Sherwood, and B. Calder. Motivation for variable length intervals and hierarchical phase behavior. In IEEE International Symposium on Performance Analysis of Systems and Software, March 2005a. J. Lau, J. Sampson, E. Perelman, G. Hamerly, and B. Calder. The strong correlation between code signatures and performance. In IEEE International Symposium on Performance Analysis of Systems and Software, March 2005b. J. Lau, S. Schoenmackers, and B. Calder. Structures for phase classification. In IEEE International Symposium on Performance Analysis of Systems and Software, March 2004. J. Lau, S. Schoenmackers, and B. Calder. Transition phase classification and prediction. In 11th International Symposium on High Performance Computer Architecture, February 2005c. 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. J. McNames. Rotated partial distance search for faster vector quantization encoding. IEEE Signal Processing Letters, 7(9), 2000. A. Moore. The anchors hierarchy: Using the triangle inequality to survive high-dimensional data. In Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence, pages 397–405. AAAI Press, 2000. H. Patil, R. Cohn, M. Charney, R. Kapoor, A. Sun, and A. Karunanidhi. Pinpointing representative portions of large Intel Itanium programs with dynamic instrumentation. In International Symposium on Microarchitecture, December 2004. 377 H AMERLY, P ERELMAN , L AU , C ALDER AND S HERWOOD D. Pelleg and A. Moore. X-means: Extending K-means with efficient estimation of the number of clusters. In Proceedings of the 17th International Conf. on Machine Learning, pages 727–734, 2000. E. Perelman, G. Hamerly, and B. Calder. Picking statistically valid and early simulation points. In International Conference on Parallel Architectures and Compilation Techniques, September 2003. F. J. Provost and V. Kolluri. A survey of methods for scaling up inductive algorithms. Data Mining and Knowledge Discovery, 3(2):131–169, 1999. J. Rissanen. Modeling by shortest data description. Automatica, 14:465–471, 1978. K. Sanghai, T. Su, J. Dy, and D. Kaeli. A multinomial clustering model for fast simulation of computer architecture designs. In KDD, pages 808–813, 2005. G. Schwarz. Estimating the dimension of a model. The Annnals of Statistics, 6(2):461–464, 1978. T. Sherwood and B. Calder. Time varying behavior of programs. Technical Report UCSD-CS99-630, UC San Diego, August 1999. T. Sherwood, E. Perelman, and B. Calder. Basic block distribution analysis to find periodic behavior and simulation points in applications. In International Conference on Parallel Architectures and Compilation Techniques, September 2001. T. Sherwood, E. Perelman, G. Hamerly, and B. Calder. Automatically characterizing large scale program behavior. In 10th International Conference on Architectural Support for Programming, October 2002. T. Sherwood, S. Sair, and B. Calder. Phase tracking and prediction. In 30th Annual International Symposium on Computer Architecture, June 2003. P. Smyth. Clustering using Monte Carlo cross-validation. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, August 1996. 378