JPH06110844A - Decentralized shared memory type multiprocessor system - Google Patents

Abstract

PURPOSE:To reduce the traffic of a shared bus and to hold the consistency of a cache in a decentralized shared memory type multiprocessor system consisting of plural processors containing the CPUs, the cache memories, and the partial and shared control parts of a main storage which are connected together via the shared bus. CONSTITUTION:A shared control part 4 includes a main storage tag memory 27 which stores the information on a fact whether the address of its own main memory is stored (shared) in the cache memory of another processor or not (non-shared) and a cache state tag memory 24 which stores the information on a fact whether the data entry of the cache memory is updated and rewritten (dirty) in a shared memory or not (clean). Then a CPU gives an invalidating instruction onto a shared bus to assure the cache consistency as long as a main storage tag is shared when the CPU writes the information in its own main memory. Meanwhile the CPU gives nothing to the shared bus if the main storage tag is not shared and performs the processing in its own processor only. If the cache state tag is dirty to the access request given from another processor unit, the cache consistency is held via the access request.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an electronic computer, and more particularly to a tightly coupled multiprocessor system in which a plurality of CPUs are coupled by a bus.

[0002]

2. Description of the Related Art A shared memory type multiprocessor is shown in FIG.
Multiple processors (processor 1 to processor n) 1000-1 to 1000-n and shared memory 1000
It has a configuration in which -1 to 1000-m are coupled by a coupling path 1002 using a bus or a switch, and the memory can be equally accessed by all the processors. Therefore,
A parallel program can access without distinguishing the memory on the main memory, and when accessing a variable shared with another process, it does not care whether the process spans between processors. Can be accessed.

By the way, even with a parallel program, the program is not executed only by accessing the shared variables. Rather, the majority of memory accesses are accesses to the local variables of the program, and the access performance of the local variables has a great influence on improving the performance of the multiprocessor.

In the shared memory type multiprocessor of FIG. 1, even if an access is made to a local variable that is not shared by the processors, if a cache miss occurs, an access to the shared bus is issued in the same manner as an access to the shared variable. , Refill the cache by accessing the shared memory.
In this method, it is not necessary to distinguish whether variables are shared between processors or not when creating a parallel program, and there are few restrictions on program creation, but the access performance of local variables cannot be improved. .

In order to obtain high system performance with the tightly coupled multiprocessor, it is essential to reduce the traffic on the shared bus and to connect more processors. You must also use the shared bus to access variables,
There is a problem that it is practically difficult to combine a large number of processors.

In recent years, semiconductor integrated circuit manufacturing technology has made great strides, and to date, not only a central processing unit (CPU) of a general-purpose computer, but also a peripheral cache memory and a memory management unit (MMU) are provided. Became difficult to integrate on the chip. It is a so-called microprocessor chip. In the DRAM used for the main memory, a degree of integration of 4 to 16 megabits has been realized per chip, and research and development aiming at a higher degree of integration have been conducted. Taking advantage of these technologies, a small-sized computer called a workstation is integrated on one board including a controller for peripheral devices such as a disk and a LAN line. High performance has been realized by tightly coupling the memory and the CPU, and if attention is paid only to the processing performance of the CPU, it has come close to the general-purpose computer of the same generation. Thus, with today's technology, it is possible to mount the CPU and memory on the same substrate at a practical level.

FIG. 2 shows a configuration diagram of a distributed shared memory type multiprocessor in which memories are distributedly arranged on respective processor boards. In this configuration, the CPU and the memory are mounted on the same substrate, and the substrates 1010-1 to 1010-n are connected by the shared bus 1012 via the bus drive buffer. With this configuration, if the memory on the same board is assigned to the local variables, the local variables can be accessed without going through the shared bus. Then, the variable shared between the processors is placed in one of the main memories of the processors that share it and accessed using the shared bus.

However, existing parallel programs are not described by distinguishing between shared variables and local variables, and even in a newly created parallel program, it is a great limitation to distinguish and describe them. A microprocessor is used to mount a CPU and memory on the same board.
Many existing microprocessors do not have a means to access shared variables and local variables separately.

The behavior of the memory system is to convey that the access to the cache memory of the processor on another board is performed using the shared bus unless the access can be denied to the shared variable. Otherwise, it will not be possible to maintain consistency, and all access will need to be carried on the shared bus.

Therefore, even if such a configuration is used, there is a problem that the traffic of the shared bus is not reduced and the expandability of the system cannot be enhanced.

[0011]

In summary, in the conventional multiprocessor, since the operation of accessing the shared memory via the shared bus is performed for all accesses, the traffic of the shared bus increases and the system There was a problem that the expandability of could not be improved.

The present invention has been made to solve the above problems, and an object of the present invention is to provide a parallel program without restricting variable access.
To reduce unnecessary traffic on the shared bus and provide a multiprocessor system with high system expandability.

[0013]

In order to solve the above problems, the present invention provides a distributed shared memory type multiprocessor system comprising a plurality of processor units coupled via a shared bus. The unit is connected to the CPU via the internal bus and the main memory for storing a distributed part of the shared memory of the system, and the main memory via the internal bus to select the shared memory CP for caching data entries
U cache memory and main memory and C via internal bus
A shared management unit that is connected to the PU cache memory and interfaces between the internal bus and the shared bus.
A main memory tag means for storing the shared state of each data entry in the main memory indicating whether or not each data entry in the main memory on the unit is shared by the CPU cache memory on another processor unit; The execution of a write instruction to a data entry of the main memory by the CPU, the shared state of the data entry of the main memory tag means is that the data entry is a CPU cache memory on another processor unit. An invalidate instruction that instructs the other processor unit to invalidate the certain data entry in the CPU cache memory on the other processor unit when indicating that the other processor unit is shared. Instruction means issued on the bus,
A cache tag means for storing the address of the selected data entry stored in the CPU cache memory, and an invalidating instruction for a certain data entry from the shared bus, and the address of the certain data entry is given to the cache tag means. And a control means for invalidating the certain data entry in the CPU cache memory when stored.

Further, the present invention is a distributed shared memory multiprocessor system comprising a plurality of processor units coupled via a shared bus, wherein each processor unit has a CPU and an internal bus. A main memory connected to the CPU for storing a distributed portion of the system's shared memory, and a CPU cache memory connected to the main memory via an internal bus for caching selected data entries of the shared memory; A shared management unit that is connected to the main memory and the CPU cache memory via the internal bus and interfaces the internal bus and the shared bus.
Stores the cache state of each data entry in the CPU cache memory indicating whether each data entry in the U cache memory has been updated in the CPU cache memory on each processor unit and not written back to the shared memory. In response to an access request for a certain data entry from the cache state tag means and another processor unit received via the shared bus, the cache state of the certain data entry of the cache state tag means is the certain state. The data entry in main memory on the other processor unit when it indicates that the data entry has been updated in the CPU cache memory on each processor unit and not written back to shared memory. Interventions to intervene in access to and When you intervene in access to 該或 of main memory Ru data entry on the processor of said another,
The cache state of the certain data entry of the cache state tag means is changed from one cache state having the ownership of the certain data entry to another cache state not having the ownership of the certain data entry. When the access to the certain data entry from each of the processor units is made by the intervention means of the other processor unit, the cache state of the certain data entry of the cache state tag means is changed to the certain data entry. · From a cache state that does not have ownership of the entry, the certain data
And a control means for controlling the state transition to another cache state having the ownership of the entry.

Further, the present invention is a distributed shared memory type multiprocessor system comprising a plurality of processor units coupled via a shared bus, wherein each processor unit is connected to a CPU via an internal bus. A main memory connected to the CPU for storing a distributed portion of the system's shared memory, and a CPU cache memory connected to the main memory via an internal bus for caching selected data entries of the shared memory; A shared management unit that is connected to a main memory and a CPU cache memory via an internal bus and interfaces the internal bus and the shared bus. Each data entry of the main memory on each processor unit is on another processor unit. Shared state of each data entry in the main memory indicating whether or not it is shared in the CPU cache memory A main storage tag means for storing, C
Stores the cache state of each data entry in the CPU cache memory indicating whether each data entry in the PU cache memory has been updated in the CPU cache memory on each processor unit and not written back to the shared memory. Cache state tag means, C
In response to the execution of a read / write instruction for a certain data entry in the main memory by the PU, the shared state of the certain data entry in the main memory tag means is the certain data entry.
To read the certain data entry of the CPU cache memory on the other processor unit onto the shared bus when indicating that the entry is shared with the CPU cache memory on the other processor unit. A command means for issuing a read command for instructing the other processor unit on the shared bus, and a certain data of the cache state tag means for a read command received from another processor unit via the shared bus. Main memory on another processor unit when the cache state of the entry indicates that the data entry has been updated in the CPU cache memory on each processor unit and not written back to shared memory. An intervention means for intervening in accessing the certain data entry of Noto, a system consisting of.

Further, the present invention is a distributed shared memory multiprocessor system comprising a plurality of processor units coupled via a shared bus, each processor unit having a CPU and an internal bus. A main memory connected to the CPU for storing a distributed portion of the system's shared memory, and a CPU cache memory connected to the main memory via an internal bus for caching selected data entries of the shared memory; A shared management unit that is connected to the main memory and the CPU cache memory via the internal bus and interfaces the internal bus and the shared bus.
Stores the cache state of each data entry in the CPU cache memory indicating whether each data entry in the U cache memory has been updated in the CPU cache memory on each processor unit and not written back to the shared memory. In response to an access request for a certain data entry from the cache state tag means and another processor unit received via the shared bus, the cache state of the certain data entry of the cache state tag means is the certain state. The data entry in main memory on the other processor unit when it indicates that the data entry has been updated in the CPU cache memory on each processor unit and not written back to shared memory. Means for intervening in access to When, a system consisting of.

Further, in the system according to claim 4,
The sharing manager is a main memory tag means for storing the shared state of each data entry in the main memory on each processor unit, the shared state being the ownership of each data entry on each processor unit. [H] state indicating that each data entry exists on another processor unit, and [A] state indicating that the ownership of each data entry exists on another processor unit, and certain data in the main memory by the CPU. In response to an access request for an entry, when the sharing state of the certain data entry of the main memory tag means is the [A] state, the certain data entry of the CPU cache memory on the other processor unit is shared. An instruction means for issuing a read instruction on the shared bus instructing the other processor unit to read out on the bus.

[0018]

According to the first aspect of the present invention, whether or not the main memory tag means has the address of its own main memory in the cache memory of another processor (shared) or not (non-shared). ), The instruction means issues an invalidation instruction on the shared bus to guarantee cache coherency when the CPU writes to its own main memory when writing to its main memory. If it is shared, nothing is output on the shared bus, and processing is performed only within its own processor. Another processor having an address to be written in the cache memory uses the cache tag means having the information of the address in the cache memory to take out the invalidation instruction from the shared bus and invalidate it by the control means. I do. In this way, since the shared bus is not used when it is not shared,
Cache coherency can be achieved by reducing traffic on the shared bus.

According to the second aspect of the present invention, the control means changes the cache state of the cache state tag means so that the ownership is transferred from the intervention destination to the intervention source. Obligation to write back to the main memory does not have the data entry of the specified address in the main memory but has the data entry of the CPU cache memory from the intervention source board to the intervention destination board that has the data entry of the specified address in the main memory When the data is transferred and later written back is requested, the data entry at the specified address can be written back to the main memory from the CPU cache memory of the substrate in the main memory using only the internal bus.

According to the third aspect of the invention, the main memory tag means determines whether the address of its own main memory exists in the cache memory of another processor (shared) or not (shared). When storing / reading information from the main memory, the instruction means issues a read instruction on the shared bus to guarantee the coherency of the cache when the CPU reads / writes from the main memory. If it is shared, nothing is output on the shared bus, and processing is performed only within its own processor. The other processor having the address to be read in the cache memory determines whether the cache state tag means has the latest address in the cache memory and has not been written back to the main memory (dirty) (clean). )
Since this information is stored, the read-out instruction is picked up from the shared bus by the intervention means and the intervention is performed if the address is dirty. As described above, since the shared bus is not used when the shared bus is not shared, the traffic on the shared bus can be reduced and the cache coherency can be maintained.

According to the inventions of claims 4 and 5,
There are only two shared states of the main memory tag means, the [H] state and the [A] state. It is possible to reduce the memory capacity and cost, and the ownership can be known without waiting for the intervention on the shared bus, so that the traffic on the shared bus can be reduced.

[0022]

DESCRIPTION OF THE PREFERRED EMBODIMENTS To explain the outline of the present embodiment, it is a multiprocessor system in which processor boards in which a CPU, a cache memory, a main memory and a shared management unit are connected by an internal bus are connected by a plurality of shared buses. The unit stores, for each cache line of the main memory, a shared state indicating whether the cache line is shared with the cache memory of the processor on another board, and the address requested by the processor is the processor on the other board. It is determined whether or not it is shared with the cache memory of the CPU, the traffic on the shared bus is monitored, and the shared state is appropriately set according to the state transition of the entry affected by the traffic. CP of the cache line
The state on the cache memory of U is stored, and it is determined whether or not the operation of keeping consistency with the cache memory of the processor on the same board is necessary for the access request on the shared bus.
The traffic on the internal bus is monitored, and the cache state of the CPU cache is appropriately set according to the state transition of the cache memory of the CPU.

The access made by the CPU is output to the internal bus, and when accessing the memory on the same substrate, the memory on the same substrate is accessed.

At the same time, the sharing management unit interprets the address and determines whether the corresponding address is shared with the cache memory of the processor on another board. If the cache memory is not shared with other cache memories, the shared bus is not used and the request is satisfied by accessing the memory on the same substrate. That is, in this case, the access request can be satisfied without using the shared bus, and the traffic of the shared bus can be reduced. Meanwhile, the shared bus can process requests issued by other boards.

Even if the memory on the same board is accessed, if the shared management unit determines that the memory is shared with the cache memory of the processor on another board, the external access means is used simultaneously with the internal bus. The shared bus is also accessed to maintain coherency with cache memory on other boards.

If the requested address is a memory on another board, a shared bus is used to convey the access to the board with the required memory. On the board having the memory of the requested address, the address on the shared bus is determined, the memory is accessed, and the request on the shared bus is answered. At this time, the shared management unit on the board having the memory is set so as to indicate that the address is in a shared state with another board.

When the shared bus is accessed, the shared management units of all the other boards judge whether or not the corresponding address exists in the cache memory on their own boards. When the corresponding address exists, the sharing management unit responds to the access source that the corresponding address is shared. If none of the boards on the shared bus responds to the sharing, the sharing management unit of the accessed board sets the corresponding address to indicate that it is not shared. In this case, subsequent access can be performed without using the shared bus.

Further, the shared management unit estimates the state of the cache memory of the CPU, and when the address requested on the shared bus is updated in the cache memory or the request on the shared bus is sent to the shared variable. Only when it is determined that the operation for maintaining the consistency is necessary such as writing, the internal bus of the board is used to instruct the cache of the CPU of the operation necessary for maintaining the consistency.

The CPU access request issued on the internal bus is completed through the above process, and a response indicating whether or not the requested cache entry is shared with the cache of another processor is shown. Based on the, the cache of the CPU determines the state of that entry. The shared management unit monitors the traffic of the above series of internal buses, estimates the state transition of the CPU cache based on this, and
Set the cache state change of PU. As a result, the shared management unit can determine whether or not the operation of maintaining the consistency for the traffic on the shared bus is necessary without inquiring the cache of the CPU, and the CPU uses the internal bus for the processing. It is possible to prevent unnecessary interference associated with shared access.

An embodiment of a distributed shared memory type multiprocessor system according to the present invention will be described below with reference to the drawings.

FIG. 3 is an overall configuration diagram of a distributed shared memory type multiprocessor system according to the first embodiment of the present invention.
Each processor unit has a CPU 1, a cache memory 2, a main memory 3 and a shared management unit 4, and an internal bus 5
They are combined with each other and mounted on the same substrate. Each of the boards A, B, C, and D on which the processor unit is mounted is connected by a shared bus 6 on the backplane, and accesses the memory on another board via the shared management unit 4.

The CPU 1 has at least one type of read command and one or more type of write command for the memory, and executes the program according to the command sequence of the program.

FIG. 4 shows the internal structure of the cache memory 2. The cache memory 2 is a shared memory data memory for the entire multiprocessor, which is composed of the main memory on each board.
It has a copy of a part of the entry, and has a data storage unit 13 for storing the copy, an address tag unit 11 for storing the address of the copy on the main memory, and a state tag unit 12 for storing the state of the copy. . Although the data storage unit of the cache memory of this embodiment has a capacity of 1 megabyte, the capacity of the cache memory is not related to the effectiveness of the present invention.

Management of addresses and states is performed in blocks called cache lines. In the present embodiment, the cache line is assumed to be 64 bytes in the following description, but the effectiveness of the present invention is not lost if the size of this cache line is not less than the data length handled by the CPU. The cache memory of the present invention manages a cache line of 16 kilo lines.

The information stored in the status tag unit 12 is shared by other CPUs (shared / non-shared) and the CPU.
Consistency of shared memory, such as the rewriting status by whether the latest value is retained by the rewriting (dirty / clean) and the valid status (valid / invalid) of the cache line value. The cache control unit 17 controls the cache memory 2 so that the cache memory 2 operates as a cache memory of a shared memory that maintains coherency. The operation of such a cache memory is disclosed in Japanese Unexamined Patent Publication
-253356 and "Cache Coherence Protoc
ols: Evaluation Using a Multiprocessor Simulation M
odel ”, J.Archibald J.Bare, ACM Transaction on Com
Various methods are described in detail in, for example, puter Systems, Vol.4 No.4 Nov. 1986, but since they are not related to the essence of the present invention, they will not be described in detail here.

The cache memory of this embodiment has a copy-back type cache system and an invalidation-type consistency holding system.

The main memory 3 is a shared memory of the system dispersed on each substrate, and different addresses are assigned to each. That is, the address determines which substrate the main memory is accessed on. In the present embodiment, the following description will be made assuming that the capacity of the main memory is 64 megabytes, but the size of the capacity of the main memory is not related to the effectiveness of the present invention. Further, the effectiveness of the present invention is not impaired even if the capacity of the main memory differs for each substrate.

The internal bus 5 is used at the time of a cache miss or a coherency holding operation, and has the following commands. When transferring data, it is done in cache line units.

[CR:] (Coherent Read) Shared read. It is caused by a read miss of the CPU and reads data while maintaining consistency.

[CRI:] (Coherent Read and Invali
date) Exclusive read. It is generated by a write miss of the CPU, reads data, and invalidates the cache line of the same address on the cache memory of another board.

[CI:] (Coherent Invalidate) Invalidation request. It is generated by the shared write hit of the CPU and invalidates the cache line of the same address on the cache memory of another board. Alternatively, it occurs when an invalidation request from another processor is transmitted to the CPU cache via the shared management unit, and the corresponding entry in the CPU cache is invalidated. No data transfer is involved.

[WR:] (Normal Write) Write back. When the cache is replaced, it occurs when the cache line to be replaced is in a dirty state described later, and data is written.

The internal bus 5 has a command line 19 for transmitting these commands, a normal address line 20, and a data line 22.
In addition, it has a sharing instruction line 18 indicating whether or not the read data is shared with the cache memory of another substrate, and an intervention instruction line 21 indicating the presence or absence of intervention described later. The sharing instruction line of the internal bus is driven when it is determined that the sharing management unit of the board shares the sharing instruction line.

The shared bus 6 is used in the consistency maintaining operation and has the following commands. When transferring data, it is done in cache line units.

[RS:] (Read Shared) Shared reading. Read data with consistency.

[RM:] (Read Modified) Exclusive reading. Data is read while maintaining consistency, and the corresponding entry in the cache memory of another board is invalidated.

[INV:] (INValidate) Invalidation request. Invalidates the corresponding entry in the cache memory on another board.

[WB:] (Write Back) Write back. Write back across the processor boards. It is used when writing the rewritten data read to another board back to the main memory of the original board.

The shared bus 6 has a command line, an address line, a data line, and the like similar to the internal bus 5, and a shared instruction line indicating whether the read data is shared with the cache memory of another substrate, which will be described later. It has an intervention line that indicates the presence or absence of intervention. The shared instruction line of the shared bus is driven when the shared management unit of each board determines that the cache memory of the board has the specified cache line,
If any of the substrates is driven, it is determined that they are shared. Such a connection logic can be easily realized by connecting a wired or connected open collector type output logic circuit.

FIG. 5 is an internal block diagram of the sharing management unit 4, which is a characteristic part of this embodiment. The shared management unit has a storage capacity of 1 bit for one line of the main memory 3 and stores whether or not each line of the main memory exists in the cache memory of the processor on another board. Two
7 and the same storage capacity as the tag portion (address tag portion 11, state tag portion 12) of the cache memory 2,
A cache address tag memory 23, which stores the result of estimating the state of the cache memory, and stores the state of the address requested by the access on the shared bus in the cache memory of the processor on the same board. And a state tag memory 24. Then, an internal access control unit 29 that controls access on the internal bus 5
An external access control unit 28 for controlling access on the shared bus 6, a main storage tag memory control unit 26 for controlling reading / updating of the main storage tag memory 27, and a reading / updating of cache state tag memory 24. A cache status tag memory control unit 25 is provided.

The main memory tag memory 27 of this embodiment has a capacity of 1 megabit, and each bit corresponds to a case where the corresponding cache line of the main memory on the same board exists in the cache memory of another processor (state. G (Grobal)) has a value of 1, and if there is no copy in the cache memory of a board that has a copy only in the cache memory on the same board (state P (Private)), it takes a value of 0.

The state of the main memory tag memory 27 transits as follows under the control of the main memory tag memory control unit 26.

(1) The initial state is P.

(2) When there is an access request of RS or RM from another CPU via the shared bus to the entry of the corresponding cache line, the state G is entered.

(3) The INV or RM of the shared bus for the corresponding cache line entry is set in its own CPU
When issued from, transitions to state P.

The cache address tag memory 23 and the cache status tag memory 24 of this embodiment manage the information of the cache line of 16 kilo lines, which is the same as the tag portion of the cache memory. The information to be managed is the address in the main memory and the state in the system for each cache line in the cache memory. The cache line is in one of the following five states.

In the following description, "dirty" means that the cache line has been updated and the updated data has not been written back to the main memory, that is, the duty to write back to the main memory is obligatory. Clean is a state that does not have such an obligation. When a cache line is shared, only one of the caches is obliged to write back, so the cache that requested dirty line sharing is set to the shared clean state.

[M] Exclusive Dirty. No copy exists in other caches, data on this line has changed and needs to be written back to memory.

[O] Shared dirty. There may be copies in other caches. The data on this line has been modified and needs to be written back to memory.

[E] Exclusive clean. There are no copies in other caches. The data on this line has not been modified and need not be written back to memory.

[S] Shared clean. There may be copies in other caches. The data on this line has not been modified and need not be written back to memory.

(In the above four states, the cache line is valid.) [I] Invalid. This cache line is not valid.

The state of the state tag unit 12 of the cache memory 2 is summarized in the table of FIG. 6 under the control of the cache control unit 17 based on the instruction from the CPU and the command issued by the shared management unit to the internal bus. The state transitions as follows.

(1) The initial state is I.

(2) When the CPU reads from state I and indicates that the sharing instruction line of the internal bus is shared with another CPU, or from state E when another CPU passes the shared bus. When the shared read is performed by
Transition to.

(3) Transition from the state I to the state E when the own CPU reads and indicates that the sharing instruction line of the internal bus is not shared with other CPUs.

(4) When its own CPU writes, it transits to state M.

(5) Transition from state M to state O when another CPU performs shared reading via the shared bus.

(6) When another CPU issues an exclusive read request or an invalidation request via the shared bus, the state transitions to state I.

Further, the cache memory may be replaced from the state E or S, and the state may transit to the state I.

On the other hand, the state of the cache state tag memory 24 of the shared management unit 4 is controlled by the cache state tag memory control unit 25, and the cache control unit 17 performs the state transition as described above and issues a command to the internal bus. ,
Also, the state transitions as follows based on the command issued to the shared bus by the shared management unit of another board.

First, in the case of access to the main memory on the own board, the states transit as follows as summarized in the table of FIG.

(1) The initial state is I.

(2) When the main memory tag is G in the state I,
When its own CPU performs shared read via the internal bus and the shared instruction line of the shared bus is driven, or
When another CPU performs shared reading from the state E via the shared bus and there is no intervention from the cache, the state transits to the state S.

Here, the intervention means that when a value is read from the main memory and the latest value that has not been written back to the main memory exists in the cache memory, the cache memory reads the value on the bus. In response to a command, it refers to the operation of driving the intervention instruction line to stop reading from the main memory and sending the latest value that it has. This intervention is done via the internal bus when the main memory to be read and the cache memory with the latest values are on the same board, and when they are on different boards via the shared bus. Done.

(3) From state I, when its own CPU performs shared read via the internal bus and the shared instruction line of the shared bus is not driven, the state transits to state E. However, even if the status tag of the shared management unit is S, the status tag of the cache memory may have transited to I (due to cache replacement), and therefore the status S may transit to status E as well. .

(4) When its own CPU makes an exclusive read or invalidation request to invalidate the cache on another board, the state transits to the state M.

(5) When another CPU performs shared read from the state M via the shared bus, the state transits to the state O.
However, even if the status tag of the shared management unit is E, the status tag of the cache memory may have transitioned to M (due to a write hit). Therefore, other CPUs from the status E can perform shared reading via the shared bus. When there is an intervention from the cache (it can be seen that the state actually transits to M here), the state transits to the state O.

(6) When another CPU issues an exclusive read or invalidation request via the shared bus, the state transits to the state I. It also transits to the state I when the replacement is performed.

On the other hand, in the case of access to the main memory on another board, the states transit as follows as summarized in the table of FIG.

(1) The initial state is I.

(2) From state I, when its own CPU performs shared read via the internal bus and the shared instruction line of the shared bus is driven, or from state E, another CPU shares it via the shared bus. When reading is performed, the state transits to the state S. However, even if the state tag of the shared management unit is E, the state tag of the cache memory may have transitioned to I (due to cache replacement), so transition from state E to state S as in state I. Sometimes.

(3) From state I, when its own CPU performs shared read via the internal bus and the shared instruction line of the shared bus is not driven, the state transits to state E. However, even if the state tag of the shared management unit is S, the state tag of the cache memory may have transitioned to I (due to cache replacement), so transition from state S to state E as in state I. Sometimes.

(4) When the own CPU makes an exclusive read or invalidation request to invalidate the cache on another board, the state M is transited to.

(5) Transition from state M to state O when another CPU performs shared read via the shared bus.

(6) When another CPU issues an exclusive read or invalidation request via the shared bus, the state transits to the state I. It also transits to the state I when the replacement is performed.

Thus, as summarized in FIGS. 6 to 8, the cache memory and the shared management unit control the state transition and the commands issued on the bus, so that the state tag of the cache memory is excluded except for some exceptions. The insides of the cache state tag memory 24 of the unit 12 and the shared management unit are matched. Even if they do not match, no error will occur if the control is performed as described in the proviso above. Further, an error is prevented by devising driving of the sharing instruction line, which will be described later.

The operation of the sharing management unit of the first embodiment will be described below.

9 and 10 are flow charts showing the operations of the cache control unit 17 and the sharing management unit 4 of this embodiment in response to a read instruction from the CPU. When the CPU executes the read instruction and misses the cache memory (S1
No), issue a shared read CR on the internal bus (S
2). If the requested address is the address of the main memory on the same board (S3 Yes), the main memory on the same board responds (S4). At the same time, the internal access control unit 29 of the sharing management unit 4 interprets the request on the internal bus, searches the main memory tag memory 27 (S4), and determines whether the requested cache line of the main memory is shared. Do (S
5). If the sharing is not performed, the sharing management unit ends the operation, and the shared read CR of the internal bus ends by accessing only the main memory (S6, S7). This corresponds to the access of the local variable allocated on the main memory on the same board, and most of the accesses at the time of program execution are performed in this form. At this time, since access is performed without using the shared bus, it is possible to reduce traffic on the shared bus. Further, during this time, the shared bus can execute the access request of another board, so that the possibility of interfering with the execution of the processor of another board is reduced. The shared instruction line of the internal bus indicates non-shared.

When it is determined that the requested cache line is shared with the CPU cache on another board as a result of the search of the main memory tag memory (S5 Yes), the external access control unit 28 of the sharing management unit 4 is used. A shared read RS is issued on the shared bus via the through to perform coherency operation with the cache memory on another board. When the latest value (dirty line) exists in the cache memory on another board, the shared management unit of the board having that value intervenes and supplies the latest value. If the latest value does not exist in the cache memory of the board, the value of the cache line exists in the main memory, so the value supplied from the main memory is supplied to the cache memory (above S8).
At this time, the state of the main memory tag memory is reset according to the value of the sharing instruction line on the shared bus (S9). As a result, it is possible to detect if sharing has been canceled between the last access and the current access. The shared instruction line of the internal bus transmits the state of the shared instruction line of the shared bus (S1).
0).

If the shared read address issued on the internal bus is the address of the main memory on another board (S3
No), the sharing management unit 4 makes a shared read RS on the shared bus.
Is issued and an operation for maintaining consistency is performed (S11).
The substrate having the main memory of the requested address responds to the shared read RS, sets the state of the main memory tag memory of the shared management unit to G, and stores that sharing is started. The sharing instruction line of the internal bus indicates sharing regardless of whether the sharing instruction line of the shared bus is shared or not (S12).

The cache line read out as described above is stored in the cache memory, and the state of the cache line is set to state S (S15) when the sharing instruction line of the internal bus indicates sharing (non-shared). If so, the state E is set (S14). The cache status tag of the shared management unit sets the state to S or E according to the value indicated by the shared instruction line of the shared bus.

What should be noted here is the difference between S10 and S12. This is a device for preventing the error described above, and when the main memory on another board is read and the sharing instruction line of the shared bus indicates non-shared, the cache status tag of the shared management unit is set to the status E. However, since the shared management unit shares the shared instruction line of the internal bus even though the shared instruction line of the shared bus indicates non-shared, the cache of the CPU is set to the state S. If the state of the CPU cache is set to E, even if writing is made to this entry, the CPU does not issue the invalidation request but transits to the state M, and the cache state tag of the shared management unit rewrites. It cannot be recognized, and the subsequent read request on the shared bus cannot be correctly answered. In the present embodiment, this problem is avoided by intentionally making the state of the CPU cache different from the state of the cache state tag of the shared management unit. CPU
If the cache state is S, the CPU cache issues an invalidation request to the internal bus at the time of writing, so that the sharing management unit can recognize the writing. In this case, since the cache status tag is the status E, it is understood that it is not necessary to transmit the invalidation request on the internal bus to the shared bus.
It does not increase traffic on the shared bus.

FIG. 11 is a flow chart showing the operation of the cache control unit 17 and the sharing management unit 4 of this embodiment in response to the CPU write command. When the CPU executes the write command and misses the cache memory (S21
Miss), issues an exclusive read CRI on the internal bus (S32). If the requested address is the address of the main memory on the same board (S33 Yes), the main memory on the same board responds. At the same time, the internal access control unit 29 of the sharing management unit interprets the request on the internal bus, searches the main memory tag memory 27 (S34), and determines whether or not the requested cache line of the main memory is shared. (S
36). If sharing is not performed, the sharing management unit ends the operation, and the exclusive read CRI of the internal bus ends by accessing only the main memory (S39). This corresponds to writing to a local variable allocated on the main memory on the same substrate, and most of the accesses at the time of program execution are performed in this form. At this time, since access is performed without using the shared bus, it is possible to reduce traffic on the shared bus. Further, during this time, the shared bus can execute the access request of another board, so that the possibility of interfering with the execution of the processor of another board is reduced.

When it is determined that the requested cache line is shared with the CPU cache on another board as a result of the search of the main memory tag memory (Yes at S36), the external access control unit 28 of the sharing management unit is used. An exclusive read RM is issued on the shared bus, and an operation for maintaining coherency with a cache memory on another board is performed (S37). If the latest value exists in the cache memory on another board, the shared management unit of the board having that value intervenes and supplies the latest value. If the latest value does not exist in the cache memory of any board, the value of the cache line exists in the main memory, so the value shared from the main memory is shared with the cache memory. At this time, the cache memories on the other boards are invalidated, and only the cache memories that issued the exclusive read RM have exclusive copies. Therefore, the main memory tag memory is set to the state P (S38).

Exclusive read CRI issued on internal bus
Is the address of the main memory on another board (S33, No), the shared management mechanism issues an exclusive read RM on the shared bus and performs an operation for maintaining consistency (S).
35). The substrate having the main memory of the requested address responds to the exclusive read RM, sets the state of the main memory tag memory of the sharing management unit to G, and stores that sharing is started.

The cache line read as described above is stored in the cache memory and updated by the write command of the CPU. The state of the cache line is set to M (S40), and accordingly, the cache state tag of the shared management unit is also set to state M.

Even if the CPU executes the write command and hits the cache memory, if the state of the cache line is shared (the state of the state tag unit 12 is S or O) (S2
1 shared hit), it is necessary to invalidate another copy on the cache memory, and an invalidation request CI is issued on the internal bus (S22). The internal access control unit of the shared management unit interprets the request on the internal bus, and if the requested address is the address of the main memory on the same board (S23Ye).
s) The invalidation request INV is issued on the shared bus through the shared bus control unit of the shared management unit to invalidate the cache memory entry on another board (S26). Then, the main memory tag memory is set to the state P (S27).

If the address of the invalidation request CI issued on the internal bus is the address of the main memory on another board (S
23 No), the shared management unit is the cache status tag memory 2
4 is checked (S28) and if the state is shared (S or O) (S29 Yes), an invalidation request INV is issued on the shared bus to invalidate the cache memory entry on another board (S30). Since the entry of the request source remains without being invalidated, the state of the main memory tag memory of the shared management unit on the substrate having the main memory is left as G to store that the sharing is continued. If the state is S in S28 (S2
No. 9), the invalidation request CI on the internal bus indicates that a write hit has occurred in the CPU cache (invention described above), and therefore no command is transmitted to the shared bus.

The cache line invalidated as described above is updated by the write command of the CPU, and the state of the cache line is set to M (S31). In response to this, the cache status tag of the shared management unit is also set to the status M.

The external access control units 28 of the shared management units 4 of all the boards monitor the traffic on the shared bus, and depending on the state of the cache state tag corresponding to the command on the shared bus, the following consistency is obtained. Performs sex retention operation.

FIG. 12 shows a shared read RS on the shared bus 6.
9 is a flowchart showing the operations of the sharing management unit 4 and the cache control unit 17 for the. In the case of the board having the main memory of the designated address (S41 Yes), the shared read CR is issued to the internal bus to access the main memory (S42). At this time, if the status of the corresponding status tag unit 12 of the cache memory is I or S, the CPU
Since it is not necessary to read the latest value from the cache memory of the
It is also possible to simply read the main memory without issuing R. Then, the main memory is read, but if the state of the cache memory is M or O, intervention is performed (S43). When writing in the state E, the CPU cache memory transits to the state M without issuing a command to the internal bus, and therefore the shared management unit cannot recognize this transition. Therefore, even if the state of the cache state tag is E, the state of the cache memory of the CPU may remain M, and the command issued to the internal bus is the shared read C
Must be R.

As a result of the shared read CR, the state of the state tag unit 12 of the CPU cache memory is changed by the cache control unit 17 to O for M or O, E for S or S, and I for I (S44). ). In accordance with this, the state of the cache status tag memory 24 of the shared management unit is: M, O, or E if cache intervention occurs, S for O, or E if cache intervention does not occur for S, E If it is I, transition to I is made (S45). Further, the main memory tag memory of the sharing management unit is set to G (S46).

The sharing instruction line of the internal bus indicates non-shared if the CPU cache memory is in the state I, and indicates sharing otherwise, and this value is transmitted to the sharing instruction line of the shared bus and is also transmitted from the main memory or the cache memory. The read value is output to the shared bus (S47).

When the board does not have the main memory of the specified address (No in S41), the use of the internal bus is determined according to the status of the corresponding cache status tag (S4).
8, S49). When the state is I, there is no valid copy in the cache memory on this board, so the operation for maintaining coherency is unnecessary and the shared instruction line is not driven. If the state is other than I, the shared instruction line is driven because it has a valid copy (S52, S54). If the state is M or O, the latest value exists in the cache memory of the CPU, so the shared read CR is issued to the internal bus to read the latest value from the cache memory and the intervention instruction line of the shared bus indicates the intervention. , The value is shared instead of the main memory on another board (S50, S52). When the status is other than M or O, the internal bus is not accessed.

The status tag of the CPU cache memory is M
Alternatively, if it is O, the cache status tag of the shared management unit transits to O (others remain unchanged), and if M or O, transits to O (S51).

FIG. 13 is a flow chart showing the operation of the sharing management unit 4 and the cache control unit 17 for the exclusive read RM on the shared bus. In the case of the board having the main memory at the designated address (Yes in S61), the exclusive read CRI is issued to the internal bus to access the main memory (S62). Along with the execution of this exclusive read CRI (S63, S65), the state of the CPU cache memory and the state of the cache state tag of the shared management unit are I.
Transition to. In addition, the main memory tag memory of the shared management unit is G
Is set (S64).

When the board does not have the main memory of the designated address (S61 No), the use of the internal bus is determined according to the state of the corresponding cache state tag (S6).
6, S67). When the state is I, since a valid copy does not exist in the cache memory on this board, the operation for maintaining the coherency is unnecessary and the command is not issued to the internal bus. If the status is S or E, the invalidation request C
I is issued to the internal bus (S71). State is M or O
In this case, since the latest value exists in the cache memory of the CPU, the exclusive read CRI is issued to the internal bus to read the latest value from the cache memory, and the intervention instruction line of the shared bus indicates the intervention to invalidate the cache. (S68). The read value is supplied to the request source instead of the main memory (S70). Both the state of the CPU cache memory and the state of the cache state tag of the shared management unit transit to I (S69, S72).

FIG. 14 is a flowchart showing the operation of the sharing management unit 4 and the cache control unit 17 in response to the invalidation request INV on the shared bus. If the state of the cache state tag corresponding to the designated address is not I (S8
1, S82). Issue an invalidation request CI to the internal bus, and
The valid entry in the cache memory of the PU is invalidated (S83). The state of the CPU cache memory and the state of the cache state tag of the shared management unit transit to I, and the state of the main memory tag is set to G in the case of the processor board having the main memory to which the requested address is assigned. (S
84).

In response to the write-back WB on the shared bus, only the substrate having the main memory responds, and the sent value is fetched and written back to the main memory. The other board ends the operation without responding.

An example of the operation of this embodiment will be shown below by using an example. FIG. 15 is a block diagram of an example. Here, 0x at the head of the address indicates that it is a hexadecimal number.

The processor board PB ₀ has the address 0x0000 0
It has a main memory M ₀ of 000 to 0x03ff ffff, and the processor board PB ₁ has addresses 0x0400 0000 to 0x07ff ffff.
The main memory has a M _1, the processor board PB ₂ has a main memory M ₂ of 0X0bff ffff from the address 0x0800 0000, processor board PB ₃ from the address 0x0C00 0000 of
It has a main memory M ₃ of 0x0fff ffff.

The cache line of address 0x0000 1000 exists in the main memory M ₀ of the processor board PB ₀ , but does not exist in the cache memory of any processor. Therefore, the state of the corresponding main memory tag memory MTag ₀ is P.

[0114] address 0x0400 2000 of the cache line is in main memory M ₁ of the processor board PB _1, present in the state E to the cache memory C ₁ processor board PB _1. Therefore, the state of the corresponding main memory tag memory MTag ₁ is P.

FIG. 16 shows the CPU of the processor board PB ₀ .
(CPU ₀ ) reads address 0x0000 1000 (1)
It shows the operation at the time. Cache C ₀ of the processor board PB ₀ undergoes a read miss (2), issues a shared read CR to internal bus B ₀ of the processor board PB ₀ (3). Since the main memory tag memory MTag ₀ of the processor board PB ₀ is in the state P, the shared bus SB is not accessed (5) and the main memory M of the processor board PB ₀ is not accessed.
₀ is read and (6) stored in the cache C ₀ , and the CPU
A value is supplied to (CPU ₀ ) (8).

The cache memory C ₀ and the cache status tag memory CTag ₀ of the processor board PB ₀ transit to the status E (4) (7). After that, C of the processor board PB ₀
A read from PU (CPU ₀ ) hits cache C ₀ and there is no request on internal bus B ₀ .

FIG. 17 shows the processor board PB from this state.
₀ of CPU (CPU ₀₎ indicates an operation when has been written to the address 0x0000 1000 (1). Cache C ₀ of the processor board PB ₀ undergoes a write hit (2), without accessing the internal bus B _0, a transition state to M (3). Thereafter, until evicted from the cache C _0, processor board PB ₀ of CPU (CPU
Both read and write accesses from ₀ ) hit the cache C ₀ and no request is made to the internal bus B ₀ (4). In this way, local variables on the same substrate are shared bus S
It can be accessed without using B. Although cache state tag CTag ₀ shared management unit S ₀ remains remain E, does not cause problems since the shared read in relation to accessing the main memory M ₀ is the time of performing a shared read. If the shared reading is performed from another processor board via the shared bus SB, the mismatched state is resolved.

FIG. 18 shows the CPU of the processor board PB ₀ .
(CPU ₀ ) reads address 0x0400 2000 (1)
It shows the operation at the time. Cache C ₀ of the processor board PB ₀ undergoes a read miss (2), issues a shared read CR to internal bus B ₀ of the processor board PB ₀ (3). Since this address is not the main memory M ₀ of the processor board PB ₀ , the shared read RS is issued on the shared bus SB (4).

The processor boards PB ₁ to PB ₃ start the operation by seeing the shared read RS on the shared bus SB.
The processor boards PB ₂ to PB ₃ terminate the operation because the cache status tags CTag ₂ and CTag ₃ are invalid state I (5). Since the processor board PB ₁ has the main memory M ₁ at the requested address and the cache state tag CTag ₁ is in state E, the shared read CR is issued to its internal bus B ₁ (6), and the main memory M ₁ becomes the cache line. Supply the value (7). At this time, the CPU cache C ₁ of the processor board PB ₁ recognizes that sharing is started, and the status E
Transition from S to S (8). In addition, the processor board PB ₁
The cache state tag CTag _{1 of the above is} also transited to the state S, and the main memory tag MTag ₁ thereof is transited to the state G (8).

The read cache line is supplied to the processor board PB ₀ via the shared bus SB (9). At this time, the sharing instruction line of the shared bus SB indicates sharing. Cache state tag CTag ₀ of the processor board PB ₀ sets the state to S (10), internal bus B ₀
CPU cache C while instructing sharing to the sharing instruction line
_{The value} of the cache line is supplied to ₀ (11). CPU
The cache C ₀ becomes the state S (12), and the value of the cache line is read from the CPU cache C ₀ to the CPU (CPU ₀ ) (13).

FIG. 19 shows the processor board P from this state.
The operation when the CPU of B ₀ (CPU ₀ ) writes to the address 0x0400 2000 (1) is shown. Cache C ₀ of the processor board PB ₀ can cause shared hit (2), issues an invalidate request CI to an internal bus (3).
Because sharing management unit S ₀ of the processor board PB ₀ is not the address of the main memory M ₀ on the same substrate, issues an invalidate request INV to the shared bus SB (4).

The processor boards PB ₁ to PB ₃ start the operation upon seeing the invalidation request INV on the shared bus SB.
The processor boards PB ₂ to PB ₃ terminate the operation because the cache status tags CTag ₂ and CTag ₃ are invalid state I (5). The processor board PB ₁ has a cache status tag C
Since Tag ₁ is in state S, the invalidation request CI is transmitted to the internal bus B ₁ (6). CPU cache C ₁ processor board PB ₁ is a state transition by the disabled Kayo 2CI to I (7), the cache status tag CTag ₁ also transitions to state I (8) is the main memory tag Mtag ₁ state It remains G. When the invalidation of the processor board PB ₁ is completed, the cache state tag CTag ₀ of the processor board PB ₀ transits to the state M (9), and the state of the CPU cache C ₀ also transits to M (10) writing to the cache C ₀ . Is performed (11).

FIG. 20 shows the processor board P from this state.
The operation when the CPU of B ₁ (CPU ₁ ) reads data at address 0x0400 2000 (1) is shown. Cache C ₁ processor board PB ₁ causes a read miss (2), issues a shared read CR to internal bus B ₁ (3). Although sharing management unit S ₁ of the processor board PB ₁ is a main memory M ₁ address the same substrate, a main memory since tag Mtag ₁ state is a G access main memory M ₁ (4) simultaneously with the shared bus SB Also, the shared read RS is issued (4).

Processor boards PB ₀ and PB ₂ to PB ₃
Starts the operation by looking at the shared read RS on the shared bus SB, but the processor boards PB ₂ to PB ₃ terminate the operation because the cache state tags CTag ₂ and CTag ₃ are in the invalid state I (5). Since the cache status tag CTag ₀ is in the state M, the processor board PB ₀ intervenes in the request (6).
At this point, the access to the main memory M ₁ of the processor board PB ₁ is suspended (7). Shared management section S of the processor board PB _{0 0} issues a shared read CR to internal bus B ₀ (8), retrieving the value of the cache line from the CPU cache C _0. This shared read CR causes the CPU cache C ₀ to change its state to O (9). Shared management section S of the processor board PB _{0 0} transitions the cache state tag CTag ₀ state O with placing the value of the read cache line to the shared bus SB (10).

[0125] with return sharing management unit S ₁ flies had a value of the processor board PB ₁ to internal bus B _1, transits the state of the cache status tag CTag ₁ to S (11). The CPU cache C ₁ of the processor board PB ₁ is the main memory M
Instead of the old value of _1, the value of the new cache line updated by the processor board PB ₀ supplied by the shared management unit S ₁ is fetched into the cache C ₁ and the state is set to S (1
2) From this CPU cache C ₁ to CPU (CPU ₁ )
The value of the cache line is read (13). Read processor board PB ₁ is the result of the write done by processor board PB ₀ is reflected by the above operation,
Coherency between caches is maintained.

FIG. 21 shows the processor board P from this state.
The operation when the CPU (CPU ₂ ) of B ₂ performs reading (1) at the address 0x0400 2000 is shown. Cache C ₂ processor board PB ₂ causes a read miss (2), issues a shared read CR to an internal bus B ₂ (3). Because sharing management unit S ₂ of the processor board PB ₂ is not the main memory M ₂ addresses the same substrate, the shared bus S
The shared read RS is issued to B (4).

Processor boards PB ₀ to PB ₁ and PB ₃
Starts the operation by seeing the shared read RS on the shared bus SB, but the processor board PB ₃ is the cache state tag C
Since Tag ₃ is in the invalid state I, the operation ends (5). The processor board PB ₁ is the main memory M ₁ of the requested address.
Therefore, the shared read CR is issued to the internal bus B ₁ to access the main memory M ₁ (6). In the processor board PB _0, the cache status tag CTag ₀ is in the status O.
So intervene in the request (7). At this point, access to the main memory M ₁ of the processor board PB ₁ is interrupted (8). Shared management section S of the processor board PB _{0 0 issues} a shared read CR to internal bus B _0, retrieving the value of the cache line from the CPU cache C ₀ (8). Shared management section S of the processor board PB _{0 0} is placed the value of the read cache line to the shared bus SB.

[0128] common control section S ₂ of the processor board PB _2, along with returns the resulting value to an internal bus B _2, transits the state of the cache status tag CTag ₂ to S (9). The CPU cache C ₂ of the processor board PB ₂ has an internal bus B ₂
Fetches the value returned to and sets the state to S (1
0). This value is not the old value of the main memory M ₁ of the processor board PB _1, since it is the new value that has been updated by the processor board PB _0, the result of the write done by processor board PB ₀ are reflected, shared to Coherency between caches is maintained between the processor boards PB ₀ and PB ₂ that are present.

FIG. 22 shows the CPU of the processor board PB ₀ .
(CPU ₀₎ is, to the address 0x0000 1000, has a cache memory C ₁ on the processor board PB ₁ is the cache line of the address in the state O, the cache memory C ₂ on the processor board PB ₂ is the address cache Hold the line in state S and put the processor board PB ₀
When the above main memory tag MTag ₀ indicates that the shared state of the cache line of this address is the state G,
The operation at the time of writing (1) is shown. Cache memory C ₀ of the processor board PB ₀ undergoes a write miss (2), exclusive read CRI to internal bus B ₀
Is issued (3). This address is the processor board PB
_Although it is assigned to the main memory M ₀ on ₀ , the shared state indicated by the main memory tag MTag ₀ on this processor substrate PB ₀ is the state G, so this processor substrate PB ₀
The shared management unit S ₀ accesses the main memory M ₀ (4)
At the same time, the exclusive read RM is issued to the shared bus SB (4).

The processor boards PB ₁ to PB ₃ start the operation by seeing the exclusive read RM on the shared bus SB.
The processor board PB ₃ ends its operation because the cache status tag CTag ₃ is in the invalid state I (5). Since the cache status tag CTag ₁ is in the state O, the processor board PB ₁ issues an exclusive read CRI to the internal bus B ₁ thereof and intervenes the request from the shared bus SB (6), and the main memory M on the processor board PB _0. The access of ₀ is interrupted (7), and at the same time, the cache line of this address is read from the cache memory C ₁ on the processor board PB ₁ to the shared bus SB. Since the cache status tag CTag ₂ is in the state S, the processor board PB ₂ has its internal bus B ₂
The invalidation request CI is issued to (6).

[0131] Accordingly, the cache memory C ₁ processor board PB ₁ transits the state to I (7), the cache memory C ₂ processor board PB ₂ even state transitions to I (7), of the address Invalidate the cache line. This併I, cache status tag CTag ₁ processor board PB ₁ is also a transition to state I (8), the cache status tag of the processor board PB ₂ CTag ₂ also transition to state I (8).

When the invalidation of the processor boards PB ₁ and PB ₂ is completed, the cache status tag CTag ₀ of the processor board PB ₀ transits to the state M and the main memory tag MTag ₀ transits to the state P (9). Then, the cache memory C ₀
State changes to state M (10), and the cache memory C
Writing is performed on ₀ (11).

Next, a distributed shared memory type multiprocessor system according to a second embodiment of the present invention will be described.

This second embodiment is an improvement of the first embodiment regarding transfer of ownership between different processor boards. Here, ownership is the latest value written from the cache to the main memory. Means you have to return.

In this embodiment, the shared bus 6 is further provided with a request source identification line for identifying the processor board which is the request source of the memory access request on the shared bus 6.

When a CPU 1 on one processor board executes a read command for an address assigned to the main memory on the same board and a read miss occurs in the cache memory 2, the cache memory 2 on another processor board If it has the latest value of this address, this other processor board will intervene as in the first embodiment.

In the first embodiment described above, even in such a case, the ownership is left to the other processor board which is the intervention source, so that when the write-back is requested later, this other processor board is set to the certain processor board. Writeback must be done to the main memory of the board via the shared bus 6.

On the other hand, in the second embodiment, at the time of intervention, the ownership as well as the latest value is transferred from the other processor board to the certain processor board, and the later write back is performed only within the certain processor board. Therefore, it can be performed without using the shared bus 6.

In order to transfer the ownership like this, in the second embodiment, the memory access request on the shared bus 6 is accompanied by the information indicating the request source processor board on the request source identification line. . This information may be the board identification number of a normal bus, but it is enough to indicate whether the requesting processor board is the processor board having the main memory to which the specified address is assigned. Therefore, it may be given as a 1-bit signal indicating this.

Here, in the processor board of the request source that has the main memory to which the specified address is assigned and has received the intervention, the cache memory 2 takes ownership along with the latest value via the shared bus 6. Since the cache state is received, the cache state of the cache memory 2 is set to the state O, and the cache state of the cache is set to the state S in another processor board that has performed the intervention.

Therefore, the state transitions of the cache state tag unit 12 of the cache memory 2 are summarized in FIG. 23 in place of those summarized in FIG. 6, while the state transitions of the cache state tag memory 24 of the shared management unit 4 are performed. Is shown in FIG. 24 instead of the one shown in FIG. 7 when accessing the main memory on its own processor board, and is shown in the above figure when accessing the main memory on another processor board. Instead of the one summarized in FIG. 8, the one summarized in FIG.

Further, in the second embodiment, the cache control unit 17 and the sharing management unit 4 for the read instruction of the CPU.
2 is a flowchart showing the operation of FIG.
Change it to 6,27.

That is, after the end of the consistency holding operation in S8, it is determined whether or not there is an intervention in this consistency holding operation (S16). If not, the process proceeds to S9 as in the case of FIGS. If so, the intervention instruction line of the internal bus 5 is driven (S17), and the state of the CPU cache is set to the state O (S18). Other than this, the same as in FIGS.

Further, the flowchart of FIG. 12 showing the operations of the sharing management unit 4 and the cache control unit 17 for the shared read RS on the shared bus 6 is modified as shown in FIG.

That is, after S50, it is determined whether or not the access is from the processor board having the main memory to which the requested address is assigned (S55). If not, the process proceeds to S51 as in the case of FIG. If so, the CPU cache memory status tag is M or O.
If so, the cache state tag of the shared management unit is changed to S (others are unchanged), and if M or O, the cache state tag is changed to S (S56), and the process proceeds to S52. Other than this, the same as in FIG.

FIG. 29 shows the CPU of the processor board PB ₀ .
(CPU ₀₎ is shows the operation when data is read out to the address 0x0000 0000, which is updated in the cache memory C ₁ on the processor board PB _{1 (1).}
Cache memory C ₀ of the processor board PB ₀ undergoes a read miss (2), a shared read C to the internal bus B ₀
Issue R (3). This address is the processor board P
Although what was being assigned to the main memory M ₀ on B _0, the main memory tag on the processor board PB ₀ Mtag ₀
Since the shared state indicated by is the state G, the shared management unit S ₀ of the processor substrate PB ₀ accesses the main memory M ₀ (4) and issues the shared read RS to the shared bus SB (4).

The processor boards PB ₁ to PB ₃ start the operation by seeing the shared read RS on the shared bus SB.
Processor boards PB ₂ and PB ₃ are cache status tag C
Since Tag ₂ and CTag ₃ are in the invalid state I, the operation ends (5). The processor board PB ₁ has a cache status tag C
Since Tag ₁ is in the state M, the shared read CR is issued to the internal bus B ₁ and the request from the shared bus SB is intervened (6), and the cache line of this address is transferred from the cache memory C ₁ on the processor board PB _1. Read (7). At this time, the cache state of the cache memory C ₁ changes from M to S.

[0148] Thus, the access of the main memory M ₀ on the processor board PB ₀ is interrupted (7), the latest values shared bus S read from the cache memory C ₁
It is transferred to the processor board PB ₀ via B (8).
At this point, the cache state of the cache state tag memory CTag ₁ transits from M to S (8).

Next, in the processor board PB ₀ ,
The cache state of the cache state tag memory CTag ₀ changes from I to O (9), indicating that ownership has been transferred. The data transferred via the shared bus SB is cached in the cache memory C ₀ (10), and the cache state of the cache memory C ₀ also changes from I to O, indicating that the ownership has been transferred. The latest value is read from the cache C ₀ to the CPU (CPU ₀ ) (11).

Next, a distributed shared memory type multiprocessor system according to a third embodiment of the present invention will be described.

In the third embodiment, the cache states used in the cache state tag unit 12 of the cache memory 2 and the cache state tag memory 24 of the shared management unit 4 in the first embodiment are M, E, S, and I states. Limited to state O
It is an improvement that omits.

In an actual circuit, since each cache state is represented by a binary bit, it is desirable to set the number of cache states to a range of 2. Therefore, the cache state is set to 4 states as in the third embodiment. By limiting, the cache state tag unit 12 and the cache state tag memory 24 can be easily realized.

As the cache memory coherency holding method using only four states, there are two methods of Berkeley method and Illinois method.
Although the method is known, in the present embodiment, description will be made assuming that the Illinois method is applied. However, the Berkeley method can be similarly used.

In the Illinois system, the main memory 3 has a so-called reflective function. This is a function of writing the data transferred to the internal bus by the intervention to the main memory 3 instead of interrupting the read operation of the main memory 3 when the intervention occurs during the shared reading of the main memory 3. According to this function, the intervening cache fulfills the write-back obligation at the same time as the intervention, so that the state O (shared dirty) indicating the existence of the ownership is unnecessary.

Therefore, the state transition of the cache state tag memory 24 of the shared management unit 4 is summarized in FIG. 30 in place of the one summarized in FIG. 7 when accessing the main memory on the processor board. Therefore, when accessing the main memory on another processor board, the one summarized in FIG. 31 is replaced with the one summarized in FIG.

FIG. 32 shows the CPU of the processor board PB ₁ .
(CPU ₁₎ is shows the operation when data is read out to the address 0x0000 1000, which is updated in the cache memory C ₀ on the processor board PB ₀ (1).
Cache memory C ₁ processor board PB ₁ undergoes a read miss (2), a shared read C the internal bus B ₁
Issue R (3). This address is the processor board P
Since not assigned to the main memory M ₁ on B _1, sharing management unit S ₁ of the processor board PB ₁ issues a shared read RS to the shared bus SB (4).

Processor boards PB ₀ and PB ₂ to PB ₃
Starts the operation by looking at the shared read RS on the shared bus SB, but the processor boards PB ₂ and PB ₃ terminate the operation because the cache state tags CTag ₂ and CTag ₃ are in the invalid state I (5). Since the cache status tag CTag ₀ is in the state M, the processor board PB ₀ issues the shared read CR to the internal bus B ₀ to read the cache line of this address from the cache memory C ₀ (6) and the internal bus B _0. Drive the intervention instruction line of (6) to intervene in this memory access. At this time, the cache memory C ₀ changes its cache state from M to S.

[0158] Thus with the access of the main memory M ₀ on the processor board PB ₀ is interrupted (7), is achieved obligation writeback latest value of the cache memory C ₀ is written in the main memory M _0, The latest value is transferred to the processor board PB ₁ via the shared bus SB. At this point, the cache state tag memory CTag ₀ changes its cache state from M to S, and the main memory tag memory MTag ₀ changes its shared state from P to G (7).

Next, in the processor board PB ₁ ,
Cache state tag memory CTag ₁ transitions to S cache status from the I (8), data transferred through the shared bus SB is cached in the cache memory C _1, the cache memory C ₁ in a cache state from I S
(9). From this cache C ₁ to CPU (C
The latest value is read to PU ₁ ).

FIG. 33 shows the CPU of the processor board PB ₁ .
(CPU ₁₎ is shows the operation when attempts writing to address 0x0000 1000 that has been updated in the cache memory C ₀ on the processor board PB ₀ (1).
Cache memory C ₁ processor board PB ₁ undergoes a write miss (2), exclusive read C to the internal bus B ₁
Issue RI (3). Since this address is not allocated to the main memory M ₁ on the processor board PB _1, sharing management unit S ₁ of the processor board PB ₁ issues an exclusive read RM to the shared bus SB (4).

Processor boards PB ₀ and PB ₂ to PB ₃
Starts the operation by looking at the exclusive read RM on the shared bus SB, but the processor boards PB ₂ and PB ₃ end the operation because the cache status tags CTag ₂ and CTag ₃ are in the invalid state I (5). Since the cache state tag CTag _{0 of the} processor board PB ₀ is the state M, the exclusive read CRI is issued to the internal bus B ₀ to read the cache line of this address from the cache memory C ₀ (6) and the internal bus B _0. The intervention instruction line of is driven (6) to intervene in this memory access. At this time, the cache memory C ₀ changes its cache state from M to I.

[0162] Thus, the access is interrupted in the main memory M ₀ on the processor board PB ₀ (7), the latest values are transferred to the processor board PB ₁ via the shared bus SB. The latest value is the processor board PB
_Since it is rewritten by ₁ , it is not necessary to write in the main memory M ₀ . At this point, cache status tag memory CTag
_{In 0,} the cache state transits from M to I, and in the main memory tag memory MTag _0, the shared state transits from P to G (7).

Next, in the processor board PB ₁ ,
Cache state tag memory CTag ₁ transitions to M cache status from the I (8), data transferred through the shared bus SB is cached in the cache memory C _1, the cache memory C ₁ in a cache state from I M
(9). CPU for this cache C ₁
(CPU ₁ ) writes.

FIG. 34 shows the CPU of the processor board PB ₂ .
(CPU ₂₎ is shows the operation when data is read out to the address 0x0000 1000, which is updated in the cache memory C ₁ on the processor board PB _{1 (1).}
Cache memory C ₂ processor board PB ₂ undergoes a read miss (2), a shared read C to an internal bus B ₂
Issue R (3). This address is the processor board P
Since not assigned to the main memory M ₂ on B _2, sharing management unit S ₂ of the processor board PB ₂ issues a shared read RS to the shared bus SB (4).

Processor boards PB ₀ to PB ₁ and PB ₃
Starts the operation by looking at the shared read RS on the shared bus SB, but the processor substrate PB ₃ has neither a copy of this cache line in the cache memory C ₃ nor the main memory M ₃ , so the operation ends (5 ). Processor board P
Since B ₁ has the cache state tag CTag ₁ in the state M, the shared read CR is issued to the internal bus (5), the latest value of this address is read from the cache memory C ₁ (6), and the internal bus intervention is performed. Drive the indicator line to indicate intervention. At this point, the cache memory C ₁ causes a transition to S the cache state from M, the cache status tag CTag ₁ shared managing unit S ₁ also to transition the cache state from M to S (7). Then, the latest value is added to the processor board PB ₂ together with the intervention instruction of the intervention instruction line via the shared bus SB.
(7).

Since the cache state tag CTag ₀ is in state I, the processor board PB ₀ does not respond to the shared read RS on the shared bus SB.

Next, in the processor board PB ₂ ,
The cache state tag memory CTag ₂ changes the cache state from I to S (8), but the cache state of the cache state tag memory CTag ₀ of the processor board PB ₀ remains I (8).

[0168] Then, data transferred through the shared bus SB is cached in the cache memory C _2, the cache memory C ₂ transitions the cache state from I to S (9). From this cache C ₂ to CPU (CP
The latest value is read in U ₂ ).

On the other hand, in the processor board PB ₀ , the latest value of this cache line transferred via the shared bus in response to the intervention instruction of the intervention instruction line of the shared bus SB is written in the main memory M ₀ (9 ), The write-back obligation is fulfilled.

Next, a distributed shared memory type multiprocessor system according to a fourth embodiment of the present invention will be described.

In the fourth embodiment, whether or not the cache memory on another processor board has rewritten the shared state used in the main memory tag memory 27 of the shared management unit 4 in the first embodiment, that is, other This is an improvement in that information indicating whether or not ownership is present on a processor board is added to the presence / absence of access from a cache memory on another processor board.

Since this additional information indicates whether or not ownership is absent on the processor board, it is possible to inform the main memory 3 in advance whether or not an intervention will occur when reading. It is possible.

The bits representing this additional information are shared bus 6
It is driven when the exclusive read RM and the invalidation request INV are issued above, and is released when the write back WB is issued on the shared bus 6, so that the whereabouts of the ownership can be accurately reflected. .

Therefore, in the fourth embodiment, the main memory tag memory 27 can take any of the following three states P, G and A.

[P]: There is no copy in the cache of another processor board.

[G]: The copy may exist in the cache of another processor board, but the ownership is on this processor board.

[A]: Ownership in the cache of another processor board.

Here, the existence of ownership means that
It also means that there is a copy in the cache, so these three states can cover all situations.

In the fourth embodiment, it is possible to know in advance from the shared state of the main memory tag memory whether the intervention occurs when reading from the main memory 3 without waiting for the intervention from the proprietary bus 6. Therefore, the operation on the processor board having the main memory 3 to which the designated address is assigned is performed as follows according to the sharing state of the main memory tag memory, thereby reducing the traffic on the shared bus 6. It is possible.

[P]: Reading and writing are performed only by the internal bus 5 without passing through the shared bus 6.

[G]: Read is performed only by the internal bus 5, and write is performed by issuing the invalidation request INV to the shared bus 6.

[A]: Reading is performed by interrupting access to the main memory 3 and waiting for intervention from the shared bus 6, and writing is performed by issuing an invalidation request INV to the shared bus 6.

In the fourth embodiment, if the shared state is [P] when the cache refill is performed, it means that there is no copy in another cache. Therefore, the cache state is changed to the state E (exclusive). It can be set to (clean).
When the cache state is E, writing, reading, and replacement can be performed using only the internal bus 5, so unnecessary traffic on the shared bus 6 can be reduced.

Even if the main memory on its own processor board is accessed, if the shared state is [A], the cache on another processor board intervenes, so it is necessary to access the main memory 3. Not internal bus 5
Traffic can be reduced.

Therefore, the state transition of the cache state tag memory 24 of the shared management unit 4 is summarized in FIG. 35 instead of the one summarized in FIG. 7 when accessing the main memory on its own processor board. Therefore, when accessing the main memory on another processor board, the one summarized in FIG. 36 is replaced with the one summarized in FIG.

FIG. 37 shows the CPU of the processor board PB ₁ .
(CPU ₁ ) is the main memory M on the processor board PB _0
It shows the operation when writing (1) to the address 0x0000 1000 stored in ₀ . The cache memory C ₁ processor board PB ₁ causes a read miss (2), and issues an exclusive read CRI to internal bus B ₁ (3). Since this address is not allocated to the main memory M ₁ on the processor board PB _1, sharing management unit S ₁ of the processor board PB ₁ issues an exclusive read RM to the shared bus SB (4).

Processor boards PB ₀ and PB ₂ to PB ₃
Starts the operation by looking at the exclusive read RM on the shared bus SB, but the processor boards PB ₂ and PB ₃ copy the cache lines to the cache memories C ₂ and C ₃ and to the main memories M ₂ and M ₃ . Since it does not have, the operation is finished (5). Since the processor board PB ₀ has the main memory M ₀ to which this address is assigned, it issues an exclusive read CRI to its internal bus B ₀ (5) and reads this cache line from the main memory M ₀ (6).

The read data is transferred to the processor board PB ₁ via the shared bus SB (7). At this point, the shared state of the main memory tag memory MTag ₀ changes from P to A (7), indicating that ownership has been transferred to another processor board, but the cache state of the cache state tag memory CTag ₀ is I. It remains.

Next, in the processor board PB ₁ ,
The cache state tag memory CTag ₁ changes the cache state from I to M (8), the data transferred via the shared bus SB is cached in the cache memory C ₁ (9), and the cache memory C ₁ changes the cache state. Transition from I to M (9). C for this cache C ₁
The PU (CPU ₁ ) writes.

FIG. 38 shows the CPU of the processor board PB ₂ .
(CPU ₂₎ is updated in the cache memory C ₁ on the processor board PB _1, its ownership was read to the address 0x0000 1000 are transferred from the processor board PB ₀ to the processor board PB ₁ ( The operation at the time of 1) is shown. The cache memory C ₂ of the processor board PB ₂ causes a read miss (2), and the internal bus B
_A shared read CR is issued to 2 (3). Since this address is not allocated to the main memory M ₂ on the processor board PB _2, sharing management unit S ₂ of the processor board PB ₂ issues a shared read RS to the shared bus SB (4).

Processor boards PB ₀ to PB ₁ and PB ₃
Starts the operation by looking at the shared read RS on the shared bus SB, but the processor boards PB ₀ and PB ₃ terminate the operation because the cache status tags CTag ₀ and CTag ₃ are in the invalid state I (5). In particular, the processor board PB ₀ has the main memory M ₀ to which this address is assigned, but since the main memory tag memory MTag ₀ shows the absence of ownership in the state A, a general command is sent to the internal bus B _0. Do not issue.

On the other hand, since the cache state tag CTag _{1 of} the processor board PB ₁ is in the state M, the shared read CR is issued to its internal bus B ₁ (5) to read the latest value of this address from the cache memory C _1. (6). At this point, the cache memory C ₁ changes the cache state to M
To O (6), cache state tag memory CT
Ag ₁ also changes the cache state from M to O (7). The latest read value is transferred to the processor board PB ₂ via the shared bus SB (7).

Next, in the processor board PB ₂ ,
Cache state tag memory CTag ₂ transitions to S cache status from the I (8), data transferred through the shared bus SB is cached in the cache memory C _2, the cache memory C ₂ is the cache state from I S
(9). From this cache C ₂ to CPU (C
The latest value is read to PU ₂ ).

FIG. 39 shows the CPU of the processor board PB ₁ .
(CPU ₁ ) is updated in the cache memory on the processor board PB ₁ and its ownership is changed to the processor board PB 1.
Address 0x transferred from ₀ to processor board PB ₁
The operation (1) is shown when write back (replace) is performed on 0000 1000 based on a cache collision or a cache flush instruction. Processor board PB
The cache memory C _{2 of 1} reads the latest value (2), the cache memory C ₂ changes the cache state from M to I, and issues the write-back WR to the internal bus B ₁ (3). Since this address is not allocated to the main memory M ₁ on the processor board PB _1, sharing management unit S ₁ of the processor board PB ₁ issues a WB write back to the shared bus SB (4) latest value And the cache state of the cache state tag memory CTag ₁ is transferred to M
To I.

Processor boards PB ₀ and PB ₂ to PB ₃
Starts its operation by looking at the write-back WB on the shared bus SB, but the processor boards PB ₂ and PB ₃ do not have an entry to write-back this cache line in the main memories M ₂ and M ₃ , so the operation ends ( 5). Since the processor board PB ₀ has the main memory M ₀ to which this address is assigned, the write back WR is issued to its internal bus B ₀ (5),
This indicates that the shared state of the main memory tag memory MTag ₀ is transited from A to G and the ownership is regained. The latest value transferred via the shared bus SB is written back to the main memory M ₀ (6).

FIG. 40 shows the CPU of the processor board PB ₀ .
The operation when (CPU ₀ ) reads (1) to the address 0x0000 1000 assigned to the main memory M ₀ is shown. Cache memory C ₀ of the processor board PB ₀ undergoes a read miss (2), issues a shared read CR to internal bus B ₀ (3). The shared state of the main memory tag memory MTag ₀ is P (4), and it is a completely exclusive privat
The shared bus SB is shown because it is in the e state (5).
Without access to perform direct access to the main memory M _0, the read data of the address (4), caches them in cache memory C ₀ (5). CPU ₀ reads this cache line from this cache C ₀ .

Along with this, the cache state of the cache state tag memory CTag ₀ of the cache memory C ₀ changes from I to E (5).

After that, the CPU (C
Since an access from PU ₀ ) makes a cache hit in the cache memory C ₀ , it can be performed without issuing a command to the internal bus B ₀ .

Next explained is a distributed shared memory type multiprocessor system according to the fifth embodiment of the invention.

This fifth embodiment is an improvement of the first embodiment, and further improves the fourth embodiment to change the meaning of the shared state used in the main memory tag memory 27 to change the cache on another processor board. Whether it is rewritten in memory,
That is, whether ownership exists on another processor board,
It is a two-state display that shows only that.

By limiting the shared state to two states in this way, it is possible to reduce the cost of the system. For example, if the main memory 3 is 64 megabytes and the main memory tag is provided in cache line units of 64 bytes, it can be represented by 1 bit if the shared state is 2 states, so 1 megabit as a whole. However, if the shared state is three states as in the fourth embodiment, it must be represented by 2 bits, and a total of 2 megabits of main memory tag memory is required. . This capacity is comparable to the capacity of one SRAM chip at present and can be realized, but the increase in cost cannot be avoided.

In this fifth embodiment, the main memory tag memory 27
Can take one of the following two states H and A.

[H]: A copy may exist in the cache of another processor board, but the ownership is owned by this processor board.

[A]: Ownership in the cache of another processor board.

In the fifth embodiment, the location of ownership can be known in advance from the shared state of the main memory tag memory 27 without waiting for intervention from the shared bus 6.
The traffic on the shared bus 6 can be reduced by making the operation in the processor board having the main memory 3 to which the designated address is allocated according to the sharing state of the main memory tag memory 27. is there.

[H]: Read is performed only by the internal bus 5, and write is performed by issuing the invalidation request INV to the shared bus 6.

[A]: Reading is performed by interrupting access to the main memory 3 and waiting for intervention from the shared bus 6, and writing is performed by issuing an invalidation request INV to the shared bus 6.

However, in the state H, since reading is performed only by the internal bus 5, it is impossible to obtain accurate information as to whether or not a copy exists in the cache of another processor board. Therefore, when the cache is refilled, it is necessary to drive the sharing instruction line and supply it to the cache memory as a shared state.

Even if there is an access request for the address assigned to its own main memory 3 on the shared bus 6, if the shared state of the main memory tag memory 27 is A, another processor board will intervene. Since access to the main memory 3 is unnecessary and the internal bus 5 is not used all at once, the traffic on the internal bus 5 can be reduced.

Therefore, the state transition of the cache state tag memory 24 of the shared management unit 4 is summarized in FIG. 41 instead of the one summarized in FIG. 7 when accessing the main memory on its own processor board. Therefore, when accessing the main memory on another processor board, the one summarized in FIG. 42 is replaced with the one summarized in FIG.

FIG. 43 shows the CPU of the processor board PB ₀ .
The operation when (CPU ₀ ) reads (1) at the address 0x0000 1000 assigned to the main memory M ₀ is shown. The cache memory C ₀ of the processor board PB ₀ causes a read miss (2), and the internal bus B ₀
The shared read CR is issued to (3) and the main memory M ₀ is accessed (4). Since the shared state of the main memory tag memory MTag ₀ is H (4), which indicates that the ownership is absent in another processor board (5), the main memory M _{0 is} not accessed without accessing the shared bus SB. Is directly accessed, the data at this address is read (4), and this is cached in the cache memory C ₀ (5). CPU ₀ reads this cache line from this cache C ₀ .

Along with this, the cache states of the cache memory C ₀ and the cache state tag memory CTag ₀ transit from I to S.

After that, the CPU (C
Since an access from PU ₀ ) makes a cache hit in the cache memory C ₀ , it can be performed without issuing a command to the internal bus B ₀ .

FIG. 44 shows the CPU of the processor board PB ₁ .
(CPU ₁ ) is the main memory M on the processor board PB _0
It shows the operation when writing (1) to the address 0x0000 1000 stored in ₀ . The cache memory C ₁ processor board PB ₁ causes a write miss (2), and issues an exclusive read CRI to internal bus B ₁ (3). Since this address is not allocated to the main memory M ₁ on the processor board PB _1, sharing management unit S ₁ of the processor board PB ₁ issues an exclusive read RM to the shared bus SB (4).

Processor boards PB ₀ and PB ₂ to PB ₃
Starts the operation by looking at the exclusive read RM on the shared bus SB, but the processor boards PB ₂ and PB ₃ copy a copy of this cache line to both the cache memories C ₂ and C ₃ and the main memories M ₂ and M ₃ . Since it does not have it, the operation ends (5). Since the processor board PB ₀ has the main memory M ₀ to which this address is assigned, it issues an exclusive read CRI to its internal bus B ₀ (5) and reads this cache line from the main memory M ₀ (6).

The read data is transferred to the processor board PB ₁ via the shared bus SB (7). At this point, the shared state of the main memory tag memory MTag ₀ changes from H to A, indicating that ownership has been transferred to another processor board, but the cache state of the cache state tag memory CTag ₀ remains I. is there.

Next, in the processor board PB ₁ ,
The cache state of the cache state tag memory CTag ₁ transits from I to M (8), the data transferred via the shared bus SB is cached in the cache memory C ₁ (9), and the cache state of the cache memory C ₁ changes. Transition from I to M (9). C for this cache C ₁
The PU (CPU ₁ ) writes.

FIG. 45 shows the CPU of the processor board PB ₀ .
(CPU ₀₎ is being updated by the cache memory C ₁ on the processor board PB _1, its ownership was read to the address 0x0000 1000 are transferred from the processor board PB ₀ to the processor board PB ₁ ( The operation at the time of 1) is shown. The cache memory C ₀ of the processor board PB ₀ causes a read miss (2), and the internal bus B
_A shared read CR is issued to ₀ (3), and the main memory M ₀ is accessed (4).

However, since the shared state of the main memory tag memory MTag ₀ is A (4), indicating that the ownership of this processor board is absent (5), the shared management section of this processor board PB ₀ is shown. S ₀ intervenes access to the main memory M ₀ without checking the intervention instruction line of the shared bus SB (5) and interrupts this access (6), while issuing a shared read RS to the shared bus SB ( 4).

The processor boards PB ₁ to PB ₃ start the operation by seeing the shared read RS on the shared bus SB.
The processor boards PB ₂ and PB ₃ copy the cache line to the cache memories C ₂ and C ₃ as well as the main memory M.
_The operation is terminated because it does not have it in ₂ or M ₃ (5). Since the cache status tag CTag ₁ is in the state M, the processor board PB ₁ issues a shared read CR to its internal bus B ₁ (5) and reads the latest value of this address from the cache memory C ₁ (6). At this point, the cache state of the cache memory C ₁ changes from M to O (6), and the cache state of the cache state tag memory CTag ₁ also changes from M to O (7). The latest read value is transferred to the processor board PB ₀ via the shared bus SB (7).

Next, in the processor board PB ₀ ,
The cache state of the cache state tag memory CTag ₀ transits from I to S (8), but the main memory tag memory MTag
The shared state of ₀ remains A, indicating that the processor board has no ownership.

The data transferred via the shared bus SB is cached in the cache memory C ₀ (9), and the cache state of the cache memory C ₀ transits from I to S (9). From this cache C ₀ to CPU (CPU ₀ )
The latest value is read.

FIG. 46 shows the CPU of the processor board PB ₂ .
(CPU ₂₎ is updated in the cache memory C ₁ on the processor board PB _1, its ownership was read to the address 0x0000 1000 are transferred from the processor board PB ₀ to the processor board PB ₁ ( The operation at the time of 1) is shown. The cache memory C ₂ of the processor board PB ₂ causes a read miss (2), and the internal bus B
_A shared read CR is issued to 2 (3). Since this address is not allocated to the main memory M ₂ on the processor board PB _2, sharing management unit S ₂ of the processor board PB ₂ issues a shared read RS to the shared bus (4).

Processor boards PB ₀ to PB ₁ and PB ₃
Starts the operation by seeing the shared read RS on the shared bus SB, but the processor substrate PB ₃ has neither a copy of this cache line in the cache memory C ₃ nor in the main memory M ₃ , so the operation is terminated (5 ), Processor board PB
_{For 0,} since the main memory tag memory MTag ₀ is in state A, the operation ends (5). Here, the processor board PB ₀ has a main memory M ₀ to which this address is assigned,
Since the main memory tag memory MTag ₀ indicates the absence of ownership in the state A, no simultaneous command is issued to the internal bus B ₀ .

On the other hand, since the cache state tag CTag _{1 of} the processor board PB ₁ is in the state M, the shared read CR is issued to its internal bus B ₁ (5) to read the latest value of this address from the cache memory C _1. (6). At this point, the cache state of the cache memory C ₁ is M
To O (6), cache state tag memory CT
The cache state of ag ₁ also transits from M to O (7). The latest read value is transferred to the processor board PB ₂ via the shared bus SB (7).

Next, in the processor board PB ₂ ,
The cache state of the cache state tag memory CTag ₂ transits from I to S (8), the data transferred via the shared bus SB is cached in the cache memory C ₂ (9), and the cache state of the cache memory C ₂ Changes from I to S (9). This cache C ₂ to CPU
The latest value is read out to (CPU ₂ ).

[0227]

As described above, according to the present invention, access to a non-shared variable to a memory on the same substrate can be realized without using a shared bus and while ensuring consistency. The non-shared variable access to the memory on the same board usually occupies most of the memory access, so that the deterioration of the execution operation performance of the CPU is prevented, and
Since unnecessary traffic on the shared bus can be reduced, more processor boards can be connected on the bus. As a result, there is a great effect that a multiprocessor system having high system expandability can be realized without imposing restrictions on shared variable access to parallel programs.

[Brief description of drawings]

FIG. 1 is a schematic block diagram of a conventional shared memory type multiprocessor system.

FIG. 2 is a schematic block diagram of a conventional distributed shared memory type multiprocessor system.

FIG. 3 is a schematic block diagram of a distributed shared memory type multiprocessor system according to the first embodiment of the present invention.

FIG. 4 is a detailed block diagram of the cache memory 2 according to the first embodiment of the present invention.

FIG. 5 is a detailed block diagram of the sharing management unit 4 in the first embodiment of the present invention.

FIG. 6 is a diagram showing a table summarizing the states of the state tag unit 12 in the first embodiment of the present invention and the issued commands / state transitions with respect to commands from the CPU and commands from the internal bus.

FIG. 7 summarizes the states of the cache state tag memory 24 and the issued commands / state transitions for the commands from the internal bus and the shared bus in the first embodiment of the present invention for the case of access to the main memory on the own board. The figure which shows a table.

FIG. 8 summarizes the states of the cache state tag memory 24 and the issued commands / state transitions for the commands from the internal bus and the shared bus in the first embodiment of the present invention for the case of accessing the main memory on another board. The figure which shows a table.

FIG. 9 is the first half of a flowchart showing the operations of the cache control unit and the sharing management unit in response to the read instruction of the CPU in the first embodiment of the present invention.

FIG. 10 is the latter half of the flowchart showing the operations of the cache control unit and the sharing management unit in response to the read instruction of the CPU in the first embodiment of the present invention.

FIG. 11 is a flowchart showing the operations of the cache control unit and the sharing management unit in response to a CPU write command in the first embodiment of the present invention.

FIG. 12 is a flowchart showing the operation of the shared management unit and cache control unit for shared read in the first embodiment of the present invention.

FIG. 13 is a flowchart showing the operation of the shared management unit and cache control unit for exclusive reading in the first embodiment of the present invention.

FIG. 14 is a flowchart showing the operations of the sharing management unit and the cache control unit in response to an invalidation request according to the first embodiment of this invention.

FIG. 15 is a diagram showing a configuration example of a distributed shared memory type multiprocessor system of the present invention.

FIG. 16 is a specific operation example of the first embodiment of the present invention.
The figure shown in the structural example.

FIG. 17 is a specific operation example of the first embodiment of the present invention.
The figure shown in the structural example.

FIG. 18 is a concrete operation example of the first embodiment of the present invention;
The figure shown in the structural example.

FIG. 19 is a specific operation example of the first embodiment of the present invention.
The figure shown in the structural example.

FIG. 20 is a specific operation example of the first embodiment of the present invention.
The figure shown in the structural example.

FIG. 21 is a specific operation example of the first embodiment of the present invention;
The figure shown in the structural example.

FIG. 22 is a specific operation example of the first embodiment of the present invention;
The figure shown in the structural example.

FIG. 23 is a state tag section 12 in the second embodiment of the present invention.
FIG. 6 is a diagram showing a table summarizing the state of the command and the issued command / state transition for the command from the CPU and the command from the internal bus.

FIG. 24 summarizes the state of the cache state tag memory 24 and the issue command / state transition for the command from the internal bus and the shared bus in the second embodiment of the present invention for the case of accessing the main memory on the own board. The figure which shows a table.

FIG. 25 summarizes the states of the cache state tag memory 24 and the issued commands / state transitions for commands from the internal bus and the shared bus in the second embodiment of the present invention for the case of access to the main memory on another board. The figure which shows a table.

FIG. 26 is the first half of a flowchart showing the operations of the cache control unit and the sharing management unit in response to a CPU read instruction in the second embodiment of the present invention.

FIG. 27 is the latter half of the flowchart showing the operations of the cache control unit and the sharing management unit in response to the read instruction of the CPU according to the second embodiment of the present invention.

FIG. 28 is a flowchart showing the operations of the sharing management unit and cache control unit for shared reading in the second embodiment of the present invention.

FIG. 29 is a diagram showing a specific operation example of the second embodiment of the present invention.
The figure shown in the structural example.

FIG. 30 summarizes the state of the cache state tag memory 24 and the issue command / state transition for the command from the internal bus and the shared bus in the third embodiment of the present invention for the case of access to the main memory on the own board. The figure which shows a table.

FIG. 31 summarizes the states of the cache state tag memory 24 and the issued commands / state transitions for the commands from the internal bus and the shared bus in the third embodiment of the present invention for the case of accessing the main memory on another board. The figure which shows a table.

FIG. 32 is a specific operation example of the third embodiment of the present invention.
The figure shown in the structural example.

FIG. 33 shows a concrete operation example of the third embodiment of the present invention.
The figure shown in the structural example.

FIG. 34 shows a specific operation example of the third embodiment of the present invention.
The figure shown in the structural example.

FIG. 35 summarizes the states of the cache state tag memory 24 and the issued commands / state transitions for commands from the internal bus and the shared bus in the fourth embodiment of the present invention for the case of access to the main memory on the own board. The figure which shows a table.

FIG. 36 summarizes the states of the cache state tag memory 24 and the issued commands / state transitions for the commands from the internal bus and the shared bus in the fourth embodiment of the present invention for the case of accessing the main memory on another board. The figure which shows a table.

FIG. 37 is a diagram showing a specific operation example of the fourth embodiment of the present invention.
The figure shown in the structural example.

FIG. 38 is a specific operation example of the fourth embodiment of the present invention.
The figure shown in the structural example.

FIG. 39 is a specific operation example of the fourth embodiment of the present invention.
The figure shown in the structural example.

FIG. 40 is a specific operation example of the fourth embodiment of the present invention.
The figure shown in the structural example.

FIG. 41 summarizes the states of the cache state tag memory 24 and the issued commands / state transitions for commands from the internal bus and the shared bus in the fifth embodiment of the present invention for the case of access to the main memory on the own board. The figure which shows a table.

FIG. 42 summarizes the states of the cache state tag memory 24 and the issued commands / state transitions for the commands from the internal bus and the shared bus in the fifth embodiment of the present invention for the case of accessing the main memory on another board. The figure which shows a table.

FIG. 43 is a specific operation example of the fifth embodiment of the present invention.
The figure shown in the structural example.

FIG. 44 is a specific operation example of the fifth embodiment of the present invention.
The figure shown in the structural example.

FIG. 45 is a specific operation example of the fifth embodiment of the present invention.
The figure shown in the structural example.

FIG. 46 is a specific operation example of the fifth embodiment of the present invention;
The figure shown in the structural example.

[Explanation of symbols]

 1 CPU 2 cache memory 3 main memory 4 shared management unit 5 internal bus 6 shared bus 11 address tag unit 12 status tag unit 13 data storage unit 14 comparator 15 valid / invalid determination unit 16 hit / miss signal calculation unit 17 cache control unit 18 shared instruction line 19 command line 20 address line 21 intervention instruction line 22 data line 23 cache address tag memory 24 cache state tag memory 25 cache state tag memory control unit 26 main memory tag memory control unit 27 main memory tag memory 28 external access control Unit 29 Internal access control unit

Claims (5)

[Claims] 1. A distributed shared memory multiprocessor system comprising a plurality of processor units coupled via a shared bus, each processor unit being connected to a CPU and a CPU via an internal bus. , A main memory that stores a distributed portion of the system's shared memory, a CPU cache memory that is connected to the main memory via an internal bus, and caches selected data entries in the shared memory, and an internal bus In the shared management unit that is connected to the main memory and the CPU cache memory and interfaces the internal bus and the shared bus, each data entry of the main memory on each processor unit is stored in the CPU cache memory on another processor unit. Stores the shared state of each data entry in main memory indicating whether it is shared In response to the execution of a write instruction to a certain data entry of the main memory by the main memory tag means and the CPU, the sharing state of the certain data entry of the main memory tag means is that the certain data entry is another processor. The other processor unit to invalidate the certain data entry of the CPU cache memory on the other processor unit when indicating that it is being shared by the CPU cache memory on the unit. Instruction means for issuing an invalidating instruction to be issued on a shared bus, cache tag means for storing the address of a selected data entry stored in the CPU cache memory, and an invalidating instruction for a certain data entry are shared The address of the certain data entry received from the bus is stored in the cache tag means. To, and control means for invalidating 該某 data entry CPU cache memory,
A system consisting of and including. 2. A distributed shared memory multiprocessor system comprising a plurality of processor units coupled via a shared bus, each processor unit being connected to a CPU and a CPU via an internal bus. , A main memory that stores a distributed portion of the system's shared memory, a CPU cache memory that is connected to the main memory via an internal bus, and caches selected data entries in the shared memory, and an internal bus A shared management unit that is connected to the main memory and the CPU cache memory and interfaces the internal bus and the shared bus. Each data entry of the CPU cache memory is updated in the CPU cache memory on each processor unit and Each of the CPU cache memory indicating whether it has not been written back Cache state tag means for storing the cache state of the data entry, and the cache state tag means for receiving an access request for a data entry from another processor unit received via the shared bus. On another processor unit when the cache state of the data entry indicates that the one data entry has been updated in the CPU cache memory on each processor unit and not written back to shared memory. Means for intervening in the access to the certain data entry of the main memory of the cache memory and the cache state tag means when the intervention means intervenes in the access to the certain data entry of the main memory on the other processor. The cache state of the certain data entry to the ownership of the certain data entry. State transition from one cache state with a certain data entry to another cache state that does not have ownership of the certain data entry, and access to the certain data entry from each processor unit is intervened by another processor unit. When intervened by the means, the cache state of the certain data entry of the cache state tag means is changed from one cache state that does not have ownership of the certain data entry to another that has ownership of the certain data entry. And a control means for controlling the state transition to the cache state. 3. A distributed shared memory multiprocessor system comprising a plurality of processor units coupled via a shared bus, each processor unit being connected to a CPU and a CPU via an internal bus. , A main memory that stores a distributed portion of the system's shared memory, a CPU cache memory that is connected to the main memory via an internal bus, and caches selected data entries in the shared memory, and an internal bus In the shared management unit that is connected to the main memory and the CPU cache memory and interfaces the internal bus and the shared bus, each data entry of the main memory on each processor unit is stored in the CPU cache memory on another processor unit Stores the shared state of each data entry in main memory indicating whether it is shared Main memory tag means and each data entry of the CPU cache memory indicating whether each data entry of the CPU cache memory has been updated in the CPU cache memory on each processor unit and has not been written back to the shared memory Cache state tag means for storing the cache state of the main memory tag, and the shared state of the certain data entry of the main memory tag means for execution of a read / write instruction to a certain data entry of the main memory by the CPU. Data entry indicating that it is shared with the CPU cache memory on another processor unit,
Command means for issuing a read command on the shared bus for instructing the other processor unit to read the certain data entry of the CPU cache memory on the other processor unit, and the shared bus In response to a read command from another processor unit received via the cache state tag means, the cache state of a certain data entry is
When an entry indicates that it has been updated in the CPU cache memory on each processor unit and has not been written back to shared memory, the other processor
Means for intervening in accessing the certain data entry in main memory on the unit. 4. A distributed shared memory multiprocessor system comprising a plurality of processor units coupled via a shared bus, each processor unit being connected to a CPU and a CPU via an internal bus. , A main memory that stores a distributed portion of the system's shared memory, a CPU cache memory that is connected to the main memory via an internal bus, and caches selected data entries in the shared memory, and an internal bus A shared management unit that is connected to the main memory and the CPU cache memory and interfaces the internal bus and the shared bus. Each data entry of the CPU cache memory is updated in the CPU cache memory on each processor unit and Each of the CPU cache memory indicating whether it has not been written back Cache state tag means for storing the cache state of the data entry, and the cache state tag means for receiving an access request for a data entry from another processor unit received via the shared bus. On another processor unit when the cache state of the data entry indicates that the one data entry has been updated in the CPU cache memory on each processor unit and not written back to shared memory. Means for intervening in accessing the certain data entry of the main memory of the. 5. The system according to claim 4, wherein the sharing management unit is further a main memory tag means for storing a sharing state of each data entry of the main memory on each processor unit, and the sharing state is each Ownership of the data entry is assigned to each processor
Including the [H] state indicating that the data entry exists on the unit and the [A] state indicating that the ownership of each data entry exists on another processor unit; In response to an access request for a certain data entry, when the shared state of the certain data entry of the main memory tag means is the [A] state, the certain data entry of the CPU cache memory on the other processor unit. And a command means for issuing a read command on the shared bus to instruct the other processor unit to read the data on the shared bus.