Cache Replacement Utilizing an Enhanced LRU Replacement Algorithm to Improve System Performance
Original Publication Date: 1994-Apr-01
Included in the Prior Art Database: 2005-Mar-27
Muhich, JS: AUTHOR [+1]
This invention describes the modifications made to the standard LRU cache replacement algorithm to improve overall system performance.
Cache Replacement Utilizing an Enhanced LRU Replacement
to Improve System Performance
invention describes the modifications made to the standard
LRU cache replacement algorithm to improve overall system
- The cache replacement algorithm is an
important part of the overall system performance. The
replacement algorithm must provide as high a hit ratio as
possible and also must be deterministic in order to allow
programmers to optimize code for the hardware. While there are
replacement algorithms that provide high hit ratios, they afford
no sense of predictability for software. The Least Recently Used
(LRU) algorithm provides both a high hit ratio and software
predictability but is non-optimal for some system instructions.
In the true
sense of the definition, any time a cache
associativity class is accessed, it becomes the Most Recently
Used (MRU) class in the cache. For those cache instructions that
cause the cache sector to be marked invalid or simply clean dirty
data in the cache, it is non-optimal to change that associativity
class to MRU.
2. Solution- The
solution offerred maintains the predictability of
the LRU algorithm while enhancing system performance. The LRU
algorithm is slightly modified such that cache instructions that
only modify the cache state to invalid or only "clea...