JP3653841B2 - Problem area division / allocation method - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a parallel computer that transfers data between a plurality of processors via a network.
[0002]
[Prior art]
With the development of parallel computers in which multiple processors are connected via a network, numerical simulations that analyze natural phenomena are being put into practical use. One of the basic principles governing natural phenomena (physical phenomena) is proximity action. The proximity action problem is calculated using only the values of adjacent grid points in the numerical solution. In a parallel computer, when a physical space (problem area) is divided and each divided data area is assigned to a processor, this means that data transfer occurs only between adjacent processors.
[0003]
For example, if a processor arranged in a two-dimensional grid is represented by coordinates PE [X, Y], PE [X, Y] is represented by PE [X + 1, Y], PE [X-1, Y], The calculation proceeds using the data stored in PE [X, Y + 1] and PE [X, Y-1]. As a network most suitable for this adjacent transfer, there is a lattice coupling and a torus coupling network in which the ends of the lattice are connected. Lattice torus coupling is the simplest network for high-speed processing of adjacent transfers, so the diameter of the network (distance between the furthest processors) is large, and transfer patterns that are not adjacent transfer cause contention of transfer paths. Occurs and performance decreases.
[0004]
On the other hand, a hypercube network and an N-dimensional crossbar network have been proposed for the purpose of reducing the diameter of the network and achieving performance even in transfer patterns other than adjacent transfer.
[0005]
The hypercube network decomposes 2 m processors into 2 × 2 × 2 × …… × 2 and m factors, and each of these factors is on an m-dimensional lattice space with the number of lattice points on one side. The data transfer path is configured by arranging the processors and connecting them directly.
[0006]
As disclosed in JP-A-1-267763, the N-dimensional crossbar network factors n processors into n = n ₁ × n ₂ × n ₃ × …… × n _m, and these factors Processors are arranged in an m-dimensional lattice space with each of the number of lattice points on one side, and each side is connected by a partial network composed of crossbar switches to form a data transfer path.
[0007]
Since both the hypercube network and the N-dimensional crossbar network are networks that include lattice torus coupling, adjacent transfers can transfer data with the highest performance without path contention. In addition, since there are more paths than lattice torus coupling, there is less competition for transfer paths than lattice torus coupling even in transfer patterns other than adjacent transfer.
[0008]
Conventionally, parallel application users who handle the proximity action problem are conscious of the number and configuration of parallel computers in order to speed up communication between processors, so that the highest performance can be obtained in data transfer (proximity action = adjacent transfer). The problem area has been divided and assigned to each processor.
[0009]
FIG. 9 shows a conventional division / allocation method. 9-2 is a parallel computer, and 9-1 is a target problem area. The parallel computer 9-2 has a two-dimensional configuration, and each processor has a processor number of two-dimensional coordinates. Conventionally, as shown in FIG. 9, the user divides the target problem area 9-1 into the same dimensional configuration as the parallel computer 9-2 and assigns the divided areas to the corresponding processors as they are. If the parallel computer has a two-dimensional configuration of l × m, the problem area is divided into two dimensions of l × m and assigned to each processor. When the parallel computer has a three-dimensional configuration having l × m × n processors, the problem area is divided into three dimensions of l × m × n, and the divided data areas are assigned to the corresponding processors as they are. As described above, the problem area is divided in consideration of the number and configuration of the parallel computers, the divided data areas are allocated to the processors, and the proximity action is made to correspond to the adjacent transfer as it is.
[0010]
[Problems to be solved by the invention]
In the conventional dividing method and assigning method, the problem area in the physical space is divided so as to have the same dimensional configuration as that of the parallel computer, and assigned to the processor. For this reason, even if the network of parallel computers to be used has more transfer paths than the lattice torus connection, only the paths used for adjacent transfer are used.
[0011]
On the other hand, an actual physical space can have various dimensions such as one dimension, two dimensions, three dimensions, four dimensions, and so on. In general, the dimensional configuration of a parallel computer cannot be changed dynamically. Therefore, if the dimensional configuration of the problem area is different from the dimensional configuration of the parallel computer, not only will the user's labor increase, but data transfer other than adjacent transfer will occur depending on the region division method and divided data region allocation method, As a result, path contention occurs and communication performance deteriorates.
[0012]
The object of the present invention is to efficiently use a network including lattice torus coupling, and let the user image the dimensional configuration of the parallel computer as if it is the same as the dimensional configuration of the target proximity action problem region. Even if data transfer is performed in the proximity effect problem with the image as it is, the problem area division method that can obtain the same communication performance as when adjacent transfer is performed without causing path contention and the area to each processor It is to provide an allocation method and a library provided with the allocation method.
[0013]
[Means for Solving the Problems]
In order to achieve the above object, a parallel computer having a network including lattice torus coupling and capable of expressing the number of processors N by the nth power of a prime number x (≧ 2),
(1) within a range that does not exceed the n determines the number of dimensions m problem areas means (2) each dimension of the lattice points of the physical space n _1, n _2, n _3, ......, when n _m, a,
[0014]
[Equation 3]
log _x N ≧ log _x (n ₁ × n ₂ × n ₃ × …… × n _m ) (Formula 1)
n ₁ , n ₂ , n ₃ ,..., n _m = x (≧ 2) power of region division method candidate satisfying power (3) means for determining a region division method to be used from candidates (4 ) It is provided with means for allocating a divided area to a processor having the same physical number as the one-dimensionally displayed divided area number. By these means, the dimensions of the proximity action problem area can be freely divided without matching the dimension configuration of the parallel computer, and even if data is transferred between the divided areas, high-speed data can be transferred without competing for transfer paths in the network. Transfer can be realized.
[0015]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, a problem area division / allocation method according to the present invention will be described with reference to the drawings.
[0016]
The present invention has a network (N-dimensional crossbar network, hypercube network, complete crossbar connection, multistage connection, etc.) including a lattice torus connection, and a parallel computer in which the number of processors N can be expressed by the nth power of a prime number x (≧ 2) Applicable to. This parallel computer network has a full duplex path, and the routing method is based on the premise that fixed routing is used. The processor has physical numbers from 1 to N.
[0017]
FIG. 1 shows the overall configuration of a computer library provided with the problem area division / allocation method of the present invention. In the figure, 1-1 is a problem area dimension determining means, 1-2 is an area dividing method candidate selecting means, 1-3 is a dividing method determining means, and 1-4 is a divided area assigning means.
[0018]
The problem area dimension determining unit 1-1 determines the number of dimensions of the problem area in the physical space. In the next area division method candidate selection means 1-2, the problem area division method candidates are raised from the number of dimensions of the problem area and the number of processors. The division method determining means 1-3 selects one division method from the candidates and divides the problem area. The divided area assigning means 1-4 assigns the divided area to the processor.
[0019]
FIG. 2 shows the processing contents of each means. When the number N of processors to which a problem area should be assigned can be expressed by a prime number x (≧ 2) raised to the nth power (2-1), the problem area dimension determination means 1-1 receives the dimension number m of the problem area in the physical space as an input. (2-2). In the determination, the number of dimensions m should not exceed n (2-3). If the dimension number m exceeds n, re-input is repeated until the condition is satisfied.
[0020]
Then, the region division method candidates selecting unit 1-2, each dimension of the lattice points of problem areas _{n 1, n 2, n 3} , ......, when n _m, a,
[0021]
[Expression 4]
log _x N ≧ log _x (n ₁ × n ₂ × n ₃ × …… × n _m ) (Formula 1)
_{n 1, n 2, n 3} , ......, n m = n 1 satisfying exponentiation of _{x (≧ 2), n 2} , n 3, ......, finding a combination of n _m (2-4).
[0022]
The dividing method determining means 1-3 selects the most appropriate combination from the combinations obtained by the area dividing method candidate selecting means 1-2 (2-5) and sets it as the problem dividing method. Then, the problem area is divided according to the dividing method (2-6).
[0023]
Finally, the divided area assigning means 1-4 assigns divided areas to the processors having the same physical numbers as the divided area numbers displayed one-dimensionally (2-7).
[0024]
Dividing the problem areas in the three-dimensional FIG. 3 shows an example of assigning the divided regions into two ^nine processors.
[0025]
When dividing into three dimensions, m = 3 is set (3-2). Since the number of processors N is 2 ^9, a number of dimensions m area m = 1 to 9 to nine selectable (3-3). In order to determine a division method candidate, a combination of (n ₁ , n ₂ , n ₃ ) is obtained (3-4). The combinations are as follows: (2 ⁷ , 2 ¹ , 2 ¹ ) (2 ⁶ , 2 ¹ , 2 ² ) (2 ³ , 2 ³ , 2 ³ ) (2 ² , 2 ³ , 2 ⁴ ). In the above example, when the problem area is handled as a cube, the combination of (8, 8, 8) is selected (3-5) and divided into 2 ³ × 2 ³ × 2 ³ (3-6). Finally, the divided area (Num = X + 8 × (Y−1) + 64 × (Z−1): 1 ≦ X ≦ 8, 1 ≦ Y ≦ 8, 1 ≦ Z ≦ 8) is allocated to the processor (Num) (3 -7).
[0026]
As described above, by using the four means, even when the dimensional configuration of the problem area is different from the dimensional configuration of the parallel computer, it is possible to obtain communication performance equivalent to that when performing adjacent transfer without causing path contention. Further, since the divided areas may be simply assigned to processors having the same number, the user does not need to be aware that the dimensional configuration of the problem area is different from that of the parallel computer. In this embodiment, these means are provided as a library. However, when the user himself / herself performs programming, the problem area may be divided according to this procedure, and the divided area may be allocated to the processor.
[0027]
Next, a specific application example of the present invention to a two-dimensional crossbar network will be described. Consider a case where a problem area is divided into three dimensions and the divided areas are allocated to a parallel computer composed of 64 (8 × 8) processors having a two-dimensional crossbar network.
[0028]
FIG. 4 shows the configuration of the parallel computer used in this embodiment. In FIG. 4, reference numerals 4-1 to 4-64 denote processors (hereinafter abbreviated as PE). 4-65 to 4-72 are X-direction crossbar switches (hereinafter abbreviated as X-XB), and 4-73 to 4-80 are Y-direction crossbar switches (hereinafter abbreviated as Y-XB). . When these crossbar switches are not distinguished, they may be simply referred to as XB. 4-81 to 4-144 are relay switches (hereinafter abbreviated as EX) provided at the intersections of the respective X-XBs and the respective Y-XBs. Each XB and EX is a full crossbar switch with each input port directly coupled to all output ports. A combination of XB and EX is collectively called a two-dimensional crossbar network.
[0029]
Each PE is given in advance as its PE number the X and Y coordinates of one lattice point in the two-dimensional coordinate space and the physical number obtained from the coordinates. For example, in this example, each PE has a value of [X, Y], X + 8 × (Y−1) as a number. The routing method uses fixed routing. First, data is transferred in the X direction, and then transferred in the Y direction.
[0030]
First, the number of dimensions of the problem area is determined by the problem area dimension determination means 1-1 in FIG. In this embodiment, since the PE number 64 can be expressed as ²⁶ , the number of dimensions of the problem area may be any as long as it is 6 dimensions or less. Here, the number of dimensions of the problem area is set to three dimensions, and this is used as an input.
[0031]
Next, candidate division methods satisfying the conditions are selected by the area division method candidate selection unit 1-2 in FIG. 1, and the division method is determined by the division method determination unit 1-3. Problem region dividing method satisfying log _x 2 ⁶ ≥log _x (n ₁ × n ₂ × n ₃ ), where n ₁ , n ₂ , n ₃ (power of 2) is the number of grid points in each dimension of the problem region There are a total of 10 types even when the number of divided areas is equal to the number of processors, and X dimension × Y dimension × Z dimension is 16 × 2 × 2, 2 × 16 × 2, 2 × 2 × 16, 8 × 4 × 2, respectively. Divide into 8 × 2 × 4, 4 × 8 × 2, 4 × 2 × 8, 2 × 8 × 4, 2 × 4 × 8, and 4 × 4 × 4. Since any division method can be freely selected, a method for dividing the problem area into 16 × 2 × 2 is selected from a plurality of candidates.
[0032]
FIG. 5 shows how the problem area is divided. Since this problem is three-dimensional, three of the X coordinate, Y coordinate, and Z coordinate are substituted into X + 16 × (Y−1) + 32 × (Z−1) and displayed one-dimensionally. A one-dimensional number is assigned as shown in 5-1.
[0033]
Finally, the problem area shown in FIG. 5 is assigned to the processors having the same numbers in FIG. 4 by the divided area assigning means 1-4 shown in FIG. For example, problem area [1] is assigned to PE [1] and problem area [16] is assigned to PE [16].
[0034]
FIG. 6, FIG. 7 and FIG. 8 show the state of data transfer of the proximity effect problem by the above-described division allocation method. The user performs data transfer while keeping the image that the dimensional configuration of the parallel computer is the same as the dimensional configuration of the problem area. Since the problem area has a three-dimensional configuration, communication occurs in a total of six directions.
[0035]
FIG. 6 shows data transfer patterns in three directions in the problem area divided into 16 × 2 × 2. 6-1 is a proximity action in the + X direction, 6-2 is a proximity action in the + Y direction, and 6-3 is a proximity action in the + Z direction. The end is adjacent to the opposite end.
[0036]
7 and 8 show the state of data transfer when this problem area is assigned to a processor using the means of the present invention. FIG. 7 shows the state of data transfer in the case of the proximity action in the + X direction, and FIG. 8 shows the state of data transfer in the case of the proximity action in the + Y direction. As can be seen from these two figures, by using the above-described division / allocation method, it is possible to efficiently transfer data using a transfer path used other than adjacent transfer in a two-dimensional crossbar switch. Become.
[0037]
Here, an example in which the problem area is divided into 16 × 2 × 2 and assigned to the processor has been described. However, if the candidate is obtained from the area division method candidate selection unit 1-2, a transfer path to be used other than the adjacent transfer is selected. It is possible to transfer data efficiently and at high speed.
[0038]
Also, here, an example is shown in which a three-dimensional problem area is assigned to a two-dimensional crossbar network, but high-speed data transfer is possible even if an m-dimensional problem area is assigned to an N-dimensional crossbar network in the same manner. .
[0039]
In the above description, a two-dimensional crossbar network is used. Instead of this, however, a hypercube network (10-1) or a multistage coupling network (10-2) composed of a large number of relay switches as shown in FIG. It can also be applied to a fully crossbar coupled network.
[0040]
【The invention's effect】
According to the present invention, even when the dimensional configuration of the problem area is different from the dimensional configuration of the parallel computer, it is possible to obtain the same communication performance as when the dimensional configuration is the same.
[Brief description of the drawings]
FIG. 1 is a block diagram of a problem area division / allocation method of the present invention.
FIG. 2 is a flowchart of processing of a problem area division / allocation method according to the present invention.
FIG. 3 is a specific flowchart of the present invention.
FIG. 4 is a block diagram of a two-dimensional crossbar network to which the present invention is applied.
FIG. 5 is an explanatory diagram of region division according to the present invention.
FIG. 6 is an explanatory diagram of a data transfer pattern according to the present invention.
FIG. 7 is a block diagram of data in the two-dimensional crossbar network of the present invention.
FIG. 8 is a block diagram of data in the two-dimensional crossbar network of the present invention.
FIG. 9 is an explanatory diagram showing a conventional problem area division / allocation method.
FIG. 10 is an explanatory diagram of a network to which the present invention is applicable.
[Explanation of symbols]
1-1: Problem area dimension determining means, 1-2: Area dividing method candidate selecting means, 1-3: Dividing method determining means, 1-4: Dividing area assigning means.

Claims (1)

A problem region division / allocation method in a parallel computer having a hypercube network or an N-dimensional crossbar network that includes a function of a lattice torus coupling network, and in which the number of processors N can be expressed by the nth power of a prime number x (≧ 2),
receiving and determining a setting input of the dimension number m of the problem area within a range not exceeding n;
When the number of grid points in each dimension of the physical space is n ₁ , n ₂ , n ₃ ,..., N _m ,
log _x N ≧ log _x (n ₁ × n ₂ × n ₃ × …… × n _m )
n ₁ , n ₂ , n ₃ ,..., n _m = power of x (≧ 2) (Equation 1)
Selecting a region segmentation method candidate that satisfies
Determining a region dividing method to be used from among the candidates;
A problem area dividing / allocating method comprising: assigning a divided area to a processor having the same physical number as the one-dimensionally displayed divided area number.

Images