System and method for cache line replacement

Details System and method for cache line replacement System and method for cache line replacement

1998-09-30

2001-12-04

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S136000, C711S160000

Reexamination Certificate

active

06327643

ABSTRACT:

TECHNICAL FIELD
The present invention relates in general to data processing systems, and in particular, to an operation of cache memory.
BACKGROUND INFORMATION
A cache memory can be constructed in many ways. Initially, the cache is empty, and the cache elements can be conceived as having pointers to the beginning and the end of the cache. These pointers are referred to as the head and tail pointers. The head pointer points to the next available cache line (newest), whereas the tail pointer points to the beginning, or oldest cache line within the cache. As rasterization of a display occurs, the head pointer is incremented as cache misses occur, until the cache fills. Then, the head pointer wraps to the beginning or oldest cache line, and the tail pointer is incremented. This concept is referred to as a circular buffer.
A cache line has associated tags, which track to memory pages, banks, and discreet memory locations within each page/bank group. As prefetching or cache misses occur, current or subsequent cache items may actually point to memory locations with no spatial coherence to each other (i.e., on different memory pages/addresses).
Using an LRU approach, cache line replacement would be forced to incur a page access, possibly degrading system memory performance while the memory subsystem starts the new (or old) cache memory page. This problem might be exaggerated if the cache line to be replaced must first be written out, and it is on a totally different memory page. The system performance degradation is due to the time associated with memory page crossings.
Therefore, there is a need in the art for an improved cache line replacement technique, which improves upon the prior art LRU method.
SUMMARY OF THE INVENTION
The present invention addresses the foregoing need by differentiating between cache lines that have been written with those that have not. Replacement selection begins with a determination if the cache is full. If not full, the cache line indicated by the LRU head pointer is filled. If the cache is full, then the oldest cache line that has been written back is replaced (LRU). If no unwritten cache lines are available (all cache lines are dirty), the oldest cache line that meets pipeline temporality criteria and is currently on page and on bank is written back and replaced. If there are no cache lines available that meet the above criteria, then the cache line indicated by the tail (LRU) pointer is replaced, and the system incurs a page access penalty.
This process is used for cache misses occurring during a prefetch access and for write mode accesses.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention.


REFERENCES:
patent: 5611071 (1997-03-01), Martinez, Jr.
patent: 5636355 (1997-06-01), Ramakrishnan et al.
patent: 5737751 (1998-04-01), Patel et al.
patent: 5887152 (1999-03-01), Tran

Affiliated with

Also associated with

Rating

System and method for cache line replacement does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method for cache line replacement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for cache line replacement will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2570207