Browse Prior Art Database

Cache Control

IP.com Disclosure Number: IPCOM000083635D
Original Publication Date: 1975-Jun-01
Included in the Prior Art Database: 2005-Mar-01
Document File: 4 page(s) / 65K

Publishing Venue

IBM

Related People

Haims, MJ: AUTHOR

Abstract

A simple relocatable segment-pointer approach to a memory organization is illustrated in Fig. 1. When a cache is used, Fig. 2 could represent the implementation of the active cache. In this example, 8 bits of the IC (instruction counter) in the instruction register directly access the Cache Segment Table 41 and four segment entries are fetched in parallel. Fields F1X contain segmentable pointer bits that serve as tags. Fields F2X contain the high order bits of the real memory address. Fields F3X contain protection access codes.

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

Page 1 of 4

Cache Control

A simple relocatable segment-pointer approach to a memory organization is illustrated in Fig. 1. When a cache is used, Fig. 2 could represent the implementation of the active cache. In this example, 8 bits of the IC (instruction counter) in the instruction register directly access the Cache Segment Table 41 and four segment entries are fetched in parallel. Fields F1X contain segmentable pointer bits that serve as tags. Fields F2X contain the high order bits of the real memory address. Fields F3X contain protection access codes.

The four F1 fields are compared to the ID field via a four-way comparator 40. If any one compares equal, the corresponding F2 field is concatenated with the low-order bits of the IC field to form the address.

If there is no match, then the three bits in a fifth field (least recently used (LRU) register) identify which one of the four fields in the segment table entry should be replaced.

The four-way compare 40 compares four candidate values of F1 (F11, F12, F13 or F14) in table 41 with the desired value contained in the instruction register. The output of compare 40 is a 4-bit array wherein a "1" designates a "hit" and a "0" designates a "miss".

If there is a hit in any one of the four fields, the corresponding bit becomes 1 and the memory access can proceed with the indicated address; however, if there is a total miss, compare 40 shows 0000. Then, one of the fields in table 41 must be replaced. This algorithm makes the choice as to which field to replace.

Output values from compare 40 for any access cycle in which there is a hit are converted to a three-bit (ABC) representation in most recently used (MRU) register, according to the "tree" algorithm shown in Fig. 3.

A value of 0 for A indicates that the value of B is to be used to point either to hit position 1 (for which B=0) or to hit position 2 (for which B=1); the value of C is a "don't care" for A=0. If A=1, then B is a "don't care", and either hit position 3 is pointed to by C=0 or hit position 4 is pointed to by C=1.

Whenever the output of compare 40 is 000 representing a miss, the replacement algorithm decodes the contents of MRU from the previous hit into a "quasi-LRU" by inverting A and B if A=1, or by inverting A and C if A=0. This defines the entry in table 41 Fv1; Fx2, Fy3, or Fy4) to be replaced, and also the value to be left in the MRU after a cycle is completed in which a replacement has been made.

The following table shows the contents of the MRU following a hit:

MRU bits

When hit is are set at

in Field No. A B C

1 0 0 P

1

Page 2 of 4

2 0 1 P

3 1 P 0

4 1 P 1 where P is the previous value.

The replacement algorithm following a miss is summarized in the following table which indicates the MRU bit positions to be inverted from the last previous hit, to provide the new contents of the LRU and MRU. MRU contents MRU positions

from last to be

previous hit inverted

A B C

0 X X A, C

1 X X A, B where X = don't care.

MRU positions not in...