JPH07152712A - Multiprocessor with barrier synchronization - Google Patents

Abstract

(57) [Abstract] [Purpose] To realize barrier synchronization at high speed using a general-purpose multistage connection network. [Configuration] N processing means 110 are connected via a multi-stage connection network 120 of logN stages, and the connection state of a switch box 121 on a path is switched according to control information included at the end of a message. Individual processing means 110
In a multiprocessor configured to communicate with each other,
Prior to the transmission of the message notifying the arrival of the barrier, each processing unit 110 sets the connection state of the switch box 121 of each stage according to the first destination of the message, and the arrival of the barrier. Lo to notify
Through the multistage coupling network 120 and the message transmission means 112 for adding control information according to the next notification destination to the end of the gN number of messages and transmitting it to the multistage coupling network 120,
The determination means 113 determines that all the processing means 110 have reached the barrier when logN messages are received.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multiprocessor which is connected by a multistage connection network and performs barrier synchronization among all the processors connected to the network.

As an example of a network connecting N processors forming a multiprocessor, there is a multistage coupled network such as a binary n-cube or Omega. This multistage network is lo
Two or more switch boxes with two inputs and two outputs are arranged and connected to each of the gN stages, and communication between N processors is controlled by controlling the connection state of these switch boxes. Has been realized.

On the other hand, in the multiprocessor, various synchronization methods have been proposed because it is necessary to synchronize the processes which the processors are proceeding in parallel. Barrier synchronization is
This is an example, and a barrier for synchronization is provided in the processing of each processor, and when all the processors reach this barrier, each processor is allowed to go over the barrier and proceed to the next processing. It is a method.

[0004]

2. Description of the Related Art Barrier synchronization interrupts processing when each processor reaches the barrier, notifies other processors that the barrier has been reached, and receives notifications from the other processors, so that the When both the arrival of the barrier and the arrival of the barrier by another processor are established, the processing is restarted.

A butterfly barrier synchronization method is a method for promptly notifying that all the processors have reached the barrier by the above notification. FIG. 5 shows a message exchange procedure in the butterfly barrier synchronization method.

FIG. 5 shows an example in which the butterfly barrier synchronization system is applied to a multiprocessor consisting of 2 ³ processors. 5, the processing of each processor is represented by
A solid arrow with a symbol indicates a message exchanged by each processor, and a dotted arrow indicates a message exchanged by each processor.

First, the message reaching the barrier is exchanged between the adjacent processors, and then the message is exchanged with the corresponding processor of the set of the adjacent processors which have finished exchanging the messages. This procedure is repeated sequentially, and when each processor receives log2 ³ (that is, 3) messages, it is determined that all the processors have reached the barrier, and the processing is restarted.

In this butterfly barrier synchronization, each processor is connected using a gate circuit as shown in FIG. 6, and when each processor reaches the barrier, a transmission register (R
This can be realized by the configuration in which the logic "1" is output via s) and the output of the gate circuit is received via the reception register (Rr). However, in FIG.
An example in which butterfly barrier synchronization is applied to a multiprocessor system including four processors indicated by reference symbols ~ has been shown.

It is also possible to implement the above-mentioned message exchange procedure by software using a multi-stage connection network connecting the processors. FIG. 7 shows the configuration of a multiprocessor system in which four processors are connected by a binary n-cube type multistage connection network.

In FIG. 7, the binary n-cube type network is composed of four switch boxes and a transmission line connecting them. In addition, each switch box has a straight state in which the input to each of the two input terminals is sent to the corresponding output terminal and a cross state in which the input to each input terminal is sent to the output terminal corresponding to the other, in response to the instruction. There are two states, a state and a state.

Wormhole routing is generally known as a routing method for setting the states of these switch boxes and forming a message transmission path. In this wormhole routing, information about the destination is added to the header of the message, and the switch box at each stage sets its own state according to this information, and the message is transmitted to the destination. is there.

For example, in the case of implementing butterfly barrier synchronization in a system consisting of four processors (-), in phase 0, the first-stage switch box is set to the cross state and the second-stage switch box is set to the straight state, and adjacent to each other. The messages may be exchanged by the processors of the same group, and in the phase 1, the first stage may be in the straight state and the second stage may be in the cross state, and the messages may be exchanged with the corresponding processor of the adjacent processor set as the destination.

Therefore, in this case, as shown in FIG. 8, butterfly barrier synchronization can be realized by executing a program for transmitting / receiving a phase 0 message and executing a program for transmitting / receiving a phase 1 message.

[0014]

By the way, in an actual multiprocessor, the time at which each processor reaches the barrier varies.

For example, as shown in FIG. 9, there are cases where the processor and the set of processors and the set of the processor and the processor arrive at the barrier at significantly different times. Here, in FIG.
The barriers set in the above are indicated by the symbols b1 to b4, respectively, and the message sent by each processor is indicated by a dotted arrow.

In this case, the processors have received the phase 1 message from the processors before exchanging the phase 0 messages with each other.

Therefore, in order to realize the butterfly barrier synchronization by software, it is necessary to determine not only the number of received messages but also the phase of the messages. Therefore, the software becomes complicated and it is difficult to realize barrier synchronization at high speed.

On the other hand, if the butterfly barrier synchronization is realized by hardware, a dedicated gate circuit (see FIG. 6) used only for the barrier synchronization is required, which increases the cost.

Therefore, there is a need for a method for realizing barrier synchronization at high speed by software. here,
The applicant of the present invention has disclosed techniques for enabling message waiting in a multi-stage connection network, as disclosed in Japanese Patent Laid-Open No. 3-91337, “Network Control Method” and Japanese Patent Laid-Open No. 3-1453.
Japanese Patent No. 54, “Network Control Method” has already been filed.

In these techniques, the initial state of the switch box is set in advance, and the switch is switched according to the destination of the next message according to the routing information included in the tail portion of the message. It switches the state of the box.

For example, as shown in FIG. 10 (a), a message including setting information for setting the switch box in the cross state is input to the input terminal 1 of the switch box in which the straight state is set in advance. When passing through the switch box, the state of the switch box is partially switched (see FIG. 10 (b)). After that, when a message including setting information for setting the switch box to the cross state passes through the input terminal 2, switching of the connection state of the switch box is completed, and the cross state is set as shown in FIG. 10 (c). Becomes

By making the input terminal selectable from the output terminal side in this way, it is possible to realize the waiting of the message from the input terminal 2 and the next message from the input terminal 1.

As described above, the butterfly barrier synchronization is for sequentially transmitting the messages of each phase, and therefore, Japanese Patent Laid-Open Nos. 3-91337 and 3-1.
It is considered that butterfly barrier synchronization can be realized with simple software by applying the technique of Japanese Patent No. 45354.

An object of the present invention is to provide a multiprocessor system capable of realizing high-speed barrier synchronization by using a general-purpose multistage connection network.

[0025]

According to the invention of claim 1, the N processing means 110 are connected to each other via a multistage connection network 120 of logN stages, and are included at the end of a message transmitted by the processing means 110. A multiprocessor having a configuration in which each of the N processing units 110 communicates with all the processing units 110 by switching the connection state of the switch box 121 on the path through which the message has passed in the multistage coupling network 120 according to the control information. At each processing means 110
However, prior to the transmission of the message notifying that the barrier has been reached, the initial state setting means 111 for setting the connection state of the switch boxes 121 of the respective stages of the multistage coupling network 120 in accordance with the first destination of the message. , When it reaches the barrier, it creates logN messages notifying that it has reached the barrier, and at the end of these messages,
Message processing means 112 for adding control information according to the next notification destination and sending it to the multistage coupling network 120, and all processing means 110 when logN messages are received via the multistage coupling network 120. Is configured to include a determining unit 113 that determines that has reached the barrier.

[0026]

According to the present invention, each processing means 110 is connected by the multi-stage connection network disclosed in Japanese Patent Laid-Open Nos. 3-91337 and 3-145354, and each processing means 110 is connected.
When the connection state of each switch box 121 of the multi-stage connection network 120 is set in advance by the initial state setting means 111, and when each processing means 110 reaches the barrier, the corresponding message sending means 112 outputs logN messages. Are sequentially transmitted, and when logN messages are received, the determination unit 113 determines that all the processing units 110 have reached the barrier.

Here, each switch box 121 of the multistage connection network 120 has only a route connected to the input terminal and the output terminal on the route of the message according to the control information included at the end of the message passing through itself. , It is switched according to the next message. Therefore, only when two messages of the same phase are input via both input terminals, the connection state of the switch box 121 is completely switched and the passage of the message of the next phase is permitted.

In this way, the messages of each phase can be waited for, so that the judging means 113
It is possible to determine whether all the processing means 110 have reached the barrier based only on the number of messages received.

[0029]

Embodiments of the present invention will now be described in detail with reference to the drawings. FIG. 2 is a block diagram of an embodiment of the multiprocessor system of the present invention.

In FIG. 2, the multiprocessor system includes four processors 210 corresponding to the processing means 110.
_{0 to} 210 ₃ are connected via a binary n-cube type multistage connection network using 2 × 2 stages (4 in total) of switch boxes 221 ₁₁ , 221 ₁₂ , 221 ₂₁ , 221 ₂₂ . .

In FIG. 2, the processors 210 ₀ , 21
0 ₁ is connected to the two input terminals of the switch box 221 ₁₁ of the first stage, and
0 ₂ and 210 ₃ are connected to the two input terminals of the switch box 221 ₁₂ . The two output terminals of the switch box 221 ₂₁ of the second stage are connected to the processors 210 ₀ and 210 ₂ , respectively, and the output terminals of the switch box 221 ₂₂ are the processors 210 ₁ and 21 ₁ .
0 ₃ is connected.

Hereinafter, the processors 210 _{0 to} 210 ₃ and the switch boxes 221 ₁₁ , 221 ₁₂ , 221, ₂₁ and 2 will be described.
21 ₂₂ are collectively referred to as processors 210,
It is called a switch box 221.

The processor 210 includes a process processing unit 211 and a communication processing unit 2 which process assigned processes.
12 and the communication buffer 213, the communication processing unit 212 responds to an instruction from the process processing unit 211.
It is configured to process normal communication with other processors via the multistage connection network. In addition, at this time, the message exchanged with the other processor is stored in the communication buffer 213.

Further, in the processor 210, the barrier synchronization control unit 214 responds to the notification from the process processing unit 211 that the barrier has been reached, and the message creation unit 21.
5 is started, and then the communication buffer 213 is referenced via the communication processing unit 212 to determine whether or not another processor has reached the barrier based on the number of received messages, and the process processing unit 211 It is configured to notify.

In response to an instruction from the barrier synchronization control unit 214, the above-mentioned message creating unit 215 adds at least one setting information held in the setting information holding unit 216 to the end of each message, and sequentially performs communication processing. Part 21
It is configured to be sent to the multi-stage connection network via 2.

As shown in FIG. 3, the switch box 221 includes two input buffers corresponding to the respective input terminals, two output buffers corresponding to the respective output terminals, and an input buffer and an output buffer. It is composed of a router that sets a route connecting between the two.

This router comprises two distributors corresponding to the respective input buffers and two aggregators corresponding to the respective output buffers, and two output terminals respectively provided for the two distributors. Are respectively connected to one of the two input terminals provided in each of the two aggregators.

The distributor and the aggregator described above select the output terminal and the input terminal respectively according to the setting information at the end of the message passing through the distributor and the aggregator, thereby selecting the selected output terminal and the input buffer. The connection is made, the selected input terminal is connected to the output buffer, and the route for transmitting the next message is preset.

In FIG. 3, thick lines are drawn between the output terminal selected by the distributor and the input buffer and between the input terminal selected by the aggregator and the output buffer, respectively. In this case, since the switch box is set in the straight state, the message input to each input terminal of the switch box is transmitted from the corresponding output terminal to the switch box in the subsequent stage.

The detailed structure and operation of the switch box are described in JP-A-3-91337 and JP-A-3-91337.
See Japanese Patent No. 145354. Here, in the multiprocessor system shown in FIG. 2, after the switch boxes 221 of the first stage are set to the cross state and the switch boxes 221 of the second stage are set to the straight state, and the adjacent processors 210 exchange messages, Straighten the first-stage switch box 221
Set the switch box 221 of the second stage to the cross state,
Barrier synchronization can be realized by exchanging messages between corresponding processors 221 of a pair of adjacent processors.

Therefore, the setting information holding unit 216 stores
First setting information that sets the first-stage switch box 221 to the cross state and the second-stage switch box 221 to the straight state, and sets the first-stage switch box 221 to the straight state and the second-stage switch The second setting information for setting the box 221 in the cross state may be held.

When performing barrier synchronization for the first time, the message creating section 215 first creates a message for initialization, and then creates two messages for notifying arrival of the barrier.

The initialization message may be formed from the header indicating that the switch box 221 is initially set and the above-mentioned first setting information. Further, the message of phase 0 notifying the arrival of the barrier may be formed by adding the above-mentioned second setting information to the end, and the message of phase 1 may be formed by adding the first setting information to the end. .

Here, in practice, the contents of the message notifying the arrival of the barrier are unnecessary, so that the above two messages are sufficient for the setting information only. Further, by adding the first setting information to the phase 1 message, all the switch boxes 221 have already been set according to the first setting information when barrier synchronization is performed next time. It is not necessary to send a message for Therefore, in this case, the message creating unit 215 only needs to create two messages that notify the arrival of the barrier.

As described above, in response to the instruction from the barrier synchronization control unit 214, the message creating unit 215 creates a message using the information in the setting information holding unit 216, so that the initial state setting unit 111 and the message are transmitted. The function of the means 112 can be realized.

It should be noted that the switch box 221 may recognize the header indicating the above-mentioned initial setting and pass the message straight. Below, the switch box 2 when transmitting the message notifying the arrival of the barrier
21 will be described.

FIG. 4 is a diagram for explaining how the connection state of the switch boxes at each stage changes. In FIG.
The symbols M _i0 and M _i1 are the processors 210 _i (i = 0 to
3 shows the phase 0 and phase 1 messages sent by 3). Also, four switch boxes 221 ₁₁
Each of ˜221 ₂₂ is shown as a rectangle, and a subscript for identification is underlined.

In FIG. 4A, the switch boxes 221 of each stage are already initialized by the above-mentioned initialization message and the like, and the processor 21
The messages of phase 0 sent by 0 ₀ , 210 ₂ and 210 ₃ pass through the switch boxes 221 of each stage,
It is transmitted to the appropriate destination.

In the process of transmitting these Phase 0 messages, the states of the switch boxes 221 at the respective stages partially change according to the setting information contained in each of them. That is, the distributor and the aggregator of the first-stage switch box 221 on the path through which each message passes are switched to the straight side, and the distributor and the aggregator of the second-stage switch box 221 are switched to the cross side.

In this case, since the processor 210 ₁ has not reached the barrier yet, the distributor and the aggregator on the message path of the processor 210 ₁ cannot be switched. For this reason, as shown in FIG. 4B, the switch boxes 221 ₁₁ and 221 ₂₁ are in a partially switched state.

Therefore, the message M ₀₁ of the phase 1 sent by the processor 210 ₀ is the switch box 2
It will stay on the input side of 21 ₁₁ (see Fig. 4 (b)).
On the other hand, as shown in FIG. 4 (b), the switch box 22
Since the switching of 1 ₁₂ has been completed, the processor 210
₂ and the message M ₂₁ and M ₃₁ of the phase 1 sent by the processor 210 ₃ respectively pass through the paths set by the switch box 221 ₁₂ and reach the switch box 221 of the second stage.

In FIG. 4B, the switch box 2
Since the switching of 21 ₂₂ is also completed, the message M ₃₁
Are further sent to the processor 210 ₁ via the switch box 2212 ₂₂ . On the other hand, the switch box 22
Since the switching of 1 ₂₁ is not completed, the message M
₂₁ is retained in the input buffer of switch box 221 ₂₁ .

The state of the switch box 221 on the route of these messages is switched by the setting information contained in the above-mentioned messages M ₂₁ and M ₃₁ , and the switch boxes 221 ₁₂ are crossed as shown in FIG. 4 (c). To the state
The switch box 221 ₂₂ is partially switched to the straight state.

When the processor 210 ₁ reaches the barrier at this stage, the message M _{10 of} phase 0 passes through the switch box 221 ₁₁ in the cross direction and then passes straight through the switch box 221 ₂₁ in the processor 210 1.
Dispatched _1, in the process, and switching between the two switch box 221 _11, 221 ₂₁ described above is completed, the respective straight state and the cross state (see FIG. 4 (d)).

[0055] Thus, the message M ₀₁ and the message M ₂₁ which had been fastened into the input buffer of the switch box 221 ₁₁ and the switch box 221 ₂₁ becomes passable, via the path set by the switch box 221 _11, 221 ₂₁ , Are sent to their respective destinations.
Also, the message M of the phase 1 of the processor 210 _0
01 is sent to the processor 210 ₃ via the route set by the switch boxes 221 ₁₁ and 221 ₂₂ .

In the process of transmitting these messages,
The distributor and the aggregator of the switch box 221 on each path are switched according to the setting information (first setting information described above) of each message. As a result, the initial state is set in the switch boxes 221 at each stage, as shown in FIG. 4 (e).

As described above, by applying the techniques of Japanese Patent Laid-Open Nos. 3-91337 and 3-145354, as shown in FIGS. 4 (c) and 4 (d),
It is possible to realize the waiting of the phase 0 message and the phase 1 message. That is, the phase 0 message and the phase 1 message can be reliably transmitted to each processor 210 in that order.

In this case, it is not necessary to determine the message phase. Therefore, the barrier synchronization control unit 214 of each processor 210 may realize the function of the determination unit 113, and determine whether or not another processor has reached the barrier, based on the number of messages that have reached the communication buffer 213. .

Here, the barrier synchronization control unit 214, when two messages arrive in the communication buffer 213,
Judging that all the processors 210 have reached the barrier,
Since it is sufficient to notify the process processing unit 211, the barrier synchronization control unit 214 can be realized with simple software.

Similarly, the message creating section 215 uses the first
The configuration is such that a phase 0 message including the setting information of 1 and a phase 1 message including the second setting information are sequentially created and sent to the multi-stage coupling network via the communication processing unit 212. Can be realized with.

Thus, by simplifying the software, it becomes possible to realize barrier synchronization at high speed by using a general-purpose multi-stage connection network, and to provide a high-performance multiprocessor system at low cost. You can

In the case of a multiprocessor system in which N processors are connected by a logN-stage binary n-cube type connection network, the switchbox of the first stage is set to the cross state and the switchboxes of the other stages are set as initial states. Is set straight.

Corresponding to the phase number i (i = 0 to n-1), the switch box of the ((i + 1) mod _n ) +1) th stage is set to the cross state and the switch boxes of the other stages are set to the straight state. The setting information holding unit 216 holds the setting information to be set, and the message creating unit 215 may add the setting information corresponding to the phase number i to each of the messages from phase 0 to phase n-1.

In this case as well, each processor sends logN messages when it reaches the barrier, and then confirms the reception of logN messages.
Barrier synchronization can be realized among N processors.

It is also possible to apply the present invention to a multiprocessor system connected through another type of multistage connection network such as an Omega network, and realize barrier synchronization by waiting for messages in each phase. Is.

This is because it has been shown that these multistage connected networks can be treated as a generalized-cube network in a unified manner (HJ Siegel: Interconnection Networks for Large).
-Scale Parallel Processing (1985), DCHeath and Com
pany, Massachusetts.).

[0067]

As described above, according to the present invention, it is possible to realize the waiting of the message of each phase indicating the arrival of the barrier. Therefore, by operating the existing multistage interconnection network with simple software, high speed operation can be achieved. It is possible to realize various barrier synchronizations. As a result, a high-performance multiprocessor system can be provided at a low price.

[Brief description of drawings]

FIG. 1 is a principle block diagram of the present invention.

FIG. 2 is a configuration diagram of an embodiment of a multiprocessor system of the present invention.

FIG. 3 is a detailed configuration diagram of a switch box.

FIG. 4 is a diagram illustrating a change in a connection state of a switch box.

FIG. 5 is an explanatory diagram of a message exchange procedure in the butterfly barrier synchronization method.

FIG. 6 is a diagram showing an example of a gate circuit that realizes butterfly barrier synchronization.

FIG. 7 is an explanatory diagram of a binary n-cube type multi-stage connection network.

FIG. 8 is a diagram illustrating an example of software that realizes butterfly barrier synchronization.

FIG. 9 is a diagram showing a case where the barrier arrival times of the respective processors vary.

FIG. 10 is a diagram illustrating message waiting.

[Explanation of symbols]

 110 Processing Means 111 Initial State Setting Means 112 Message Sending Means 113 Determining Means 120 Multistage Connection Networks 121,221 Switch Boxes 210 Processors 211 Process Processing Units 212 Communication Processing Units 213 Communication Buffers 214 Barrier Synchronization Control Units 215 Message Creation Units 216 Holding Setting Information Department

Claims (1)

[Claims] 1. N processing means (110) are connected to each other via a multistage connection network (120) of logN stages, and the processing means (110) is responsive to control information included at the end of a message transmitted by the processing means (110). The switch box (1) on the path through which the message has passed in the multi-stage connection network (120).
By switching the connection state of (21), each of the N processing means (110) has all the processing means (11).
0), the processing means (110) transmits the message notifying that the barrier has been reached, prior to sending the message to notify that the barrier has been reached, in accordance with the first destination of the message, 120) switch box (12)
Initial state setting means (111) for setting the connection state of 1)
Then, when it reaches the barrier, it creates logN messages that notify that the barrier has been reached, and adds the control information according to the next notification destination to the end of these messages to add the multistage message. When the logN number of messages are received through the message sending means (112) for sending to the connection network (120) and the multistage connection network (120), all the processing means (110) reach the barrier. A multiprocessor for performing barrier synchronization, which is configured to include a determination unit (113) for determining.