# US 2004/0083341 A1 · Weighted cache line replacement

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0083341 A1
- Document ID: US20040083341A1
- Status: Published application
- Kind: A1
- Application number: 10/279,246
- Filed: 2002-10-24
- Published: 2004-04-29
- Earliest claimed: 2002-10-24
- Assignees: International Business Machines Corporation
- Inventors: John T. Robinson; Robert B. Tremaine; Michael E. Wazlowski
- Web page: https://patentgrep.com/patent/US20040083341A1

## CPC

- G06F 12/126: with special data handling, e.g. priority of data or instructions, handling errors or pinning
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for selecting a line to replace in an inclusive set-associative cache memory system which is based on a least recently used replacement policy but is enhanced to detect and give special treatment to the reloading of a line that has been recently cast out. A line which has been reloaded after having been recently cast out is assigned a special encoding which temporarily gives priority to the line in the cache so that it will not be selected for replacement in the usual least recently used replacement process. This method of line selection for replacement improves system performance by providing better hit rates in the cache hierarchy levels above, by ensuring that heavily used lines in the levels above are not aged out of the levels below due to lack of use.

## Claims

### Claim 1

A method for use in a computer system with a cache memory and a cache memory controller, said method comprising:
detecting when cache lines that have been recently replaced in said cache memory are subsequently reloaded into said cache memory; and
giving priority to said cache lines by said cache memory controller, so that while said cache lines have priority they are locked and cannot be selected for replacement on cache misses.

### Claim 2 (depends on 1)

The method in claim 1, further comprising detecting, by the use of timestamps, cache lines that have been recently replaced in said cache memory and then subsequently reloaded.

### Claim 3 (depends on 1)

The method in claim 1, further comprising detecting, by the use of a FIFO array containing the addresses of recently replaced cache lines, cache lines that have been recently replaced in said cache memory and then subsequently reloaded.

### Claim 4 (depends on 1)

The method in claim 1, wherein a cache line that has priority retains priority for a predetermined number of accesses to the cache set in which the cache line resides, after which the cache line again becomes eligible for replacement.

### Claim 5 (depends on 1)

The method in claim 1, wherein a cache line that has priority retains priority for a predetermined number of misses to the cache set in which the cache line resides, after which the cache line again becomes eligible for replacement.

### Claim 6

A method for use in a computer system having a cache memory and a cache memory controller, said method comprising:
identifying cache lines that are removed from and subsequently reloaded into a cache memory more recently than a predetermined reload standard as priority cache lines, and
locking said priority cache lines to temporarily prevent said priority cache lines from being replaced on cache misses.

### Claim 7 (depends on 6)

The method in claim 6, wherein said identifying uses timestamps to determine if said cache lines are replaced more recently than said predetermined reload standard, and wherein said predetermined reload standard is a time period.

### Claim 8 (depends on 6)

The method in claim 6, wherein said identifying uses a first-in first-out (FIFO) table to determine if said cache lines are replaced more recently than said predetermined reload standard, and wherein said predetermined reload standard is a length of said FIFO table.

### Claim 9 (depends on 6)

The method in claim 6, wherein a priority cache line retains priority for a predetermined number of accesses to the cache set in which the cache line resides, after which said priority cache line loses priority status and again becomes eligible for replacement.

### Claim 10 (depends on 6)

The method in claim 6, wherein a priority cache line retains priority for a predetermined number of misses to the cache set in which the cache line resides, after which said priority cache line loses priority status and again becomes eligible for replacement.

### Claim 11

A method for use in a computer system having a cache memory and a cache memory controller, said method comprising:
identifying cache lines that are removed from and subsequently reloaded into a cache memory more recently than a predetermined reload standard as priority cache lines, and
locking said priority cache lines to temporarily prevent said priority cache lines from being replaced on cache misses irrespective of a cache miss line replacement process applied to non-locked cache lines.

### Claim 12 (depends on 11)

The method in claim 11, wherein said identifying uses timestamps to determine if said cache lines are replaced more recently than said predetermined reload standard, and wherein said predetermined reload standard is a time period.

### Claim 13 (depends on 11)

The method in claim 11, wherein said identifying uses a first-in first-out (FIFO) table to determine if said cache lines are replaced more recently than said predetermined reload standard, and wherein said predetermined reload standard is a length of said FIFO table.

### Claim 14 (depends on 11)

The method in claim 11, wherein a priority cache line retains priority for a predetermined number of accesses to the cache set in which the cache line resides, after which said priority cache line loses priority status and again becomes eligible for replacement.

### Claim 15 (depends on 11)

The method in claim 11, wherein a priority cache line retains priority for a predetermined number of misses to the cache set in which the cache line resides, after which said priority cache line loses priority status and again becomes eligible for replacement.

### Claim 16

A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method comprising:
identifying cache lines that are removed from and subsequently reloaded into a cache memory more recently than a predetermined reload standard as priority cache lines, and
locking said priority cache lines to temporarily prevent said priority cache lines from being replaced on cache misses.

### Claim 17 (depends on 16)

The program storage device in claim 16, wherein said identifying uses timestamps to determine if said cache lines are replaced more recently than said predetermined reload standard, and wherein said predetermined reload standard is a time period.

### Claim 18 (depends on 16)

The program storage device in claim 16, wherein said identifying uses a first-in first-out (FIFO) table to determine if said cache lines are replaced more recently than said predetermined reload standard, and wherein said predetermined reload standard is a length of said FIFO table.

### Claim 19 (depends on 16)

The program storage device in claim 16, wherein a priority cache line retains priority for a predetermined number of accesses to the cache set in which the cache line resides, after which said priority cache line loses priority status and again becomes eligible for replacement.

### Claim 20 (depends on 16)

The program storage device in claim 16, wherein a priority cache line retains priority for a predetermined number of misses to the cache set in which the cache line resides, after which said priority cache line loses priority status and again becomes eligible for replacement.
