Control Of Processor Cache Memory Occupancy

Abstract

Techniques are described for controlling processor cache memory within a processor system. Cache occupancy values for each of a plurality of entities executing the processor system can be calculated. A cache replacement algorithm uses the cache occupancy values when making subsequent cache line replacement decisions. In some variations, entities can have occupancy profiles specifying a maximum cache quota and/or a minimum cache quota which can be adjusted to achieve desired performance criteria. Related methods, systems, and articles are also described.

What is claimed is: 
     
         1 . A method for controlling processor cache memory within a processor system, the method comprising:
 calculating, for each of a plurality of entities executing in the processor system, a cache occupancy value for the entity based on cache lines in the cache memory having identifiers associated with the entity; and   replacing, using a cache replacement algorithm that provides for varying treatments based on a number of occupied cache lines, cache lines in the cache memory required for execution of at least a portion of the entities based on the occupancy values.   
     
     
         2 . A method as in  claim 1 , wherein the calculating comprises by repeatedly counting a number of cache lines allocated to the entity offset by a number of cache lines vacated for the entity. 
     
     
         3 . A method as in  claim 1 , wherein the entities are each selected from a group comprising: a single task, a group of tasks, a thread, a group of threads, a single state machine, a group of state machines, a single virtual machine, and a group of virtual machines, and any combination thereof. 
     
     
         4 . A method as in  claim 1 , wherein each entity has an associated occupancy profile. 
     
     
         5 . A method as in  claim 4 , wherein the occupancy profile comprises a minimum quota specifying a minimum number of cache lines a corresponding entity should occupy. 
     
     
         6 . A method as in  claim 5 , wherein the occupancy profile comprises a maximum quota specifying a maximum number of cache lines the corresponding entity should occupy. 
     
     
         7 . A method as in  claim 6 , further comprising:
 monitoring performance of at least one of the entities by the processor system; and   varying, based on the monitoring of the performance, at least one of the minimum quota and the maximum quota to affect subsequent performance for one or more of the at least one monitored entity.   
     
     
         8 . A method as in  claim 7 , wherein performance is based on at least one of: cache hit values and cache miss penalty. 
     
     
         9 . A method as in  claim 8 , further comprising:
 determining that a cache hit value is below a predetermined level for one of the entities; and   increasing the minimum quota for the entity having the cache hit value below the predetermined level.   
     
     
         10 . A method as in  claim 8 , further comprising:
 determining that a cache miss penalty is above a predetermined level for one of the entities; and   decreasing the maximum quota for the entity having the cache hit value above the predetermined level.   
     
     
         11 . A method as in  claim 5 , further comprising:
 encoding, for each entity, a corresponding occupancy value into an n-bit compliance value by comparing a number of lines specified by the occupancy value with the minimum quota and the maximum quota for the entity.   
     
     
         12 . A method as in  claim 11 , wherein the occupancy values for each entity are encoded in an N-bit code that is stored in a compliance table. 
     
     
         13 . A method as in  claim 12 , wherein the cache replacement algorithm reads the compliance values for entities in the compliance table and compares those compliance values to select cache lines to be replaced. 
     
     
         14 . A method as in  claim 5 , wherein the cache replacement algorithm selects a cache line to replace by taking into account, in prioritized order, whether an entity:
 occupies a number of cache lines exceeding its corresponding maximum quota above a first threshold,   occupies a number of cache lines exceeding its corresponding maximum quota above a second threshold, but below the first threshold,   occupies a number of cache lines less than its corresponding maximum quota and more than its corresponding minimum quota,   occupies a number of cache lines less than its minimum quota by more than a third threshold, and   occupies a number of cache lines substantially less than its minimum quota below a fourth threshold that is lower than the third threshold.   
     
     
         15 . A method as in  claim 1 , wherein if the cache replacement algorithm is not able to identify a cache line to be replaced, a randomly selected cache line is replaced. 
     
     
         16 . A method as in  claim 1 , wherein if the cache replacement algorithm is not able to identify a cache line to be replaced and there is not an empty cache line, a least recently used cache line is replaced. 
     
     
         17 . A method as in  claim 1 , wherein if the cache replacement algorithm identifies multiple cache lines to be replaced and there is not an empty cache line, a randomly selected or least recently used cache line among the identified multiple cache lines is replaced. 
     
     
         18 . A method for controlling execution of entities using cache memory within a processor system, the method comprising:
 monitoring performance of a plurality of entities and their usage of cache memory within the processor system; and   selectively adjusting at least one of a minimum cache quota and a maximum cache quota for entities based on the monitoring.   
     
     
         19 . A method as in  claim 18 , wherein the monitoring and adjusting are implemented by at least one data processor. 
     
     
         20 . An apparatus for controlling processor cache memory within a processor system, the apparatus comprising:
 means for calculating, for each of a plurality of entities executing in the processor system, a cache occupancy value for the entity based on cache lines in the cache memory having identifiers associated with the entity; and   means for replacing, using a cache replacement algorithm that provides for varying treatments based on a number of occupied cache lines, cache lines in the cache memory required for execution of at least a portion of the entities based on the occupancy values.