JPH0583943B2 - - Google Patents

Description

[Detailed description of the invention] [Industrial application field]

The present invention relates to a parallel computer comprising a plurality of independently operable processing elements and a network that enables communication between them.

[Conventional technology]

In a conventional parallel computer, as described in Japanese Patent Application Laid-Open No. 62-274451 (hereinafter referred to as the first conventional technology), data output from a transmitter processor is sent to an interconnection network in the order in which it is output. Furthermore, data arriving from the interconnection network is taken into the receiving processor in the order in which it is received. In other words, the data transfer from the source processor to the interconnection network is
This was done by writing data from the processor to the transmit data register, then transferring it from the transmit data register to the transmit register, and then from the transmit register to the interconnect network. Furthermore, data is transferred from the interconnection network to the destination processor by transferring the data from the interconnection network to the reception data register, from the reception data register to the reception data register, and then from the reception data register to the processor. This was done by being transferred to. Although it is not a parallel computer, in a system in which a large number of processors are arranged in a distributed manner, as described in Japanese Patent Application Laid-Open No. 58-40952 (hereinafter referred to as the second prior art), it is necessary to send data to a communication line. It is known that priority control is used when In other words, when transmitting data from the source processor to the line, high-priority priority data and low-priority non-priority data are stored in the first memory and second memory, respectively, and the priority data is stored consecutively up to a predetermined number. Only one piece of data is output to the third memory when a predetermined condition is met for non-priority data, and when the line becomes available, the data in the third memory is output to the third memory. was output to the line.

[Problem to be solved by the invention]

In the first conventional technique, data that requires urgent transfer and data that does not need to be transferred are not distinguished and transferred. Furthermore, unless the transfer of one data is completed, the next data to be transferred cannot be output from the processor. For this reason, it is not possible to transfer data that is desired to be transferred as soon as possible with priority over other data. Furthermore, in the second prior art, there is a distinction between priority data and non-priority data in the data to be transmitted, but the receiving processor can process the data only in the order in which it is transferred from the line. Networks such as a crossbar configuration are often used in parallel computers. In this case, the source of the data sent to one receiving processor is
Not one. For this reason, even if the priority data at the source is output to the network early, the processor on the receiving side cannot receive it with priority. In a parallel computer, when distributing the load between processors, it is necessary to know the load of other processors as soon as possible. In such a case, with the above-mentioned conventional technology, there is a possibility that the inquiry of the load value to other processors and the reply from there may be delayed. During this delay, a change in the load of the processor to be queried occurred, making it impossible to know the correct load value for that processor, making it impossible to dynamically perform desirable load distribution. An object of the present invention is to provide a parallel computer that can more quickly transfer urgent data.

[Means to solve the problem]

In order to achieve the above object, the present invention uses a message identifier to determine whether a message output from a processor in a processing element requires urgent forwarding, and if the message requires urgent forwarding, another processing A means is provided for selecting a message that requires urgent transfer as a message to be transmitted next to a network, giving priority to messages waiting to be transmitted stored in a means for storing messages to be transferred to an element. Furthermore, it is determined based on the message identifier whether a message transferred from the network requires immediate forwarding, and if the message requires urgent forwarding, it is stored in a means for storing messages forwarded from other processing elements. Means is provided for selecting a message that requires urgent forwarding as the next message to be processed by the processor, giving priority to messages waiting to be processed.

[Effect]

A message output from a processor in a processing element is determined by means for determining whether the message requires urgent forwarding, and if the message requires urgent forwarding as a result of the determination, it is forwarded to another processing element. The waiting time until the message is sent to the network is short because it is sent to the network with priority over messages that are already stored in the storage means and are waiting to be sent. In addition, a message newly received from the network is judged by a means for judging whether or not the message requires urgent forwarding, and if the result of the judgment is that the message needs to be forwarded immediately, the message is sent from another processing element. Since messages that are already stored in the transferred message storage means and are being input to the processor are given priority to be processed, urgent messages can be transferred quickly.

【Example】

An embodiment of the present invention will be described below with reference to FIGS. 1 and 2. FIG. 1 shows an example of a parallel computer implementing the present invention. In the diagram, PE ₁ to _{PE o} are processing elements, NET is network, and CPU ₁ to _{CPU o.}
are processors in processing elements PE ₁ to PE _o . OD ₁ to OD _o are output registers,
OB ₁ or OB _o is the output buffer, SO ₁ or SO _o
is the output selector, OR ₁ or OR _o is the receive register, IB ₁ or IB _o is the input buffer, SI ₁ or SI _o
is an input selector, and ID ₁ to ID _o are input registers. ODEC ₁ to ODEC _o are output identification decoders, and IDEC ₁ to IDEC _o are input identification decoders. LOR ₁ to LOR _o are logical sum circuits. Next, the functions of each component shown in FIG. 1 will be explained. NET is a network that transfers a message to a processing element specified in the message, such as a crossbar or omega network. C5−l or C5−
n is for a processing element attempting to send a message to the network NET.
This is a signal output from the network NET that instructs to suppress message transmission. These signals are
'1' if the transfer of a message previously received by the network has not been completed due to network NET blockage; '0' otherwise.
Since the processing elements PE ₁ and PE _o have the same components, the processing element PE ₁ will be explained below as an example. Processor CPU ₁ is
For example, Hitachi's microprocessor H32
It consists of memory and other peripherals connected to it. OD ₁ is an output register through which CPU ₁ receives messages to be transferred to other processing elements from line 11-1. The format of this message is shown in FIG. A message consists of a PE number field f _p indicating the number of the processing element to which the message is transferred, an identifier field f _i indicating whether the message requires urgent transfer, and a message data field f _d . The format of this message is the output register
This format is common to OD ₁ , output buffer OB ₁ , transmission register OR ₁ , reception register IR ₁ , input buffer IB ₁ , and input register ID ₁ . When CPU ₁ writes a message to output register OD ₁ , inhibit signal C5
If -1 is '1', even if the message you are trying to write requires immediate forwarding,
The CPU ₁ suspends writing until the inhibition signal C5-1 becomes '0'. Furthermore, the value of the identifier field f _i is
On CPU ₁ , it can be determined programmatically when creating a message. The output identification decoder ODEC ₁ decodes the identifier field f _i of the message input to the output register OD ₁ , and in the case of a message that requires urgent transfer, it outputs '1' on the line C1-1 and '1' on the line C2-1.
0', otherwise output ' to line C1-1.
0', output '1' to line C2-1. LOR ₁ is an OR circuit, and when one or both of line 1-1 and line C5-1 is '1', line C12-
Outputs '1' for 1 and '0' otherwise. The output buffer OB ₁ is a FIFO, and when the output C2-1 of the output identification decoder ODEC ₁ is '1', it reads the message in the output register OD ₁ via the line l2-1, and also reads the message in the output register OD 1 through the line l2-1. LOR output C12-1
If is '0', messages are output to line l3-1 in the order in which they are read, otherwise they are not output. Output selector SO ₁ is output identification decoder
When output C1-1 of ODEC ₁ is '0', output l3-1 of output buffer OB ₁ is selected and output C1-1 is '1'.
In this case, the output l2-1 of the output register OD ₁ is selected and output to the line l4-1. Transmit register OR ₁
takes the output l4−1 of output selector SO ₁ as input,
Output to network NET from line l5-1.
Receive register IR ₁ is the output l6 of the network NET
Enter the message from -1. The input identification decoder IDEC ₁ decodes the identifier field f _i of the message input into the receiving register IR ₁ and, in the case of a message that requires urgent forwarding, sends an '' to the line C3-1.
1', outputs '0' to line C4-1; otherwise, '0' is output to line 33-1, and '1' is output to line C4-1. . The input buffer IB ₁ is FICO, and when the output C4-1 of the input identification decoder IDEC ₁ is '1', the message of the receiving register IR ₁ is sent to the line l7-1.
If the output C4-1 of the input identification decoder IDEC ₁ is '0' and the read instruction signal _p1 from the CPU ₁ is '1', the messages are sent to the line l8-1 in the order in which they are read. output, otherwise do not output. When the output C3-1 of the input identification decoder IDEC ₁ is '0', the input selector SI ₁
Select output l8-1 of input buffer IB ₁ and connect line C3
If −1 is '1', the output l7− of receiving register IR ₁
1 is selected and output to line l9-1. The input register ID ₁ receives the output l9-1 of the input selector SI ₁ and outputs it to the CPU ₁ from the line l10-1. CPU ₁
When the line C3-1 is '1', this is used as an interrupt signal and a predetermined process is immediately performed. Also,
The CPU ₁ stores data in the input buffer IB ₁ at the end of a certain process, for example, when one task is completed. To read messages waiting to be processed,
It outputs '1' to the read instruction signal _p1 , reads the message, and processes it. The above is an explanation of the functions of each component of the parallel computer shown in FIG. Next, the operation of this parallel computer will be explained. Peripheral devices (not shown) are connected to the CPU of each processing element, and a plurality of tasks are input to the CPU from a terminal device (not shown) among them. Each processing element (e.g. PE ₁ ) processes an input task, but
When the load on that CPU (for example, CPU ₁ ) becomes too large, for example, when the execution waiting time of a task becomes larger than a certain value, the number of another processing element (for example, PE _o ) and an identifier indicating urgent transfer are sent. and data indicating the number of the processing element PE ₁ that made the inquiry. Creates a message for the inquiry and sends it to its processing element via the network NET.
PE _o to inquire about the task execution wait time. The processing that received the message
An interrupt occurs to CPU _o in element PE _o , interrupts normal processing, and immediately sends data to processor CPU _o indicating the task execution waiting time, an identifier f _i indicating urgent transfer, and the source processing.・Create a reply message consisting of the number of element PE ₁ and send the reply. however,
At this time, as the number of the processing element that is the inquiry source, the number written in the data in the received inquiry message is used as is. The queryer's processing
CPU ₁ of element PE ₁ compares the execution waiting time of the task on its own CPU ₁ with the returned execution waiting time of the task on CPU _o of another processing element PE _o , and determines the execution waiting time of the task on its own CPU ₁ . When the execution waiting time of a task is longer, the task being processed by its own CPU ₁ is transferred along with the program and data to its processing element PE _o using a message without an identifier requesting urgent transfer. Processing tasks to other processing elements
Let PE _o do it. After the task is completed, the result is sent as a non-urgent message.
Transferred to processor CPU ₁ in original processing element PE ₁ . Messages such as transfer of task processing results to any other processing element are sent to the output buffer OB ₁ in the processing element PE ₁ that is the inquirer.
, even if the input buffer remains unprocessed IB ₁ or the output buffer OB o or input buffer _{IB o} in the processing element PE _o to be queried, a message for inquiring about the execution waiting time of the task and a reply message are sent. The message of
As urgent messages, they are transferred with priority over messages remaining in the output buffers OB ₁ and OB _o and the input buffers IB ₁ and IB _o . As shown above, in this embodiment, there is a single network NET, so when implementing it, each processing element PE _i and network
It is possible to quickly transfer messages between processing elements without changing the number of signal lines connecting NET. In this embodiment, in the receiving processing element, if a newly received message requires urgent transfer, the input identification decoder (IDEC _o ) generates an interrupt to the processor (CPU _o ), and the process is started. However, instead of this, after the task being executed in the processor (CPU _o ) is finished, the newly received message is processed by that processor (CPU _o ) as the next message to be processed.
You may also enter it in Of course, using an interrupt as in this embodiment has a great advantage in that a message that needs to be transferred immediately can be processed more quickly.

【Effect of the invention】

According to the present invention, messages that must be exchanged urgently can be transferred more quickly between processing elements.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a parallel computer according to an embodiment of the present invention, and FIG. 2 is a format diagram of messages used in the parallel computer of FIG. NET...Network, PE ₁ , PE _o ...Processing element, CPU ₁ , CPU _o ...Computer,
OD ₁ , OD _o ... Output register, ODEC ₁ , ODEC _o
...Output identification decoder, OB ₁ , OB _o ...Output buffer, SO ₁ , SO _o ...Output selector, OR ₁ , OR _o
...Transmit register, IR _1, IR _o ...Receive register,
IDEC ₁ , IDEC _o ...Input identification decoder, IB ₁ , IB _o
...Input buffer, SI ₁ , SI _o ...Input selector,
ID ₁ , ID _o ...Input register, LOR ₁ , LOR _o ...
OR circuit.

Claims (1)

[Scope of Claims] 1 Consists of a plurality of processing elements and a network that transfers messages between them, and each processing element has a processor and a state in which the output from the processor is waiting for transmission to the network. a transmission message storage means for storing messages in the network; and a first transfer control means for sequentially transmitting the stored messages waiting to be sent to the network in response to the fact that a message transmission inhibition signal is not input from the network. and,
Received message storage means for storing messages received from the network and waiting to be processed by the processor, and sequentially transmitting the stored received messages to the processor in response to a received message read request from the processor. and a second transfer control means, the first transfer control means detecting whether a message newly output from the processor is a message that should be transferred immediately by using a message identifier included in the message. If the new message is a message that should be transferred immediately, the new message should be sent next to the network, giving priority to the messages already stored in the sending message storage means. a first selection means for selecting a message, and the second transfer control means determines whether a message newly received from the network is a message that should be urgently transferred. If the newly received message is a message that should be forwarded immediately, it is processed next by the processor in priority to messages waiting to be processed stored in the received message storage means. A parallel computer characterized by having second selection means for selecting the message as an appropriate message. 2 Each time the processor finishes executing a task,
The second selection means reads the received message from the received message storage means, and when the newly received message is a message that should be forwarded immediately, the second selection means selects the second selection means to request processing of the message. 2. A parallel computer according to claim 1, further comprising means for interrupting a processor.