JPS6029419B2 - buffer memory device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention provides a buffer memory device, in particular, in managing the replacement order of block unit information being transferred to the buffer memory, when a so-called buffer hit occurs, the hit A buffer memory device that performs processing to lower the replacement order of an entry position (that is, make it difficult to rebrace) and also perform processing to increase the replacement order of the entry position when the block unit information being transferred becomes invalid. It is related to.

As is well known in the art, a buffer memory device is configured to have a plurality of entry locations, but since the number of entry locations is limited, replacement processing, such as replacement processing using an LRU algorithm, is performed.

When it becomes necessary to load new block-by-block information from the main memory, the one with the highest placement order is replaced. In the above-described place processing, in addition to the determination based on the LRU algorithm described above, a determination as to whether or not block unit information stored at a certain entry position is invalid has conventionally been added.

That is, for example, first, it is checked whether there is an entry position where an invalid indication is displayed, and if there is only one entry position where an invalid indication is displayed, the determination by the above LRU algorithm is omitted and the entry position is Replace with . Furthermore, if there is no entry position with an invalid indication, a determination is made using the LRU algorithm. However, in the above case, if there are multiple entry positions with invalid indications, it is necessary to decide in advance which one to replace, which becomes more complicated as the number of entry positions increases. .

The purpose of the present invention is to solve the above-mentioned problems, and the buffer memory device of the present invention transfers the contents of the main memory in units of blocks onto a buffer memory having a plurality of entry positions, and then processes the contents. The above buffer and
In a data processing system that executes processing while accessing memory, a validity bit is provided for each block transferred to each entry position on the buffer, and a validity bit is provided for each block transferred to each entry position on the buffer. It manages the place order between block units transferred to the entry position, holds place information, and determines the next entry position to be replaced based on the contents of the place information holding section and the replacement information holding section. It has a place entry determination circuit section for determining a place entry, and a brace information update processing section for updating the content of the IJ place information holding section, and the replacement information update processing section is configured to update the buffer information using the content of the entry position. The above IJ place information is updated to lower the consigned IJ place ranking for the entry position at the time of a hit, and to increase the IJ place ranking for the relevant entry position at the time of invalidation when the content of the entry position is invalidated, and then It is characterized in that it is configured to be stored in the information storage unit.

This will be explained below with reference to the drawings. FIG. 1 is an explanatory diagram for explaining replacement information, FIG. 2 is an explanatory diagram for explaining an update algorithm for replacement information according to the present invention, and FIG. FIG. 4 shows the configuration of an embodiment of the replacement processing circuit section in the buffer memory device of the present invention.

Assuming that there are four entry positions in the buffer memory, the replacement information is RO1 shown in Figure 1.
, R02, R03, R12, R13, and R23. In other words, set the entry position to #0, #1
, #2, #3, create a 4x4 grid and use bits RO1 and R02 to indicate the order of entry positions.
, R03, R12, R13, and R23. And entry position #3 replace = R03・R13・R2
3 entry position #2 replace = R02, R12, R2
3 entry position #1 replace = RO1・R12・R1
3...'1} Entry position #0 replace = RO1・
Based on R02 and R03, the entry position to be replaced is determined.

The replacement entry position has been managed using the conventionally known LRU algorithm using the entrusted IJ place information ROI to R23 as follows.

That is, if a buffer hit now occurs at the #1 entry position (in this specification, the case where a new block of information is transferred and stored in a certain entry position by block transfer is also referred to as a buffer hit), 1st
Bits RO1, R12, R in column #1 in the grid shown in the diagram
13 all set to logic “1” and #1 row bit RO1
, R12, and R13 were all set to logic "0". As a result, even if the #1 entry position was previously in a state of being replaced, the bit rewriting causes the #1 entry position to have the lowest replacement order. In other words, it is made the least likely to be replaced. As for other entry positions, the replacement ranking will be increased while maintaining the previous ranking. Conventionally, replacement entry positions have been managed using the LRU algorithm as described above, but when information in blocks at a certain entry position is invalidated, a valid bid is simply set to, for example, logic "1". The above IJ place information was never updated.

Therefore, as mentioned at the beginning of this specification, consideration must be given to the case where the entry becomes invalid at a plurality of entry positions. The present invention improves this point, and as in the past, when a buffer hit occurs, an update is performed to lower the replacement order of the entry position, and when the entry becomes invalid, an update is performed to increase the replacement order of the entry position. Make it.

With this, when replacing, it is sufficient to simply extract and replace the item with the highest replacement ranking. FIG. 2 explains the replacement information updating algorithm according to the present invention.

The figure shows cases where a buffer hit occurs and an invalidity occurs from a state in which the replacement order is initially lower in the order of #3 entry position, #2 entry position, #1 entry position, #0 entry position. It shows the change in Nori place ranking. That is, 1 indicates a case where a buffer hit occurs at the #3 entry position from the state on the left side of the diagram.

0 indicates that a buffer hit occurs at the #1 entry position.

m indicates a case where a buffer hit occurs at the #2 entry position. W indicates a case where a buffer hit occurs at the #0 entry position. Further, V indicates a case where an invalidity occurs at the #2 entry position. Town indicates the case where an invalid occurs at the #0 entry position. The skin shows the case where an invalidity occurs at the #3 entry position. The plate shows the case where an invalid occurs at the #1 entry position. As can be seen from the figure, when a buffer hit occurs, the bits in the column of the illustrated square corresponding to the entry position are set to logic "0" in order to minimize the replacement order of the entry position.
” and the horizontal bit is set to logic “1”. In addition, if an invalidity occurs, in order to maximize the replacement order of the entry position, the bits in the vertical column of the grid corresponding to the entry position are set to logic "1" and the bits in the horizontal row are set to logic "0". do. The logic for performing such bit changes is expressed by the following logical formula.

Note that RDROI to RDR23 are the bit information corresponding to the bits ROI to R23 shown in FIG. 1 before the bit change processing, respectively, and the departure Ti is the buffer and
iVHTi, a signal that becomes logic “1” when a hit occurs;
is the logic "when an invalidity occurs at the #i entry position"
1'' signals, WTROI to WTR23, are the bits ROI to R23 shown in FIG. 1 after the bit change processing, respectively.
represents bit information corresponding to . WTROI=R
DRO1・BSHT1・iVHTO+BSHTO+iV
HTI...'2'WTR02=RDR02・BSHT2・
iVHTO+BSHTO+iVHT2...'3}WT
R03=RDR03・BSHT3・iVHTO+BSH
TO+iVHT3...'41WTR12=RDR12
・BSHT2・iVHTI×BSHTI×iVHT2・
...{5}WTR13=RDR13・BSHT3・jV
HTI+BSHTI+iVHT3...'6}WTR2
3=RDR23・BSHT3・iVHT20BSHT2
10iVHT3...[7] For example, the fact that the {2'th expression holds true correctly means that when referring to Figure 2 0, W, W, skin, the bit ROI is logically determined when a buffer hit occurs at the #1 entry position. It is set to logic "0" when an invalid occurs at the #0 entry position, logic "1" when a buffer hit occurs at the #0 entry position, and logic "1" when an invalid occurs at the #1 entry position. This can be understood from the fact that it is ``1''.

FIG. 3 shows a replacement information update processing section according to the present invention.
2 shows the configuration of an embodiment, and shows an example of a logic circuit corresponding to the above-mentioned formula 2'. Since the reference numeral 1 in the figure represents an AND circuit, 2 represents an OR circuit, and 3 and 4 each represent a NOT circuit, it is clear that the bit output WROI corresponding to the above equation (2) is obtained. FIG. 4 shows the configuration of an embodiment of the replacement processing circuit section in the buffer memory device of the present invention.

Reference numeral 5 in the figure indicates a replace array (replace information holding section, which is provided in correspondence with, for example, an address array in a buffer memory device (not shown), 6 indicates a replace entry determination circuit section, and 7 indicates a replace array. Information update processing unit, 8 is a replace entry register in which entry position information to be replaced is set, 9 is a replace write data register which stores bit information WTROI to WTR23.
represents what is set. Correspondingly, when a buffer memory device is accessed, a replacement
Array 5 is read accessed.

The place information RDROI to RDR23 extracted from the array 5 is supplied to a circuit section 6 and a processing section 7. Then, the circuit section 6 determines the entry position with the highest replacement order and sets it in the register 8. On the other hand, the processing unit 7 is supplied with the buffer hit signal BSHO or Madarahi 3 and the invalid signal iVHTO or iVHT3, and the processing unit 7 is supplied with the buffer hit signal BSHO or Ikuhi 3 and the invalid signal iVHTO or iVHT3, and the processing unit 7 is supplied with the buffer hit signal BSHO or Ikuhi 3 and the invalid signal iVHTO or iVHT3, and the buffer hit signal BSHO or the invalid signal iVHTO or iVHT3 is supplied to
Based on the logic of the equation, the updated replacement information WTROI to WTR23 is set in the register 9. The information is 1
' Stored in place array 5. As explained above, according to the present invention, the replace entry determining circuit section 6 shown in FIG. 4 can employ a single logic of extracting the highest IJ place order.

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram for explaining replacement information, FIG. 2 is an explanatory diagram for explaining an update algorithm for replacement information according to the present invention, and FIG. FIG. 4 shows the configuration of an embodiment of the replacement processing circuit section in the buffer memory device of the present invention. In the figure, 5 represents a replacement information holding section, 6 a replacement entry determining circuit section, and 7 a replace information update processing section. Chi' Kousai Z Kyouya) Study size 4 legs

Claims (1)

[Claims] 1. In a data processing system in which the contents of the main memory are transferred in blocks to a buffer memory having multiple entry positions, and the processing is executed while accessing the buffer memory, A validity bit is created corresponding to the block unit transferred to each entry position on the buffer, and a replacement order among the block units transferred to each entry position is determined corresponding to the plurality of entry positions. A replace information holding unit that holds managed replacement information; a replace entry determination circuit unit that determines the position of an entry to be replaced next based on the contents of the replace information holding unit; and a replace information holding unit that updates the contents of the replace information holding unit. a replacement information update processing unit, and the replacement information update processing unit lowers the replacement ranking for the entry position when the content of the entry position is used and the content of the entry position is invalidated. A buffer memory device characterized in that the buffer memory device is configured to update the replacement information so as to increase the replacement ranking for the entry position when invalidation occurs, and to store the updated information in the replacement information storage unit.