DYNAMIC PRIORITIZATION OF CACHE ACCESS

• US 20140258642A1
• Filed: 05/21/2014
• Published: 09/11/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.
• Granted Patent: US 9,563,559 B2
• Time in Patent Office: Days
• US Class Current: 711/141
• 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 operations that include determining that an access request to a computer memory results in a cache miss. In some examples, the operations further include determining an amount of cache resources used to service additional cache misses that occurred within a period prior to the cache miss. Furthermore, in some examples, the operations further include servicing the access request to the computer memory based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss.

Claims

1. A method comprising:

determining that an access request to a computer memory results in a cache miss;

determining an amount of cache resources used to service additional cache misses that occurred within a period prior to the cache miss; and

servicing the access request to the computer memory based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss.

2. The method of claim 1 further comprising:

during the period prior to the cache miss, storing, in a number of flip flops equivalent to a number of clock cycles of the period, a portion of the cache misses that corresponds to each of the clock cycles; and

adding together the values in each of the flip flops.

3. The method of claim 1, wherein the servicing the access request to the computer memory based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises:

determining a count of the additional cache misses over a number of clock cycles;

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

in response to the comparing, determining to either reject the access request to the computer memory or perform a plurality of cache coherence operations in accordance with the cache miss.

4. The method of claim 1, wherein the servicing the access request to the computer memory based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises:

determining a count of the additional cache misses over a number of clock cycles that occurred during the period;

determining a count of cache hits over the number of clock cycles;

computing a ratio of the count of the cache hits to the count of the additional cache misses;

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

based on the comparing the ratio to the threshold value, determining to either reject the access request to the computer memory or perform a plurality of cache coherence operations in accordance with the cache miss.

5. The method of claim 1, wherein the servicing the access request to the computer memory based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises:

determining a count of the additional cache misses over a number of clock cycles that occurred during the period;

determining a count of cache hits over the number of clock cycles;

computing a first value that comprises a count of the cache hits divided by the count of the additional cache misses;

computing a second value that comprises the count of the cache hits divided by a sum of the count of the additional cache misses plus one;

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

comparing the first value to the third value; and

based on the comparing the first value to the third value, determining to either reject the memory access request or perform a plurality of cache coherence operations in accordance with a cache miss.

6. The method of claim 1 further comprising:

determining a count value of one or more of a number of rejections of the access request and a number of rejections of additional access requests previous to the access request; and

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

7. The method of claim 6, wherein the servicing the access request to the computer memory based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises:

determining that the count value exceeds a rejection count threshold; and

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

8. An apparatus comprising:

one or more processors; and

one or more computer-readable storage devices configured to store instructions, which when executed by at least one of the one or more processors, are configured to

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

in response to a cache miss for the memory access request, determine an amount of cache resources used to service additional cache misses that occurred within a period prior to the cache miss; and

service the memory access request based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss.

9. The apparatus of claim 8 further comprising 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 period, wherein the at least one shift register is configured to track within each of the flip flops, a portion of the additional 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.

10. The apparatus of claim 8, wherein the one or more computer-readable storage devices configured to store the instructions, which when executed by at least one of the one or more processors, are configured to service the memory access request based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises one or more computer-readable storage devices configured to store instructions, which when executed by at least one of the one or more processors, are configured to:

determine a count of the additional cache misses over a number of clock cycles;

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

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

11. The apparatus of claim 8, wherein the one or more computer-readable storage devices configured to store the instructions, which when executed by at least one of the one or more processors, are configured to service the memory access request based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises one or more computer-readable storage devices configured to store instructions, which when executed by at least one of the one or more processors, are configured to:

determine a count of the additional cache misses over a number of clock cycles that occurred during the period;

determine a count of cache hits over the number of clock cycles;

compute a ratio of the count of the cache hits to the count of the additional cache misses;

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

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

12. The apparatus of claim 8, wherein the one or more computer-readable storage devices configured to store the instructions, which when executed by at least one of the one or more processors, are configured to service the memory access request based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises one or more computer-readable storage devices configured to store instructions, which when executed by at least one of the one or more processors, are configured to:

determine a count of the additional cache misses over a number of clock cycles that occurred during the period;

determine a count of cache hits over the number of clock cycles;

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

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

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

compare the first value to the third value; and

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

13. The apparatus of claim 8 further comprising one or more computer-readable storage devices configured to store instructions, which when executed by at least one of the one or more processors, are 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 additional memory access requests previous to the memory access request; and

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

14. The apparatus of claim 13, wherein the one or more computer-readable storage devices configured to store the instructions, which when executed by at least one of the one or more processors, are configured to service the memory access request based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises one or more computer-readable storage devices configured to store instructions, which when executed by at least one of the one or more processors, are 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.

15. A computer program product for accessing a computer memory, the computer program product comprising:

a computer readable storage medium having computer usable program code embodied therewith, the computer usable program code comprising a computer usable program code configured to;

determine that an access request to the computer memory results in a cache miss;

determine an amount of cache resources used to service additional cache misses that occurred within a period prior to the cache miss; and

service the access request to the computer memory based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss.

16. The computer program product of claim 15, wherein the computer usable program code configured to service the memory access request based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises computer usable program code configured to:

determine a count of the additional cache misses over a number of clock cycles;

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

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

17. The computer program product of claim 15, wherein the computer usable program code configured to service the memory access request based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises computer usable program code configured to:

determine a count of the additional cache misses over a number of clock cycles that occurred during the period;

determine a count of cache hits over the number of clock cycles;

compute a ratio of the count of the cache hits to the count of the additional cache misses;

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

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

18. The computer program product of claim 15, wherein the computer usable program code configured to service the memory access request based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises computer usable program code configured to:

determine a count of the additional cache misses over a number of clock cycles that occurred during the period;

determine a count of cache hits over the number of clock cycles;

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

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

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

compare the first value to the third value; and

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

19. The computer program product of claim 15 further comprising computer usable program code 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 additional memory access requests previous to the memory access request; and

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

20. The computer program product of claim 19, wherein the computer usable program code configured to service the memory access request based, at least in part, on the amount of the cache resources used to service the additional cache misses within the period prior to the cache miss comprises computer usable program code 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.