Preferred write-mostly data cache replacement policies

1. A computer-implemented method of cache replacement, the method comprising steps of:

determining, for each cache block in a cache memory, a type of access that brought the cache block into the cache memory;

augmenting metadata associated with each cache block with an indicator of type of access request;

upon receiving an access request resulting in a cache miss, the cache miss indicating that a cache block needs to be replaced, examining the indicator in the metadata of each cache block for determining a probability that the cache block will be replaced;

wherein determining the probability comprises:

checking the indicator;

if the indicator identifies the cache block as a read block, determining that the cache block is likely to be used again as a write block; and

setting a high probability of replacement for the cache block; and

selecting for replacement one of the cache blocks with a highest probability for replacement among the cache blocks.

2. The computer-implemented method of claim 1 wherein augmenting the metadata comprises setting a bit in the metadata as the indicator.

3. The computer-implemented method of claim 1 wherein determining the probability comprises:

checking the indicator;

if the indicator identifies the cache block as being a write block, determining that the cache block is likely to be used again as a write block; and

setting a high probability of replacement for the cache block.

4. The computer-implemented method of claim 1 wherein the selecting element further comprises determining whether a last miss to the cache block was due to a write access.

5. The computer-implemented method of claim 1 further comprising examining a least recently used stack for determining the probability that the cache block will be replaced, the least recently used stack comprising a temporally-ordered list of cache block access.

6. The computer-implemented method of claim 5 further comprising:

determining that the cache block in the least recently used stack has the highest probability of replacement.

7. The computer-implemented method of claim 6 further comprising allocating the highest probability of replacement to the cache block in a top percentile of the least recently used stack.

8. The computer-implemented method of claim 1 wherein determining the probability comprises determining whether the cache block was ever read while in the cache memory.

9. The computer-implemented method of claim 1 wherein determining the probability comprises determining a ratio of read accesses to write accesses to the cache block while in the cache memory.

10. The computer-implemented method of claim 1 further comprising basing the probability on access types other than read and write access requests.

11. The computer-implemented method of claim 10 wherein the probability is based on instruction fetches.

12. A system for cache replacement comprising:

a cache memory comprising cache blocks wherein each cache block comprises metadata, the metadata comprising an indicator of a type of access request that brought the cache block into cache memory;

a cache controller configured for:

determining, for each cache block brought into the cache memory, the type of access request that brought the cache block into the cache memory;

setting an indicator in the metadata for each cache block, the indicator indicating the type of access request;

receiving access requests and retrieving cache blocks to satisfy the access requests; and

evicting cache blocks according to a determined probability of eviction; and

a cache algorithm for determining the probability of eviction; and

a least recently used stack comprising a temporally ordered listing of cache block access;

wherein determining which cache block to evict comprises:

checking the least recently used stack associated with each block;

for every block determined to be least recently used:

checking the indicator in the metadata; and

if the indicator identifies the cache block as being a read block,

determining that the cache block is likely to be used again as a write block;

setting a high probability of replacement for the cache block; and

selecting for replacement one of the cache blocks with a highest probability for replacement among the cache blocks.

13. The system of claim 12 wherein determining which cache block to evict comprises:

checking the indicator in the metadata; and

if the indicator identifies the cache block as being a write block, determining that the cache block is likely to be used again as a write block; and

setting a high probability of replacement for the cache block.

14. The system of claim 12 wherein determining which cache block to evict comprises:

checking the least recently used stack associated with each block;

for every block determined to be least recently used:

checking the indicator in the metadata;

if the indicator identifies the cache block as being a write block, determining that the cache block is likely to be used again as a write block; and

setting a high probability of replacement for the cache block.

15. The system of claim 12 wherein determining which cache block to evict comprises:

checking the least recently used stack associated with each block;

for every block determined to be least recently used:

checking the indicator in the metadata; and

if the indicator identifies the cache block as being a read block setting a high probability of replacement for the cache block.

16. A computer program product tangibly embodied on a non-transitory computer readable medium and comprising code that, when executed, causes a computer to:

determine, for each cache block in a cache memory, a type of access that brought a cache block into the cache memory;

augment metadata associated with each cache block with an indicator of type of access request;

upon receipt of an access request resulting in a cache miss, examining the indicator in the metadata of each cache block to determine a probability that the cache block will be replaced;

wherein determining the probability comprises:

checking the indicator;

if the indicator identifies the cache block as a read block, determining that the cache block is likely to be used again as a write block; and

setting a high probability of replacement for the cache block; and

selecting for replacement one of the cache blocks with a highest probability for replacement.

17. A computer-implemented method of cache replacement, the method comprising steps of:

determining, for each cache block in a cache memory, a type of access that brought the cache block into the cache memory;

augmenting metadata associated with each cache block with an indicator of type of access request;

upon receiving an access request resulting in a cache miss, the cache miss indicating that a cache block needs to be replaced:

checking a least recently used stack comprising a temporally ordered listing of cache block access;

examining the indicator in the metadata for each cache block determined to be least recently used; and

if the indicator identifies the cache block as being a read block, determining that the cache block is likely to be used again as a write block; and setting a high probability of replacement for the cache block; and

selecting for replacement one of the cache blocks with a highest probability for replacement.