# US 2014/0372705 A1 · Least-recently-used (lru) to first-dirty-member distance-maintaining cache cleaning scheduler

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

- Number: US 2014/0372705 A1
- Document ID: US20140372705A1
- Status: Published application
- Kind: A1
- Application number: 14/033,726
- Filed: 2013-09-23
- Published: 2014-12-18
- Earliest claimed: 2013-06-18
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Benjiman L. Goodman; Jody B. Joyner; Stephen J. Powell; Aaron C. Sawdey; Jeffrey A. Stuecheli
- Web page: https://patentgrep.com/patent/US20140372705A1

## CPC

- G06F 12/0891: using clearing, invalidating or resetting means
- G06F 12/0804: with main memory updating (G06F12/0806 takes precedence)
- G06F 12/122: of the least frequently used [LFU] type, e.g. with individual count value
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A technique for scheduling cache cleaning operations maintains a clean distance between a set of least-recently-used (LRU) clean lines and the LRU dirty (modified) line for each congruence class in the cache. The technique is generally employed at a victim cache at the highest-order level of the cache memory hierarchy, so that write-backs to system memory are scheduled to avoid having to generate a write-back in response to a cache miss in the next lower-order level of the cache memory hierarchy. The clean distance can be determined by counting all of the LRU clean lines in each congruence class that have a reference count that is less than or equal to the reference count of the LRU dirty line.

## Claims

### Claim 1

A method of scheduling cache write-back operations, the method comprising:
for each congruence class of a cache memory, determining an indication of a number of line allocations that can be supported by the current state of the congruence class without causing a write-back of a dirty line;
comparing the indication to a specified clean distance value to determine when to schedule write-backs of dirty lines of the cache memory;
responsive to the comparing determining that write-backs should be scheduled, scheduling the write-backs of one or more of the dirty lines.

### Claim 2 (depends on 1)

The method of claim 1, wherein the scheduling comprises:
generating a cache cleaning vector encompassing all of the congruence classes, specifying dirty lines to flush from the cache memory; and
periodically flushing the dirty lines according to the cache cleaning vector.

### Claim 3 (depends on 1)

The method of claim 1, wherein the cache memory is a victim cache that is the highest-order cache of a cache hierarchy, wherein the periodically flushing the dirty lines flushes the dirty lines to a system memory coupled to the cache memory.

### Claim 4 (depends on 1)

The method of claim 1, wherein the indication is a count of the number of clean cache lines that would be victimized according to a least-recently-used algorithm before the write-back of the dirty line would occur in response to a miss in a next lower-order cache memory.

### Claim 5 (depends on 4)

The method of claim 4, wherein the determining comprises:
summing a first number of clean members of the congruence class for each reference count of the least-recently-used algorithm; and
determining a total of the first number for each reference count lower than or equal to a reference count of the dirty line as the number of lines that would be victimized in response to the miss in the next lower-order cache memory.

### Claim 6 (depends on 1)

The method of claim 1, wherein the specified clean distance value is variable, whereby the clean distance can be varied according to system characteristics.

### Claim 7 (depends on 6)

The method of claim 6, further comprising setting the clean distance value according to a measure of a write burst delay for a write of one or more cache lines from the cache memory to a system memory.
