Dynamic temporal optimization framework

Abstract

A temporal profiling framework useful for dynamic optimization with hot data stream prefetching provides profiling of longer bursts and lower overhead. For profiling longer bursts, the framework employs a profiling phase counter, as well as a checking phase counter, to control transitions to and from instrumented code for sampling bursts of a program execution trace. The temporal profiling framework further intelligently eliminates some checks at procedure entries and loop back-edges, while still avoiding unbounded execution without executing checks for transition to and from instrumented code. Fast hot data stream detection analyzes a grammar of a profiled data reference sequence, calculating a heat metric for recurring subsequences based on length and number of unique occurrences outside of other hot data streams in the sequence with sufficiently low-overhead to permit use in a dynamic optimization framework.

1 . A method of detecting a hot data stream in a data reference sequence from sampled bursts of a program execution trace, the method comprising: 
 parsing the data reference sequence to extract a compressed grammar representation of the data reference sequence, the compressed grammar representation comprising a plurality of language elements each representing a number of occurrences of unique subsequences and related as a directed acyclic graph;    numbering the language elements according to a reverse postorder numbering;    calculating a heat measure of each language element related to a product of the length of the subsequence represented by the language element together with a number of occurrences of the subsequence represented by the language element that are not included in a heat measure of a predecessor language element according to the numbering that meets a hot criteria;    comparing the heat measure of each language element to the hot criteria; and    identifying the subsequence represented by a language element meeting the hot criteria as a hot data stream.    
     
     
         2 . The method of  claim 1  wherein the reverse postorder numbering results in non-terminal nodes being numbered such that whenever a non-terminal node is a child of another non-terminal node, a number assigned to the child node is greater.  
     
     
         3 . The method of  claim 1  wherein a data reference comprises a data pair of a program counter value which indicates an address of a data load or store instruction and a memory location accessed by the data load or store instruction.  
     
     
         4 . The method of  claim 1  wherein the hot data stream is a data reference subsequence in a profiled burst with a regularity magnitude that exceeds the hot criteria.  
     
     
         5 . The method of  claim 4  wherein the regularity magnitude of a data reference subsequence v, is defined as v.heat=v.length*v.frequency, where v.frequency is the number of non-overlapping occurrences of v in the profiled burst.  
     
     
         6 . The method of  claim 4  wherein the regularity magnitude of a non-terminal node A comprises A.heat=w A .length*A.coldUses, where A.coldUses is a number of times A occurs in a unique parse tree not counting occurrences in sub-trees belonging to hot non-terminals other than A.  
     
     
         7 . A dynamic optimizer comprising: 
 a temporal profiling framework insertion tool operating to modify a program to provide instrumentation for capturing a temporal data reference sequence for sampled bursts of an execution trace of the program;    a hot data stream detector operating to parse the temporal data reference sequence to extract a compressed grammar representation of the data reference sequence, the compressed grammar representation comprising a plurality of language elements each representing a number of occurrences of unique subsequences and related as a directed acyclic graph, the hot data stream detector further numbering the language elements according to a reverse postorder numbering, the hot data stream detector further calculating a heat measure of each language element related to a product of the length of the subsequence represented by the language element together with a number of occurrences of the subsequence represented by the language element that are not included in a heat measure of a predecessor language element according to the numbering that meets a hot criteria, the hot data stream detector further comparing the heat measure of each language element to the hot criteria, and identifying the subsequence represented by a language element meeting the hot criteria as a hot data stream; and    a prefetching code injector for inserting prefetching instructions at locations in the program corresponding to occurrences of the identified hot data stream in the data reference sequence.    
     
     
         8 . The dynamic optimizer of  claim 7  wherein the temporal profiling framework insertion tool modifies an executable binary version of the program.  
     
     
         9 . The dynamic optimizer of  claim 8  wherein the modified executable binary version of the program comprises a profiling phase counter and a checking phase counter controlling transitions to and from instrumented code for sampled bursts.  
     
     
         10 . The dynamic optimizer of  claim 7  wherein the reverse postorder numbering results in numbering language elements such that when a non-terminal language element is a child of another non-terminal language element, a number assigned to the child is greater.  
     
     
         11 . The dynamic optimizer of  claim 7  operating in phases comprising a profiling phase, analysis and optimization phase, and a hibernation phase.  
     
     
         12 . The dynamic optimizer of  claim 11  wherein the profiling phase comprises sampling bursts of the execution trace of the program.  
     
     
         13 . The dynamic optimizer of  claim 11  wherein the analysis and optimization phase comprises operation of the hot data stream detector.  
     
     
         14 . The dynamic optimizer of  claim 11  wherein the hibernation phase comprises the program executing as optimized with prefetch instructions.  
     
     
         15 . A computer-readable program carrying medium having a program carried thereon executable on a computer to perform a method of detecting a hot data stream in a data reference sequence from sampled bursts of a program execution trace, the method comprising: 
 parsing the data reference sequence to extract a compressed grammar representation of the data reference sequence, the compressed grammar representation comprising a plurality of language elements each representing a number of occurrences of unique subsequences and related as a directed acyclic graph;    numbering the language elements according to a reverse postorder numbering;    calculating a heat measure of each language element related to a product of the length of the subsequence represented by the language element together with a number of occurrences of the subsequence represented by the language element that are not included in a heat measure of a predecessor language element according to the numbering that meets a hot criteria;    comparing the heat measure of each language element to the hot criteria; and    identifying the subsequence represented by a language element meeting the hot criteria as a hot data stream.    
     
     
         16 . The computer-readable program carrying medium of  claim 15  wherein the reverse postorder numbering comprises non-terminal nodes being numbered such that when a non-terminal node is a child of another non-terminal node the child node is assigned a greater number.  
     
     
         17 . The computer-readable program carrying medium of  claim 15  wherein a data reference in a sequence comprises: 
 a program counter value which indicates an address of a data load or store instruction; and    a memory location accessed by the data load or store instruction.    
     
     
         18 . The computer-readable program carrying medium of  claim 15  wherein the hot data stream is a data reference subsequence in a profiled burst with a regularity magnitude that exceeds the hot criteria.  
     
     
         19 . The computer-readable program carrying medium of  claim 18  wherein the regularity magnitude of a data reference subsequence v comprises: 
 v.heat=v.length*v.frequency where v.frequency is the number of non-overlapping occurrences of v in the profiled burst.    
     
     
         20 . The computer-readable program carrying medium of  claim 18  wherein the regularity magnitude of a non-terminal node A comprises A.heat=w A .length*A.coldUses, where A.coldUses is the number of times A occurs in a unique parse tree not counting occurrences in sub-trees belonging to hot non-terminals other than A.