Cost-conscious pre-emptive cache line displacement and relocation mechanisms

Abstract

A hardware based method for determining when to migrate cache lines to the cache bank closest to the requesting processor to avoid remote access penalty for future requests. In a preferred embodiment, decay counters are enhanced and used in determining the cost of retaining a line as opposed to replacing it while not losing the data. In one embodiment, a minimization of off-chip communication is sought; this may be particularly useful in a CMP environment.

1 . An apparatus for effecting cache management, said apparatus comprising:
 an arrangement for displacing data from a cache block;   an arrangement for ascertaining a new cache location for displaced data;   said ascertaining arrangement being adapted to determine the suitability of one or more candidates for a new cache location via at least one of:   determining a cost of re-fetching the replaced data;   determining a likelihood of future reference to the replaced data; and   determining whether a candidate is able to retain the replaced data.   
   
   
       2 . The apparatus according to  claim 1 , wherein said ascertaining arrangement is adapted to determine the suitability of one or more candidates for a new cache location via all three of:
 determining a cost of re-fetching the replaced data;   determining a likelihood of future reference to the replaced data; and   determining whether a candidate is able to retain the replaced data.   
   
   
       3 . The apparatus according to  claim 1 , wherein said ascertaining arrangement is adapted to seek an on-chip peer cache as a suitable candidate for a new cache location. 
   
   
       4 . The apparatus according to  claim 3 , wherein said ascertaining arrangement is adapted to seek a peer L2 cache as a suitable candidate for a new cache location. 
   
   
       5 . The apparatus according to  claim 1 , wherein said ascertaining arrangement is adapted to determine the suitability of one or more candidates for a new cache location via determining a cost of re-fetching the replaced data. 
   
   
       6 . The apparatus according to  claim 5 , wherein said ascertaining arrangement is adapted to determine the cost of re-fetching based on a state of a candidate cache block. 
   
   
       7 . The apparatus according to  claim 6 , wherein said ascertaining arrangement is adapted to estimate that a cost of re-fetching is cost-effective if a candidate cache block is an exclusive copy, or represents the only copy of a shared cache block within a chip. 
   
   
       8 . The apparatus according to  claim 1 , wherein said ascertaining arrangement is adapted to determine the suitability of one or more candidates for a new cache location via determining a likelihood of future reference to the replaced data. 
   
   
       9 . The apparatus according to  claim 8 , wherein said ascertaining arrangement is adapted to employ a decay counter corresponding to each candidate cache block to determine a likelihood of future reference to the replaced data. 
   
   
       10 . The apparatus according to  claim 9 , wherein:
 said ascertaining arrangement is further adapted to employ a residency counter per congruence class to determine a likelihood of future reference to the replaced data; and   the likelihood of future reference to replaced data corresponds to a threshold being reached in the residency counter.   
   
   
       11 . The apparatus according to  claim 10 , wherein the residency counter threshold is 2 n-1 , where n represents a count of instances in which a cache block belonging to a corresponding congruence class is replaced before the decay counter reaches a predetermined decay threshold. 
   
   
       12 . The apparatus according to  claim 1 , wherein said ascertaining arrangement is adapted to determine the suitability of one or more candidates for a new cache location via determining whether a candidate is able to retain the replaced data. 
   
   
       13 . The apparatus according to  claim 12 , wherein said ascertaining arrangement is adapted to employ cache block usage data among candidates for a new cache location. 
   
   
       14 . The apparatus according to  claim 13 , wherein said ascertaining arrangement is adapted to employ cache block usage data wherein the most recent requester of a candidate cache block is tracked. 
   
   
       15 . A method of effecting cache management, said method comprising the steps of:
 displacing data from a cache block;   ascertaining a new cache location for displaced data;   said ascertaining arrangement step comprising determining the suitability of one or more candidates for a new cache location via at least one of:   determining a cost of re-fetching the replaced data;   determining a likelihood of future reference to the replaced data; and   determining whether a candidate is able to retain the replaced data.   
   
   
       16 . The method according to  claim 15 , wherein said ascertaining step comprises determining the suitability of one or more candidates for a new cache location via all three of:
 determining a cost of re-fetching the replaced data;   determining a likelihood of future reference to the replaced data; and   determining whether a candidate is able to retain the replaced data.   
   
   
       17 . The method according to  claim 15 , wherein said ascertaining step comprises seeking an on-chip peer cache as a suitable candidate for a new cache location. 
   
   
       18 . The method according to  claim 17 , wherein said seeking step comprises seeking a peer L2 cache as a suitable candidate for a new cache location. 
   
   
       19 . The method according to  claim 15 , wherein said ascertaining step comprises determining the suitability of one or more candidates for a new cache location via determining a cost of re-fetching the replaced data. 
   
   
       20 . The method according to  claim 19 , wherein said step of determining a cost of re-fetching comprises determining the cost of re-fetching based on a state of a candidate cache block. 
   
   
       21 . The method according to  claim 20 , wherein said step of determining the cost of re-fetching based on a state of a candidate cache block comprises estimating that a cost of re-fetching is cost-effective if a candidate cache block is in an exclusive state or represents the only or last copy of a shared cache block. 
   
   
       22 . The method according to  claim 15 , wherein said ascertaining step comprises determining the suitability of one or more candidates for a new cache location via determining a likelihood of future reference to the replaced data. 
   
   
       23 . The method according to  claim 22 , wherein said step of determining a likelihood of future reference comprises employing a decay counter corresponding to each candidate cache block. 
   
   
       24 . The method according to  claim 23 , wherein:
 said step of determining a likelihood of future reference further comprises employing a residency counter per congruence class to determine a likelihood of future reference to the replaced data, wherein the likelihood of future reference to replaced data corresponds to a threshold being reached in the residency counter.   
   
   
       25 . The method according to  claim 24 , wherein the residency counter threshold is 2 n-1 , where n represents a count of instances in which a cache block belonging to a corresponding congruence class is replaced before the decay counter reaches a predetermined decay threshold. 
   
   
       26 . The method according to  claim 15 , wherein said ascertaining step comprises determining the suitability of one or more candidates for a new cache location via determining whether a candidate is able to retain the replaced data. 
   
   
       27 . The method according to  claim 26 , wherein said step of determining whether a candidate is able to retain the replaced data comprises employing cache block usage data among candidates for a new cache location. 
   
   
       28 . The method according to  claim 27 , wherein said step of employing cache block usage data comprises tracking the most recent requester of a candidate cache block. 
   
   
       29 . A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for effecting cache management, said method comprising the steps of:
 displacing data from a cache block;   ascertaining a new cache location for displaced data;   said ascertaining arrangement step comprising determining the suitability of one or more candidates for a new cache location via at least one of:   determining a cost of re-fetching the replaced data;   determining a likelihood of future reference to the replaced data; and   determining whether a candidate is able to retain the replaced data.