Eviction algorithm for inclusive lower level cache based upon state of higher level cache

Abstract

A cache eviction algorithm for an inclusive cache determines which among a plurality of cache lines may be evicted from the inclusive cache based at least in part upon the state of the cache lines in a higher level cache. In particular, a cache eviction algorithm may determine, from an inclusive cache directory for a lower level cache, whether a cache line is cached in the lower level cache but not cached in any of a plurality of higher level caches for which cache directory information is additionally stored in the cache directory. Then, based upon determining that a cache line is cached in the lower level cache but not cached in any of the plurality of higher level caches, the cache eviction algorithm may select that cache line for eviction from the cache.

1 . A circuit arrangement, comprising: 
 a plurality of processors, each processor including at least one higher level cache; and    an inclusive multi-way set associative lower level cache coupled to the plurality of processors, the lower level cache including a cache directory including cache directory information for a plurality of cache lines that are currently cached in any of the lower level cache and plurality of processors, the lower level cache configured to, in response to a cache miss on a requested cache line, selectively evict a cache line from the lower level cache based upon a determination that the cache line is cached in the lower level cache but is not cached in any of the plurality of processors.    
   
   
       2 . A circuit arrangement, comprising: 
 an inclusive cache directory associated with a lower level cache and configured to store cache directory information for the lower level cache and a plurality of higher level caches; and    control logic coupled to the inclusive cache directory and configured to selectively evict a cache line from the lower level cache based upon a determination that the cache line is cached in the lower level cache but not cached in any of the plurality of higher level caches.    
   
   
       3 . The circuit arrangement of  claim 2 , wherein the lower level cache is disposed in a node controller of a multi-node data processing system, and wherein the plurality of high level caches are disposed in a plurality of processors coupled to the node controller.  
   
   
       4 . The circuit arrangement of  claim 3 , wherein the lower level cache is a fourth level cache, and wherein the plurality of high level caches includes at least one first, second, and third level cache disposed in each of the plurality of processors coupled to the node controller.  
   
   
       5 . The circuit arrangement of  claim 2 , further comprising a cache memory for the lower level cache.  
   
   
       6 . The circuit arrangement of  claim 2 , wherein the control logic is configured to selectively evict the cache line in response to a request for another cache line that misses on the lower level cache.  
   
   
       7 . The circuit arrangement of  claim 6 , wherein the inclusive cache directory comprises a multi-way set associative cache directory, wherein the other cache line is in the same associativity set as the evicted cache line, and wherein the control logic is configured to selectively evict the cache line only after determining that no empty associativity class exists for the associativity set.  
   
   
       8 . The circuit arrangement of  claim 7 , wherein the control logic is further configured to apply a cache replacement algorithm in response to determining that no associativity class in the associativity set stores a cache line that is cached in the lower level cache but not cached in any of the plurality of higher level caches.  
   
   
       9 . The circuit arrangement of  claim 8 , wherein the cache replacement algorithm is selected from the group consisting of least recently used, most recently used, random and round robin.  
   
   
       10 . An integrated circuit device comprising the circuit arrangement of  claim 2 .  
   
   
       11 . A chipset comprising the circuit arrangement of  claim 2 .  
   
   
       12 . A data processing system, comprising: 
 a plurality of processors; and    a node controller coupled to the plurality of processors and comprising the circuit arrangement of  claim 2 , wherein the plurality of higher level caches are disposed in the plurality of processors.    
   
   
       13 . The data processing system of  claim 12 , wherein the plurality of processors and the node controller are disposed in a first node among a plurality of nodes in the data processing system.  
   
   
       14 . A program product, comprising a hardware definition program that defines the circuit arrangement of  claim 2;  and a computer readable medium bearing the hardware definition program.  
   
   
       15 . A method of evicting a cache line from a cache, the method comprising: 
 determining from an inclusive cache directory for a lower level cache whether a cache line is cached in the lower level cache but not cached in any of a plurality of higher level caches for which cache directory information is additionally stored in the cache directory; and    evicting the cache line from the lower level cache based upon determining that the cache line is cached in the lower level cache but not cached in any of the plurality of higher level caches.    
   
   
       16 . The method of  claim 15 , wherein the lower level cache is disposed in a node controller of a multi-node data processing system, and wherein the plurality of high level caches are disposed in a plurality of processors coupled to the node controller.  
   
   
       17 . The method of  claim 16 , wherein the lower level cache is a fourth level cache, and wherein the plurality of high level caches includes at least one first, second, and third level cache disposed in each of the plurality of processors coupled to the node controller.  
   
   
       18 . The method of  claim 15 , wherein determining and evicting are performed in response to a request for another cache line that misses on the lower level cache.  
   
   
       19 . The method of  claim 18 , wherein the inclusive cache directory comprises a multi-way set associative cache directory, wherein the other cache line is in the same associativity set as the evicted cache line, and wherein evicting the cache line is performed only after determining that no empty associativity class exists for the associativity set.  
   
   
       20 . The method of  claim 19 , further comprising applying a cache replacement algorithm in response to determining that no associativity class in the associativity set stores a cache line that is cached in the lower level cache but not cached in any of the plurality of higher level caches.  
   
   
       21 . The method of  claim 20 , wherein the cache replacement algorithm is selected from the group consisting of least recently used, most recently used, random and round robin.