JPH0340412B2 - - Google Patents

Description

[Detailed description of the invention]

[Industrial Application Field] The present invention relates to a second buffer memory (MBS) having a copy of a part of a main storage device, a copy of a part of the second buffer memory (MBS), or a second buffer memory (MBS) having a copy of a part of the main memory. In a computer system having a two-layer buffer memory system including a first buffer memory (LBS) having a copy of a part of the main memory that is not in the main memory (MBS),
This paper relates to a buffer memory (MBS) replacement method. In recent large-scale computer systems, a small capacity but high-speed buffer memory (BS) is installed between the central processing unit (CPU) and the main storage unit (MSU).
Generally, a method is adopted in which the average access time to the main storage unit (MSU) is shortened by providing a main storage unit (MSU). However, with recent remarkable advances in hardware technology, the arithmetic units of central processing units (CPUs) are becoming faster and faster, but main storage units (MSUs) are becoming larger in capacity. In order to be
The current situation is that the speed cannot be increased much. Therefore, the buffer memory (BS) mentioned above has been made faster and has a larger capacity to match the speed of the arithmetic unit, but compared to the increase in the capacity of the main storage unit (MSU), the difference is smaller. I am in a situation where I am not allowed to do so. As a means to solve the above problem, a medium-speed, large-capacity buffer memory (BS) is used as a second buffer memory (MBS). ) and a main storage unit (MSU), a so-called two-layer buffer memory system is known. Below, each
This BS will be referred to as the first BS. In such a buffer memory system,
The problem is the replacement in the second BS. In particular, block size of second BS > first BS
When the block size is , and the difference is an integer multiple, if the replacement blocks for the first BS and the second BS are determined independently, the second BS is transferred from the main storage unit (MSU). There is a problem that the data moved in to the first BS may be replaced at the second BS before it is used up (specifically, it is not transferred to the first BS). Therefore, the first BS replacement operation and the second
By creating a certain correlation between the BS replacement operation and the BS replacement operation, an effective replacement method can be expected. [Prior Art] First, the concept of a computer system including a general two-layer buffer memory (BS) will be explained with reference to FIG. In this figure, 1 is the arithmetic unit, 2 is the first BS
(LBS), 3 is the second BS (MBS), and 4 is the main storage unit (MSU). In such a computer system, the first
Both BS (LBS) 1 and second BS (MBS) 2,
When the data required by the arithmetic unit 1 does not exist, the data is stored in the first BS (LBS) from the main storage unit (MSU) 4.
1 and the second BS (MBS) 2 for the corresponding blocks, and the necessary data is transferred from the first BS (LBS) 2 to the arithmetic unit 1. . If data does not exist in the first BS (LBS) 2 and data exists in the second BS (MBS) 3, the data block is transferred from the second BS (MBS) 3 to the first BS (MBS) 3. The block is transferred to the first BS (LBS) 2, and necessary data is further transferred from the first BS (LBS) 2 to the arithmetic unit 1. FIG. 4 shows an example of the configuration of a three-layer memory system consisting of a two-layer buffer memory and a main storage unit (MSU). In this configuration example, the block size of the first BS (LBS) 2 is 32 bytes, and the block size of the second BS (MBS) 3 is 32 bytes.
The block size of is a 128-byte block, which is 4 times the block size of the first BS (LBS) 2, and the block size of the first BS (LBS) 2, the second BS (MBS)
In both cases, the degree of association (number of ways) is way 0 to way 3.
It consists of four levels. If the first BS (LBS) 2, the second BS (MBS)
In both cases, when the required data does not exist, the 32-byte data requested by the first BS (LBS) 2 is block transferred from the main storage unit (MSU) 4, and then transferred to the first BS (LBS). LBS) 2, second BS
(MBS) Registered in both 3. At this time, the ways to be registered are the first BS (LBS) 2, the second BS
(MBS) Sometimes all three are the same way,
It may be a different way. Next, the remaining 96 bytes of the 128-byte block of the second BS (MBS) 3 are divided into 32 bytes x 3 blocks, transferred from the main storage unit (MSU) 4, and transferred to the second BS (MBS) 3. (MBS) Registered in 3. Also, there is no data in the first BS (LBS) 2, and the second
If data exists in BS (MBS) 3,
The 32-byte data requested by the first BS (LBS) 2 is read from the second BS (MBS) 3,
It is forwarded to the first BS (LBS) 2. In such a conventional two-layer buffer memory system, the above data transfer (move-in)
When the first BS (LBS) 2 and the second BS (LBS) 2
Each of the BS (LBS) 3 was doing it independently. [Problem to be solved by the invention] Therefore, in the conventional system, for example, the first
Blocks replaced from BS (LBS) 2,
Even if the second BS (MBS) 3 contains a block, the block may not be replaced by the second BS (MBS) 3, or conversely, the second BS (MBS) 3 may not be replaced from the main storage unit (MSU) 4. ) 3 to the first BS (LBS) 2.
2nd BS (MBS) 3 before it is used up.
In many cases, the second BS (MBS) 3 is used less efficiently. In view of the above-mentioned drawbacks of the conventional art, the present invention focuses on the locality of address distribution during program execution, and takes advantage of the feature that accesses to a storage device occur sequentially to some extent in time to a certain continuous area. Taking into account, the usage efficiency of the second BS (MBS) 3 can be improved by creating a certain correlation between the replacement operation in the first BS (LBS) 2 and the replacement operation in the second BS (MBS) 3. The purpose of the present invention is to provide a replacement method that improves the performance. [Means for solving the problem] This purpose is to create a system in which the contents of each sub-block obtained by dividing a block of the buffer memory into the block size of the first buffer memory (LBS) are stored in the second buffer memory (MBS). The n-bit copy bits indicating that the data has been transferred to the buffer memory (LBS) are transferred to the second buffer memory (MBS).
When the second buffer memory (MBS) needs to be replaced, among the m blocks (m is the number of associative levels of the second buffer memory) that are candidates for replacement, Referring to the copy bits above, if there is anything that indicates that the contents of all subblocks of the block have been transferred to the first buffer memory (LBS), that block will be prioritized for replacement. control. When replacing a certain block from the first buffer memory (LBS), means is provided for transmitting address information of the block to be replaced to the second buffer memory (MBS),
There is no data in the second buffer memory (MBS), so the second buffer memory (MBS)
The second buffer memory (MBS) control circuit is provided with a comparator for detecting whether any one of the blocks to be replaced includes the transmitted address. When determining a replacement block for the first buffer memory (MBS), if the comparator detects a block containing the address transmitted from the first buffer memory (MBS), the block is replaced and the first buffer memory (MBS) is replaced. If a block containing the address that has been replaced is not detected, the block to be replaced is determined using the LRU method. This is achieved by the replacement method in the buffer memory of the present invention. [Operation] That is, according to the present invention, the storage capacity of the first BS (LBS)<the storage capacity of the second BS (MBS), and the storage capacity of the second BS (MBS)
The block size of BS (MBS) is the first BS
In a computer system equipped with a two-layer buffer memory system whose block size is an integral multiple of the block size of (LBS), (1) data copied from the second BS (MBS) to the first BS (LBS) A copy memory for storing sub-blocks is provided, and when replacement is required in a second BS (MBS), a block in which all sub-blocks have been copied to the first BS (LBS) is preferentially replaced. (2) Memorize the replacement address (subblock address) in the first BS (LBS),
When replacement is required in the second BS (MBS), if there is a block that includes the above sub-block, that block will be replaced preferentially. (3) If conditions (1) and (2) are not met, publicly known
Replace the block selected by LRU method. Therefore, the second BS (MBS)
This has the effect of improving the usage efficiency of the computer and improving the performance of the entire computer system. [Examples] Examples of the present invention will be described in detail below with reference to the drawings.
FIG. 1 is a block diagram showing one embodiment of the invention, and FIG. 2 is a block diagram showing another embodiment of the invention. Note that the same reference numerals indicate the same objects throughout the figures. In FIG. 1, a is, for example, the second BS
(MBS) 3 shows an example of the configuration of the copy bit provided in the tag part, and b is the second copy bit.
This shows an example of the configuration of BS (MBS) 3. First, referring to a in the figure, the operation for copy bits, which is the main focus of the present invention, will be explained. In this figure a, 320 is a copy bit provided in each entry of the tag part 32 in the second BS (MBS) 3, and the number of subblocks in the block of the second BS (MBS) 3, that is, A 4-bit address is provided for each entry. 330 indicates one block of 128 bytes of the second BS (MBS) 3, and one block of 128 bytes of the first BS (LBS) 2.
20, each time one subblock (32 bytes) is transferred, one bit of the corresponding copy bit 320 is set to '1', and in this figure, three subblocks are BS
(LBS) 2. Next, the replace operation according to the present invention will be explained using b. First, the address of the requested data is set in the address register (hereinafter referred to as AR) 31, and at its lower address, the tag part (TAG) 32,
The data section 33 and LRU memory 35 are referenced. Next, the high-order address in the tag section (TAG) 32 and the high-order address of the AR31 are connected to a comparator (C).
Compared in 34, NOR circuit (NOR) 38
Through this process, the required data is transferred to the second BS (MBS)
Not present in 3 (i.e. line missing)
is detected, the block is moved in from the main storage unit (MSU) (not shown).
The address of AR31 goes through MSAR31',
The move-in data is sent to the main storage unit (MSU), and after a certain period of time, the move-in data is sent to the second BS (MBS) 3.
will be forwarded to. It is necessary to determine the replacement block as the write destination for the move-in data, but usually,
The LRU memory 35 is selected from a total of four blocks determined for each way by the lower address.
At , the oldest block is selected as the replacement block. In the present invention, in addition to the information from the LRU memory 35, information from an AND circuit (AND) 36 that outputs an AND signal of the copy bits 320 stored in the tag section (TAG) 32 is used to
The feature lies in determining the replacement block. In other words, the above AND circuit (AND) for each way
Among the 36 outputs ACPYO~3 (here, 0~3 correspond to ways 0~3), the block (way) '1' has already had its entire contents transferred to the first BS (LBS).
Since the way has been transferred to No. 2, this way is given priority as the block to be replaced. In other words, for each way that is a replacement candidate,
Of the total 4 blocks, the corresponding ACPYO~3
If there is only one '1' in the block,
The information is to be replaced regardless of the information from the LRU memory 35. If ACPYO~3 corresponding to each way is '1'
If there are multiple blocks (ways), select one of them based on the information from the LRU memory 35,
Target the oldest block for replacement. Therefore, if there is no block that is ``1'' in the corresponding ACPYO~3, the oldest block is targeted for replacement based on the information from the LRU memory 35 as before. The table below shows that when the information in the LRU memory 35 indicates that the information is used in the order of Way 0 Way 1 Way 2 Way 3, the replacement decision circuit 37 uses the value of ACPYO~3 above. This shows the replacement block to be selected.

【table】

〔Effect of the invention〕

As explained above in detail, the replacement method in the buffer memory of the present invention is based on the first BS.
(LBS) storage capacity < Second BS (MBS) storage capacity, and the block size of the second BS (MBS) is
In a computer system equipped with a two-layer buffer memory system whose block size is an integral multiple of the block size of the first BS (LBS), (1) from the second BS (MBS) to the first BS (LBS); A copy memory is provided to record the sub-blocks copied to the first BS (MBS), and when replacement is required in the second BS (MBS), the block whose all sub-blocks have been copied to the first BS (LBS) is given priority. Replace. (2) Memorize the replacement address (subblock address) in the first BS (LBS),
When replacement is required in the second BS (MBS), if there is a block that includes the above sub-block, that block will be replaced preferentially. (3) If conditions (1) and (2) are not met, publicly known
Replace the block selected by LRU method. Therefore, the second BS (MBS)
This has the effect of improving the usage efficiency of the computer and improving the performance of the entire computer system.

[Brief explanation of drawings]

Fig. 1 is a block diagram showing one embodiment of the present invention, Fig. 2 is a block diagram showing another embodiment of the invention, and Fig. 3 is an information processing system equipped with a two-layer buffer memory. FIG. 4 is a diagram showing an example of the configuration of the system. FIG. 4 is a diagram showing an example of the configuration of a three-layer memory system. In the drawing, 1 is an arithmetic unit, 2 is a first BS
(LBS), 3 is the second BS (MBS), 4 is the main storage unit (MSU), 21 is the address register (LBAR), 2
2 is a tag section (TAG), 23 is a data section, 24 is a comparator (C, LC1 to LC4), 25 is an LRU memory, 2
7' is LRU determination circuit 1, 28' is HIT/NON-
HIT detection circuit-1, 29 is PBAR, 31 is address register (AR, MBAR), 32 is tag section (TAG), 33 is data section, 34 is comparator (C,
MC1 to MC4), 34' is a comparator (PBC1 to PBC4),
35 is an LRU memory, 37 is a replacement decision circuit,
37' is LRU determination circuit 2, 38' is HIT/NON-
HIT detection circuit-2 is shown.

Claims (1)

[Claims] 1. In a set associative type buffer memory, if desired data is present on the first buffer memory (LBS), the data is read from the first buffer memory (LBS) and the data exists. If not, refer to the second buffer memory (MBS), and if there is data in the second buffer memory (MBS), transfer the data from the second buffer memory (MBS) to the first buffer memory (LBS). When a block is transferred and there is no data in the second buffer memory (MBS), the data is transferred from the main memory to the first buffer memory (LBS).
The data is controlled to be transferred in blocks to both of the second buffer memories (MBS), and the block size of the second buffer memory (MBS) is n times the block size of the first buffer memory (LBS). In a computer system equipped with a two-layer buffer memory system that uses the LRU method to replace the oldest block, the data replacement algorithm for both buffer memories (BS) is based on the second buffer memory system. buffer memory (MBS),
A copy bit of n bits indicating that the contents of each sub-block obtained by dividing the block of the buffer memory into the block size of the first buffer memory (LBS) is transferred to the first buffer memory (LBS) is transferred to the second buffer memory (MBS). ), and when the need for replacement arises in the second buffer memory (MBS), m blocks (m is the number of associative levels of the second buffer memory (MBS)) are provided as candidates for the replacement. Among them, if there is one that indicates that the contents of all subblocks of the block have been transferred to the first buffer memory (LBS) by referring to the copy bits, that block is preferentially replaced. A replacement method in a buffer memory characterized by controlling the target. 2 In a set associative type buffer memory, if the desired data exists on the first buffer memory (LBS), the data is read from the first buffer memory (LBS), and if the data does not exist, the data is read from the second buffer memory (LBS). If there is data in the second buffer memory (MBS), block transfer the data from the second buffer memory (MBS) to the first buffer memory (LBS), and then transfer the data to the second buffer memory (MBS). If there is no data in the first buffer memory (MBS), the data is transferred from the main memory to the first buffer memory (LBS).
The data is controlled to be transferred in blocks to both of the second buffer memories (MBS), and the block size of the second buffer memory (MBS) is n times the block size of the first buffer memory (LBS). n ≥ 2), and the data replacement algorithm for both buffer memories (BS) is the first one described above in a computer system equipped with a two-layer buffer memory system that uses the LRU method to replace the oldest block. When replacing a certain block from the second buffer memory (LBS), a means is provided for transmitting the address information of the block to be replaced to the second buffer memory (MBS),
Since there is no data in the second buffer memory (MBS), check whether any one of the blocks to be replaced in the second buffer memory (MBS) includes the transmitted address. A detecting comparator is provided in the second buffer memory (MBS) control circuit, and when determining a replacement block for the second buffer memory (MBS), the address transmitted from the first buffer memory (LBS) is determined. When a block containing the transmitted address is detected by the comparator, the block is replaced, and when a block containing the transmitted address is not detected, the comparator replaces the block.
A replacement method in a buffer memory characterized by controlling to determine a block to be replaced by an LRU method.