Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Cache Replacement Utilizing an Enhanced LRU Replacement Algorithm to Improve System Performance

IP.com Disclosure Number: IPCOM000112332D
Original Publication Date: 1994-Apr-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 48K

Publishing Venue

IBM

Related People

Muhich, JS: AUTHOR [+2]

Abstract

This invention describes the modifications made to the standard LRU cache replacement algorithm to improve overall system performance.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 58% of the total text.

Cache Replacement Utilizing an Enhanced LRU Replacement Algorithm
to Improve System Performance

      This invention describes the modifications made to the standard
LRU cache replacement algorithm to improve overall system
performance.

1.  Introduction/History - 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...