Cache storage management using dual stacks

Details Cache storage management using dual stacks Cache storage management using dual stacks

1999-10-08

2002-01-01

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S134000

Reexamination Certificate

active

06336167

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to data processing and more particularly to management of a data storage cache where cache control employs dual stacks.
BACKGROUND OF THE INVENTION
Memory systems in computers generally have two layers: a slow, inexpensive layer for mass storage (main memory) and a fast, more expensive layer (cache) for current use. Main memory is typically implemented in the form of disk storage while cache memory is typically implemented in semiconductor technology.
Cache management is an important aspect of every computer system. The goal is always to cache or store in the fast, more expensive layer of memory those items which will be frequently used in the future but only those items. Choosing which items to store in cache memory is done on the basis of item use history. A primary characteristic of cache performance is hit ratio, the frequency with which memory requests are satisfied using items already stored in the cache. It is well-known that some stored data is accessed more frequently than other stored data. If frequently used main memory, typically disk sectors, can be quickly and accurately identified, the data in such sectors can be moved to cache storage to improve the hit ratio and accelerate data retrieval, thereby boosting overall system performance.
While much of the following discussion is in the context of movement of stored data from main memory to cache memory in computer memory systems, it should be understood that caching techniques can also be useful where tables of calculated values must be constructed and maintained to support other computer processes. An example is a routing table used for making routing decisions in TCP/IP networks. By using caching techniques to build a small routing table containing only frequently used information, it may be possible to boost the overall performance of a router system.
Depending upon the application, cache control can be implemented using either of at least two techniques. According to the first technique, each location in a cache memory is used to store both a data unit to be made available to a computer system and a small, unambiguous label that functions as a pointer to that data unit. According to the second technique, only the labels are stored in the cache control element with the labels serving as pointers or addresses to data units stored in a separate cache memory unit. The first technique may be favored for applications in which the size of the data units is limited since the first technique avoids the need to address a separate cache memory. The second technique may be favored where large data units need to be accommodated. While the following description may refer only to the existence of labels or entries in cache stacks, it should be understood that the description is intended to cover cache systems implemented using either of the two techniques described.
Presently cache maintenance problems are commonly solved with a cache replacement algorithm known as Least Recently Used (LRU). In a computer memory system using LRU for cache management, the cache is refreshed each time a memory request is generated. Initially, all entries in the cache have a default value assumed here to be zero. When a new request can be satisfied using an entry already stored in the cache, the entry is retrieved from the cache without going to main memory. The entry is moved to the top of the cache stack and other entries in the stack are pushed down one position in the stack without changing their relative order.
When a request cannot be satisfied with cached entries, the entry is retrieved from main memory, sent to the requesting system and also written into the position at the top of the stack. Existing stack entries are pushed down one position with the stack entry previously at the bottom of the stack being discarded.
Discussions of LRU, related cache algorithms and their performance can be found at page 378 of
Computer Architecture: a Quantitative Approach
, 2
nd
edition, by J. Hennessy and D. Patterson, published in San Francisco by Morgan Kaufinan in 1990, and in R. Bachrach and Ran El-Yaniv,
Online list accessing algorithms and their applications: recent empirical evidence
, Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms, (1997) Vol. 8, pages 53-62.
SUMMARY OF THE INVENTION
The present invention is an improvement over known LRU algorithms which is believed to provide a higher hit ratio and thus an improvement in overall system performance under typical operating conditions.
The invention makes use of a cache storage control having two stacks. The first stack, which may be referred to as a preliminary stack, and the second stack, which may be referred to as the real stack, are preferably but not necessarily the same size; that is, have the same number of storage locations. When a new label request is received, both stacks are checked to determine whether a label already exists in the stacks. If the requested label is found in either stack, it is retrieved from the stack in which it is found and processed to recover the associated data unit. A conventional LRU algorithm of the type discussed above is used to refresh both the first and the second stacks. If the requested label is not found in either stack, the second stack is tested to determine if the bottom stack position is empty. If the bottom position is empty, the requested label (retrieved from a primary data source in a separate operation) is written to the top position of the second stack and all prior stack entries are pushed down one stack location. If the bottom position of the stack is not empty, all existing stack entries at and below a predetermined insertion point are shifted down one position with the label previously at the bottom the stack being discarded. The requested label is then written into the predetermined insertion point in the second stack.


REFERENCES:
patent: 5107457 (1992-04-01), Hayes et al.
patent: 5893148 (1999-06-01), Genduso et al.
patent: 6138210 (2000-10-01), Tremblay et al.

Affiliated with

Also associated with

Rating

Cache storage management using dual stacks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cache storage management using dual stacks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache storage management using dual stacks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2863169