JPH11250035A - Editing system and its method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To enable parallelization and vectrization even for a loop jumping out of the loop and to improve execution performance. SOLUTION: An editing device 1 is provided with a syntax analysis part 2 reading a source program, analyzing a syntax and generating an intermediate text, a parallelizing and vectorizing processing part 3 outputting the intermediate text as a parallel intermediate text for executing it in parallel, and a code generation part 4 generating and outputting a target program by using the parallelizing intermediate text. The parallelizing and vectorizing processing part 3 is provided with a structure analysis part 5 analyzing a structure based on the intermediate text, a data depending relation analysis part 6 analyzing whether a contradiction occurs in a definition reference relation on respective variables, a parallelizing and vectorizing text generation part 7 generating the paralleling intermediate text for parallelizing and vectorizing and an effect simulation part 8 predicting and comparing execution time in the case of whole loop scalar and that when parallelizing and vectorizing are executed.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an editing method and method, and more particularly to an editing method and method for jumping out of a loop during editing for creating a target program to be executed on a system having a vector processor and having a multiprocessor. The present invention relates to an editing method and method for vectorizing and parallelizing a loop.

[0002]

2. Description of the Related Art In a conventional editing method and method, for example, disclosed in Japanese Patent Application Laid-Open No. 63-187365, variables defined under an IF statement in a loop are referenced outside the loop. In this case, vectorization is enabled by using a work vector area and a mask.
In this case, only the data dependency of variables defined under the IF statement in the loop is considered as the vectorization hindrance factor. If only the closing price guarantee can be secured, only vectorization is possible. Is what it is. For this reason, there is no consideration for a case in which the variable randomly jumps out of the loop due to the operation result of the variable. In general, there is a search function that searches for an element having a specific value from an arbitrary array, which is considered as a case where there is a jump out of the loop and vectorization is performed.
This usually uses a macro operation function, and this method cannot be used if the prepared case is slightly deviated.

[0003]

The above-mentioned conventional editing method and method, for example, attempt to vectorize a loop in which a macro operation function cannot be used due to irregular jumps out of the loop due to a variable operation result. In this case, there is a problem that the vector operation cannot be used because the loop length cannot be determined. Further, there is also a problem that it is not possible to guarantee the closing value of a variable defined in the loop because it is not possible to know when to exit the loop.

[0004] It is an object of the present invention to provide an editing method and method capable of improving the execution performance by enabling parallelization and vectorization even for a loop having a jump outside the loop.

[0005]

According to the editing method of the present invention, in an editing method for generating and outputting a target program from a source program including a given loop, a source program written in a high-level language is read and analyzed. A syntactic analysis unit that generates an intermediate text, a parallelization vectorization processing unit that creates and outputs a parallelized intermediate text for parallelizing and vectorizing the intermediate text and executing the parallel execution, and using the parallelized intermediate text. And a code generation unit that generates and outputs a target program.

[0006] In the editing method according to the present invention, the parallelization vectorization processing unit may perform a structure analysis based on the intermediate text, and at least one of division, parallelization, and vectorization of the intermediate text. A data dependency analysis unit for analyzing whether or not a definition reference relationship is inconsistent for each variable when one is implemented, and a parallel / vector text generation for generating a parallelized intermediate text for parallelization and vectorization And an effect simulating unit for estimating and comparing the execution time of the case of all loop scalars and the case of performing parallelization and vectorization.

According to the editing method of the present invention, a task specified by the intermediate text and the parallelized intermediate text is executed in parallel in a target program generated by the code generation unit. May be incorporated to suspend other tasks when is not completed.

According to the editing method of the present invention, in an editing method for generating and outputting a target program from a source program including a given loop, an intermediate text is generated by reading and parsing a source program written in a high-level language, Structural analysis is performed based on the intermediate text, and if at least one of division, parallelization, and vectorization is performed on the intermediate text, it is determined whether or not inconsistency occurs in the definition reference relationship for each variable. Analyze, and if the result of the analysis is executable, block the processing for each branch in the loop, and include information including the calculation of the conditional expression of each IF statement for generating a vectorized text and mask for each block. Create text to be collected, predict the effect of using parallelized and vectorized text, and use the Is expected, a parallelized intermediate text for executing each text in parallel is created, and the parallelized intermediate text and the intermediate text for executing the entire loop in scalar are executed in parallel. At the time of termination, a target program incorporating an instruction to suspend another task when the other task is not terminated is generated.

[Operation] The effect simulating unit of the present invention comprises:
When performing parallelization and vectorization processing, in order to prevent that it becomes slower than scalar processing by itself, despite division, due to overhead of necessary preparation and post-processing, etc. Simulate the execution time at the loop length (if you did not jump out of the loop to the end)
Compare with the scalar case by itself. The present invention can improve the C performance even when the execution performance is not improved as compared with the conventional method.
This is to reduce the risk of wasteful use of assets such as PUs and storage areas.

In addition to the code for parallelization and vectorization, a scalar code for the entire loop is embedded in the target program, and the shorter processing time is adopted. This occurs at a very early stage, and the code that executes the entire loop with a scalar may have a shorter processing time, thereby preventing performance degradation due to this. Therefore, the effect simulation unit is not always necessary if the system can close eyes on wasteful use of assets.

[0011]

Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing a first embodiment of the present invention.

The editing apparatus 1 according to the present invention reads a source program written in a high-level language, performs a syntax analysis, and generates an intermediate text, and a parallelizing and vectorizing the intermediate text for parallel execution. Parallelization vectorization processing unit 3 that creates and outputs parallelized intermediate text
And a code generation unit 4 that generates and outputs a target program using the parallelized intermediate text.

The parallelized vectorization processing unit 3 performs a structure analysis unit 5 for performing a structure analysis based on the intermediate text, and performs at least one of division, parallelization, and vectorization on the intermediate text. In this case, for each variable, a data dependency analysis unit 6 that analyzes whether or not a contradiction occurs in the definition reference relationship, and a parallel / vector text generation unit 7 that generates a parallelized intermediate text for parallelization and vectorization And an effect simulating unit 8 for predicting and comparing the execution time of the case of all loop scalars and the case of performing parallelization and vectorization.

FIG. 2 is an explanatory diagram for explaining a basic form of a source program for which application of the present invention is expected. The number of branches may be any number, but here, two is set for easy understanding.

FIG. 3 is a flowchart showing the flow of processing in the parallelized vectorization processing section. The description will be given using the names and reference numerals in FIG. 1 and according to the connection in FIG. 1 and the flow in FIG.

First, the editing device 1 reads a source program. When the source program is read, the parsing unit 2 generates an intermediate text. Next, step (hereinafter S
This information is passed to the parallelization vectorization processing unit 3 at 1). In the parallelization vectorization processing unit 3, the structure analysis unit 5 performs the structure analysis based on the intermediate text in S2, the data dependency analysis unit 6 performs the data dependency analysis in S3, and performs parallelization and It is determined whether vectorization can be applied. In the vectorization analysis, an IF statement having a branch to the outside of the loop is treated as a statement that cannot be vectorized, and this fact alone does not constitute a non-vectorizable factor for the entire loop. At the stage where the parallelization becomes impossible, it is determined that the vectorization to the entire loop cannot be performed. The analysis target of the parallelization is a process α, a process β, a process γ, and a portion necessary for generating a mask such as a conditional branch between them (see FIG. 2). Further, the processes α, β, and γ do not necessarily have to be all vectorized. If division is possible, neither a partial vector nor a scalar is a reason not to parallelize.
If parallelization and vectorization are not possible by the analysis in the previous step S4, the process exits the parallelization vectorization processing unit 3 and, based on the intermediate text created by the syntax analysis unit 2, the entire loop is a scalar only. Become a purpose program. If parallelization and vectorization are possible, the process proceeds to the parallel / vector text generation unit 7, and in S5, an intermediate text for parallelization vectorization is created for the following. (1) Preparation for parallelization and vectorization (2) Data collection for mask creation (calculation of conditional expressions,
Subscript formula calculation. etc) (3) Processing α (4) Processing β (5) Processing γ (6) Creation of a mask for variables requiring storage (7) Post-processing for parallelization and vectorization. (Mainly store processing with a mask) At this time, (2) to (5) are arranged in parallel. Therefore, variables stored during these processes are stored in the work area so as not to directly change the storage area of the variables. The actual storage in the storage area is performed using the mask created in (6) during the processing of (7). (2) are all scalar instructions.

FIG. 4 is an explanatory diagram for explaining the execution state of the target program. Although the description of FIG. 4 is not made here, it is only mentioned that it shows the execution state of parallelization and vectorization currently being described. The content is the content of the process assigned to each of the processors 11, 12, 13, 14, and 15 when the source program becomes the target program by the means of the present invention.

When the processing in the parallel / vector text generation section 7 is completed, the processing shifts to the effect simulation section 8. Since vectorization is originally effective as the loop length becomes longer, the most effective method in this case is a case in which the loop is not jumped out to the end. Even in this ideal state, if the number of processes is small or the overhead is too large, parallelization and vectorization may become meaningless. If it is found that the data is wasteful, it is better not to perform parallelization and vectorization. Therefore, the effect simulating unit 8 calculates the cost (execution time) required for parallelization and vectorization in S6,
Simulate the cost of a scalar over the entire loop and compare the results. For the reasons already explained, it is assumed that the simulation did not jump out of the loop until the end. The cost of parallelization and vectorization is the addition of the following costs. (1) Preparation for parallelization and vectorization (2) The following items with the highest cost. Since the following items are processed in parallel, it is necessary to synchronize, and the highest cost becomes the total cost. -Data collection for mask creation (conditional expression calculation, subscript expression calculation. Etc)-Processing α-Processing β-Processing γ (3) Creation of masks for variables requiring storage (4) Parallelization and vectorization For post-processing. The processing for interrupting the processing of the processor 15 shown in FIG. 4 does not need to be included in the calculation. This part is also embedded at the end of the scalar processing code. In the case of the scalar, the processing of the processors 11 to 14 is interrupted.

In S7, the expected cost calculated by the above means is compared with the expected cost of the scalar. If the cost of the scalar is lower, the processing exits the parallelization vectorization processing unit 3, and
On the basis of the intermediate text created by the parsing unit 2, the entire loop becomes a scalar-only target program. If the scalar is more expensive, use the parallelized intermediate text created by the means of the present invention.

If an effect can be expected by using the present invention, a new intermediate code is embedded in the existing intermediate code in step S8. At the end of the text when the entire loop is a scalar, text that interrupts the processing of the other party is added.

[0022]

Next, an embodiment of the present invention will be described with reference to the drawings. Here, a description will be given of how the target program created using this method is executed on a system to which the target program is applied.

FIG. 5 is an explanatory diagram for explaining a source program used in the embodiment of the present invention, and FIG. 6 is an explanatory diagram for explaining processing contents of respective processors which perform parallel processing when the source program is edited into a target program. It is.

In this example, since the processes α, β, and γ do not have any vectorization inhibiting factors, all vectors can be obtained. Since “n = n + 1” is required for both processing γ and data collection for mask creation, the calculation is performed by either of the processors 11 and 14. However, since the processor 11 is a scalar and the processor 14 is a vector, the result of the processor 14 is not used in the store processing after synchronization, but the result of the processor 11 is stored. This does not change even if all the processors 14 perform scalar processing. The processing performed by the processor 14 is,
The operation is performed assuming that there is no branch outside the loop. Even if the operation is a scalar operation, it is necessary to store the result based on the mask created from the operation result of the processor 11 in order to use the result. There is.

It1, it2 in the processor 11
it3 indicates the number of executions of the processes α, β, and γ, respectively.

After all the operations of the processors 11 to 14 are completed, the mask is obtained by the result of the processor 11, the initial value, the final value, the increment value of the loop, and, in the case of an array, the subscript expression. If it1 = it2 = x, it3 = x-1, the masks for variables in each process are as follows. Data collection for mask creation

Open mouth processor 2 processing α

Processor 3 processing β

If k is not constant during the loop but is calculated in the process β, the value of k is calculated not only by the processor 3 but also by the processor 11. Port processor 4 processing γ

If the variable "s" is vectorized,
Used as if it were an array. When storing, the last on element of the mask is stored as the closing value.

At the stage when these masks have been created,
The operation of the entire loop scalar processing (if the processor 15 in FIG. 4 is not completed, this operation is interrupted. Since the processing of the processor 5 is the same as the conventional processing method, the store here is the actual processing). However, there is no problem since it is overwritten by a store process with a mask (post-processing for parallelization and vectorization).

Conversely, if the processing of the processor 15 is completed before the mask is completed, the processors 11 to 14
Is interrupted and these processes are not performed. As described above, the operation results by the processors 11 to 14 are not yet stored in the actual storage area at this stage.
No problem.

In the final post-processing for parallelization and vectorization, a store with a mask is provided for an array, and a close value is guaranteed for a variable using a mask. The result of the processing by the processor 11 is always stored as it is. Processor 12
As for 14, stores are performed in the order of execution. Array "a"
Is defined by the processing α and the processing γ, the store with mask is performed in the order of the result of the processor 12 and the result of the processor 14.

[0034]

As described above, according to the present invention, a source program written in a high-level language is read and parsed to generate an intermediate text, and a structural analysis is performed based on the intermediate text. If at least one of the division, parallelization, and vectorization is performed, it is analyzed whether or not a contradiction occurs in the definition reference relation for each variable. If the result of this analysis is feasible, a loop is executed. Processing is blocked for each branch of each IF, and each IF is used to generate a text and mask by vectorizing each block.
Create a text that collects information including the calculation of the conditional expression of the sentence, predict the effect of using the parallelized and vectorized text, and if the effect of the prediction is expected, parallel each text Create parallelized intermediate text to be executed, execute the parallelized intermediate text and the intermediate text to execute the entire loop in scalar in parallel. By generating a target program in which an instruction for interrupting a task is incorporated, it is possible to parallelize and vectorize even a loop having a jump outside the loop, thereby improving the execution performance. .

[Brief description of the drawings]

FIG. 1 is a block diagram showing a first embodiment of the present invention.

FIG. 2 is an explanatory diagram illustrating a basic form of a source program for which application of the present invention is predicted.

FIG. 3 is a flowchart showing a flow of processing in a parallelization vectorization processing unit.

FIG. 4 is an explanatory diagram illustrating an execution state of a target program.

FIG. 5 is an explanatory diagram illustrating a source program used in the embodiment of the present invention.

FIG. 6 is an explanatory diagram illustrating processing contents of each processor that performs parallel processing when a source program is edited into a target program.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Editing device 2 Syntax analysis part 3 Parallelization vectorization processing part 4 Code generation part 5 Structure analysis part 6 Data dependence analysis part 7 Parallel / vector text generation part 8 Effect simulation part 11, 12, 13, 14, 15 Processor

Claims (4)

[Claims] 1. An editing system for generating and outputting a target program from a source program including a given loop, wherein the parsing unit reads a source program written in a high-level language and performs a syntax analysis to generate an intermediate text;
A parallelization vectorization processing unit for creating and outputting a parallelized intermediate text for parallelizing and vectorizing the intermediate text for parallel execution, and a code generation for generating and outputting a target program using the parallelized intermediate text And an editing method comprising: 2. The parallelized vectorization processing unit performs a structure analysis unit that performs a structure analysis based on an intermediate text, and performs at least one of division, parallelization, and vectorization on the intermediate text. A data dependency analysis unit for analyzing whether or not a contradiction occurs in the definition reference relationship for each variable, a parallel / vector text generation unit for generating a parallelized intermediate text for parallelization and vectorization, and a full loop 2. The editing method according to claim 1, further comprising an effect simulating unit for estimating and comparing execution times between the case of scalar and the case of parallelization and vectorization. 3. The target program generated by the code generation unit includes a task specified by the intermediate text and the parallelized intermediate text, which is executed in parallel, and each task is terminated when its own task ends. 2. The editing method according to claim 1, wherein an instruction for interrupting another task when there is no other task is incorporated. 4. An editing method for generating and outputting a target program from a source program including a given loop, reading a source program written in a high-level language, performing syntax analysis, generating an intermediate text, and using the intermediate text as a basis. And analyzing whether or not inconsistency occurs in the definition reference relationship for each variable when at least one of division, parallelization, and vectorization is performed on the intermediate text. If the result is executable, the process is blocked for each branch in the loop, and the text for which information collection including the calculation of the conditional expression of each IF statement for generating a mask and the text for each block is generated. Create, predict the effect of using parallelized and vectorized text, and if the prediction results show an effect, Creates a parallelized intermediate text that causes each text to be executed in parallel, executes this parallelized intermediate text and the intermediate text that causes the entire loop to be executed by a scalar in parallel, and allows each task to execute other tasks at the end of its own task. An editing method characterized by generating a target program incorporating an instruction for interrupting another task when not finished.