Browse Prior Art Database

Method of Modeling Least Recently used s. Algorithm

IP.com Disclosure Number: IPCOM000050101D
Original Publication Date: 1982-Sep-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 2 page(s) / 45K

Publishing Venue

IBM

Related People

Rivero, JL: AUTHOR

Abstract

This is a description of a method of modeling the compilation of LRU (least recently used) values. The LRU algorithm describes a way for handling order of hit entries in cache associated systems. The LRU identifies the older page in a cache section so this page can be moved to main memory and replaced with a requested page.

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

Page 1 of 2

Method of Modeling Least Recently used s. Algorithm

This is a description of a method of modeling the compilation of LRU (least recently used) values. The LRU algorithm describes a way for handling order of hit entries in cache associated systems. The LRU identifies the older page in a cache section so this page can be moved to main memory and replaced with a requested page.

Table A is a simple LRU table and the associated bit patterns. Table B is a table of the actual valid transitions, and a subset can be seen for each of the hit entries. The actual compilation (in logic) of "new" LRU from "old" LRU and the hit entry can be very complicated and therefore difficult to model. The problem is further complicated by the bit pattern gaps that can exist in the valid values of the LRU.

The drawing shows a flow chart for the algorithm that will compute the LRU values. Two tables are needed for this algorithm. The LRUTRANS Table is addressed with the "old" LRU value, and therefore it has as many entries as can be addressed by the LRU bit pattern. The content of the LRUTRANS Table is either the address to the LRUTAB Table, where the "new LRU resides, or an error flag. The error may occur due to invalid values of the "old" LRU. The LRUTAB Table contains the valid LRU values for any of the possible hits. This table describes all possible transitions that the LRU algorithm supports.

Note that the flow chart shows a check for a value of 5 in LRUADR and checking for only 3 val...