Method of cache prefetching that increases the hit rate of a next faster cache
The size of a cache is modestly increased so that a short pointer to a predicted next memory address in the same cache is added to each cache line in the cache. In response to a cache hit, the predicted next memory address identified by the short pointer in the cache line of the hit along with an associated entry are pushed to a next faster cache when a valid short pointer to the predicted next memory address is present in the cache line of the hit.
1. A method of cache prefetching, the method comprising:
determining whether a cache has received a read request from a next faster cache, the read request including a currently requested memory address;
determining whether the currently requested memory address is stored in the cache when the read request has been received;
outputting an entry associated with the currently requested memory address to the next faster cache when the currently requested memory address is stored in the cache;
determining whether a cache line with the currently requested memory address has a valid short pointer pointing to a predicted next memory address; and
pushing the predicted next memory address and an entry associated with the predicted next memory address to the next faster cache in response to determining that the cache line with the currently requested memory address has the valid short pointer.
2. The method of claim 1 , further comprising determining whether a cache line with a previously requested memory address has a valid short pointer pointing to the currently requested memory address.
3. The method of claim 2 , further comprising setting a confidence bit or increasing a multi-bit confidence value when the cache line with the previously requested memory address has the valid short pointer pointing to the currently requested memory address.
4. The method of claim 2 , further comprising updating the cache line with the previously requested memory address so that the valid short pointer points to the currently requested memory address when the cache line with the previously requested memory address does not have the valid short pointer pointing to the currently requested memory address.
5. The method of claim 4 , further comprising determining whether a response to a read request sent to a next slower memory or cache has been received.
6. The method of claim 5 , further comprising storing a memory address and an entry incoming from the next slower memory or cache when the response has been received, and outputting the entry incoming from the next slower memory or cache to the next faster cache.
7. The method of claim 1 , wherein the cache stores a plurality of cache lines, and wherein the valid short pointer points to another location in the cache.
8. A computer system, comprising:
a memory; and
a processor coupled to the memory to execute instructions stored in the memory, the processor configured to:
determine whether a cache has received a read request from a next faster cache, the read request including a currently requested memory address;
determine whether the currently requested memory address is stored in the cache when the read request has been received;
output an entry associated with the currently requested memory address to the next faster cache when the currently requested memory address is stored in the cache;
determine whether a cache line with the currently requested memory address has a valid short pointer pointing to a predicted next memory address; and
push the predicted next memory address and an entry associated with the predicted next memory address to the next faster cache in response to a determination that the cache line with the currently requested memory address has the valid short pointer.
9. The computer system of claim 8 , wherein the processor is further configured to determine whether a cache line with a previously requested memory address has a valid short pointer pointing to the currently requested memory address.
10. The computer system of claim 9 , wherein the processor is further configured to set a confidence bit or increase a multi-bit confidence value when the cache line with the previously requested memory address has the valid short pointer pointing to the currently requested memory address.
11. The computer system of claim 9 , wherein the processor is further configured to update the cache line with the previously requested memory address so that the valid short pointer points to the currently requested memory address when the cache line with the previously requested memory address does not have the valid short pointer pointing to the currently requested memory address.
12. The computer system of claim 11 , wherein the processor is further configured to determine whether a response to a read request sent to a next slower memory or cache has been received.
13. The computer system of claim 12 , wherein the processor is further configured to store a memory address and an entry incoming from the next slower memory or cache when the response has been received, and outputting the entry incoming from the next slower memory or cache to the next faster cache.
14. The computer system of claim 8 , wherein the cache stores a plurality of cache lines, and wherein the valid short pointer points to another location in the cache.
15. A non-transitory computer-readable medium having computer-readable instructions stored thereon which, when executed by a processor, cause the processor to execute a method of cache prefetching, the method comprising:
determining whether a cache has received a read request from a next faster cache, the read request including a currently requested memory address;
determining whether the currently requested memory address is stored in the cache when the read request has been received;
outputting an entry associated with the currently requested memory address to the next faster cache when the currently requested memory address is stored in the cache;
determining whether a cache line with the currently requested memory address has a valid short pointer pointing to a predicted next memory address; and
pushing the predicted next memory address and an entry associated with the predicted next memory address to the next faster cache in response to determining that the cache line with the currently requested memory address has the valid short pointer.
16. The non-transitory computer-readable medium of claim 15 , wherein the method further comprises determining whether a cache line with a previously requested memory address and an entry to be pushed has a valid short pointer pointing to the currently requested memory address.
17. The non-transitory computer-readable medium of claim 16 , wherein the method further comprises setting a confidence bit or increasing a multi-bit confidence value when the cache line with the previously requested memory address has the valid short pointer pointing to the currently requested memory address.
18. The non-transitory computer-readable medium of claim 16 , wherein the method further comprises updating the cache line with the previously requested memory address so that the valid short pointer points to the currently requested memory address when the cache line with the previously requested memory address does not have the valid short pointer pointing to the currently requested memory address.
19. The non-transitory computer-readable medium of claim 18 , wherein the method further comprises determining whether a response to a read request sent to a next slower memory or cache has been received.
20. The non-transitory computer-readable medium of claim 15 , wherein the cache stores a plurality of cache lines, and wherein the valid short pointer points to another location in the cache.