JPH05314010A - System for selecting substitution object data - Google Patents

Abstract

(57) [Abstract] [Purpose] LRU (Least Recent U)
sed) The LRU approximation method is realized at high speed by hierarchizing the management table in a plurality of stages, and the exclusive right management is performed for each LRU table, whereby the processes for a plurality of data access requests are simultaneously performed. The LRU table is hierarchized in a plurality of stages, and the LRU approximation method is executed in each layer to determine data for replacement processing with a low-speed storage device, and each LRU table.
A lock flag is provided for each RU table, and when the access to each LRU table is completed, the exclusive right of the LRU table is abandoned (that is, the lock of the LRU table is released).

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data replacement system between a high speed storage device and a low speed storage device in a parallel computer system.

[0002]

2. Description of the Related Art In an information processing apparatus such as a computer system, a part of data on a low-speed storage device is copied to a high-speed storage device so that the data can be referred to the high-speed storage device. There is a method to increase the speed. The high speed memory device and the low speed memory device include a secondary memory and a main memory, a main memory and a cache device, and the like.

To access the high-speed storage device, the high-speed storage device is searched in response to an access request for certain data, and if it exists, the data is accessed. If it does not exist, the certain data in the high-speed storage device is accessed. The data is written in the low-speed storage device, and the data requested to be accessed from the low-speed storage device at that position is read into the high-speed storage device. In this replacement between the high-speed storage device and the low-speed storage device, the method of writing out the data in the high-speed storage device to the low-speed storage device has a conventional method of replacing the most recently referenced data with LRU (Least Recently Used). There is a method.

The LRU system is difficult to realize accurately,
The approximation method is often used instead. Conventionally, as this approximation method, for example, Mamoru Maekawa, Iwanami Course Software Science 6 Operating System, 26 published by Iwanami Shoten
Some were shown on pages 1 to 264.

FIG. 8 is a block diagram showing a conventional LRU approximation method, where 1 is a request source program for reading data and 4 is a request source program.
Is a high speed storage device, 5 is a low speed storage device, and 13 is an LRU table. It should be noted that the LRU table 13 stores a data identifier portion 22 that stores a data identifier used when searching for data in order to realize the LRU approximation method, and 1-bit information indicating whether the data is referred to from the previous replacement process. The reference bit unit 19 for storing and the counter unit 20 for storing the number of times the reference bit unit 19 is 0 at the time of replacement processing. Further, the reference bit unit 19 and the counter unit 20
The initial state of is all 0.

In the system having such a configuration, the LRU approximation method is performed based on the flowchart shown in FIG. First, when a request to read the required data is issued to the request source program 1, the high-speed storage device 4 is searched based on the data identifier (hereinafter referred to as a reference identifier) for identifying the data to be read in step 1, and the corresponding data is found. If it exists in the high-speed storage device 4, the data is taken out and the process proceeds to step 2 to set the reference bit portion corresponding to the reference data in the LRU table 13. If it does not exist, the process proceeds to step 3 to perform the replacement process. In step 2,
Search the LRU table 13 using the reference identifier as a key,
The reference bit part 19 of the corresponding entry is set to 1. This completes the setting of the reference bits corresponding to the search data. In step 3, for all the entries in the LRU table 13, if the reference bit part 19 is 0, the counter part 20 is incremented by 1. If the reference bit part 19 is 1, the reference bit part 19 is set to 0 and the counter part is Set 20 to 0. Next, the LRU table 13 is searched for the entry with the maximum value of the counter section 20, the value of the data identifier section 22 of the searched entry is taken out, and it is set as the data identifier to be replaced, and this entry is deleted. Go to step 4. In step 4, the replacement data is stored in the high-speed storage device 4 based on the replacement target data identifier obtained in step 3.
It is taken out from and written back to the low speed storage device 5. Next, the search data is read from the low speed storage device 5 based on the reference identifier, the data is written in the high speed storage device 4, and the process proceeds to step 5 to register the reference data. In step 5, a new entry in which the value of the data identifier portion 22 is the search identifier, the value of the reference bit portion 19 is 0, and the value of the counter portion 20 is 0 is registered in the LRU table 13.

As described above, in the conventional method, the reference bit unit 19 indicates whether or not the data has been referenced since the previous replacement, and the counter unit 20 counts the number of unreferenced data every replacement. Thus, the LRU method is approximated by determining that the data having the largest value in the counter unit 20 has not been referred to for the longest time.

[0008]

DISCLOSURE OF THE INVENTION Problems to be Solved by the Invention
In the RU approximation method, the reference bit part is manipulated for all entries in the LRU table at the time of replacement, and the maximum entry of the counter part is searched. However, as the size of the high speed storage device increases, the size of the LRU table also increases. Since the size becomes large and the operation for all entries of the LRU table takes a very long time, there is a problem that the replacement process cannot be performed at high speed. Also, in a parallel computer,
There may be multiple request source programs and multiple data access requests may be issued at the same time. In the conventional method,
There is also a problem in that the parallelism is reduced because the LRU table is occupied for a long time for one request.

In the invention of Japanese Patent Laid-Open No. 61-156446, this problem is solved by dividing the management table for the replacement process into a plurality of parts. However, in this method, at most, the square root of the size of the storage device is multiplied. You can only speed things up.

[0010]

In the replacement target data selection method suitable for a parallel computer according to the present invention, an LRU is selected.
The table is hierarchized into a plurality of stages, and means for determining the data to be replaced with the low-speed storage device by executing the LRU approximation method in each layer and a lock flag for each LRU table are provided to each LRU table. When the access to the LRU table is completed, the exclusive right of the LRU table is relinquished (that is, the lock of the LRU table is released).

[0011]

In the present invention, the LRU table is hierarchized in a plurality of stages, so that the size of each LRU table is very small, which is a fraction of the number of hierarchies, and the LRU approximation method can be realized at high speed. A lock flag is provided for each LR, and when the access to each LRU table ends, the LR
By unlocking the U table, another request source program can access the LRU table, and the replacement processing of a plurality of request source programs can be executed in parallel.

[0012]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 is a block diagram showing an embodiment of the present invention. 1 to 3 are request source programs for reading data operating in parallel, 4 is a high speed storage device, 5 is a low speed storage device, and 6 to 6.
Reference numeral 12 is an LRU set table, and 13 to 16 are LRU tables. The LRU set table stores information for realizing the LRU approximation method and a lower LRU set table or LRU table. Also,
The LRU table stores information and data identifiers for realizing the LRU approximation method.

In this embodiment, the high speed storage device 4 and the low speed storage device 5 store the data together with the data identifier assigned in a one-to-one correspondence with the data, and based on the 32-bit data identifier. Moreover, it is possible to retrieve data in a time that does not depend on the size of the storage device. The size of the high-speed storage device 4 is 1 megaword (that is, 2 to the 20th power word), and the number of hierarchical layers of the LRU table is four. Therefore, the LRU set table consists of 32 entries.

FIG. 2 is a block diagram showing one LRU set table, where 17 is a lock flag, 18 is a key section,
Reference numeral 19 is a reference bit portion, 20 is a counter portion, 21 is a lower table portion, and 17 is 1 in the LRU set table.
18 to 21 exist for each entry (that is, 32 entries). The lock flag 17 is set to L by a program.
It stores 1-bit information indicating whether or not the RU set table is used. If the value is 0, it is an unused state (that is, unlocked state), and if it is 1, it is a used state (that is, locked state). State). The key part 18 is from 0 to 31
Are stored, and the reference bit part 19 indicates whether the entry has been referred to since the previous replacement process.
Bit information is stored. If the value is 0, it is not referred to, and if the value is 1, it indicates that it is referred to. The counter unit 20 stores the number of times the reference bit unit 19 is 0 in the replacement process, and the lower table unit stores the LRU set table or LRU table one level lower. The LRU based on the value of the key part 18
The set table can be searched in a fixed time. Further, it is assumed that the lock flag 17, the reference bit unit 19, and the counter unit 20 are all initialized to the value 0.

FIG. 3 is a block diagram showing one LRU table. Reference numerals 17, 19 and 20 are the same as the LRU set table shown in FIG. 2, and 22 is a data identifier section, which is a data identifier. Is stored.

In the system having such a configuration, the LRU approximation method is performed based on the flow charts shown in FIGS. First, when a request for reading necessary data is issued to the request source program 1, the high-speed storage device 4 is searched based on the data identifier (that is, the reference identifier) for specifying the data to be read in step 1, and the corresponding data is found. If it exists in the high-speed storage device 4, the data is taken out and the LRU set table 6 of the first layer is targeted, and the process proceeds to step 2 to set the reference bit part, and if it does not exist, the LRU set table of the first layer. In step 6, the replacement process is performed for step 6.

In step 2, if the lock flag 17 of the target table is 0 (that is, it is not locked), the process proceeds to step 2a, and if the lock flag 17 is 1 (that is, it is locked), it is locked. Wait until the flag 17 becomes 0 and proceed to step 2a. In step 2a, the lock flag 17 is set to 1, the 5-bit information from the 1st bit to the 5th bit of the reference identifier is used as a key to search the target table (that is, the LRU set table or the LRU table), and the corresponding entry is searched. The reference bit part 19 of the above is set to 1, and if the target table is the LRU set table, the process proceeds to step 2b, and the target table is the LRU.
If it is a table, go to step 2c. Step 2b
Then, the lower table is taken out from the lower table part 21 of the corresponding entry, the lock flag 17 is set to 0, and the process proceeds to step 2 for the lower table, but the key value when searching for an entry based on the key is Depending on the level of the hierarchy, if the target table is the second layer, 5-bit information from the 6th bit to the 10th bit of the reference identifier is used as a key, and if it is the 3rd layer, the 11th of the reference identifier is used.
If the 5th bit information from the 15th bit to the 15th bit is used as a key and it is the 4th layer (that is, the next target table is LR
In the case of U table) The reference identifier is used as a key. In step 2c, the lock flag is set to 0. This completes the setting of the reference bits corresponding to the search data.

In step 3, if the lock flag 17 of the target table is 0, the process proceeds to step 3a, and if the lock flag 17 is 1, waits until the lock flag 17 becomes 0,
Go to step 3a. In step 3a, the lock flag 1
7 is set to 1, and for all entries in the target table,
If the reference bit part 19 is 0, the counter part 20 is incremented by 1, and if the reference bit part 19 is 1, the reference bit part 19 is set to 0.
And the counter unit 20 is set to 0. Next, the entry having the maximum value of the counter unit 20 is searched in the target table, and if the target table is the LRU set table, the process proceeds to step 3b, and if the LRU table, the step 3 is performed.
Go to c. In step 3b, the lower table is taken out from the lower table portion 21 of the entry searched above, the lock flag 17 is set to 0, and the process proceeds to step 3 for the lower table. In step 3c, the value of the data identifier portion 22 of the entry searched above is taken out,
It is used as a data identifier to be replaced, the entry is deleted, the lock flag 17 is set to 0, and the process proceeds to step 4.

In step 4, the replacement data is taken out from the high speed storage device 4 and written back to the low speed storage device 5 based on the data identifier of the replacement target obtained in step 3. Next, the reference data is read from the low-speed storage device 5 based on the reference identifier, the data is written to the high-speed storage device 4, and the first layer LRU table 6 is targeted to proceed to step 5 to register the reference data.

In step 5, the target table is L
If it is a RU set table, proceed to step 5a, L
If it is the RU table, the process proceeds to step 5b. Step 5
In a, the target table is searched using the 5-bit information from the first bit to the fifth bit of the reference identifier as a key, the lower table is searched from the lower table part 21 of the corresponding entry, and the lower table of the corresponding entry is searched. The lower table is taken out from the section 21 and the process proceeds to step 5 for the lower table. However, the key value when searching for an entry based on the key differs depending on the level of the hierarchy, and the target table is the second layer. For example, using the information of 5 bits from the 6th bit to the 10th bit of the reference identifier as a key,
In the case of a layer, 5-bit information from the 11th bit to the 15th bit of the reference identifier is used as a key. In step 5b, if the lock flag 17 of the target table is 0, the process proceeds to step 5c, and if the lock flag 17 is 1, the lock flag 17 is set.
Until 0 becomes 0, and proceed to step 5c. Step 5
In c, the lock flag 17 is set to 1, the value of the identifier portion 22 is the reference identifier, the value of the reference bit portion 19 is 0, and the counter portion 20.
A new entry with the value of 0 set to 0 is registered in the target table, and the lock flag 17 is set to 0. This completes the registration of the reference data in the LRU table.

As described above, by arranging the LRU table into four layers, the size of one table is as small as 32 entries, so that the LRU approximation method can be performed at high speed. Further, in the parallel computer, if another request source program is also attempted to be read in the middle of processing the request source program 1, the lock flag 17 is used to manage the exclusive right for each table. When the access to a table (that is, the LRU set table or the LRU table) of the original program 1 is completed, other requesting programs 2 and 3 can access the table, and the requesting programs 2 and 3 are executed in parallel. The data replacement process between the low-speed storage device and the high-speed storage device can be simultaneously executed by the program.

Although the present embodiment has been described by using an example in which the number of stages of hierarchization of the LRU table is 4 and the size of the high speed storage device is 1 mega word, the number of stages of hierarchization and high speed are explained. The size of the storage device can be any value.

[0023]

As described above, according to the present invention, the LRU
The LRU approximation method can be executed at a high speed by hierarchizing the table into a plurality of stages and reducing the size of one LRU table, and by providing a lock flag for each LRU table and managing the exclusive right, a plurality of request source programs can be obtained. It is possible to execute the replacement processing of in parallel.

[Brief description of drawings]

FIG. 1 is an overall configuration diagram showing an embodiment of the present invention.

FIG. 2 is a configuration diagram showing an LRU set table.

FIG. 3 is a configuration diagram showing an LRU table.

FIG. 4 is a flowchart showing the operation of this embodiment.

FIG. 5 is a flowchart showing the operation of this embodiment.

FIG. 6 is a flowchart showing the operation of this embodiment.

FIG. 7 is a flowchart showing the operation of this embodiment.

FIG. 8 is a configuration diagram showing a conventional LRU approximation method.

FIG. 9 is a flowchart showing the operation.

[Explanation of symbols]

 1-3 Request Source Program 4 High Speed Storage Device 5 Low Speed Storage Device 6-12 LRU Set Table 13-16 LRU Table 17 Locking Flag 18 Key Part 19 Reference Bit Part 20 Counter Part 21 Lower Table 22 Data Identification Part

Claims (2)

[Claims] 1. A high-speed storage device comprising a plurality of entries and a low-speed storage device, wherein when the data to be accessed exists in the high-speed storage device, the data is accessed, and when the data does not exist, the high-speed storage device is accessed. In a storage management system that replaces appropriate data in a storage device with data to be accessed in a low-speed storage device, a table that manages the access order of each data in the high-speed storage device is hierarchized in a plurality of stages, If there is data to be accessed, the first means for updating the hierarchical management table and the reference order information of the reference data, and if there is no data to be accessed in the high-speed storage device, then The second method of replacing the hierarchized management table and the data judged to be accessed most recently with the low-speed storage device. A method for selecting replacement target data, which is characterized by having steps. 2. In the storage management method, when a locking flag is provided for each hierarchical management table and the management table is accessed, if the locking flag is in the unlocked state, the locked state is set and the access is performed. Replacement target data comprising first means for making an unlocked state at the time of completion, and second means for making an access after waiting until the unlocked state if the locking flag is in the locked state. Selection method.