Dynamic prefetching of hot data streams

• US 20060070040A1
• Filed: 11/15/2005
• Published: 03/30/2006
• Est. Priority Date: 11/25/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chilimbi, Trishul, Hirzel, Martin
• Granted Patent: US 8,046,752 B2
• Time in Patent Office: Days
• US Class Current: 717/130
• 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.

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.

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 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.

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

12. 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.

13. The computer readable medium of claim 12 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.

14. The computer readable medium of claim 13 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.

15. The computer readable medium of claim 12 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.

16. The computer readable medium of claim 12 wherein the operation is an exclusive-or operation.