JPH08227405A - Parallel iterative execution method - Google Patents

Abstract

(57) [Summary] [Purpose] To enable iterative processing such as LU decomposition processing to be executed in a shorter time on a parallel computer. [Structure] The K-th iteration process is a process P that cannot be parallelized.
(K) and a process Q (K) that can be parallelized, the process Q (K) uses the result of the process P (K), and
+ 1st processing P (K + 1) is Kth processing Q1 (K)
When using the results of some of the processing Qs (K), the processing Q
(K) is the same number of processes as the number P of processors Q1 (K)
To QP (K), and the processing Q1 (K) includes the processing QS (K). Process Q1 (K) and process P (K +
M) is sequentially executed by the same processor, and in parallel with this, other processes Q2 (K) to Qn (K) are executed by other P-1 processors. Thereafter, the above processing is repeated every time the processing of all the processors is completed.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention repeatedly executes the same processing on different data, such as LU decomposition processing that decomposes a coefficient matrix of N-dimensional simultaneous linear equations into a lower triangular matrix and an upper triangular matrix. The present invention relates to a method of executing repetitive processing on a parallel computer having a plurality of processors.

[0002]

2. Description of the Related Art Numerical simulation has been put to practical use in the development of various industrial products. A process often used in such a numerical simulation is a process of solving the N-dimensional simultaneous equations AX = B by the Gaussian elimination method. here,
A is a coefficient matrix with N rows and N columns, and X and B are vectors with N columns. The main part of the process of solving the above equation by the Gaussian elimination method is the LU decomposition process that decomposes the coefficient matrix A into a matrix LU that is the product of the lower triangular matrix L and the upper triangular matrix U.

Practical application of LU decomposition processing of large-scale matrices is progressing, and the multistage simultaneous expansion method is generally used especially for supercomputers. These methods are described in literatures: Murata, Oguni, Karaki, Supercomputer, Maruzen, 91-103.
Page, 1985 and literature: Blocking LU decomposition method VP2
About tuning for the 000 series, Proceedings of the 42nd Annual Conference of the Information Processing Society of Japan (the first half of 1991), Volume 1 7
1-72, JP-A-4-259064 and JP-A-6-
75988 and the like.

Particularly recently, with the progress of parallel computers,
A lot of research is being conducted to apply parallel computers to numerical simulation.

A parallel computer which has been put to practical use in recent years generally takes the following three types of forms. FIG. 1 is a main memory shared parallel computer in which a plurality of processors 2 to 4 share a main memory 1. This is the mainstream of current vector type supercomputers. In the case of supercomputers, each processor 2 to 4 collects a large number of data as vector data, and the same processing is performed on the vector data by using a pipeline arithmetic unit. It is a vector processor that is continuously applied.

FIG. 2 shows independent computers 6 to 8 each having an arithmetic processing unit 10 and a dedicated main memory 9. Here, the computers 6 to 8 are called processors. These processors 6 to 8 are connected by an interconnection network 5. Currently, each processor is often composed of a high-performance microprocessor such as superscalar and a memory.

FIG. 3 has a configuration in which main memory shared parallel computers 12 to 14 (similar to FIG. 1) each composed of a main memory 15 and a plurality of processors 16 to 17 are further connected by an interconnection network 11. This is disclosed in, for example, Japanese Patent Laid-Open No. 6-96032. Each of the main memory shared computers 12 to 14 in the configuration of FIG. 3 is called a cluster.

An example of a method for executing LU decomposition processing in a parallel computer of the type shown in FIG. 2 is disclosed in Hoshino PAX Computer, Ohmsha Co., Ltd., 1985, JP-A-3-105694 and the like.

An outline of LU decomposition processing and a conventional method for executing LU decomposition processing by the parallel computer shown in FIG. 1 will be described with reference to FIGS. 4 and 5.

FIG. 4 shows K of the LU decomposition processing for the matrix A.
It is a figure for demonstrating the loop processing of the time. That is, each element a (i, j) of the matrix A (that is, the element at the i-th row and the j-th column) is divided into an element group subjected to different processing, and the element group is shown in the form of a region. . N in the figure
Is the matrix size. Here, the LU decomposition processing from the first row to the (K−1) th row and from the first column to the (K−1) th column is completed. In each iteration, a so-called multi-stage simultaneous erasing method in which M columns are grouped at once and LU decomposition processing is performed is used for speeding up. For this, M is plural,
In principle, M may be 1.

For the following description, the area from the Kth column to the Nth column to the Kth row to the Nth row of the matrix A is divided into five areas, and the areas are given the following names.

(1) L1 (K) 22: from the Kth column to the Kth +
Lower left triangular area composed of M-1 column and Kth to K + M-1th rows (2) U1 (K) 21: from Kth column to K + M-1th column and from Kth row to K + M-1th row Upper right triangular area configured (3) L2 (K) 23: rectangular area composed of Kth column to K + M-1th column and K + Mth row to Nth row (4) U2 (K) 24: Kth + Mth column To Nth column and Kth to K + M-1th rows (5) A (K) 25: K + Mth to Nth columns and K + Mth to Nth rows rectangular area diagram FIG. 5 shows an LU decomposition processing program according to the related art, which can be executed by the parallel computer of FIG. In this figure, L
The U decomposition program is composed of double DO loops.

The outer loop 20 repeats M / N times, which is the size N of the matrix divided by M, in order to process M columns at a time.

The inside is composed of two DO loops, and their processing is as follows. The number of times the outer loop 20 is repeated is K.

First, in the processing of the first inner loop (DO 1), from the Kth column to the K + M-1th column, that is, U
The partial axis selection (so-called pivot processing) and the erase update processing for the partial axis selection are repeated for each column in the areas of 1 (K) 21, L1 (K) 22 and L2 (K) 23. The outline of these processes is as follows.
The number of loop iterations of the first inner loop (DO 1) is K
Let M. However, KM is a value unrelated to K and M.

(1) Pivot processing: The maximum value is retrieved from the elements from the KMth row to the Nth row of the KM column, and the row containing the retrieved maximum value and the KMth row are exchanged. That is,
Swap the elements from the KMth column to the K + M-1th column of those rows.

(2) Erase / update processing: Erase / update processing for each element a (i, j) in the rectangular area constituted by the KM + 1th column to the K + M−1th column and the KM + 1th row to the Nth row. a (i, j) = a (i, j) −a (KM, j) ×
a (i, KM).

Hereinafter, the processing of this DO loop will be referred to as processing P (K). In the processing of this DO loop, since it is necessary to repeat the sequential processing of maximum value search,
Even if the loop itself is parallelized, the performance does not improve so much.

Next, the second inner DO loop (DO 2)
Then, the following processing is performed on the area U2 (K) and the area A (K).

(1) Area U2 (K) and area A (K)
Row exchange: For the elements from the K + Mth column to the Nth column of the M sets of rows subjected to the row exchange processing in the pivot processing described above,
Perform line exchange processing.

(2) Erase / update processing of area U2 (K) using area U1 (K) and area L1 (K): this area U2
For each element a (i, j) in (K), erase update processing a (i, j) = a (i, j) −a (k, j) × a (i, k)
Perform Here, k is sequentially changed from K to K + M-1, and this calculation is performed M times in total. Note that i is K + 1
To K + M−1, and j takes a value from K + M to N. Therefore, this calculation is based on
(K), L1 (K) using elements in region U2
The element in (K) is updated.

(3) Erase update process of elements in the region A (K) using the regions U2 (K) and L2 (K): erase update process a (i, j) = a (i, j) -a (K, j) × a (i, k)
Perform Here, k is sequentially changed from K to K + M, and this calculation is performed a total of M times. Here, i is one of k + M to N and j is one of K + M to N.

The process of the second inner loop will be referred to as process Q (K) below.

These calculations (1) to (3) are for the area U
It is possible to calculate independently for each column of 2 (K) and A (K). That is, the process of executing the above processes (1) to (3) for each column is a basic process, and the process Q (k) is a collection of this unit process for a plurality of columns. There is. For this reason, the processing for each column is performed by the processing Q.
It can be said that the partial processes constituting (K) can be executed in parallel with each other. Therefore, the Q (K) 28 is evenly divided into p groups in units of columns, and each is divided into Q1 (K) and Q2.
(K), ..., QP (K), and dividing into p processors to perform the processing makes it possible to obtain a p-number effect close to p times.

A flow chart of such LU decomposition processing is as shown in FIG. In FIG. 7, following the initial value setting 35 of the parameter K, after the process P (K) 36 is executed, the process Q (K) that can be parallelized is parallelized 37, and p processes Q are performed.
The processing is divided into 1 (K) 38 to processing Qp (K) 40, each processing is shared by p processors, and executed in parallel.
At this time, after the parallelized process Q (K), the process is sequentially returned to perform the K update process 41 and the convergence determination 42, and the process P (K +) that is the next K + Mth iteration loop.
M), and further process Q (K + M) is executed.

In order to obtain a program which divides the process Q (K) into a plurality of processes which can be executed in parallel, the automatic parallelization mechanism of the optimizing compiler can be used to execute parallel execution in the source program. The method is to detect these parts and automatically convert them into an object program that can be executed in parallel, or add a parallel directive line to the source program and convert this into an object program that can be executed in parallel by the compiler. To be The program shown in FIG. 5 is an example having a DO ALL type parallelization instruction line 29. In the case of this program, process Q
The parallelization of (K) 28 is performed by the parallel instruction line 29 every time each iteration.

As is clear from the above description, the basic processing flow of the LU decomposition processing is, as shown in FIG. 6, the initial value setting 30 of the parameter K and the updating processing 3 of the parameter.
3 and controls process P (K) 31 and process Q (K) 3.
It is repeatedly executed until the condition 34 (convergence condition or the number of iterations) specifying 2 is satisfied. The program of FIG. 5 enables this processing to be executed by the parallel computer of the format of FIG. 1 in accordance with the procedure shown in FIG. 7, and thereby speeds up the LU decomposition processing.

In the numerical simulation, not only the LU decomposition process, but also many iterative processes in which almost the same process is repeated according to the procedure shown in FIG. In that case, M may be 1. Even in such another iterative process, even if the process P can be originally executed only sequentially, by performing the process Q in parallel according to the process procedure shown in FIG. 7, such other iterative process can be performed at high speed. I can do it.

[0029]

When the LU decomposition process is processed by the procedure shown in FIG. 7, the process Q (K) is executed in parallel by a plurality of processors constituting the parallel computer, and therefore the process is executed. The time is reduced as the number of processors is increased. However, since the process P (K) is executed by one processor constituting a parallel computer at each iteration, the execution time of this process P (K) is large even if the number of processors is large. It prevents the processing time of the.

Suppose now that the size N of the target matrix is 1
000, the above process Q (K) and process P (K)
Respectively occupy about 98% and 2% of the total calculation amount of the LU decomposition process. However, the usage rates of the arithmetic units during execution of the processing P (K) and the processing Q (K) are significantly different.

For example, when the parallel computer of FIG. 1 is composed of four processors and each processor is a vector processor, this processing Q (K) can be processed in parallel, and pipes in different vector processors are used for this processing. A line arithmetic unit is also used, and since the calculation processing of the process Q (K) is a product-sum calculation, the usage rate of the pipeline arithmetic unit in each vector processor is high. On the other hand, the process P (K) uses only the arithmetic unit in one vector processor, and the main part of this process is the maximum value search process, and the amount of calculation is relatively large with respect to the required data amount. However, only some of the pipeline arithmetic units in this one vector processor are used, and the utilization rate of the arithmetic units is not high. Therefore, in the estimation example for the parallel computer including the four vector processors described above, the operation unit utilization rate of the process P (K) with respect to the process Q (K) is as low as about 1/10. Therefore, the ratio of the processing times of the processing P (K) and the processing Q (K) is about 10:12 (= 2: 98 / (10 × 4)), and the processing P (K ) Occupies about half of the processing time of the entire LU decomposition processing. Therefore, 4
Despite the use of one processor, the maximum performance improvement is only two.

The processor 1 shown in FIG. 1 is a superscalar processor and the total number of processors is 1.
In the estimation example in the case of about 00 units, the operation unit utilization rate of the process P (K) with respect to the process Q (K) is about 1/2. Therefore, the ratio of the processing times of the processing P (K) and the processing Q (K) is about 4: 1 (= 2: 98 / (2 × 100)), and the processing P (K ) Occupies about 80% of the calculation time. Therefore, 100
Despite using 10 processors, only 10 or more performance improvement can be obtained.

Therefore, the execution time of the process P (K) is
It is desired to further reduce the effect of LU decomposition processing on the overall processing time.

The same problem is not limited to the LU decomposition process, but the first process exemplified by the process P (K) and the parallel process exemplified by the process Q (K) to be executed after the execution of the process. The second process that can be executed is repeated, and this repetition occurs when the first and second processes are executed so that the first process is executed after the execution of the second process.

In other words, in the conventional method, some of the plurality of processors do not perform processing, and the other processors wait for a long time.

Therefore, the object of the present invention is to perform the first processing which should be sequentially processed and the subsequent processing,
And a second process that can be executed in parallel, and the first and second processes should be repeatedly executed so that the first and second processes are executed again after waiting for the completion of the second process. It is an object of the present invention to provide a parallel execution method of iterative processing capable of reducing the processing time of the entire iterative processing when the iterative processing is executed by a parallel computer.

Another object of the present invention is to reduce the time during which the processor is in a waiting state when executing such processing.

A more specific object of the present invention is to provide a parallel execution method of LU decomposition processing which can reduce the processing time of the entire LU decomposition processing when it is executed by a parallel computer. is there.

Another more specific object of the present invention is this L
The goal is to reduce the amount of time the processor is in a wait state when performing U decomposition processing.

[0040]

In the LU decomposition process described above, the process P is executed when the outer loop repeat count K is reached.
In the processing Q (K) executed using the result of (K),
The updated values of the elements of the area U2 (K) and the area A (K) are calculated. Among these elements, the elements used to calculate the process P (K + M) executed at the next iteration of the outer loop are the regions U1 (K) and L1 at the K + 1th time.
(K) and L2 (K) are the only elements that should belong. That is, in FIG. 4, it is an element in the region 26 constituted by the K + Mth row to the Nth row and the K + Mth column to the K + 2 * M−1th column. Therefore, the process P (K + M) is the process Q (K) (this is QS
(Let's call it (K)) must start execution after. However, the process P (K + M) is the area A
The processing Q (K) for the elements in the area other than the area 26 in (K) can be executed in parallel.

In the present invention, by utilizing this fact, the first process (for example, P (K), which is shown below in parentheses is an example) which should originally be processed sequentially, and the parallel process which should be executed after that. It has a second process (Q (K)) that can be executed, and repeats the first and second processes so that the first and second processes are executed again after waiting for the completion of the second process. When the parallel computer executes the iterative process to be executed in the same manner, the second process (Q (K)) executed in a certain iteration (Kth) is executed in the next iteration (K + Mth). First process to be performed (P
(K + M)) generates a processing result used by (Ks (K)) and the first processing (P (K) at the time of the next iteration).
+ M)) is assigned to the same processor, and this first process (P (K + M)) is executed in that processor following this partial process (QS (K)). Second process (Q
(K)), a part other than this partial process (QS (K)) can be executed in parallel by a number equal to the number P-1 of the remaining processors (Q2 (K) to QP (K)). ),
Run in parallel by those remaining processors.

At this time, when the processing time of the processor for executing the partial processing (Qs (K)) and the first processing (P (K + M)) is shorter than that of the other processor,
The partial processing (Q (K)) of the second processing (Q (K)) is performed so that the former processing time becomes almost the same as that of the other processors.
It is more desirable to allocate a part other than S (K)) to the processor to which this partial process (QS (K)) is allocated.
That is, after the first process (P (K)) necessary for carrying out the second process process (Q (K)) is executed in advance by one of the processors, each processor is processed as described above. A part of the second process (Q (K)) to be assigned is determined, and each processor follows the partial process (QS (K) or Qi (K) (i =
2 to p-1)) is executed.

In the processor to which the partial process (QS (K)) is assigned, when this process is completed, the first process (P (K + M)) is executed. This partial processing (QS
(K) and the first process (P (K + M)) and other partial processes (Q2 (K) to QP (K)) are completed,
The above process is repeated.

The present invention can also be implemented in parallel computers of the types shown in FIGS.

[0045]

The first process (P) of the next iteration ((K + M))
(K + M)) is a process other than the partial process (QS (K)) that needs to be executed prior to the first process (P (K + M)) of the second process (Q (K)). Since the processes are executed in parallel, the time during which the processors in the parallel computer are in the waiting state can be reduced, and the effective use of computer resources can be achieved. This makes it possible to reduce the processing time of the entire iterative process. Also, as in the past,
The first process (P (K + M)) is replaced with the second process (Q (K))
As compared with the conventional case of sequentially executing the above, the influence of the execution time of the first process (P (K + M)) on the entire iterative process can be reduced. The first process (P (K +
M)) is executed after this processing in the processor to which the partial processing (QS (K)) is assigned, and thus outputs a normal result.

[0046]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS A parallel execution method of iterative processing according to the present invention will be described below in more detail with reference to some embodiments shown in the drawings. In the following, the same reference numbers represent the same or similar items.

<Embodiment 1> This embodiment shows a parallel execution method of LU decomposition processing using the main memory sharing type parallel computer of FIG. FIG. 8 is an example of a program used in this embodiment, and FIG. 9 is a flowchart showing a procedure for executing the program in the apparatus of FIG.

In the following, the present embodiment will be described mainly on the basis of the flow chart of FIG. 9 regarding the parts different from FIG. 7 shown in the conventional example.

As described with reference to FIG. 5, the process P (K + M) in the next iteration of the LU decomposition process is the matrix A shown in FIG.
In, the processing is executed on the area 26 surrounded by the dotted line. Therefore, among the processing Q (K) of the previous iteration, FIG.
From the K + Mth column, which is the region 26 in the matrix A of K + 2 *
The remaining process (Q (K) -QS (K)) obtained by removing the update process QS (K) of the M-1 column from the process Q (K) and the process P (K +)
M) can be executed in parallel. The process P (K + M) can be executed any time after the process QS (K) is completed. Therefore, in FIG. 9, the process 63 for parallelizing the process Q (K) is executed, and the process Q1 ′ (K) 6 including the process QS (K) is performed.
4. The process Q2 '(K) 65 to the process QP' (K) 66 is divided into p parts, of which the process Q1 '(K) 64 is the same processor as the process P (K + M) 67, and before that process. By executing the process, the process Q2 '(K) 65 to the process QP' (K) 66 and the process P (K + M) can be executed in parallel.

In order to execute the process P (K + M) 67 in the Kth iteration, before entering the iteration loop controlled by 61, 68 and 69, the process P (1) 60 when K = 1.
Need only be executed once.

Process Q1 '(K) 64, process Q2' (K) 6
5 to processing QP '(K) 66 is divided into processing P (K +
It is necessary to divide so that the entire process including M) 67 is even. The division of the process Q (K) can be freely handled by changing the number of columns assigned to each processor. Here, the columns handled by the process Q1 ′ (K) 64 are K + M to K1, the columns handled by the process Q2 ′ (K) 65 are K1 + 1 to K2, and the columns handled by the process QP ′ (K) 66 are K (p- 1) to N.

K1, K by the equal division of this processing
A procedure of determining 62 of 2, ..., K (p-1) will be described.

First, the process QS (K) that needs to be executed prior to the process P (K + M) is at least the process Q1 '(K).
It must be included in 64. Therefore, K1 becomes K + 2 * M-1 or more (condition 1). Temporarily, process P
The number of columns when the calculation amount of (K + M) 67 is converted into the calculation amount of columns in the process Q (K) is Prow. Processing Q1 '
In order to make the sum of the operation amounts of (K) 64 and the process P (K + M) 67 1 / p of the whole and to satisfy the condition 1, the value of K1 is

[0054]

## EQU1 ## K1 = MAX (K + 2M-1, K + M + (N- (K + M) + 1-Prow) / p) (1) can be expressed. Here, MAX is a function for obtaining the maximum value.

Further, K2 to K (p-1) are processed Q
The process obtained by removing the process Q1 '(K) 64 from (K) may be equally divided by the remaining p-1 processors. Therefore, K2 to K (p-1) are given by

[0056]

## EQU2 ## It can be expressed by Ki = K1 + (i-1) / (p-1) * (N-K1) +1 (2). Where Ki is K2 or K
Indicates (p-1).

K1, K2, ... K by equal division of processing
The determination process 62 of (p-1) is efficient if it is performed for each iteration, but the target matrix gradually becomes smaller.
It is also possible to update the value every few iterations.

The program shown in FIG. 8 is the number of processors
This is the case where P is 4.

First, the process P (1) 45 when K = 1 is executed, and the iterative process instructed by the DO9 loop 46 is executed. Next, according to the equations (Equation 1) and (Equation 2) described above,
Determine K1, K2, K3 to divide the process evenly 4
7

In the parallel description of the program, since the process P (K + M) 58 is assigned to only one processor,
SECTION type parallelization instruction lines 48 to 53 are used. The processing of each processor executes the range delimited by each SECTON () statement.

In SECTION (1) 49, the process Q1 '
The (K) 54 and the process P (K + M) 58 are executed in this order. Here, the process Q1 ′ (K) 54 is the K + Mth matrix A
Responsible from column to column K1. Here, K1 is calculated using (Equation 1). The definition of K1 in (Equation 1) can guarantee that the processing Q1 '(K) 54 includes the processing QS (K) described above.

In SECTION (2) 50, processing Q2 '
(K) Execute 55. Process Q2 '(K) 55 is matrix A
(K1 + 1) to K2 columns. Here, K2 is calculated using (Equation 2).

In SECTION (3) 51, processing Q3 '
(K) 56 is executed. Process Q3 '(K) 56 is matrix A
(K2 + 1) to K3 columns. Here, K3 is also obtained using (Equation 2).

In SECTION (4) 52, processing Q4 '
(K) Execute 57. Process Q4 '(K) 57 is matrix A
Are in charge of the (K3 + 1) th column to the Nth column. Here, K3 is obtained using (Equation 2).

By compiling the program shown in FIG. 8, an object program executed in the procedure shown in FIG. 9 is generated. By this compilation, object parts corresponding to the parts shown in FIG. 8 are generated, and in order to control the execution of these object parts, the code for executing the parallelization process 63 and the synchronization process 69 is stored in this object program. Is added. Compilers for such purposes are already known.

According to this embodiment, since the process P can be incorporated into the parallel process substantially, the execution time of the process P is substantially shortened to (1-1 / p). As a result, the processing time of the entire LU decomposition processing is shortened. For example, if the parallel computer of the type shown in FIG. 1 has four processors and each processor is a vector processor,
When the size N of the matrix is 1000 and the execution times of the process P and the process Q are almost the same, the execution time of the LU decomposition process can be reduced by up to 35% by using this embodiment.

<Embodiment 2> This embodiment provides another example of a parallel execution method of LU decomposition processing using the main memory sharing type parallel computer of FIG. FIG. 10 is an example of a program used in this embodiment, and FIG. 11 is a flowchart showing an execution procedure when the apparatus of FIG. 1 executes this program.

In the first embodiment, as shown in FIG. 9, the parallelization processing 63 is performed every iteration so that the processing P (K + M) and the processing Q1 '(K +) of the next iteration are performed.
M) or processing QP ′ (K + M) is guaranteed to be in order. However, the parallelization process 63 that is performed each time may cause performance degradation because all processors are synchronized. In the present embodiment, a method will be described in which order synchronization processing is finely performed using synchronous processing using Post processing or Wait processing and the parallelization processing is moved to the outside of the iterative loop of the control variable K. The Post process and Wait process used here are Post / Wai issued by the OS.
It is not a t macro but a Post / Wait library which is one of the parallel control libraries of the compiler, and is a process with a low cost.

This processing procedure will be described with reference to FIG. 11 in comparison with FIG. First, as in FIG. 9, process P (1) 10
Execute 1. Next, the parallelization process 102 is moved outside the iterative loop indicated by the control variable K. For this reason, the equal division processes 103 to 105, the iterative loop control variable K updating processes 117 to 119, and the iterative loop determination processes 120 to 122 are executed in parallel for each processor. Further, in order to guarantee the order relation with the processing of the next iteration of another processor, it is necessary to execute the Post processing and the Wait processing between the processors.

The positions to be set in the Post process and Wait process will be described. The basic policy is to execute the Post process as soon as possible and the Wait process as late as possible. This increases the independence of execution of each processor and allows dynamic factors (eg,
It is possible to reduce unnecessary synchronization waiting at the time of Wait processing due to main memory access competition.

First, the execution order of the processor in charge of the process P (K + M) 107 will be described. The erase update process Q1 '(K) executed by this processor is processed QS (K) 106.
And processing (Q1 '(K) -QS (K)) 108. Here, the process QS (K) 106 is the process P (K +
M) 107, which is an updating process from the K + Mth row to the K + 2 * M−1th row in the matrix A, which is performed before the M) 107. Processing (Q1 '
(K) -QS (K)) 108 is the remaining processing relating to the processing Q (K) that this processor is in charge of. Process P
By executing (K + M) 107, it is possible to execute the processing Q2 '(K + M) 109 to the processing QP' (K + M) 110 of the next iterative loop of the other processor. Therefore, here, the Post processing 111 and the Wait processing are executed. The processes 115 to 116 are executed. Here, the Post process 111 corresponds to the Wait process of the other p-1 processors. Next, process (Q1 '(K) -Q1S
(K)) 108 is executed. Processing of the next iteration P (K + 2
In order to execute * M), it is necessary to execute the processing Q2 ′ (K) 109 to the processing QP ′ (K) 110 of another processor before that. Therefore, here, the Post processing 113 is performed.
Through 114 and Wait process 112. Here, the Wait processing 112 is established by receiving all Post processing from p-1 processors.

In this way, the processing Q1 '(K) is processed QS
(K) 106 and processing (Q1 '(K) -Q1S (K)) 10
By decomposing it into two, the Post process 111 can be executed immediately after the process P (K + M) 107, and the post process 111 is pos only for the time of the process (Q1 ′ (K) −Q1S (K))
The t process 111 can be executed earlier than the Wait processes 115 to 116 of other processors.

In the program shown in FIG. 10, the SECTI
The ON type parallelization 70 to 75 is performed only once.
Iterative loop 7 of control variable K executed by each processor between each SECTION () statement and each SECTION () statement
There are 6 to 79. Within each iterative loop is each operation 80-89. Multiple Post processes and W
In order to correspond to the ait process, an event variable is used as an argument here. The Post process 90 having a plurality of event variables issues the set number of events and corresponds to the Wait processes 95 to 97. The Wait process 94 having a plurality of event variables is established by receiving the set number of events from the corresponding Post processes 91 to 93.

By compiling the program shown in FIG. 10, an object program executed in the procedure shown in FIG. 11 is generated. This is the same as Example 1
Is the same as

<Embodiment 3> This embodiment provides a parallel execution method of LU decomposition processing using the main memory distributed parallel computer of FIG. FIG. 13 is an example of a program used in this embodiment, and FIG. 14 is a flow chart showing an execution procedure when the apparatus of FIG. 2 executes this program.

In such a parallel computer, as shown in FIG. 2, data transmission / reception processing is required between the processors 6 to 8 via the mutual connection network 5. The order is assured by using this data transmission / reception process. In the following, a message exchange type parallel computer will be described as an example.

In a distributed storage type parallel computer, it is necessary to divide and arrange data first. Here, as shown in FIG. 12, the matrix A is divided into rows for each width M of multistage expansion,
Divide into each processor sequentially. In such division, each processor sequentially takes charge of the pivot process P.

This processing procedure will be described with reference to FIG.
14 differs from FIG. 11 in that
(1) Instead of the Post / Wait process of the synchronous process,
Send processing and Re with data transmission / reception processing
(2) In the embodiment of FIG. 14, one processor is always in charge of the pivot processing P, whereas in the third embodiment, in order to make the load as uniform as possible, Alternate to take charge of the pivoting process. FIG. 14 shows a case where processing is executed by two processors (PEa and PEb). Of course, the same applies to the case of three or more processors. The process Q (K) is evenly divided into two, which is the number of processors. Process Qa performed by each processor
(K) and processing Qb (K).

At this time, if the data to be sent is Sen
When the d process and the Receive process for receiving the data can be executed asynchronously, it is necessary to precede the Send process as much as possible and similarly execute the Receive process as late as possible. This is Post / in FIG.
It is similar to the scheduling policy when the Wait process is used, and can be realized by decomposing the process Qa (K) into the process Qs (K) 170 and the process (Qa (K) -Qs (K)) 172. is there.

First, in each processor, 16
At 0 and 161, it is determined which processor the own processor is. This is generally for example UNIX
Prepare a discrimination library such as WHOAMI for commands in advance. Here, it is assumed that the respective processors are 162 and 163 which are determined to be their own processors.

Next, in the processor PEa, the process P (1)
166, and Send processing 167 is performed to transmit the data in the generated area L2 (FIG. 4) to the processor PEb.
Perform

On the other hand, the processor PEb executes the Receive process 168 for receiving this data. Less than,
Each processor enters an iterative loop of control variables K, respectively.

First, the processor PEb processes QS
(K) 173 is executed, and then process P (K + M) 1
Execute 74. As a result, the region L2 used for the K + Mth erasing process can be generated, so the Send process 178 is immediately executed on the processor PEa. After that, the remaining processing (Qb (K) -Qs (K)) 175 is executed, and the procedure is advanced to the K + M step which is the next iteration.

On the other hand, in the processor PEa, first the processing Q
The a (K) 169 updates the area of Q in charge, and then receives the L2 data necessary for the K + M step in the Receive processing 177. At this time, since the Send processing 178 on the processor PEb side is executed as soon as possible, there is not much waiting for reception in the Receive processing 177, and data can be received immediately.

Next, the process proceeds to the K + M step. This time, the processor PEa side is the pivot processing P (K + 2 * M) 171
In charge of. The following processing is equivalent to the procedure of the K step of the processor PEb. The processing of K + M steps is also performed in the other processor PEb in the same manner as the processing of K steps in the processor PEa.

First, the process QS (K + M) 170 is executed, and subsequently the process P (K + 2 * M) 171 is executed. As a result, the area L2 used for the K + 2 * Mth erase processing can be generated, and therefore the Send processing 179 is immediately executed on the processor PEb. After that, the remaining processing (Qa (K + M) -Qs (K + M)) 172 is executed, and in order to advance the procedure to the next iteration, K + 2 * M steps, the control variable K update processing 181 and the determination processing 183.
Perform

On the other hand, in the processor PEb, first the processing Q
The area of Q in charge is updated by the b (K) 176, and then the Receive processing 180 receives the L2 data necessary for K + 2 * M steps. At this time,
Since the Send processing 179 on the processor PEa side is executed as soon as possible, the Receive processing 180
There is not much waiting for reception, and data can be received immediately. After that, the control variable K update processing 182 and the determination processing 184 are performed.

In the program shown in FIG. 13, first, 130
Then, it determines which processor is its own processor. This is typically the case with the UNIX command WHOA, for example.
Prepare a discrimination library such as MI in advance.
The processing of each processor is performed by conditional statements 131 to 1
It is determined at 33. In FIG. 13, 136 or less 13
The process up to immediately before 2 is the process of the processor PEa, and the process up to just before 148 and 133 is the process of the processor PEb.

In order to alternately take charge of the pivot process in each processor, first, the process P (1) 136 is performed only once in the processor PEa, and the result is sent to the SEND process 1.
45, and the processor PEb receives RECEIV.
It is received in the E processing 148. Then, each processor enters an iterative loop. Each iteration loop DO91 and DO92
Performs the process for the control variable K twice.
Therefore, the designation of the intervals of the DO91 and DO92 loops is performed as shown in 134 and 135 of FIG.
It is twice as large as that of the example.

In the Kth step, the processor PEb
In, processing QS (K) 141, processing P (K + M) 1
42 and the processing (Qb (K) -Qs (K)) 143 are performed, and the pivot value is transmitted to the processor PEa in the SEND processing 149. The processor PEa processes Q in parallel.
a (K) 137 is performed, and the pivot value is received in the RECEIVE processing 146.

In the K + Mth step, the processor P
In Ea, processing QS (K + M) 138, processing P (K
+ 2 * M) 139 and processing (Qa (K + M) -Qs (K
+ M)) 140 arithmetic processing, and SEND processing 14
At 7, the pivot value is transmitted to the processor PEb. The processor PEb performs the process Qb (K) 144 in parallel, and receives the pivot value in the RECEIVE process 150.

By compiling the program shown in FIG. 13, an object program executed in the procedure shown in FIG. 14 is generated. This is the same as Example 1
Is the same as

<Embodiment 4> This embodiment is shown in FIG.
Provided is a parallel execution method of LU decomposition processing using a main memory distributed parallel computer configured by a plurality of clusters. FIG. 15 is an example of a program used in this embodiment, and FIG. 16 is a flowchart showing an execution procedure when this program is executed by the apparatus of FIG.

In such a parallel computer, the order is guaranteed based on the data transmission / reception processing as in the third embodiment.
Further, the parallel processing as in the first and second embodiments is performed between the processors in the cluster for each iteration.

The difference of the fourth embodiment from the third embodiment is that the parallel processing between the processors in the cluster is executed within each step execution. The procedure at this time is shown in FIG.
The method shown in Example 1 described above is used. Of course, it is also possible to use the procedure of FIG. 11 shown in the second embodiment.

In this embodiment, two clusters CLa and C are used.
It is assumed that Lb and the number of processors in each cluster are p. The processing procedure in this embodiment will be described below with reference to FIG.

16 is different from FIG. 14 in that
(1) The processors PEa and PEb in FIG. 14 correspond to the clusters CLa and CLb in FIG. 16, respectively. (2) In the processing of each step in each cluster, parallel processing is performed in p processors in the cluster. There are two things to do. FIG. 16 shows a case where the process is executed by two clusters (CLa and CLb). Of course, the same applies to the case of three or more clusters.

At this time, if the transmission S for transmitting data
When the end process and the Receive process for receiving data can be executed asynchronously, it is necessary to execute the Send process as early as possible and similarly execute the Receive process as late as possible. This is S in FIG.
It is the same as the scheduling policy when the end process / Receive process is used.

First, in the cluster CLa, the pivot process P
(1) The area L2 generated by performing 252 (see FIG. 4)
Send process 253 is executed to transmit the data of the above to the cluster CLb.

On the other hand, the cluster CLb executes the Receive process 254 for receiving this data. Hereinafter, each cluster enters an iterative loop of the control variable K. The control of the control variable K is performed by 279 to 282. The process Q (K) is evenly divided into two, which is the number of clusters. Process Qa for each cluster
(K) and processing Qb (K).

First, the cluster CLb performs the parallel processing 256 by using the p processors in the cluster in the Kth iteration processing. At this time, the method of dividing the parallel processing can be the same method as that of the first to third embodiments.

The processor in charge of the pivot process P (K + M) 263 executes the process QS (K) 262, and subsequently executes the pivot process P (K + M) 263.
As a result, the area L2 used for the K + Mth erasing process can be generated, and the cluster CLa is immediately converted into S.
The end process 268 is executed. After that, the remaining processing (Q
b (K) -Qs (K)) 264 is executed. Cluster CL
The other processors in b respectively process in parallel Qb2.
(K) 265 and the processing Qbp (K) 266 are executed.
Synchronization between processors within a cluster within K steps is
The parallelization processing 256 is performed. Then, the procedure proceeds to K + M steps.

On the other hand, in the cluster CLa, first the processing Qa1
(K) The area of Q in charge is updated in (K) 259, and then the Receive processing 267 receives the L2 data required for the K + M step. At this time, the Send process 268 on the side of the cluster CLb is executed as soon as possible, and therefore there is not much waiting for reception in the Receive process 267, and data can be received immediately.
The other processors in the cluster CLa execute the process Qa2 (K) 260 and the process Qap (K) 261 respectively in parallel. The synchronization between the processors in the cluster within K steps is performed in the parallelization processing 255. Then K +
Proceed to M steps.

Next, the process proceeds to the K + M step. This time, the cluster CLa side is in charge of the pivot process P (K + 2 * M) 270. The following processing is equivalent to the procedure of the K step of the cluster CLb.

The process QS (K + M) 269 is executed, and then the pivot process P (K + 2 * M) 270 is executed. As a result, the area L2 used for the K + 2 * Mth erasing processing can be generated, so that the cluster C
Send processing 277 is executed for Lb. After that, the remaining processing (Qa1 (K + M) -Qs (K + M)) 271 is executed. The other processors in the cluster CLa respectively perform the processing Qa2 (K) 272 and the processing Qap (K) 27 in parallel.
Execute 3. The synchronization between the processors in the cluster within K + M steps is performed by the parallelization processing 257. After that, the procedure proceeds to K + 2 * M steps.

On the other hand, in the cluster CLb, first, the processing Qb1
In (K + M) 274, the area in charge is updated, and then the L2 data necessary for K + 2 * M steps is received by the Receive processing 278. At this time, the Send process 277 on the side of the cluster CLa is executed as soon as possible, and therefore the Receive process 27 is executed.
There is not much waiting for reception at 8, and data can be received immediately. The other processors in the cluster CLb respectively perform the processing Qb2 (K) 275 and the processing Qbp (K) 2 in parallel.
Execute 76. The synchronization between the processors in the cluster within K + M steps is performed by the parallelization processing 258.
After that, the procedure proceeds to K + 2 * M steps.

The program shown in FIG. 15 shows a case where there are two clusters (CLa and CLb) and the number of processors in each cluster is two. Of course, in the case of a cluster of three or more, or the number of processors in the cluster can be three or more. In FIG.
The process from 206 to 202 immediately before 202 is the processing of the cluster CLa, and the process from 208 to 203 immediately before the 203 is processing of the cluster CLb. Here, first, in 200, it is determined which cluster is the own cluster. In general, a discrimination library such as WHOAMI of UNIX command is prepared in advance.

In order to alternately perform the pivot processing in each cluster, DO91 loop 204 and DO92 loop 2
Reference numeral 05 is processing the control variable K twice. Therefore, as in the third embodiment, DO91 and D
The designation of the O92 loop interval is 2 as compared with the first and second embodiments.
Has doubled.

Within each cluster, parallelization is instructed by parallel processing directives 209 to 224 for each iterative step K and K + M.

In the example of FIG. 15, in the cluster CLa, the parallel processing is defined for the step K by the parallel instruction lines between 209 and 212.
25 and 226, RECEIIVE processing 237. In step K + M, parallel processing is defined by the parallel instruction lines between 213 and 216.
7 to 229 and 230, and SEND processing 239.

In the cluster CLb, also for step K, parallel processing is similarly defined by the parallel instruction lines between 217 and 220, and arithmetic processing 231 to 234 and SEND processing 238 are performed. Step K + M
In the above, parallel processing is defined by the parallel instruction lines between 221 and 224, and the arithmetic processing 235 and 236, R
ECEIVE processing 240 is performed.

In the third and fourth embodiments, in this processing, Send processing for receiving and transmitting data and Rec.
It is necessary to execute the ive processing in parallel with other arithmetic processing. Of course, this Send processing and Receive
If the process can run on a dedicated communications processor,
After removing the processing time required for these communications, it is necessary to equalize the processing of the calculation amount within the processor in charge of the calculation.

Similar to the case of the first embodiment, an object program for executing the processing procedure shown in FIG. 16 is generated by compiling the program shown in FIG.

[0114]

The present invention has a first process that should be sequentially processed and a second process that can be executed in parallel and that can be executed in parallel. After waiting for the completion of the second process, the first process is executed again. When the parallel computer executes the iterative process that should be executed by repeating the first and second processes so as to execute the second process, the time during which the processor is in the waiting state can be reduced.
Effective use of computer resources can be promoted. This makes it possible to reduce the processing time of the entire iterative process.

[Brief description of drawings]

FIG. 1 is a diagram showing a schematic structure of a conventional main memory sharing type parallel computer.

FIG. 2 is a diagram showing a schematic structure of a conventional main memory distributed parallel computer.

FIG. 3 is a diagram showing a schematic structure of a conventional cluster-coupled parallel computer.

FIG. 4 is a diagram showing an outline of a conventional multistage simultaneous erasure LU decomposition method.

FIG. 5 is a diagram showing a program example of a conventional multi-stage simultaneous erase LU decomposition method.

FIG. 6 is a flowchart of conventional iterative calculation processing.

FIG. 7 is a flowchart of parallelized iterative calculation processing.

FIG. 8 is a diagram showing an example of a program used in the first embodiment of the present invention.

FIG. 9 is a flowchart of iterative calculation processing according to the first embodiment.

FIG. 10 is a diagram showing an example of a program used in the second embodiment.

FIG. 11 is a flowchart of iterative calculation processing according to the second embodiment of the present invention.

FIG. 12 is a diagram showing division of data for a distributed storage computer.

FIG. 13 is a diagram showing an example of a program used in Example 3 of the present invention.

FIG. 14 is a flowchart of iterative calculation processing according to the third embodiment.

FIG. 15 is a diagram showing an example of a program used in Example 4 of the present invention.

FIG. 16 is a flowchart of iterative calculation processing according to the fourth embodiment.

[Explanation of symbols]

20, 34, 42 ... Loop control, 27, 31, 36 ... Sequential processing P (K), 28, 32 ... Parallelizable processing Q
(K), 29 ... Parallel instruction, 38 to 40 ... Process capable of parallelization Q (K) is divided

Front page continuation (72) Yuko Tamaki, 1-280, Higashi Koikekubo, Kokubunji, Tokyo, Central Research Laboratory, Hitachi, Ltd. (72) Inventor, Tadayuki Sakakibara 1-280, Higashi Koikeku, Kokubunji, Tokyo Hitachi Research Center, Ltd. (72) Inventor Machiko Asaya 1-280, Higashi Koigokubo, Kokubunji, Tokyo Inside Central Research Laboratory, Hitachi, Ltd. (72) Yoshiko Yasuda 1-280, Higashi Koikeku, Kokubunji, Tokyo Inside Central Research Laboratory, Hitachi, Ltd.

Claims (14)

[Claims] 1. A repetitive process for repetitively executing a first process and a second process using the execution result, the second process comprising:
Processing consists of multiple sub-processes that can be executed in parallel,
The first process is the second process during a certain iteration of the iterative process.
A method of causing a parallel computer to execute the execution result of the process of step 1) used in the next iteration of the iterative process, comprising: (a) performing the iterative process by any one of a plurality of processors constituting the parallel computer. (B) One processing group uses the first processing in the next iteration among the plurality of partial processings included in the second processing. To generate at least some of the partial processing and the first processing, and the other processing group includes the second processing.
Included in the first process and the second process so as to include a part of a plurality of partial processes other than the plurality of partial processes included in the process. The plurality of the plurality of partial processes are divided into a plurality of processing groups whose number is equal to the number of the plurality of processors, and (c) the execution result of the step (a) is obtained for the first iteration. Using the result of this execution of the plurality of sub-processes for the next iteration, the first process being performed The one processing group including at least a part of a plurality of partial processings and the first processing is executed by any one of the plurality of processors, and (d) each of the plurality of other processors Using one of the plurality of processing groups for the first iteration using the execution result of the step (a) And (e) after the execution of step (c) or (d) by each processor is performed in parallel with the above execution by step (c) by the one processor, e)
In the iteration, (e1) the second processing is executed for the iterations after the next iteration, and the first processing is performed for the next iteration of the iterations after the next iteration. The execution result of the first process, which is obtained as a result of the execution of step (c) before executing the steps (c) to (d) and (e2) above, as A parallel execution method of the iterative process used in the second process in step (d) executed after repeating the above process. 2. A parallel execution method for iterative processing according to claim 1, wherein at the time of repeating by step (e), step (b) is also executed and then repeated. 3. The step (b) is such that a plurality of other partial processings to be executed by the one processor in addition to the plurality of partial processings belong to the one processing group. The parallel execution method for iterative processing according to claim 1, further comprising the step of executing the division. 4. The step (b) is required for execution of each of the plurality of partial processes and a first processing time required for executing the first process, and each of the plurality of other partial processes. The parallel execution method for iterative processing according to claim 1, further comprising the step of performing the division so that the execution times of the plurality of processing groups are substantially equal based on the second processing time. 5. The iterative process is a process for LU decomposition of a coefficient matrix of N-dimensional simultaneous linear equations, the first process includes a pivot process, and the second process is an erase / update process of a coefficient matrix. A parallel execution method for iterative processing according to any one of claims 1 to 4, further comprising: 6. The step (e), after detecting the end of the processing in each processor, repeats the step (c) by the one processor and the step (d) by each of the other plurality of processors. 2. The parallel execution method for iterative processing according to claim 1, further comprising the step of starting simultaneously. 7. The step (e) comprises the step of determining, by each processor, the end of the process by each of the other processors after the end of the process by that processor, and by each processor. 2. The parallel execution method for iterative processing according to claim 1, further comprising the step of activating the repetition of step (c) or (d) in the processor when the end of the processing is detected. 8. The parallel computer further comprises a main memory shared by the plurality of processors, the method comprising: (f) when each processor finishes executing the step (c) or (d). The method further comprises the step of writing information indicating the end by the processor to the main memory, wherein the step (e) is based on the information written by the processor to the main memory and indicating the end of the processing by the processor. The parallel execution method of the iterative process according to claim 7, which is performed by the method. 9. In step (f), after the execution of step (c), information indicating the end of processing by the one processor is written in the main memory by the one processor, and the information of the plurality of other processors is written. Step (d) by each
After the execution of any of the sub-processing groups by, each processor writes information indicating the end of the processing in that processor to the main memory, and step (e) is performed by the one processor. After writing the information indicating the end, the first processor monitors whether or not the information indicating the end is written in the main memory by each of the other plurality of processors, and the plurality of other processors are monitored. After the writing of the information indicating the end by each of the processors, whether or not the information indicating the end by each of the processors other than the plurality of other processors is written in the main memory is determined. By monitoring by each of the processors, execution of the process at step (c) or (d) by the other processor is completed by each of the plurality of processors. Step (e) is performed for each processor based on the determination result of the end of another processor for each processor in Step (e). 9. The parallel execution method for iterative processing according to claim 8, further comprising the step of determining the start time of the iteration of (d). 10. An iterative process for iteratively executing a first process and a second process using the execution result, wherein the second process comprises a plurality of partial processes that can be executed in parallel. The first process is a method of causing a parallel computer to execute the execution result of the second process in a certain iteration of the iterative process, which is used in the next iteration of the iterative process. Any one of the plurality of processors constituting the parallel computer executes the first process for the first iteration of the iterative process, and (b) one process group is included in the second process. Among the plurality of partial processes, the first process includes at least a part of the partial processes that generate data to be used in the next iteration and the first process, and the other process group includes , Second
Of the plurality of partial processes included in the process, the plurality of the plurality of partial processes included in the second process are included so as to include a part of a plurality of partial processes other than the plurality of partial processes of the part. The partial processing and the first processing are divided into a plurality of processing groups whose number is equal to the number of the plurality of processors, and (c) the execution result of the step (a) is used for the first iteration. To execute the first process using the execution result of the plurality of partial processes for the next iteration. The one processing group including at least the plurality of partial processings and the first processing is executed by any one of the plurality of processors, and (d) the plurality of processings are performed by each of the plurality of other processors. One of the processing groups, using the execution result of step (a) for the first iteration, And (e) in each processor, when the execution of step (c) or (d) by the processor is completed, the processor is executed in parallel with the execution of step (c) by the one processor. By repeating (c) or (d) above,
In the repetition, (e1) step (c) or (d) is executed so that another processor group different from the processing group executed in step (c) or (d) is executed in that processor. (E2) When the other processing group includes the partial processing group of the second processing, the partial processing group is executed for the iterations after the next iteration, and the other processing group When it includes the processing of 1, the first
Is executed for the next iteration of the iterations after the next iteration, and (e3) when the processing group executed by the processor in step (c) or (d) does not include the first processing, A parallel execution method of repetitive processing, comprising the step of starting the above-mentioned repetition after confirming the notification of the execution result of the first processing notified from another processor. 11. The parallel execution method for iterative processing according to claim 10, wherein the iteration in step (e) is performed so that each processor sequentially executes a different processing group for each iteration in step (e). 12. When any one of the processors executes the one processing group for any of the repetitions in step (c), the execution result is notified to a plurality of other processors, and the other plurality of processors are notified. Each of the processors executes the other one process group of the plurality of process groups for the repetition after confirming that the execution result is notified from the one processor. Executing the one processing group for the next iteration of the above iteration, notifying another processor of the execution result of the other processing group by each of the other plurality of processors, and In the processor, after the reception of the execution result of the plurality of processing groups for the repetition from the plurality of processors other than the processor is confirmed by the other processor, Relative return, claim 10 further comprising the step of initiating said one processing
A parallel execution method of the described iterative processing. 13. A distributed computer having a set work for connecting the plurality of processors to each other, and a local memory provided corresponding to each processor for holding a program and data executed by the processor. 13. A parallel execution method for repetitive processing according to claim 12, wherein the method is a memory parallel computer, and the notification of the execution result of the one processing and the notification of the execution result of the other processing group are performed via this network. 14. A repetitive process for repetitively executing a first process and a second process using the execution result, wherein the second process comprises a plurality of partial processes that can be executed in parallel. In the first process, the execution result of the second process in one iteration of the iterative process is used in the next iteration of the iterative process and shared by a plurality of processors. A plurality of clusters having local memory for holding programs and data;
A method of executing in a distributed storage parallel computer comprising a network connecting them, comprising: (a) repeating by one of a plurality of processors included in any one of the plurality of clusters. The first process is executed for the first iteration of the process, and (b) one process group is included in the second process, and when the first process is the next iteration, At least a part of a plurality of partial processes for generating data to be used and the first process are included, and the other process group includes a second process.
Included in the first process and the second process so as to include a part of a plurality of partial processes other than the plurality of partial processes included in the process. The plurality of the plurality of partial processings are divided into a plurality of processing groups whose number is equal to the number of the plurality of clusters, and (c) one of the plurality of processing groups is divided by each of the plurality of clusters. (C1) The plurality of partial processes and the first partial process are executed in one processing group when executing one processing group by each cluster. When processing and is included,
One partial process group including at least a part of the plurality of partial processes and the first process, and other than the some of the plurality of partial processes included in the second process. Of the plurality of partial processes, the process of the one process group is divided into a plurality of other partial process groups, and the one part of the plurality of partial processes and the first partial process When the processing is not included, among the plurality of partial processings included in the second processing, a plurality of other partial processings each including a part of a plurality of partial processings other than the plurality of partial processings The processing of the one processing group is divided into processing groups, and (c2) a plurality of processors in the cluster divides the processing into the step (c
One of a plurality of partial processing groups obtained by the division according to 1),
When the first processing is included in the one processing group executed in the cluster in parallel with the execution of another partial processing group by another processor in the cluster, (c3) One processor that has executed one partial process group to which one process belongs notifies other clusters of the execution result of the first process. (D) In each cluster, the step (c1 (C) is repeated when the execution of () is completed, and in the repetition, (d1) another processing group different from the processing group executed in step (c) by the cluster among the plurality of processing groups. Repeat step (c) so that
(D2) If the first process is not included in the process group executed by the cluster in step (c), the execution result of the first process notified by another cluster is notified. After confirming, the execution of the other processing group is started, and (d
3) The other processing group executed in the repetition is the second
When the sub-process group belonging to the process is included, the sub-process group is executed for the iterations after the next iteration, and the other process group includes the first process. Sometimes, the parallel execution method of the iterative processing that executes the other processing group so that the first processing is executed for the next iteration of the iteration after the next iteration.