Method and apparatus of prefetching streams of varying prefetch depth
First Claim
Patent Images
1. A method of prefetching streams of varying prefetch depth, comprising:
- monitoring a plurality of load requests from a processing unit for data in a prefetch buffer and determining an access pattern associated with the plurality of load requests;
adjusting a prefetch depth according to the access pattern; and
prefetching data of prefetch depth to the prefetch buffer;
wherein in response to an occurrence of a load miss on requested data contained in cache line n, determining whether the cache line n exists in the prefetch buffer,and if the cache line n exists in the prefetch buffer, fetching next cache line n+1 into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n+1 to true if the next cache line n+1 does not exist in the prefetch buffer,and if the cache line n does not exist in the prefetch buffer, checking a history buffer for an address associated with the cache line n and if the history buffer contains the address associated with the cache line n, fetching the cache line n into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n to true, and if the history buffer does not contain the address associated with the cache line n, inserting the address associated with the cache line n and an address associated with the cache line n+1 into the history buffer,and if the next cache line n+1 exists in the prefetch buffer, determining whether the access pattern is single memory stream access pattern or whether the prefetch on hit flag associated with the cache line n+1 is set to true andif the access pattern is single memory access pattern or the prefetch on hit flag associated with the cache line n+1 is set to true or both, fetching cache line n+2 into the prefetch buffer if the cache line n+2 is not in the prefetch buffer, and setting a prefetch on hit flag associated with the cache line n+2 to true, and resetting the prefetch on hit flag associated with the cache line n to false; and
if the access pattern is not single memory access pattern and the prefetch on hit flag associated with the cache line n+1 is not set to true, resetting the prefetch on hit flag associated with the cache line n to false.
2 Assignments
0 Petitions
Accused Products
Abstract
Method and apparatus of prefetching streams of varying prefetch depth dynamically changes the depth of prefetching so that the number of multiple streams as well as the hit rate of a single stream are optimized. The method and apparatus in one aspect monitor a plurality of load requests from a processing unit for data in a prefetch buffer, determine an access pattern associated with the plurality of load requests and adjust a prefetch depth according to the access pattern.
-
Citations
20 Claims
-
1. A method of prefetching streams of varying prefetch depth, comprising:
-
monitoring a plurality of load requests from a processing unit for data in a prefetch buffer and determining an access pattern associated with the plurality of load requests; adjusting a prefetch depth according to the access pattern; and prefetching data of prefetch depth to the prefetch buffer; wherein in response to an occurrence of a load miss on requested data contained in cache line n, determining whether the cache line n exists in the prefetch buffer, and if the cache line n exists in the prefetch buffer, fetching next cache line n+1 into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n+1 to true if the next cache line n+1 does not exist in the prefetch buffer, and if the cache line n does not exist in the prefetch buffer, checking a history buffer for an address associated with the cache line n and if the history buffer contains the address associated with the cache line n, fetching the cache line n into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n to true, and if the history buffer does not contain the address associated with the cache line n, inserting the address associated with the cache line n and an address associated with the cache line n+1 into the history buffer, and if the next cache line n+1 exists in the prefetch buffer, determining whether the access pattern is single memory stream access pattern or whether the prefetch on hit flag associated with the cache line n+1 is set to true and if the access pattern is single memory access pattern or the prefetch on hit flag associated with the cache line n+1 is set to true or both, fetching cache line n+2 into the prefetch buffer if the cache line n+2 is not in the prefetch buffer, and setting a prefetch on hit flag associated with the cache line n+2 to true, and resetting the prefetch on hit flag associated with the cache line n to false; and if the access pattern is not single memory access pattern and the prefetch on hit flag associated with the cache line n+1 is not set to true, resetting the prefetch on hit flag associated with the cache line n to false. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method of prefetching streams of varying prefetch depth, comprising:
-
receiving a load request from a processing unit; determining whether the load request follows a sequential access pattern of memory locations; for the load request that follows a sequential access pattern, increasing or maintaining a prefetch depth to have at least two additional cache lines adjacent to a cache line associated with the load request prefetched to a prefetch buffer; for the load request that does not follow a sequential access pattern, decreasing the prefetch depth if a previous load request was following a sequential access pattern; and prefetching data of the prefetch depth to the prefetch buffer, wherein in response to an occurrence of a load miss on requested data contained in cache line n, determining whether the cache line n exists in the prefetch buffer, and if the cache line n exists in the prefetch buffer, fetching next cache line n+1 into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n+1 to true if the next cache line n+1 does not exist in the prefetch buffer, and if the cache line n does not exist in the prefetch buffer, checking a history buffer for an address associated with the cache line n and if the history buffer contains the address associated with the cache line n, fetching the cache line n into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n to true, and if the history buffer does not contain the address associated with the cache line n, inserting the address associated with the cache line n and an address associated with the cache line n+1 into the history buffer, and if the next cache line n+1 exists in the prefetch buffer, determining whether the access pattern is single memory stream access pattern or whether the prefetch on hit flag associated with the cache line n+1 is set to true and if the access pattern is single memory access pattern or the prefetch on hit flag associated with the cache line n+1 is set to true or both, fetching cache line n+2 into the prefetch buffer if the cache line n+2 is not in the prefetch buffer, and setting a prefetch on hit flag associated with the cache line n+2 to true, and resetting the prefetch on hit flag associated with the cache line n to false. - View Dependent Claims (11, 12, 13, 14)
-
-
15. An apparatus for prefetching streams of varying prefetch depth, comprising:
-
a prefetch buffer operable to store prefetched data; a mode control logic operable to monitor a plurality of load requests from a processing unit for data in the prefetch buffer and to determine an access mode associated with the plurality of load requests; and a prefetch engine operable to adjust a prefetch depth according to the access mode to prefetch data of prefetch depth to the prefetch buffer, wherein in response to an occurrence of a load miss on requested data contained in cache line n, determining whether the cache line n exists in the prefetch buffer, and if the cache line n exists in the prefetch buffer, fetching next cache line n+1 into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n+1 to true if the next cache line n+1 does not exist in the prefetch buffer, and if the cache line n does not exist in the prefetch buffer, checking a history buffer for an address associated with the cache line n and if the history buffer contains the address associated with the cache line n, fetching the cache line n into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n to true, and if the history buffer does not contain the address associated with the cache line n, inserting the address associated with the cache line n and an address associated with the cache line n+1 into the history buffer, and if the next cache line n+1 exists in the prefetch buffer, determining whether the access pattern is single memory stream access pattern or whether the prefetch on hit flag associated with the cache line n+1 is set to true and if the access pattern is single memory access pattern or the prefetch on hit flag associated with the cache line n+1 is set to true or both, fetching cache line n+2 into the prefetch buffer if the cache line n+2 is not in the prefetch buffer, and setting a prefetch on hit flag associated with the cache line n+2 to true, and resetting the prefetch on hit flag associated with the cache line n to false; and if the access pattern is not single memory access pattern and the prefetch on hit flag associated with the cache line n+1 is not set to true, resetting the prefetch on hit flag associated with the cache line n to false. - View Dependent Claims (16, 17, 18, 19)
-
-
20. A system for prefetching streams of varying prefetch depth, comprising:
-
means for storing prefetched data; means for monitoring a plurality of load requests from a processing unit for data in the prefetch buffer and determining an access mode associated with the plurality of load requests; and means for adjusting a prefetch depth according to the access mode and prefetching data of prefetch depth to the prefetch buffer, wherein in response to an occurrence of a load miss on requested data contained in cache line n, determining whether the cache line n exists in the prefetch buffer, and if the cache line n exists in the prefetch buffer, fetching next cache line n+1 into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n+1 to true if the next cache line n+1 does not exist in the prefetch buffer, and if the cache line n does not exist in the prefetch buffer, checking a history buffer for an address associated with the cache line n and if the history buffer contains the address associated with the cache line n, fetching the cache line n into the prefetch buffer and setting a prefetch on hit flag associated with the cache line n to true, and if the history buffer does not contain the address associated with the cache line n, inserting the address associated with the cache line n and an address associated with the cache line n+1 into the history buffer, and if the next cache line n+1 exists in the prefetch buffer, determining whether the access pattern is single memory stream access pattern or whether the prefetch on hit flag associated with the cache line n+1 is set to true and if the access pattern is single memory access pattern or the prefetch on hit flag associated with the cache line n+1 is set to true or both, fetching cache line n+2 into the prefetch buffer if the cache line n+2 is not in the prefetch buffer, and setting a prefetch on hit flag associated with the cache line n+2 to true, and resetting the prefetch on hit flag associated with the cache line n to false; and if the access pattern is not single memory access pattern and the prefetch on hit flag associated with the cache line n+1 is not set to true, resetting the prefetch on hit flag associated with the cache line n to false.
-
Specification