Browse Prior Art Database

Redundant LRU Encoding for Cache Directories

IP.com Disclosure Number: IPCOM000045995D
Original Publication Date: 1983-May-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 4 page(s) / 41K

Publishing Venue

IBM

Related People

Doyle, DE: AUTHOR

Abstract

A technique is described for implementing a least recently used (LR replacement algorithm for two-way set associative caches which provides a number of advantages over the conventional method of using a single directory bit to indicate the usage history of each pair of cache lines. (Image Omitted) cache, a MOD bit is set in the directory, and if that line is subsequently displaced from the cache, it is written back to the main store. Cache initialization following power-up requires that each line also have a validity bit in its directory entry.

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

Page 1 of 4

Redundant LRU Encoding for Cache Directories

A technique is described for implementing a least recently used (LR replacement algorithm for two-way set associative caches which provides a number of advantages over the conventional method of using a single directory bit to indicate the usage history of each pair of cache lines.

(Image Omitted)

cache, a MOD bit is set in the directory, and if that line is subsequently displaced from the cache, it is written back to the main store. Cache initialization following power-up requires that each line also have a validity bit in its directory entry.

Totalling the above requirements, the directory entry for each line requires l3 bits of information. Since there are only two possibilities as to which line of each pair or congruence class in the cache is the least recently used, only one bit is required to represent this information. Using normal byte-wide high speed arrays for the directory entries provides l6 available bits in each side of the directory; therefore, the LRU bit may be placed in either side. Side A has been chosen in Fig. l, which illustrates the traditional method of implementing this type of cache control.

During a processor data access, both sides of the directory are read and their contents tested against the upper bits of the requested address which is supplied by the translation mechanism. If neither comparison is successful, a cache miss exists. Since LRU replacement is being used, the line whose directory entry indicates that it is the least recently used of the two lines is displaced from the cache by the required line (accessed from main store), and the directory entry is updated to reflect the address of the newly fetched line. Note that since this line has just been accessed, the other side of the cache now becomes least recently used. Neglecting the cases where lines are invalid, four situations can occur.

1. The required data is found in side A.

Required action: Possible change of LRU bit in

side A.

Possible change of MOD bit in

side A.

2. The required data is found in side B.

Required action: Possible change of LRU bit in

side A.

Possible change of MOD bit in

side B.

3. The required data is not found, and A is least

recently used.

Required action: Put new upper address bits in

side A.

Change LRU bit in side A.

Update MOD bit in side A.

1

Page 2 of 4

4. The required data is not found, and B is least

recently used.

Required action: Put new upper address bits in

side B.

Change LRU bit in side A.

Update MOD bit in side B.

The entries under "Required action" refer only to cache directory maintenance and neglect any actions associated with cache data transfers.

In all cases a write operation is performed on side A. Case three requires that the upper address bits from the requested address be written to side A. In all other cases the previous contents of the side A entry must be preserved in a buffer provided for that purpose and rewritten along with the updated LRU bit...