JPS5816262B2 - Control method for multi-tier storage device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a control method for a multi-tiered storage device that employs a swapping method as a store processing method.

An information processing device cannot achieve sufficient performance if data requested by a central processing unit is transferred from a slow main storage device each time.

Therefore, by placing a low-capacity but high-speed buffer storage device that can synchronize with the speed of the central processing unit between the central processing unit and the main memory device, it is usually possible to transfer data from the buffer storage device at high speed. .

This method is called a buffer storage method.

The low capacity of the buffer storage device is based on the ubiquitous nature of the program.Due to the nature of this program, some data in the main storage device is stored in the buffer storage device (copy) to meet the demands of the central processing unit. Probability that the data to be stored does not exist in the buffer storage device (NIBR: not 1nBu
ffer Ratio) can be set within 10 ratios.

The data correspondence between the main memory and the buffer memory is dynamically exchanged so that the data most needed by the central processing unit at that time is present in the buffer memory.

The buffer storage system, which is currently widely used, is a two-level hierarchical storage system and is a type of multiple storage system.

As a multi-layered storage system, an n-level hierarchical storage device can generally be considered.

In the buffer storage system, the number of buffer storage devices is n-1, and the number of main storage devices is n=2.

FIG. 1 shows part of an n-level hierarchical storage device, Mi+1
A storage device of y Mi , 1vfi-1 is illustrated.

i is n-1≧i≧1, and Mo is considered a central processing unit.

The data correspondence between each storage device is assumed to be such that the data amount between Mi and Mi-1 is called a block, and the data amount between Mi and Mi+1 is called a line.

Here, the line generally consists of several blocks.

Data transfer between storage devices (consisting of four blocks in the figure) is performed according to data requests.

For example, when Mi-1 requests block a3 from Mi, M
i checks whether line A containing the requested block exists in Mi, and if it has not been imported yet, requests line A from Mi+1, and after transferring line A from Mi+1 to Mi (line transfer), from Mi. The block a3 is transferred (plot transfer) to Mi-1, and the data transfer process ends.

For store processing from Mi-1, there is a so-called store-through method in which data is updated up to the storage device of Mi+1 every time a store request occurs. In order to
It can be said that the hierarchical storage method does not fully demonstrate its advantages for store processing.

In contrast, the so-called swapping method aims to improve the speed of store processing by completing the processing by updating data in Mi when a store entry exists in Mi.

Generally, in the swapping method, the store entry is
If it does not exist, line transfer is performed from Mi+1, and data is updated on that 1Mi.

In the swapping method, the data of Mi +1 and Mi do not necessarily match.

In order to display this mismatched line, generally a 1-bit identification latch (change bit) is provided for each line of Mi, and the change bit is set to 11'' each time a store operation is performed on the line.

When a line transfer occurs due to a store or read request from Ml-1, a replacement line is determined by a predetermined algorithm, but if valid data is stored in the line and the change bit is '1'', the line is Prior to transfer, update the unupdated line in Mi by swapping out the line to Mi +1.9 If the request from M1-1 is a read request, Mi-1 issues a read request to Mi, and then・Mi until data arrives
-1 can hardly do any other processing, so
Mi needs to send read data to <Mi-1 as soon as possible.

By the way, if the read request is a line transfer request that involves a swap out, conventionally, after the swap out process,
Line transfer was performed and read data was sent to Mi-1.

For this reason, the swap-out processing time resulted in a large overhead compared to Mi-1.

Therefore, an object of the present invention is to prevent swap out from becoming an overhead for Ml-1.

2 In order to achieve the above object, the present invention uses swap/
A storage device is provided to store out data.

When a line transfer request that involves a swap out occurs from Mi-1, the swap out data is stored in the storage device at the same time as the line transfer request is issued to Mi+1, and after the line transfer operation is completed, the swap out data is stored in the storage device. The swap out data stored in the device is swapped out to 7J i +1.

FIG. 2 is a detailed block diagram of FIG. 1 and shows an example of memory mapping.

The storage device Mi+1 is divided into lines of CpXRx entries, the storage device Mi is divided into lines of CpXRy entries, column C2 of Mi+1, line A of row R1 is column C2 of Mi, and row R2 is divided into columns so that they are in a pair. However, which row is supported is determined depending on the usage status of Mi's rows.

Generally x > y. On the other hand, the storage device M i-1 is
CqXRz is divided into blocks of entries, e.g.
Block a3 in column C2 of i, line A of row R2
corresponds to column C1 and row R1 of Mi-1.

In general, p≧q, and multiple columns of Mi correspond to one column of Mi-1.

The rows used differ depending on the usage status of the block.

x > y > z, and in MO, generally q=i,
It is imaged as 2=1.

FIG. 3 is a logical block diagram of the storage device Mi control section showing a detailed example of the actual UI of the present invention.

1 is the memory request address register to be compared with the memory request address from the storage device Mi-1, and the address is the tag.
It consists of an address section T, a line address section, and a block address section B.

Line address decoders 2 and 6 output select signals corresponding to the columns of address table 3 and change bit table 7, respectively.

3 is an address tape where the upper bits of the memory request address, that is, the tag address are recorded, and Mi+
1 and Mi's chief response, and in this example, it facilitates the following explanation. 5 second 4 columns x 20 8
Zashi from entry: 1.・The address comparison circuit corresponding to the row of the address table compares the tag address extracted from the address table with the tag address of the memory request address.

Reference numeral 5 denotes a control circuit that outputs various control signals according to the result of the address comparison in step 4, and outputs control signals 81, 82, etc.

Control signals 81 and 82 correspond to the rows of the address table and indicate a match result of address comparison or replacement.
Connection of row determination circuit (not shown) M7. (, (from 81.
Either one of 82 is set to "1".

7 is a change bit table which is divided in the same way as the address table 3 and consists of 8 entries in this example.

8 is a change bit storage register in which the contents of the selected 1-en l-IJ of the change bit table 7 are stored.

9 is a control signal S1. The encoder inputs S2 and its output is stored in the upper part of the 10 pair Mi address registers to form the row address.

The 10 paired Mi address registers are row address parts,
Consists of a line address section and a block address section.
The refer address of the storage device Mi is stored.

Reference numeral 11 denotes a pair Mi+1 address register, which consists of a tag address field and a line address field, and stores the refer address of the storage device Mi+1.

12 is a block address plus one circuit, and 16 swap out data during line transfer and swap out data.
Counts up the block address when storing the out data storage circuit.

13 to 16 are characteristic logic circuits for implementing the present invention, and the block address register 13 stores a block address for sending the contents of the 16 swap-out data storage circuits to Mi+1. .

14 is a plus one circuit for the block address of 13.

A block address decoder 15 outputs a select signal corresponding to a block of the swap-out data storage circuit.

16 is the swap out data read from the storage device Mi.
This is a circuit that stores data.

The operation when a memory request (read or store) is generated from the storage device Mi-1 will be described below.

When a memory request is generated from the storage device Mi-1, the memory request address that is valid on the address transfer path 100 is stored in the request address register 1.

If the memory request from Mi-1 is for a store, at this point a response signal for accepting store data is sent to Mi-1, and the store processing of Mi-1 is ended.

The line address portion of request address register 1 is routed through path 102 to column address decoder 2 to refer to one column of address array 3.

If column C2 is selected now, tag address A stored in C2XR1 is input to the address comparison circuit 4 through path 104, and tag address B stored in C2XR2 is input through path 105.

The tag address of the refer request address register 1 is inputted to the other input of the address comparison circuit 4 through a path 101.

The result of address comparison is input to the control circuit of No. 5 through paths 106 and 107, and the control circuit of No. 5 closes the signal line S1 to 11" when there is a match in row 1, and closes the signal line S2 to 11" when there is a match on row 2. shall be.

9 The following describes the control when no match is detected by the address comparison circuit.

Note that the operation when a match is detected by the address comparison circuit is the same as the conventional one, and therefore a description thereof will be omitted.

The control circuit 5 activates a replacement row determining circuit (not shown) when the result of the address comparison 4 is a non-match, that is, the memory request entry from Mi-1 does not exist in Mi, and performs the replacement. After determining the desired row number, the signal line 81
．． One of 82 is applied to 11".

Now, when row 1 is selected and signal line S1 is added to 11'', change bit a from the change bit table 7 is stored in register 8 through the 108° path 110.

If the change bit stored in register 8 is 11" or "
The following control differs depending on whether the value is 0", but the control in the case of 0" is the same as the conventional one, so the explanation will be omitted.

When the change bit stored in register 8 is 11", the tag address part of the request address register of 1,
The line address section and the block address section are respectively passed through 101. Through path 102 and path 103, it is stored in the pair Mi+1 address register, and the address is made valid on path 111 and a line transfer request is sent to storage device Mi+1.

In the line transfer, in this example, four blocks are transferred in order from the request block.

At the same time, the row address is stored in the 10 pair Mi address registers through the path 112, the line address is stored through the path 102, and the block address part is stored as 1.
1" is stored.

Pass 1 after being stored in the pair Mi address register of 10
13, and issues a read request to the storage device Mi.

The read data depth of Mi is one block in this example.

The block address portion of the 10 pair M1 addresses is sent over path 114 to the 15 block address decoders to thread the 16 swap out data storage circuit blocks (81-B4).

The data read from the storage device Mi is stored in the selected block through the path 115.

The block address portion of the 10 paired Mi address registers is 12 +1 circuits, and 1 line of data (in this example, counted up and swapped out every time 1 block is stored in 16 memory circuits through path 116). One line consists of four blocks.

) are stored in all 16 memory circuits.

Generally, in the hierarchical storage system, the access time of Mi is selected to be sufficiently smaller than the access time of Mi+1.

Therefore, a line transfer request is sent to Mi+1. Mi+1
The process of storing the swap-out data in the 16 swap-out data storage circuits is completed until the data is transferred from 1. When the storage of the swap-out data is completed, the 10 paired Mi address registers are The block address portion of the memory request address register of 1 is set through path 103 in the block address portion of the memory request address register.

Other bits are retained. When data is transferred from Mi+1 in response to a line transfer request sent to Mi+1, if the line transfer was caused by a store request from Mi-1, the first block transferred is from Mi+1.
After being merged with the store data from path 11 (not shown), the contents of the pair Mi address register of 10
3 and requests writing to the storage device Mi.

For the remaining blocks, the transfer data from the storage device Mi+1 is written as is into the storage device Mi (not shown).

At this time, the block of 10 Mi address registers
The address part is 12+1 times.

The count is increased each time one block is transferred through the path 116.

Further, if the line transfer is caused by a read request from Mi-1, all transferred blocks are written to the storage device Mi as they are.

Then, the corresponding entry (a in this example) in change bit table 6 is set to 'X□''.

Thereafter, the read request data from Mi-1 is transferred to the storage device M.
Read from i and transfer to Mi-1 [7 (not shown) Mi
The read process for l ends.

As for Mi, there remains a process of swapping out the data stored in the 16 swap-out data storage circuits to the storage device M i +1.

Next, this process will be explained.

After the above line transfer is completed, the block address register of 13 is set to 11".

This includes 15 block addresses through path 116.
16 swap out data records sent to registers;
A block of storage circuitry is selected and the data in that block is read out onto path 117.

At the same time, the tag address from the corresponding entry in address table 3 (?:j:C2XRl in this example) is stored in the tag address field of pair Mi+1 address register 11 through paths 104 and 113, and the block Thirteen swap out block address registers are stored in the address portion through path 116.

The line address portion is retained.

When the swap out data is read onto path 11, the address stored in the pair Mi+1 address register of 11 is made valid on 7Q111, and a store request is sent to storage device Mi+1 using the data on path 117 as store data. do.

13 block address registers pass 116.1
Each time 17 blocks of data are stored through the 4 +1 circuit and path 118, a count is increased 97, and the above operation is repeated until all swap-out data is stored in the storage device Mi+1.

Memory request from memory value ff1M i-1 is 1j-i-
', and if this request causes a line transfer accompanied by a swap out operation, the present invention realizes that after the line transfer, the memory device Mi+1 is swapped out.

This reduces the time from when Mi-1 issues a memory request (read) until the read data reaches Mi-1 by approximately 1/2 compared to the conventional method of swapping out prior to line transfer. This has the effect of being able to shorten the time to 2.

Since Mi-1 is located closer to the central processing unit, this effect has a large impact on the processing speed of the central processing unit.

[Brief explanation of drawings]

FIG. 1 is a diagram for explaining an n-level hierarchical storage method, FIG. 2 is a detailed block diagram of FIG. 1, and FIG. 3 shows an embodiment of the present invention. 1: Request address register, 2: Line address register
Decoder, 3; Address table, 4; Address comparison circuit, 5; Control circuit, 6; Line address decoder, 7; Change bit table, 8; Change bit register, 9; Encoder, 10; Mi address register, 11; versus Mi+1 address register, 1
2; +1 circuit, 13; block address register,
14; +1 circuit; 15; block address decoder; 16; swap-out data storage circuit.

Claims (1)

[Claims] 1. In a storage device with a multi-layered configuration in which a lower storage device stores part of the data in an upper storage device as a copy,
A swap-out data storage device is provided to store swap-out data, and when a memory request that involves a swap out occurs for one lower storage device, a transfer request is issued to the upper storage device and The swap out data from the lower storage device is stored in the swap out data storage device, and after the transfer operation from the upper storage device to the lower storage device in response to the transfer request is completed, the swap out data storage is performed. Swap out a device
A control method characterized by storing data in an upper storage device.