Phase DetectionMotivationBasic MethodologyOverviewSherwood et al. 2003Definition of a PhaseKey Program MetricsSingle Unified MetricMetric for ClassificationAdvantages of BBVsHardware ImplementationVisualization of the FootprintsWhat do we do with our footprint?Comparing FootprintsFinding a MatchOpportunityWithin Phase HomogeneityPhase PredictionSimple PredictionMarkov Model PredictorRun Length EncodingSlide 22Prediction AccuracyApplicationsFrequent Value LocalityCache Size AdaptationProcessor Width AdaptationSummary of BBV methodBottom LineShen et al. 2004Metric of InterestReuse DistanceSlide 33New Definition of PhaseReuse TraceWhy Offline Analysis?Phase Detection Process1) Record Reuse Trace2) Signal Processing3) Phase PartitioningMissing LinkPhase MarkersUsing PhasesSlide 44Negative ExamplesSlide 46Adaptive Cache ResizingCache Size ReductionsCache Size Reductions with 5% Miss IncreaseMemory RemappingMemory RemappingSummary of the locality-based methodSlide 53Overall ConclusionsOpportunitiesPhase DetectionJonathan WinterCasey SmithCS 61204/05/05Phase Detection 2 Jonathan Winter and Casey Smith Motivation•Large-scale phases exist (order of millions of instructions)–For many programs, if we look at any interesting metric (cache misses, IPC, etc.), we see repeating behavior–Call the regions with similar behavior “phases”•Knowledge of phase-based behavior can be used for adaptive optimization–Current hardware doesn’t exploit phase behaviors•For instance–A region of execution may only need a small cache—save power/increase performance by shrinking–A region of execution may benefit from data structure reorganizationPhase Detection 3 Jonathan Winter and Casey Smith Basic Methodology1) Identify phase boundaries2) Classify phases3) Determine what optimizations to perform for each phaseWhen can each step be performed? Run time, compile time, offlinePhase Detection 4 Jonathan Winter and Casey Smith Overview•We’ll focus two papers on phase detection–Sherwood, Sair, and Calder, “Phase Tracking and Prediction,” ISCA 2003– Shen, Zhong, and Ding, “Locality Phase Prediction,” ASPLOS 2004Phase Detection 5 Jonathan Winter and Casey Smith Sherwood et al. 2003•Classifies the behavior of a program into phases based on code execution•Finds strong correlations between code execution phases and important performance and energy metrics •Simulates hardware for real-time detection and prediction of phases•Demonstrates usefulness through a variety of optimization techniques made possible by phase detectionPhase Detection 6 Jonathan Winter and Casey Smith Definition of a Phase•Previously (stemming from Denning 1972), a phase was defined as an interval of execution where a measured program metric stayed relatively constant. •Sherwood et al. consider all sections of code with similar values for the program metric to be part of the same phase even if the intervals are spread out over the course of the programs execution.Phase Detection 7 Jonathan Winter and Casey Smith Key Program Metrics•Instructions per cycle (IPC), energy, branch prediction accuracy, data cache misses, instruction cache misses, L2 cache misses are all vital statistics for optimizing speed and power consumptionPhase Detection 8 Jonathan Winter and Casey Smith Single Unified Metric•Goal: find a single metric that–Uniquely distinguishes phases–Guides optimization and policy decisions•Need some section of code on which to measure this metric—pick 10M instructions–Much longer time span than typical architectural techniques handle–Long enough to capture large-scale behavior–Short enough to capture detailed phase behavior–Size of an OS timeslicePhase Detection 9 Jonathan Winter and Casey Smith Metric for Classification•Based on Basic Blocks–Basic blocks are a section of code with one entry point and one exit point•Basic Block Vector–Count the number of times each basic block is executed in the 10M interval–Entries in the vector are the product of the number times each basic block is executed and the block length (BB1*L1, BB2*L2, BB3*L3, …)–This vector is a signature of the phase which correlates well with other metrics of interest: IPC, cache misses, etc.Phase Detection 10 Jonathan Winter and Casey Smith Advantages of BBVs•Independent of architectural measures and thus unaffected by optimizations•Weighting biases the signatures to more frequently executed instructions•Creates unique signatures which execute the same code but in different proportionsPhase Detection 11 Jonathan Winter and Casey Smith Hardware Implementation•Don’t want to store and examine the whole vector: compress to a 32-entry vector (footprint)Phase Detection 12 Jonathan Winter and Casey Smith Visualization of the FootprintsFootprints for different intervals of gzipPhase Detection 13 Jonathan Winter and Casey Smith What do we do with our footprint? •Store a small sample of representative footprints as phase signatures•Compare the current footprint to previously stored footprints•If we have a close enough match, we classify them as the same phase•If not, we store the new footprint as the representative member of a new phasePhase Detection 14 Jonathan Winter and Casey Smith Comparing Footprints•To save space, only store the top 6 bits of each entry in the 32-vector–Counters were saturating 24-bit counters–The smallest value that the maximum entry could have would occur if all 10M instructions were distributed evenly across the 32 entries–In this case the top six bits means that a counter value of 10M/32 would have a value of 1•Distance between footprints is defined as the Manhattan distance: the sum of the absolute difference between corresponding entries in two vectorsPhase Detection 15 Jonathan Winter and Casey Smith Finding a Match•If the Manhattan distance is less than a threshold, two footprints are classified as being in the same phase•Determine thresholdby false positives/false negatives ascompared to an offlineoracle tool.•Threshold of 220 chosenPhase Detection 16 Jonathan Winter and Casey Smith Opportunity•These classification methods are oversimplified•Opportunity to apply better machine learning techniquesPhase Detection 17