Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-12-30
2003-02-04
Hudspeth, David (Department: 2651)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S133000, C711S144000
Reexamination Certificate
active
06516384
ABSTRACT:
BACKGROUND
(1) Field of the Invention
The invention relates to cache replacement schemes. More specifically, the invention relates to combined round robin cache replacement and cache line locking schemes.
(2) Background
Various schemes exist for defining what data is replaced when a new data set is loaded into a cache. One favored scheme in direct mapped caches is a least recently used (LRU) scheme. In an LRU scheme, as the name implies, the block of data that has been used least recently is replaced with any incoming data. Because of the locality of reference common to computer software execution and data usage, this has been found to be a fairly efficient cache replacement scheme. However, as set associativity increases, the complexity and overhead for an LRU scheme make such schemes less attractive due to increasing hardware requirements.
Additionally, in content addressable memory (CAM)-based caches without separate decoders, high set-associativity is achieved, and identifying where to write fill data becomes increasingly problematic. One possible solution that has been employed is a round robin replacement scheme in which a circular shift register loops through identifying the line to be loaded. This has the effect of throwing away the oldest information in the cache, but the replacement is completely independent of the frequency of use. Thus, it can result in a greater amount of cache thrashing.
Some prior solutions to prevent data from being kicked out of the cache prematurely was to allow way locking. These systems failed to provide much granularity. For example, in a two-way cache, half the cache would be locked, even if the block of data to be retained was relatively small. This often results in inefficient cache usage.
BRIEF SUMMARY OF THE INVENTION
A first plurality of latches are daisy chained together, forming a register, with each latch associated with a particular cache line. Similarly, a second plurality of latches are daisy chained together with each latch associated with a cache line. The first register defines a fill order of cache lines and the second register defines a lock order for the cache lines.
REFERENCES:
patent: 4783735 (1988-11-01), Miu et al.
patent: 5029072 (1991-07-01), Moyer
patent: 5353425 (1994-10-01), Malamy et al.
patent: 5408629 (1995-04-01), Tsuchiva et al.
patent: 5787431 (1998-07-01), Shaughnessy
patent: 5913224 (1999-06-01), MacDonald
patent: 5928343 (1999-07-01), Farmwald et al.
patent: 5928352 (1999-07-01), Gochman
patent: 5937429 (1999-08-01), Kumar et al.
patent: 6044478 (2000-03-01), Green
patent: 6073182 (2000-06-01), Jones et al.
patent: 6098152 (2000-08-01), Mounes-Toussi
patent: 6151655 (2000-11-01), Jones et al.
patent: 6240489 (2001-05-01), Durham et al.
patent: 2284911 (1993-12-01), None
Clark Lawrence T.
Clark Matthew M.
Blakley Sokoloff Taylor & Zafman LLP
Hudspeth David
Intel Corporation
Tzeng Fred F.
LandOfFree
Method and apparatus to perform a round robin and locking... 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 to perform a round robin and locking..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus to perform a round robin and locking... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3148827