Predictive sequential prefetching for data caching

• US 8,473,689 B2
• Filed: 07/27/2010
• Issued: 06/25/2013
• Est. Priority Date: 07/27/2010
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Anderson, Timothy D., Chirca, Kai
• Primary Examiner(s): Rojas, Midys
• Application Number:
  US12/843,980
• Publication Number:
  US 20120030431A1
• Time in Patent Office: 1,064 Days
• Field of Search: 711/137, 711/146, 711/154, 711/156, 711/163, 711/204, 711/213, 711/E12.004
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6022 Using a prefetch buffer or dedicated prefetch cache
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

A system for prefetching memory in caching systems includes a processor that generates requests for data. A cache of a first level stores memory lines retrieved from a lower level memory in response to references to addresses generated by the processor'"'"'s requests for data. A prefetch buffer is used to prefetch an adjacent memory line from the lower level memory in response to a request for data. The adjacent memory line is a memory line that is adjacent to a first memory line that is associated with an address of the request for data. An indication that a memory line associated with an address associated with the requested data has been prefetched is stored. A prefetched memory line is transferred to the cache of the first level in response to the stored indication that a memory line associated with an address associated with the requested data has been prefetched.

Claims

1. A method for prefetching memory in caching systems, comprising:

receiving a request for a memory line having an associated address;

in response to a request for a memory line determining whether the memory line is stored in a prefetch buffer, the prefetch buffer having a plurality of prefetch buffer entries, each prefetch buffer entry including a data field for storing a corresponding memory line, an address field for storing an address corresponding to the memory line and an prefetch indicator field for storing an indication whether a memory line next adjacent to the corresponding memory line is stored in the prefetch buffer;

if the requested memory line is stored in the prefetch buffer supplying the requested memory line from the prefetch buffer;

if the requested memory line is not stored in the prefetch buffer

requesting the requested memory line from a next level memory, and

supplying the requested memory line;

following supply of the requested memory line, accessing the prefetch indicator field of the prefetch entry allocated to the requested memory line to determine whether the next adjacent memory line has been prefetched; and

in response to a determination of the accessed prefetch indicator field that indicates the next adjacent memory has not been prefetched

prefetching the next adjacent memory line from the next level memory,

allocating a prefetch buffer entry to the next adjacent memory line, and

storing the prefetched next adjacent memory line in the allocated prefetch buffer entry by storing in the data field the prefetched next adjacent memory line, storing in the address field the associated address and storing in the prefetch indicator field an indication that the memory line next adjacent to the corresponding memory line is not stored in the prefetch buffer, and

storing an indication in the prefetch indicator field of the prefetch buffer entry associated with the requested memory line that the next adjacent memory line has been prefetched.

2. The method of claim 1, further comprising:

storing the prefetched memory line in a prefetch buffer that is external to a set-associative cache.

3. The method of claim 2, wherein the prefetch buffer is fully associative.

4. The method of claim 1, wherein the accessing a prefetch indicator associated with the requested memory line to determine whether the next adjacent memory line has been prefetched is performed in response to a determination that the requested memory line is not stored in a cache of a first level.

5. The method of claim 1, wherein in the associated memory address of the next adjacent line is greater than the associated memory address of the requested line.

6. A system for prefetching memory in caching systems, comprising:

a processor that is configured to generate requests for data, wherein each request for data has an associated address that is included within at least one memory line;

a cache of a first level configured to store memory lines from a lower level memory, wherein each memory line is associated with at least one memory address of a request for data;

a prefetch buffer having a plurality of prefetch buffer entries, each prefetch buffer entry including a data field for storing a memory line, an address field for storing an address corresponding to the memory line and an indicator field for storing an indication whether a memory line next adjacent to the corresponding memory line is stored in the prefetch buffer, said prefetch buffer configured to prefetch a next adjacent memory line from the lower level memory in response to the request for data wherein the next adjacent memory line is a memory line that is adjacent to a requested memory line if the prefetch indicator field of the prefetch entry corresponding to the requested memory line indicates the next adjacent memory line has not been prefetched, to store an indication in the prefetch indicator field of the prefetch entry corresponding to the requested that a memory line that the next adjacent memory line has been prefetched; and

to transfer a prefetched memory line to the cache of the first level in response to the stored indication that a memory line associated with an address associated with the requested data has been prefetched.

7. A method for prefetching memory in caching systems, comprising:

receiving a request from a central processing unit for a memory line having an associated address;

determining whether the requested memory line is stored in a data cache;

if the requested memory line is stored in the data cache, supplying the requested memory line to the central processing unit from the data cache;

if the requested memory line is not stored in the data cache, determining whether the requested memory line is stored in a prefetch buffer, the prefetch buffer having a plurality of prefetch buffer entries, each prefetch buffer entry including a data field for storing a corresponding memory line, an address field for storing an address corresponding to the memory line and an prefetch indicator field for storing an indication whether a memory line next adjacent to the corresponding memory line is stored in the prefetch buffer

if the requested memory line is stored in the prefetch buffer, copying the requested memory line from the prefetch buffer into the cache and supplying the requested memory line to the central processing unit, and

if the requested memory line is not stored in the prefetch buffer, recalling the requested memory line from a lower level memory, storing the requested memory line from the lower level memory into the cache and supplying the requested memory line to the central processing unit;

if the requested memory line was not stored in the data cache and following supply of the requested memory line to the central processing unit

determining whether a next adjacent memory line to the requested memory line has been prefetched by accessing the prefetch indicator field of an entry in the prefetch buffer corresponding to the requested memory line, and

if the next adjacent memory has not been prefetched prefetching the next adjacent memory line from the next level memory,

storing the prefetched next adjacent memory line in the prefetch buffer, and

storing an indication in the prefetch indicator field associated with the requested memory line that the next adjacent memory line has been prefetched.

8. The method of claim 7, further comprising:

replacing entries within the cache according to a least recently used technique on a plurality of set associative ways; and

replacing entries within the prefetch buffer according to a first-in-first-out technique in a fully associative manner.