Dynamic prefetching of hot data streams

• US 7,058,936 B2
• Filed: 11/25/2002
• Issued: 06/06/2006
• Est. Priority Date: 11/25/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chilimbi, Trishul, Hirzel, Martin
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Wood, William H.
• Application Number:
  US10/304,306
• Publication Number:
  US 20040103408A1
• Time in Patent Office: 1,289 Days
• Field of Search: 717/130, 717/131, 717/154, 717/158
• 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 dynamically instrumenting a computer program 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:

creating instructions that detect when the prefix of elements in the stream have been fetched by the computer program;

creating instructions that prefetch elements in a suffix of the stream when the prefix is detected; and

instrumenting the computer program with the created instruction;

wherein a prefix is detected when a created instruction determines that an operation performed on two or more consecutive prefix element values is equivalent to a key value in a table.

2. The method of claim 1 further comprising:

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 the created instructions that detect the prefix of instructions in the stream, are created from a deterministic finite state machine that describes states for plural streams of data fetches.

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

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

6. A computer system for reducing data fetch latency by dynamically determining in advance, data object fetch requests that will be executed by a computer program before the fetch requests are made, the system comprising:

a central processing unit, a main memory and a secondary memory, transferring data and instructions via a bus;

a computer program executing in the system comprising fetching data elements in sequences;

an optimization program that is provided with plural sequences of data elements fetched by the computer program, and that pauses the executing computer program in order to inject instructions into the computer program that optimize the computer program'"'"'s performance as follows;

determine when a prefix of data elements in a sequence have been fetched by the computer program; and

prefetch a suffix of the data elements in the sequence upon making the determination;

wherein the prefix of data elements is determined to be fetched when an injected instruction determines that an operation performed on two or more consecutive prefix element values is equivalent to a key value in a table.

7. The system of claim 6 wherein the same prefix identifies two different suffixes, and both suffixes are prefetched upon making the determination.

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

9. The system of claim 6 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.

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

11. A computer readable medium comprising a method for performing an optimization on an executing computer program, the method comprising:

pausing the executing computer program;

constructing computer executable instructions that determine when a prefix of data fetches in a stream of data accesses have been fetched by the computer program;

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

injecting instructions into the computer program that direct execution to procedures containing the constructed executable instructions; and

resuming execution of the computer program;

wherein the prefix determination is made when an injected instruction determines that an operation performed on plural consecutive prefix element values corresponds with a key value in a table.

12. The computer readable medium of claim 11 wherein the instructions that determine prefix fetches comprise a series of state transitions to an accepting state, one such transition for each data fetch seen in the prefix.

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

14. The computer readable medium of claim 11 wherein the operation is an exclusive-or operation.

15. A computer implemented method of dynamically instrumenting a computer program 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:

creating instructions that detect when the prefix of elements in the stream have been fetched by the computer program;

creating instructions that prefetch elements in a suffix of the stream when the prefix is detected; and

instrumenting the computer program with the created instructions;

wherein instructions that detect when the prefix is fetched comprise a series of state transitions to an accepting state, one such transition for each data fetch seen in the prefix, and wherein elements in the prefix of elements comprise an address of a program counter and an address where a data object is fetched.

16. The method of claim 15 wherein a prefix is detected when a created instruction determines that an operation performed on elements in a stream corresponds with a key value in a table.

17. A computer system for reducing data fetch latency by dynamically determining in advance, data object fetch requests that will be executed by a computer program before the fetch requests are made, the system comprising:

a central processing unit, a main memory and a secondary memory, transferring data and instructions via a bus;

a computer program executing in the system comprising fetching data elements in sequences;

an optimization program that is provided with plural sequences of data elements fetched by the computer program, and that pauses the executing computer program in order to inject instructions into the computer program that optimize the computer program'"'"'s performance as follows;

determine when a prefix of data elements in a sequence have been fetched by the computer program; and

prefetch a suffix of the data elements in the sequence upon making the determination;

wherein instructions that determine when the prefix of data elements have been fetched comprise a series of state transitions to an accepting state, one such transition for each data fetch seen in the prefix, and wherein data elements in the prefix of data elements comprise an address of a program counter and an address of a data object.

18. The system of claim 17 wherein a prefix is determined when a created instruction determines that an operation performed on elements in a sequence corresponds with a key value in a table.

19. A computer readable medium comprising a method for performing an optimization on an executing computer program, the method comprising:

pausing the executing computer program;

constructing computer executable instructions that determine when a prefix of data fetches in a stream of data accesses have been fetched by the computer program;

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

injecting instructions into the computer program that direct execution to procedures containing the constructed executable instructions; and

resuming execution of the computer program;

wherein instructions that determine when the prefix of data fetches have been fetched comprise a series of state transitions to an accepting state, one such transition for each data fetch seen in the prefix, and wherein fetches in the prefix of data fetches comprise an address of a program counter and an address of a data object.

20. The computer readable medium of claim 19 wherein a prefix of data fetches in a stream of data accesses are determined to have been fetched when a constructed executable instruction determines that an operation performed on elements in a stream corresponds with a key value in a table.