Browse Prior Art Database

Cache Directory for Least Recently Used Replacement Algorithm

IP.com Disclosure Number: IPCOM000051785D
Original Publication Date: 1981-Mar-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 2 page(s) / 29K

Publishing Venue

IBM

Related People

Hogerhuis, W: AUTHOR

Abstract

In a four-way associative directory for a cache memory, a directory wor holds data relating to the recent usage of each of the four storage blocks. This data in the directory word is coded in such a way that a few bits in the word give the sequence of recent use of all four memory blocks and thereby identify the one section that has been least recently used. The validity bits are also coded in a way that reduces the required length of the directory word.

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

Page 1 of 2

Cache Directory for Least Recently Used Replacement Algorithm

In a four-way associative directory for a cache memory, a directory wor holds data relating to the recent usage of each of the four storage blocks. This data in the directory word is coded in such a way that a few bits in the word give the sequence of recent use of all four memory blocks and thereby identify the one section that has been least recently used. The validity bits are also coded in a way that reduces the required length of the directory word.

In a four-way associative cache memory system, the cache is divided into four memory sections. The four sections are individually identified by two high- order bits of the cache address, and the low-order bits of the address apply to each of the four sections. A block of data from a backing store is loaded into the cache in any one of the sections where the low-order cache address bits are the same as the low-order backing store address bits. A cache directory holds information that permits the high-order backing store address bits to be transformed into the two high-order cache address bits that identify the cache section where the backing store data is located, if in fact the backing store data is located in the cache. When new data is required from the backing store, a validity bit in the directory is checked to find any unused space in the cache. If no space is available in the cache, a block must be bumped from the cache. The cache directory contains information for choosing the block that is to be bumped.

Fig. 1 shows the format of a cache directory word. Bit positions 3-6 are not used in the operations being described. Bits 7-8 identify the section of cache memory most recently used, and bits 9-10 identify the section next most recently used. The remaining two sections of the cach...