Dynamic prefetching of hot data streams

• US 8,046,752 B2
• Filed: 11/15/2005
• Issued: 10/25/2011
• Est. Priority Date: 11/25/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hirzel, Martin, Chilimbi, Trishul
• Primary Examiner(s): Bullock, Jr.; Lewis
• Assistant Examiner(s): GOORAY, MARK A
• Application Number:
  US11/280,476
• Publication Number:
  US 20060070040A1
• Time in Patent Office: 2,170 Days
• Field of Search: None
• US Class Current: 717/158
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/45525 Optimisation or modification within the same instruction set architecture, e.g. HP Dynamo

Abstract

A method and system for creating and injecting code into a running program that identifies a hot data stream, and prefetching data elements in the stream so they are available when needed by the processor. The injected code identifies the first few elements in a hot data stream (i.e. the prefix), and prefetches the balance of the elements in the stream (i.e., the suffix). Since the hot data stream identification code and prefetch code is injected at run time, pointer related time-dependencies inherent in earlier prefetch systems are eliminated. A global deterministic finite state machine (DFSM) is used to help create conceptual logic used to generate the code injected into the program for prefix detection.

Claims

1. A computer implemented method of a computer system dynamically instrumenting a computer program executing on the computer system to detect that plural data fetches comprise a prefix of data fetches in a given stream of data fetches, and to prefetch a suffix of data fetches in the stream, the method comprising the computer system performing acts of:

during execution of the computer program;

gathering a data reference profile by profiling the executing computer program;

extracting a hot data stream of data accesses from a data reference profile, wherein the hot data stream comprises an ordered sequence of data accesses of at least a particular length;

pausing the executing computer program;

based at least in part on the hot data stream of data accesses from the data reference profile, constructing computer executable instructions that dynamically determine when during the execution of the computer program a prefix of data fetches in the hot data stream of data accesses have been fetched by the computer program, wherein the prefix of data fetches comprises a first partial sequence of elements in the hot data stream of data accesses;

wherein a data fetch of the prefix of data fetches comprises an address of a program counter of the executing program where a data fetch instruction is located, and an address where a data object is fetched;

wherein the instructions that dynamically determine when the prefix of data fetches have been fetched are constructed from a deterministic finite state machine that describes states for plural streams of data accesses, and the instructions that dynamically determine when the prefix of data fetches have been fetched comprise a series of state transitions to an accepting state, wherein the state transitions are based on data fetches included in the prefix of data fetches;

constructing computer executable instructions that prefetch in a suffix of the hot data stream when the prefix of data fetches is detected;

instrumenting the computer program with instructions that direct execution to procedures containing the constructed executable instructions for determining the prefix of data fetches and prefetching the suffix of the hot data stream; and

resuming execution of the computer program.

2. The method of claim 1 further comprising the computer system performing acts of:

pausing a thread of the computer program while instrumenting a procedure of the computer program;

resuming execution of the thread after completing the instrumentation.

3. The method of claim 1, wherein a state in the deterministic finite state machine comprises a stream identifier and a number of elements seen in the identified stream.

4. The method of claim 1, wherein each of the plural streams comprises an accepting state for that stream.

5. A computer readable storage medium comprising computer executable instructions for performing a method for performing an optimization on an executing computer program, the method comprising:

during execution of the computer program;

gathering a data reference profile by profiling the executing computer program;

extracting a hot data stream of data accesses from the data reference profile, wherein the hot data stream comprises an ordered sequence of data accesses of a predetermined minimum length;

pausing the executing computer program;

based at least in part on the hot data stream of data accesses from the data reference profile, constructing computer executable instructions that dynamically determine when during execution of the computer program a prefix of data fetches in the hot data stream of data accesses have been fetched by the computer program, wherein the prefix of data fetches comprises a first partial sequence of elements in the hot data stream of data accesses;

wherein data fetches comprise an address of a program counter of the executing program where a data fetch instruction is located, and an address where a data object is fetched;

wherein the instructions that, dynamically determine when the prefix of data fetches have been fetched are constructed from a deterministic finite state machine that describes states for plural streams of data accesses, and comprise a series of state transitions to an accepting state, wherein the state transitions are based on data fetches seen in the prefix of data fetches;

constructing computer executable instructions that prefetch a suffix of the hot data stream;

injecting instructions into the computer program that direct execution to procedures containing the constructed executable instructions for determining said prefix and prefetching said suffix of said hot data stream; and

resuming execution of the computer program.

6. The computer readable medium of claim 5 wherein the prefix determination is made when an injected instruction determines that an operation performed on two consecutive prefix element values is equivalent to a key value in a table.

7. The computer readable medium of claim 6 wherein the operation is an exclusive-or operation.

8. The computer readable medium of claim 5 further comprising:

removing the injected instructions in the computer program that direct execution to procedures containing the constructed executable instructions.

9. A computer system, the computer system comprising:

a central processing unit and memory, the memory comprising computer executable instructions causing the computer system to perform a method, the method comprising;

during execution of a computer program executing on the computer system;

gathering a data reference profile by profiling the executing computer program;

extracting a hot data stream of data accesses from the data reference profile, wherein the hot data stream comprises an ordered sequence of data accesses of at least a particular length;

pausing the executing computer program;

based at least in part on the hot data stream of data accesses from the data reference profile, constructing computer executable instructions that dynamically determine when during execution of the computer program a prefix of data fetches included in the hot data stream of data accesses have been fetched by the computer program, wherein the prefix of data fetches comprises a partial sequence of elements in the hot data stream of data accesses;

wherein a data fetch of the prefix of data fetches comprises an address of a program counter of the executing program where a data fetch instruction is located, and an address where a data object is fetched;

wherein the instructions that dynamically determine when the prefix of data fetches have been fetched are constructed from a deterministic finite state machine that describes states for plural streams of data accesses, and the instructions that dynamically determine when the prefix of data fetches have been fetched comprise a series of state transitions to an accepting state, wherein the state transitions are based on data fetches included in the prefix of data fetches;

constructing computer executable instructions that prefetch a suffix of the hot data stream;

injecting instructions into the computer program that direct execution to procedures containing the constructed executable instructions for determining the prefix of data fetches and prefetching the suffix of the hot data stream; and

resuming execution of the computer program.

10. The computer system of claim 9 wherein the same prefix of data fetches identifies two different suffixes, and both suffixes are prefetched upon making the determination.

11. The computer system of claim 9 wherein prefix determination is a series of state transitions to an accepting state, one such transition for each data element in the prefix.

12. The computer system of claim 9 wherein each data element comprises an address of the program counter where the data fetch instruction is located, and an address where the data object is fetched.

13. The computer system of claim 9 wherein the prefix determination is made when an injected instruction determines that an operation performed on two consecutive prefix element values is equivalent to a key value in a table.

14. The computer system of claim 9 wherein the prefix length is two and the balance of the data elements in the sequence is at least 8 elements.