JP3300388B2 - Parallel process generation method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a process for generating a parallel process in a short time in a distributed memory type parallel computer system in which a problem is divided into processes operating on respective processors and the process is executed at high speed. And a method for generating a parallel process.

2. Description of the Related Art With the rapid progress in the field of scientific and technological computing, demands for ultra-high-speed computing capabilities are increasing in universities, research institutes, and industrial fields. In addition, this demand is expanding to fields such as fluid analysis, structural analysis, image processing, and even weather forecasting. A parallel computer is one of means for realizing ultra-high-speed calculation for such a request. In this method, a plurality of processors are used, and a given problem is divided and executed by the processors.

[0003] Parallel computers can be broadly classified into two types, a shared memory type and a distributed memory type, depending on how the memory is held. The shared memory type is a method in which memory is shared by multiple processors. While it is possible to easily transfer a sequential processing program, it is a major issue how to avoid contention for memory access. It is difficult to combine a thousand processors.

[0004] The distributed memory type is a system having a memory for each processor, and it is easy to expand the processor, but it is difficult to transfer existing software. When a problem is divided and executed using a distributed memory type parallel computer, there is a method of allocating a process to each processor and executing the process. This process is called a parallel process.
If it takes a long time to generate a parallel process, the entire processing is slowed down by that much. Therefore, a technique for generating a parallel process as quickly as possible is required.

[0005]

2. Description of the Related Art FIG. 4 is an explanatory diagram of the prior art. The process of generating one parallel process is performed by the operating system. Conventionally, when generating n parallel processes, the parent process has generated all processes using a function provided by the operating system.

FIG. 4A shows a processing flow of a parent process for generating a parallel process according to the prior art.
That is, in the prior art, the following processes for generating a parallel process are executed.

The counter i for the number of processes to be created is set to 0
Initialize to A process is created on the destination processor using the functions of the operating system.

The counter i is incremented by one. It is determined whether the value of the counter i is smaller than the number of processes to be created. If the value is smaller, the process returns to the process, and the process is repeated in the same manner. When the value of i reaches the number of processes, the process ends.

By the above processing, in the prior art, as shown in FIG. 4B, the parent process P0 sequentially generates child processes P1, child processes P2,..., Child processes Pi. become.

This method has the advantage that the parent-child relationship of the processes is simple and easy to handle, but has the disadvantage that it takes too much time to generate all the processes because parallel processes are generated one by one.

[0011]

The time required for the process of generating one process has a considerable overhead of several tens to several hundreds of times as compared with the normal process. Therefore, when a parallel computer combining several hundreds or thousands of processors is realized, the conventional method for generating a parallel process requires a long time for generating all the parallel processes, and the overhead is a major problem. Become.

SUMMARY OF THE INVENTION It is an object of the present invention to solve the above-mentioned problems, to reduce the overhead at the time of generating a parallel process, and to fully exploit the performance of a parallel computer.

[0013]

FIG. 1 is a diagram illustrating the principle of the present invention. In FIG. 1, 10-0, 10-1,..., 1
0-i is a processor constituting a parallel computer, 11 is a first process for generating a parallel process, 12 is a second process for generating a parallel process, and P0 to Pi are processes. Represents a parent process, and P1 to Pi represent child processes.

A parallel computer embodying the present invention has a large number of processors 10-0 to 10-0, for example, as shown in FIG.
10-i are connected, and in each processor, a process for executing a given program operates. This parallel computer is of a distributed memory type, and each of the processors 10-0 to 10-i has a local memory. The connection method of the processors may be any connection method such as a bus connection, a crossbar connection, a network connection, and a lattice connection.

In the present invention, as shown in FIG.
First, in a first step 11, one parent process P0 generates one child process P1. Next, the second process 1
According to 2, the parent process P0 and the child process generated in the previous process respectively generate different child processes. This second step 12 is repeated until the required number of processes has been generated.

That is, when the parent process P0 generates the child process P1 in the first process 11, the second process 1
In 2, the parent process P0 and the child process P1 generate a child process P2 and a child process P3, respectively. further,
In the second step 12, the four processes of the parent process P0 and the child processes P1, P2, and P3 each create a new child process. Similarly, the newly created child process becomes the parent and creates the next child process. Special
In addition, in the present invention, a parallel processor operating on each of the above processors is used.
Function or support a generation processing program that generates processes.
Input parameters of the generation processing program
Is the source processor number and the
A value corresponding to the number. This generation processing program
Until the required number of processes have been created,
Process to create a process in the
And the generation destination processor.
Processing to recursively call and execute
I do. In determining the generation destination processor,
Divide the value corresponding to the number of processes to be spawned into two
From the generated processor number,
Determines the processor number and calls the generation processing program recursively.
At the time of the
The input parameter is a value corresponding to the number of processes.

[0017]

According to the present invention, not all the child processes are created by the parent process P0, but a new child process is created again by the created child process. Therefore, the generation process of the parallel process is performed by each of the processors 10-0 to 10-.
Since i executes the load sharing as uniformly as possible, and the processes are generated in a binary tree in a double-by-two manner, the entire process generation time can be greatly reduced. In particular, the source processor number and the
Generate values corresponding to the number of processes as input parameters
Just call the processing program and the required number of parallel programs
Process can be generated, so that
A row process can be created.

[0018]

FIG. 2 shows a processing flow of an embodiment of the present invention.
In the present invention, for example, a parallel process operating on each processor of the parallel computer system is generated by the processing of the generation processing program shown in FIG. This processing is made into a function or a subroutine. The parent process executes first, and the parent process and the child process execute in parallel after the second time.

Hereinafter, description will be made in accordance with the processing shown in FIG. In the following description, a processor number is a number assigned in advance to identify a processor. Here, for simplicity,
It is assumed that the processor number of the parent process is 0 and the number of the processor on which the child process operates is a continuous number from 1.

The input parameters are the source processor number and “width”. Here, the width means a value corresponding to the number of processes to be created. First, it is determined whether or not the required number of processes have been created by checking the width parameter, and if so, control is returned to the caller and the process creation process is terminated.

If it is necessary to create a process, the width value is reduced to half the current value. The value obtained by adding the value of the new width to the source processor number is used as the destination processor number.

For the operating system,
Requests the process to create a process from the creation destination processor,
Create a child process. By a so-called recursive call, a generation processing program having the same processing procedure is called. At this time, as the input parameter, the generation source processor number is used as the generation source processor number, and the value of the width calculated in the process is used as the width.

Similarly, a generation processing program having the same processing procedure is called. The input parameters at this time are
The generation destination processor number set in the processing is used as the generation source processor number, and the width value calculated in the processing is used as the width. With this call, another child process is created on the processor on which the new child process operates.

The processing of the generation processing program shown in FIG.
When expressed by a notation in the well-known C language, it becomes as shown in FIG. Here, in a function named tree-fork, the generation source processor number and the width are arguments of the function. When the width becomes 1, the process generation processing ends, and the process returns to the calling source. The reason why the width is reduced to half each time a process is generated is that the process is generated in a binary tree shape.

For example, when a total of eight parallel processes are required, first, the parent process is set to tree-fo
Execute rk (0,8). That is, the function is executed with the generation source processor number set to 0 for the processor number on which the parent process operates and the width set to 8.

By executing the function, the width becomes 8/2 = 4, and the generation destination processor number becomes 0 + 4 = 4. Based on this value, a child process operating on the processor with the processor number of 4 is generated. After that, tree-fork
(0, 4) and tree-fork (4, 8) are executed. In the former function, the originating parent process sets the width to 4
In the latter function, the generated child process executes the generation process of another child process.

By repeating the above processing until the width becomes 1, a total of eight parallel processes including the parent process can operate. (B) of FIG.
A state of generation of a process when ork (0, 8) is executed is shown. The parent process first creates a child process 4, then the parent process creates a child process 2, and the child process 4 creates a child process 6. Thus, a process always creates a child process.

Assuming that x is the generation time per process and n is the number of processes, in the case of the prior art, the total generation time of the child process is as follows. Total process creation time = x * n (* is a multiplication symbol) In contrast, according to the method of the present invention, the total creation time of the child process is as follows.

[0029] As the whole process generation time = x * log ₂ n clear from this, when using the technique of the present invention, the total generation time of the process is greatly shortened, the effect is large enough, especially a large number of parallel processes to produce .

[0030]

As described above, according to the present invention,
The total process generation time is greatly reduced, and the overhead during parallel process generation can be reduced. This makes it possible to further exploit the capabilities of parallel computers for scientific and technological calculations, and will greatly contribute to the development of parallel technologies in the future.

[Brief description of the drawings]

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

FIG. 2 is a processing flow of an embodiment of the present invention.

FIG. 3 is an explanatory view of one embodiment of the present invention.

FIG. 4 is an explanatory diagram of a conventional technique.

[Explanation of symbols]

 10-0 to 10-i Processor 11 First Process 12 Second Process P0 Parent Process P1 to Pi Child Process

────────────────────────────────────────────────── ─── Continuation of the front page (56) References JP-A 1-25953 (JP, A) JP-A 1-70862 (JP, A) JP-A 62-160563 (JP, A) Takeo Nakata, Susumu Horiguchi , Parallel Sorting on Multiprocessor Workstations, IEICE Technical Report, July 19, 1990, Vol. 90, No. 143, p. 41-p. 46 (58) Fields surveyed (Int.Cl. ⁷ , DB name) G06F 9/46 G06F 15/16-15/177 JICST file (JOIS)

Claims (1)

(57) [Claims] 1. A parallel process generation method in a parallel computer system in which a plurality of processors execute a plurality of processes in parallel, at least a generation source processor number and a program to be generated.
The value corresponding to the number of processes
A function that creates a parallel process running on the processor or
A required number of processes are executed by using the generation processing program which is a subroutine.
Until it is created, the process that creates the process in the destination processor and the process of both the source processor and the destination processor
Call the generation processing program recursively
Performs a process to be executed by, in determining the product destination processor, attempts to the product
Using the value obtained by dividing the value corresponding to the number of processes
From the source processor number to the destination processor number.
Is determined and when the generation processing program is recursively called,
Corresponds to the number of processes that will try to generate the bisected value next
A method for generating a parallel process, characterized in that it is an input parameter of a value to be processed.