JPH02224443A - Communication system - Google Patents

Abstract

PURPOSE:To realize efficient communication between processing elements by providing an alternative counter in a communication packet, and determining successively an adjacent processing element to which the packet is sent by calculating an evaluated value by the linear coupled expression of the degree of congestion of the directly connected adjacent processing element or a communication channel and the value of the alternative counter. CONSTITUTION:The communication packet 103 is provided with a transmitted destination processing element address 104, the alternative counter 105 and transmission data 106. At the time of the transmission of the communication packet 103 from the processing element PE(0, 0) to PE(1, 3), the evaluated values of PE(1, 1) and PE(2, 0) which can be communicated from PE(1, 0) are '4' for PE(1, 1) and '2' for PE(2, 0), and the communication packet 103 is transmitted to PE(2, 0). At that time, the alternative counter 105 in the communication packet 103 becomes '2'. Thus, the communication packet 103 is transmitted from PE(0, 0) to PE(1, 3) as detouring the processing element PE(1, 1) of the higher degree of congestion.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a communication control system between processing elements in a parallel computer.

[Conventional technology]

An example of this type of technique described is, for example, Japanese Patent Application Laid-open No. 181962/1983.

In the conventional communication control method for parallel computers, as described in the above publication, a communication packet, which is a transmission unit, contains transmission data and a destination processing element address, and the processing element transmits the communication packet. When doing so, the processing element with the shortest route among the adjacent processing elements directly connected by the communication path is determined from the destination processing second address, and from then on, communication packets are sent to the processing element determined in this way. was being sent.

[Problem to be solved by the invention]

However, the above-mentioned conventional technology does not take into consideration the difference in the degree of congestion between each processing element, which depends on the amount of communication. Therefore, when communication is concentrated between specific processing elements, a phenomenon occurs in which the processing elements (or communication paths) on the communication path that is the shortest path between the processing elements become locally congested. At this time, if the shortest route between other processing elements overlaps with the congested communication route, there is a concern that the time required for communication will become extremely long, which will affect the entire system.

The present invention has been made with a focus on the above-mentioned problems, and its purpose is to avoid congestion of local communication paths even when communication is concentrated between specific processing elements, and to achieve efficient The objective is to realize communication between processing elements.

The above and other objects and novel features of the present invention will become apparent from the description of this specification and the accompanying drawings.

[Means for Solving the Problems] A brief summary of typical inventions disclosed in this application is as follows.

In other words, the communication packet contains the transmission data along with the destination processing element address and a detour counter that records how much longer the route has taken than the original shortest distance, and is directly connected from the viewpoint of the processing element where the communication packet is located. one or more adjacent processing elements)
・Alternatively, know the degree of congestion of the communication channel, and calculate the evaluation value using a linear combination formula of this degree of congestion and the value of the detour counter,
Adjacent processing elements to which communication packets are to be sent are sequentially determined based on the magnitude of this evaluation value.

[Effect]

According to the above-mentioned means, it is possible to send communication packets using the shortest route when there is no congestion on the communication route, and even when there is congestion, communication packets can be sent using a route that avoids extremely large detours. As a result, local congestion in processing elements can be prevented and efficient packet communication can be performed.

For example, when a communication packet is located in a certain processing element, the value of the detour counter (CTR+) when the communication packet is sent to the adjacent processing element (PE+) that is directly connected to it via a communication path, and
An evaluation value (VAL+) is calculated by a linear combination formula (for example, the following 0 formula) with the /ment or communication path congestion degree (BSY,), and the communication packet is sent to the adjacent processing element where this evaluation value is the smallest. It is something that is sent out.

The communication packet 103 includes a destination processing element address 104, a detour counter 105, and transmission data 106. As shown in the figure, processing element 10
1 is like PE (0,0)~PE(2,3),
Addressed by Y coordinate, communication path 107
The distance is expressed as the Manhattan distance on the XY coordinates. This allows the PE (Xl
, Yt) and PE (Xi, YJ)
I SIJ can be calculated using the following formula (■).

V A L (= (X X CT Rl +βX
B S Y, (2) where α and β are normalization coefficients.

[Embodiment 1] FIGS. 1(a) and 1(a) show an overview of a parallel computer and a communication packet according to an embodiment of the present invention.

In FIG. 1(a), 101 is a processing element;
2 is a communication path between processing elements, and 107 is a communication path for the communication packet 103. Moreover, the above D I S+4=
l Xt Such a congestion state is caused by the evaluation value (V
AL+ ) is calculated according to the following formula (■).

VAL+ = IXCTRi +2XBSYi
■In addition, in the above formula ■, CT Rs is PEI
Evaluation value when sending a communication packet to BSY
l represents the congestion degree of PE+ (the number of communication packets waiting to be processed in the reception buffer of PEl).

Figure 2 shows processing elements PE (0,0) to PE
When transmitting the communication packet 103 to (1, 3),
The state of all processing elements 101 adjacent to PE (0,0) and capable of transmitting data is shown. According to the figure, the communicable processing element 101 is P
E (0,1) and PE (1,0>, and the evaluation value (VAL+) in this state is PE (0,1)
is 2, and PE (1°0) is 0. Therefore, the communication packet 103 is transmitted to PE (
1,0) is first transmitted.

FIG. 3 shows the status of all processing elements 101 that are subsequently enabled to transmit from PE (1,0). Note that in this embodiment, retransmission is not performed to the processing element that is the source of the communication packet (here, PE (0, 0));
The processing element 101 that can communicate with PE (
1,1) and PE (2,0). The evaluation value in this state is PE (1, 1) is 4, PE
(2゜0) becomes 2, and PE with a small evaluation value (2,0
) A communication packet 103 is transmitted to. At this time, the detour counter 1゜5 in the communication packet 103 is "2".
becomes.

Similarly to FIGS. 1 to 3 above, as shown in FIGS. 4 to 7, each processing element 101 sequentially compares the evaluation value of the next processing element 101, and 1o7) is determined.

In this way, in this embodiment, the communication packet 103 is transmitted from PE (0,0) to PE (1,3), bypassing the processing element PE (1,1) with a high degree of congestion. This enables efficient communication between processing elements while avoiding congestion of communication paths.

[Embodiment 2] FIGS. 8(a) and 8(a) show an outline of a parallel computer and communication packet according to another embodiment of the present invention.

In FIG. 8(a), 201 is a processing element;
2 indicates communication paths between processing elements.

In the second embodiment, the communication packet 203 includes a destination processing element address 204, as shown in FIG.
a detour counter 205, a detour limit value register 207,
It is composed of transmission data 206.

As is clear from FIG. 8, the processing element 201 of the second embodiment has a three-dimensional array structure, and the PE
(0,O,O)~PE (2,2,2〉, xY
Addressed by Z coordinate.

Here, if we use the function SGN defined as below, SGN (1, J) = 1: I and J have the same sign, or J is 0: I and J
■Here, the destination processing element address 204 is (XL, yt,
Processing element P E (X
t, Yt, Zt) to another processing element PE (XJ, YJ, ZJ), whether or not it is the shortest path depends on whether the value of the following formula (■) is 3'' or not. It can be calculated.

SGN ((Xt
XJ ))+SGN ((Yt Yt)
, (Yt YJ ))+SGN ((Z
s Zi ), (Zt Zj ))■ In this embodiment as well, the congestion degree of the processing element 201 is expressed as the number of packets waiting to be processed in the reception buffer in the processing element 201, and is assumed to be 2.

Furthermore, each processing element 201 calculates its evaluation value using the following equation.

VAL+= I XCTRt +2 XBSYt (CT R, ≦LMT,) ■-12XCTRt
+ I XBSYt(CTR,>LMT,)
■-2 In the above equation, VAL is the evaluation value when a communication packet is sent to PEI, and CTR is the evaluation value when sending a communication packet to PEI.
, the value of the detour counter when a communication packet is sent to , BSY+ is the congestion degree of PE, that is, PEI
The number of communication packets waiting to be processed in the receive buffer, CTR,
indicates the current value of the detour counter in the communication packet, and LMT indicates the value of the detour limit value register in the communication packet.

Based on the evaluation value obtained from the above equation 0, communication packets with a large value in the detour limit value register may be detoured to avoid causing local congestion. Conversely, communication packets with a small value in the detour limit value register are transmitted so that detours are reduced.

Furthermore, it is assumed that the transmission source processing element sets the value of the detour limit value register in the communication packet according to the following equation (2).

LMT, = 3 (Xt Xt + Yt Y
t )/2■ In the above formula (■), Xr and Yr represent the source processing address, and X and Yt represent the destination processing address, respectively.

That is, according to formula (2), the farther the communication packet is from the source to the destination, the smaller the value of the detour limit value register becomes, and the communication packet is given priority.

Next, a specific example will be explained with reference to FIG.

In FIG. 8, the communication packet 203 is sent from a PE.
(2,1,2), the destination is PE (2,2°0),
PE (2,1,2) → PE (2,0,2) →PE
(1,0,2) →PE (1,1,2) →
It is assumed that the route is PE (1, 1, 1).

In PE (2, 1, 2), the detour limit value register 207 of the communication packet 203 is set to "1" according to the above-mentioned formula (■).
．． The detour counter 205 is set to "2" because detours have occurred only twice so far.

FIG. 9 shows the states of all processing elements 201 that can transmit data from processing element PE (1, 1, 1). As shown in the figure, the processing element (1, 1, 1)
The processing element 201 that can transmit more than PE
(1,0,1), PE (0,1゜1), P
E (2,1,1), PE (1,2,1) and PE
There are five (1, 1, 0). As is clear from the evaluation values in the figure, the minimum evaluation value for each processing element 21 is different between 2-1 and 2-2.

In this embodiment, in such a case, the value (CTR, ) of the detour counter 205 of the communication packet 203 is "2" and the value (LMT, ) of the detour limit value register 207 is "1.5". >LMT, ), formula ■-2 is preferentially adopted, and the communication packet 203 is PE (1,1゜0)
sent to.

Here, if the value of the detour limit value register 207 is larger than the value of the detour counter 205, that is, CTR, ≦
In the case of LMT, formula (1) is preferentially adopted, and communication packet 203 takes a detour to alleviate local congestion and is transmitted to PE (1,0°1).

As described above, according to the present embodiment, even when the processing elements 201 are arranged in a three-dimensional manner and are interconnected by the communication paths 202, as in the first embodiment, when the communication paths are not congested, Communication packets can be sent using the shortest route, and even when congestion occurs, communication packets can be sent using a route that avoids extremely large detours, which prevents local congestion in processing elements. This enables efficient packet communication.

〔Effect of the invention〕

A brief explanation of the effects obtained by typical inventions disclosed in this application is as follows.

In other words, if the communication route is not congested, communication packets can be sent using the shortest route, and even if the communication route is congested, communication packets can be sent using a route that avoids extremely large detours. , it is possible to prevent local congestion in processing elements and to perform efficient packet communication.

[Brief explanation of the drawing]

1(a) and (5) are explanatory diagrams showing an overview of the parallel computer and communication packets according to the first embodiment of the present invention, and FIG.
7 to 7 show that in the first embodiment, when a communication packet is transmitted from a processing element to an adjacent processing element,
An explanatory diagram showing the states of all adjacent processing elements that can be transmitted; FIGS. 8(a) and 0 are explanatory diagrams showing an overview of a parallel computer and communication packets according to the second embodiment of the present invention; FIG. 9 is an explanatory diagram showing the outline of a communication packet according to the second embodiment of the present invention. FIG. 3 is an explanatory diagram showing the states of all adjacent processing elements that can transmit when a communication node is transmitted from a processing element to an adjacent processing element in FIG. 101... Processing element, 102... Communication path, 1
03... Communication packet, 104... Destination processing element address, 105... Detour counter, 106...
...Transmission data, 107...Communication route, 201...
Processing element, 203... Communication packet, 204.
. . . Destination processing element address, 205 . . . Detour counter, 206 . . . Transmission data, 207 . . . Detour limit value register. Fig. 1 Fig. 2 Fig. 3 101: Processing element 102: Communication path 103: Communication packet 104: Destination processing element address 105: Detour counter 106: Transmission data Fig. 4 Fig. Fig. Fig. Fig. Fig. 3

Claims (1)

[Claims] 1. A communication system in which information is transmitted and received between processing elements connected by a communication path using a communication packet as a transmission unit, wherein the communication packet contains transmission data as well as a destination processing element address and an original address. congestion of one or more adjacent processing elements or communication paths that are directly connected from the perspective of the processing element where the communication packet is located, and a detour counter that records how much longer the route has taken than the shortest distance of A communication method characterized in that the degree of congestion is known, an evaluation value is calculated by a linear combination of this degree of congestion and the value of the detour counter, and adjacent processing elements to which communication packets are to be sent are sequentially determined based on the magnitude of this evaluation value. . 2. The communication system according to claim 1, wherein the congestion degree is determined by the number of packets waiting to be processed in a reception buffer of a target processing element.