PREDICTIVE SEQUENTIAL PREFETCHING FOR DATA CACHING

• US 20120030431A1
• Filed: 07/27/2010
• Published: 02/02/2012
• Est. Priority Date: 07/27/2010
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Chirca, Kai, ANDERSON, Timothy D.
• Granted Patent: US 8,473,689 B2
• Time in Patent Office: Days
• 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;

allocating memory space for storing a first adjacent memory line that has an associated address that is adjacent to the associated address of the requested memory line;

accessing a prefetch indicator associated with the requested memory line to determine whether the first adjacent memory line has been prefetched; and

in response to a determination of the accessed prefetch indicator that the first adjacent memory has not been prefetched, prefetching the first adjacent memory line and storing an indication in the prefetch indicator associated with the requested memory line that the first adjacent memory line has been prefetched.

2. The method of claim 1, further comprising, in response to prefetching the first adjacent memory line, storing an indication in the prefetch indicator associated with the first adjacent memory line that a subsequent memory line has not been prefetched;

3. The method of claim 1, further comprising:

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

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

5. The method of claim 1, wherein the accessing a prefetch indicator associated with the requested memory line to determine whether the first 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.

6. The method of claim 5, further comprising, in response to prefetching the first adjacent memory line, storing an indication in the prefetch indicator associated with the first adjacent memory line that a third memory line having an associated memory address such that the associated memory address of the first adjacent memory line lies between the associated memory address of the third memory line and the associated memory address of the requested memory line.

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

8. The method of claim 7, further comprising:

setting a direction indicator associated with the prefetched first adjacent memory line to a forward direction.

9. The method of claim 8, further comprising:

determining that a second adjacent memory line that has an associated address that is less than the associated memory address of the requested line has not been prefetched;

prefetching the second adjacent memory line; and

setting a direction indicator associated with the first adjacent memory line to a backward direction.

10. The method of claim 9, further comprising:

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

retrieving the first prefetched line in response to a determination that the associated address of the requested subsequent memory line matches the associated address of the first adjacent memory line.

11. The method of claim 10, further comprising:

transferring the retrieved first prefetched line to a data cache of a first level.

12. The method of claim 10, further comprising:

accessing the direction indicator associated with the matched first adjacent memory line to determine the direction to which the direction indicator is set; and

prefetching a subsequent memory line in accordance with the determined direction.

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

accessing a prefetch indicator associated with a requested memory line or a memory line adjacent to the requested memory line to determine whether the requested memory line has been prefetched;

in response to a determination of the accessed prefetch indicator that the requested memory line has been prefetched, transferring the prefetched requested memory line to a first level cache;

in response to a determination of the accessed prefetch indicator that the requested memory line has not been prefetched, transferring the requested memory line from a lower level memory to a first level cache; and

in response to a determination of the accessed prefetch indicator that the first adjacent memory has not been prefetched, prefetching the first adjacent memory line and storing an indication in the prefetch indicator associated with the requested memory line that the first adjacent memory line has been prefetched.

14. The method of claim 13, wherein the adjacent memory line is prefetched in a direction indicated by an indication of directionality that is associated with the requested memory line.

15. 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 configured to prefetch an adjacent memory line from the lower level memory in response to the request for data wherein the adjacent memory line is a memory line that is adjacent to a first memory line that at least includes an address associated with the request for data, to store an indication that a memory line associated with an address associated with the requested data 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.

16. The system of claim 15 wherein the indication that a memory line associated with an address associated with the requested data has been prefetched is associated with the prefetched adjacent memory line.

17. The system of claim 15 wherein the indication that a memory line associated with an address associated with the requested data has been prefetched is associated with a prefetched first memory line.

18. The system of claim 15 wherein the lower level memory is a third level data cache.

19. The system of claim 15 wherein the prefetch buffer is configured to store an indication of directionality that is associated with a direction of the prefetch of the first memory line.

20. The system of claim 19 wherein the prefetch buffer is configured to prefetch the adjacent memory line in response to the indication of directionality that is associated with a direction of the prefetch of the first memory line.