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

Line Replaceable Unit Control Mechanism for Cache Memories

IP.com Disclosure Number: IPCOM000118710D
Original Publication Date: 1997-May-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 2 page(s) / 42K

Publishing Venue

IBM

Related People

Nakada, T: AUTHOR [+2]

Abstract

Disclosed is a mechanism for implementing the Line Replaceable Unit (LRU) replacement algorithm of cache memories.

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

Line Replaceable Unit Control Mechanism for Cache Memories

      Disclosed is a mechanism for implementing the Line Replaceable
Unit (LRU) replacement algorithm of cache memories.

      A N-way set-associative cache memory consists of N banks, as
shown in Fig. 1.  When the cache memory is accessed, the address and
status fields of the N banks are simultaneously read to detect a
cache hit or miss.  On a cache miss, a victim line to be flushed is
selected based on the LRU replacement policy.  This article shows a
LRU replacement mechanism that minimizes the number of bits to be
changed on  a LRU update.  On a cache hit or miss, only the LRU field
of one bank needs to be updated.

      Each cache line has a N-1 bit LRU field to determine which bank
contains the least recently used data.  Let Z(i, j) (0 <= i < N, 0 <=
j < N, i not= j) be the LRU bits of bank i.

          Fig. 2 The Formula which is used by the LRU Bank

The mechanism operates as follows:
  1.  Initialization
        Set all Z(i, j) (0 <=  i < N,  0 <=  j < N, i not=  j) to 0.
  2.  Definition
        If i < j and Z(i, j) xor Z(j, i) = 0 then bank i is newer
         than bank j.
        If i < j and Z(i, j) xor Z(j, i) = 1 then bank i is older
         than bank j.
        If i > j and Z(i, j) xor Z(j, i) = 0 then bank i is older
         than bank j.
        If i > j and Z(i, j) xor Z(j, i) = 1 then bank i is newer
 ...