JP2636746B2 - Input/Output Cache - Google Patents

Description

Detailed Description of the Invention

[0001]

FIELD OF THEINVENTION This invention relates to an I/O cache in an I/O processor located between a central processing unit and an I/O device.

[0002]

2. Description of the Related Art An I/O cache is a small-capacity, high-speed memory provided as a storage hierarchy level between a main memory and an I/O device, and provides high-speed access to the I/O device by storing a portion of the contents of the main memory. In conventional cache memories, methods for selecting a block of data to be replaced when a cache miss occurs include, for example, a random method or an LRU (Least Recent) method.
The random method is a method that uses random numbers to randomly determine which block will be replaced next. This random method allows the hardware for replacement control to be realized with a simple configuration. The LRU method is a method that uses the least recently used (cently used) method to prevent valid data blocks that store highly needed data from being expelled to main memory.
Records accesses to each block in the cache,
This method targets data in a block that has not been accessed for the longest time for replacement. This LRU method allows for efficient data transfer because frequently used blocks remain in the cache.

These conventional block replacement methods are described, for example, in "Nagashima and Horikoshi, Cache Memory, Information Processing, Vol. 21, No. 4, pp. 332-340 (April 1980)"
can be referred to.

[0004]

However, in the conventional random method, even if a block of data is highly necessary,
There was a risk that it would be replaced and pushed out to main memory without any special consideration.

Furthermore, even if the LRU method is used, since operations such as frequently rewriting data at the same address are rare in an I/O cache, it is difficult to distinguish between the frequencies of use of blocks, and therefore there is a problem that little improvement in data transfer performance can be expected.

That is, data transfers from I/O devices often involve accessing large volumes of data using consecutive addresses, and rather than immediately accessing data that has already been accessed once, once the block has been accessed from start to finish, the block is often no longer needed. Also, among I/O devices, there are relatively high-speed devices such as disk devices and low-speed devices such as line devices. Therefore, when determining which blocks to replace in the I/O cache, it is necessary to take into account the unique circumstances of each I/O device.

SUMMARY OF THE PRESENT EMBODIMENT An object of the present invention is to solve the above problems and provide an I/O cache having a block replacement algorithm suitable for I/O caches.

Another object of the present invention is to determine whether a block has been accessed up to the last byte in the block or whether the block contains data from a device other than a disk device,
The present invention aims to determine a replacement target block by making the most of the characteristics of an input/output device when a cache miss occurs.

A further object of the present invention is to improve the performance of data transfer between a main memory device and an input/output device.

[0010]

[Means for solving the problems] In order to solve the above problems, the input/output cache of the present invention is an input/output cache managed on a block-by-block basis and accessed by an input/output device, and includes a first access flag holding means for holding a first access flag for each block which is set when accessed by the input/output device if the input/output device is an I/O device other than a disk device, and a replacement target block determination means for determining which block of the input/output cache should be selected as the replacement target block depending on the contents of the first access flag holding means when reserving a new block in the input/output cache.

Another input/output cache of the present invention comprises:
An input/output cache managed for each block and accessed by an input/output device, the input/output cache storing a first access flag for each block, the first access flag being set if the access is a line-based access when the input/output device accesses the first block.
and a replacement target block determination means for determining which block of the input/output cache should be selected as a replacement target block in accordance with the contents of the first access flag holding means when reserving a new block in the input/output cache.

Another input/output cache of the present invention comprises:
An input/output cache managed for each block and accessed by an input/output device, the input/output cache having a first access flag holding means for holding a first access flag for each block, the first access flag being set if the input/output device is an input/output device other than a disk device when the input/output device accesses the block, and a second access flag indicating that a byte at the last position in the block has been accessed.
and a replacement target block determination means for determining which block of the input/output cache should be selected as a replacement target block according to the contents of the first access flag holding means and the second access flag holding means when reserving a new block in the input/output cache.

Another input/output cache of the present invention comprises:
An input/output cache managed for each block and accessed by an input/output device, the input/output cache storing a first access flag for each block, the first access flag being set if the access is a line-based access when the input/output device accesses the first block.
the first access flag holding means for holding a second access flag for each block indicating that the last byte in the block has been accessed; and replacement target block determination means for determining which block of the input/output cache should be selected as a replacement target block in accordance with the contents of the first access flag holding means and the second access flag holding means when reserving a new block in the input/output cache.

Another input/output cache of the present invention comprises:
In an input/output cache managed on a block-by-block basis and accessed by an input/output device, the replacement target block determination means includes an unused block presence/absence determination unit which determines whether there is an empty block in the input/output cache, a first access block presence/absence determination unit which determines whether there is a block in which the first access flag is set according to the contents of the first access flag holding means, a block status determination unit which determines the status of each block in the input/output cache, and a search position holding unit which holds the start position of a block search when determining a replacement block, wherein the unused block presence/absence determination unit searches each block from the position held by the search position holding unit, and if an unused block is found, it determines the block as the replacement target block, and the first access block presence/absence determination unit searches each block from the position held by the search position holding unit, and if a block in which the first access flag is set is found, it determines the block as the replacement target block.

Another input/output cache of the present invention comprises:
In an I/O cache managed for each block and accessed by an I/O device, the replacement target block determination means includes an unused block presence/absence determination section for determining whether or not there is a free block in the I/O cache, a first access block presence/absence determination section for determining whether or not there is a block in the I/O cache with the first access flag set according to the contents of the first access flag holding means, and a replacement target block determination section for determining whether or not there is a block in the I/O cache with the first access flag set according to the contents of the second access flag holding means.
a second access block presence/absence determination unit that determines whether or not there is a block in which the access flag is set;
The input/output cache includes a block status determination unit which determines the status of each block, and a search position holding unit which holds the start position of a block search when determining a replacement block, wherein the unused block presence/absence determination unit searches each block from the position held by the search position holding unit, and if an unused block is found, determines the block as the block to be replaced, the second access block presence/absence determination unit searches each block from the position held by the search position holding unit, and if a block with the second access flag set is found, determines the block as the block to be replaced, and the first access block presence/absence determination unit searches each block from the position held by the search position holding unit, and if a block with the second access flag set is found, determines the block as the block to be replaced.

Another input/output cache of the present invention comprises:
The memory device has a data array for storing data, and a tag array for storing addresses and control information corresponding to the data array, the control information including the first access flag holding means and the second access flag holding means.

Another input/output cache of the present invention comprises:
When a cache block is accessed for a certain number of bytes or more, the first access flag corresponding to the accessed block is set.

Another input/output cache of the present invention comprises:
When a cache access is not accompanied by a disk unit identification signal, the first access flag corresponding to the accessed block is set.

[0019]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, an embodiment of an input/output cache according to the present invention will be described in detail with reference to the accompanying drawings.

Referring to FIG. 1, an input/output cache 100 embodying the present invention is included in an input/output processing unit 104 located between a system bus 103 to which a central processing unit 101 and a main memory unit 102 are connected, and an input/output bus 105 to which a group of input/output devices 106-1 to 106-n are connected.

When the central processing unit 101 issues a transfer command from the main memory 102 to the input/output unit 106, the input/output unit 106 reads the I/O bus input buffer 1
11 and the selector 112 through the I/O cache 1
00. If the desired data is present in I/O cache 100, the data is transferred to destination I/O device 106 via selector 114 and I/O bus output buffer 110. If the desired data is not present in I/O cache 100, the request is notified to main memory 102 via selector 113 and system bus output buffer 108. The block containing the requested data is read from main memory 102 and then stored in I/O cache 100 via system bus input buffer 107 and selector 112. The requested data is also transferred to destination I/O device 106 via selector 114 and I/O bus output buffer 110.
Storing the block in the I/O cache eliminates the need for subsequent access to main memory 102 for the data in that block.

It should be noted that FIG. 1 shows only those parts of the I/O processor 104 that relate to the I/O cache.

2, an I/O cache 100 according to an embodiment of the present invention includes a data array 208 for storing data, and a tag array 207 for storing addresses and control information corresponding to the data array 208. The I/O cache 100 also includes a data buffer 204 for holding commands, addresses and data.
01, an unused block presence/absence determination circuit 202 that determines the presence or absence of unused blocks, an LBU block presence/absence determination circuit 203 that determines the presence or absence of LBU (abbreviation of Last Byte Used) blocks, a block status determination circuit 204 that determines the status of each block, and an NDA block presence/absence determination circuit 206 that determines the presence or absence of NDA (access by a device other than a disk, abbreviation of Non Disk Access) blocks.
5, a replacement block determination circuit 206 that determines a block to be replaced and issues an instruction to that effect, and a replace pointer 209 that indicates the start point for searching for the replacement object.
a comparator 210 that detects whether the block to be replaced matches the block indicated by the replace pointer 209 ; and a cache control circuit 211 that controls the cache tag array 207 and the cache data array 208 .

In one embodiment of the present invention, the I/O cache comprises:
The cache tag array 207 stores the following for each block: “invalid (hereinafter referred to as I)”, “shared (hereinafter referred to as S)”, “matched/unmatched”
It is assumed that each block has one of the following statuses: "exclusive (hereinafter referred to as CE)" or "mismatched/exclusive (hereinafter referred to as DE)." If the status is "I," it indicates that no valid data is stored in that block. If the status is "S," the block is not available to the central processing unit 101.
The status indicates that the block is shared between the I/O cache and the I/O cache 100. If it is "CE", it indicates that the block is exclusively used by the I/O cache 100 and its contents match those of the storage device. If it is "DE", it indicates that the block is exclusively used by the I/O cache 100 and its contents do not match those of the storage device. These statuses are based on existing technology and can be used in a variety of ways, such as:
“Amano et al.: Parallel Processing Mechanism, Maruzen, pp.186-190 (198
The report is included in the August 2009 issue of the

In one embodiment of the present invention, the I/O cache comprises:
The cache tag array 207 further holds an LBU flag and an NDA flag for each block.

The LBU flag indicates that a read or write access has been made to the last byte in a block.
Large amounts of data are often accessed using consecutive addresses, and rather than immediately accessing data that has already been accessed once, it is often the case that once a block has been accessed from start to finish, that block becomes unnecessary. Therefore, this LBU flag is provided, and a block whose last byte has been accessed is made a replacement target.

The NDA flag indicates that the block is being used by a device other than the disk device. Since access to disk systems that can be transferred at high speeds is mainly for 16-byte transfers, and access to low-speed transfers such as line systems is mainly for 2-byte transfers, the I/O cache can be used more efficiently by flushing data from other low-speed devices rather than flushing data from disk systems that can be accessed at high speeds. To set this NDA flag, for example, when the I/O cache is accessed with a transfer of less than 16 bytes, the NDA flag of the block that is the object of the access can be set. Also, when the disk device is accessed, an identification signal can be sent to the I/O processor 104, and if this signal is not present, it can be assumed that the access is from a device other than the disk device, and the NDA flag of the block that is the object of the access can be set.

The cache control circuit 211 changes the status of the cache tag corresponding to each block, and also sets the LBU flag and NDA flag, according to the command and address held in the data buffer 201 and the contents of the cache tag array 207. The cache control circuit 211 also performs replacement processing of the cache tag array 207 and the cache data array 208 at the time of a cache miss, according to the replacement block and replacement instruction from the replacement block determination circuit 206.

The block status determination circuit 204 refers to the data in the cache tag array 207 and determines whether the status of each block is "S" or "CE" or
The result is sent to the LBU block presence/absence determination circuit 203 and the NDA block presence/absence determination circuit 204.
Send to 05.

The unused block presence/absence determination circuit 202 refers to the contents corresponding to each block in the cache tag array 207 and the replacement pointer 209, and if there is a block with a status of "I", it sends that fact and the block number to the replacement block decision circuit 206.

The LBU block presence/absence determination circuit 203 detects the LB corresponding to each block in the cache tag array 207.
It refers to the U flag, the value of the replace pointer 209 and the status information of each block from the block status determination circuit 204, and if there is a block for which the LBU flag is set, it sends that fact, the number of that block and its status to the replacement block determination circuit 206.

The NDA block presence/absence determination circuit 205 determines the ND corresponding to each block of the cache tag array 207.
It refers to the A flag, the value of the replace pointer 209, and the status information of each block from the block status determination circuit 204, and if there is a block with the NDA flag set, it sends that fact, the number of that block, and its status to the replacement block determination circuit 206. If there is no block with the NDA flag set, it sends that fact, the number of that block, and its status to the replacement block determination circuit 206.
The result is sent to a replacement block decision circuit 206 .

The replacement block determination circuit 206 determines a replacement block based on the replacement pointer 209 and the results of the cache block determinations made by the unused block presence/absence determination circuit 202, the LBU block presence/absence determination circuit 203, and the NDA block presence/absence determination circuit 205,
The block number and replacement instruction are output.

When a replacement instruction is output from replacement block determination circuit 206, comparator 210 compares the replacement block number output by replacement block determination circuit 206 with the value of the replace pointer, and if the two values match, increases the value of replace pointer 209 by one.

Next, the operation of one embodiment of the input/output cache of the present invention will be described in detail with reference to the drawings.

3 and 2, the replace pointer 209 is initially set to 0, which indicates the first block of the cache (S301). When a cache miss occurs and it becomes necessary to replace a cache block (S302), the replace pointer 209 is first
Check whether the status of the block indicated by is "I" (S
303), if "I", current replace pointer 2
The block indicated by S09 is determined as the block to be replaced (S
304).

If the status of the block pointed to by the current replace pointer 209 is not "I", other blocks are searched for "I" starting from the blocks closest to the replace pointer (S305), and if there is a block with a status of "I", that block is made the target for replacement (S306).

If there is no "I" block in the above process, this means that there are no free blocks in the cache, so a replacement target will be searched for among the blocks in use. Then, it is determined whether there is a block that has been used up to the last byte.

The LBU flag is set and a block with a status of "S" or "CE" is searched for, starting from the block closest to the replace pointer (S30).
7), if there is one, that block is selected as the replacement target (S3
08). If there is no corresponding block, the status will be "D
The blocks in "S" and "CE" are searched for a block with the LBU flag set, starting from the block closest to the replace pointer (S309), and if any, the block is selected as the replacement target (S310).
The reason why the block in is the first to be replaced is that the same data exists in the main memory in these statuses.
When replacing, there is no need to write the data of the block back to the main memory, so the replacement process can be completed immediately.
In the case of block "E", the data does not match the data in main memory, so when replacing it, it is first necessary to write the data of that block back to main memory, and the data in that block cannot be replaced until writing of this block data to main memory is completed.

In the above process, if there is no block that uses the last byte, it is determined whether or not the NDA flag is set.

The NDA flag is set, and
Search for blocks with a status of "S" or "CE" in order of proximity to the replace pointer 209 (S31
1), if there is one, that block is selected as the replacement target (S3
12) If there is no corresponding block, the status will be "D
The system searches for a block with the NDA flag set among the blocks in "DE" (S313), starting from the block closest to the replace pointer, and if there is one, it selects that block as the replacement target (S314).
When a block becomes a replacement target, the data of that block is written to the main memory and then replaced, similar to the process when the LBU flag is set (S310).

In the above process, if there is no block with the NDA flag set, it is understood that all blocks in the cache are related to the disk, so first, a search is made for blocks with a status of "S" or "CE" starting from blocks closest to the replace pointer 209 (S315), and if there is one, that block is determined to be the block to be replaced (S316). If there is no such block, only blocks with a status of "DE" remain, so in that case, the block pointed to by the replace pointer 209 is determined to be the block to be replaced (S317).

Through the above process, the block to be replaced is determined, and the status of that block is set to "S".
If the status is "CE", the data stored in the block is not written back to the main memory and the replacement process is executed, and if the status is "DE", the data stored in the block is first written to the main memory and then the replacement process is executed (S318). Then, the number of the replaced block is compared with the value of the replace pointer (S
If they are different, the value of the replace pointer 109 remains the same, but if they are the same, the value of the replace pointer 209 is incremented by one (S320) in preparation for the next cache access (S302).

In this way, according to the input/output cache of the embodiment of the present invention, by providing an LBU flag and an NDA flag for each block of the cache tag array 207, a block which has been accessed up to the last byte in the block or a block which contains data from a device other than a disk device can be detected by the LBU block presence/absence determination circuit 203 or the ND flag.
This can be easily determined by the A block presence/absence determination circuit 205.
It is possible to determine which blocks should be replaced from a performance perspective.

[0045]

As is clear from the above explanation, according to the present invention, by providing an LBU flag and an NDA flag to indicate the state of the cache memory, it is possible to easily distinguish a block which has been accessed up to the last byte in the block or a block which contains data from a device other than a disk device.
Since the block to be replaced can be determined by taking advantage of the characteristics of the I/O device when a cache miss occurs, the data transfer performance between the main memory device and the I/O device can be improved.

[Brief description of the drawings]

FIG. 1 is a diagram showing an example of an external connection of an I/O cache according to the present invention.

FIG. 2 is a diagram showing the configuration of an embodiment of an input/output cache of the present invention.

FIG. 3 illustrates the operation of an I/O cache in one embodiment of the present invention.

[Explanation of symbols] 100 I/O cache 101 Central processing unit 102 Main memory unit 103 System bus 104 I/O processing unit 105 I/O bus 106 I/O unit 107 System bus input buffer 108 System bus output buffer 110 I/O bus output buffer 111 I/O bus input buffer 112-114 Selector 201 Data buffer 202 Unused block presence/absence determination circuit 203 LBU block presence/absence determination circuit 204 Block status determination circuit 205 NDA block presence/absence determination circuit 206 Replacement block determination circuit 207 Cache tag array 208 Cache data array 209 Replace pointer 210 Comparator 211 Cache control circuit

Claims (6)

(57) [Claims] Claim 1: Managed by block and controlled by input/output device
In the I/O cache to be accessed , when an access is made from the I/O device,
The first access point that is set if the device is an I/O device other than the
an access flag holding means for holding an access flag for each block; and a replacement target block determination means for determining which block of the input/output cache should be selected as a replacement target block in accordance with the contents of the first access flag holding means when reserving a new block in the input/output cache. Claim 2: Managed by block and by input/output device
In an I/O cache that is accessed by an I/O processor slower than a predetermined speed,
The first access flag is set when an access occurs.
and a replacement target block determining means for determining which block of said input/output cache should be selected as a replacement target block in accordance with the contents of said first access flag holding means when reserving a new block in said input/output cache. Claim 3: Managed by block and by input/output device
In the I/O cache to be accessed , when an access is made from the I/O device,
The first access point that is set if the device is an I/O device other than the
a first access flag holding means for holding an access flag for each block; and a second access flag for holding, for each block, a second access flag indicating that a byte at the last position in the block has been accessed.
a second access flag holding means, when reserving a new block in the I/ O cache,
and a replacement target block determining means for determining which of the blocks in said input/output cache should be set as a replacement target block in accordance with the contents of said access flag holding means. Claim 4: Managed by block and by input/output device
In an I/O cache that is accessed by an I/O processor slower than a predetermined speed,
The first access flag is set when an access occurs.
a first access flag holding means for holding a first access flag for each block; and a second access flag for holding, for each block, a second access flag indicating that a byte at the last position in the block has been accessed.
a second access flag holding means, when reserving a new block in the I/ O cache,
and a replacement target block determining means for determining which of the blocks in said input/output cache should be set as a replacement target block in accordance with the contents of said access flag holding means. 5. The replacement target block determination means comprises: an unused block presence/absence determination section for determining whether or not there is an empty block in the I/O cache; and a replacement target block determination section for determining whether or not there is an empty block in the I/O cache according to the content of the first access flag holding section.
An input/ output cache as described in claim 1, comprising: a first access block presence/absence determination unit that determines whether there is a block with a first access flag set; a block status determination unit that determines the status of each block of the input/output cache; and a search position holding unit that holds the start position of a block search when determining a replacement block, wherein the unused block presence/absence determination unit searches each block from the position held by the search position holding unit, and if an unused block is found, it determines the block as the block to be replaced, and the first access block presence/absence determination unit searches each block from the position held by the search position holding unit, and if a block with the first access flag set is found, it determines the block as the block to be replaced. 6. The replacement target block determination means comprises: an unused block presence/absence determination section for determining whether or not there is an empty block in the I/O cache; and a first access flag setting section for setting the first access flag in the I/O cache according to the content of the first access flag holding section.
a first access block presence /absence determination unit for determining whether or not there is a block in which the second access flag is set in the I/O cache according to the content of the second access flag holding means; and a second access block presence/absence determination unit for determining whether or not there is a block in which the second access flag is set in the I/O cache according to the content of the second access flag holding means.
an unused block presence/absence determination unit for determining whether or not an unused block is present; a block status determination unit for determining the status of each block of the input/output cache; and a search position holding unit for holding a block search start position when determining a replacement block, wherein the unused block presence/absence determination unit searches each block from the position held by the search position holding unit, and if an unused block is found, determines the block as the block to be replaced ; the second access block presence/absence determination unit searches each block from the position held by the search position holding unit, and if a block with the second access flag set is found, determines the block as the block to be replaced ; and the first access block presence/absence determination unit searches each block from the position held by the search position holding unit, and if a block with the second access flag set is found, determines the block as the block to be replaced.