Dynamic prioritization of cache access

• US 8,782,346 B2
• Filed: 08/15/2012
• Issued: 07/15/2014
• Est. Priority Date: 12/12/2011
• Status: Expired due to Fees

• 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/586,518
• Publication Number:
  US 20130151784A1
• Time in Patent Office: 699 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 determining that a memory access request results in a cache miss and determining an amount of cache resources used to service cache misses within a past period in response to determining that the memory access request results in the cache miss. Some embodiments are further directed to determining that servicing the memory access request would increase the amount of cache resources used to service cache misses within the past period to exceed a threshold. In some embodiments, the threshold corresponds to reservation of a given amount of cache resources for potential cache hits. Some embodiments are further directed to rejecting the memory access request in response to the determining that servicing the memory access request would increase the amount of cache resources used to service cache misses within the past period to exceed the threshold.

Claims

1. A method comprising:

determining that a first memory access request results in a cache miss;

determining an amount of cache resources used to service cache misses within a past period in response to determining that the first memory access request results in the cache miss;

determining that servicing the first memory access request would increase the amount of cache resources used to service cache misses within the past period to exceed a threshold, wherein the threshold corresponds to reservation of a given amount of cache resources for potential cache hits;

rejecting the first memory access request in response to the determining that servicing the first memory access request would increase the amount of cache resources used to service cache misses within the past period to exceed the threshold; and

tentatively accepting a second memory access request after rejecting the first memory access request.

2. The method of claim 1, wherein the determining that servicing the first memory access request would increase the amount of cache resources used to service cache misses within the past period to exceed the threshold comprises:

determining a cache miss count for the past period; and

determining that the cache miss count exceeds the threshold, wherein the threshold represents a maximum portion of a plurality of cache state machines to be utilized to concurrently process cache misses.

3. The method of claim 1 wherein the determining that servicing the first memory access request would increase the amount of cache resources used to service cache misses within the past period to exceed the threshold comprises:

determining a cache hit count for the past period;

determining a cache miss count for the past period;

computing a ratio of the cache hit count to the cache miss count;

comparing the ratio to the threshold wherein the threshold represents a maximum portion of a plurality of cache state machines to be utilized to concurrently process cache misses; and

determining that the ratio exceeds the threshold.

4. The method of claim 1 further comprising:

tracking a rejection count of a number of rejections of the first memory access request;

after rejecting the first memory access request, determining that the rejection count exceeds a limit to the number of rejections of the first memory access request; and

servicing the first memory access request as a cache miss in response to determining that the rejection count exceeds the limit.

5. The method of claim 1, wherein the past period comprises a number of computer clock cycles prior to a current clock cycle during which the first memory access request is received.

6. The method of claim 5, wherein rejecting the first memory access request in response to the determining that servicing the first memory access request would increase the amount of cache resources used to service cache misses within the past period to exceed the threshold comprises delaying service of the first memory access request for a number of clock cycles subsequent to the current clock cycle.

7. A method comprising:

tentatively accepting a memory access request for service by at least one of a plurality of cache state machines;

determining that the memory access request results in a cache miss;

determining an amount of usage of the plurality of cache state machines within a past period;

determining 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; and

rejecting the memory access request for service by the at least one of the plurality of cache state machines in response to determining that the at least one of a plurality of cache state machines is to be reserved for the potential future cache hits.

8. The method of claim 7, wherein said determining the amount of usage of the plurality of cache state machines within the past period comprises computing a miss count of a number of cache misses that have occurred within a number of clock cycles of a computer clock prior to a current clock cycle when the memory access request is tentatively accepted.

9. The method of claim 7, wherein said determining that the at least one of the plurality of cache state machines is to be reserved for the potential cache hits comprises determining, based at least partially on the miss count, that the at least one of the plurality of cache state machines is to be reserved for the potential cache hits during subsequent clock cycles.

10. The method of claim 9, wherein said determining, based at least partially on the miss count, that the at least one of the plurality of cache state machines is to be reserved for the potential cache hits during the subsequent clock cycles comprises:

comparing the miss count to a threshold value that corresponds to a limit of the plurality of cache state machines to be used to concurrently service cache misses.

11. The method of claim 9, wherein said determining, based at least partially on the miss count, that the at least one of the plurality of cache state machines is to be reserved for the potential cache hits during the subsequent clock cycles comprises:

computing a ratio of a hit count to the miss count; and

comparing the ratio to a tolerance value that corresponds to reservation of a given amount of cache resources for potential cache hits.

12. The method of claim 7, wherein said determining 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 comprises:

computing a hit count of a number of cache hits that have occurred within the number of clock cycles of the computer clock prior to the current clock cycle,

computing a first value comprising dividing the hit count by the miss count,

computing a second value comprising dividing the hit count by a sum of the miss count plus one,

computing a third value comprising adding a tolerance factor to the second value, wherein the tolerance factor corresponds to a limit of concurrent usage of the plurality of cache state machines,

comparing the first value to the third value, and

determining to reject the memory access request for service by the at least one of the plurality of cache state machines in response to the comparing the first value to the third value.

13. The method of claim 7, wherein said rejecting the memory access request comprises:

preventing the memory access request from being serviced by the at least one of the plurality of cache state machines that tentatively accepts the memory access request.