System and method for a shared cache with adaptive partitioning

Patent metadata

Field	Value
Publication number	US-9734070-B2
Application number	US-201514921468-A
Country	US
Kind code	B2
Filing date	Oct 23, 2015
Priority date	Oct 23, 2015
Publication date	Aug 15, 2017
Grant date	Aug 15, 2017

Abstract

A cache controller adaptively partitions a shared cache. The adaptive partitioning cache controller includes tag comparison and staling logic and selection logic that are responsive to client access requests and various parameters. A component cache is assigned a target occupancy which is compared to a current occupancy. A conditional identification of stale cache lines is used to manage data stored in the shared cache. When a conflict or cache miss is identified, selection logic identifies candidates for replacement preferably among cache lines identified as stale. Each cache line is assigned to a bucket with a fixed number of buckets per component cache. Allocated cache lines are assigned to a bucket as a function of the target occupancy. After a select number of buckets are filled, subsequent allocations result in the oldest cache lines being marked stale. Cache lines are deemed stale when their respective component cache active indicator is de-asserted.

First claim

What is claimed is:

1. A method for adaptively partitioning a shared cache, comprising:
storing parameters that define aspects of an integer number of component caches in the shared cache, wherein at least one of the integer number of component caches is associated to a set of parameters including a target occupancy and an occupancy counter;
applying, to client requests, a unique identifier corresponding to a component cache within the integer number of component caches;
in response to the client requests to store client data in the shared cache,
using information stored in the set of parameters to make cache line allocations, wherein when a cache line is allocated an associated occupancy counter is incremented; and
using the information stored in the set of parameters to identify candidate cache lines for eviction, wherein when a separate cache line is evicted the associated occupancy counter is decremented.

2. The method of claim 1 , further comprising:
assigning an active indicator to the at least one of the integer number of component caches, wherein cache lines present in the shared cache are associated by default with a stale condition when their respective component cache has the active indicator de-asserted.

3. The method of claim 2 , further comprising:
assigning a bucket pointer and a bucket level counter to the at least one of the integer number of component caches, wherein the at least one of the integer number of component caches is divided into an integer number of buckets; and
for each cache line allocation that addresses the at least one of the integer number of component caches,
incrementing a bucket level value in the bucket level counter for the at least one of the integer number of component caches,
when the bucket level value reaches a fixed fraction of the target occupancy for the at least one of the integer number of component caches, incrementing the bucket pointer and resetting the bucket level counter; and
storing the bucket pointer in the shared cache in association with an allocated cache line.

4. The method of claim 3 , further comprising:
for access operations that address the at least one of the integer number of component caches, identifying a set of candidate cache lines for replacement; and
for each candidate cache lines of the set of candidate cache lines, calculating an age by comparing the value of the bucket pointer associated with a particular candidate cache line with a current bucket pointer value for the component cache associated with the particular candidate cache line.

5. The method of claim 4 , further comprising:
for each of the candidate cache line, determining a stale condition depending on the respective age, and
storing the stale condition in the shared cache in association with the particular candidate cache line.

6. The method of claim 4 , wherein the set of parameters includes a least recently used parameter that conditionally identifies when a cache line from an older bucket should be moved to the current bucket.

7. The method of claim 5 , further comprising:
for a component cache access that results in a hit condition, conditionally updating the bucket pointer and stale condition for the accessed cache line, and conditionally updating the bucket level value for the component cache.

8. The method of claim 7 , wherein the bucket pointer is refreshed, the stale condition is reset and the bucket level value is incremented when the component cache least recently used parameter is set and the bucket pointer is not equal to the component cache current bucket pointer.

9. The method of claim 2 , further comprising:
for a component cache access that results in a miss condition, conditionally identifying a replacement candidate.

10. The method of claim 9 , further comprising:
assigning a priority parameter to the at least one of the integer number of component caches; and
conditionally identifying the replacement candidate when no stale candidates exist.

11. The method of claim 10 , wherein the replacement candidate is selected in a preferred sequence including from among any stale cache lines, from the lowest priority cache line with a lower priority than an accessed cache component, from the accessed cache component, and when multiple fresh replacement candidates are identified, from an oldest cache line.

12. The method of claim 11 , further comprising:
when multiple replacement candidates are identified, applying an additional replacement candidate criteria.

13. The method of claim 12 , wherein the additional replacement candidate criteria includes identifying a default way.

14. The method of claim 1 , further comprising:
assigning an optional allocate parameter to the at least one of the integer number of component caches; and
conditionally allocating a cache line.

15. The method of claim 14 , wherein a cache line is not allocated when the respective component cache is full and the optional allocate parameter is set.

16. An adaptive partitioning cache controller, comprising:
registers arranged to store a set of operational parameters for a desired number of component caches of a shared cache;
tag comparison and staling logic coupled to the registers and arranged to receive a cache address and a unique component cache identifier identifying a cache line in the shared cache, the tag comparison and staling logic in response to an operational mode input generates a measure of elapsed time that information has been stored in a particular cache line in the shared cache, conditionally records a stale condition, a valid condition and updates a bucket pointer; and
selection logic coupled to the tag comparison and staling logic and the registers, the selection logic arranged to receive the measure of elapsed time that the information has been stored in the particular cache line in the shared cache, the unique component cache identifier, and a priority indicator, and identify in accordance with the stale condition and the valid condition a component cache identifier of a candidate cache line to be replaced in the shared cache.

17. The adaptive partitioning cache controller of claim 16 , wherein the set of operational parameters include a target occupancy and a current occupancy.

18. The adaptive partitioning cache controller of claim 17 , wherein the set of operational parameters include an active indicator and cache lines present in the shared cache are associated by default with the stale condition when their respective component cache has the active indicator de-asserted.

19. The adaptive partitioning cache controller of claim 18 , wherein the set of operational parameters include one or more of a priority value, a current bucket pointer, a current bucket level and a least recently used parameter.

20. The adaptive partitioning cache controller of claim 16 , wherein the selection logic is arranged to enable a preferred sequence including identification of a replacement candidate from among any stale cache lines, from the lowest priority cache line with a lower priority than an accessed cache component, from the accessed cache component, and when multiple fresh replacement candidates are identified, from an oldest cache line.

21. The adaptive partitioning cache controller of claim 16 , wherein the selection logic is arranged to identify replacement candidates in accordance with at least three levels of priority.

22. A computing device, comprising:
a processor;
a shared cache configured to provide a da

Assignees

• Qualcomm Inc

Inventors

• Artieri Alain
• Palacharla Subbarao
• Moll Laurent
• Sankuratri Raghu
• Bhole Kedar
• Chamarty Vinod

Classifications

• G06F12/0864

  using pseudo-associative means, e.g. set-associative or hashing · CPC title

• G06F12/084 Primary

  with a shared cache · CPC title

• G06F2212/62

  Details of cache specific to multiprocessor cache arrangements · CPC title

• G06F2212/1048

  Scalability · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title