Browse Prior Art Database

Optimum Implementation of LRU Hardware for a 4 Way Set Associative Memory

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

Publishing Venue

IBM

Related People

Chia, DK: AUTHOR

Abstract

A 4-input permutation network can be used to obtain an optimum implementation of hardware of an LRU (Least Recently Used) algorithm for a 4-way set-associative memory.

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 58% of the total text.

Page 1 of 2

Optimum Implementation of LRU Hardware for a 4 Way Set Associative Memory

A 4-input permutation network can be used to obtain an optimum implementation of hardware of an LRU (Least Recently Used) algorithm for a 4- way set-associative memory.

Fig. 1 illustrates a permutation network for the 4-input case.

The permutation cell, which is the building block for the network, contains a memory element F with two inputs (X1, X2) and two outputs. The memory state defines the two modes of operation. The "regular" mode defined by F = 1, arranges X1 ahead of X2 at the output, and the "crossing" node defined by F = 0 arranges X2 ahead of X1.

Let F1, F2, F3, F4, F5 be the respective present state of the permutation cells of Fig. 1 and X1, X2, X3, X4 represent the 4 blocks in the memory, the different arrangement of (X1, X2, X3, X4) can then be defined by the 5-tuple (F1, F2, F3, F4, F5). Thus, the problem of implementing the LRU hardware boils down to one of determining the next state equations for the permutation cells, given a new arrangement of the 4 memory blocks.

The next state equations for the five cells can be derived by analyzing Fig. 1 and noting that only one memory block can be referenced at a time. Once a block is referenced, it is arranged ahead of all other blocks, while the relative ordering of the remaining blocks are maintained. The next state equations after Boolean minimization is given as follows: f1 = X1 + X2F1 f2 = X3 + X4F2 f3 = X1 + X2 + X3X4F3 f4 = (...