JPH06214801A - Automatic parallelizing translation device and method - Google Patents

Abstract

(57) [Summary] [Purpose] Enter the original code written in the sequential language,
A parallel DO loop that can be executed in parallel by a parallel computer and a serial DO loop that cannot be executed in parallel are extracted from the original code, and the extracted parallel DO loop is configured to execute each term in the DO loop in parallel. The present invention relates to an automatic parallelizing translation apparatus and method for converting an original code into a target code for a parallel computer by creating a parallelized code, and by reducing the number of processing steps, speeding up the processing, reducing the processing time, and reducing the parallelism. Since the processing efficiency of the computer can be improved, the purpose is to effectively utilize the parallel computer. A dependency between the extracted DO loops is detected, and parallel execution between the DO loops is possible based on the parallelization code in the DO loop and the detected dependency between the DO loops. It is configured to create parallelized code between DO loops.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an automatic parallelizing translation apparatus (compiler) and method, and in particular, a parallel DO loop capable of parallel execution by a parallel computer by inputting an original code described in a sequential language. Also, a serial DO loop that cannot be executed in parallel is extracted from the original code (program), and each term (step, iteration) is executed in parallel in the extracted DO loop D
The present invention relates to an automatic parallelizing translation apparatus and method for converting an original code into a target code (program) for a parallel computer by creating a parallelized code in an O loop. Currently, as a method to realize a high-speed computer (super computer),
Parallel computers are in the spotlight. As one of the methods of programming a parallel computer, there is a method of describing a process in a serial language that has been widely used from the past such as Fortran and converting it into a code for a parallel computer by using an automatic parallelizing compiler. is important. The reason is that it is difficult to directly describe parallel processing, that there is no standard programming language that describes parallel processing yet, and in the past F
Making use of assets written in ortran etc. can be mentioned. The present invention relates to a technique for executing DO loops in parallel in the automatic parallelizing translation device and method (automatic parallelizing compiler).

[0002]

2. Description of the Related Art Conventionally, as shown in FIG. 12, a parallel DO loop which can be executed in parallel by a parallel computer and a serial DO loop which cannot be executed in parallel are extracted from an original code written in a serial language. For the DO loop extraction unit 1 and the extracted parallel DO loop, create a DO loop parallelization code so that each term in the DO loop is executed in parallel D
There is an automatic parallelizing translation device that has an in-O-loop parallel code creating unit 8 and converts the original code into a target code for a parallel computer. Scientific computing programs are usually
It is known that most of the processing time is spent on the DO loop in the program. In the conventional parallelization, the DO
The loop extraction unit 1 can execute each iteration (term, step) in parallel from the DO loop (parallel D
O loop), and the DO loop parallelization code creation unit 8
Each item (iteration, step) is assigned to the processor by and the target code for parallel execution is created.

[0003]

In the conventional example described above, in the method of mapping each step of the parallel DO loop to the processor and executing the parallel execution,
There has been a problem that the processing of the portion of the sequential DO loop has to be always performed sequentially, and the goodness of the parallel computer is not utilized and it takes time. In addition, recently, a method of considering one DO loop as one task and performing parallelization at the task level has been proposed. However, this task-level processing has a problem that even if the DO loop is a parallel DO loop, the fact is not utilized and higher parallelism cannot be obtained. Therefore, according to the present invention, in order to realize a parallel execution method that can bring out the advantages of both, even if a plurality of DO loops are all sequential DO loops and there is a dependency even at the task level and parallel execution is not possible, some parallel execution is performed. It is an object of the present invention to provide an automatic parallelizing translation device and method for performing code conversion to obtain a code that can be processed at high speed.

[0004]

In order to solve the above technical problems, the first invention is, as shown in FIG. 1 and claim 1, a parallel computer from an original code written in a sequential language. A DO loop extraction unit 10 that extracts a parallel DO loop that can be executed in parallel and a sequential DO loop that cannot be executed in parallel, and a DO loop that causes each term in the DO loop to be executed in parallel for the extracted parallel DO loop. In the automatic parallelizing translation device that has a DO parallel code creating unit 80 for creating parallelized code, and converts the original code into a target code for a parallel computer, the dependency relationship between the extracted DO loops Inter-DO-loop dependency relationship detection unit 20 for detecting the DO loop, and the parallel execution between the DO loops dynamically based on the inter-DO-loop parallelization code and the detected dependency relationship between the DO loops. Possible to those having a DO loop between dynamic parallelized code creation unit 30 to create a dynamic parallelized code between DO loops.

In the second invention, as shown in FIG. 2 and claim 2, the original code described in the sequential language is input (S
1), a parallel DO loop that can be executed in parallel by a parallel computer and a serial DO loop that cannot be executed in parallel are extracted from the original code, and the extracted parallel DO loop is DO
In an automatic parallelizing translation method for converting an original code into a target code for a parallel computer by creating a DO loop parallelizing code for executing each term in the loop in parallel (S2), between the extracted DO loops Between the DO loops that enable parallel execution dynamically between the DO loops based on the detected dependency between the parallelized code in the DO loops and the detected DO loops (S3). This is to create a dynamic parallelization code (S4).

A third invention is, as shown in FIG. 3 and claim 3, a parallel DO loop capable of parallel execution by a parallel computer and an impossibility of parallel execution from an original code written in a sequential language. A DO loop extraction unit 10 that extracts a sequential DO loop, and a DO loop parallelization code creation unit 80 that creates a DO loop parallelization code that causes each term in the DO loop to be executed in parallel for the extracted parallel DO loop. In the automatic parallelizing translation device for converting the original code into the target code for the parallel computer, the inter-DO loop dependency relationship detection unit 20 for detecting the dependency relationship between the extracted DO loops, and the processing are A designation information output unit 40 that outputs designation information that designates a processor to be allocated in advance, the DO loop parallelization code, the dependency relationship between the detected DO loops, and Based on the designation information and has static and DO loop between static parallelized code creating unit 31 that creates a static parallelized code between DO loop that enables parallel execution between a DO loop.

In a fourth invention, as shown in FIG. 4 and claim 4, an original code described in a sequential language is input (S
1), a parallel DO loop that can be executed in parallel by a parallel computer and a sequential DO loop that cannot be processed in parallel are extracted from the original code, and the extracted parallel DO loop is DO.
In the automatic parallelizing translation method for converting an original code into a target code for a parallel computer by creating an intra-DO loop parallelizing code to be executed in parallel within the loop (S2), the dependency between the extracted DO loops Is detected (S3), the DO loop parallelization code, the detected dependency between the DO loops, and the designation information that pre-designates the processor to which the process is to be assigned are statically set between the DO loops. This is to create a static parallelization code between DO loops for executing the parallel execution of (S14).

[0008]

Next, the processing operation of the present invention will be described.
In step S1, the original code written in the sequential language that is the target of automatic parallel translation is written into the DO loop extracting unit 1.
Enter 0. Here, "automatic parallelization translation" refers to conversion of an original code (original program) written in a sequential language into an object code (object program) for a parallel computer. Further, the "serial language" is, for example, FORTR.
It is a language that has been widely used from the past, such as AN, and that automatically controls a computer sequentially according to a series of instructions designated in advance. In step S2, the DO loop extraction unit 10 extracts a parallel DO loop and a sequential DO loop from the original code. Here, the "parallel DO loop" is a DO loop in which each item (step, iteration) can be executed in parallel by a parallel computer, and the "sequential DO loop" is an irregular dependency of each item by the parallel computer. It means a DO loop that cannot be executed in parallel because of having a relationship. The extraction of the parallel DO loop is a parallel DO loop, in which parallel execution is possible when the terms are independent by examining the data dependency between the terms in the DO loop. For example, there is a case where each term (i = 1, 2, ..., N) is represented as A (i) and A (i−1), respectively. The case where parallel execution is not possible is a case where, for example, each term (i = 1, 2, ..., N) is represented as A (i) and A (n + 1-i), respectively. When a parallel DO loop is extracted, the DO loop parallelization code creating unit 8
0 is D to execute each term in the parallel DO loop in parallel.
Create parallel code in O-loop.

In step S3, the inter-DO-loop dependency relationship detecting section 20 detects the inter-DO loop dependency relationship. Generally, when there is no dependency between DO loops, it means that processing can be performed independently between the DO loops and parallel execution is possible. In step S4, the dynamic parallelization code creation unit 30 between the DO loops.
Is the dependency relationship detected by the inter-DO loop dependency relationship detection section 20 and the DO loop parallelization code creation section 80.
DO that enables parallel execution dynamically between DO loops based on the parallelized code in the DO loop created by
Create dynamic parallelization code between loops. Here, “dynamic” means “dynamic scheduling”, and a program (code) that does not depend on the number of processors of a parallel computer is generated at the time of compilation. Inserts the code for allocating (scheduling) processing to a free processor at runtime. The advantage is that load distribution is easy. The disadvantage is the overhead of processor allocation at runtime. On the other hand, "static" means "static scheduling", which is a method of allocating programs to be executed in parallel to processors at the time of compilation. The advantage is that there is no processor allocation (scheduling) overhead at runtime. The disadvantage is that load distribution is difficult. For example, as described in claims 5 and 6, when it is detected that there is no dependency between each serial DO loop and the parallel DO loop, the serial DO loop is preferentially used in the parallel computer at the time of execution. Assigned to other processors, and parallel D
The inter-DO loop parallelization code or the inter-DO loop static parallelization code is created to execute the O loop.

Further, in claim 7 and claim 8, the DO loop inter-dependency relation detecting section 20 causes the data dependency between two DO loops having data dependency to be the term of each of the two loops. When it is detected that the numbers (subscripts) are always equidistant, the DO loop dynamic parallelization code creating unit 30 or the DO loop static parallelization code creating unit 31 pipelines the execution of each item. A dynamic parallelization code between DO loops or a static parallelization code between DO loops for executing Here, “equal distance” means that it can be expressed by “Distansce vector”. For example, each term of the two DO loops is A (i)
, And A (i-1). On the other hand, each term of the two DO loops is A (i),
The case represented by A (100-i) is an example when the distances are not equidistant. According to claim 9, when a plurality of DO loops are pipeline-executed on a parallel computer having a hierarchical memory, the DO loops are allocated to the same cluster so that the communication between the DO loops does not cross the hierarchy. Create dynamic parallelization code or dynamic parallelization code between DO loops. Here, "hierarchical memory" refers to a plurality of memory devices connected to various distances from the processor when attention is paid to the processor on the system, and a hierarchy is set according to the distance. There is. For example, the cache memory is closest to the processor, the next is the main memory of the cluster, and the main memory of another cluster connected via the network. The memory is located. When a pipeline execution between DO loops is performed by a parallel computer having a hierarchical memory, the DO clusters are allocated to the same cluster so that the communication between the DO loops does not cross the hierarchy. This enables high-speed pipeline execution. In addition, when the protocol for maintaining cache coherency within the cluster is to copy directly from cache to cache, the effect is further enhanced because data is pipeline transferred between caches directly without intervening memory. large. According to the present invention, higher parallelism can be obtained by the conventional parallelizing compiler. Further, when pipeline execution between DO loops is performed, the data can be transferred at high speed. As described above, high-speed calculation can be executed on a parallel computer.

[0011]

EXAMPLE An example of the present invention will be described with reference to FIG.
As shown in the figure, in this embodiment, an original code file 5 in which an original code described in a sequential language is stored, and an automatic parallelizing translation device for converting the original code into a target code for a parallel computer ( Compiler) 7 and automatic parallelizing translation device 7
It has a target code file 6 for storing a target code converted from the original code and a designation information storage unit 4 for storing designation information for designating a processor to which a process is to be assigned in advance. Further, the automatic parallelizing translation device 7
Is a parallel DO loop that can be executed in parallel by a parallel computer and a serial DO that cannot be executed in parallel, as shown in FIG.
A DO loop extraction unit 1 that extracts a loop, a DO loop internal parallelization code creation unit 8 that creates a DO loop internal parallelization code that causes each term in the DO loop to be executed in parallel for the extracted parallel DO loop, and an extraction Inter-DO-loop dependency relationship detection unit 2 that detects the dependency relationship between the generated DO loops
And the parallelized code in the DO loop and the detected DO
D based on the dependency between loops or the specified information
DO loop inter-parallelization code creation unit 3 that creates DO loop inter-parallelization code that enables parallel execution between O loops
And have. In the DO loop parallelization code creating unit 3, the DO loop interdependency detecting unit 2 detects that there is no dependency between each sequential DO loop and the parallel DO loop, as shown in FIG. If
Independent parallel DO loop creation that gives instructions to create dynamic parallelization code between DO loops or static parallelization code between DO loops so that parallel DO loops are executed preferentially at the time of execution and parallel DO loops are executed by the remaining processors Indicator 3
a and the DO loop interdependency detection unit 2, the two DO loops having the data dependency are always equidistant with respect to the subscript (term number) of each iteration (term) of the two loops. When it is detected, equidistant sequential DO loop allocation for instructing the creation of a dynamic parallelization code between DO loops or a static parallelization code between DO loops for executing the pipeline for execution of each term When it is detected that the data dependency is always equidistant between the instruction unit 3b and the two DO loops having the data dependency, the term numbers of the terms of the two loops are detected.
Regarding the processing of each term, an equidistant DO loop allocation instructing section 3c for instructing the creation of a dynamic parallelization code between DO loops or a static parallelization code between DO loops for executing pipeline processing, and a hierarchical type When a plurality of DO loops are pipeline-executed on a parallel computer having a memory, dynamic parallelization code between DO loops or DO loops is assigned so that communication between DO loops is assigned to the same cluster so as not to cross the hierarchy. Hierarchical memory allocation instructing section 3d for instructing the creation of inter-stationary static parallelization code, the independent parallel DO loop allocation instructing section 3a, equidistant sequential DO loop allocation instructing section 3b, equidistant DO loop allocation instructing section 3c and hierarchy. When there is an allocation instruction from the type memory allocation instruction unit 3d, the DO loop parallelization code and the detected DO are detected.
The target code creating section 3e creates an object code on the basis of the dependency between the loops or the specified information read from the specified information storage section 4.

Further, FIG. 8 shows a system configuration diagram of a parallel computer according to the present embodiment in which parallel execution is performed by the object code converted by the automatic parallelizing compiler (translating device). As shown in the figure, in this system, the cache memories 15 ₁₁ b to 15 ₂₄ , which are hierarchical memories, are used.
b is a parallel computer having a main memory device 13 ₁ and 13 ₂ , and is a system in which _two clusters 11 ₁ and 11 ₂ are connected by a network 12. Each of the clusters 11 ₁ and 11 ₂ has processors 15 _{11 a to} 15 _24.
a plurality of pairs 15 _{11-15 24} a and the cache memory 15 ₁₁ b~15 ₂₄ b, all of the processors 16 ₁₁ a to 1
A common main memory 13 ₁ accessible from 5 ₂₄ a,
13 ₂ and. In addition, each of the main storage devices 13 ₁ and 13 ₂
It has schedulers 14 ₁ and 14 ₂ that indicate the usage status of each processor at the time of execution, and storage units 16 ₁ and 16 ₂ that store the target code.

Next, the operation according to this embodiment will be described. As shown in FIG. 6, in step SJ1, the original code written in the sequential language that is the target of the automatic parallelizing translation is read from the original code file 5 and input to the automatic parallelizing translation device (compiler) 7. Then, step S
At J2, the DO loop extraction unit 1 extracts a DO loop. If there is no DO loop in step SJ3, the process ends, and if a DO loop is extracted, step SJ4.
Then, it is judged whether or not the parallel DO loop. Parallel DO
Whether or not it is a loop is determined by checking the data dependence of each term in the DO loop, and when each term is independent, it is determined to be a parallel DO loop. When it is determined in step SJ4 that the DO loop is the parallel DO loop, step SJ
Proceeding to J5, the DO loop parallelization code creating unit 8 creates a parallelization code in the DO loop so that each iteration (term) in the DO loop can be executed in parallel by a plurality of processors. In step SJ6, the equidistant sequential DO loop allocation instructing section 3b of the inter-DO loop parallelization code creating section 3 has a subscript (term number) while there is a data dependency relationship.
Searches for an equidistant sequential DO loop. Step SJ
If there is a sequential DO loop whose subscripts are equidistant in step 7, the object code creating unit 3e creates an object code for pipeline processing according to the instruction in step S15.

On the other hand, the DO extracted in step SJ4
If it is determined that the loop is a sequential DO loop,
In step SJ8, the inter-DO-loop dependency relationship detecting unit 2 searches for a parallel DO loop having no data dependency relationship with the sequential DO loop. If there is a parallel DO loop having no data dependency in step SJ9, the process proceeds to step SJ10, and the independent parallel DO loop allocation instructing section 3 is executed.
In a, the sequential DO loop is preferentially allocated to the processors of the parallel computer, and the parallel DO loops are allocated to the remaining processors. In step SJ9, if there is no parallel DO loop having no dependency, the process proceeds to step SJ11, and the equidistant sequential DO loop allocation instructing section 3b searches for a sequential DO loop whose subscripts (terms) are equidistant, If it is determined in step SJ12 that there is such a sequential DO loop, the process proceeds to step SJ15 to instruct the target code creating unit 3e to perform an allocation process so that the pipeline process is executed.

On the other hand, if it is determined in step SJ12 that there is no sequential DO loop whose subscripts are equidistant, step SJ12.
13, the equidistant DO loop allocation instructing section 3c searches for a parallel DO loop whose subscripts are equidistant, and if there is such a parallel DO loop, then in step SJ15, to the target code creating section 3e, Instruct the execution of pipeline processing. However, in step SJ15,
When the parallel computer has a hierarchical memory, when pipeline execution is realized between the DO loops, the same communication is performed so that communication between both DO loops executed by the pipeline does not cross the hierarchy. Cluster (11 in FIG. 8)
₁ and 11 ₂ ). This enables high-speed pipeline execution. Also, cache coherency within the cluster is maintained (when any processor in the cluster sets numerical data etc., similar numerical data etc. is also set in each cache memory of other processors). Protocol)
In the case of copying directly from cache memory to cache memory, if the amount of data communicated in the pipeline is large enough to fit in cache memory, there is no need to use shared memory directly between cache memories. Since the data is pipeline transferred, the effect is even greater. In the above description, in the case of dynamic scheduling, the object code is created so that allocation is performed according to the number of available processors according to the execution status. An object code for processor allocation is created based on the information from the designated information storage unit 4.

FIG. 7 shows a concrete example in which the original code is converted into the target code by the automatic parallelizing translation device (compiler) 7. A DO loop of the original code is shown in FIG. In this example, as the designation information, for example,
If there are four processors, the number of each processor (0,
1, 2, 3) are set to the variable P. Here, the process means a unit of processing assigned to the processor. FIG. 2B shows an example in which the DO loop parallelization code creation unit 3 creates a DO loop static parallelization code, which is a target code, on the basis of designation information for designating the original code in advance. Show. In this example, four processors will simultaneously perform the following processes. However, since the value of P in each processor is different, DO I = 1,256 is meant for processor φ, and for processor 1,
DO I = 257, 512 ... And so on. On the other hand, FIG. 7C shows a DO parallel dynamic parallelization code which is an object code in the case of dynamic scheduling. In the figure, I is a global variable commonly accessible from all processors, i is a private variable only in each processor, and each processor is
In order to prevent two or more processors performing the processing from fetching the values one by one from the numbers 1 to 256 and putting them in their local variable i, for example, the scheduler When accessing the queue provided in the above, only the processor concerned can access it, and in order to prevent access from other processors and prevent duplicate execution, “LOCK” is performed and When the reading of the
K ”will be released.

An example of processor allocation at the time of execution will be described below with reference to FIGS. In each of these examples, in the original code, each term of the DO loop 1 is a DO loop (Loop) including A (i), and DO i = 1,16 A (i) Each term of the DO loop 2 is B (i). ), Which is represented by DO i = 1,16 B (i), and A (i) and B (i) have no data dependency relationship with each other. Further, for simplicity of explanation, it is assumed that the processing time of each step in the DO loop 1 and the DO loop 2 is equal, and the number of items (steps) of each item (step, iteration) is 16. Further, p0 to p3 indicate each processor forming a parallel computer to be allocated.

FIG. 9A shows a case of a conventional example, in which a DO loop 1 which is a parallel DO loop is divided into respective processors and executed in parallel, and thereafter a D loop which is a sequential DO loop is executed.
A state where the O loop 2 is executed by one processor is shown. In this case, 20 steps are required. FIG. 2B shows a state in which the DO loop 1 that is a parallel DO loop and the DO loop 2 that is a sequential DO loop are executed in parallel. The sequential DO loop 2 is allocated to one processor, and the parallel DO loop 1 is distributed to the remaining three processors and executed in parallel. The number of steps (number of terms) required for the entire processing is 16, which is faster.

In the case of FIG. 10, both the DO loop 1 and the DO loop 2 are sequential DO loops. From the DO loop 1 to the DO loop 2, when the respective subscripts are compared,
The case where there is a data dependency of the distance 0 is shown. in this case,
It allows pipelined execution of two loops. Figure 10
In (a), which corresponds to the conventional example, the DO loop 1 is executed and then the DO loop 2 is executed. In this case, the number of steps required for processing is 32. FIG. 10B shows a state where the DO loop 1 and the DO loop 2 are pipeline-executed. In this case, the number of steps required for processing is 17, which is faster.

In the case of FIG. 11B, the DO loop 1 is a sequential DO loop, the DO loop 2 is a parallel DO loop, and when there is a data dependency from the DO loop 1 to the DO loop 2, In the conventional example, the result is as shown in FIG. 11B, and the number of steps is 20. The number of steps is increased to 17 by executing pipeline execution as in the case of FIG. 10 (FIG. 10B) without performing parallel execution of the DO loop 2. As described above, in this embodiment, the DO loop is processed in parallel as much as possible. Therefore, the number of steps of the processing can be reduced, and the processing can be speeded up. Further, as shown in FIG. 8, in the case of a parallel computer having a hierarchical memory, as described above, when the pipeline execution between the DO loops is realized, both DOs executed in the pipeline are executed. By allocating loops in the same cluster, data communication can be realized without intervening network and high-speed execution becomes possible. If the amount of data communicated in the pipeline is large enough to fit in the cache memory, it can be transferred directly from the cache memory to the other party's cache memory without intervening shared memory, and faster execution is possible. It will be possible. Furthermore, in this embodiment, the original code is converted into the target code not only in the case of static scheduling but also in the case of dynamic scheduling. Therefore, the advantage of each case can be selected according to the case, which is convenient. That is, in static scheduling, it is not necessary to allocate processors at the time of execution, so the time for the processing (overhead) can be omitted, and the processing becomes faster. In addition, the dynamic scheduling is convenient because the compiled program (target code) can operate on a parallel computer with any number of processors.

[0021]

As described above, according to the present invention, when executing a DO loop in a parallel computer, not only between the respective terms in each parallel DO loop but also between the respective DO loops. However, the original code is converted into the target code so that each processor can execute them in parallel as much as possible. Therefore, by reducing the number of processing steps, the processing can be speeded up, the processing time can be reduced, and the processing efficiency of the parallel computer can be improved, so that the parallel computer can be effectively used. Further, in the cases of the first and second inventions, since the parallelization in the case of the dynamic scheduling is performed, the translated program can be operated on the parallel computer having any number of processors. Further, in the case of the third and fourth inventions, since the parallelization in the case of static scheduling is performed, it is not necessary to perform processor allocation at the time of execution, and the processing speed is increased accordingly. .

[Brief description of drawings]

FIG. 1 is a block diagram of the principle of the first invention.

FIG. 2 is a flowchart of the principle of the second invention.

FIG. 3 is a block diagram showing the principle of the third invention.

FIG. 4 is a block diagram of the principle of the fourth invention.

FIG. 5 is a block diagram according to an embodiment.

FIG. 6 is a flowchart according to an embodiment.

FIG. 7 is a diagram showing an example of converting a DO loop code according to the embodiment.

FIG. 8 is a diagram showing a system configuration of a parallel computer according to the embodiment.

FIG. 9 is a diagram (1) showing an allocation example at the time of execution according to the conventional example and the example.

FIG. 10 is a diagram (2) showing an allocation example at the time of execution according to the conventional example and the example.

FIG. 11 is a diagram (3) showing an allocation example at the time of execution according to the conventional example and the example.

FIG. 12 is a block diagram according to a conventional example.

[Explanation of symbols]

 10, 1 DO loop extraction unit 20, 2 DO loop interdependency detection unit 30 DO loop dynamic parallelization code creation unit 31 DO loop static parallelization code creation unit 40 (4) Designated information output unit (designated information Storage unit) 80,8 DO loop in-parallel code creation unit

Claims (10)

[Claims] 1. From an original code written in a sequential language,
A parallel DO loop that can be executed in parallel by a parallel computer and a DO that extracts a serial DO loop that cannot be executed in parallel
A loop extraction unit (10) and an intra-DO loop parallelization code creation unit (80) that creates a DO loop intra-parallelization code that causes each term in the DO loop to be executed in parallel for the extracted parallel DO loop. In an automatic parallelizing translation device for converting the original code into a target code for a parallel computer, DO for detecting a dependency between the extracted DO loops
An inter-loop dependency relationship detection unit (20), and a DO loop inter-movement dynamically enabling parallel execution between the DO loops based on the inter-DO loop parallelization code and the detected inter-DO loop dependency relationship. An automatic parallelizing translation device, comprising: a DO parallel inter-DO loop dynamic parallelizing code creating unit (30) that creates a static parallelizing code. 2. A parallel D capable of inputting an original code described in a sequential language (S1) and executing parallel execution by a parallel computer.
An O loop and a serial DO loop that cannot be executed in parallel are extracted from the original code, and a DO loop parallelization code for executing each term in the DO loop in parallel is created for the extracted parallel DO loop (S2). In this way, in the automatic parallelizing translation method for converting the original code into the target code for the parallel computer, the dependency between the extracted DO loops is detected (S3), and the parallelized code in the DO loop and the detected parallel code are detected. Said DO
An automatic parallelization translation method, characterized in that a dynamic parallelization code between DO loops that dynamically enables parallel execution between DO loops is created (S4) based on the dependency between the loops. 3. From an original code written in a sequential language,
A parallel DO loop that can be executed in parallel by a parallel computer and a DO that extracts a serial DO loop that cannot be executed in parallel
A loop extraction unit (10) and a DO loop internal parallelization code creation unit (80) that creates a DO loop internal parallelization code that causes each term in the DO loop to be executed in parallel for the extracted parallel DO loop. In an automatic parallelizing translation device for converting the original code into a target code for a parallel computer, DO for detecting a dependency between the extracted DO loops
Inter-loop dependency relationship detection unit (20), specified information output unit (40) that outputs specified information that specifies in advance the processor to which the process is allocated, the DO loop parallelization code, and the detected DO loop dependence Statically based on the relationship and the specified information
An automatic parallelizing translation apparatus, comprising: a DO loop static parallelizing code creating unit (31) for creating a DO loop static parallelizing code that enables parallel execution between O loops. 4. A parallel D capable of inputting an original code described in a sequential language (S1) and performing parallel execution by a parallel computer.
By extracting an O loop and a sequential DO loop that cannot be processed in parallel from the original code, and creating an intra-DO loop parallelized code that causes the extracted parallel DO loop to execute in parallel in the DO loop (S2). In an automatic parallelizing translation method for converting a code into a target code for a parallel computer, a dependency between the extracted DO loops is detected (S3), the intra-DO loop parallelizing code, and the detected DO loops are detected. To create a static parallelization code between DO loops that statically executes parallel execution between the DO loops based on the inter-dependency relationship and the designation information that pre-designates the processor to which the process should be allocated (S14). Automatic parallelized translation method characterized by. 5. The inter-DO loop dependency relationship detection unit (2)
When 0) detects that there is no dependency between each sequential DO loop and parallel DO loop, the sequential DO loop is preferentially assigned to the processor at the time of execution, and the parallel DO loop is assigned to the remaining processors. DO loop dynamic parallelization code creation unit (3) that creates the DO loop dynamic parallelization code to be executed or the DO loop static parallelization code
0) or a DO loop static parallelization code generation unit (31), The automatic parallelization translation device according to claim 1 or 3. 6. When it is detected that there is no dependency between each serial DO loop and the parallel DO loop, the serial DO loop is preferentially allocated to the processor at the time of execution,
5. The automatic parallelizing translation method according to claim 2, wherein a dynamic parallelizing code between DO loops or a static parallelizing code between DO loops that causes the remaining processors to execute parallel DO loops is created. 7. The inter-DO loop dependency relationship detection unit (2)
0) detects that the data dependence is always equidistant between the two DO loops having the data dependence, the DO loop dynamic parallelism. The execution code creation unit (30) or the DO loop static parallelization code creation unit (31) executes the DO loop dynamic parallelization code or the DO loop static parallelization code that causes the pipeline to execute for the execution of each term. The automatic parallelizing translation device according to claim 1 or 3, which is created. 8. When processing is performed between two DO loops having a data dependency relationship, it is detected that the data dependency is always equidistant with respect to the item numbers of the respective terms of the two loops. Is a DO that executes pipeline processing
The automatic parallelization translation method according to claim 2 or 4, wherein a dynamic parallelization code between loops or a static parallelization code between DO loops is created. 9. When a plurality of DO loops are pipeline-executed on a parallel computer having a hierarchical memory, D
8. The automatic parallelization translation according to claim 7, wherein the DO loop dynamic parallelization code or the DO loop static parallelization code is created such that the communication between the O loops is assigned to the same cluster so as not to cross the hierarchy. apparatus. 10. When a plurality of DO loops are pipeline-executed on a parallel computer having a hierarchical memory,
9. The automatic parallelization according to claim 8, wherein the DO parallel dynamic parallelization code or the DO loop dynamic parallelization code is created so as to be assigned to the same cluster so that the communication between the DO loops does not cross the hierarchy. How to translate.