JP2000035918A - Cache memory device - Google Patents

Abstract

(57) [Summary] The present invention relates to a cache memory device,
It is an object of the present invention to improve a cache hit rate and reduce a data transfer amount due to prefetching. SOLUTION: In a cache main memory which holds a part of contents of a main memory and exchanges data with a processor instead of the main memory, data is prefetched from the main memory based on an address requested from the processor. In such a case, the data of the upper and lower addresses of the request address is read and held.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a high-speed, small-capacity memory which is disposed between a processor and a main memory, temporarily stores data in the main memory, and replaces the main memory with the processor and the data. The present invention relates to a cache memory device that exchanges data.

[0002]

2. Description of the Related Art The processor speed of computer systems has increased, and correspondingly high-speed storage devices have been required. However, the access speed of the main memory is not as fast as that of the processor, and the time difference is increasing. Therefore, how fast the data in the main memory can be supplied affects the performance of the entire system. Therefore, it is important for the computer system to shorten the access time of the main memory.

[0003] The cache memory is a high-speed, small-capacity memory used to reduce the access time of the processor, and is located between the processor and the main memory. Then, a part of the contents of the main memory is copied and held, and data is exchanged with a processor instead of the main memory to realize high-speed data access.

FIG. 15 shows a computer system having a conventional cache memory. FIG. 15A illustrates a conventional computer system, and FIG. 15B illustrates a prefetch operation of the conventional computer system.

[0005] From the processor 110 to the main memory 120
Is issued, first, in the cache device 111, the control device 113 receives the access request. The control device 113 controls the cache memory 11
2 is searched to determine whether data corresponding to the requested address is held in the cache memory 112. If data corresponding to the requested address is held in the cache memory 112, the control device 113 does not access the main memory 120 and
2 and return it to the processor 110. In this case, the cache memory 112 is
Because of the higher speed, data can be returned in a shorter time than accessing the main memory 120.

If the requested data is not held in the cache memory 112, the control device 113
Requesting data from the cache memory 1 and transferring the returned data to the processor 110;
12 is also stored. This takes advantage of the temporal locality of memory access, which is likely to be accessed in the near future for the address once requested,
This is to improve the cache hit rate.

[0007] The control device 113
The case where data corresponding to the requested address is found is called a cache hit, and the case where it cannot be found is called a cache miss. The number of cache hits with respect to the total number of access requests is called a cache hit ratio.

When the cache hit rate is improved, the number of times data can be supplied from the high-speed cache memory 112 instead of the low-speed main memory 120 increases, so that the average access time is reduced. Therefore, an improvement in the cache hit rate leads to an increase in the speed of the memory system, and further to an improvement in the performance of the entire system. For this reason, various attempts have been made to improve the cache hit rate.

The greatest contrivance for improving the hit ratio is to utilize the spatial locality of memory access. The term "spatial locality of memory access" generally means that a memory address close to a memory address once accessed is likely to be accessed in the near future. The most widely used method utilizing this property is access in block units. This means that when a cache miss occurs, not only the data corresponding to the address where the miss occurred, but also the data corresponding to the address that will be accessed in the near future, that is, the address located near the accessed address. This is a method in which data to be processed are collectively stored in the cache memory 112. In general, a method is used in which the main memory 120 is divided into blocks each having a fixed length, and all blocks including a memory corresponding to the address at which the access request is generated are stored in the cache memory.

In order to further utilize the spatial locality of memory access, the block size may be increased.
However, simply increasing the block size,
When writing back from the cache memory 112 to the main memory 120, there arises a problem that wasteful traffic is likely to occur. Therefore, the size of the block can only be increased to a certain extent. Therefore, when the spatial locality is to be further utilized, writing back to the main memory 120 can be performed in small units.
The block size is kept small and the main memory 12
When reading from 0 to the cache memory 112, a method of reading a plurality of blocks simultaneously is used.

At this time, it is also conceivable to simultaneously read not only the adjacent blocks but also the next accessible block, read the block with the accessed block from the main memory 120, and store it in the cache memory 112. .

The method of transferring not only the block containing the address for which the access request was made but also the other blocks collectively from the main memory to the cache memory is called prefetching. The prefetching occurs not only when a read request is issued from the processor to the main memory, but also when the processor writes to the cache memory. At this time, when the data requested to be updated does not exist in the cache memory, the cache memory fetches the data requested to be accessed by the main memory, predicts the next block which is likely to be accessed next, and reads the data of the block. Is also read from the main memory and held in the cache memory at the same time.

Among the prefetching methods, the simplest one is a method in which blocks (corresponding to a higher memory address) following a block including an address for which an access request is made are collectively stored in a cache memory.

FIG. 15B shows the operation of this system. Generally, an access request from a processor is often made continuously in an upper address direction. Therefore, if the block of the next higher address is pre-read and held, the probability of a cache hit increases.

Further, as a more complicated method, there is a method of predicting a block to be prefetched using the access history so far. For example, if addresses at a certain interval are continuously accessed, it can be predicted that the next access will be a certain width ahead. In that case, the data of the block including the predicted address may be stored in the cache memory. There is also a method of predicting whether a next address is accessed or not by a suitable logic circuit based on the history so far, and prefetching a block corresponding to the address.

[0016]

However, these techniques have the following problems. The method of prefetching and storing the block of the upper address works effectively only when the address is simply accessed continuously in the upper direction. In a real application program, there are many random accesses, and this method is only effective to a certain extent. In addition, the method of adaptively predicting a block to be prefetched and the method of predicting a fixed interval have problems that the structure is complicated and accurate prediction is difficult.
In particular, the method of predicting a fixed interval has a certain effect on a regular application program such as array access, but has little effect on an application program such as a database. In addition, the method of predicting with a logic circuit also has a problem that the logic for prediction is difficult to assemble.

Further, as can be said for the prefetching method in general, there is a possibility that the prefetched block may not be accessed by the processor after all, so that unnecessary blocks are always stored in the cache memory. This means that the actual utilization rate of the cache memory is reduced, and that unnecessary data transfer is performed between the main memory and the cache memory.

The present invention, taking these problems into account,
It is an object of the present invention to provide a cache memory device that relatively simply improves the cache hit rate and reduces the amount of data transferred by prefetching even in the case of irregular access, for example, in an application program such as a database.

[0019]

According to the present invention, when a cache miss occurs, not only a block including an address requested to be accessed but also a cache memory device is disclosed.
The upper n blocks and the lower m blocks are also prefetched.

Further, this block is higher (U) or lower (D) with respect to the original requested block.
The tag which distinguishes is provided. This tag is used for the next look-ahead.

This tag can be provided by a method of attaching it to the block read ahead, a method of providing only an independent tag without corresponding to the data of the block read ahead, or both.

Further, the tag can be provided with a parameter k called depth. This depth is used when determining whether to prefetch or not.

FIG. 1 shows the basic configuration of the present invention. In FIG. 1, reference numeral 1 denotes a processor.

Reference numeral 2 denotes a cache memory device. 3 is a cache memory. Reference numeral 4 denotes a cache control device.

A control unit 5 determines whether or not the data of the address requested by the processor 1 exists in the cache memory 3 and determines a cache hit and a cache miss of the address requested to be read. It is to judge. If it is a cache hit, a read instruction (at the time of a read request) or a write (write request) from the cache memory 3 is issued.
If it is a cache miss, it instructs the main memory 10 to copy the data of the requested address and the data of the upper and lower addresses of the requested address to the cache memory 3.

Reference numeral 6 denotes a cache hit judging unit for judging a hit or a mishit of an address for which an access request has been made. Reference numeral 7 denotes a data reading unit which reads data from the main memory 10 at an address for which an access request has been made.

Numeral 8 denotes a lower block reading section for reading data from the main memory 10 at a lower address than the requested address. Reference numeral 9 denotes an upper block reading unit which reads data of an upper address from the requested address from the main memory 10.

Reference numeral 10 denotes a main memory. The operation of the configuration of FIG. 1 will be described. An access request is generated from the processor 1 (read from the main memory 10 or write to the main memory 10). Cache hit determination unit 6
Determines whether there is data at the requested address in the cache memory 3. If the data at the requested address is in the cache memory 3 (cache hit), the data read unit 7 instructs a read from the cache memory 3 (at the time of a processor read request) or writes the data to the cache memory (from the processor). At the time of a write request). If the data of the requested address is not in the cache memory 3 (cache miss), the data reading unit 7 reads the data of the requested address from the main memory 10, stores the data in the cache memory 3 and transfers the data to the processor 1 (read by the processor). (At the time of a request) or data of the requested address is read from the main memory 10 and written from the processor to the requested address (at the time of a write request from the processor). Furthermore, if there is a cache mishit, in any case of writing, the cache memory 3
When the data is read from the main memory 10, the lower block read unit 8 and the upper block read unit 9 read the data of the lower block and the upper block of the requested address from the main memory 10, respectively, and store them in the cache memory 3.

According to the present invention, when a cache miss occurs, not only the block including the address requested to be accessed but also the upper n blocks and the lower blocks m are to be prefetched. For this reason, the cache hit rate can be improved not only in the case of continuous access in the upper direction but also in the case of random access to some extent, as compared with simple prefetching of only the upper block.

[0030]

FIG. 2 shows Embodiment 1 of the present invention.
The embodiment of the cache memory device used in the second embodiment is shown.

In FIG. 2, reference numeral 1 denotes a processor for generating a memory access. 2 is a cache memory device.

Reference numeral 3 denotes a cache memory, which comprises a cache array 21 for holding cache data and a prefetch buffer 22 for holding prefetch data. The cache memory is expensive and has a small capacity, but is a high-speed memory.

Reference numeral 4 denotes a cache control device. In the cache control device 4, reference numeral 5 denotes a control unit.

Reference numeral 6 denotes an address calculation unit. A main memory 10 holds data to be accessed by the processor. The main memory is slow but cheap and of large capacity. Reference numeral 23 denotes a data selection unit which selects data read from the cache array 21 and data read from the pre-read buffer 22 and passes them to the processor 1.

In the cache memory 3, reference numeral 21 denotes a cache array which holds data read from the main memory when a cache miss occurs.

Reference numeral 22 denotes a prefetch buffer which holds data prefetched from the main memory 10 when a cache miss occurs. 10 is a main memory.

The operation of the configuration shown in FIG. 2 will be described. The prefetch according to the present invention is applied to both a read request and a write request from the processor. Hereinafter, the operation will be described by taking as an example a case where there is a read request from the processor.

When an access request is issued from the processor 1, in the cache control device 4, the control unit 5 converts the address into a block address. This is because all processes performed in the cache memory device 2, such as management in the cache array, management of prefetching, and data request to the main memory, are performed in block units.

Next, the control unit 5 checks whether the block address having the requested address is already stored in the cache array 21 and the prefetch buffer 22 (used in the same meaning as the search). Since the cache array 21 and the prefetch buffer 22 are independent memories, this check can be performed simultaneously.

The requested data is stored in the cache array 21.
In the case of a cache hit, the requested data is read from the cache array 21, selected by the data selection unit 23, and transferred to the processor. At this time,
No prefetching is performed.

If there is a cache hit but not in the cache array 21 but in the prefetch buffer 22,
The control unit 5 performs the following three operations. 1. The data is read from the prefetch buffer 22 and copied to the cache array 21.

At the same time as 2.1, the data read from the prefetch buffer 22 is returned to the processor 1 as a result of the access request (the data in the prefetch buffer 22 is read, selected by the data selection unit 23, and transferred to the processor).

When the steps 3 and 2 are completed, the data is deleted from the prefetch buffer 22. If there is no data corresponding to the requested block address in either the cache array or the prefetch buffer 22, the control unit 5 issues a data read request to the main memory 10. At this time, as described with reference to FIG. 1, not only the memory requested to be accessed by the processor 1 but also the data of the blocks corresponding to the upper and lower parts thereof are requested. In Embodiment 1, m = 1 and n = 1 will be described as an example.

At this time, if the upper and lower blocks already exist in the cache array 21, no read request is made to the main memory 10. The same applies to the prefetch buffer 22. However, when the inspection in the prefetch buffer 22 is difficult due to mounting reasons, even if the prefetch buffer 22 already has the same data as the prefetch target data, the prefetch may be performed. . However, the same data is duplicated in the prefetch buffer 22, so that the memory is wasted and the data transfer amount between the main memory 10 and the cache memory 3 increases.

When the read result is returned, the block requested by the processor 1 for access is stored in the cache array 21 and returned to the processor 1 as a result of the access request. The blocks corresponding to the upper order and the lower order are stored in the prefetch buffer 22.

In FIG. 2, the cache memory is divided into the cache array 21 and the prefetch buffer 22, and the prefetch data is stored in the prefetch buffer 22, but the prefetch data may be stored directly in the cache array 21. . The present invention can be applied to any configuration of the cache memory, but in the following description, FIG.
The case of the configuration described above will be exemplarily described.

FIG. 3 shows the configuration of the cache array and the prefetch buffer according to the first embodiment of the present invention. FIG. 3A shows the configuration of the cache array.

FIG. 3B shows a configuration using a prefetch buffer. In the first embodiment, the cache array and the prefetch buffer have the same configuration, and are composed of a block address, data, and a flag indicating whether the column is valid or invalid.
The look-ahead buffer has fewer buffer columns.

In the configuration of the cache array, in addition to the direct map system (one block corresponds to one block) as shown in FIG. 3, a set associative system (a plurality of blocks correspond to one column) Although the present invention can be applied to any of them, the first embodiment exemplarily describes a direct map method.

In the first embodiment, when an access request is issued from the processor, blocks corresponding to the upper and lower blocks are prefetched and stored in the prefetch buffer. By doing so, even if there is no cache hit,
Since the possibility of hitting the prefetch buffer is increased, the cache hit rate is improved. Furthermore, since not only the upper block but also the lower block is prefetched, a high hit ratio can be obtained even when the access is made random.

FIG. 4 is a flowchart of the first embodiment of the present invention. S1, S2 Check if the requested block already exists in the cache array.

S3, S4 If the judgment result in S2 exists, it is checked whether the requested block already exists in the prefetch buffer. If the determination results in S5 and S4 exist, the data in the prefetch buffer is transferred to the cache array.

S6 The data in the prefetch buffer is deleted. S7 If there is no test result in S4, the main memory is requested to transfer data of the requested block, upper block, and lower block.

S8 If the judgment result in S2 exists, the access result is sent to the processor. FIG. 5 shows the configuration of the prefetch buffer according to the second embodiment of the present invention.

According to the second embodiment of the present invention, the pre-read data in the pre-read buffer is provided with a tag indicating the direction of the next pre-read. Note that the device configuration of the second embodiment is the same as that of FIG.

With respect to the pre-read block, a direction indicating whether the block is higher (U) or lower (D), when viewed from the original requested block, is recorded. When the subsequent access hits the pre-read block, the direction of this tag is checked, and if the tag content is U, only the higher-order block is pre-read, and the tag content is D.
If so, only the lower block is prefetched. Thus, when continuous access occurs in both the upper direction and the lower direction, there is always a block that has been pre-read, and the cache hit rate can be further improved.

In the recording of the direction, specifically, as shown in FIG. 5, a tag (direction (U / D)) indicating a pre-read state is added to the block data. This tag is an extended form of the flag indicating valid / invalid. The direction takes the value of U or D, and if U, it indicates that the requested block is a block adjacent to the original block in the upper direction,
D indicates that the block is a block adjacent to the requested original block in the lower direction.

This embodiment performs the following operation. The operation from the generation of the access request to the main memory by the processor to the checking of the cache array and the prefetch buffer is the same as in the first embodiment. In the second embodiment, when there is data, the tag (direction) of the pre-read buffer is also read when there is data in the pre-read buffer.

If the data corresponding to the requested block address has already been stored in the cache array, the control unit reads the data from the cache array and returns it to the processor as a result of the access request.
In this case, prefetching is not performed.

When data corresponding to the requested block address is stored in the cache array, the control unit performs the following four operations. 1. The data is read from the prefetch buffer and copied to the cache array.

Simultaneously with 2.1, the data read from the prefetch buffer is returned to the processor as a result of the access request. 3. Further prefetching is performed according to the state of the tag (direction) of the prefetch buffer.

If the direction state is U, data corresponding to a higher-order block address is set as prefetch data,
Request to main memory. If the direction state is D, the data corresponding to the lower block address is requested to the main memory as prefetch data.

4. When 1, 2, and 3 are completed, the data is deleted from the prefetch buffer. If the data corresponding to the requested block address is neither in the cache array nor in the prefetch buffer, the control unit issues a data read request to the main memory. At this time, as described with reference to FIG. 1, not only the memory to which the processor has made an access request, but also the upper and lower blocks (m = 1, n = 1) corresponding to the upper and lower blocks are requested. Setting an appropriate tag (direction (U / D), etc.) is the same as in the first embodiment of the present invention.

FIG. 6 is a flowchart according to the second embodiment of the present invention. S1, S2 Check if the requested block already exists in the cache array.

S3, S4 If the determination result in S2 does not exist, it is checked whether the requested block already exists in the prefetch buffer. If the determination results in S5 and S4 exist, the data in the prefetch buffer is transferred to the cache array.

S6, S7 The direction of the tag is checked, and if it is lower (D), the data of the lower block is prefetched in S7. S6, S8 The direction of the tag is checked, and if it is higher (U), the data of the upper block is prefetched in S8.

S9 Erases the requested block in the prefetched buffer. S10 If it is determined in S4 that the requested block does not already exist in the prefetch buffer, the main memory is requested to transfer data of the requested block, upper block, and lower block.

S11 A direction tag of U is attached to the upper block, and a direction tag of D is attached to the lower block, and stored in the prefetch buffer. S12 Send the access result to the processor.

FIG. 7 shows Embodiments 3, 4, 5, and 5 of the present invention.
6 shows a configuration of a cache memory device used in the second embodiment. FIG.
Consists of a tag (look-ahead tag) separately from the look-ahead buffer.
It has a buffer that holds only

In FIG. 7, the same reference numerals as those in FIG. 2 denote the same items. A buffer 23 holds a prefetch tag. Details of the operation of the configuration in FIG. 7 will be described later.

FIG. 8 shows a third embodiment of the present invention. The cache array and prefetch buffer of the third embodiment are the same as those of the first embodiment shown in FIG.

In Embodiments 1 and 2 described above, useless prefetching occurs, the number of blocks to be prefetched increases, and data transfer between the main memory and the cache memory may increase too much. In such a case, the amount of pre-read data is large, but the data that is really necessary for the processor is small, and the performance is reduced. Therefore, comparing the cache hit rate with the disadvantage of increasing the data transfer amount, if the disadvantage of increasing the data transfer amount is large, it is better to reduce the data transfer amount even if the cache hit ratio is somewhat sacrificed. good.

As a method of reducing the data transfer amount, the following method is considered. The tag information accompanying the block data of the prefetch buffer is provided independently of the block data of the prefetch buffer. Then, even when the block data in the prefetch buffer is erased, the tag information held independently of the block data is left. Then, when prefetching for an arbitrary block occurs, it is possible to judge only by using the prefetch tag whether to prefetch in the upper direction or to prefetch in the lower direction.

When a tag is attached to a block as in the above-described second embodiment, a block in the upper or lower direction is always brought at the time of a cache miss. However, if an independent tag is provided, information on the direction of the tag may remain even in the case of a cache miss. If direction information remains in the tag, it is possible to prefetch only the direction described in the tag by referring to the information. In this way, the amount of pre-reading can be reduced, and the amount of data transfer can be reduced.

FIG. 8 shows a configuration of a prefetch buffer and a prefetch tag according to the third embodiment of the present invention. FIG. 8A shows a look-ahead buffer, in which a valid / invalid flag, a block address,
It is composed of data.

FIG. 8B shows a look-ahead tag, which is composed of a valid / invalid flag, a block address, and a direction (U / D). The prefetch tag exists independently of the block data of the prefetch buffer, and remains after the block data of the prefetch buffer is erased.

When the prefetch buffer and the prefetch tag are configured as in the third embodiment of the present invention, the operation of the configuration shown in FIG. 7 is as follows. The operation from the generation of an access request to the main memory by the processor, the conversion of the request address to the block address by the control unit, and the search of the cache array and the prefetch buffer are the same as those in FIG. In the third embodiment, it is checked not only whether the requested block address is registered in the cache array and the prefetch buffer, but also whether the requested block address is registered in the prefetch tag. The cache array, the prefetch buffer, and the prefetch tag can be searched simultaneously.

If the data corresponding to the requested block address has already been stored in the cache array, the control unit reads the data from the prefetch buffer and transfers the data to the cache array, as in the above-described embodiment. And returns it to the processor as a result of the access request.

If the data corresponding to the requested block address is not in the cache array but is stored in the prefetch buffer, the control unit transfers the data from the prefetch buffer to the cache array, and transmits the result of the access request to the processor. As

If the data corresponding to the requested block address is neither in the cache array nor in the prefetch buffer, the prefetch control unit issues a data read request to the main memory and stores the returned result in the cache array. Sends the result of the access request to the processor.
In this case, prefetching is further performed.

The prefetching is performed according to the inspection result of the prefetch tag regardless of the inspection result of the data corresponding to the requested block address. The control unit performs the following operation according to the search result of the look-ahead tag.

(1) When the requested block address is registered in the look-ahead tag, the following operation is performed depending on the content in the tag direction. Only the block whose direction is higher is prefetched and stored in the prefetch buffer. At the same time, the pre-read block address is registered in the pre-read tag, and the direction is U.

Only the block whose direction is lower is prefetched and stored in the prefetch buffer. At the same time, the pre-read block address is registered in the pre-read tag, and the direction is set to D. (2) If the requested block address is not registered in the prefetch tag, the data of the upper and lower block addresses are prefetched and stored in the prefetch buffer, the prefetched block address is registered in the prefetch tag, and the upper block address is registered. Is U, and the direction of the lower block address is D.

In the third embodiment, the number of tag columns can be increased from the number of prefetch buffer columns by making the tags independent of the prefetch buffer. In that case, even after the data has disappeared from the prefetch buffer, only the tag information can be left, and even in the case of a cache miss, block data in only an appropriate direction can be prefetched.
Therefore, the amount of data transfer between the main memory and the cache memory device can be suppressed.

FIGS. 9 and 10 are flowcharts showing the operation of the third embodiment of the present invention. FIG. 9 shows the overall operation.
FIG. 10 is a flowchart of the prefetch unit. The flowchart of FIG. 9 will be described.

S1, S2 Check if the requested block already exists in the cache array. S3, S4 If the determination result in S2 does not exist, it is checked whether the requested block already exists in the prefetch buffer.

If the determination results in S5 and S4 exist, the data in the prefetch buffer is transferred to the cache array. S6 Erase the requested block in the prefetch buffer.

S7 If the search result of S4 does not exist, the requested block,
Requests data transfer of upper block and lower block. S8 If the determination result in S2 exists, the access result is sent to the processor.

S9 The process of the prefetch unit is performed (see FIG. 10). A flowchart of the prefetch unit according to the third embodiment in FIG. 10 will be described. S21, S25 Check whether the requested block already exists in the cache array.

S23 If the judgment result in S22 does not exist, the data of the upper block and the lower block are pre-read. S24 Attach a direction tag of U to the upper block and a direction tag of D to the lower block, and store them in the prefetch tag.

S25, S26 The direction is checked in S25,
If it is in the lower direction (D), the data of the lower block is prefetched in S26. S27 Attach a direction tag of D to the lower block and store it in the look-ahead tag.

S28 If the direction check in S25 is the upper direction (U), the data in the upper direction is prefetched. S29 Attach a U direction tag to the upper block and store it in the prefetch tag.

FIG. 11 shows a look-ahead buffer and look-ahead tags according to the fourth embodiment of the present invention. In the case of having a prefetch tag as in the third embodiment of the present invention, it is necessary to have a block address in both the prefetch buffer and the prefetch tag. This has the same block address in two places, which is wasteful. However, it is possible to have a look-ahead tag independently, to have a tag in a look-ahead buffer, and to have a tag information in a look-ahead buffer. Do well. In this way, the waste of having two block addresses can be eliminated.

As shown in FIG. 11A, the prefetch buffer according to the fourth embodiment has a direction tag (U / D) in addition to a valid / invalid flag, a block address, and data. Further, it has a look-ahead tag as shown in FIG.

The device configuration of the fourth embodiment of the present invention is the same as that of FIG. The fourth embodiment operates as follows. The operations from generating a memory address in the processor, converting the access request into a block address in the control device, and searching for the cache array, prefetch buffer, and prefetch tag are the same as those in the third embodiment of the present invention. In addition, the cache array, the prefetch buffer, and the prefetch tag can be searched at the same time as in the third embodiment. further,
When the data of the request address is already stored in the cache array, the prefetch control unit reads the data from the cache array and returns the data to the processor as a result of the access request, similarly to the third embodiment of the present invention.

If the data corresponding to the requested block address is not in the cache array but is in the prefetch buffer, the control device performs the following four operations. 1. The data is read from the prefetch buffer and copied to the cache array.

At the same time as 2.1, the data read from the prefetch buffer is returned as a result of the access request. 3. Further prefetching is performed according to the state of the tag (direction) of the prefetch buffer.

If the state of the direction is U, a request is made to the main memory for data corresponding to a higher block address as prefetch data. If the state of the direction is D, data corresponding to a lower block address is requested to the main memory as prefetch data.

After the steps 1, 2, 3 are completed, the data corresponding to the requested block address is erased from the prefetch buffer, and the block address and tag information registered in the prefetch buffer are simultaneously held in the prefetch tag. .

If there is no data corresponding to the requested block address in the cache array or the prefetch buffer, data is read from the main memory. Further, the prefetch buffer and the prefetch tag are checked, and the following operation is performed.

(1) When the requested block address is registered in the look-ahead tag, if the direction is U according to the contents of the direction of the tag, only the upper block is prefetched and stored in the prefetch buffer. Further, U is registered as direction information in the tag storage portion of the prefetch buffer.

If the direction is D, only the lower block is prefetched and stored in the prefetch buffer. Further, D is registered as direction information in the tag storage portion of the prefetch buffer. (2) If the requested block address is not registered in the prefetch tag, the upper and lower blocks are prefetched and stored in the prefetch buffer.

Further, U is registered in the upper block and D is registered in the lower block as direction information in the tag storage portion of the prefetch buffer. FIG. 12 shows the entire operation of the fourth embodiment of the present invention. The flowchart of the prefetch unit according to the fourth embodiment of the present invention is the same as the flowchart of the prefetch unit (FIG. 10) of the third embodiment.

The overall flowchart of FIG. 12 will be described. S1, S2 Check if the requested block already exists in the cache array.

S3, S4 If the judgment result in S2 does not exist, it is checked whether the requested block already exists in the prefetch buffer. S5 If the determination result in S4 exists, the data in the prefetch buffer is transferred to the cache array.

S6 The direction inspection is performed. If D, the process of S7 is performed, and if U, the process of S9 is performed. S7 Pre-read the data of the lower block.

S8 The prefetched data is stored in the prefetch buffer, and D is registered in the tag storage portion as direction information. S9 The data of the upper block is pre-read.

S10 The prefetched data is stored in the prefetch buffer, and U is registered as direction information in the tag storage portion. S11 Erase the requested block in the prefetch buffer.

S12 The access result is sent to the processor. S13 If there is no search result in S4, a request is made to the main memory for data transfer of the requested block.

S14 If the judgment result in S2 exists, the access result is sent to the processor. S15 The process of the prefetch unit is performed (see FIG. 10).

The operation of the part (prefetch unit) for searching for the prefetch tag and determining the block to be prefetched according to the fourth embodiment is the same as that of FIG. 10, and therefore the description is omitted. As described above, the tag can be held efficiently by having the tag in both the prefetch buffer and the prefetch tag.

FIG. 13 shows a fifth embodiment of the present invention. Embodiment 5 of the present invention is a method for further reducing the data transfer amount of each of the above embodiments. It has a look-ahead tag as in the above-described third or fourth embodiment. The prefetch buffer may not have the tag information as in the third embodiment, and the prefetch buffer may also have the tag information as in the fourth embodiment. In the fifth embodiment, prefetching is not performed immediately at the time of a cache miss. Instead, it records information indicating that it should have been prefetched. In a later memory access, when an access request is made to the block that should have been prefetched, the block is prefetched based on the prefetch information.

FIG. 13A shows a look-ahead tag according to the fifth embodiment. If the data corresponding to the requested block address is not in the look-ahead buffer, the control unit checks whether the block is registered in the look-ahead tag. The following operation is performed according to the contents. Hereinafter, the requested block address is represented as ADR.

(1) If ADR is not registered in the look-ahead tag, register ADR + 1 as direction U and register ADR-1 as direction D (ADR + 1 in the block address column of direction flag U, block address of direction flag D). ADR-1). (2) If the ADR is registered in the look-ahead tag, look at its contents. If the direction is U, read data corresponding to ADR + 1 from the main memory and store it in the look-ahead buffer. Let U be the direction tag of the prefetch buffer.

If the direction is D, data corresponding to ADR-1 is read from the main memory and stored in the prefetch buffer. The direction tag of the prefetch buffer is D. (3) Thereafter, the column corresponding to the block address requested from the prefetch tag is deleted. FIG. 13B is a flowchart in a case where data corresponding to the requested block address is not in the prefetch buffer. Only the prefetch part is shown. The entire flowchart is common to FIG.

With the above operation, even if a cache miss occurs, read-ahead is not performed once, but read-ahead is performed only when an access occurs to a next adjacent block. Therefore, prefetching is started only when there is a tendency to operate continuously, so that transfer between the main memory and the cache memory can be performed efficiently.

S1, S2 It is checked whether the requested block already exists in the look-ahead tag. S3 In the inspection in S2, if there is not, in S3, ADR + 1 is registered in the pre-read tag if it is in the upper direction, and ADR-1 is registered in the lower direction if it is in the lower direction.

If it exists in the S2 inspection, if it is the lower direction (D) in the direction inspection, the process of S5 is performed, and if it is the upper direction (U) in the direction inspection, the S356 process is performed. S5 Pre-read the data of the lower block.

S6 The data of the upper block is prefetched. FIG. 14 shows a sixth embodiment of the present invention. The sixth embodiment of the present invention performs prefetching only when c or more adjacent blocks in the same direction are successively accessed.

FIG. 14A shows an embodiment of a look-ahead tag for that purpose. Record the depth k in the look-ahead tag. k is the number of successive accesses to adjacent blocks in the same direction. If the depth k is equal to or smaller than a certain number c, prefetching is not performed, the address of the next adjacent block is registered in a prefetch tag, and the depth is set as k + 1. If the depth k is equal to or more than the predetermined number c, the contents of the tag are inspected, and if the contents in the direction of the tag are U, a higher-order block is prefetched. If the content of the tag direction is the lower direction D, the lower block is prefetched.

In this way, the processor moves upward,
In the lower direction, prefetching is performed only when continuous access is performed over a certain number of blocks. By doing so, the overall cache hit rate slightly decreases, but only the blocks that are likely to be cache hits are prefetched, and the amount of unnecessary data transfer between the main memory and the cache memory is reduced. be able to.

The structure of the prefetch buffer according to the sixth embodiment is the same as that of the fifth embodiment of the present invention. As shown in FIG. 14A, depth information k is added to the prefetch tag. The operation of the sixth embodiment is the same as that of the fifth embodiment except that there is no data in the prefetch buffer.

When the data corresponding to the requested block address is not in the prefetch buffer, the control unit checks whether the corresponding block is registered in the prefetch tag. The following operation is performed according to the contents.

(1) If ADR is not registered in the look-ahead tag, ADR + 1 is set as [direction U, depth 1], and
ADR-1 is registered as [direction D, depth 1]. (2) If the ADR is registered in the look-ahead tag, look at its contents. (A) If the depth k of the ADR is less than a certain value c, if the direction is U, set ADR + 1 to [direction U, depth k +
1] is registered in the pre-read tag.

If the direction is D, ADR-1 is registered in the look-ahead tag as [direction U, depth k + 1]. (B) If the depth k of the ADR is equal to or greater than a certain value c, if the direction of the ADR is U, read data corresponding to ADR + 1 from the main memory and store it in the prefetch buffer. Let U be the direction tag of the ADR + 1 look-ahead buffer.

If the direction is D, data corresponding to ADR-1 is read from the main memory and stored in the prefetch buffer. The direction tag of the prefetch buffer is D. If the direction of ADR is D, data corresponding to ADR-1 is read from the main memory and stored in the prefetch buffer. Let D be the direction of the tag in the ADR-1 look-ahead buffer.

(3) Thereafter, the column corresponding to the block address requested from the prefetch tag is deleted. FIG.
FIG. 9B is a flowchart in the case where data corresponding to the requested block address is not in the prefetch buffer. Only the prefetch part is shown. The entire flowchart is common to FIG.

According to the above operation, even if a cache miss occurs or a certain number of cache misses occur, prefetching is performed from the next time without performing prefetching. Is started, the transfer between the main memory and the cache memory can be performed efficiently.

The flowchart of FIG. 14B will be described. S41, S42 It is checked whether the requested block already exists in the look-ahead tag.

S43: In the inspection in S42, if there is not, if it is determined in S43 that the pre-read tag is in the upper direction, ADR +
1 in [direction U, depth k + 1], and ADR-1 in [direction D,
Depth k + 1] is registered in the look-ahead tag.

S47, 48 The depth k is checked. If k ≧ c, the process of S44 is performed, and if k <c, the process of S49 is performed. S44, S45 If the direction check is the lower direction (D),
Read ahead the data in the lower block.

S44, S46 If the direction check indicates the upper direction (U), the data of the upper block is pre-read. S49, S50 If the direction check is the lower direction (D),
ADR-1 is registered in the look-ahead tag as [direction D, depth k + 1].

S49, S51 If the direction check indicates the upper direction (U), ADR + 1 is added to the pre-read tag [direction U,
Depth k + 1].

[0134]

According to the present invention, the cache hit rate is improved, and the access time of the main memory can be reduced. It is possible to reduce the amount of data transfer between the main memory and the cache memory due to prefetching.
Therefore, according to the present invention, a highly efficient cache memory device in which the access time to the main memory is apparently short can be realized.

[Brief description of the drawings]

FIG. 1 is a diagram showing a basic configuration of the present invention.

FIG. 2 is a diagram illustrating an example of a device configuration according to the first and second embodiments of the present invention.

FIG. 3 is a diagram illustrating a cache array and a prefetch buffer according to the first embodiment of the present invention.

FIG. 4 is a diagram showing a flowchart of the first embodiment of the present invention.

FIG. 5 is a diagram illustrating a prefetch buffer according to a second embodiment of the present invention.

FIG. 6 is a diagram showing a flowchart according to the second embodiment of the present invention.

FIG. 7 is a diagram illustrating an example of a device configuration according to Embodiments 3, 4, 5, and 6 of the present invention.

FIG. 8 is a diagram illustrating a prefetch buffer and a prefetch tag according to the third embodiment of the present invention.

FIG. 9 is a diagram showing a flowchart (entire) of a third embodiment of the present invention.

FIG. 10 is a diagram showing a flowchart (look-ahead unit) according to a third embodiment of the present invention.

FIG. 11 is a diagram illustrating a prefetch buffer and a prefetch tag according to the fourth embodiment of the present invention.

FIG. 12 is a view showing a flowchart (entire) of a fourth embodiment of the present invention.

FIG. 13 is a diagram showing a fifth embodiment of the present invention.

FIG. 14 is a diagram showing a sixth embodiment of the present invention.

FIG. 15 is a diagram illustrating a computer system including a conventional cache memory.

[Explanation of symbols]

 1: Processor 2: Cache memory device 3: Cache memory 4: Cache controller 5: Control unit 6: Cache hit determination unit 7: Data read unit 8: Lower block read unit 9: Upper block read unit 10: Main memory

Claims (3)

[Claims] 1. A cache memory which retains a part of the contents of a main memory and exchanges data with a processor instead of the main memory, based on a request address which is an address for which an access request is made from the processor. A cache memory device for reading and holding data of an upper address and a lower address of the request address when prefetching data from the main memory. 2. A tag information indicating whether prefetched data to be prefetched and held is an upper address or a lower address of a request address is added. When an access request is made to the prefetched data, the tag information is When the tag information indicates the upper address, the data of the upper address is prefetched based on the request address. When the tag information indicates the lower address, the data of the lower address is prefetched based on the request address. 2. The cache memory device according to claim 1, wherein the cache memory device holds the cache memory. 3. The apparatus according to claim 2, wherein a value k representing the number of times of access requests has been recorded in arbitrary tag information, and prefetching is performed in accordance with the tag information when the value of k exceeds a predetermined value c. 3. A cache memory device according to claim 1.