Memory controller for non-sequentially prefetching data for a processor of a computer system

• US 8,356,142 B1
• Filed: 11/12/2003
• Issued: 01/15/2013
• Est. Priority Date: 11/12/2003
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Danilak, Radoslav
• Primary Examiner(s): Doan, Duc T
• Application Number:
  US10/712,520
• Time in Patent Office: 3,352 Days
• Field of Search: None
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch

Abstract

A memory controller for non-sequentially prefetching data for a processor of a computer system. The memory controller performs a method including the step of storing a plurality of address pairs in a table data structure, wherein the address pairs include a first address and a second address. The first address and the second address are non-sequential as fetched by a processor of a computer system. The address pairs are prioritized in accordance with a frequency of use for each of the address pairs. A system memory of the computer system is accessed and a plurality of cache lines corresponding to the address pairs are stored in a prefetch cache. Upon a cache hit during a subsequent access by the processor, data is transferred from the cache lines stored in the prefetch cache to the processor.

Claims

1. A method for implementing a non-sequential prefetch of data for a processor of a computer system, comprising:

storing a plurality of address pairs as leg entries in a table data structure of a memory controller that couples to the processor via a front side bus and couples to a system memory via a system memory bus, the address pairs including a first address and a second address, wherein the first address and the second address are non-sequential as fetched by a processor of a computer system due to a branch instruction execution;

prioritizing the address pairs in accordance with a frequency of use for each of the address pairs;

accessing system memory and storing a plurality of cache lines corresponding to the address pairs in a prefetch cache; and

upon a cache hit during a subsequent access by the processor, decrementing a confidence value upon a hit on the corresponding leg entry; and

incrementing the confidence value when there is no hit on the corresponding leg entry and a hit on the second address transferring data from the cache lines stored in the prefetch cache to the processor.

2. The method of claim 1 further comprising:

updating the table data structure by replacing an address pair having a lowest frequency of use with a new address pair in the table data structure.

3. The method of claim 1 further comprising:

maintaining a confidence value for each of the address pairs in the table data structure, the confidence value indicating the frequency of use for each of the address pairs.

4. The method of claim 3 further comprising:

decreasing the confidence value for a less frequently used address pair in the table data structure; and

updating the table data structure by deleting the less frequently used address pair if the confidence value decreases below a confidence threshold.

5. The method of claim 1 further comprising:

storing new cache lines in the prefetch cache corresponding to new address pairs in the table data structure as the table data structure is updated.

6. A device for implementing a non-sequential prefetch of data for a processor of a computer system, comprising:

a memory controller for interfacing the processor to a system memory via a system memory bus, wherein the memory controller couples to the processor via a front side bus;

a prefetch cache included in the memory controller, the prefetch cache configured to access the system memory to retrieve and store a plurality of cache lines; and

a leg table data structure included in the memory controller, the leg table data structure for storing a plurality of legs, wherein each of the legs includes a first address and a second address non-sequential to the first address due to a branch instruction execution;

the legs having a priority in accordance with a frequency of use for each of the legs; and

the legs controlling the storing of the plurality of cache lines in the prefetch cache, such that upon a cache hit during a subsequent access by the processor, decrementing a confidence value upon a hit on the corresponding leg; and

incrementing the confidence value when there is no hit on the corresponding leg and a hit on the second address data is transferred from the cache lines stored in the prefetch cache to the processor.

7. The device of claim 6 wherein the prefetch cache is configured to retrieve the cache lines when the system memory bus is not being used by the processor.

8. The device of claim 6 wherein the leg table data structure is configured to be updated by replacing a leg having a lowest frequency of use with a new leg in the leg table data structure.

9. The device of claim 6 further comprising:

a confidence value stored for each of the legs in the leg table data structure, wherein the confidence value indicates the frequency of use for each of the legs.

10. The device of claim 9 wherein the confidence value is configured to decrease for a less frequently used leg in the leg table data structure, and wherein the leg table data structure is updated by deleting the less frequently used leg if the respective confidence value decreases below a confidence threshold.

11. The device of claim 6 wherein the prefetch cache is configured to store new cache lines corresponding to new legs in the leg table data structure as the leg table data structure is updated.

12. The device of claim 6 wherein the prefetch cache is configured to delete cache lines from the prefetch cache on a least recently used basis.

13. The device of claim 6 wherein the prefetch cache is configured to delete cache lines from the prefetch cache on a first in first out basis.

14. The device of claim 6 wherein the cache lines are 64-bit cache lines.

15. The device of claim 6 wherein the cache lines are 128-bit cache lines.

16. The device of claim 6 wherein the prefetch cache is larger than 2 KB.

17. A system for implementing non-sequential data prefetching for a processor of a computer system, comprising:

a processor;

a system memory;

a prefetch cache configured to access the system memory to retrieve and store a plurality of cache lines, wherein the prefetch cache couples to the processor via a front side bus and couples to the system memory via a system memory bus; and

a memory controller coupled to the prefetch cache, the processor and the system memory, the memory controller for interfacing the processor to the system memory and implementing a method for non-sequential prefetching, comprising;

storing a plurality of legs in a leg table data structure, the legs including a first address and a second address, wherein the first address and the second address are non-sequential as fetched by a processor of a computer system due to a branch instruction execution;

prioritizing the legs in accordance with a frequency of use for each of the legs;

accessing system memory and storing a plurality of cache lines corresponding to the legs in a prefetch cache; and

upon a cache hit during a subsequent access by the processor, decrementing a confidence value upon a hit on the corresponding leg; and

incrementing the confidence value when there is no hit on the corresponding leg and a hit on the second address transferring data from the cache lines stored in the prefetch cache to the processor.

18. The system of claim 17 further comprising:

updating the leg table data structure by replacing a leg having a lowest frequency of use with a new leg in the leg table data structure.

19. The system of claim 17 further comprising:

maintaining a confidence value for each of the legs in the leg table data structure, the confidence value indicating the frequency of use for each of the legs.

20. The system of claim 19 further comprising:

decreasing the confidence value for a less frequently used leg in the leg table data structure; and

updating the leg table data structure by deleting the less frequently used leg if the confidence value decreases below a confidence threshold.

21. The system of claim 17 further comprising:

storing new cache lines in the prefetch cache corresponding to new legs in the leg table data structure as the leg table data structure is updated.

22. The system of claim 17 wherein the plurality of legs in the leg table data structure include a first address and a second address, and wherein the first address is used to index the leg table data structure and the second address is used to prefetch a corresponding cache line to the prefetch cache.