Browse Prior Art Database

Upgrading LRU Positions in Cache Management

IP.com Disclosure Number: IPCOM000040295D
Original Publication Date: 1987-Oct-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 2 page(s) / 26K

Publishing Venue

IBM

Related People

Liu, L: AUTHOR

Abstract

The present invention describes a method for upgrading LRU (least recently used) stack positions upon repeated references. The method provides cache miss reductions in an environment with more transient access. In certain cache environments there are frequent transient accesses. A transient line access is one that is momentary and does not repeat in a long time. It is often beneficial not to put such transient lines to the cache or to the MRU (most recently used) positions. In this invention a scheme for caching lines is provided so that such transient accesses will have small impact on overall miss ratios. Consider an LRU mechanism for cache replacements in congruence classes. Let the set-associativity be N.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Upgrading LRU Positions in Cache Management

The present invention describes a method for upgrading LRU (least recently used) stack positions upon repeated references. The method provides cache miss reductions in an environment with more transient access. In certain cache environments there are frequent transient accesses. A transient line access is one that is momentary and does not repeat in a long time. It is often beneficial not to put such transient lines to the cache or to the MRU (most recently used) positions. In this invention a scheme for caching lines is provided so that such transient accesses will have small impact on overall miss ratios. Consider an LRU mechanism for cache replacements in congruence classes. Let the set- associativity be N. First consider a cache miss on a line L which causes the line brought into the cache to replace the LRU positioned line in the congruence class. After the line is brought in, instead of making L MRU as in usual cache designs, L is made the k-th MRU position in the congruence class, where 1&k&N is a design parameter. If L does not get accessed again in reasonable time, it will age out of the cache. Repeated access to the line will cause upgrade of its LRU position in its congruence class according to certain rules. A variety of upgrading policies (for repeated accesses to a cache line) may be chosen. One simple way is to make a line MRU upon repeated accesses. Another way is to gradually move the line toward the MRU position. Consider an implementation of the second policy in a PLRU environment. The replacement status of a congruence class is represented as a binary tree with log2(N) index nodes. Assume that N = 4 and K = 3. Fig. 1 depicts a replacement tree status, where an L(R, respectively) at a node indi...