Automatically Characterizing Large Scale Program Behavior

Timothy Sherwood, Erez Perelman and Brad Calder
March 18, 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 complier techniques, from thread scheduling, to feedback directed optimizations, to the way that 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 {\em Basic Block Vectors}. In this paper we quantify the effectiveness of Basic Block Vectors in capturing program behavior across several different architectural metrics (such as cache hit rates), explore the large scale behavior of several programs, develop a set of algorithms based on clustering capable of analyzing this behavior and automatically breaking the execution into a set of classes. We then demonstrate an application of this technology to automatically determine where to simulate for a program to help guide computer architecture research.

How to view this document

The authors of these documents have submitted their reports to this technical report series for the purpose of non-commercial dissemination of scientific work. The reports are copyrighted by the authors, and their existence in electronic format does not imply that the authors have relinquished any rights. You may copy a report for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect the author's copyright. For information concerning the use of this document for other than research or instructional purposes, contact the authors. Other information concerning this technical report series can be obtained from the Computer Science and Engineering Department at the University of California at San Diego,

[ Search ]

This server operates at UCSD Computer Science and Engineering.
Send email to