JP2002268943A - Cache memory device - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To make it easy to record data that has been evicted from a cache memory or data that has been invalidated by an invalidation request from another processor in the cache memory, thereby enabling the cache memory to be effective. Enhance the nature. Kind Code: A1 A conventional cache unit including a plurality of entries in which a data portion for recording data and a tag portion for recording the address and state of the data are paired, and only a tag portion having no data portion. And a data-less cache unit composed of a plurality of entries. Data is recorded in an empty entry of the conventional cache unit based on information recorded in the data-less cache unit.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] The present invention relates to a cache memory device. A normal cache memory is composed of an entry in which a data portion for recording a data value and a tag portion for recording an address and a state of the data are paired.
In particular, the present invention relates to a cache memory device which has an area (data-less cache) composed of only an entry including a tag portion having no data portion to enhance the effectiveness of the cache memory.

[0002]

2. Description of the Related Art In general, a cache memory is located between a processor and a main memory, and among data recorded in the main memory, data used by the processor in the past is recorded, and the processor uses the data. Transfer the data to the processor instead of the main memory. Since the cache memory has a smaller capacity but a higher speed than the main memory, data transfer to the processor can be completed in a short time. Therefore, if the data is recorded in the cache memory and the data can be transferred from the cache memory, the data waiting time of the processor can be reduced as compared with the case where the data is transferred from the main memory, and the processing time can be reduced. Performance can be improved.

In order to effectively use the capacity of the cache memory, data recorded in the cache memory is LRU
(Least Recently Used) system or a system similar thereto is often used. The LRU method is a method based on an empirical rule that recently used data is more likely to be used again in the near future than data that is not so. Since the cache memory has a smaller capacity than the main memory, it is often impossible to newly record data without deleting already recorded data. In this case, data having the lowest LRU priority is evicted from the cache memory, and new data is recorded in the cache memory as data having the highest LRU priority. FIG. 8 shows a state in which new data is recorded in the cache memory.

In a parallel computer, since it is necessary to maintain consistency between cache memories of each processor, cache memories are generally managed according to a rule called a coherence protocol. Coherence protocols are roughly classified into an update type and an invalidation type, and an invalidation type is often used. In the invalidation type, when data is shared between processors, when a certain processor updates the data, it is necessary to invalidate the corresponding data recorded in the cache memory of another processor. Therefore, when the other processor accesses the corresponding data later, a cache miss occurs because the data is invalidated in the cache memory of the other processor.

[0005]

[Problems to be Solved by the Invention] Regarding data that is evicted from the cache memory: When recording new data in the cache memory, if there is no empty entry for recording the data, the LRU priority is the lowest among the data already recorded in the cache memory. Data is evicted from cache memory. Thereafter, access to the data evicted from the cache memory results in a cache miss because the data is not recorded in the cache memory, and data transfer from the main memory is required. As shown in FIG. 9, even if a space for recording data in the cache memory is vacant due to some event (for example, an invalidation request from another processor), data that has been evicted from the cache memory returns to the cache memory. Therefore, an access to the data is a cache miss.

As a method of rescuing data that has been evicted from the cache memory, there is victimcache.
The victim cache is a buffer for recording data evicted from the cache memory, but since the capacity is smaller than that of the cache memory, the victim cache is used.
The time during which data is recorded in the ache is short. Therefore, unless the access to the data occurs in a short time, the data is also expelled from the victim cache, and the subsequent access to the corresponding data is a cache miss.

[0007] 2. Data to be invalidated by an invalidation request from another processor: As shown in FIG.
Consider the case where c and d) are shared. Assume that the processors are connected by a shared bus, and an invalidation type is adopted as a cache coherent protocol.

When the processor a issues a request for invalidating the data A to the other processors b, c and d in order to update the data A, the other processors b, c and d receive the request,
The data A recorded in the cache memory is invalidated (erased). Thereafter, it is assumed that data A is accessed in the order of the processors b, c, and d.

I. When the processor b accesses the data A, a cache miss occurs because the data A is not recorded in the cache memory of the processor b, and data transfer from the main memory (or another cache) is required.

Ii. Next, when the processor c accesses the data A, the data A is recorded in the cache memory of the processor c because the access to the data A of the processor b which occurred earlier does not affect the cache memory of the processor c. Since it is not performed, a cache miss occurs, and data transfer from the main memory is required.

Iii. Next, when the processor d accesses the data A, the previous access of the processors b and c to the data A has no effect on the cache memory of the processor d. Is not recorded, a cache miss occurs, and data transfer from the main memory is required. The number of cache misses is one for each of the processors b, c, and d. However, from the viewpoint of the entire system, three cache misses occur for the same data.

As a method of relieving this, there is a method of providing an external shared memory between the cache memory and the main memory. FIG. 11 shows this system configuration. According to this method, the access of the processor b to the data A does not matter. However, since the access records the data A in the external shared cache, the subsequent access of the processors c and d to the data A is performed by the external shared cache memory. To hit. Since the operation of the external shared cache memory is faster than that of the main memory, the data transfer time can be shortened. However, as compared with the case where the cache memory is hit, it takes too much time as before.

[0013]

In order to solve the above-mentioned problem, according to the present invention, a region (conven) constituted by a pair of entries of a data portion and a tag portion is provided.
area (d) in addition to an entry of only a tag portion having no data portion in addition to the data portion (d.
(cache-data cache).

FIG. 1 is a block diagram showing the principle of the present invention.
nventional cache 1 and data-les
1 shows a cache memory device including an s-cache 2.

1. Regarding data to be evicted from the cache memory: According to this method, when data is evicted from the cache memory (conventional cache), the address and state of the data are changed to d.
Recorded in the data-less cache, for example,
By issuing a prefetch based on the information (address) recorded in the data-less cache when a free space is generated in the conventional cache, data evicted from the cache memory can be returned to the cache memory again. .

FIG. 2 is a diagram showing the effect of the present method. The conventional cache in FIG. 2 is a 4-way set-associati controlled by the LRU method.
ve cache memory.

I. Data A, B, C, and D are recorded in the conventional cache.

Ii. When access to data E occurs,
The data A having the lower LRU priority is evicted and the data E c
Record in the initial cache. At the same time, the information of the tag portion of the entry of the data A that has been evicted is recorded in the data-less cache.

Iii. When another processor issues a data E invalidation instruction, the data E is invalidated (erased).

Iv. The address (address of data A) recorded in the data-less cache due to the vacancy in the conventional cache.
Issues a prefetch to The obtained data (data A) is recorded in the conventional cache.

V. When an access to the data A occurs, the data A has returned to the cache memory, so that a cache hit occurs. In the conventional method, an access to data once evicted from the cache memory is a cache miss. (See FIG. 9) However, according to this method, as described above, data-l
By issuing a prefetch based on the information recorded in the ess cache, the evicted data can be returned to the cache memory, so that an access to the data evicted from the cache memory can be a cache hit.

2. Data Invalidated by Invalidation Request from Other Processor: FIG. 3 shows a configuration example of a bus-coupled parallel computer to which the present invention is applied. According to this method, when data is invalidated from another processor,
Data address and state of the data
Recorded in the cache, for example, if another processor d
When data at the address recorded in the data-less cache is transferred, the data is obtained by taking advantage of it,
By recording in the conventional cache, invalidated data can be returned to the cache memory.

FIG. 4 is a diagram showing the effect of the present method.

I. The four processors a, b, c, and d share the data A (convention of each processor)
Data A is recorded in the nal cache).

Ii. When processor a issues a request to invalidate data A to update data A, processor b,
c and d invalidate the data A recorded in the conventional cache, and record information (address) of the tag portion of the data A in the data-less cache.

Iii. When the processor b accesses the data A, a cache miss occurs because the data A is not recorded in the conventional cache, and the data is transferred from the main memory (or another cache memory). The processors c and d detect that data coincident with the address recorded in the data-less cache is transferred, take advantage of this data transfer to obtain data A, and record the data A in each of the conventional caches.

Iv. Next, when the processor c accesses the data A, a cache hit occurs because the data A is recorded in the conventional cache of the processor c by the data transfer of the processor b.

V. Next, when the processor d accesses the data A, a cache hit occurs because the data A is also recorded in the conventional cache of the processor d by the data transfer of the processor b.
In the conventional method, access to data invalidated in the cache memory results in a cache miss (see FIG. 10). However, according to this method, as described above,
By obtaining data by taking advantage of data transfer by another processor, access to invalidated data can be made a cache hit.

[0029]

DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be described below with reference to embodiments.

FIG. 5 is a diagram showing the configuration of the cache memory device 10 of the first embodiment according to the present invention. The cache memory device 10 is an area for recording an entry in which a tag part and a data part are paired.
It is composed of a nal cache 11, a data-less cache 12 which is an area for recording only the tag part of the entry, and a cache controller 13 which is a part for controlling the cache memory. The cache controller 13 includes a control management unit 14, a prefetch control unit 1
5, a processor interface (IF) section 16 and a bus interface (IF) section 17. The cache memory device 10 has a processor interface (I
F) is connected to a processor 18 via a section 16 and a system bus 19 is connected via a bus interface (IF) section 17.
It is connected to the. Cache memory device 1 shown in FIG.
The operation of 0 is as follows. (Operation 1) When data is evicted from the conventional cache 11, the address and the state recorded in the tag portion of the relevant data entry are stored in the data-
The information is recorded in the corresponding entry of the less cache 12. (Operation 2) When a free space is generated in the entry of the conventional cache 11, a prefetch for the address recorded in the corresponding entry of the data-less cache 12 is issued, and the obtained data is c.
The information is recorded in the empty entry of the overhead cache 11. Issuance of prefetch is controlled by the prefetch control unit 15.

By operating as described above, the cache memory device 10 of the present embodiment transfers the data evicted from the cache memory (conventional cache 11) once again to the cache memory (convv).
It can be recorded in the central cache 11).

Regarding the operation 1, it is also possible to adopt a method of determining whether or not to record the data in the data-less cache 12 according to the address and the state of the operation target data.

Regarding the operation 2, it is also possible to adopt a method of determining whether or not to issue a prefetch in accordance with the address and state of the operation target data, the free state of the conventional cache 11, and the like.

FIG. 6 is a diagram showing the configuration of the cache memory device 10 according to the second embodiment of the present invention. The cache memory device 10 is an area for recording an entry in which a tag portion and a data portion are paired.
Tional cache 11, data-less cache 1, which is an area for recording only the tag portion
2. It is composed of a cache controller 13 which controls the cache memory. The cache controller 13 includes a control management unit 14, a bus monitoring unit 2
0, a processor interface (IF) unit 16, and a bus interface (IF) unit 17. The cache memory device 10 has a processor interface (I
F) is connected to a processor 18 via a unit 16 and a system bus 19 is connected via a bus interface (IF) unit 17.
It is connected to the. Another processor node 21 is connected to the system bus 19. The operation of the cache memory device 10 shown in FIG. 6 is as follows. (Operation 1) In response to an invalidation request from another processor connected to the system bus 19,
When invalidating the data recorded in the l-cache 11, the address and the state recorded in the tag portion of the data entry are stored in the data-less cache 12.
Record in the corresponding entry. (Operation 2) The bus monitoring unit 20 monitors a signal on the system bus 19, and the address of a request issued to the system bus 19 by another processor matches the address recorded in the data-less cache 12. At this time, the data is obtained by piggybacking at the time of data transfer of the corresponding request, and is recorded in the conventional cache 11.

By operating as described above, the cache memory device 10 of this embodiment replaces the data once invalidated in the cache memory (conventional cache 11) again with the cache memory (convene).
It can be validated by the central cache 11).

Regarding the operation 1, depending on the type of request issued by the other processor, the type of response to the request, whether or not the conventional cache 11 has a certain amount of free space, etc.
A method of deciding whether to record data in the online cache 11 or not can be adopted.

FIG. 7 is a diagram showing a configuration of the cache memory device 10 according to the third embodiment of the present invention. The cache memory device 10 is an area for recording an entry in which a tag portion and a data portion are paired.
Tional cache 11, data-less cache 1 which is an area for recording an entry of only a tag portion
2. It is composed of a cache controller 13 which controls the cache memory. The cache controller 13 includes a control management unit 14, a request conversion unit 22, a processor interface (IF) unit 16, and a bus interface (IF) unit 17. The cache memory device 10 is connected to a processor 18 via a processor interface (IF) unit 16 and to a system bus 19 via a bus interface (IF) unit 17. Another processor node 21 is connected to the system bus 19. The operation of the cache memory device 10 shown in FIG. 7 is as follows. (Operation 1) When data is evicted or invalidated from the conventional cache 11, the address and state recorded in the tag portion of the data entry and the reason for evicting (Evicted)
or Invalidated) to data-less
The information is recorded in the corresponding entry of the cache 12. (Operation 2) When a processor makes a read access to an address recorded in the data-less cache 12 and whose state is "Modified" and whose eviction reason is "Invalidated", the system is normally operated. Although a read request is to be issued to the bus 19, an exclusive read request is issued instead.

When updating data, the system bus 19
In most cases, a read request is issued to the system bus 19, followed by an invalidation request to the system bus 19. In this case, there are two requests issued to the system bus 19. When the cache memory device 10 of the present embodiment is used, a read request for data that is likely to be updated (that has been updated in the past) is sent to the system bus 19 as an exclusive read request. There is no need to issue an invalidation request to the system bus 19. That is, the number of requests issued to the system bus 19 can be reduced.

Each of the first to third embodiments shown in FIGS. 5 to 7 has a prefetch control unit 15, a bus monitoring unit 20, and a request conversion unit 22, respectively. A configuration that combines any two functions of
Alternatively, a configuration having all three functions can be appropriately adopted as needed.

(Supplementary Note 1) A first cache unit composed of a plurality of entries including a pair of a data portion for recording data and a tag portion for recording the address and state of the data, and a data portion A cache memory device comprising: a second cache unit including a plurality of entries including only a tag unit without including the tag unit.

(Supplementary Note 2) When the data recorded in the first cache unit is evicted, all or a part of the information recorded in the tag unit of the entry is transferred to the second cache unit. 3. The cache memory device according to claim 1, wherein the data is recorded in a cache memory.

(Supplementary Note 3) When the data recorded in the first cache unit is evicted, the data is evicted in addition to all or a part of the information recorded in the tag unit of the entry. 2. The cache memory device according to claim 1, wherein information indicating the reason for the failure is recorded in the second cache unit.

(Supplementary Note 4) The cache memory device is used in a bus-coupling type parallel computer system, and when another processor issues a request to the bus, the access target address of the request is set to the second address. Appendix 1 characterized in that the information is recorded in the cache unit of
4. The cache memory device according to any one of claims 1 to 3, wherein

(Supplementary Note 5) When data of an address recorded in the second cache unit is obtained, the data is recorded in the first cache unit. The cache memory device according to any one of the above.

(Supplementary Note 6) A prefetch is issued to an address recorded in the second cache unit,
6. The cache memory device according to any one of supplementary notes 1 to 5, wherein the data at the address is obtained.

(Supplementary Note 7) The cache memory device is used in a bus-coupled parallel computer system, and another processor issues a bus request to an address recorded in the second cache unit. 7. The cache memory device according to any one of supplementary notes 1 to 6, wherein data is obtained by piggybacking at the time of data transfer of the bus request.

(Supplementary Note 8) The cache memory device is used in a bus-coupled parallel computer system, and is used when an address recorded in the second cache unit is accessed from a processor. 8. The cache memory device according to claim 1, wherein a type of the request to be sent to the bus is determined according to information recorded in an entry of the address.

(Supplementary Note 9) When an access from the processor to an address recorded in the second cache unit occurs, a new access is made in accordance with the information recorded in the entry of the address. The first
9. The cache memory device according to claim 1, wherein a value of a tag portion of an entry recorded in the cache unit is determined.

(Supplementary Note 10) The cache memory device is used in a bus-coupled parallel computer system, and another processor issues a bus request to an address recorded in the second cache unit. 10. The cache memory device according to claim 1, wherein a response to the bus request is determined in accordance with information recorded in an entry of the address.

(Supplementary Note 11) As information indicating the reason why the data recorded in the first cache unit was evicted, information based on the capacity of the cache and information based on an invalidation request from another processor are included. 4. The cache memory device according to claim 3, wherein

(Supplementary Note 12) When a read access from the processor to an address recorded in the second cache unit occurs, the state of the information recorded in the entry of the address is changed to “Modify”.
9. The cache memory device according to claim 8, wherein when the eviction is "d" and the reason for eviction is "Invalidated", an exclusive read request is issued to the bus instead of the read request.

[0052]

According to the cache memory device of the present invention, an access to data that has been evicted from a cache memory that causes a cache miss in the conventional method or data that has been invalidated from the cache memory due to an invalidation request from another processor can be performed by a cache hit. Can be Specifically, a data-less cache that records a tag portion of data that has been recorded in the cache memory in the past is introduced, and data is stored in a free entry of the cache memory based on information recorded in the data-less cache. Record. As a result, the capacity of the cache memory can be used more effectively, and as a result, the system performance improves.

[Brief description of the drawings]

FIG. 1 is a principle configuration diagram of the present invention.

FIG. 2 is a diagram showing access to data evicted from a cache memory in the present invention.

FIG. 3 is a diagram illustrating a configuration example of a bus-coupled parallel computer to which the present invention is applied;

FIG. 4 is a diagram showing access to invalidated data in the present invention.

FIG. 5 is a diagram illustrating a configuration of a cache memory device according to a first embodiment of the present invention;

FIG. 6 is a diagram showing a configuration of a cache memory device according to a second embodiment of the present invention.

FIG. 7 is a diagram showing a configuration of a cache memory device according to a third embodiment of the present invention.

FIG. 8 is a diagram showing a state when new data is recorded in a cache memory.

FIG. 9 is a diagram showing access to data that has been evicted from the cache memory.

FIG. 10 is a diagram showing access to invalidated data.

FIG. 11 is a diagram illustrating a configuration example of a computer system having an external shared cache memory.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 conventional cache 2 data-less cache 10 cache memory device 11 conventional cache 12 data-less cache 13 cache controller 14 control management unit 15 prefetch control unit 18 processor 19 system bus 20 bus monitoring unit 22 request conversion unit-

Claims (10)

[Claims] A first cache unit including a plurality of entries including a pair of a data unit for recording data and a tag unit for recording an address and a state of the data, and excluding a data unit. And a second cache unit including a plurality of entries including only a tag unit. 2. When the data recorded in the first cache unit is evicted, all or a part of the information recorded in the tag unit of the entry is recorded in the second cache unit. 2. The method according to claim 1, wherein
3. A cache memory device according to claim 1. 3. When data recorded in the first cache section is evicted, the data is evicted in addition to all or a part of information recorded in a tag section of the entry. The information indicating the reason is recorded in the second cache unit.
3. A cache memory device according to claim 1. 4. The cache memory device is used in a bus-coupled parallel computer system,
4. The cache memory device according to claim 1, wherein when another processor issues a request to the bus, an access target address of the request is recorded in the second cache unit. . 5. The method according to claim 1, wherein when data of an address recorded in said second cache unit is obtained, said data is recorded in said first cache unit. The cache memory device according to any one of the above. 6. The apparatus according to claim 1, wherein a prefetch is issued to an address recorded in the second cache unit, and data at the address is obtained. Cache memory device. 7. The cache memory device is used in a bus-coupled parallel computer system,
2. The method according to claim 1, wherein when another processor issues a bus request to an address recorded in the second cache unit, data is obtained by piggybacking when transferring the data of the bus request. Item 7. A cache memory device according to any one of Items 6. 8. The cache memory device is used in a bus-coupled parallel computer system,
When an access from the processor to an address recorded in the second cache unit occurs, the type of request to be issued to the bus is determined according to the information recorded in the entry of the address. The cache memory device according to any one of claims 1 to 7, wherein: 9. When an access from a processor to an address recorded in the second cache unit occurs, the access newly regenerates the address in accordance with information recorded in an entry of the address. 9. The cache memory device according to claim 1, wherein a value of a tag portion of an entry recorded in the first cache unit is determined. 10. The cache memory device is used in a bus-coupled parallel computer system, and is used when another processor issues a bus request to an address recorded in the second cache unit. ,
According to the information recorded in the entry of the address,
10. The cache memory device according to claim 1, wherein a response to the bus request is determined.