×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×