Browse Prior Art Database

Replacement Algorithm for a Fully Associative Cache

IP.com Disclosure Number: IPCOM000122807D
Original Publication Date: 1998-Jan-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 77K

Publishing Venue

IBM

Related People

Carnevale, MJ: AUTHOR [+2]

Abstract

Disclosed is a replacement algorithm for a fully associative cache that is more flexible than previous algorithms, such as Least Recently Used (LRU) and First In-First Out (FIFO).

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

Replacement Algorithm for a Fully Associative Cache

      Disclosed is a replacement algorithm for a fully associative
cache that is more flexible than previous algorithms, such as Least
Recently Used (LRU) and First In-First Out (FIFO).

      Cache line replacement for fully associative data caches need a
relatively large amount of hardware in order to keep track of the
Least Recently Used (LRU) cache lines.  If a First In-First Out
(FIFO) replacement algorithm is used to determine which cache line
gets replaced, there is no flexibility associated with trying to keep
cache lines in the cache that are frequently getting referenced in
relation to the other cache lines that currently reside in the cache.

      If the idea is accepted that the least recently used cache line
will not always be selected for cache line replacement, but at the
same time an effort is made to try to recognize that the most
recently used  cache lines should not be replaced, then a reference
bit combined with  a FIFO pointer can be used together to reduce the
amount of hardware and  cycle time required for cache directory
lookups.

      For a fully associative cache with 256 lines, an eight bit
pointer can be implemented that points to the next cache line that is
to be replaced.  When the cache is empty (power-up time), the pointer
simply points to line 0 and increments up to line 255 as the cache
lines are brought into the cache.  Each cache line also has a
reference bit (one latch/cache line) that will set when a cache line
is referenced after it has been initially inpaged into the cache.
When the pointer value reaches 255, the cache is full and the next
access to the cache that misses will cause a cache line to be
replaced.  When the cache full  point is reached, the pointer will
wrap back to line 0 and, if line 0 had  not been referenced since it
was brought into the cache, it is selected  as the cache line to be
replaced.  If line 0 had been referenced, the pointer increments to
point to line 1 and line 0's reference bit i...