Phase Tracking and PredictionTimothy Sherwood Suleyman Sair Brad CalderDepartment of Computer Science and EngineeringUniversity of California, San Diego{sherwood,ssair,calder}@cs.ucsd.eduAbstractIn a single second a modern processor can execute billionsof instructions. Obtaining a bird’s eye view of the behavior of aprogram at these speeds can be a difficult task when all that isavailable is cycle by cycle examination. In many programs, be-havior is anything but steady state, and understanding the pat-terns of behavior, at run-time, can unlock a multitude of opti-mization opportunities.In this paper, we present a unified profiling architecture thatcan efficiently capture, classify, and predict phase-based pro-gram behavior on the largest of time scales. By examining theproportion of instructions that were executed from different sec-tions of code, we can find generic phases that correspond tochanges in behavior across many metrics. By classifying phasesgenerically, we avoid the need to identify phases for each opti-mization, and enable a unified prediction scheme that can fore-cast future behavior. Our analysis shows that our design cancapture phases that account for over 80% of execution using lessthat 500 bytes of on-chip memory.1 IntroductionModern processors can execute upwards of 5 billion instructionsin a single second, yet most architectural features target programbehavior on a time scale of hundreds to thousands of instruc-tions, less than half a µS. While these optimizations can providelarge benefits, they are limited in their ability to see the programbehavior in a larger context.Recently there has been a renewed interest in examin-ing the run-time behavior of programs over longer periods oftime [10, 11, 19, 20, 3]. It has been shown that programs canhave considerably different behavior depending on which por-tion of execution is examined. More specifically, it has beenshown that many programs execute as a series of phases, whereeach phase may be very different from the others, while still hav-ing a fairly homogeneous behavior within a phase. Taking ad-vantage of this time varying behavior can lead to, among otherthings, improved power management, cache control, and moreefficient simulation. The primary goal of this research is the de-velopment of a unified run-time phase detection and predictionmechanism that can be used to guide any optimization seekingto 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 in-terval of execution during which a measured program metric isrelatively stable. We extend this notion of a phase to include allsimilar sections of execution regardless of temporal adjacency.Simply put, if a phase of execution is correctly identified, thereshould only be small variations between any two execution in-tervals identified as being part of the same phase. A key point ofthis paper is that the phase behavior seen in any program metricis directly a function of the way the code is being executed. Ifwe can accurately capture this behavior at run-time through thecomputation of a single metric, we can use this to guide manyoptimization and policy decisions without duplicating phase de-tection mechanisms for each optimization.In this paper, we present an efficient run-time phase trackingarchitecture that is based on detecting changes in the propor-tions of the code being executed. In addition, we present a novelphase prediction architecture that can predict, not only when aphase change is about to occur, but also the phase to which itis will transition. Since our phase tracking implementation isbased upon code execution frequencies, it is independent of anyindividual architecture metric. This allows our phase tracker tobe used as a general profiling technique building up a profile ordatabase of architecture information on a per phase basis to beused later for hardware or software optimization. Independencefrom architecture metrics allows us to consistently track phaseinformation as the program’s behavior changes due to phase-based optimizations.We demonstrate the effectiveness of our hardware basedphase detection and classification architecture at automaticallypartitioning the behavior of the program into homogeneousphases of execution and to identify phase changes. We showthat the changes in many important metrics, such as IPC and en-ergy, correlate very closely with the phase changes found by ourmetric. We then evaluate the effectiveness of phase tracking andprediction for value profiling, data cache reconfiguration, andre-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 befound in Section 3. Section 4 describes our phase tracking ar-chitecture. The design and evaluation of the phase predictor arefound in Section 5. Section 6 presents several potential applica-tions of our phase tracking architecture. Finally, the results aresummarized in Section 7.2 Related WorkIn this Section we describe work related to phase identificationand phase-based optimization.In [19], we provided an initial study into the time varyingbehavior of programs, showing that programs have repeatablephase-based behavior over many hardware metrics – cache be-havior, branch prediction, value prediction, address prediction,IPC and RUU occupancy for all the SPEC 95 programs. Lookingat these metrics over time, we found that many programs haverepeating patterns, and that important metrics tend to change atthe same time. These places represent phase boundaries.In [20], we proposed that by profiling only the code that wasexecuted over time we could automatically identify periodic andphase behavior in programs. The goal was to automatically findthe repeating patterns observed in [19], and the lengths (peri-ods) of these patterns. We then extended this work in [21], usingtechniques from machine learning to break the complete exe-cution of the program into phases (clusters) by only tracking thecode executed. We found that intervals of execution grouped intothe same phase had similar behavior across all the architecturemetrics examined. From this analysis, we created a tool calledSimPoint [21], which automatically identifies a small set of in-tervals of execution (simulation points) in a program to performarchitecture
View Full Document
Unlocking...