Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Patent
1997-10-17
2000-08-01
Chan, Eddie P.
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
G06F 1212
Patent
active
060981520
ABSTRACT:
A method and apparatus are provided for miss sequence cache block replacement in a cache including a plurality of cache blocks in a computer system. First checking for an invalid block is performed. Responsive to identifying an invalid cache block, the identified invalid block is selected for replacement. If an invalid cache block is not found, then checking for a first priority cache block and not equal to most recently used (MRU) state is performed. Responsive to identifying a first priority cache block and not equal to most recently used (MRU) state, the identified first priority cache block is selected for replacement. If a first priority cache block and not equal to most recently used (MRU) state is not found, then checking for a next priority cache block and not equal to most recently used (MRU) state is performed. Responsive to identifying a next priority cache block and not equal to most recently used (MRU) state, the identified next priority cache block is selected for replacement. In the absence of identifying an invalid cache block, a first priority cache block and not equal to most recently used (MRU) state, or a next priority cache block and not equal to most recently used (MRU) state, one of the plurality of cache blocks is randomly selected for replacement. A tag field stores the most recently used (MRU) state information which is used to determine where not to replace a cache block in the cache.
REFERENCES:
patent: 4493026 (1985-01-01), Olnowich
patent: 4885680 (1989-12-01), Anthony et al.
patent: 5130922 (1992-07-01), Liu
patent: 5261066 (1993-11-01), Jouppi et al.
patent: 5317716 (1994-05-01), Liu
patent: 5325504 (1994-06-01), Tipley et al.
patent: 5367653 (1994-11-01), Coyle et al.
patent: 5535361 (1996-07-01), Hirata et al.
patent: 5588131 (1996-12-01), Borrill
patent: 5706463 (1998-01-01), Ebrahim et al.
patent: 5729712 (1998-03-01), Whittaker
patent: 5793941 (1998-08-01), Pencis et al.
A Low-Cost Usage-Based Replacement Algorithm for Cache Memories, Yannick DeVille, pp. 53-58, ACM, 1990.
Data Cache Management Using Frequency-Based Replacement, Murthy V. Devarakonda and John T. Robinson, pp. 134-142, ACM, 1990.
Cache Operations by MRU Change, IEEE Transactions on Computers, vol. 37, No. 6, Rudolph N. Rechtschaffen and Kimming So, pp. 700-708.
Instruction Cache Replacement Policies and Organizations, IEEE Transactions on Computers, vol. C-34, No. 3, Mar. 1985, James R. Goodman and James E. Smith, pp. 234-241.
Cache Replacement with Dynamic Exclusion, Scott McFarling, pp. 191-200, ACM, 1992.
Pendse et al, "A Fuzzy Block Replacement Algorithm for Disk Caches", 1997, pp. 995-998, IEEE.
Mounes-Toussi, "The Effect of Using State-Based Priority Information in a Shared-Memory Multiprocessor Cache Replacement Policy," IEEE, 1998, pp. 217-224.
Chan Eddie P.
Ellis Kevin L.
International Business Machines - Corporation
Pennington Joan
LandOfFree
Method and apparatus for miss sequence cache block replacement u 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 miss sequence cache block replacement u, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for miss sequence cache block replacement u will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-674158