JPH077358B2 - Hierarchical cache memory device - Google Patents

Description

The present invention relates to a hierarchical cache memory device having a plurality of cache memory devices hierarchically structured between a plurality of processors and a main memory device. .

(Prior Art) In a computer system in which a plurality of processors and a main memory device are commonly connected via a bus, and data is exchanged with other processors or main memory devices via the bus, So-called bus contention due to simultaneous access from processors becomes a problem. Therefore, a high-speed small-capacity memory device corresponding to each processor may be provided as a cache between the processor and the main memory device, and the cache memory device may have a copy of the data of the main memory device. It is considered.

According to such a cache memory system, each processor can equivalently exchange data with the main memory device or another processor at high speed by accessing the cache memory device. It is possible to effectively avoid problems such as tension.

By the way, in this type of cache memory system, there is a problem in that the data contents of a plurality of cache memory devices and the main memory device match. That is, when the data is updated by writing from the processor to the cache memory device, the data content copied to another cache memory device or the main memory device becomes invalid. Therefore, in this case, it is necessary to notify other cache memory devices or main memory devices that the data contents have been updated. As a method for this purpose, for example, the following document proposes the timing of the notification and the method of expressing the validity of the data.

"Archibold, J. and Baer, J.-L." Csche Coherence Protocols: Evaluation Using a Multiprocessor Simulation Model "ACM Transaction on Computer Systems, Vol.4, No.4, November 1986, pp273-298" In a program in which the processor writes to the same address or in a program in which blocks are frequently ejected from the cache memory device, bus contention by a command for data transfer or invalidation of the contents of other cache memory devices may occur. The problem arises. In order to solve such a problem, the following document proposes a method for hierarchically providing a new cache memory device between the cache memory device and the main memory device to reduce the bus traffic. .

“Hattori, A., Koshino, M. And S.Kamimoto“ Three-level hierarchical storage system for FACO
M M-380 / 382 "pp693-697 Proc. Information Proceeding IFIP, 1983" However, when the number of processors increases, the bus condition between the upper cache memory device and the lower cache memory device, which are layered, becomes hierarchical. In order to deal with such a problem, it is considered to increase the number of cache memory devices in the lower hierarchy, as proposed in the following document, for example.

“AW Wilson Jr.“ The 14th Annual International Symposium on COMPU
TER ARCHITECTURE "COMPUTER ARCHITECTURE NEWS Vol.15 No.2 June2-5,19
87 Pittsburg, Pennsylvania] FIG. 2 is a diagram showing a schematic configuration of a hierarchical cache memory device constructed based on such a viewpoint, and P is a plurality of processors. A plurality of first cache memory devices C1 are provided corresponding to each of these processors P, and these first cache memory devices C1 are commonly connected by a predetermined number by a plurality of first buses B1. Further, the plurality of second cache memory devices C2 are connected to the above-mentioned first buses B1.
The second cache memory device C2 is commonly connected by the second bus B2. A main memory device M is connected to the second bus B2, and a plurality of cache memory devices C1 and C2 are provided between the main memory device M and the plurality of processors P described above on the bus B.
A memory structure that is hierarchically provided via 1 and B2 is realized.

However, in such a configuration, the second cache memory device C2 in the lower hierarchy has the first bus B1 located in the upper level thereof.
And a command relating to the coherency of the data content in the cache memory device C2 may be received from both of the second buses B2 located below it.

However, in this case, depending on the type of the command and the data content in the cache memory device C2, the cache memory device C2 responds to the command received from the upper side (first bus B1) by the lower bus (second bus). It may be necessary to issue a command to B2) and also to issue a command to an upper bus (first bus B1) in response to a command received from the lower side (second bus B2). However, the upper side bus (first bus B1) is occupied by the command from the upper side (first cache memory device C1), while the lower side bus (second bus B2) is in the lower side (others). Since it is occupied by the command from the second cache memory device C2), there is a problem that a so-called deadlock state occurs. For this reason, there are some problems to be solved in order to make a plurality of cache memory devices in the lower hierarchy, and in general, a hierarchical memory structure as shown in FIG. 2 is adopted. There was a problem that it was difficult.

The state of occurrence of this deadlock will be specifically described with reference to FIG.

FIG. 3A shows that the processor P1 issues a read request command to the first cache memory device C11 corresponding to itself. However, cache memory device
Suppose C11 does a cache miss because it does not have the requested block (data). In this case, the cache memory device C11 needs to bring a copy of the requested block from another cache memory device. As a result, the cache memory device C11 is shown in FIG.
As shown in FIG. 5, a copy of the block requested from the processor P1 is sent to the other cache memory devices C12 and C13 of the same hierarchy and the second cache memory device C21 of the lower hierarchy via the first bus B1. The requested command is transmitted by broadcasting.

However, if the other cache memory devices C12 and C13 and the second cache memory device C21 in the same hierarchy as the cache memory device C11 do not have the block requested to be read by the above-mentioned command, the second cache memory The device C21 is the cache memory device C21.
In order to bring a copy of the block requested to be read by the above command from another cache memory device C22 or the main memory device M in the same hierarchy as the second bus B2 as shown in FIG. 3 (c). The above command is output via.

However, at the same time when the command is transmitted from the processor P1, the upper processor P2 of the second cache memory device C22 to which the command is given via the bus B2 is shown in FIG. 3 (b). It is assumed that a command requesting copying of the generated block has entered as shown in FIG. 3 (c). When the cache memory device C22 does not have the block requested by the command from the upper bus (processor P2), the cache memory device C22 tries to issue the command requesting the copy of the block to the lower bus.

However, the second bus B2 is already occupied by the command from the processor P1 described above. As a result, as shown in FIG. 3 (d), the second cache memory device C22 cannot output the command requested by the processor P2, which is the upper processor, to the second bus B2, and
In response to a command from the processor P1 given via the bus B2 of
It cannot be responded to because it is occupied by the command from P2.

The deadlock situation thus generated cannot be resolved unless either the command given from the second bus B2 or the command given from the first bus B1 is sent back and the bus is released.

On the other hand, attempts have been made to avoid the deadlock described above by programming. Specifically, by programming, the second cache memory device C2 returns a response to the command from the second bus B2 on the lower side, and then the second cache memory device C2 on the upper side with respect to the second cache memory device C2. It has been attempted to avoid the occurrence of deadlock by allowing commands to be given from one bus B1.

However, even after the second cache memory device C2 returns a response to the command from the lower second bus B2, the lower second bus B2 is still occupied by other resources. If the second cache memory device C2 is left as it is, the second cache memory device C2 cannot respond to a command from the upper side until the second bus B2 on the lower side is released. It will be necessary to wait for the release of B2.

Especially in the following situations, the waiting time becomes large.
One is that, in the memory device having the above-mentioned hierarchical structure, the access time is generally longer in the lower cache memory device. Therefore, a command occupying the lower-order bus is accessing the lower-order memory device. In the first example, if the distance between the cache memory devices in this hierarchical cache memory device is defined by the number of times the command passes through the bus, for example, the commands occupying the lower level buses are separated by distance. This is the case when the cache memory device is reached.

In either of these cases, if a command that occupies a lower bus continues to wait for a command that occupies the lower bus to release the bus, it will also occupy the upper bus. Will continue. When such a situation occurs, the processing efficiency for individual requests from a plurality of processors is significantly hindered and the overall processing efficiency is greatly reduced, which is a serious problem.

(Problems to be solved by the invention) As described above, in the conventional cache memory technology, when the cache memory device is hierarchically structured, a plurality of cache memory devices in the lower hierarchy are provided due to the problem of the deadlock described above. Had some issues to solve. Further, in this hierarchical structure, even if deadlock in the cache memory device of the lower layer is avoided by programming, for example, when a command from the upper side bus is issued and the command is issued to the lower side bus, the cache memory If the lower bus of the device C is already occupied by another resource, the cache memory device needs to wait for a response to the upper command until the lower bus is released. When such a situation occurs, there is a problem in that the bus on the upper side is also occupied during that time, and as a result, there is a problem that the processing efficiency with respect to requests from a plurality of processors is significantly reduced.

The present invention has been made in consideration of such circumstances, and an object of the present invention is to effectively avoid the occurrence of deadlock and prevent unintentional occupation of a bus to prevent a processor from a plurality of processors. It is an object of the present invention to provide a highly practical hierarchical cache memory device capable of effectively responding to a request and improving the overall processing efficiency thereof.

[Configuration of the Invention] (Means for Solving the Problems) The present invention, as shown in the schematic configuration in FIG. 2, includes a plurality of first cache memory devices provided corresponding to a plurality of processors P, respectively. C1 and a plurality of second cache memory devices respectively connected to the first cache memory device C1 through a plurality of upper-side buses B1 interconnecting a plurality of these first cache memory devices C1 C2
And a main memory device M connected to the second cache memory device C2 via a lower-order bus B2 connecting these second cache memory devices C2 to each other, When the second cache memory device C2 receives a command from the upper bus B1 and tries to output a command to the lower bus B2, is the lower bus B2 already occupied by another device? When it is determined by the determining means that determines whether or not the lower-order bus B2 is occupied, the command from the upper-order bus B1 is returned to the request source and the higher-order side is determined. It is characterized in that a return means for releasing the bus B1 is provided.

In other words, as shown in the control processing concept in FIG. 1, a command from the upper side bus B1 is input and the lower side bus B2 is input.
When a command is to be output to the second cache memory device C2 (step a), the second cache memory device C2
The determination means determines whether or not the lower side bus B2 is already occupied by another device, such as when the command from the B2 is input and the command is output to the upper side bus B1 (step b), Lower side bus B2 by the judging means
If it is determined that is already occupied by another device, the sending-back means sends back the command from the bus B1 on the upper side to the request source to release the bus B1 on the upper side ( The step c) is characterized in that the command from the upper side bus B1 is transmitted to the lower side bus B2 (step d) only when the lower side bus B2 is idle. .

(Operation) According to the present invention having such a determination means and a send-back means, the second cache memory device receives a command from the bus on the upper side thereof and outputs the command to the bus on the lower side with respect to this command. In doing so, if the determining means determines that the lower-side bus is already occupied by another device, the send-back means detects this and requests the command from the upper-side bus. Since the upper side bus is released by sending back to the original, the command from the lower side bus can be effectively transmitted to the upper side bus, and deadlock can be avoided before and effectively. It becomes possible.

In addition, since the occurrence of deadlock is avoided in this way, the upper side bus will not be occupied by the lower side bus, and the released upper side bus will be used. It is possible to process a command from another request source first. In other words, other commands that do not need to be transmitted to the lower bus can be processed first. As a result, it is possible to improve the processing efficiency for requests from a plurality of processors.

(Embodiment) An embodiment of a hierarchical cache memory device according to the present invention will be described below with reference to the drawings.

FIG. 4 is a diagram showing a schematic configuration of a second cache memory device in the hierarchical cache memory device according to the first embodiment, and 1 is a cache memory device main body. The cache memory device main body 1 includes a first cache memory device C1 provided corresponding to a plurality of processors P, respectively.
A first bus B1 interconnecting the two is connected as an upper bus 2, and another second cache memory device C2 in the same hierarchy is connected.
And a second bus interconnecting the main memory devices M to each other
B2 is connected as the lower bus 3 to perform the cache function.

However, the cache memory device body 1 basically comprises a RAM section 4 which is composed of a tag RAM and a data RAM and functions as a cache memory, and an access to the RAM section 4 in response to a command from the host bus 2. It comprises a cache controller 5 on the upper bus side for controlling, a bus controller 6 for the lower bus 3, and a snoop controller 7 for controlling access to the RAM section 4 in response to a command from the lower bus 3.

The second cache memory device according to this embodiment is characterized in that, in addition to the cache memory device body 1 having the above-described configuration, the cache memory device body 1 attempts to output a command to the lower bus 3. At this time, it is detected whether or not the lower bus 3 is already occupied by another command, and if it is occupied, a response for sending back the command is returned to the cache memory device body 1 and If the lower bus 3 is not occupied, the lower bus occupancy determination device 8 having a function of transmitting the command as it is to the lower bus 3 is provided.

That is, in the lower bus occupation determination device 8, the cache memory device main body 1 receives a command from the upper bus 2,
When a command is output to the lower bus 3 as a response, the command to be output to the lower bus 3 is input. Then, when this command is input, it is checked whether or not the lower bus 3 is already occupied by another command or the like, and the command is output to the lower bus 3 on condition that the lower bus 3 is empty. If the lower bus 3 is already occupied by another command, the lower bus occupancy determination device 8 returns a response to the cache memory device body 1 in order to return the command to the request source. When the cache memory device body 1 receives such a response from the lower bus occupancy determination device 8, it sends back the command to be output to the lower bus 3 to the request source (processor) via the upper bus 2.

FIG. 5 shows the flow of processing operations in a hierarchical cache memory device constructed using the second cache memory device having the above-described functions, and in particular, the desired cache operation is performed by avoiding deadlock. It is a figure which shows typically the process.

In FIG. 5 (a), the request for copying the block output from the first cache memory device C11 in the upper hierarchy is the second request.
Also in the cache memory device C2 of the second cache memory device C2, a command to bring a copy of the block from another cache memory device of the same hierarchy or the main memory device M is cache missed. It shows a state in which the main body 1 outputs to the lower bus occupation determination device 8.

At this time, however, if the lower bus 3 is already occupied by another command, the lower bus occupancy determination device 8 sends a response for returning the command as shown in FIG. 5 (b) to the main body of the cache memory device. 1 bus controller 6
Return to. Then, as shown in FIG. 5 (c), the bus controller 6 which has received the response of the command return from the lower bus occupancy determination device 8 sends the command return response to the upper bus side cache controller 5. Returns
The cache controller 5 on the upper bus side, which has received this, returns a command send back response to the upper bus 2 as shown in FIG. 5 (d). Such a command return response is sequentially transmitted to the command requesting processor, and the command requesting processor releases the upper bus 2 as shown in FIG. 5 (e).

As a result, the snoop controller 6 receiving the command from the lower bus 3 releases the upper bus 2 by the above-mentioned command return, so that FIG.
As shown in, a command for requesting block copy from the lower bus 3 to the upper bus 2 can be sent to the upper bus 2.

FIG. 6 shows that by the processing function of the lower bus occupancy determination unit 8 described above, when the lower bus 3 is occupied, a command is sent back to the upper bus 2 to improve the processing efficiency in response to requests from a plurality of processors. It is a figure which shows the situation.

In FIG. 6A, the read command issued by the processor P1 causes a cache miss in the cache memory device C11, and the cache memory device C11 has a cache memory device C12 in the same layer and a cache memory device C in the lower layer.
First command to request 21 to copy block
However, the cache memory device C21 also shows a cache miss. Then, it is necessary to issue a command from the cache memory device C21 to the lower second bus B2, but the second bus B2 is already occupied by another command, and the command is far from the cache memory. It shows the situation of reaching the device.

In this case, it is expected that it takes a relatively long time until the response to the command reaching the cache memory device which is far away via the second bus B2 is returned. Further, in this situation, no deadlock occurs in the cache memory device C21.
Could wait for the command output to the lower bus B2 until the lower bus B2 is released.

However, now, in the upper layer of the cache memory device C21,
In addition to the above-mentioned first cache memory device C111, I want to issue a command to the first bus B1 due to a read / write miss, but the first bus B1 is issued by the command issued by the cache memory device C11. Is occupied, so
Suppose there is a cache memory device C12 waiting for its bus B1 to be released. In addition, the command output from the cache memory device C12 may be the second bus B which is lower than the second bus B depending on the contents of the second cache memory device C21.
Sometimes it is not necessary to issue a command to 2.

In such a case, the first cache memory device C11
If the command from the cache memory device C12 is once returned to release the bus B1, the command from the cache memory device C12 is accepted by the second cache memory device C21, and the command is processed, the overall processing efficiency is improved. That is, the second bus B2
Is used to process the request by the command from the cache memory device C12, which does not need to output the command to the second bus B2, by using the waiting time until it is released. It can be expected to improve efficiency.

According to the device of this embodiment, however, the command given from the cache memory device C11 to the second cache memory device C21 is stored in the second cache memory device C21 due to the occupation of the second bus B2. By the operation of the bus occupation determination device 8, the data is returned to the cache memory device C11 and the first bus B1 is released. This first bus B1
Is released, the second cache memory device C21 becomes the second cache memory device C21.
The request from another cache memory device C12 will be processed by using the period in which the bus B2 is occupied and the command from the cache memory device C11 is waiting.

Further, in FIG. 6 (b), a command requesting a copy of a block is sent from the upper bus B1 to the second cache memory device C21, but a cache miss occurs, and the second lower bus
I need to issue a command to B2, but already on the second bus
B2 is occupied by another command and the command reaches the main memory device M. However, in general, since it takes a relatively long time to access the main memory device M, the above-described sixth method is used.
It is expected that it will take a considerably long time before the second bus B2 is released as in the situation shown in FIG. Since the deadlock does not occur even in such a situation, the second cache memory device C21 may continue to wait until the second bus B2 is released.

However, I want to issue a command to the bus due to a read or write miss in the upper hierarchy of the cache memory device C21, but since the command reaching the cache memory device C21 occupies the first bus B1, Suppose there is another cache memory device C12 waiting for the first bus B1 to be released. However, the request from the cache memory device C12 may hit the second cache memory device C21.

Therefore, under such a circumstance, the second cache memory device C21 releases the first bus B1 by temporarily returning the command currently given from the higher-order bus B1. Then, it is determined whether a request from another cache memory device C12 hits or misses, and if it is confirmed that it is not necessary to issue a command to the second bus B2, the second cache memory Device C21 is the first bus B1
A response to the request from the cache memory device C12 is returned to.

If a request from another cache memory device C12 is missed and the second bus B2 is still occupied by another command at this time, the command from the cache memory device C12 is directly transmitted to the first bus B1. Send back to. If the second bus B2 is released, the command from the cache memory device C12 is output to the second bus B2.

In other words, as the second cache memory device C21, the second bus among the commands given from the upper layer is waited during the waiting time until the lower second bus B2 is released.
It is possible to send back a response to those that do not need to issue commands to B2. This has a remarkable effect in improving the throughput with respect to the demand from the processor. In fact, according to the apparatus of the embodiment described above,
When the bus B2 is occupied, the lower bus occupancy determination device 8 sends back a reply response to the command to be transmitted from the upper side to the lower side. As a result, the first high-order bus
Since B1 is released, the second cache memory device C21
Allows the waiting time of a command from one processor while the second bus B2 is occupied by another command to process a request from another processor.

Although the lower bus occupancy determination device 8 is provided outside the cache memory device body 1 in this embodiment, the cache memory device body 1 is provided with its function, or the bus controller in the cache memory device body 1 is provided. Of course, it is also possible to give 6 the function.

By the way, in the above embodiment, when the deadlock situation is about to occur, it is judged that the lower bus (second bus B2) is occupied and the command is sent back. As a sufficient condition for occurrence of the above, rather than the fact that the second bus B2 is occupied, it is more severe when a command is given to the second cache memory device C2 from the second bus B2. It becomes a condition.
Therefore, when a certain cache memory device tries to issue a command to the lower bus, when a command is given from the lower bus, the command from the upper host is sent back to avoid deadlock. You can

FIG. 7 shows an embodiment in which the above-mentioned bus controller 6 itself has a function of returning the command given from the upper side when the commands are given from the upper side and the lower side at the same time. . That is, the bus controller 6 is provided with a function of detecting whether or not a command is given from the lower bus (second bus B2) when the command is given from the upper bus side cache controller 5, When a command is given from the second bus B2, it has a function of returning a response to the command given from the upper-level bus side cache controller 5 for instructing the return of the command. I am trying.

According to the embodiment apparatus configured as described above, the deadlock situation is avoided as shown in FIG.

Now, as shown in FIG. 8A, the read command requested by the processor P1 causes a cache miss in the first cache memory device C11, and the cache memory device C11 is inferior to the other cache memory devices 12 in the same hierarchy. It is assumed that a command requesting copy of a block is issued to the second cache memory device C2 in the hierarchy. However, the cache memory device C12 of the same layer does not have a copy of the block, and if the lower second cache memory device C2 also determines that the command is a cache miss, the second cache memory device C12 concerned. The upper bus side cache controller 5 in C2 gives a command to the bus controller 6 for requesting a copy of a block to the cache memory device of the same hierarchy or the main memory device M.

However, at this time, in addition to the command given from the high-order bus side cache controller 5, it is assumed that a command requesting block copy from the low-order bus (second bus B2) has entered the bus controller 6. .

However, under such circumstances, as mentioned above,
The controller 6 has a function of returning a send-back response to the command from the above-mentioned command when the command is received from the lower-order bus when the command comes from the higher-order and has not yet returned the response to it. have.
Since the state shown in FIG. 8 (a) is just that, the bus controller 6 instructs the cache controller 5 on the upper bus side to send back the command as shown in FIG. 8 (b). Will be returned.

While the command is being sent back, the command given from the second bus B2 is transmitted from the bus controller 6 to the snoop controller 7.

Here, the snoop controller 7 has a block requested by the command given from the second bus B2, but it is assumed that the content has already been updated in the cache memory device C12 of a higher level. Then, in this case, the snoop controller 7 tries to issue the command to the upper bus (first bus B1) in order to bring a copy of the block from the upper cache memory device C12. However, since the first bus B1 is still occupied by the command from the cache memory device C11, the snoop controller 7 operates the first bus B1.
Will continue to wait for the release.

However, in such a situation, as shown in FIG. 8 (c), the host bus side controller 5 which has received the response from the bus controller 6 for returning the command is
Sending back a command return response to the bus B1. As a result, the cache memory device C11 that has received the response to send back the command releases the first bus B1.
As shown in FIG. 8 (d), a second cache memory device
The snoop controller 7 of C2 can send a command to the first bus B1.

In this way, the occurrence of deadlock in the second cache memory device C2 is avoided, and the second cache memory device C2
The command output from C2 reaches the target first cache memory device C12. The command sent back to the cache memory device C11 is a response to the command given to the cache memory device C12,
Wait for the first bus B1 to be released and then again the first bus
Dispatched to B1.

By the way, in the cache memory device having the hierarchical structure as described above, even if a command for copying a block comes from a higher-order bus to a certain cache memory device, the command does not necessarily have to be issued to the lower-order bus. . It is only under certain limited conditions that a lower bus needs to be commanded. Specifically, when the cache memory device does not have the block requested by the command from the higher-order bus and requests the copy of the block to another cache memory device, or when the copy of the block is copied to the main memory device M. For example, when backing up, or when invalidating the contents of a block of another cache memory device.

Similarly, even if a command comes from a lower bus, it does not necessarily have to be issued to a higher bus. Specifically, when the content of a block of the cache memory device is updated in the cache memory device of the upper level, and the data is not written back, the data is read, This is a case where the contents of the cache memory device are invalidated.

FIG. 9 shows an embodiment which is optimized so as to send back a command only in a situation where such a deadlock can really occur.

The cache memory device in this embodiment is realized by providing the deadlock avoidance device 9 in the cache memory device body 1 having the above-described configuration.

The deadlock avoidance device 9 detects a command that the cache memory device is trying to issue to the upper bus (first bus B1) and the lower bus (second bus B2) respectively, and both commands are issued. In the meantime, it has a function of returning a response for rewinding the command to the command which is about to be issued to the lower bus (second bus B2). That is, when the command from the upper first bus B1 is received and the command is issued to the lower second bus B2, the command given from the second bus B2 is simultaneously sent to the first command. When trying to communicate to B1,
It has a function of stopping the output of the command to be output to the second bus B2 and sending the command back to the first bus B1.

According to the embodiment apparatus configured as described above, the occurrence of deadlock is avoided as shown in FIG.

That is, FIG. 10 (a) shows the deadlock avoidance device 9
The command to be output to the second (lower) bus B2 from the controller 6 and the first command from the snoop controller 7
This shows a situation in which a command to be output to the (upper) bus B1 is simultaneously given. In this way, when the command from the bus controller 6 is given, the deadlock avoidance device 9 judges whether the command from the snoop controller 7 has come, and that the command actually comes from the snoop controller 7. Confirm and confirm Fig. 10 (b).
As shown in (4), a response for sending back a command is returned to the bus controller 6.

Then, the bus controller 6 which has received the response for sending back the command from the deadlock avoidance device 9 sends back the command to the upper cache controller 5 as shown in FIG. 10 (c). Return a response. As a result, as shown in FIG. 10 (d), the upper bus side cache controller 5 that has received the command send back response sends a command send back response to the upper bus (first bus B1). Will be returned.

As a result, the cache memory device C11 of the processor P1, which is the request source of the command, receives the first response in response to the above-mentioned return response.
Release bus B1. Then, when the first bus B1 is released, as shown in FIG. 10 (e), the deadlock avoidance device 9
Is the first command from the snoop controller 7.
To the target first cache memory device C12 to request a copy of the block.

According to the apparatus of this embodiment, the command from the upper side is returned only when the deadlock actually occurs. In this respect, although the cache control is slightly different in that the commands are returned even if the deadlock does not occur in the above two embodiments, the cache control is basically different depending on each of these control modes. It is possible to effectively avoid the occurrence of deadlock, and it is possible to effectively respond to requests from other processors on the upper side by utilizing the period in which the lower bus is occupied. It is possible to improve various processing efficiency.

The present invention is not limited to the above embodiments. For example, the configuration of the main body of the cache memory device, the condition determination for sending back the command, and the like may be determined according to the system specifications. Further, the cache memory device may be constructed in three or more layers to avoid the occurrence of deadlock in each cache memory. In addition, the present invention can be variously modified and implemented without departing from the scope of the invention.

As described in detail above, according to the present invention, it is possible to effectively avoid the occurrence of deadlock in a cache memory device in a memory device having a hierarchical structure, and to respond to requests from a plurality of processors. The processing efficiency can be greatly improved by greatly improving the processing efficiency.

[Brief description of drawings]

FIG. 1 is a diagram showing a processing concept of the present invention, FIG. 2 is a diagram showing a concept of a hierarchical structure of a cache memory device to which the present invention is applied, and FIG. 3 is a schematic view of a deadlock occurrence state in a conventional device. 4 and FIG. 4 are diagrams showing a schematic configuration of a main part of a cache memory device of a certain hierarchy according to the first embodiment of the present invention, and FIG. 5 is a command inside the cache memory device in the first embodiment. And FIG. 6 is a diagram showing the flow of response, FIG. 6 is a diagram schematically showing the improvement of the throughput in response to a request from the processor according to the present invention, FIG. 7 is a schematic configuration diagram of a main part of the second embodiment device, and FIG. Is a diagram showing the flow of commands and responses in the device of the second embodiment, FIG. 9 is a schematic configuration diagram of the essential parts of the device of the third embodiment, and FIG. 10 is a flow of commands and responses in the device of the third embodiment. FIG. P ... Processor, C1 ... First cache memory device, B1 ... First bus, C2 ... Second cache memory device, B2 ... Second bus, M ... Main memory device, 1
...... Cash memory device main unit, 2 …… High-order bus (1st
Bus B1), 3 …… Lower bus (second bus B2), 4 ……
RAM, 5 ... High-level bus side cache controller, 6
...... Bus controller, 7 ...... Snoop controller, 8 ...... Lower-order bus occupation determination device, 9 ...... Deadlock avoidance device.

Claims (1)

[Claims] 1. A plurality of first cache memory devices provided corresponding to each of a plurality of processors, and a plurality of upper-side buses interconnecting a plurality of these first cache memory devices. And a plurality of second cache memory devices respectively connected to the first cache memory device, and the second cache memory device via a lower-order bus interconnecting these second cache memory devices. In a hierarchical cache memory device including a main memory device connected to the second cache memory device, the second cache memory device receives the command from the upper bus and outputs the command to the lower bus. Determination means for determining whether or not the side bus is already occupied by another device, and this determination means determines that the lower side bus is occupied. When Rukoto is determined, hierarchical cache memory device which is characterized in that a remand means for releasing the bus of the upper side remand commands from the host side of the bus to the requester.