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

Least Recently Used Page Replacement Algorithm for Cache Memories

IP.com Disclosure Number: IPCOM000049938D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 3 page(s) / 78K

Publishing Venue

IBM

Related People

Check, GP: AUTHOR [+2]

Abstract

The least recently used (LRU) algorithm applies to a cache memory having a number of independently replaceable pages. When the cache is full and a memory reference is not found in any page in the cache, the page to be replaced is the one which has not been accessed for the longest amount of time. An ordered history of page numbers, called an LRU stack, must be generated for successive memory references.

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

Page 1 of 3

Least Recently Used Page Replacement Algorithm for Cache Memories

The least recently used (LRU) algorithm applies to a cache memory having a number of independently replaceable pages. When the cache is full and a memory reference is not found in any page in the cache, the page to be replaced is the one which has not been accessed for the longest amount of time. An ordered history of page numbers, called an LRU stack, must be generated for successive memory references.

Fig. 1 shows a system having a processing unit (CPU) 10, and a main storage 11 interconnected by an address bus having high-order page address bits 12 and low-order bits 13, and by bidirectional data bus 14. Cache memory modules 15 hold pages P(1)-P(N), whose page numbers are held in page registers 16. New page numbers are updated, when necessary, from bus 12 via gates 17. Stored page numbers are matched against the current page address in comparators 18, whose signals enable the appropriate cache module 15 at a cycle time T1, via gates 19.

LRU control logic 20 (Fig. 2) uses the page-match signals 21 to determine which page is the oldest, and to replace it with a new page number via control lines 22. If the requested page is not in cache, signal 23 requests the data from storage 11. When CPU 10 requests a storage reference in a cycle divided into four time signals T1-T4, logic 20 performs the following sequence of events. AT time T1: Generate NoMatch = 1 if no page-match signal 21 is

active.

IF NoMatch = 0: (i.e., if a match has occurred)

AT time T2:

Transfer matched page P(m) of cache 15 to/from data

bus 14.

Compare a count CTR(m) for the matched page to

counts CTR(i) for all other pages.

AT time T4:

FOR all CIR(i) c CTR(m):

Increment CTR(i).

Clear CTR(m) = 0.

IF NoMatch = 1 (i.e., if the desired page is not in any cache module)

AT time T2:

Start main-storage cycle via signal 23.

Determine which CTR(h) contains the highest

possible count.

AT time T3:

Gate new page address into REG(h) via signal 22.

Load data from storage 11 to P(h) of cache 15.

AT time...