JPH03186963A - Connection method for computer - Google Patents

Abstract

PURPOSE:To hold the number of links per processing element PE and to reduce a maximum inter-PE distance by adding a bypass link to a hypercube connection composed of plural (PEs) to constitute one PE aggregate, providing plural PE aggregates, completely connecting them and constituting a parallel PE connec tion network. CONSTITUTION:Plural PE are connected in a hypercube form by the links 2 and plural PE aggregates 1 are arranged with PE groups in which the links 2 are added to PE having the maximum inter-PE distance as one PE aggregate 1. Then, respective PE aggregates 1 are completely connected so as to constitute a parallel computer. When the number of PE in hypercube connection in which the maximum inter-PE distance D comes to be a base is set to be M, it does not depend on the number of all PE but it comes to be D=1+log2M (D=2+log2 M when log2M is odd). The number L of the links 2 required for one PE comes to be L=2+log2M. Thus, the maximum inter-PE distance can be set small compared to the maximum inter-PE distance and the number of the links in simple hypercube connection.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention relates to a so-called message passing type parallel computer connection network in which a plurality of processing elements (hereinafter referred to as PEs) are interconnected by links. In particular, the present invention relates to a computer connection method suitable for keeping the number of connections (number of links) between PEs small and increasing performance.

[Conventional technology]

Conventionally, parallel computer connection networks in which PEs are interconnected by pairs of links include tree connections in which PEs are connected in a binary line, two-dimensional array connections in which PEs are connected in a two-dimensional grid, and PEs in a two-dimensional array. There is a so-called hypercube combination in which all PEs whose focus patterns differ by one bit when expressed in binary are combined.

In such a connected network, communication with PEs that are not connected by direct links is performed by relaying through several PEs, so it is required that the number of relays be small.

It is also required that the coupling be symmetrical and that communications not be concentrated on any particular link. Due to these demands, hypercube coupling has recently attracted attention, and several machines have been put into practical use. FIG. 4 shows a hypercube connection when the number of PEs is 8.

[Problem to be solved by the invention]

In hypercube join, when the number of PEs is N, each P
E is connected to log2N PEs by direct links, and
Maximum I) E which is the maximum number of relays in communication between Pus
The open circuit HD (also called diameter) is og2N. In this way, hypercube coupling has the feature that the maximum distance between PEs can be reduced with a relatively small number of links (log2N links per PE).

However, in a highly parallel computer where the number N of PEs is, for example, 103 to 104 or more, both the number of links per PE and the maximum distance between PEs cannot be said to be small. That is, there are problems in that the increase in the number of links makes it difficult to process connections between PEs on implementation, and the increase in the maximum distance between PEs causes communication delays that limit the performance of the entire system.

In contrast, K, Hwang, etc.
Let us propose a combination configuration called tK, Hwang,
et al.: “Hypernet: A
Communication-Effjcient A
rchj, texture for construct
tingMassively Parallel Co
mputers”, I E E E Trans,
Compute.

Vol, C-36, N [112, PP, 1450-14
663 (upper 987)), also F, P, Prepara
ta et al. have proposed a coupling configuration called CCC (
F.

P, Praparata+ at al-,: “
'I'he Cube-Connected Cycle
es: A Versatile Network
for Parallel Computations
, Commun, ACM, pp.

300-309 (1981)), both of which reduce the number of links but cannot reduce the maximum distance between PEs.

In this way, with conventional technology, it is generally difficult to simultaneously reduce the number of links and the maximum distance between PEs, and even if these are relatively small hypercube connections, if the number of PEs is large, it cannot be said that these are sufficiently small. There were two problems: system implementation and system performance.

An object of the present invention is to provide a method for connecting PEs in a parallel computer that can achieve a smaller maximum distance between PEs with a smaller number of links.

[Means to solve the problem]

In order to achieve the above objective, the present invention uses a plurality of PEs.
A group of PEs in which the PEs are connected in a hypercube shape by links and links are added to the PEs having the maximum inter-PE distance is defined as a PE aggregate.
A parallel computer is constructed by arranging a plurality of E aggregates and completely coupling the PE aggregates to each other.

[For production]

In such a parallel computer connection network, the maximum distance between PEs is 111
1D does not depend on the total number of PEs N, and D = 1 +
log, M (when log2M is an odd number, D=2+
log2M). Also, the number of links required per PE is L = 2 + log2M. In other words, the value can be made much smaller than the maximum inter-PE distance and the number of links of a conventional simple hypercube connection.

〔Example〕

An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 shows a schematic configuration of an embodiment of a parallel computer coupling network according to the present invention. In FIG. 1, 1 is a PE aggregate, and 2 is a link for coupling between PE aggregates. In the embodiment, it is assumed that one PE aggregate is composed of eight PEs. FIG. 1 shows such a PE aggregate 1
A parallel computer connection network is constructed by arranging nine PE aggregates and completely connecting them with each other through PE aggregate connection links 2. Therefore, the parallel computer network consists of a total of 72 PEs.

FIG. 2 is a detailed configuration diagram of one PE aggregate 1 in FIG. It has a configuration with the addition of the use of the King King 3.

In Figure 2, (OOO) to (111) are 8 PEs.
Bypass link number 1 is shown in binary format.
3 is (000) and (111), (001) and (110)
, (010) and (101), and (olz) and (100). In other words, when the number of a certain PE is expressed in binary (ao+alr a2+...an-1
), this PE is (a 01 a 11 a 2
It is coupled to the PE numbered 1"'a n-0) by a bypass link.

FIG. 3 shows a schematic configuration of one PE, including a CPU 6-1], a memory 112, and a plurality of input/outputs (Il
o) Consists of ports 1-3. In this example, five input/output ports 113 are required.

As shown in Figure 2, when a bypass link is added to the hypercube of the base PE aggregate, the number of links for each PE increases by one, but the maximum distance between PEs of that hypercube is halved. Generally, if the number of PEs in a hypercube is M, then (], og2M ) / 2
becomes (], when og2M is an odd number, (1+log
2M) / 2). This is because if the distance between the communication source PE and communication destination PE (equal to the number of different bits when they are expressed in binary) is less than or equal to (LogzM)/2, the communication is relayed sequentially using hypercube links. In other cases, the bypass link can be used to relay to the farthest PE, and then the hypercube links can be used for relaying in sequence.

For example, in a hypercube consisting of 16 PEs (00
When communicating from the PE of (00) to the PE of (01-1,1), one PE of (OOOO) bypass ring → (1
Engineering 11) PE->Hypercube link->(01
41) PE, and the maximum distance between PEs is (1, ogz6)/2=2. In the case of FIG. 2, since M=8 and LogzM is an odd number, the maximum distance between PEs in the PE aggregate is 2. That is, in the present invention, each PE has a distance Ml from any PE within the PE aggregate.
(1,ogzM) / 2 (or (1+log2M)
/ 2) can communicate, reducing the maximum distance between E to 1/2 of the hypercube based on it.

A plurality of PE aggregates configured as described above are arranged, and the first
As shown in the figure, when each PE aggregate is regarded as one PE, they are combined to form a complete combination. In order to achieve this complete connection, as shown in Figure 2,
Each PEt1 in the PE aggregate is provided with a link 2 for coupling between PE aggregates.

With this configuration, it is possible to reach all other PE aggregates over a distance from a certain PE aggregate. Therefore, I
? At worst, communication between E is realized by a combination of relaying within the PE aggregate to which the communication source PE belongs, relaying between PE aggregates, and relaying within the PE aggregate to which the communication destination PE belongs. That is, the maximum PE-to-PE open circuit lID of the coupling network according to the present invention is:
The distance between each PE in a PE aggregate is maximum (log, M
) / 2, so D= (LogzM)/2+1
+ (LogzM)/2=1(logzM (Logz
When M is an odd number, it becomes 2 0], og, M). For example, in the embodiment shown in FIG. 2 and FIG. 2, D=5.

Also, the number of links per PE is the number of PE links in the base hypercube, the number of bypass links, and P
E is the total number of links for connection between aggregates, L = l
og7M Juoh+↓=2+log2M. For example, in the case of the embodiment, L=5. That is, in the embodiment shown in FIGS. 1 and 2, 72 PEt-PEs are connected by five links per PE with a maximum inter-PE distance of 5. This is a small value compared to the number of links of 6 and the maximum number of open circuits between PEs of 6 in the case of a hypercube consisting of 64 PEs. (D and L in this case are still 5).

In the above embodiment, the number of PE aggregates was set so that all links for connecting PE aggregates of the base hypercube were used (number of PE aggregates = base hypercube). IJE number + 1), and generally the number of PE aggregates can be less than or greater than this (in addition, if it is more than this, it is necessary to have multiple links for connecting PE aggregates for each PE instead of one). Needless to say, however, in that case, the connections between all PEs will not be completely symmetrical.

〔Effect of the invention〕

As explained above, according to the present invention, a bypass link is added to a hypercube connection consisting of a plurality of PEs to form one PE aggregate, a plurality of PE aggregates are provided, and a complete connection is established between them. In order to configure a parallel PE connection network, the number of links per PE is kept small and the maximum
The distance between them can be reduced. This effect is more pronounced in systems with a larger number of PEs. For example, in a zero-parallel computer consisting of 4096 PEs, in the case of hypercube connection, the number of links per PE and the maximum distance between PEs are both 12, but in the present invention, the number of PEs is 64, and the maximum distance between PEs is 12. If the number of links is 64, the number of links per PE is 8, and the maximum distance between PEs is 7.
becomes.

That is, according to the present invention, there is an advantage that the maximum distance between PEs can be reduced to less than that with a smaller number of links than in a hypercube connection, and as a result, it is possible to improve the feasibility of a highly parallel computer and reduce the communication delay thereof.

[Brief explanation of drawings]

FIG. 1 is a schematic configuration diagram of an embodiment of a parallel computer coupling network according to the present invention, FIG. 2 is a detailed configuration diagram of one PE aggregate in FIG. 1, and FIG. 3 is a diagram showing an outline of one PE. , 4th
The figure is a diagram showing an example of the configuration of hypercube connections. 1... PE aggregate, 2... Link for coupling between PE aggregates, 11... PE (processing element). 12...Link for hypercube, 11-13... Link for bypass. =12=

Claims (1)

[Claims] (1) Combine multiple processing elements (hereinafter referred to as PEs) into a hypercube shape using links, and
A PE group in which links are added to PEs having a distance between them is regarded as one PE aggregate, and a plurality of PE aggregates are arranged,
Each PE aggregate is connected to form a complete connection when each PE aggregate is regarded as one PE, and links that realize the complete connection are uniformly connected to PEs in each PE aggregate. A computer combination method characterized by: