Browse Prior Art Database

# Near Least-Recently-Used Algorithm for Six Associativity Clases

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

IBM

## Related People

Baldus, DF: AUTHOR

## Abstract

Many systems today utilize an associative cache. Since many addresses may map to the same cache line, it is desirable to hold in the cache at any given time those that are most likely to be referenced in the near future. How recently an address has been used is often a good predictor of this. Described below is an algorithm that protects the most recently used data in a cache row from being aged out. Aging occurs when a new access has an address which maps to a cache line with all congruence classes filled. This Least Recently Used (LRU) algorithm is designed for a six-way associative cache. (Six- way associative iplies six congruence clases.)

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

Near Least-Recently-Used Algorithm for Six Associativity Clases

Many systems today utilize an associative cache.  Since many
addresses may map to the same cache line, it is desirable to hold in
the cache at any given time those that are most likely to be
referenced in the near future.  How recently an address has been used
is often a good predictor of this.  Described below is an algorithm
that protects the most recently used data in a cache row from being
aged out.  Aging occurs when a new access has an address which maps
to a cache line with all congruence classes filled.  This Least
Recently Used (LRU) algorithm is designed for a six-way associative
cache.  (Six- way associative iplies six congruence clases.)

The algorithm used is based on the modified binary tree shown
below.  Note the repeat use of the letters d and f.

The numbers 0 through 5 at the bottom of the tree represent the
six congruence classes in the directory row.  Binary values are
assigned to letters a through g:'0' means to take the left path, "1"
implies the right.  A path is thereby established from a to one of
the six congruent classes.  This class represents the least recently
used entry and will be selected as the entry to age out when a new
access arrives with all classes in the row filled.  For example,
a='1', c='0', and f='1' points to congruence class 4.

The LRU is updated when one of three conditions occur:

1.  one of the current entries is accessed.

2.  a new entry must be formed without needing to age out a current
entry (all congruence classes are not being used).

3.  a new entry must be formed causing the aging out of a current
entry (all congruence classes are being used).

In (1) above, the LRU would be updated to point away from the
accessed entry.  For example, if class 2 were accessed only the
letters a, b, and e will be updated.  New values would be a=1, b=0,
c=unchanged, d=unchanged, e=1, f=unchanged, g=unchanged.  (All the
letters in the path to 2 are set to point away from the...