Dynamically tuning the size of a cache stored in a shared memory

• US 8,788,783 B1
• Filed: 06/18/2010
• Issued: 07/22/2014
• Est. Priority Date: 06/18/2010
• Status: Active Grant

• Current Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Original Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Inventors: Molinari, Guy A., Karnati, Sravana Kumar, Parkinson, David T.
• Primary Examiner(s): Parikh, Kalpit
• Application Number:
  US12/818,896
• Time in Patent Office: 1,495 Days
• Field of Search: 121/18, 711/118, 711/170
• US Class Current: 711/170
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 2212/601 Reconfiguration of cache memory

Abstract

A system and method configured to dynamically tune the size of a cache stored in a shared memory minimizes the amount of the shared memory consumed by the cache while achieving a desired cache hit ratio. A maximum size of the cache is computed based on a slope, the current cache size, a target hit ratio, and a current hit ratio. The maximum size is then used to dynamically adjust the size of the cache, decreasing or increasing the size based on the computed maximum size.

Claims

1. A computer-implemented method for tuning the size of a dynamically-sized cache in a shared memory, the method comprising:

determining a plurality of cumulative hit ratios for the dynamically-sized cache, where each cumulative hit ratio is the ratio of a first number of cache reads of data that is stored in the dynamically-sized cache (cache hits) to a sum of the first number and a second number of cache reads of data that is not stored in the dynamically-sized cache (cache misses), wherein at least one cumulative hit ratio of the plurality of cumulative hit ratios is determined when an entry in the dynamically-sized cache is filled in response to a cache miss;

computing a slope as a first order derivative of each cumulative hit ratio of the dynamically-sized cache with respect to a size of the dynamically-sized cache associated with each cumulative hit ratio;

computing, based on the slope, a maximum value that limits the size of the dynamically-sized cache in the shared memory; and

adjusting the size of the dynamically-sized cache in the shared memory based on the maximum value.

2. The computer-implemented method of claim 1, wherein the maximum value is computed based on a difference between a target hit ratio for the dynamically-sized cache and a current cumulative hit ratio of the plurality of cumulative hit ratios.

3. The computer-implemented method of claim 1, wherein the maximum value is computed based on a desired level of performance corresponding to a target hit ratio for the dynamically-sized cache.

4. The computer-implemented method of claim 1, wherein the maximum value is computed based on a smoothing factor.

5. The computer-implemented method of claim 1, wherein the slope is computed by sampling the plurality of cumulative hit ratios and size of the dynamically-sized cache at multiple points in time within a sliding window.

6. The computer-implemented method of claim 1, further comprising the step of maintaining a current size of the dynamically-sized cache when the amount of the shared memory consumed by the dynamically-sized cache and other data exceeds a high threshold limit.

7. The computer-implemented method of claim 1, wherein the step of adjusting to the size of the dynamically-sized cache is delayed if an adjustment would decrease the size of the cache.

8. The computer-implemented method of claim 1, wherein the maximum value is computed by computing a difference between a target hit ratio and a current cumulative hit ratio of the plurality of cumulative hit ratios, dividing the difference by the slope and scaling the resulting quotient by a smoothing factor, and then summing the resulting scaled quotient with a current size of the dynamically-sized cache.

9. A system for tuning the size of a dynamically-sized cache in a shared memory, the system comprising:

a shared memory configured to store the dynamically-sized cache in a portion of the shared memory; and

a cache management unit coupled to the shared memory and configured to;

determine a plurality of cumulative hit ratios for the dynamically-sized cache, where each cumulative hit ratio is the ratio of a first number of cache reads of data that is stored in the dynamically-sized cache (cache hits) to a sum of the first number and a second number of cache reads of data that is not stored in the dynamically-sized cache (cache misses), wherein at least one cumulative hit ratio of the plurality of cumulative hit ratios is determined when an entry in the dynamically-sized cache is filled in response to a cache miss;

compute a slope as a first order derivative of each cumulative hit ratio of the dynamically-sized cache with respect to a size of the dynamically-sized cache associated with each hit ratio;

compute, based on the slope, a maximum value that limits the size of the dynamically-sized cache stored in the shared memory; and

adjust the size of the dynamically-sized cache in the shared memory based on the maximum value.

10. The system of claim 9, wherein the cache management unit is further configured to compute the maximum value based on a difference between a target hit ratio for the dynamically-sized cache and a current cumulative hit ratio of the plurality of cumulative hit ratios.

11. The system of claim 9, wherein the cache management unit is further configured to compute the maximum value based on a desired level of performance corresponding to a target hit ratio for the dynamically-sized cache.

12. The system of claim 9, wherein the cache management unit is further configured to compute the maximum value based on a smoothing factor.

13. The system of claim 9, wherein the cache management unit is further configured to compute the slope by sampling plurality of cumulative hit ratios and size of the dynamically-sized cache at multiple points in time within a sliding window.

14. The system of claim 9, wherein the cache management unit is further configured to maintain a current size of the dynamically-sized cache when the amount of the shared memory consumed by the dynamically-sized cache and other data exceeds a high threshold limit.

15. The system of claim 9, wherein the cache management unit is further configured to delay an adjustment to the size of the dynamically-sized cache if the adjustment would decrease the size of the cache.

16. The system of claim 9, wherein the cache management unit is further configured to compute the maximum value by computing a difference between a target hit ratio and a current cumulative hit ratio of the plurality of cumulative hit ratios, dividing the difference by the slope and scaling the resulting quotient by a smoothing factor, and then summing the resulting scaled quotient with a current size of the dynamically-sized cache.

17. A non-transitory computer-readable medium storing instructions that, when executed by a processor, cause a computer system to tune the size of a dynamically-sized cache in a shared memory, by performing an operation comprising:

determining a cumulative hit ratio for the dynamically-sized cache as the ratio of a first number of cache reads of data that is stored in the dynamically-sized cache (cache hits) to a sum of the first number and a second number of cache reads of data that is not stored in the dynamically-sized cache (cache misses), wherein at least one cumulative hit ratio of the plurality of cumulative hit ratios is determined when an entry in the dynamically-sized cache is filled in response to a cache miss;

computing a slope as a first order derivative of the cumulative hit ratio of the dynamically-sized cache with respect to a size of the dynamically-sized cache associated with each cumulative hit ratio;

computing, based on the slope, a maximum value that limits the size of the dynamically-sized cache in the shared memory; and

adjusting the size of the dynamically-sized cache in the shared memory based on the maximum value.

18. The non-transitory computer-readable medium of claim 17, wherein each cumulative hit ratio of the plurality of cumulative hit ratios is determined when an entry in the dynamically-sized cache is filled in response to a cache miss, wherein the maximum value is computed by a cache management unit, wherein the cache management unit is configured to:

in a first instance, compute the maximum value based on a difference between a target hit ratio for the dynamically-sized cache and a current cumulative hit ratio of the plurality of cumulative hit ratios;

in a second instance, compute the maximum value based on a desired level of performance corresponding to a target hit ratio for the dynamically-sized cache;

in a third instance, compute the maximum value based on a smoothing factor.

19. The non-transitory computer-readable medium of claim 18, wherein the slope is computed by sampling the plurality of cumulative hit ratios and size of the dynamically-sized cache at multiple points in time within a sliding window, wherein the operation further comprises:

maintaining a current size of the dynamically-sized cache when the amount of the shared memory consumed by the dynamically-sized cache and other data exceeds a high threshold limit;

wherein the step of adjusting to the size of the dynamically-sized cache is delayed if an adjustment would decrease the size of the cache.

20. The non-transitory computer-readable medium of claim 19, wherein the cache management unit is configured to compute the maximum value in the first instance by computing the difference between the target hit ratio and the current cumulative hit ratio of the plurality of cumulative hit ratios, dividing the difference by the slope and scaling the resulting quotient by a smoothing factor, and then summing the resulting scaled quotient with a current size of the dynamically-sized cache, wherein the cache management unit comprises a cache size tuning unit, wherein the cache size tuning unit comprises:

a maximum cache size calculation unit configured to compute the maximum value in the first, second and third instances, respectively;

a dynamic size calculation unit configured to adjust the size of the dynamically-sized cache in the shared memory based on the maximum value; and

a hit ratio measurement unit configured to determining the plurality of cumulative hit ratios for the dynamically-sized cache.