JP3097941B2 - Cache memory controller - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a cache memory control device in a multiprocessor system, and more particularly to a method for making data in a cache memory consistent.

[0002]

2. Description of the Related Art In a multiprocessor system in which a plurality of processors and a main memory (main storage device) shared by the processors are connected via a shared bus, it is possible to prevent all accesses of each processor from being concentrated on the shared bus. Therefore, each processor generally has a cache memory. On the other hand, in such a multiprocessor system, since each processor has its own cache memory, a copy of the same data exists in a plurality of cache memories, and therefore, the uniformity of these data is maintained. There is a need.

Therefore, in a multiprocessor system,
When a change occurs in the data in the cache memory of each processor, not only the main memory but also the other cache memories are notified of the data change so as to maintain the uniformity of the data in the system. This protocol is called a cache memory coherency protocol, and various protocols have been proposed.
These protocols have the following configuration in order to make them consistent.

That is, when each processor performs an operation, the processor occupies the shared bus until the operation is completed, and
A signal corresponding to the operation is broadcast on a shared bus. On the other hand, other processors monitor the shared bus,
If the corresponding block is stored in the cache memory, consistency is assured by processing such as changing the state of the block according to the signal.

[0005] For example, a case of a processor read miss in the Illinois protocol will be described below as such a non-consistent protocol. (A) When the processor performs a read operation and causes a cache miss, the processor makes the read miss signal significant,
Request data from the shared bus. (B1) When data is sent from another cache memory, the data is registered in a "Shared Clean" state (normally, data from another cache memory is faster and has higher priority than data in the main memory). ). (B2) If there is no data in the other cache memory, the data is sent from the main memory, and in this case, the data is registered in a “Private Clean” state.

As described above, in the conventional non-consistent protocol, the two operations (a) and (b1) or (b2) are divided into one inseparable operation, that is, after the operation of (a) is started. Until the operation of (b1) or (b2) is completed, one synchronization unit is used, and during this period, the operation is performed without releasing the exclusive state of the bus.

[0007]

However, the limitation of "treating some operation groups as inseparable operations on the bus" in the above-mentioned conventional non-consistent scheme is not so large when the multiprocessor is small. Although this does not occur, it becomes a serious problem when a large-scale system or bus is replaced with a general-purpose network connection network. For example,
When a large-scale multiprocessor system is considered, the propagation delay of a signal flowing through the bus cannot be ignored. The same applies when a general-purpose network connection network is considered.

That is, when considering the same synchronization unit as in the prior art in such a large-scale system, in order to guarantee the consistency of the cache memory, the propagation delay time is taken into consideration and the system is used. The maximum delay time must be a synchronization unit. As a result, as the scale of the system increases, the occupation time of the network by the operation of one processor increases and the performance of the system deteriorates. Therefore, such a configuration cannot be adopted at all.

On the other hand, in order to cope with such a problem, it is conceivable that each processor independently sets a synchronization unit without considering delay of a signal from a bus. In other words, this is a method in which the exclusive use of the bus is used as an operation unit of each processor. However, when using such a method,
In the conventional cache memory non-consistent method, the following problem occurs. In other words, in the conventional cache memory non-contradiction method, the event of the state transition of each cache memory is broadcasted simultaneously with the occurrence of the event by a global clock as a system. However, when the above synchronization unit is set, broadcasting of such an event occurrence involves a delay, and furthermore, depending on the distance from the source,
In some cases, the notification is transmitted with the reversal of the notification. Therefore, such a reversal of the notification causes a problem that it is not possible to guarantee the consistency of the cache memory.

[0010] Such a problem will be described by taking a processor read miss by the above-mentioned Illinois protocol as an example. First, conventionally, as described above, the operation (a) and the operation (b1) or (b2) are performed by one inseparable operation. On the other hand, the operations are (a), (b1),
It is considered that the operation is divided into (b2) and each operation is performed independently.

FIG. 2 shows a main part of a multiprocessor system for explaining this. In FIG. 2, illustration of a processor and the like is omitted to avoid complexity. In the figure, reference numerals 1 and 2 denote cache memories, and it is assumed that these cache memories 1 and 2 and the main memory 3 are connected via a bus 4. In addition, the time during which an operation travels between the cache memory 1 and the main memory 3 is represented by n, and the time through which the operation travels between the cache memory 2 and the main memory 3 is represented by m, where n> m.

In such a configuration, consider a case where when the cache memory 1 is dirty, a processor read miss occurs in the cache memory 2 and a block of the cache memory 1 is read. At this point, it is assumed that correct data is present in the cache memory 1 and old incorrect data is present in the main memory 3 (a write hit is repeated in the cache memory 1 and the data is updated).

The flow of events will be described below. In the cache memory 2, a processor read miss occurs for the block X. At the same time as above, block X
Causes a swap-out (writing back data to the main memory 3). After m hours, the cache memory 2 receives the data (old / incorrect) from the main memory 3. That is, n> m
At this time, the data from the cache memory 1 has not reached the main memory 3 at this time. After n hours, the main memory 3 receives the data (correct) from the cache memory 1. After n + m hours, the cache memory 1 receives a data request from the cache memory 2, but the block X does not exist because of swap-out. In this case, the cache memory 1 normally processes the data request of the cache memory 2. Therefore, the cache memory 2 cannot receive correct data.

In the above-mentioned operation, in the conventional method, either one of the processor read miss and the swap out takes the bus right, and if the processor read miss takes the bus right, the swap out occurs. , And the correct data from the cache memory 1 is transferred to the cache memory 2. When the swap-out takes the bus right, a processor read miss is awaited. After the swap-out is performed on the main memory 3, correct data is transferred from the main memory 3 to the cache memory 2. . On the other hand, when the operation group is divided as described above, data from another cache memory does not always arrive quickly and preferentially, and old data is received, which guarantees consistency of the cache memory. There was a problem that it could not be done.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-mentioned conventional problems. Even in a large-scale multiprocessor system, it is possible to guarantee that the performance of the cache memory is not reduced and that the cache memory is made consistent. It is an object to provide a cache memory control device.

[0016]

According to the present invention, there is provided a cache memory control device for a multiprocessor system comprising processor elements each having a processor and a cache memory connected to a network having a broadcasting function. Each of the processor elements has a synchronization unit control unit that occupies the network only when each processor element sends out a signal.After releasing the right of the processor element to occupy the network, a response to a request from the processor element is issued. A monitoring unit that monitors an input signal from the network for a maximum time necessary to be received, and a content of an input signal and a priority of a predetermined operation during a monitoring time period by the monitoring unit. , The plurality
According to the priority of each of the processor elements of
A state management unit for determining a state of data in the own cache memory which has generated the request.

[0017]

In the cache memory control device according to the present invention, for example, when a read miss occurs and a data request for the read miss occurs, the synchronization unit control unit occupies the shared bus or network only when the data request is made. Claim the right to After the processor element releases the exclusive right, the monitoring unit monitors a signal input from the shared bus or the network for a predetermined maximum time necessary for receiving a response to the request.

The state management unit determines the state of the data in the cache memory based on the signal input at the time monitored by the monitoring unit and a rule of a predetermined priority . For example, when data for a read miss is input during the monitoring time and a write hit signal is input from another processor element having a higher priority , the input data and the data that has been write hit by another processor element are one. Therefore, the input data becomes invalid, and the state of the cache memory becomes “Invalid”. Also, in other cases, the state management unit is determined in advance.
The state of the cache memory is determined after the monitoring time according to the priority rule. Therefore, even when the processor element has given up the right to occupy the shared bus or the network, it is possible to guarantee that data in the cache memory is not inconsistent.

[0019]

Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 1 is a block diagram showing an embodiment of the cache memory control device of the present invention. The illustrated device includes a plurality of processor elements 10 (10-1 to 10-n), a main memory 20, and a shared bus (network) 30. The processor elements 10 each include a processor 1
1 (11-1 to 11-n) and the cache memory 12
(12-1 to 12-n). Since the configuration of the processor elements 10-2 to 10-n is the same as that of the processor element 10-1, the internal configuration is not shown, and the configuration common to each processor element 10 is the processor 11 and the cache memory 12 It will be described as.

The processor 11 is a control unit that controls various controls. In particular, in a shared memory type multiprocessor system, the cache memory 12 and the main memory 20
It controls the write / read of data between them and controls the data transfer between the cache memories 12 and the like. The processor 11 includes a synchronization unit control unit 13, a monitoring unit 14, and a state management unit 15 as control devices for the cache memory 12. The synchronization unit control unit 13 has a function of dividing an operation into synchronization units. This division will be described later.

The monitoring unit 14 includes a buffer memory 14
a for monitoring data buffered at a predetermined monitoring time. Here, the predetermined monitoring time refers to the processor element 10
When a certain request is generated from the server, the maximum delay time as a system required from the start of the request to the reception of a response. Further, the state management unit 15 has a rule based on a predetermined priority order . If any response signal is input during the monitoring time by the monitoring unit 14, the state management unit 15 stores the state of the cache memory 12 according to the rule. Is determined.

The cache memory 12 has a known function as a cache memory, and has a state management unit 15.
Is used to determine the state of the data block stored. The main memory 20 is a memory that is shared by the processor elements 10,
A bus 0 connects the processor element 10 and the main memory 20. In this embodiment, a network connecting a plurality of processor elements 10 and a main memory 20 which is a shared memory of the processor elements 10 will be described as a shared bus 30.
The shared bus 30 includes a plurality of processor elements 10
The same applies to a general-purpose network having a broadcast function between them.

Next, an example of division of the operation by the synchronization unit control unit 13 will be described by taking the case of the Illinois protocol as an example. FIG. 3 shows the state transition of the Illinois protocol.
The numbers in parentheses in FIG. 3 correspond to the following numbers.

(1) Processor Read Miss (a) When the processor 11 performs a read operation and causes a cache miss, it makes the read miss signal significant and requests data from the shared bus 30. (B1) Cache memory 12 or main memory 20
And waits for data sent from another cache memory 12, and when the data is sent from another cache memory 12,
ed Clean ". (B2) When data is sent from the main memory 20 (when there is no data in another cache memory 12)
Registers data in a state of “Private Clean”.

(2) Bus read miss This is a request from the processor 11 which is a slave of the shared bus 30 (the processor receiving this request while another processor 11 is issuing a request). This is the case where the user has a copy of the data and receives a “bus read miss”.

The state is "Private Clean"
Or “Shared Clean” (a) Master side cache memory 12 (cache memory of the processor element that issued the request)
The requested data is block-transferred, and the state of the cache memory 12 is set to “Shared Clean”. When the state is “Dirty” (a) The requested data is block-transferred to the cache memory 12 and the main memory 20 on the master side, and the state of the cache memory 12 is changed to “Shared C”.
"lean".

(3) Processor write hit status is "Dirty" or "Private Cl
ean "(a) Data is immediately written to the cache memory 12,
Change the state to "Dirty". When the state is “Shared Clean” (a) The processor 11 sends an invalidation signal to the shared bus 30. Also, the data is written to the cache memory 12,
Change the state to "Dirty".

(4) Processor Write Miss (a) When a cache miss occurs, the write miss signal is made significant and data is requested from the shared bus 30. (B) Wait for data sent from the cache memory 12 or the main memory 20 and store the data in “Dirty”
In the cache memory 12 in the state described above. At this time, the data from the cache memory 12 is registered with priority. Then, the processor 11 writes to the cache memory 12.

(5) When the bus write hit state is "Shared Clean" (a) The processor 11 invalidates the state of the corresponding data.

(6) Bus Write Miss When the processor 11 which is the slave of the shared bus 30 has a copy of the requested data and receives a “Bus Write Miss”, the status is “Private Clean”. "Or" Sh
"ared Clean" (a) The requested data is block-transferred to the cache memory 12 on the master side, and the cache memory 12
Invalidates the state of. When the state is "Dirty" (a) The requested data is block-transferred to the cache memory 12 and the main memory 20 on the master side, and the state of the cache memory 12 is invalidated.

As described above, (a), (b), (b1), (b)
Operations such as 2) are individually performed in one synchronization unit,
That is, it is performed as a unit for requesting the bus right.

Then, (1) the processor read
In the case of a miss and (4) a processor write miss, it is necessary to wait for data sent from another cache memory 12 or the main memory 20, and the order from these is not guaranteed. Therefore, the monitoring unit 14 buffers the signal from the shared bus 30 in the buffer memory 14a during the maximum delay time of the system.

Further, the state management unit 15 determines the state of the cache memory 12 based on the signal sent within the monitoring time by the monitoring unit 14. The rules for the determination are as follows in order of priority. (1) Swap-out from other cache memory 12 (2) Data block transfer from other cache memory 12 (3) Data block transfer from main memory 20 The state management unit 15 monitors according to such priorities. After a lapse of time, the state of the cache memory 12 is written. The division of the operation of the processor element 10 is the division of the operation on the shared bus 30, and there is no need to divide the operation related to the state transition of the cache memory 12 as described above.

Further, when the delay time of the signal is taken into consideration, there is a state in which an event occurs simultaneously with respect to the same block. Various state transitions in such a case will be described below using two processor elements as an example.

FIGS. 4 to 10 are diagrams showing the state. In these figures, Pi and Pj are processor elements, respectively, and each processor element P
The length indicated by the thick line on the time axis of i, Pj is the shared bus 30
The time when the monitoring unit 14 monitors a signal flowing (broadcasting) thereover is shown.

[1] When a plurality of read misses occur simultaneously for the same block (FIG. 4) In FIG. 4, "read miss" indicates that the processor has made a read miss, and "RM" Is a read miss signal, “SH” is a shared response, “shared”
Indicates that the state of the cache memory is Shared Clean
It has become. In the case of (a), before the read miss signal from the processor element Pi reaches the processor element Pj, the processor element P
This is the case where a read miss signal is output from the j side to the same block. In the case of (b), the read miss signal is output from the processor element Pi to the processor element Pj.
, A read miss signal is output from the processor element Pj side. In the case of such two patterns, the processor P which has both received the read miss signal
i returns a response SH to be shared, and changes its state to “Sha
red Clean ".

That is, these processor elements Pi,
After transmitting the read miss signal, Pj receives the corresponding block of data from the cache memory 12 or the main memory 20 of another processor element. In either case, Pj shares this block and
"SharedCl"
ean ”.

[2] When Read Miss and Write Hit for the Same Block Occur Simultaneously (FIG. 5) In FIG. 5, "write hit" indicates that the processor has caused a write hit, and "WH" Indicates a write hit signal, and “IV” indicates an invalidation response. "Shared" indicates that the state of the cache memory is Shared Clean, and further,
"Dirty" indicates that the state of the cache memory is dirty.
And "invalid" indicates that the state of the cache memory is invalid.

Here, (a) shows that a write hit signal from the processor element Pi is output from the processor element Pj.
In this case, a read miss signal is output from the processor element Pj side to the same block before the write hit signal reaches the processor element Pj before the write hit signal reaches the processor element Pj. This is a case where a read miss signal is output from the element Pj side.

In the case of such two patterns, the processor Pi, which has both received the read miss signal, returns a response IV for invalidation and changes its state to "Dirty". When receiving the invalidation response, the processor element Pj changes its own state to “Invalid”. That is, in the cache memory 12 of the processor element Pi,
Since the new data has been written, the block does not match the block of the main memory 20, and if another cache memory 12 has the same block, the data becomes invalid.

After the monitoring time, the processor element Pj changes the state of the cache memory 12 to "Inval.
Then, the read miss signal is transmitted again.

[3] Case where a read miss and a write miss occur in the same block at the same time (FIG. 6) In FIG. 6, “write miss” indicates that the processor has made a write miss, and “WM” is a write miss. Represents a signal. Here, (a) and (b) show a read miss from the processor element Pj side to the same block before the write miss signal from the processor element Pi reaches the processor element Pj, as in the case of the above [2]. When a signal is output, or after a write miss signal reaches processor element Pj from processor element Pi, processor element P
This is a case where a read miss signal is output from the j side. (C) is a case where the read miss signal from the processor element Pj reaches the processor element Pi first.

In such a case, as in the case of the above [2], all the processor elements Pi
A response to invalidate j is returned, and the processor element Pj
Receives the invalidation response, changes its state to “Invali
d ”. In this case, the processor element Pj
During the monitoring time, it is conceivable that data for a read miss is received from a processor element other than the processor element Pi or the main memory 20, but since the data other than the processor element Pi is incorrect data, it is set to "Invalid". Things.

If the processor element Pi does not receive a notification of occurrence of an event such as a write hit or a write miss from a processor element having a higher priority as described later within the monitoring time, the processor element Pi changes its state to “Dirty”. ".

[4] Simultaneous occurrence of a plurality of write hits or write misses for the same block (FIGS. 7 to 9) As shown in the figure, there are eight patterns (a) to (h). ) And others. That is, the pattern of (a) indicates that the processor Pi in transition of the write hit is
Is a case where a write hit signal is received from the processor element Pj which is another processor element, and in this case, it follows the priority of the processor. For example, if the received signal has a higher priority than the own processor element, the status of the own signal is set to "Invalid". If the received signal has a lower priority than the own processor element, the received signal is ignored.

In the examples shown in FIGS. 7A to 7H, the priority of the processor element is set to Pi> Pj. Therefore, in FIG. 7A, the processor element Pi changes its state to “Dirty”. The processor element Pj sets its state to “Invalid”.

In the pattern (b), a write hit occurs when the processor element Pi is in the “Shared Clean” state, the processor element Pj receives the write hit signal, and thereafter the processor element Pj receives the write hit signal.
j is a case where a write miss signal is transmitted. in this case,
If the processor element Pi does not receive a notification of occurrence of an event such as a write hit or a write miss from another processor element having a higher priority than itself during the monitoring time,
The state is set to “Dirty”, and the processor element Pj sets the state to “Invalid” after the monitoring time.
d ”.

Next, the pattern (c) shows that the processor element Pi is a write miss and the processor element Pj
Is a light hit. In this case, since the processor element Pi has a higher priority, an invalidation signal is sent to the processor element Pj, and its state is set to "Dirty".

The pattern (d) shows that the processor element Pi is a write hit and the processor element P
j is an example of a write miss. Also in this case, the processor element Pi having a higher priority returns an invalidation response to the processor element Pj and changes its state to "D".
irty ”.

Then, the pattern of (e) corresponds to the above (d)
In this case, the processor element Pi is a write miss and the processor element Pj is a write hit. However, also in this case, since the state transition is performed according to the priority, the processor element Pi having a higher priority returns an invalidation response to the processor element Pj, and sets its own state to “Dirty”.

Further, the patterns (f), (g) and (h) are for the case where both the processor elements Pi and Pj are write misses, and when (f) occurs almost simultaneously,
(G) is a case where the processor element Pi occurs earlier and its write miss signal arrives earlier than a write miss occurrence of the processor element Pj, and (h) is a case opposite to (g). Also in these examples, the processor element Pi having the higher priority is set to the processor element Pj of the partner.
Returns a response to invalidate the status and changes the status to "Dirty".
And

[5] When a read miss or write miss and a swap-out occur simultaneously in the same block (FIG. 10) In (a) and (b), a read miss or a write miss occurs in the processor element Pi, and the processor This is an example in which a swap-out has occurred in the element Pj. In such a case, regardless of the priority of the processor element, the event of the swap-out is prioritized, so that the data block transferred from the main memory 20 for the read miss or the write miss of the processor element Pi becomes invalid, and the monitoring time After that, the processor element Pi sends out a read miss signal or a write miss signal again. The processor element Pj that has been swapped out has no data block in its cache memory 12.

As described above, in the above embodiment, the maximum delay time of the system is determined by monitoring the signal from the shared bus 30 and determining the maximum delay time of the cache memory 12 according to a predetermined rule.
Is determined, the cache memory 2 can receive correct data, for example, even in the conventional example shown in FIG. That is, in the example of FIG. 2, the cache memory 2 receives data from the main memory 3 after m hours, but this data is invalidated by a swap-out signal from the cache memory 1 input within the monitoring time. Then, the cache memory 2 sends a read miss signal again, and correct data is sent from the main memory 3 by the read miss signal.

In the above embodiment, the Illinois protocol has been described as an example of a protocol for making the cache memory consistent in the multiprocessor system. However, the present invention is not limited to this, and various protocols such as the Berkeley protocol can be applied. is there.

[0055]

As described above, according to the cache memory control device of the present invention, the operation group of the processor element is divided, the synchronization unit exclusively occupies the network only at the time of signal transmission, and the request is generated from the request generation. Monitors the input signal from the network for the maximum time required to receive a response to, and determines the data state of the cache memory according to a rule based on a signal input within the monitored time and a predetermined priority. As a result, the utilization efficiency of the network is improved, so that it can be replaced with a large-scale bus for a large-scale system or a general-purpose network connection network, and an improvement in the performance of the entire system can be expected.

[Brief description of the drawings]

FIG. 1 is a block diagram of a cache memory control device of the present invention.

FIG. 2 is a main part configuration diagram of a multiprocessor system for explaining a conventional problem.

FIG. 3 is an explanatory diagram of a state transition of an Illinois protocol relating to the cache memory control device of the present invention.

FIG. 4 is an explanatory diagram when a plurality of read misses occur simultaneously for the same block in the cache memory control device of the present invention.

FIG. 5 is an explanatory diagram when a read miss and a write hit for the same block occur simultaneously in the cache memory control device of the present invention.

FIG. 6 is an explanatory diagram of a case where a read miss and a write miss occur simultaneously for the same block in the cache memory control device of the present invention.

FIG. 7 is an explanatory diagram when a plurality of write hits or write misses to the same block occur simultaneously (part 1) in the cache memory control device of the present invention.

FIG. 8 is an explanatory diagram of a case where a plurality of write hits or write misses to the same block occur simultaneously (No. 2) in the cache memory control device of the present invention.

FIG. 9 is an explanatory diagram of a case where a plurality of write hits or write misses to the same block occur simultaneously (part 3) in the cache memory control device of the present invention.

FIG. 10 is an explanatory diagram of a case where a read miss or a write miss and a swap-out occur simultaneously for the same block in the cache memory control device of the present invention.

[Explanation of symbols]

 10-1 to 10-n Processor element 11-1 to 11-n Processor 12-1 to 12-n Cache memory 13-1 to 13-n Synchronization unit control unit 14-1 to 14-n Monitoring unit 15-1 15-n state management unit

──────────────────────────────────────────────────続 き Continued on the front page (58) Field surveyed (Int.Cl. ⁷ , DB name) G06F 12/08

Claims (1)

(57) [Claims] 1. A cache memory control device for a multiprocessor system, wherein processor elements each having a processor and a cache memory are connected to a network having a broadcasting function, wherein each of the processor elements includes a signal of each processor element. A synchronization unit control unit that occupies the network only at the time of transmission; and after the processor element releases the right to occupy the network, the synchronization unit control unit transmits the synchronization unit control unit from the network for a maximum time necessary for receiving a response to a request from the processor element. A monitoring unit that monitors the input signal of the plurality of input signals, a content of an input signal, a priority of a predetermined operation, and the plurality of programs during a monitoring time by the monitoring unit.
A cache memory control device comprising: a state management unit that determines the state of data in the own cache memory that has generated the request according to the priority of each of the processor elements .