JP3068427B2 - Message control unit - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a message control device, and more particularly to a message control device having a plurality of buffers for transmitting a plurality of types of requests to a common bus in a system in which a plurality of devices are connected to a common bus. .

[0002]

2. Description of the Related Art Conventionally, in this type of technology, there are two FIFOs, a request FIFO which is a first-in first-out buffer (hereinafter referred to as a "FIFO") for holding a request for another device and a response FIFO for responding to a request from another device. Is configured. For example, Japanese Patent Application Laid-Open No. 5-189391 discloses a technique of a system connected by a multistage switch network.

[0003] Referring to FIG. 4, in the above prior art, a plurality of processor memory elements (hereinafter, referred to as “PME”) 701, 702, 703, and 704 are connected through a multistage switch switching network 705. The multistage switch switching network 705 includes a plurality of stages 711 and 712, and each stage has the same number of switches 721 to 724 as the PME.
Consists of Each switch includes a request FIFO 731 for storing a request message, a response FIFO 732 for storing a response message, a request FIFO and a response FIFO.
A message selector 733 for selecting the next message to be transmitted from O is provided. The prior art includes two types of FIFOs, a request FIFO and a response FIFO, and a response FIFO.
By sending the message in the upper row to the next stage always, control is performed so that deadlock does not occur.

[0004]

In the above-mentioned prior art,
In order to solve the deadlock problem, the response message is preferentially transmitted to the next stage.
24, a phenomenon occurs in which a request message that arrives first is overtaken by a response message that arrives later, and the waiting time for the request message increases. Therefore, the load increases once, and the number of response messages in the switch increases. Until the new request message stagnates and the load is reduced to some extent, the system performance is reduced.

[0005] In order to solve this, it is necessary to transmit messages to the next stage in the order in which they arrive at each switch.
If this can be realized, a certain performance can be realized regardless of the load. However, processing messages in the order of arrival may result in deadlock as follows.

Referring to FIG. 5, in a diagram showing a state in which a deadlock has occurred between CPU 1 and CPU 2, for example, REQ 12
2 means a request, and RES12 means a response from CPU1 to CPU2. In the response FIFOs 732 and 742, all entries are filled with requests, and a new request cannot be accepted. Moreover, the request FIFO 73
Since the requests 1 and 741 were input earlier, the response FIFO must be output unless this request is output.
No output from 732 or 742. On the other hand, the request FI
The FOs hold requests destined for the other side of the CPU 1 or the CPU 2 and it can be seen that the FO is in a deadlock state.

An object of the present invention is to provide a message control device which prevents or eliminates the occurrence of such a deadlock.

It is another object of the present invention to provide a message control device for preventing occurrence of overtaking between the above messages.

[0009]

In order to solve the above problems, a message control device according to the present invention has a request buffer having a plurality of entries and holding a request message to another device, and a plurality of entries. A response buffer for holding a response message to another device, and a plurality of entries.
A reception buffer for holding a request message from another device Te, select a detection means for detecting that the reception buffer is full, a message stored in one of the request buffer and the response buffer Pertinent
A selector for outputting to another device that is a destination of a message, the selector including the request buffer or the response buffer from the earliest when the detecting unit does not detect the full state of the reception buffer. The input message is output, and when the detection means detects that the reception buffer is full, the message held in the response buffer is output with priority.

[0010] Another message control apparatus of the present invention includes a request buffer for holding a request message to another device having a plurality of entries, a plurality of entries
A response buffer for holding a response message to another device, and a predetermined buffer provided for each entry in the response buffer
, A reception buffer having a plurality of entries and holding a request message from another device, and a priority output when the reception buffer is detected to be full. A value indicating that all of the flags
Detecting means for setting a message stored in one of the request buffer and the response buffer, and selecting the message stored in the other buffer as a destination of the message.
And a selector for outputting the message corresponding to the earliest message input to the response buffer.
A value indicating that the flag should be output with priority is set in the flag.
Tsu if not bets outputs earliest input message to the request buffer or the <br/> response buffer are output preferentially in flag corresponding to the earliest input message in the response buffer To do
If the value indicated is set to output a response message earliest input to the response buffer.

Further, another message control device of the present invention includes a request buffer having a plurality of entries and holding a request message to another device, a read pointer indicating a reading position from the request buffer, A write pointer indicating a write position in the request buffer, a response buffer having a plurality of entries and holding a value of the write pointer at that time together with a response message to another device; Provided predetermined
, A reception buffer having a plurality of entries and holding a request message from another device, and a priority output when the reception buffer is detected to be full. A value indicating that all of the flags
A detecting means for setting relative to the flag corresponding to the entry matched by comparing the value of the write pointer is held in the response buffer with the value of the read pointer
The selected comparison means for setting a value indicating that to be preferentially output against a message stored in one of the request buffer and the response buffer
A selector for outputting to another device that is a destination of the message , wherein the selector has a value indicating that the message is to be preferentially output in a flag corresponding to the message input first in the response buffer. is but outputs a request message earliest input to the request buffer if not set, the value indicating that to be preferentially output in flag corresponding to the earliest input message in the response buffer If that is set to output a response message earliest input to the response <br/> answer buffer.

Further, in another message control device of the present invention, each of the request buffer, the response buffer, and the reception buffer is constituted by a first-in first-out buffer.

[0013]

[0014]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, an embodiment of the message control device of the present invention will be described in detail with reference to the drawings.

Referring to FIG. 1, in one embodiment of the present invention, a plurality of central processing units 201,
202, main storage devices 205 and 206, and input / output devices 203 and 204 are connected. Each device includes a request FIFO 114 and a response FIFO 108 for waiting for a message to be transmitted to the system bus 200.
Also, each device has a reception REG 105 for receiving a message from another device connected to the system bus 200, an address array 104 for determining whether a message from the other device is addressed to its own device, a determination result and a message of the other device. FIFO 107 for storing the
The reception FIFO control unit 106 that controls the reception 107, the reception F
A deadlock condition detecting unit 111 for detecting a deadlock from the state of the FIFO 107, a mark flag 110 for marking the priority of the response FIFO 108 when the deadlock condition is detected, and a write pointer for each entry of the response FIFO 108 A pointer comparator 109 for comparing the value with the value of the request FIFO read pointer 112; a FIFO selector 115 for selecting the system bus of the request FIFO 114 or the response FIFO 108 according to the value of the output line 116 of the order control mark flag; Devices 101 and 102 and arithmetic processing device 1
It has a message selector 103 for selecting messages from 01 and 102.

The request received by the reception FIFO 107 from another device becomes a response message via a memory access (not shown) or the like, and is held in the response FIFO 108.

The response FIFO 108 holds the response message and the value of the write pointer 113 at that time in each entry as a pair. The order control mark flag 110 has a one-to-one correspondence with each entry of the response FIFO 108.

Upon receiving a request from the selector 103, the request FIFO 114 holds the request in the entry indicated by the write pointer 113. Thereafter, the write pointer 113 is counted up by one. When the request FIFO 114 is selected by the selector 115, the request FIFO 114 outputs a request from the entry indicated by the read pointer 112. Read pointer 11
2 is then incremented by one. That is, the request FIFO 114 has a ring buffer configuration and is controlled by the read pointer 112 and the write pointer 113.

The order control mark flag 110 is provided for each entry of the response message, and is set to 1 in the following two cases. The first is the pointer comparison device 109
Is set individually for the entry for which a match has been detected. This is the request FIFO 114 or the response F
This is to guarantee the order in which the requests or responses are input to the IFO 108. Response FIFO 10 as described above
8 holds a pair of the value of the write pointer 113 at the time of input in addition to the response message in each entry. By referring to the value of the write pointer, a value between the request FIFO 114 and the response FIFO 108 is stored. Order relation can be guaranteed.

For example, if there is an input to the FIFO in the order of first request → first response → second response → second request, the first request is input to the first entry of the request FIFO 114. Thereafter, the first response is input to the first entry of the response FIFO 108, and the second response is input to the second entry. At this time, the write pointer 11 of the response FIFO 108
"2", which is the value of 3, is held. Then the request FIF
The second request is input to the second entry of O114. When reading this, first, from the request FIFO 114, the first
Is output, the read pointer 112 becomes "2".
Becomes, because the match is detected in the first entry and the second entry by the pointer comparator 109, the corresponding sequence control mark flag 110 is set to 1. As a result, the selector 115 sets the response FIFO 108
Side is selected, and a second response is output following the first response.

In the second case where the order control mark flag 110 is set to 1, the deadlock condition detecting section 111
Is a case where the possibility of occurrence of deadlock is detected. In this case, all the order control mark flags 110 are set to 1. That is, when the occurrence of the deadlock is predicted, the response in the response FIFO 108 at that time is output with priority.

The occurrence of deadlock is predicted as follows. The reception FIFO control unit 106 receives the reception FIFO 1
07 is transmitted to the deadlock condition detecting unit 111 in a full state. In response to this, when the reception FIFO 107 is full, the deadlock condition detection unit 111 determines that there is a possibility of deadlock, and
Order control mark flag 110 for all entries of FO 108
To the order control mark flag 110. In response, the order control mark flag 110
Sets the order control mark flag 110 of all entries to one.

The order control mark flag 110 thus set to 1 is cleared to 0 at the time when the corresponding request is issued.

By setting the order control mark flag 110 in this manner, the request FIFO 114 or the response FIFO 114 can be used unless the possibility of deadlock is predicted.
Responses or requests can be output from both FIFOs to the system bus 200 while maintaining the order of input to 108.

Next, the operation of the embodiment of the present invention will be described in detail with reference to the drawings.

Referring to FIGS. 1 to 3, first, when the arithmetic processing unit 101 or 102 issues a request message (step 501), the message selector 103 selects the issued message (step 502). This selection is performed by, for example, round robin. Then, the address array 104 is searched by the selected message (step 503). Thus, it is determined whether a request message should be transmitted to system bus 200 (step 504). If the central processing unit 201 does not hold the requested data as a result of the search, the request message is stored in the request FIFO 114 (step 505). When the central processing unit 201 holds the requested data, the data in the central processing unit is returned to the arithmetic processing unit 101 or 102, and the process is terminated. Buffer order control mark flag 110
(Step 506), and when the buffer order control mark flag = 1, the FIFO selector 115 selects the contents of the response FIFO 108 (step 50).
7) A response message is transmitted to the system bus 200 (step 508), and then the request FIFO 114
Wait for the selection by the FO selector 115. If the order control mark flag = 0, the FIFO selector 11
5 selects the request FIFO 114 (step 50
9) Output a request message to the system bus 200 (step 510). The output request message is held in the reception REG 105 by the other central processing unit 202, the input / output device 203 or 204, or the main storage device 205 or 206 (step 511). The message received in this manner is stored in the address array 10
4 (step 512), thereby determining whether the request is for the own device (step 51).
3). If the request is for a device other than the own device, the process ends. If the request is for the own device, the message is stored in the reception FIFO 107 (step 514). Then, a response to the request message is created by memory access (not shown) or the like, and this is stored in the response FIFO 108 as a response message (step 515).

The request FIFO 1 thus input
14 or when the reading of the response FIFO 108, to check the contents of the sequence control mark flag 11 0 (step 516). If the flag = 0, the FIFO selector 115 selects the request FIFO 114 (step 524), and outputs a request message to the system bus 200 (step 525). This is repeated until the flag becomes 1. When the order control mark flag = 1, FI
The FO selector 517 selects a response FIFO (step 517), and outputs a response message to the system bus 200 (step 518). The output request message is held in the reception REG 105 by the other central processing unit 202, the input / output device 203 or 204, or the main storage device 205 or 206 (step 519). The message received in this manner is used for searching the address array 104 (step 520), and it is determined whether the message is a request to the own device (step 521). If the request is for a device other than the own device, the process ends. If the request is for the own device, the message is stored in the reception FIFO 107 (step 522).
Then, the processing unit 1 that is the transmission source of the request message
A response message is returned to 01 or 102 (step 523).

As described above, according to the message control device of one embodiment of the present invention, the deadlock condition detecting unit 11
1 detects the possibility of deadlock occurrence and sets the order control mark flag 110, so that the response FI
Deadlock can be avoided by giving priority to output from the FO. In addition, by holding the value of the write pointer 113 to the request FIFO 114 at the time of input in the response FIFO 108, the request FIFO 114 and the response F
It is possible to prevent passing of the message to and from the IFO 108.

[0029]

As is apparent from the above description, according to the present invention, the response FI is detected by detecting the possibility of deadlock.
Deadlock can be avoided by giving priority to output from the FO side. Also, by holding the value of the write pointer to the request FIFO when the response FIFO is input, it is possible to prevent the passing of the message between the request FIFO and the response FIFO.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a configuration of an embodiment of a message control device of the present invention.

FIG. 2 is a diagram illustrating an operation of a message control device according to an embodiment of the present invention.

FIG. 3 is another diagram showing the operation of the message control device according to the embodiment of the present invention.

FIG. 4 is a diagram illustrating an example of a system configuration according to the related art.

FIG. 5 is a diagram showing a state of occurrence of a deadlock in a conventional message control device.

[Explanation of symbols]

 101, 102 Processing unit 103 Message selector 104 Address array 105 Receiving REG 106 Receiving FIFO control unit 107 Receiving FIFO 108 Response FIFO 109 Pointer comparator 110 Order control mark flag 111 Deadlock condition detecting unit 112 Request FIFO read pointer 113 Request FIFO write Pointer 114 Request FIFO 115 FIFO selector 116 Sequence control signal 117 System bus output signal 118 System bus input signal 200 System bus 201, 202 Central processing unit 203, 204 Input / output processing unit 205, 206 Main storage device 701-704 Processor memory Element 705 Crossbar network 711,712 Each stage of the crossbar network 721-724 Switch 731 Request FIFO 732 Response FIFO 733 Message selector

──────────────────────────────────────────────────続 き Continued on the front page (58) Field surveyed (Int.Cl. ⁷ , DB name) G06F 15/16-15/177

Claims (4)

(57) [Claims] 1. A response buffer that holds a request buffer for holding a main <br/> determined message to other devices having a plurality of entries, the response message includes a plurality of entries to other devices A reception buffer having a plurality of entries and holding a request message from another device; a detection unit for detecting that the reception buffer has become full; and any of the request buffer and the response buffer of the message by selecting a message that is held
A selector for outputting to another device that is a destination , wherein the selector is input to the request buffer or the response buffer from the earliest when the detection unit does not detect the full state of the reception buffer. A message control unit that outputs a message stored in the response buffer when the detection unit detects a full state of the reception buffer. 2. A response buffer that holds a request buffer for holding a main <br/> determined message to other devices having a plurality of entries, the response message includes a plurality of entries to other devices And a predetermined value provided for each entry of the response buffer.
Shown but a flag is set, a receiving buffer for storing a request message from another apparatus having a plurality of entries, the effect to be preferentially output to detect that the reception buffer is full Value to all of the above flags
Detecting means for setting the message, and selecting a message held in one of the request buffer and the response buffer to select the message.
A selector for outputting to a destination other device , wherein the selector sets a value indicating that the message is to be preferentially output in a flag corresponding to the message input first in the response buffer. the main <br/> outputs earliest input message to determined buffer or the response buffer is outputted preferentially in flag corresponding to the earliest input message in the response buffer if it is not If the value indicating that it should be set is set
A message control device for outputting a response message input first to said response buffer. 3. A request buffer having a plurality of entries and holding a request message to another device, a read pointer indicating a reading position from the request buffer, and writing to the request buffer. A write pointer indicating a position; a response buffer having a plurality of entries and holding the value of the write pointer together with a response message to another device; and a predetermined buffer provided for each entry of the response buffer . value
Shown but a flag is set, a receiving buffer for storing a request message from another apparatus having a plurality of entries, the effect to be preferentially output to detect that the reception buffer is full Value to all of the above flags
A detecting means for setting to, matched entry by comparing the value of the write pointer is held in the response buffer with the value of the read pointer
That priority should be given to the corresponding flag
Comparing means for setting a value indicating the message, and selecting a message held in one of the request buffer and the response buffer and selecting the message
A selector for outputting to a destination other device , wherein the selector sets a value indicating that the message is to be preferentially output in a flag corresponding to the message input first in the response buffer. It is when outputs no earliest entered request message to the main <br/> determined buffer, the effect to be preferentially output in flag corresponding to the earliest input message in the response buffer
Message controller when the value indicated is set and outputs a response message earliest input to the response buffer. 4. The request buffer, the response buffer,
4. The message control device according to claim 3 , wherein each of the reception buffers is configured by a first-in first-out buffer.