Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-05-31
2003-12-30
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S134000, C711S135000, C711S138000, C711S160000
Reexamination Certificate
active
06671780
ABSTRACT:
FIELD OF THE INVENTION
This invention pertains to caches in computer systems, and more particularly to a method for replacing blocks in the cache.
BACKGROUND OF THE INVENTION
Caches provide a closer, faster access to important information for the Central Processing Unit (CPU) of a computer. For example, caches are often used to store memory blocks that have been accessed recently by the CPU. But it is not practical to make caches large enough to store all of the available memory blocks. Aside from the obvious fact that such a large cache would make the main memory unnecessary, cache memory is more expensive than main memory. To keep costs down, caches tend to be small in size relative to main memory.
Because caches cannot store every block in main memory, when a new block needs to be allocated from the cache, the cache must use a replacement policy to decide what block currently in the cache is to be replaced. Various replacement policies are known in the art. The random replacement policy randomly selects an existing cache block to replace. The Least Recently Allocated (LRA, sometimes also called First In, First Out, or FIFO) replacement policy tracks how long each block has been in the cache and replaces the block that has been in the cache the longest. The Least Recently Used (LRU) replacement policy tracks how long it has been since each block in the cache has been used and replaces the block that has gone the longest since it was last used.
Assuming that the sequence of memory block misses is not known in advance, the LRU replacement policy generally provides the best performance. However, the LRU replacement policy is the most complicated replacement policy to implement. Information about each cache block access must be kept to maintain the order of cache block accesses, thus requiring fields to be updated at every access. The random and LRA replacement policies are easier to implement but provide poorer performance.
The present invention addresses this and other problems associated with the prior art.
REFERENCES:
patent: 5526511 (1996-06-01), Swenson et al.
patent: 5715427 (1998-02-01), Barrera et al.
patent: 5737753 (1998-04-01), Tsuchiya et al.
patent: 5778442 (1998-07-01), Ezzat et al.
patent: 5897655 (1999-04-01), Mallick
patent: 5966722 (1999-10-01), Singh et al.
patent: 6161167 (2000-12-01), Witt
patent: 6230237 (2001-05-01), Tao et al.
patent: 6240489 (2001-05-01), Durham et al.
patent: 6345344 (2002-02-01), Arimilli et al.
patent: 6523092 (2003-02-01), Fanning
Lai Konrad
Lu Shih-Lien L.
Bataille Pierre-Michel
Intel Corporation
Kim Matthew
Marger & Johnson & McCollom, P.C.
LandOfFree
Modified least recently allocated cache replacement method... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Modified least recently allocated cache replacement method..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modified least recently allocated cache replacement method... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3135091