Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1998-10-29
2001-06-05
Ellis, Kevin L. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
Reexamination Certificate
active
06243792
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention is a method and an apparatus for identifying a least recently used (LRU) item of a group or set of items, such as the least recently used data entry associated with a memory cache.
2. Background
In a computer system, data is stored in a memory, such as a hard disk, a random access memory (RAM), or other memory. These memories are capable of storing large amounts of data, but they may be relatively slow or difficult to access. A small, fast memory known as a “cache memory” is used to store a subset of data stored in larger memory. The computer looks first in the cache to see if desired data is available, and if so, obtains it quickly from the cache memory. This is known as a cache “hit”. If the desired data is not found in the cache, a cache “miss”, the computer retrieves the data from a larger memory and then stores it in the cache for future use. There is a problem in the prior art of determining where in the cache to store the most recently retrieved data.
In many situations, the newly retrieved data replaces the least recently used (LRU) data already found in the cache. This scheme is based on the theory that the least recently used data is less likely to be accessed anytime soon than the more recently selected data.
There are several prior art methods for determining which data associated with the cache is the least recently used. Generally, the cache memory cache can be thought of as a plurality of lines of memory, where each line can store some retrieved data from larger memory. Each line of cache memory is an address at which data can be stored. In one prior art method, a time stamp is associated with each cache address at the time data is placed into the address location. This arrangement is illustrated in FIG.
1
. In this example, the memory cache has sixty-four (64) entries or addresses each having associated “time” data “TS” from a time stamp. As an example, the memory cache may comprise a 64×32 memory and the time stamp may comprise a 12 bit stamp indicating month, day, year, hour, minute and second. The least recently used item associated with the cache may be identified from the address or entry having the “oldest” time as indicated by the time stamps.
This method has several disadvantages. One problem is that the time stamp requires a large number of bits to facilitate a time stamp which has sufficient precision to identify the relative age of items. For example, the twelve (12) bit time stamp described above only permits the time stamp to indicate time to the nearest second. In such a case, many entries may be time stamped with the same time, preventing them from being distinguished as the least recently used.
Another problem is that substantial effort is required to identify the least recently used item. In the case of the above-referenced 64×32 memory, if one uses a 4-way search (that is, a search in which four comparisons can be made per cycle) it takes 64 cycles to read through all of the entries and determine the oldest time stamp, and thus the least recently used entry. Even if the memory cache is divided into two 32×32 memories, it takes thirty-three (33) cycles to determine the oldest time stamp.
In another method, a global counter is associated with the memory cache and counts each access to the cache. This arrangement is generally illustrated in FIGS.
2
(
a-b
). Each address or entry of the cache is provided with a count value equal to the count value (C0-C63) of the global counter at the time the entry is accessed. In the arrangement illustrated in FIG.
2
(
a
), the memory has sixty-four (64) addresses or entries, where each entry has been accessed in order and the global count values have been assigned in order.
The least recently used entry is defined as that entry having the lowest associated count value. By searching for the lowest count value in the cache, the least recently used item is supposed to be identifiable.
This arrangement has the significant drawback that the counter will eventually “roll-over” or reset. For example, if the global counter is a six (6) bit counter permitting sixty-four (64) count values from zero (0) to sixty-three (63), the counter will roll over to zero (0) at the next cache access after sixty-three (63). When the counter rolls over, the new entry is assigned the count value of zero (0). This arrangement is illustrated in FIGS.
2
(
a
) and
2
(
b
).
It is noted that the cache is commonly accessed without replacing the least recently used item. In the case illustrated in FIG.
2
(
b
), when the global counter has a count value of sixty-three (63), address or entry E
3
is accessed. The global counter resets to zero (0) and assigns count value zero (0) to entry E
3
.
If the next access of the cache is for the purpose of replacing the least recently used item with an item just retrieved remotely, it is not possible to correctly identify the least recently used item. In the example illustrated in FIG.
2
(
b
), entries E
1
and E
3
both have assigned count values of zero (0). This is a problem not only because there are two entries with the same count value, but also because the item associated with one entry is actually the oldest and the item associated with the other entry is the newest. This problem results from the “rollover” problem associated with the global counter. With two possible entries being the least recently used entry, the chance of identifying the LRU item correctly is 50%. If a more recently used item is overwritten, and then that same item is requested in a subsequent memory access, the data will not be there, resulting in a cache miss. Cache efficiency is reduced as the number of cache misses increases.
Another problem with this method is that, as with the time stamp system, many cycles of comparisons are required to find the lowest count value to identify the entry or address containing the least recently used item. The large number of comparisons limits system performance.
A method and apparatus for identifying the least recently used item of a group of items which overcomes these problems is desired.
SUMMARY OF THE INVENTION
The present invention is a method and apparatus for identifying the least recently used item of a set of items. In accordance with one or more embodiments of the invention, a unique count value is associated with each item. More particularly, a first count value is assigned to an oldest or least recently used item, a second count value is assigned to a newest or most recently used item, and items having an age between the oldest and newest are assigned successive count values between the first and second count values in accordance with the age of the item.
When an item is accessed, a pivot count value associated with the accessed item is determined. The pivot count value comprises the count value of the accessed item at the time it is accessed. Each count value between the pivot count value and the second count value is incremented in the direction of the first count value. The count value associated with the accessed item is then reset to the second count value. The least recently used item is identified as that item associated with or having the first count value.
In one or more embodiments, each item is associated with an address of a memory cache. Each count value is associated with a counter corresponding to an address of the memory cache.
In one or more embodiments, the first count value is a predetermined high count value and the second count value is a predetermined low count value. The step of incrementing comprises the step of raising the value of the count value of each address location having a count value falling between the pivot count value and predetermined low count value towards the predetermined high count value. The least recently used item is identifiable as the item associated with the predetermined high count value.
In one or more embodiments, the first count value is a predetermined low count value and the second count value is a predetermined high count value. T
Ellis Kevin L.
Krall Noreen
Sun Microsystems Inc.
LandOfFree
Method and apparatus for identifying a least recently used item 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 and apparatus for identifying a least recently used item, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for identifying a least recently used item will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2484062