Browse Prior Art Database

3/2/2 LRU Algorithm With Line Delete Capabilities

IP.com Disclosure Number: IPCOM000101695D
Original Publication Date: 1990-Aug-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 5 page(s) / 156K

Publishing Venue

IBM

Related People

Langston, DG: AUTHOR

Abstract

Disclosed is a least recently used (LRU) algorithm that allows the deletion of a line in the cache or in the directory.

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

3/2/2 LRU Algorithm With Line Delete Capabilities

       Disclosed is a least recently used (LRU) algorithm that
allows the deletion of a line in the cache or in the directory.

      The 3/2/2 LRU algorithm consists of a three-bit sequence code,
a two-bit most recently used (MRU) code, and a two-bit deletion code.
This algorithm will allow up to three sets to be deleted per line in
the cache and directory.  The sequence code represents one of the six
repeating sequences that occur in a standard LRU sequence: ABCD,
ABDC, ACBD, ACDB, ADBC, and ADCB.  The MRU in an encoding of the last
set for that line on which there was a directory hit.  The deletion
code is an encoding of the number of sets that are deleted for that
line.

      The order for the sets from the most recently used to the least
recently used set for a four-way set associative cache yields 24
possible combinations of set usage.  The combinations are as follows:
 ABCD BCDA CDAB DABC    ABDC BDCA CABD DCAB  ACBD BDAC CBDA DACB
 ACDB BACD CDBA DBAC    ADBC BCAD CADB DBCA  ADCB BADC CBAD DCBA

      By applying the mathematical concept of repeating series, the
above 24 combinations reduce to the aforementioned six repeating
sequences.  The exact order of set usage is given by knowing the
sequence and the starting point in that repeating sequence, also
called the most recently used set. This starting point is set
directly from the directory compares for that line. If a directory
hit...