Cost-aware cache replacement

Abstract

Systems and methods relate to cost-aware cache management policies. In a cost-aware least recently used (LRU) replacement policy, temporal locality as well as miss cost is taken into account in selecting a cache line for replacement, wherein the miss cost is based on an associated operation type including instruction cache read, data cache read, data cache write, prefetch, and write back. In a cost-aware dynamic re-reference interval prediction (DRRIP) based cache management policy, miss costs associated with operation types pertaining to a cache line are considered for assigning re-reference interval prediction values (RRPV) for inserting the cache line, pursuant to a cache miss and for updating the RRPV upon a hit for the cache line. The operation types comprise instruction cache access, data cache access, prefetch, and write back. These policies improve victim selection, while minimizing cache thrashing and scans.

What is claimed is: 
     
         1 . A method of cache management, the method comprising:
 determining a re-reference interval prediction value (RRPV) for one or more of insertion or hit updates of a cache line of a cache, based on miss costs associated with operation types pertaining to the cache line; and   determining a cost-aware dynamic re-reference interval prediction (DRRIP) for the cache line based on the RRPV.   
     
     
         2 . The method of  claim 1 , wherein the operation types comprise instruction cache access, data cache access, prefetch, and write back. 
     
     
         3 . The method of  claim 1 , comprising pursuant to a cache miss for a contender cache line, identifying a victim cache line to be replaced, wherein the victim cache line has the highest RRPV among cache lines in the cache. 
     
     
         4 . The method of  claim 1 , comprising determining the RRPVs of follower sets of the cache based on set-dueling between RRPVs of leader sets with RRPVs set based on cost-aware static re-reference interval prediction (SRRIP) and cost-aware bi-modal re-reference interval prediction (BRRIP). 
     
     
         5 . The method of  claim 4 , comprising assigning an RRPV of “0” or “near-immediate”, associated with least likely to be replaced, for insertion of the cache line pursuant to an instruction cache miss, for cost-aware SRRIP and cost-aware BRRIP. 
     
     
         6 . The method of  claim 4 , comprising assigning an RRPV of “2” or “far”, associated with more likely to be replaced, for insertion of the cache line, pursuant to a data cache miss, for cost-aware BRRIP. 
     
     
         7 . The method of  claim 4 , comprising adaptively assigning an RRPV of one of: “2” or “far”, associated with more likely to be replaced, or “3” or “distant”, associated with most likely to be replaced, for insertion of the cache line, pursuant to a write back of the cache line to the cache, for cost-aware SRRIP. 
     
     
         8 . The method of  claim 4 , comprising assigning an RRPV of “3” or “distant,” associated with most likely to be replaced, for insertion of the cache line, pursuant to a prefetch of the cache line to the cache, for cost-aware SRRIP. 
     
     
         9 . The method of  claim 4 , comprising adaptively assigning an RRPV of “0” or “near-immediate”, associated with least likely to be replaced, or not updating the RRPV, for a hit update of the cache line for cost-aware SRRIP and cost-aware BRRIP. 
     
     
         10 . An apparatus comprising:
 a cache; and   a cache controller configured to manage the cache, wherein the cache controller is configured to:
 determine a re-reference interval prediction value (RRPV) for one or more of insertion or hit updates of a cache line of a cache, based on miss costs associated with operation types pertaining to the cache line; and 
 determine a cost-aware dynamic re-reference interval prediction (DRRIP) for the cache line based on the RRPV. 
   
     
     
         11 . The apparatus of  claim 10 , wherein the operation types comprise instruction cache access, data cache access, prefetch, and write back. 
     
     
         12 . The apparatus of  claim 10 , wherein the cache controller is configured to identify a victim cache line to be replaced pursuant to a cache miss for a contender cache line, wherein the victim cache line has the highest RRPV among cache lines in the cache. 
     
     
         13 . The apparatus of  claim 10 , wherein the cache controller is configured to determine the RRPVs of follower sets of the cache based on set-dueling between RRPVs of leader sets with RRPVs set based on cost-aware static re-reference interval prediction (SRRIP) and cost-aware bi-modal re-reference interval prediction (BRRIP). 
     
     
         14 . The apparatus of  claim 13 , wherein the cache controller is further configured to:
 assign an RRPV of “0” or “near-immediate”, associated with least likely to be replaced, for insertion of the cache line, pursuant to an instruction cache miss, for cost-aware SRRIP and cost-aware BRRIP;   assign an RRPV of “2” or “far”, associated with more likely to be replaced, for insertion of the cache line, pursuant to a data cache miss, for cost-aware BRRIP;   adaptively assign an RRPV of one of: “2” or “far”, associated with more likely to be replaced, or “3” or “distant”, associated with most likely to be replaced, for insertion of the cache line, pursuant to a write back of the cache line to the cache, for cost-aware SRRIP;   assign an RRPV of “3” or “distant,” associated with most likely to be replaced, for insertion of the cache line, pursuant to a prefetch of the cache line to the cache, for cost-aware SRRIP;   adaptively assign an RRPV of “0” or “near-immediate”, associated with least likely to be replaced, or not updating the RRPV, for a hit update of the cache line, for cost-aware SRRIP and cost-aware BRRIP; or   a combination thereof.   
     
     
         15 . The apparatus of  claim 10 , integrated in a device selected from the group consisting of a set top box, a music player, a video player, an entertainment unit, a navigation device, a personal digital assistant (PDA), a fixed location data unit, a computer, a laptop, a tablet, a communications device, and a mobile phone. 
     
     
         16 . A non-transitory computer readable storage medium comprising code, which, when executed by a processor, causes the processor to perform operations for cache management, the non-transitory computer readable storage medium comprising:
 code for determining a re-reference interval prediction value (RRPV) for one or more of insertion or hit updates of a cache line of a cache, based on miss costs associated with operation types pertaining to the cache line; and   code for determining a cost-aware dynamic re-reference interval prediction (DRRIP) for the cache line based on the RRPV.   
     
     
         17 . The non-transitory computer readable storage medium of  claim 16 , wherein the operation types comprise instruction cache access, data cache access, prefetch, and write back. 
     
     
         18 . The non-transitory computer readable storage medium of  claim 16 , further comprising code for identifying a victim cache line to be replaced, pursuant to a cache miss for a contender cache line, wherein the victim cache line has the highest RRPV among cache lines in the cache. 
     
     
         19 . The non-transitory computer readable storage medium of  claim 16 , further comprising code for determining the RRPVs of follower sets of the cache based on set-dueling between RRPVs of leader sets with RRPVs set based on cost-aware static re-reference interval prediction (SRRIP) and cost-aware bi-modal re-reference interval prediction (BRRIP). 
     
     
         20 . The non-transitory computer readable storage medium of  claim 19 , comprising code for:
 assigning an RRPV of “0” or “near-immediate”, associated with least likely to be replaced, for insertion of the cache line, pursuant to an instruction cache miss, for cost-aware SRRIP and cost-aware BRRIP;   assigning an RRPV of “2” or “far”, associated with more likely to be replaced, for insertion of the cache line, pursuant to a data cache miss, for cost-aware BRRIP;   adaptively assigning an RRPV of one of: “2” or “far”, associated with more likely to be replaced, or “3” or “distant”, associated with most likely to be replaced, for insertion of the cache line, pursuant to a write back of the cache line to the cache, for cost-aware SRRIP;   assigning an RRPV of “3” or “distant,” associated with most likely to be replaced, for insertion of the cache line, pursuant to a prefetch of the cache line to the cache, for cost-aware SRRIP;   adaptively assigning an RRPV of “0” or “near-immediate”, associated with least likely to be replaced, or not updating the RRPV, for a hit update of the cache line for cost-aware SRRIP and cost-aware BRRIP; or   a combination thereof.