Phase Tracking and Prediction Timothy Sherwood Suleyman Sair Brad Calder Department of Computer Science and Engineering University of California San Diego sherwood ssair calder cs ucsd edu Abstract In a single second a modern processor can execute billions of instructions Obtaining a bird s eye view of the behavior of a program at these speeds can be a difficult task when all that is available is cycle by cycle examination In many programs behavior is anything but steady state and understanding the patterns of behavior at run time can unlock a multitude of optimization opportunities In this paper we present a unified profiling architecture that can efficiently capture classify and predict phase based program behavior on the largest of time scales By examining the proportion of instructions that were executed from different sections of code we can find generic phases that correspond to changes in behavior across many metrics By classifying phases generically we avoid the need to identify phases for each optimization and enable a unified prediction scheme that can forecast future behavior Our analysis shows that our design can capture phases that account for over 80 of execution using less that 500 bytes of on chip memory 1 Introduction Modern processors can execute upwards of 5 billion instructions in a single second yet most architectural features target program behavior on a time scale of hundreds to thousands of instructions less than half a S While these optimizations can provide large benefits they are limited in their ability to see the program behavior in a larger context Recently there has been a renewed interest in examining the run time behavior of programs over longer periods of time 10 11 19 20 3 It has been shown that programs can have considerably different behavior depending on which portion of execution is examined More specifically it has been shown that many programs execute as a series of phases where each phase may be very different from the others while still having a fairly homogeneous behavior within a phase Taking advantage of this time varying behavior can lead to among other things improved power management cache control and more efficient simulation The primary goal of this research is the development of a unified run time phase detection and prediction mechanism that can be used to guide any optimization seeking to exploit large scale program behavior A phase of program behavior can be defined in several ways Past definitions are built around the idea of a phase being an interval of execution during which a measured program metric is relatively stable We extend this notion of a phase to include all similar sections of execution regardless of temporal adjacency Simply put if a phase of execution is correctly identified there should only be small variations between any two execution intervals identified as being part of the same phase A key point of this paper is that the phase behavior seen in any program metric is directly a function of the way the code is being executed If we can accurately capture this behavior at run time through the computation of a single metric we can use this to guide many optimization and policy decisions without duplicating phase detection mechanisms for each optimization In this paper we present an efficient run time phase tracking architecture that is based on detecting changes in the proportions of the code being executed In addition we present a novel phase prediction architecture that can predict not only when a phase change is about to occur but also the phase to which it is will transition Since our phase tracking implementation is based upon code execution frequencies it is independent of any individual architecture metric This allows our phase tracker to be used as a general profiling technique building up a profile or database of architecture information on a per phase basis to be used later for hardware or software optimization Independence from architecture metrics allows us to consistently track phase information as the program s behavior changes due to phasebased optimizations We demonstrate the effectiveness of our hardware based phase detection and classification architecture at automatically partitioning the behavior of the program into homogeneous phases of execution and to identify phase changes We show that the changes in many important metrics such as IPC and energy correlate very closely with the phase changes found by our metric We then evaluate the effectiveness of phase tracking and prediction for value profiling data cache reconfiguration and re configuring the width of the processor The rest of the paper is laid out as follows In Section 2 prior work related to phase based program behavior is discussed Simulation methodology and benchmark descriptions can be found in Section 3 Section 4 describes our phase tracking architecture The design and evaluation of the phase predictor are found in Section 5 Section 6 presents several potential applications of our phase tracking architecture Finally the results are summarized in Section 7 2 Related Work In this Section we describe work related to phase identification and phase based optimization In 19 we provided an initial study into the time varying behavior of programs showing that programs have repeatable phase based behavior over many hardware metrics cache behavior branch prediction value prediction address prediction IPC and RUU occupancy for all the SPEC 95 programs Looking at these metrics over time we found that many programs have repeating patterns and that important metrics tend to change at the same time These places represent phase boundaries In 20 we proposed that by profiling only the code that was executed over time we could automatically identify periodic and phase behavior in programs The goal was to automatically find the repeating patterns observed in 19 and the lengths periods of these patterns We then extended this work in 21 using techniques from machine learning to break the complete execution of the program into phases clusters by only tracking the code executed We found that intervals of execution grouped into the same phase had similar behavior across all the architecture metrics examined From this analysis we created a tool called SimPoint 21 which automatically identifies a small set of intervals of execution simulation points in a program to perform architecture simulations These simulation points provide an accurate and
View Full Document
Unlocking...