Patent ID: 7996622

Claim:
A method for detecting unused cache lines, said method comprising: in response to a cache miss, requesting that data be written from main memory to a cache; selecting a cache line in said cache to write said data to, wherein said selecting comprises i) identifying cache lines in said cache that are not referenced during a test interval, wherein bit values associated with said cache lines that are not referenced during said test interval have a binary first value at the beginning of said test interval and remain set to said first value at the end of said test interval, and ii) selecting said cache line, wherein said cache line is one of said cache lines not referenced during said test interval; allocating to said cache line a new address tag that replaces an existing address tag associated with said cache line; in response to said allocating, changing a bit associated with said cache line from said first value to a binary second value, wherein if said bit has said second value then said cache line is not a candidate to be written to; and writing said data to said cache line that is selected.