Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-02-24
2001-05-29
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S129000, C711S133000, C711S144000
Reexamination Certificate
active
06240489
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present disclosure relates to a method for improving data processing in general and, in particular, to a method of implementing a pseudo Least Recently Used (LRU) mechanism in a cache memory within a data processing system. Still more particularly, the present disclosure relates to a method for implementing a pseudo LRU mechanism in a four-way cache memory within a data processing system.
2. Description of the Prior Art
A data processing system typically includes both a system memory and a cache memory. A cache memory is a small and relatively high-speed memory interposed between a processor and the system memory. Information such as data or instructions may be copied from a portion of the system memory into the cache memory so that the information will be available to the processor in a relatively short amount of time when the requested information resides in the cache memory.
However, if the information requested by the processor cannot be found in the cache memory (i.e., a cache miss), the requested information must be obtained from the system memory. After the information has been obtained from the system memory, a copy of the information may also be placed in the cache memory for future usage, in addition to the immediate usage by the processor. Thus, when all possible storage locations for the information within the cache memory are completely filled, some of the information already stored in the cache memory has to be replaced by the new information via an operation known as linefill. Needless to say, it is important to have a strategy to decide what specific information already stored in the cache memory needs to be discarded in order to make room for the new information. Generally speaking, usually either a Least Recently Used (LRU) or a pseudo LRU strategy is employed to select a cache line of information to be replaced when a cache miss occurs. This is because statistical data has shown that for low associativity caches (caches that are configured as four-way set associative or less), an LRU type of replacement scheme can best minimize the cache miss ratio when compared to other cache replacement schemes such as random replacement or round-robin. The present disclosure provides a method for implementing a pseudo LRU cache replacement mechanism with fewer bits than prior art implementations.
SUMMARY OF THE INVENTION
Within a four-way set associative cache memory, each congruence class contains four cache lines. In accordance with a method of the present invention, each congruence class within the cache memory is associated to a least recently used (LRU) field that has four bits. Each of four cache lines within the congruence class is then assigned a respective set number. The set number of a cache line designated as a least recently used set among the four cache lines is stored in two bits of the LRU field. The set number of a cache line designated as a most recently used set among the four cache lines is stored in another two bits of the LRU field. In response to a determination that the set number of the least recently used set is higher than the set number of the most recently used set, one of the remaining two cache lines that has a higher set number is assigned to be a second least recently used set.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5765191 (1998-06-01), Loper et al.
patent: 5875464 (1999-02-01), Kirk
Durham Christopher McCall
Hanley Brian Patrick
Bracewell & Patterson L.L.P.
International Business Machines - Corporation
Namazi Mehdi
Salys Casimer K.
Yoo Do Hyun
LandOfFree
Method for implementing a pseudo least recent used (LRU)... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for implementing a pseudo least recent used (LRU)..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for implementing a pseudo least recent used (LRU)... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2465148