Browse Prior Art Database

Self Checking Page Replacement Control Networks

IP.com Disclosure Number: IPCOM000083763D
Original Publication Date: 1975-Jul-01
Included in the Prior Art Database: 2005-Mar-01
Document File: 2 page(s) / 49K

Publishing Venue

IBM

Related People

Chia, DK: AUTHOR [+2]

Abstract

This hardware implementation of a least recently used (LRU) algorithm provides fault checking with a minimum number of circuits and variables.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 2

Self Checking Page Replacement Control Networks

This hardware implementation of a least recently used (LRU) algorithm provides fault checking with a minimum number of circuits and variables.

Let X = [x(-1), x(-2),...,x(-n)] be some permutation of n numbers [1,2,....n] and can represent the present ordering of n data blocks, where the leftmost umber represents the address of the most used data block and the rightmost number, the least recently used. Let y be any number between 1 to n representing the currently used data block.

If the updated ordering of the addresses is Z = [z(-1), z(-2), ...,z(-n)] then the process of updating can be conveniently described in the following three steps:
(i) z(-1) = Y (ii) z(-j) = x(-j -1) if x(-i) = y for all i, 1 i j (iii) z(-j) = x(-j) if x(-i) = y for some i, 1 i j

It may be easily seen that the above algorithm places the external input y in the leftmost position and shifts all the components of the vector x that precede x(- k), x(-k) = y, by one position to the right.

In the figure, C(1), C(2), ...,C(n) represent the comparators capable of comparing y with each x, a 1 output indicates a match, 0 otherwise. The sum circuitries S(3), S(4), ...,S(n) perform the logical OR on a suitable combination of the outputs of the comparators. Specifically S(i) performs the OR operation of the outputs of C(1), C(2), ...,C(i-1).

The outputs of S(i) will be 1 if there was a match before the i/th/ stage, 0 otherwise. The gating networks G(2), G...