Browse Prior Art Database

Dual Tracking Least Recently Used Scheme

IP.com Disclosure Number: IPCOM000106524D
Original Publication Date: 1993-Nov-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 82K

Publishing Venue

IBM

Related People

Brown, JD: AUTHOR [+2]

Abstract

Least Recently Used (LRU) schemes are used to determine which entry in a memory unit (i.e., cache, Lookaside buffer) was Least Recently Used. This Publication shows another LRU alternative for keeping a complete order LRU for N members or associative classes. This scheme is good for memory units with a large number of classes and for memory units which have more than one output port for accesses.

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

Dual Tracking Least Recently Used Scheme

      Least Recently Used (LRU) schemes are used to determine which
entry in a memory unit (i.e., cache, Lookaside buffer) was Least
Recently Used.  This Publication shows another LRU alternative for
keeping a complete order LRU for N members or associative classes.
This scheme is good for memory units with a large number of classes
and for memory units which have more than one output port for
accesses.

      Example

      A Lookaside Buffer (LB) for address translation is designed as
an 8 way associative entry Buffer.  The Lookaside Buffer LRU logic
will track the order these entries are used so a new entry will
replace the least recently used (LRUed) lookaside buffer entry.
Instruction dataflow and Data dataflow share the Lookaside Buffer.
Each dataflow uses the Lookaside Buffer entries independently.  All
the possible combinations for one LB entry with these two Dataflows
accessing the Lookaside buffer independently are shown below.  (Miss
and Hit refer to Address Translation hit or miss.)  (When using the
words "above" and "below", picture the 8 entries in a stack where the
MRUed member is at the top (above the others) and the the LRUed
member is at the bottom (below the others).  This is shown in the
Figure.

1.  Instruction Miss and Data Miss

2.  Instruction Miss and Data Hit

    o   Data hit on entry

    o   Data hit on another entry

3.  Instruction Hit and Data Miss

    o   Instruction hit on entry

    o   Instruction hit on another entry

4.  Instruction Hit and Data Hit

    o   Instruction hit above and Data hit above entry

        a.  Same entry hit for both

        b.  Different entries hit

    o   Instruction hit above and Data hit Below entry

    o   Instruction hit Below and Data hit above entry

    o   Instruction hit Below and Data hit Below entry

        a.  Same entry hit for both

        b.  Different entries hit

5.  Instruction hit on entry and Data hit above entry

6.  Instruction hit on entry and Data hit below entry

7.  Instruction hit above entry and Data hit on entry

8.  Instruction hit below entry and Data hit on entry

9.  Instruction hit on entry and Data hit on entry

   ...