DYNAMIC TEMPORAL OPTIMIZATION FRAMEWORK

• US 20070083856A1
• Filed: 10/05/2006
• Published: 04/12/2007
• Est. Priority Date: 11/25/2002
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chilimbi, Trishul, Hirzel, Martin
• Application Number:
  US11/539,111
• Publication Number:
  US 20070083856A1
• Time in Patent Office: Days
• US Class Current: 717/128
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466

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.

Claims

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.