JPH06100982B2 - Hierarchical cache memory device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a hierarchical cache memory device hierarchically provided between at least one processor and a main memory device.

[0002]

2. Description of the Related Art A bus-sharing tightly coupled multiprocessor, compared to other multiprocessor architectures,
It is often used in commercial parallel computers because it is easy to implement and the programming of the program to be executed is easy.

However, in such an architecture,
When the number of processors increases to some extent, the so-called bus
A bottleneck problem arises.

In order to solve this problem, conventionally, a cache memory is provided between a plurality of processors and the main memory to effectively reduce the frequency of access to the main memory and connect more processors to the bus. The method of letting is adopted.

By the way, in such an architecture, there is a problem regarding data consistency between the cache memories and between the cache memory and the main memory, that is, a so-called cache consistency problem.

As a method of guaranteeing the consistency of data, a method of guaranteeing the consistency by software and a method of guaranteeing the consistency by hardware are considered. Here, as a method using hardware, a method using a snooping cache and a directory-based method are known.

The method using the snooping cache will be described below.

In the snooping cache, the data in the cache memory is not only sent from the processor side,
It can also be accessed from the bus side. Then, in order to guarantee the consistency of data, the cache refers to / updates information called its state in addition to the data value and address in response to a request from the processor side or the bus side. Such a rule of cache response to a request from a processor or a bus is called a cache consistency protocol, and many proposals have already been made (PerStens).
trom, "Survey of Cache Coh"
erenceSchemes for Multipr
processors, "IEEE Computer 2"
3, 6 (1990), 12-24).

However, even in a bus-coupled multiprocessor having a cache memory, if the number of processors increases to some extent, a bus bottleneck becomes a problem again. This is a bus for access from the processor.
This is because, in addition to the increase in transaction frequency, the frequency of bus transactions for maintaining data consistency between the cache memory and the main memory or between the cache memories also increases.

To solve this problem, a hierarchical cache memory system has been proposed in which a new cache memory hierarchy is provided between the cache memory and the main memory to distribute and reduce the load on the bus (Andrew).
W. Wilson, Jr. , "Hierarchic
al Cache / Bus Architecture
for Shared Memory Multip
processors, "Proc. 14th Int
'L Symp. on ComputerArchi
Tecture (1987), 244-252. ).

Such a hierarchical cache memory device comprises a private cache (first
A plurality of processors that own a cache) are connected to a new cache (hereinafter referred to as a second cache) by a bus (hereinafter referred to as a cache bus) to form one cluster, and the plurality of clusters are connected to each other. It is configured by connecting to a main memory by a new bus (hereinafter referred to as a memory bus).

As the cache consistency protocol of the hierarchical cache memory device, a relatively simple control such as a write-through system and easy to implement is often adopted. In order to further reduce the
A protocol which is an extension of the consistency protocol has also been proposed (Shigehiro Asano, “Two-layer parallel cache consistency protocol,” IPSJ Computer Architecture Research Group Report 80-3 (1990), 17-2.
7).

Hierarchical cache memory devices also often impose a constraint called multi-level inclusion (MLI) to facilitate control for data consistency. The MLI is that the data in the first cache (child cache memory) always exists in the second cache of the cluster.

In a system in which MLI is guaranteed, the capacity of the second cache must be at least the sum of the capacities of the child cache memories. In other words, if the capacity of the first cache is C _f , the capacity of the second cache is C _s , and the number of child cache memories per second cache is N, then C _S > N · C _f .

For data shared by a plurality of child cache memories, the second cache secures only one entry, and the MLI is guaranteed.
Therefore, assuming that (100 × s)% of the data existing in the child cache memory is shared data, the capacity C _eff that can store the data that the child cache memory does not have in the capacity of the second cache. Is C
It is given by [N · (1-s) + s] · C f - eff = C s.

When the second cache stores data that does not exist in the child cache memory, an access to the data causes a cache miss in the child cache memory, but a cache hit in the second cache. Access to main memory and other clusters.

In order to increase the hit rate in this second cache, it is preferable that C _eff is large. C _eff
In order to increase, it is conceivable to increase C _s or increase _s . No problem if C _s is sufficiently large, it is often not possible to secure a sufficiently large C _s constraints of board or chip area.

Although s depends on the nature of the program,
It is difficult to make it larger depending on the programmer's will. Generally, in a bus-coupled tightly-coupled multiprocessor, when data sharing between processors is large (that is, when s is large), the frequency of bus transactions for guaranteeing data consistency increases. In this case, the problem of bus bottleneck occurs, and it cannot be said that the multiprocessor is effectively used.

[0019]

As described above, the conventional ML is used.
In the hierarchical cache memory device where I holds,
If the capacity of the second cache cannot be made large enough, the effect of introducing the second cache cannot be expected so much, and therefore, the second cache had to have a sufficiently large capacity, but this also varies. There was a case that a sufficiently large second cache capacity could not be secured due to the restriction of.

The present invention has been made in view of the above circumstances, and provides a hierarchical cache memory device capable of effectively utilizing the capacity of the second cache and realizing the effect of introducing the second cache. With the goal.

[0021]

SUMMARY OF THE INVENTION The present invention comprises at least one
Connect at least one first cache to each processor, connect the first cache to the first bus, and connect at least one second cache to form a cluster, A hierarchical cache memory device in which a plurality of clusters are connected to a main memory via a second bus, wherein the second cache directly connects to the second cache via the first bus. Corresponding to an entry of tag storage means for storing a tag relating to the data stored in the first cache connected thereto, a data storage means for storing a copy of the data stored in the first cache, and an entry of the tag storage means Existence storage means for storing information regarding whether or not the data to be stored secures an entry in the data storage means, the entry and the existence in the data storage means Corresponding storage means for storing information on the correspondence relationship of the entries in the storage means is provided, and when the entry corresponding to the request address in response to the request from the second bus exists in the tag storage means, the existence storage means provides the first storage means. It is determined whether or not the data exists in the cache No. 2, and if the data exists, the corresponding storage means selects an entry in the data storage means and returns the data to the request source.

When an entry corresponding to the request address for the invalidation request from the second bus exists in the tag storage means, the invalidation request is issued to the first cache and the entry in the tag storage means is invalidated. I am trying.

Further, in response to a request from the first bus, the existence storage means determines whether or not there is data in the second cache, and if there is data, the data is read / written.

Further, when an entry corresponding to the request address for the copy back request from the first bus exists in the existing storage means, the corresponding storage means selects the entry in the data storage means to update the data, A replacement algorithm that guarantees data consistency when no entry exists secures an entry in the data storage means before performing copy back, or issues a copy back request up to the second bus. ing.

[0025]

As a result, according to the present invention, when a read shared or read modified request is received via the second bus, is there an entry corresponding to the requested address in the tag storage means? Determine whether or not. When the tag exists, the existence storage unit determines whether or not the data exists in the second cache. If the data exists, the corresponding storage means selects an entry in the data storage means and returns the data to the request source. In read modified, an invalidation request is issued to the first bus if necessary. If there is no data, issue a read shared request to the first bus. On the other hand, if the tag does not exist, no data is returned.

Further, when an invalidation request is received via the second bus, it is determined whether or not the entry corresponding to the requested address exists in the tag storage means. When the tag exists, the invalidation request is issued to the first cache and the entry of the tag storage means is also invalidated if necessary according to the state. If the tag does not exist, neither the request to the processor nor the invalidation of the entry in the tag storage means is performed.

Furthermore, when a read shared or read modified request is received via the first bus, the existence storage means determines whether or not data exists in the second cache. When the data exists, the data is read or written. In read modified, an invalidation request is issued to the second bus if necessary. If there is no data, and if it is determined by the algorithm that guarantees the consistency of the data that the entry can be secured in the data storage means, the entry is secured and the read shared or read modified request is made to the second bus. Emit.

Further, when a copy back request is received via the first bus, it is determined whether or not the entry corresponding to the requested address exists in the existence storage means. If it exists, the corresponding storage means selects an entry in the data storage means to update the data. On the other hand, if there is no entry, a copy back request is made after the entry in the data storage means is secured before a copy back is made, or a copy back request is made to the second bus in accordance with a replacement algorithm that guarantees data consistency. Emit.

From these facts, the memory capacity of the second cache can be effectively used, and even when the capacity of the second cache cannot be secured sufficiently,
You will be able to realize the effect of introducing the second cache.

[0030]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 shows a hierarchical cache according to the embodiment.
1 shows a schematic configuration of a memory device. In this case, each of the plurality of processors 1 has a first cache 2
And the first cache 2 is connected to the cache bus 3, and the second cache 4 is connected as a new cache to form one cluster 5
And a plurality of rasters 5 are combined and connected to the main memory 7 by a memory bus 6 as a new bus.

Next, FIG. 2 shows a schematic structure of the second cache 4. In this case, 11 is a tag memory, 12 is a data memory, 13 is an existing memory, 14 is a corresponding memory, 15 is an interface unit on the cache bus side, 16 is an interface unit on the memory bus side, 17
Is a cache bus controller, and 18 is a memory bus controller.

Here, the cache bus controller 17 performs control for responding to a request from the cache bus of the interface section 15 and control for issuing a request to the cache bus. The memory bus controller 18 also performs control for responding to a request from the memory bus of the interface unit 16 and control for issuing a request to the memory bus. Further, the cache bus controller 17 and the memory bus controller 18 use the information stored in the tag memory 11, the existing memory 13, and the corresponding memory 14 for control.

The tag memory 11 stores a tag portion of a memory address and indicates which address the entry corresponds to. The determination of cache hit / miss is made by comparing the value of this entry with the tag portion of the memory address sent in response to the request, and checking if they match.

The tag memory 11 also represents the state of the cache block. The type and number of cache block states vary depending on the cache protocol used, but in general, whether the data in that cache block is valid or not is shared with other cache memory. It represents information such as whether it is present or not. The cache protocol used in this embodiment will be described later in detail.

Further, the tag memory 11 stores information (U bit) indicating in which child cache memory the data of this cache block exists. The second cache is intended to mitigate bus transactions on the cache bus by storing some of the information about the state of the first cache. In this embodiment, the U bits form an area of N bits per entry (N is the number of child cache memories per second cache), and each bit corresponds to a child cache memory. For example, the number of child cache memories per second cache N = 4
(In the following description of the present invention, N = 4 is taken as an example), and if the value of the U bit of a certain entry is 0101, the first digit and 3
This means that there is a copy of the data of this cache block in the first cache corresponding to the bit of the digit.

In the existing memory 13, each entry has a fixed one-to-one correspondence with the entry in the tag memory 11.
It stores information regarding whether or not the cache block reserves an entry in the data memory 12. If the entry in the resident memory 13 is one, the cache block stores a copy of the data in the entry in the data memory specified by the value of the entry in the corresponding memory 14 described below. On the other hand, the existence memory 13
If the value of the entry is 0, the cache block has not reserved the entry in the data memory 12.
In this embodiment, there are two valid cache blocks in the second cache, one is an address, a cache block in which a copy of data is stored together with a tag and a state, and the other is an address tag. A cache block in which a copy of the data is not stored, although the cache and the state are stored.

In the correspondence memory 14, each entry fixedly corresponds to the entry in the tag memory 11. It stores information about which entry in the data memory 12 an entry in the tag memory 11 corresponds to. However, when the value of the entry of the existing memory 13 is 0, the value of the entry of the corresponding memory 14 is meaningless.

The data memory 12 also existed in the conventional second cache, but in that case, the entry of the tag memory 11 and the entry of the data memory 12 had a fixed one-to-one correspondence. Therefore, there is no need for a memory corresponding to such a memory 14. The feature of the present embodiment is that the entries of the tag memory 11, the existing memory 13 and the entries of the data memory 12 do not correspond one-to-one, and the correspondence is not fixed, and according to the cache protocol described later. The point is that the correspondence changes dynamically.

The corresponding memory 14 may be realized so that each entry in the tag memory 11 can specify a correspondence with any entry in the data memory 12, but generally, the data memory 12 is used. Since the number of entries in is large, the amount of information required to specify the entry is large.
Therefore, the corresponding memory 14 requires a considerably large area.

Therefore, in this embodiment, the entries in the corresponding memory 14 are realized so that only a part of the entries in the data memory 12 can be designated. The realization of the second cache by the set associative method will be described as an example.

FIG. 3 shows the correspondence of each entry of the tag memory 11, the data memory 12, the existing memory 13, and the corresponding memory 14. In this case, tag memory 1
1, the existing memory 13 and the corresponding memory 14 use the 8-way set associative method, the data memory 12 uses the 4-way set associative method, and the number of lines is the tag
The same applies to the memory 11, the existing memory 13, and the corresponding memory 14 (the entry for one line is shown in FIG. 3). Then, when an address is accessed by the second cache, the tag memory 1
1, the existing memory 13, and the corresponding memory 14 read one line (8 entries) at the same time, and the cache hit / miss determination is stored in the address tag portion of the request target address and the tag memory 11. This is done by comparing the address tags that exist.

For example, in FIG. 3, the fourth entry from the top indicates that the cache block is NON,
Since the U bit is 0101, there is a copy of the data in the first cache corresponding to the bit for which 1 is set. Further, since the value of the entry in the existing memory 13 is 1 in this cache block, the cache block also has data, and the data exists in the entry in the data memory 12 designated by the entry in the corresponding memory 14. is doing. The entry at the top indicates that the cache block is EXC and the value 0100 of the entry of the U-bit memory indicates that data exists only in one certain first cache. Since the value of the entry in the existing memory 13 is 0, this data does not exist in the second cache.

As described above, in this embodiment, the tag
Since the correspondence between the entries of the memory 11 and the entries of the data memory 12 is not one-to-one, and the correspondence is fixed in the conventional example, in the present embodiment,
The correspondence is not fixed. First, the value of the entry of the existing memory determines whether or not it corresponds to any one of the entries in the data memory 12, and as a result, if it does, the correspondence memory 14 The value of the entry determines which entry in the data memory 12 it corresponds to.

Next, a cache consistency protocol that guarantees data consistency will be described.

In this case, for comparison, Berke first
A conventional hierarchical cache protocol obtained by extending the ley method will be described.

FIG. 4 shows a state transition diagram of the cache block of the first cache. The nodes in the drawing represent the states of cache blocks in the first cache, and the edges represent requests to the first cache. As for the subscript of the request, P represents a request from the processor and C represents a request of the cache bus. The meaning of each state is as follows. : INV: invalid, UNO: valid & u
known & shared, NON: valid
& Owned & shared, EXC: val
The cache blocks of id & owned & exclusive and the first cache have three types of attributes. validity: Whether the data of the cache block is valid (valid) or not (invalid), explicitness:
Is data shared with other caches (share
d) Whether or not (exclusive), ownershi
p: Do you have ownership of the data (owne
d) unowned (PA Swazey)
and A. J. Smith, "A Class o
f Compatible Consistency
Protocols and Support by
the IEEE Futurebus, "Proc.
13th Int'l Symp. on Comput
er Architecture (1989), 414.
-423).

Here, the fact that the cache block of the first cache shares the data means that the data is shared with another first cache, or
It means sharing data with the second cache of another cluster. Ownership is an attribute relating to whether or not copy back needs to be performed when the cache block is evicted, and a cache block having ownership must be copied back when evicted.

The fast cache receives requests from both the processor and the cache bus. Requests from the processor are read (Read _p ) and write (Wri).
te _p ) (Of course, in general, there are a plurality of types of requests, reads, and writes other than these, but since they do not affect the gist of the present invention, they are omitted). The cache bus requests are: REO: Read modified request from the first cache. RSH: Read shared request from first cache. FAI: Read modified request from second cache. FWI: Read shared request from second cache. WFI: Invalidation request. WWI: Copy back request. There is.

Next, FIG. 5 shows a state transition diagram of cache blocks of the second and cache. The nodes in the drawing represent the states of cache blocks in the second cache, and the edges represent requests to the second cache. As for the subscript of the request, C represents the request for the cache bus and M represents the request for the memory bus. The meaning of each state is as follows: INV: invalid, UNO: valid & c.
-Unowned & c-shared, NON: v
alid & c-owned & c-share
d, EXC: vaild & c-owned & c
-Exclusive, where the attributes used to distinguish the states are validity and c-exclu
There are three types: seveness and c-ownership. Whether the data is valid is valid (v
alid) Whether or not (invalid), c-exclus
The event is whether the cluster shares the data with other clusters (c-shared) or not (c
-Exclusive) and c-ownership indicate whether any of the first caches in the cluster has the latest data and whether copy back is necessary (c-owned) or not (c-owned) (Muratani). Hirofumi, "Extended MOESI Model and Parallel Hierarchical Cache Protocol," IPSJ Computer Architecture Research Group Report 89-23 (1991), 169-17
6. ).

The second cache receives requests from both the cache bus and the memory bus. The request from the cache bus is the same as for the first cache. Requests from the memory bus are: REO: Read Modified Request. RSH: Read / Shared request. WFI: Invalidation request. WWI: Copy back request. There is. Then, the responses of the second cache to these requests are as shown in FIGS. 6 and 7.
(Hereinafter, the cache bus and the memory bus are abbreviated as CB and MB respectively in the drawings. Also, ubit and eb
It represents the value of the U bit and the entry value of the existing memory. On the other hand, in the consistency protocol according to the present embodiment, the state of the cache block and the type of bus request are the same as in the conventional example, but the response of the second cache to the bus request is different.

FIGS. 8 and 9 and FIGS. 10 and 11 show responses to requests from the cache bus and memory bus, respectively.

Comparing with FIGS. 6 and 7 showing the response in the above-mentioned conventional example, the response to the request from the memory bus is the same, but there are some responses to the request from the cache bus. There are differences, and more specifically, the cases described below.

When RSH _c hits UNO.

When WWI _c hits EXC.

In any case, the value of the existing bit is judged and a different response is made depending on the judgment result.

Here, as a restriction on a cache block that does not reserve a data entry, in the conventional cache protocol, even if the cache block does not have a data entry, the child cache
It may be considered that the data may reside in any of the memories: (1) In response to a request of the memory bus, a request must be issued to the cache bus.

(2) A request must be issued to the memory bus in response to a request from the cache bus.

In these situations, the second cache determines whether or not to send the request according to the value of the entry of the tag memory, and it is not necessary to refer to the data memory.

The reason why it is better for the cache block in the NON state to have a data entry is that a cache protocol that allows a cache block having no data entry in any state can be realized. However, as the protocol becomes more complicated, the cache block replacement algorithm becomes more complicated, and bus transactions during copy back may increase significantly.

In this embodiment, restrictions are imposed on the state permitted as a cache block having no data entry. Also, the data in a cache block in the NON state must be copied back when it is evicted. A cache block in the NON state must have a data entry if the U bit is 0000. On the other hand, if the U bit is not 0000, then there is no need for a data entry to exist. This is because the data exists in any of the child cache memories.

Then, it seems that the consistency can be guaranteed by the second cache according to the state transition rule as shown in FIG. 12, but the data is lost in the following situations and it becomes difficult to guarantee the consistency. In FIG. 12, the meaning of the symbol indicating the state of the cache block is, for example, that UNO is (0, 1) in the UNO state, the U bit is 0000, and the existence bit is 1.

It is assumed that the U bit is 0010 and there is a cache block having no data entry. It is assumed that the data in this cache block is evicted in the child cache memory due to a cache miss. No copy back is performed because the cache block state in its child cache memory is UNO. Therefore, the U bit is 0000, and in the cluster,
There is no data in the child cache memory or the second cache.

In order to avoid this, when the cache block in the UNO state is evicted in the first cache, the copy back is always performed, or
It is conceivable to judge whether or not there is a copy of the data in the data in another child cache memory, and to copy back if the copy of the data does not exist. Both are not preferable because they may increase the frequency of bus transactions.

Similar examination is performed for other states. FIG. 13 shows combinations of states, U bits, and presence bits that may cause problems.

When the U bit is 0000 and the existence bit is 0 in the UNO state, there is no data in the cluster, but the tag memory entry exists. It's okay to keep the data consistent, but it wastes tag entries. It can also result in wasted transactions.

If the U bit = 0000 and the existence bit = 0 in the NON state, the data to be copied back will be lost, so this state should be prohibited.

When the U bit is 0000 and the existence bit is 0 in the EXC state, the data to be copied back is lost and should be prohibited. U bit in EXC state =
If 0000 and the existence bit = 0, it means that the data to be copied back from the first cache to the second cache has been lost and should be prohibited.

In the present embodiment, based on the above consideration, NON
State cache blocks are constrained to always have a data entry. There are two ways to implement this constraint: (1) Reserve a data entry when transitioning from EXC to NON.

(2) Reserve a data entry when transitioning to EXC.

Here, (C1) means "if the cache block is in the NON state, it has a data entry". On the other hand, (C2) means "if the cache block has ownership, it has a data entry". Other restrictions are possible as long as the protocol complexity is acceptable. (Cache block replacement algorithm) When a cache block needs to be replaced in the second cache: (A) When all tag memory entries that are candidates for replacement are used, (B) All candidate data memory entries have been used. MLI holds for tag memory entries. The number of entries in the tag memory whose U bit is not 0000 is the maximum number of entries that are mapped to the same line of the second cache in the child cache memory, but the number of entries in the second cache is in one line. It is guaranteed to have the above tag entries. Therefore, in the situation of (A), the replacement of the tag memory entry may be performed according to the conventional cache block replacement algorithm. For example, (1) selecting from the entries in the INV state. (2) If there is no entry in the INV state, select the entry whose U bit is 0000. (3) If there is no entry in which the U bit is 0000, the entry used by the requesting first cache is selected.

In the situation of (B), one of the already used data entries must be selected to secure the data entry. The data entry replacement algorithm is based on the two constraints (C1) and (C
It depends on which of 2) is adopted. Constraint (C
When 1) is adopted, the next entry is selected.

(1) Data entry not secured from any tag entry, (2) Tag in the UNO state
Data entry reserved from entry, (3)
A data entry reserved from a tag entry in the EXC state.

A cache block whose data entry is robbed by the data entry replacement algorithm sets the existence bit to 0.

As described above, it is not always guaranteed that the data entry can be secured. For example, data
When all the entries are secured by the tag entries in the NON state, the above algorithm does not need to replace only the data entry, but the entry in the tag memory is replaced.

When the constraint (C2) is adopted, the data entry of (3) above is not selected. When all the data entries are secured by the tag entries in the NON state or the EXC state, the entry in the tag memory needs to be replaced.

The cache protocols of FIGS. 8 and 9 shown above are due to the constraint (C1). FIG. 14 is a state transition diagram of cache blocks in the second cache. In this embodiment, a cache block in the NON state is guaranteed to always have a data entry. The difference from the conventional example in the following points: (1) If the RSH _C hits the UNO, to determine the presence memory entry, emit 0, RFO _M, or main other second cache Get data from memory.

(2) When WWI _C hits EXC, the entry in the existing memory is determined, and if 0, the data entry is secured according to the above replacement algorithm,
Store the copied back data there. It is also possible to copy back the copied data to the main memory as it is without securing the data entry.

(3) When RSH _M hits EXC, the value of the entry in the existing memory is determined, and if 0, the data entry is secured and the latest data from the first cache is stored therein. If 1, the latest data is stored in the already secured data entry.

(4) When RSH _M or RFO _M misses, after obtaining a copy of data from another cluster or main memory, if there is a free data entry, secure the data entry and store the data. after,
Returns data to first cache. (If the data entry cannot be secured, it is possible to always secure the data entry according to the replacement algorithm.) (5) The EXC or UNO cache block with the existence bit = 1 is selected by the replacement algorithm. Then, the data entry is released and the existence bit = 0 is set.

(6) The cache block of the UNO having the existence bit = 0 transits to INV when it is evicted from all the first caches in the cluster (when transiting to U bit = 0).

Next, the cache by the method (C2)
Describe the protocol. The response to the second cache request is shown in FIGS. Figure 10
FIG. 6 is a diagram showing a response to a request of a cache bus.
FIG. 11 is a diagram showing a response to a request from the memory bus.

FIG. 15 is a state transition diagram of cache blocks in the second cache. In this embodiment, the cache blocks in the NON state and the EXC state are guaranteed to have data entries. The difference between the conventional example in the following points: (1) If the RSH _C hits the UNO, to determine the presence memory entry, emit 0, RFO _M, other second cache or main memory Bring data from.

(2) When RFO _C or WFI _C hits UNO, after obtaining data from another cluster or main memory, the entry in the existing memory is determined,
If it is 0, the data entry is secured according to the above replacement algorithm, the data is stored therein, and the data is returned to the first cache.

(3) If RSH _M misses, after obtaining a copy of data from another cluster or main memory, if there is a free data entry, secure the data entry and store the data , Return data to first cache. (If a data entry cannot be secured, a method of always securing a data entry according to the replacement algorithm is also possible.) (4) When a cache block of UNO having an existence bit = 1 is selected by the replacement algorithm , Release the data entry and transition to presence bit = 0.

(5) A UNO cache block whose existence bit = 0 is set to all first caches in the cluster.
When it is evicted from the cache (when transitioning to U bit = 0), it transits to INV.

Next, the effect expected by the second cache of the present invention will be described.

FIG. 16 and FIG. 17 show examples of transactions frequently occurring in the memory bus when the capacity of the second cache is not sufficient in the conventional example. Addresses A1 and A2 are assumed to map to the same cache line.

FIG. 16A: A read from the processor P1 to the first cache F1 to the address A1 is performed, a cache miss occurs, and if necessary, after copying back the data of the address A2, the R is transferred to the second cache S1.
SH was emitted.

FIG. 16B: Second cache S1
The entry of the line corresponding to the requested address is occupied by the data of other addresses, and a cache miss occurs. The second cache S1 has an address A2 where data does not exist in the child cache memory.
Select the cache block of the memory, copy the data back to the main memory if necessary, and then
Issue an RSH request to 1 on the memory bus.

FIG. 16C: The returned data is stored in the selected cache block and the data is returned to the first cache F1.

FIG. 16D: First cache F
1 stores the returned data and returns the data to the processor.

FIG. 16 (e): The address A2 is accessed again, and a cache miss occurs in the first cache.

FIG. 16 (f): The second cache does not already have a cache block for storing the data of the address A2.

FIG. 17A: A data read request must be issued to the memory bus. This is because the second cache does not have enough capacity, so address A
This is because both 1 and the copy of the data at the address A2 could not be stored.

FIG. 17B: Second cache S1
Stores the returned data of address A2 and
The data is returned to the first cache F1.

FIG. 17C: First cache F
1 stores the returned data and returns the data to the processor P1.

It is conceivable to effectively use the memory capacity of the second cache by the hierarchical cache memory in which the MLI does not hold. In the following example, it seems more advantageous if the MLI does not hold.

FIG. 18A: The processor P1 accesses the data at the address A1, a cache miss occurs in the first cache F1, and a read request is issued up to the second cache S1. However, the data of the address A1 does not exist in the second cache S1, and each entry is already occupied by the data of another address.

FIG. 18B: Second cache S1
Decides to store the data of address A1 in the entry in which the data of address A3 is stored, and issues a request to the memory bus to read the data of address A1.

FIG. 18C: Second cache S1
Stores the data at address A1 and returns the data to the first cache F1.

FIG. 18D: Although the data is returned, the first cache F1 stores the data and returns the data to the processor P1.

However, when MLI does not hold,
In the following situations, transactions are increased and system performance is degraded, and desired effects cannot be obtained.

FIG. 19 (a): Another second cache issues a request to invalidate the data at the address A0 to the second cache S1 via the memory bus, and the second cache S1 issues a request to the second cache S1. There was no cache block for that data.

FIG. 19B: Since the MLI is not established, the second cache S1 does not have information on whether or not the data to be invalidated exists in the first cache in the cluster. -A request for invalidation was issued to the bus.

FIG. 19C: None of the child cache memories stores the data of address A0, and the response is returned to the second cache S1 as it is.

FIG. 19 (d): The second cache S1 which has received the responses from all the child cache memories sends the responses to the memory bus.

Thus, if no child cache memory has data, the transaction is wasted. A similar situation occurs not only for invalidation but also for read modified requests. This waste transaction did not occur when the MLI holds.

When the MLI does not hold, useless transactions occur during copy back, but the following examples correspond to this.

FIG. 20A: When a read or write access is made from the processor P1 to the first cache F1, the first cache F1 does not have the data of the address to be accessed and a cache miss occurs. However, the data at the address A0 needs to be copied back.

FIG. 20 (b): First cache F
When the data at the address A0 was copied back from 1 to the second cache S1, the cache block for storing the data did not exist in the second cache S1.

FIG. 20C: Second cache S1
Indicates that a request is issued to the memory bus in order to copy back the copied back data of the address A0 to the main memory as it is.

FIG. 20D shows a case where the copy back to the main memory is completed and a response is returned to the second cache S1.

FIG. 20E: Second cache S1
Returns a response from the first cache F1 indicating the completion of the copy back, and the first cache starts the operation for the original memory read or write.

The above copy back to the main memory is a transaction that occurs because the MLI does not hold.

Next, the effect expected from the second cache of this embodiment in the situation of FIG. 16 which is a problem in the conventional example in which the MLI is established will be described.

FIG. 21A: The processor P1 makes a read access to the address A1 from the first cache F1 to cause a cache miss, and if necessary, the address A.
After copying back the data of 2, the RSH request is issued to the second cache S1.

FIG. 21B: Second cache S1
, The corresponding line entry has the address A1
There is no tag entry for and there was a cache miss.
Then, the second cache S1 selects an entry for storing the tag / state of the address A1 and issues an RSH request to the memory bus.

FIG. 21C: Since there is no space in the data entry, the data is not stored in the data entry and the data is returned to the first cache F1 as it is.

FIG. 21D: First cash F1
Stores the returned data and returns the data to the processor P1.

FIG. 22A: An access to the address A2 occurs, and a cache miss still occurs in the first cache F1.

FIG. 22B: Second cache S1
Since the data of address A2 remains in the memory,
Data is returned to the first cache F1 without requesting data to the bus.

FIG. 22C: First cache F
1 stores the returned data of the address A2 and returns the data to the processor P1.

As in this example, in the cache miss caused by re-accessing the data evicted from the second cache due to the insufficient capacity of the second cache in the conventional example, the entry of the tag memory is included in the cache miss. There are some that can be prevented from occurring by preparing enough numbers. This reduces the transaction frequency of the memory bus and improves system performance.

The situation of FIG. 19 which is a problem in the conventional example in which the MLI is not established will be described.

FIG. 23 (a): A request for invalidating the data at the address A0 is issued to the second cache S1 from another second cache via the memory bus. Regarding the tag memory, since the MLI is established, if the entry of address A0 does not exist in the tag memory of the second cache S1, it is known that the data of address A0 does not exist in the cluster.

FIG. 23B: Second cache S1
Is returning a response without making a request to the cache bus.

It is possible to prevent a wasteful transaction that occurs because the MLI does not hold as in this example.

Further, it will be explained that in the situation shown in FIG. 19, useless transactions can be prevented in some cases.

FIG. 24A: When a read or write access is made from the processor P1 to the first cache F1, the first cache F1 does not have the data of the address to be accessed and a cache miss occurs. However, the data at the address A0 needs to be copied back.

FIG. 24B: Since the data entry for storing the copied back data is not empty, it is judged whether or not there is a data entry which can be ejected according to the data entry replacement algorithm. , If it exists, the data copied back is stored in it.

FIG. 24 (c): The data entry in which the data of the address A4 was stored is selected, the copied back data is stored in the selected data entry, and a response notifying the end of the copy back is sent to the first cache F1. I'm returning.

The present invention is not limited to the above-mentioned embodiments, and can be carried out by appropriately modifying it without changing the gist.

In this embodiment, write-invali is used.
Although a date-based cache protocol has been described, other types (eg, write-bro) are used.
adcast method, read-broadcast method, competitive-snooping method,
Also, it can be applied to a cache protocol of these mixed methods).

In the present embodiment, the existing memory and the corresponding memory have been described as two different means. However, the information to be stored by both means is one that stores the information indicating the correspondence between the entries in the tag memory and the data memory. It can also be realized by means.

Although the present embodiment has been described only for the cache memory device having two layers, it can be applied to a cache memory device having a larger number of layers. Conventionally, ML
Because of I, the cache of a level close to the main memory
It was difficult to realize because the memory capacity became huge. According to the present invention, the required memory capacity can be reduced and the implementation becomes easy.

The present invention is not limited to a cache memory device, but in a system for storing information in a distributed manner, the system includes a plurality of storage bodies, active bodies that access information in the storage bodies, and active bodies. The present invention can be applied to the configuration including the memory and the information transmitting means for connecting the memory by replacing the processor, the cache memory, and the bus of this embodiment with the active body, the memory, and the information transmitting means, respectively. When a request for data having a certain address (data ID) is transmitted to a storage body having a request for data having a certain address (data ID), the contents of the entry of the tag memory are directly stored in an adjacent storage body connected by an information transmission means. On the other hand, it can be regarded as an entry storing information (request transmission management information) for determining whether or not the request needs to be transmitted.

In this embodiment, only the system having the tree structure topology has been described, but the system can be extended to an arbitrary structure. For example, in the case of the system as shown in FIG. 25, the MLI has the following meaning: "When a request for information of a certain ID is transmitted to a certain memory, the information having that ID is stored in the memory. If it does not exist in the body, it is not necessary to transmit the request to an adjacent storage body (other than the request source) directly connected to the storage body by the information transmission means. Here, the request is an access such as data read, write, invalidation, broadcast, or copyback. This property guarantees that the elements of the set of storage bodies having the information of the same ID are “connected” because they are directly connected to any other by the information transmission means. The effect of this property is that the access time to the information can be shortened by preventing the request from being unnecessarily transmitted to the storage body which originally does not need to be transmitted.
In other words, the purpose of storing information in each storage body is not merely the purpose of storing information, but also the purpose as management information indicating to which storage body a request for information needs to be transmitted.

The management information indicating to which storage body the request needs to be transmitted is information such as whether or not the data is shared and whether or not the data exists in the adjacent storage body. (Request transmission management information)
However, it is not the content of the data itself. Therefore, the present invention is a "heterotic MLI" having the following meaning.
It can be considered as an example of: “When a request for data having a certain ID is transmitted to a certain storage body,
If the request transmission management information having the ID does not exist in the storage body, it is not necessary to transmit the request to the adjacent storage body (other than the request source) directly connected to the storage body by the information transmission means. ] That is, regarding the request transmission management information, M
LI is established, but the contents of the data itself is MLI.
Does not have to hold. As a result, the amount of information to be stored in each storage unit can be reduced, and useless transmission of requests can be prevented.

[0140]

As described above, according to the present invention, the memory capacity of the second cache can be effectively used, and even if the second cache capacity cannot be secured sufficiently, the second cache can be The introduced effect can be realized and the system performance can be improved by improving the cache hit rate.

Further, even when the number of layers exceeds two layers, the capacity of the cache memory of the layer on the main memory side needs to be sufficiently large because of the MLI, which is extremely difficult to realize. Realization becomes easy because it is sufficient to secure only the capacity of the entry. This makes it possible to realize about 1,000 multiprocessors by bus connection.

[Brief description of drawings]

FIG. 1 is a conceptual diagram of a hierarchical cache memory device according to an embodiment of the present invention.

FIG. 2 is a schematic configuration diagram of a second cache in the embodiment.

FIG. 3 is a diagram showing the correspondence of entries in each memory.

FIG. 4 is a state transition diagram of a first cache for explaining a conventional example.

FIG. 5 is a state transition diagram of a second cache for explaining a conventional example.

FIG. 6 is a diagram showing a response to a request from a second cache in a conventional example.

FIG. 7 is a diagram showing a response to a second cache request in a conventional example.

FIG. 8 is a diagram showing a response to a request of the second cache in the embodiment.

FIG. 9 is a diagram showing a response to a request from the second cache according to the present embodiment.

FIG. 10 is a diagram showing a response to a request from the second cache according to the present embodiment.

FIG. 11 is a diagram showing a response to a request from the second cache according to the present embodiment.

FIG. 12 is a state transition diagram of the second cache according to the present embodiment.

FIG. 13: State of cache block causing problems
The figure showing the combination of U bit and existence bit.

FIG. 14 is a state transition diagram of the second cache according to the present embodiment.

FIG. 15 is a state transition diagram of the second cache according to the present embodiment.

FIG. 16 is a diagram showing a situation in which useless bus traffic occurs in a conventional example in which MLI is established.

FIG. 17 is a diagram showing a situation in which useless bus traffic occurs in a conventional example in which MLI is established.

FIG. 18 is a diagram showing a situation in which useless bus traffic is prevented in a conventional example in which MLI does not hold.

FIG. 19 is a diagram showing a situation where useless bus traffic occurs in a conventional example in which MLI does not hold.

FIG. 20 is a diagram showing a situation where useless bus traffic occurs in a conventional example in which MLI does not hold.

FIG. 21 is a diagram showing a situation in which useless bus transactions are prevented in this embodiment.

FIG. 22 is a diagram showing a situation in which useless bus transactions are prevented in this embodiment.

FIG. 23 is a diagram showing a situation in which useless bus transactions are prevented in this embodiment.

FIG. 24 is a diagram showing a situation in which useless bus transactions are prevented in this embodiment.

FIG. 25 is a conceptual diagram of a system in which heterotic MLI is effective.

[Explanation of symbols]

1 ... Processor, 2 ... First cache, 3 ... Cache bus, 4 ... Second cache, 5 ... Cluster, 6 ... Memory bus, 7 ... Main memory, 11 ...
Tag memory, 12 ... Data memory, 13 ... Existing memory, 14 ... Corresponding memory, 15 ... Cache bus interface unit, 16 ... Memory bus interface unit, 17 ... Cache bus controller, 18 ... Memory, Bus controller.

Claims (2)

[Claims] 1. At least one first cache is connected to at least one processor, the first cache is connected to a first bus, and at least one second cache is connected. To configure the cluster,
In a hierarchical cache memory device in which a plurality of clusters are connected to a main memory via a second bus, the second cache is directly connected to the second cache via the first bus. Tag storage means for storing a tag relating to data stored in the connected first cache, data storage means for storing a copy of the data stored in the first cache, and an entry of the tag storage means An existence storage unit that stores information regarding whether or not the data corresponding to the entry secures an entry in the data storage unit; and stores information regarding a correspondence relationship between the entry in the data storage unit and the entry in the existence storage unit. A corresponding storage means, wherein the entry corresponding to the request address for the request from the second bus is the tag storage If the data exists in the stage, the existence storage means determines whether data exists in the second cache, and if the data exists, the corresponding storage means selects an entry of the data storage means and returns the data to the request source. A hierarchical cache memory device, characterized in that 2. When an entry corresponding to the request address for the copy back request from the first bus exists in the existing storage means, the corresponding storage means selects the entry in the data storage means to update the data, When an entry does not exist, a copy algorithm is performed after securing an entry in the data storage means by a replacement algorithm that guarantees data consistency, or a copy back request is issued up to the second bus. The hierarchical cache memory device of claim 1, wherein the hierarchical cache memory device comprises: