JPS5856175B2 - Buffer memory control method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a buffer memory control system, and more particularly to a buffer memory control system that prevents block data fetched from main memory immediately before being replaced when data is replaced.

Conventional set-associative type buffer memory controls the buffer memory address by dividing it into a set address, 1, which corresponds to the lower part of the access address, and a block address, 1, which is unrelated to the access address. , the replacement unit controls this "block address".

When copying data from the main memory to the buffer memory (this is called a block fetch), one set address corresponding to the access address is determined.

One set address has a plurality of blocks, and one block among these is the part to be replaced by one block fetch.

The replace unit selects one of the plurality of blocks and specifies the location where the data is to be replaced.

Now, if a block fetch is performed and all the blocks at the corresponding set address already contain data and there is no empty block, the replacement part will retrieve all the data in the blocks from the past. Check how old the block was when it was accessed, and specify the block address of the block containing the oldest data as the block to be replaced.

It is well known that this is called the LRu method.

It is already known how to control the replacement switching control bits, ie, the bits written to the replacement memory array, each time the buffer memory is accessed.

When controlling by the complete LRu method, if there are n data blocks corresponding to one set address section, the replacement section will be n 1 for one set address.
) has n/2 bits of control bits in the replacement memory.

One bit indicates the ordering of two data blocks among the n blocks, and one set of total bits completely indicates the arrangement or ordering of the n data blocks.

If the buffer memory is now accessed, a set address is determined from the access address, and (nl)n/2 bits of the replacement memory corresponding to the set are selected as the object of control.

Upon notification of which data block has been accessed, (n-1) bits are selected and the access order of that data block is rewritten to be the latest one.

This is a replacement update.

By repeating this operation, the replacement memory always stores the order of newness, ie, oldest access, of n data blocks for all set addresses.

When fetching a block, the set address is determined from the access address, so this (n-
1) n/2 bits of information, ie information indicating the order of chronology of accesses of all n data blocks, are read.

The logic for extracting the block address of the oldest accessed data block from among these is the opposite logic to that for updating.

Corresponding to each block address, n-1 bits of (n-1)n/2 bits of replacement information are assigned, and the writing pattern at the time of update is completely reversed, that is, all bits are inverted. In the case of a pattern, that block is the oldest accessed data block.

Therefore, if we take the logic of whether or not the n1 bits assigned to each block correspond to this oldest pattern, one of the blocks will definitely correspond.

The above is the function of the conventional replacement control bit.

The replacement information read from the replacement memory has order information of all the ages of n data blocks corresponding to one set address.

In other words, it includes all n pieces of information indicating how old (i.e., new) each data block is.

Therefore, it is possible to create a circuit for extracting the second or nth oldest data block.

For example, if there are 4 blocks in one set, complete LRu
Since n=4, (n-4)n/26, therefore, the replacement information is 6 bits, and the bits allocated to each data block are n-1-3 bits.

Each of these 6 bits is Rot2. RO2, Ro3t R
12tR137R23 as shown in the table below, each bit per block pattern 0Ro1. R02, Ro3111000 1R01, R12, R13011100 2R02, R1□, horse, 001 1103
RO3, R73, R23000111 In this case, if the ROI J RO2J RO3j bits are all /, 0, the data block is the oldest accessed program.

The pattern of each bit in the second oldest case is a pattern in which any one bit is inverted from the pattern shown in the case where the bits assigned to each data block are the oldest.

For example, if ROI, RO2t R03 is 100,010°001, then α' is the data block and the second oldest block is accessed.

Similarly, logic for the second oldest of all blocks can be created.

In short, in the case of complete LRu, the n assigned to the pot block
- If the bit pattern of 1 bit differs from the oldest pattern by 1 bit, it becomes the second oldest, and if it differs by 2 bits, it becomes the third oldest, and if it differs by 2 bits, it becomes the third oldest. This indicates that the block is the nth oldest block, that is, the most recently accessed block.

As described above, it is possible to create logic to extract even old data blocks, and therefore also create the circuit.

Also, even if it is not a complete LRu, 1
Any method that has an algorithm that determines the order of all data blocks in a set can similarly extract data blocks other than the oldest, and is often simpler in terms of logic.

(The nth oldest here means what the replacement bit represents, and if it is not a complete LRu, it is not necessarily the true nth.) When fetching a block, in the conventional method, the fetched data is written to the buffer memory. In the process, the contents of the replacement memory array are also rewritten to register that the block address was most recently accessed.

This registration is called a replacement update, and this is the timing towards the end of block fetch access.

Nevertheless, replacement reading is performed immediately after block fetch access is started, and the position of the block whose data is to be replaced is memorized in advance.

Follow. If block fetch accesses are issued consecutively, the address of the replacement data block specified by the first access and the block address specified by the second access will be the same unless the contents of the replacement memory are updated. The same address is specified.

In other words, the exact same location will be the target of the exchange, and there is a strong possibility that the block data brought from the first main memory will be used again later (in any case, the second location). Immediately more than one color was painted on Nukudek,
Being insulted (yelling)

In other words, in the conventional control method, when block fetches with access addresses indicating the same set address are issued consecutively, the first block data is immediately erased from the buffer memory. .

Also, to avoid this, block fetches for the same set address should wait until the previous block fetch is completed, that is, until the contents of the replace memory are updated and the next block to be replaced can be correctly determined. There was also a method to do this, but in this case, the performance would inevitably drop due to the amount of time it would take to wait.

The purpose of the present invention is to replace not only the oldest data block in the case of consecutive block fetch accesses with the same set address, but also the address of the second or nth oldest data block in the case of the second access. By specifying, you can make the second and subsequent accesses wait until the first access is completed,
The purpose is to improve performance by solving the drawback that previously fetched block data is erased due to duplicate writing.

In other words, if the next block fetch is required for the same set address before the contents of the replace memory are updated as a result of a block fetch, the block fetch is currently in progress and as a result, the main memory data cannot be written. The purpose of this is to improve performance by not specifying the block position that has been missed as the write destination block for the next block fetch.

In order to achieve the above object, the present invention updates the contents of the replacement memory every time the buffer memory is accessed, records that the block containing the accessed data is the latest, and stores the required data. If it does not exist in the buffer memory, determine the block number to be evicted based on the read data of the replacement memory,
In a buffer memory control method for block transfer of new data from main memory to a block position of the block number, a first replay input determination circuit that determines the oldest data block number based on the read data of the replace memory; and a second replacement determination circuit that determines the newest data block number next to the oldest, and if there is no block transfer that is already in progress, the first replacement determination circuit determines the block number to be replaced. If there is a block transfer that has been determined and is already in progress, the second replacement determination circuit determines the block number to be replaced.

The present invention will be explained below with reference to Examples.

The figure shows a replacement control circuit according to an embodiment of the present invention.
In the figure, 1 is the replacement memory section, 2 is the first LRU circuit that determines the oldest data block, 3 is the second LRU circuit that determines the second oldest data block, and 4 is the nth oldest data block. nth LRU circuit, 5 is a comparison circuit, 6 is a selection circuit, 7 is a second register, 8 is a second register, 9 is an nth register, 10 is information specifying the buffer memory write block number of the first block fetch data Line 11 is an information line 12 specifying the buffer memory write block number of the second block fetch data.
is an information line that specifies the buffer memory write block number of the nth block fetch data.

The replacement information output from the replacement memory section 1 is the first LRU circuit 2, the second LRU circuit 3,...
is simultaneously input to the n-th LRU circuit 4, and the first LRU circuit 2
The oldest data block number is output from 2nd LR.
The U circuit 3 outputs the second oldest data block number, and the nth LRU circuit 4 outputs the nth oldest data block number in the same manner.

Comparison circuit 5 compares the set addresses of block fetches that occur continuously, and determines whether there are block fetches with the same set address or not, and if there are block fetches with the same set address, how many of the same set addresses there are. death,
It sends a selection signal to the selection circuit 6.

The selection circuit 6 receives the selection signal from the comparison circuit 5;
Any one of the first LRU circuit 2 to the n-th LRU circuit 4 and any one of the register 7 to the n-th register 9 are selected, and the output of the selected LRU circuit is sent to the selected register.

If there is no previously issued block fetch that has not been completed and this is the first block fetch, the position of the oldest data block obtained by the first LRU circuit 2 based on the replacement information output from the replacement memory unit 1. Information is set in the second register.

That is, the selection signal from the comparison circuit 5 causes the selection circuit 6 to
leads the output of the first LRU circuit 2 to the second register.

On the other hand, if there is a block fetch that has already been issued but has not yet been completed, and a second block fetch is issued in this state, the comparison circuit 5 compares the set addresses of the previous and subsequent block fetches.

If the set addresses of both do not match as a result of the comparison, the selection signal from the comparison circuit 5 causes the first LRU circuit 2 to
The output of is set to the second register 8.

Further, if the two set addresses match, the output of the second LRU circuit 3 is set to the second register 8 by the selection signal from the comparison circuit 5.

Similarly, if a block fetch on the nth day occurs while the previous (n-1) block fetches are not completed, the set address of the nth block fetch is different from any previous set address. If they do not match, the output of the first LRU circuit 2 is set to the nth register 9.

On the other hand, when the set addresses of the 1st to nth block fetches are all the same, the output of the nth LRU circuit 4 is
Set to register 9.

As a result, in the case of overlapping block transfers, the same block position in the buffer memory is not consecutively designated for storing data from the main memory.

As already explained, the present invention adds a circuit to the conventional circuit that determines the second or nth oldest data block based on brace information, thereby improving the area of successive block fetches of the same set address. Since the block fetch data is prevented from being designated as a buffer write block and loss of block fetch data is prevented, this has the excellent advantage of improving performance and simplifying control.

[Brief explanation of the drawing]

The figure shows a replacement control circuit according to an embodiment of the present invention. In the figure, 1 is a replacement memory section, 2 to 4 are LRU circuits,
5 is a comparison circuit, 6 is a selection circuit, 7 to 9 are registers, 10
-12 are information lines for designating the buffer memory write block number.

Claims (1)

[Claims] 1. Every time the buffer memory is accessed, the contents of the replacement memory are updated to record that the block containing the accessed data is the latest, and the required data does not exist in the buffer memory. In this case, in a buffer memory control method in which a block number to be evicted is determined based on the successive data of the replace memory, and new data is block transferred from the main memory to the block position of the block number, based on the read data of the replace memory. a first replacement determination circuit that determines the oldest data block number, and a second replacement determination circuit that determines the next newest data block number, and there is no block transfer that is already in progress. In this case, the first replacement determination circuit determines the block number to be replaced, and if there is a block transfer that is already in progress, the second replacement determination circuit determines the block number to be replaced.
A buffer memory control method characterized in that a block number to be replaced is determined by a replacement determination circuit. 2 Even if there is a block transfer that is already in progress, if the comparison result of a specific part of the addresses of the block transfer in progress and the subsequent block fetch request shows a mismatch, always follow the above first replacement determination circuit. 2. The buffer memory control method according to claim 1, wherein replacement control is performed.