EP-4736015-A1 - RUNNING AVERAGE CACHE HIT RATE

Abstract

The disclosed device includes a first register that stores a cumulative delta value and a second register that stores an average cache hit rate. The device also includes a control circuit that calculates a cache hit rate and updates the cumulative delta value based on the cache hit rate and the average cache hit rate. The control circuit also updates the average cache hit rate based on the updated cumulative delta value, and can update a cache allocation policy based on the updated average cache hit rate. Various other methods, systems, and computer-readable media are also disclosed.

Inventors

• Munoz, Edgar
• PATEL, Chintan S.
• DONLEY, GREGG
• KALYANASUNDHARAM, VYDHYANATHAN

Assignees

• Advanced Micro Devices, Inc.

Dates

Publication Date

20260506

Application Date

20240627

Claims (20)

1. 1. A device comprising: a first register configured to store a cumulative delta value; a second register configured to store an average cache hit rate; and a control circuit configured to: calculate a cache hit rate; update the cumulative delta value based on the cache hit rate and the average cache hit rate; update the average cache hit rate based on the updated cumulative delta value; and update a cache allocation policy based on the updated average cache hit rate.
2. 2. The device of claim 1, wherein the control circuit is configured to update the cumulative delta value by: determining a difference between the cache hit rate and the average cache hit rate; and adding the difference to the cumulative delta value.
3. 3. The device of claim 1, wherein the control circuit is configured to update the average cache hit rate based on determining that the updated cumulative delta value exceeds a delta range.
4. 4. The device of claim 3, wherein the control circuit is configured to determine that the updated cumulative delta value exceeds the delta range by determining that the updated cumulative delta value exceeds an upper delta threshold.
5. 5. The device of claim 4, wherein the control circuit is configured to update the average cache hit rate by incrementing the average cache hit rate in response to the updated cumulative delta value exceeding the upper delta threshold.
6. 6. The device of claim 5, wherein the control circuit is configured to increment the average cache hit rate using an increment factor.
7. 7. The device of claim 6, wherein the increment factor is based on a magnitude of the updated cumulative delta value exceeding the upper delta threshold.
8. 8. The device of claim 3, wherein the control circuit is configured to determine that the updated cumulative delta value exceeds the delta range by determining that the updated cumulative delta value is below a lower delta threshold.
9. 9. The device of claim 8, wherein the control circuit is configured to update the average cache hit rate by decrementing the average cache hit rate in response to the updated cumulative delta value being below the lower delta threshold.
10. 10. The device of claim 9, wherein the control circuit is configured to decrement the average cache hit rate using a decrement factor.
11. 11. The device of claim 10, wherein the decrement factor is based on a magnitude of the updated cumulative delta value being below the lower delta threshold.
12. 12. The device of claim 1, wherein the control circuit is further configured to reset the cumulative delta value in response to updating the average cache hit rate.
13. 13. The device of claim 12, wherein the control circuit is configured to reset the cumulative delta value using the updated average cache hit rate.
14. 14. A system comprising: a physical memory; at least one physical processor comprising a cache; a first register configured to store a cumulative delta value; a second register configured to store an average cache hit rate for the cache; and a control circuit configured to: calculate a cache hit rate for the cache; update, in the first register, the cumulative delta value based on the cache hit rate and the average cache hit rate; determine that the updated cumulative delta value exceeds a delta range; update, in response to determining that the updated cumulative delta value exceeds the delta range, the average cache hit rate in the second register; and update a cache allocation policy for the cache based on the updated average cache hit rate.
15. 15. The system of claim 14, wherein the control circuit is configured to update the cumulative delta value by: determining a difference between the cache hit rate and the average cache hit rate; and adding the difference to the cumulative delta value.
16. 16. The system of claim 14, wherein: the control circuit is configured to determine that the updated cumulative delta value exceeds the delta range by determining that the updated cumulative delta value exceeds an upper delta threshold; and the control circuit is configured to update, in response to the updated cumulative delta value exceeding the upper delta threshold, the average cache hit rate by incrementing the average cache hit rate using an increment factor that is based on a magnitude of the updated cumulative delta value exceeding the upper delta threshold.
17. 17. The system of claim 14, wherein: the control circuit is configured to determine that the updated cumulative delta value exceeds the delta range by determining that the updated cumulative delta value is below a lower delta threshold; and the control circuit is configured to update, in response to the updated cumulative delta value being below the lower delta threshold, the average cache hit rate by decrementing the average cache hit rate using a decrement factor that is based on a magnitude of the updated cumulative delta value being below the lower delta threshold.
18. 18. The system of claim 14, wherein the control circuit is further configured to reset the cumulative delta value using the updated average cache hit rate.
19. 19. A method comprising: calculating a cache hit rate for a cache; determining a difference between the cache hit rate and an average cache hit rate for the cache; updating a cumulative delta value by adding the difference to the cumulative delta value; determining that the updated cumulative delta value exceeds a delta range; updating, in response to determining that the updated cumulative delta value exceeds the delta range, the average cache hit rate; resetting the cumulative delta value in response to updating the average cache hit rate; and updating a cache allocation policy for the cache based on the updated average cache hit rate.
20. 20. The method of claim 19, wherein: determining that the updated cumulative delta value exceeds the delta range includes determining that the updated cumulative delta value exceeds an upper delta threshold; updating the average cache hit rate includes updating, in response to the updated cumulative delta value exceeding the upper delta threshold, the average cache hit rate by incrementing the average cache hit rate using an increment factor that is based on a magnitude of the updated cumulative delta value exceeding the upper delta threshold; determining that the updated cumulative delta value exceeds the delta range includes determining that the updated cumulative delta value exceeds the delta range by determining that the updated cumulative delta value is below a lower delta threshold; updating the average cache hit rate includes updating, in response to the updated cumulative delta value being below the lower delta threshold, the average cache hit rate by decrementing the average cache hit rate using a decrement factor that is based on a magnitude of the updated cumulative delta value being below the lower delta threshold; and resetting the cumulative delta value includes resetting the cumulative delta value using the updated average cache hit rate.

Description

RUNNING AVERAGE CACHE HIT RATE BACKGROUND [0001] Managing a cache involves managing cache allocation policies (e.g., reserving portions of the cache) to improve performance. Cache thrashing (e.g., continuous cache misses which require reading from memory) reduces performance and is a factor for determining cache allocation policies. Detecting cache thrashing involves tracking a running average cache hit rate, which further involves tracking a history of cache hit rates. However, tracking this history of cache hit rates can require sufficient processor storage, which can be expensive. BRIEF DESCRIPTION OF THE DRAWINGS [0002] The accompanying drawings illustrate a number of exemplary implementations and are a part of the specification. Together with the following description, these drawings demonstrate and explain various principles of the present disclosure. [0003] FIG. 1 is a block diagram of an exemplary system for a running average cache hit rate. [0004] FIG. 2 is a diagram of a running average cache hit rate without a cache hit rate history. [0005] FIG. 3 is a flow diagram of an exemplary method for a running average cache hit rate. [0006] FIG. 4 is a flow diagram of another exemplary method for a running average cache hit rate. [0007] Throughout the drawings, identical reference characters and descriptions indicate similar, but not necessarily identical, elements. While the exemplary implementations described herein are susceptible to various modifications and alternative forms, specific implementations have been shown by way of example in the drawings and will be described in detail herein. However, the exemplary implementations described herein are not intended to be limited to the particular forms disclosed. Rather, the present disclosure covers all modifications, equivalents, and alternatives falling within the scope of the appended claims. DETAILED DESCRIPTION [0008] The present disclosure is generally directed to a running average cache hit rate that can be implemented without the need to track a history of cache hit rates. As will be explained in greater detail below, implementations of the present disclosure track a cumulative delta value from a current cache hit and an average cache hit rate, and update the average cache hit rate based on the delta. A cache allocation policy can be updated from the updated average cache hit rate. [0009] In one implementation, a device for maintaining a running average cache hit rate includes a first register configured to store a cumulative delta value, a second register configured to store an average cache hit rate, and a control circuit. The control circuit can be configured to (i) calculate a cache hit rate, (ii) update the cumulative delta value based on the cache hit rate and the average cache hit rate, (iii) update the average cache hit rate based on the updated cumulative delta value, and (iv) update a cache allocation policy based on the updated average cache hit rate. [0010] In some examples, the control circuit is configured to update the cumulative delta value by determining a difference between the cache hit rate and the average cache hit rate, and adding the difference to the cumulative delta value. [0011] In some examples, the control circuit is configured to update the average cache hit rate based on determining that the updated cumulative delta value exceeds a delta range. In some examples, the control circuit is configured to determine that the updated cumulative delta value exceeds the delta range by determining that the updated cumulative delta value exceeds an upper delta threshold. In some examples, the control circuit is configured to update the average cache hit rate by incrementing the average cache hit rate in response to the updated cumulative delta value exceeding the upper delta threshold. In some examples, the control circuit is configured to increment the average cache hit rate using an increment factor. In some examples, the increment factor is based on a magnitude of the updated cumulative delta value exceeding the upper delta threshold. [0012] In some examples, the control circuit is configured to determine that the updated cumulative delta value exceeds the delta range by determining that the updated cumulative delta value is below a lower delta threshold. In some examples, the control circuit is configured to update the average cache hit rate by decrementing the average cache hit rate in response to the updated cumulative delta value being below the lower delta threshold. In some examples, the control circuit is configured to decrement the average cache hit rate using a decrement factor. In some examples, the decrement factor is based on a magnitude of the updated cumulative delta value being below the lower delta threshold. [0013] In some examples, the control circuit is further configured to reset the cumulative delta value in response to updating the average cache hit rate. In some examples, the control circuit is conf