Browse Prior Art Database

5-Bit Least Recently Used Code for 4-Way Set Associativity

IP.com Disclosure Number: IPCOM000034731D
Original Publication Date: 1989-Apr-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 2 page(s) / 55K

Publishing Venue

IBM

Related People

Tast, HW: AUTHOR

Abstract

This article relates to a 5-bit code which, by using a minimum of circuit means, can be converted into the commonly used 6-bit code in which it is updated. Then, the 6-bit code is reconverted into the 5-bit code and stored. Standard replacement algorithms for 4-way set associativity are stored and modified in the 6-bit code. This code denotes for each bit how two of four columns, say, 0, 1, 2, 3, are related to each other, meaning how column 0 is related to column 1 column 0 is related to column 2 column 0 is related to column 3 column 1 is related to column 2 column 1 is related to column 3 column 2 is related to column 3 The relation of the columns denotes which column has not been used for a longer period of time.

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

Page 1 of 2

5-Bit Least Recently Used Code for 4-Way Set Associativity

This article relates to a 5-bit code which, by using a minimum of circuit means, can be converted into the commonly used 6-bit code in which it is updated. Then, the 6-bit code is reconverted into the 5-bit code and stored. Standard replacement algorithms for 4-way set associativity are stored and modified in the 6-bit code. This code denotes for each bit how two of four columns, say, 0, 1, 2, 3, are related to each other, meaning how column 0 is related to column 1

column 0 is related to column 2

column 0 is related to column 3

column 1 is related to column 2

column 1 is related to column 3

column 2 is related to column 3 The relation of the columns denotes which column has not been used for a longer period of time.

The advantage of this code is that when one column is used, only three bits of the code have to be changed to indicate the order in which the four columns have been used. For each memory address six bits are stored. There are, however, only 24 valid combinations. The bits of the proposed 5-bit code are used as follows: 2 bits designate the most recently used (MRU) column, 2 bits designate the least recently used (LRU) column, and 1 bit designates the relation of the two columns which have neither been used most recently nor least recently. Depending upon the application, the LRU or the LRU and the MRU column is required in a simply coded form for controlling the write/update logic. The propos...