Dynamic prioritization of cache access

• US 8,769,210 B2
• Filed: 12/12/2011
• Issued: 07/01/2014
• Est. Priority Date: 12/12/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bell, Robert H. Jr., Hua, Hong L., Maron, William A., Srinivas, Mysore S.
• Primary Examiner(s): PORTKA, GARY J
• Application Number:
  US13/323,076
• Publication Number:
  US 20130151788A1
• Time in Patent Office: 932 Days
• Field of Search: None
• US Class Current: 711/140
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 2212/1024 Latency reduction

Abstract

Some embodiments of the inventive subject matter are directed to a cache comprising a tracking unit and cache state machines. In some embodiments, the tracking unit is configured to track an amount of cache resources used to service cache misses within a past period. In some embodiments, each of the cache state machines is configured to, determine whether a memory access request results in a cache miss or cache hit, and in response to a cache miss for a memory access request, query the tracking unit for the amount of cache resources used to service cache misses within the past period. In some embodiments, the each of the cache state machines is configured to service the memory access request based, at least in part, on the amount of cache resources used to service the cache misses within the past period according to the tracking unit.

Claims

1. A cache comprising:

a cache directory;

a cache array; and

a cache controller coupled to the cache directory and the cache array, the cache controller comprising,

a tracking unit configured to track an amount of cache resources used to service cache misses within a past period, and

a plurality of cache state machines, wherein each of the plurality of cache state machines is configured to,

determine whether a memory access request results in a cache miss or cache hit,

in response to a cache miss for a memory access request, query the tracking unit for the amount of cache resources used to service cache misses within the past period, and

service the memory access request based, at least in part, on the amount of cache resources used to service the cache misses within the past period according to the tracking unit.

2. The cache of claim 1 wherein the tracking unit comprises at least one shift register and at least one counter, wherein the at least one shift register comprises a number of flip flops equivalent to a number of clock cycles that comprise the past period, wherein the at least one shift register is configured to track within each of the flip flops, a portion of the cache misses that occurs within each of the of clock cycles, and wherein the at least one counter is configured to add individual counts of the cache misses stored in each of the flip flops to generate a total cache miss count.

3. The cache of claim 1 wherein each of the plurality of cache state machines is configured to service the memory access request based, at least in part, on the amount of cache resources used to service the cache misses within the past period according to the tracking unit being configured to

request a count of the cache misses over a number of clock cycles from the tracking unit,

compare the count of the cache misses to a tolerance value that corresponds to reservation of a given amount of the plurality of cache state machines for potential cache hits, and

determine whether to reject the memory access request or perform a plurality of cache coherence operations in accordance with a cache miss in response to comparison of the count of the cache misses to the tolerance value.

4. The cache of claim 1 wherein each of the plurality of cache state machines is configured to service the memory access request based, at least in part, on the amount of cache resources used to service the cache misses within the past period according to the tracking unit being configured to

request a count of the cache misses over a number of clock cycles from the tracking unit,

request a count of cache hits over the number of clock cycles from the tracking unit,

compute a ratio of the count of the cache hits to the count of the cache misses,

compare the ratio to a threshold value that corresponds to a limit of the plurality of cache state machines to be used to concurrently service cache misses, and

determine whether to reject the memory access request or perform a plurality of cache coherence operations in accordance with a cache miss based on comparison of the ratio to the threshold value.

5. The cache of claim 1 wherein each of the plurality of cache state machines is configured to service the memory access request based, at least in part, on the amount of cache resources used to service the cache misses within the past period according to the tracking unit being configured to

request a count of the cache misses over a number of clock cycles from the tracking unit,

request a count of cache hits over the number of clock cycles from the tracking unit,

compute a first value that comprises count of the cache hits divided by the count of the cache misses,

compute a second value that comprises the count of cache hits divided by a sum of the count of cache misses plus one,

compute a third value that comprises the a sum of a tolerance factor to the second value, wherein the tolerance factor corresponds to a limit of the amount of cache resources used to service cache misses within the past period,

compare the first value to the third value, and

determine whether to reject the memory access request or perform a plurality of cache coherence operations in accordance with a cache miss based on comparison of the first value to the third value.

6. The cache of claim 1 wherein the each of the plurality of cache state machines is further configured to

determine a count value of one or more of a number of rejections of the memory access request and a number of rejections of memory access requests previous to the memory access request, and

service the memory access request based, at least in part, on the count value.

7. The cache of claim 6 wherein the each of the plurality of cache state machines is configured to service the memory access request based, at least in part, on the each of the plurality of cache state machines being configured to

determine that the count value exceeds a rejection count threshold, and

service the memory access request based on the count value exceeding the rejection count threshold.

8. An apparatus comprising:

a processor; and

a cache controller coupled with the processor, the cache controller configured to receive memory access requests from the processor, the cache controller comprising a plurality of cache state machines, wherein each of the plurality of cache state machines is configured to,

tentatively accept one of the memory access requests,

determine that the one of the memory access requests results in a cache miss,

determine an amount of usage of the plurality of cache state machines within a past period,

determine that at least one of the plurality of cache state machines is to be reserved for potential future cache hits based on the amount of usage of the plurality of cache state machines within the past period in response to determination that the one of the memory access requests results in the cache miss, and

reject the memory access request in response to determination that the at least one of the plurality of cache state machines is to be reserved for the potential future cache hits.

9. The apparatus of claim 8 further comprising a core interface unit configured to buffer the memory access requests, wherein the cache controller is configured to fetch the one of the memory access requests buffered in the core interface unit.

10. The apparatus of claim 8, wherein the past period comprises a number of computer clock cycles prior to a clock cycle from which the one of the memory access requests is tentatively accepted, and wherein the each of the plurality of cache state machines is configured to reject the memory access request being configured to delay service of the memory access request for a number of clock cycles subsequent to the clock cycle from which the memory access request is tentatively accepted.

11. The apparatus of claim 8, wherein the each of the plurality of cache state machines is configured to determine that the at least one of a plurality of cache state machines is to be reserved for potential future cache hits based on the amount of usage of the plurality of cache state machines within the past period being configured to

determine a first value that comprises one or more of a cache hit count for the past period, a cache miss count for the past period, and a ratio of a cache hit count for the past period to a cache miss count for the past period,

compare the first value to a second value that comprises at least a tolerance factor that corresponds to a limit of the plurality of cache state machines to be used to concurrently service cache misses, and

determine, based on comparison of the first value to the second value, that the at least one of the plurality of cache state machines is to be reserved for potential future cache hits.

12. The apparatus of claim 11, wherein the cache controller is further configured to

determine that a number of the plurality of cache state machines becomes inoperable, and adjust the tolerance factor based on the number of the plurality of the cache state machines that become inoperable.