JPH05341966A - Optimizing system for built-in m-system random number generating function - Google Patents

Abstract

PURPOSE:To accelerate the generating processing speed of an M-system random number and the execution speed of a generated object program in an optimizing system for the compiler of a computer system provided with a vector computing function. CONSTITUTION:A built-in random number generating function detecting means 6 detects an intermediate text in accordance with the innermost side loop including a built-in M-system random number generating function, and a deformable text detecting means 7 decides whether or not the intermediate text detected by the built-in random number generating function detecting means 6 can be deformed. A text deformation means 9 generates the M-system random number of the intermediate text in accordance with the innermost side loop whose generating number is decided statically just before the innermost side loop by a vector arithmetic operation comprehensively, and performs deformation in such a manner that the processing of the innermost side loop is performed by using a generated M-system random number.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an optimization technique for a compiler in an electronic computer system having a vector operation function, and more particularly to an M sequence for optimizing an M sequence random number generating built-in function existing in an innermost loop. It relates to an optimization method of a random number generation built-in function.

[0002]

2. Description of the Related Art Conventionally, in a compiler of an electronic computer system having a vector operation function, the M-sequence random number generating built-in function in the innermost loop has been vectorized. Since the M-series random number generating built-in function is vectorized in the innermost loop, vectorization can be performed only when the number of M-series random number generating built-in functions existing in the innermost loop is one. It was

For example, as shown in FIG. 3, in the case of an innermost loop having two M-sequence random number generation built-in functions RANDM1 (), A (1), A (2), ..., A (100
The value of 0) is the M-sequence random number generation built-in function RANDM1
() Is determined by the values of the first, third, ..., 1999th generated random numbers, and C (1), C (2),
The value of C (1000) is determined by the value of the second, fourth, ..., 2000th generated random number. However, if the M-sequence random number generation built-in function RANDM1 () is vectorized in the innermost loop, A (1), A
The values of (2), ..., A (1000) are the first, second, ..., Of the M-sequence random number generation built-in function RANDM1 ().
Determined by the value of the 1000th generated random number, C
The values of (1), C (2), ..., C (1000) are the 100th.
It is determined by the value of the first, 1002, ..., 2000th generated random numbers, and the processing result differs depending on whether the vectorization is performed or not.

[0004]

As described above, the conventional compiler can perform vectorization only when the number of M-sequence random number generating built-in functions existing in the innermost loop is one. When there are a plurality of M-sequence random number generation built-in functions in the innermost loop, there is a problem that it takes a lot of time to generate the M-sequence random number.

Further, when the target program generated by the conventional compiler is executed, the M-sequence random number is generated by the scalar operation in the innermost loop including a plurality of M-sequence random number generating built-in functions. There was also a problem that the execution speed of was slow.

An object of the present invention is to provide a plurality of M in the innermost loop.
Even if there is a built-in random number generation function,
An object of the present invention is to provide an optimization method of a random number generation built-in function that can generate random numbers at high speed and can increase the execution speed of an object program.

[0007]

In order to achieve the above object, the present invention provides (A) a text generating means for generating an intermediate text group from a source program in a compiler of an electronic computer system having a vector operation function, Innermost loop text detecting means for detecting an intermediate text corresponding to the innermost loop from the intermediate text group generated by the text generating means, and intermediate text corresponding to the innermost loop detected by the innermost loop text detecting means A random number generating built-in function detecting means for determining whether or not the M-sequence random number generating built-in function is included, and the innermost side determined by the random number generating built-in function detecting means to include the M-sequence random number generating built-in function. The intermediate text corresponding to the loop is set by vector operation of the M-sequence random number immediately before the innermost loop. The deformable text detecting means for determining whether or not it is possible to deform so as to occur, and the repeat count of the innermost loop corresponding to the intermediate text determined to be deformable by the deformable text detecting means is static. The number of occurrences of the M-series random number in the innermost loop is determined, and the number of occurrences is larger than the maximum value of the number of times that the processing speed is faster when the intermediate text is not transformed. Thus, the intermediate text corresponding to the innermost loop is generated collectively by vector operation of M-sequence random numbers immediately before the innermost loop, and the processing in the innermost loop is performed immediately before the innermost loop. A target program is created by using a text transforming means for transforming the generated M-sequence random number and an intermediate text group transformed by the text transforming means. It is provided with a the object program generating means for forming.

Further, in order to achieve the above object, the present invention provides:
(B) In a compiler of an electronic computer system having a vector operation function, it corresponds to a text generating means for generating an intermediate text group from a source program and an innermost loop from the intermediate text group generated by the text generating means. Innermost loop text detecting means for detecting intermediate text, and random number generation for determining whether or not the intermediate text corresponding to the innermost loop detected by the innermost loop text detecting means includes an M-sequence random number generating built-in function The built-in function detecting means and the intermediate text corresponding to the innermost loop determined to include the M-series random number generating built-in function by the random number generating built-in function detecting means are M-series random numbers immediately before the innermost loop. Transformable to determine whether or not it can be transformed by batch operation by vector operation When the number of iterations of the innermost loop corresponding to the intermediate text determined to be deformable by the text detecting means and the deformable text detecting means is determined at the time of execution of the program, the intermediate text corresponding to the innermost loop is set. If the number of generated M-series random numbers determined when the program is executed is greater than the maximum value of the number of times that processing speed is faster if the intermediate text is not transformed, vector calculation of the M-series random numbers is performed immediately before the innermost loop. , And then the processing in the innermost loop is performed using the M-series random number generated immediately before the innermost loop, and the number of generated M-series random numbers determined when the program is executed is the intermediate text. If the number is less than the maximum value, the processing speed will be faster if the transformation is not performed. And preparative deforming means is obtained by providing the object program generating means for generating a target program using an intermediate text group having undergone deformation in the text deforming means.

[0009]

In the configuration (A), the text generating means generates the intermediate text group from the source program, and the innermost loop text detecting means detects the intermediate text corresponding to the innermost loop.

Thereafter, the innermost loop including the M-series random number generating built-in function is detected by the random number generating built-in function detecting means, and whether the innermost loop including the M-series random number generating built-in function is deformable by the deformable text detecting means. Is determined.

The number of iterations of the innermost loop determined to be deformable is statically determined, and the number of M-series random numbers generated in the innermost loop is higher than the number of times when the intermediate text is not deformed. Is greater than the maximum value of
By the text transforming means, the intermediate text corresponding to the innermost loop causes the M-sequence random numbers to be collectively generated by vector operation immediately before the innermost loop, and the processing in the innermost loop occurs immediately before that. It is transformed so as to be performed using the generated M-sequence random number.

Then, the target program generating means generates the target program by using the transformed intermediate text group.

In the configuration of (B), when the number of repetitions of the innermost loop determined to be deformable by the deformable text detecting means is determined at the time of execution of the program, the text deforming means causes the innermost loop. In the intermediate text corresponding to the loop, if the number of M-series random numbers generated at the time of execution of the program is greater than the maximum value of the processing speed that is faster if the intermediate text is not transformed, then immediately before the innermost loop. Then, the M-series random numbers are collectively generated by a vector operation, and then the processing in the innermost loop is performed using the M-series random number generated immediately before the innermost loop to determine the M
If the number of generated sequence random numbers is less than or equal to the maximum value of the number of times that the processing speed is faster when the intermediate text is not transformed, the processing is performed as it is.

[0014]

Embodiments of the present invention will now be described in detail with reference to the drawings.

FIG. 1 is a block diagram of an embodiment of the present invention. A compiler 2 for compiling a source program 1 to generate an object program 12 is a text generating means 3.
, Innermost loop text detecting means 5, random number generating built-in function detecting means 6, and deformable text detecting means 7
A loop repetition number determination detection means 8, first and second
It is composed of the text transforming means 9 and 10 and the object program generating means 11.

The text generation means 3 is the source program 1
Has a function of parsing and generating the intermediate text group 4.

The innermost loop text detecting means 5 has a function of searching the intermediate text group 4 for an intermediate text corresponding to the innermost loop.

Based on the intermediate text corresponding to the innermost loop detected by the innermost loop text detecting means 5, the random number generating built-in function detecting means 6 determines whether or not the M-sequence random number generating built-in function exists in the innermost loop. It has a function to judge.

The deformable text detecting means 7 detects the presence of the M-sequence random number generating built-in function by the random number generating built-in function detecting means 6, and the intermediate text corresponding to the innermost loop is the first and second text changing means 9, It has a function of determining whether or not the transformation by 10 is possible.

The loop repeat count determination detecting means 8 determines whether the repeat count of the innermost loop determined to be deformable by the deformable text detecting means 7 is statically determined or is determined when the program is executed. judge.

The first text transforming means 9 is the number of M-series random numbers generated by the M-series random number generating built-in function in the innermost loop in which the loop repetition count judgment detecting means 8 judges that the repetition count is statically determined. A function of obtaining N and a threshold value S in which the number N is predetermined (immediately before the innermost loop, a random number generation process is performed rather than deformed so that the M-sequence random numbers are collectively generated by a vector operation. It is a maximum value of the number of generated random numbers that shortens the time, and a function of determining whether it is larger than a value obtained by actual measurement, and if the number N is larger than a threshold value S, an intermediate value corresponding to the innermost loop It has a function of transforming the text so as to perform the process in the innermost loop by using the M-series random number generated collectively by the vector operation immediately before the innermost loop.

The second text transforming means 10 outputs the intermediate text corresponding to the innermost loop, which is determined by the loop repeat count determination detecting means 8 as not having a static repeat count.
Number of generated M-series random numbers N'determined when the program is executed
Is larger than the threshold value S, the processing in the innermost loop is performed by using the M-series random number generated collectively by the vector operation immediately before the innermost loop. If the number N ′ is equal to or smaller than the threshold value S, the original It has the function of transforming the processing in the innermost loop as it is.

The target program generating means 11 has a function of generating the target program 12 based on the intermediate text group 4.

FIG. 2 is a flowchart showing a processing example of the compiler 2. The operation of this embodiment will be described below with reference to the drawings.

Referring to step a, the text generation means 3 of the compiler 2 parses the source program 1 and generates an intermediate text group 4.

Referring to steps b to e, the innermost loop text detecting means 5 checks the intermediate texts in the intermediate text group 4 in the order in which they were generated, and detects the intermediate texts corresponding to the innermost loop, thereby performing control. It is passed to the random number generation built-in function detecting means 6.

Referring to steps f and g, the random number generating built-in function detecting means 6 to which the control is passed is set to the innermost loop based on the intermediate text corresponding to the innermost loop detected by the innermost loop text detecting means 5. It is determined whether or not the M-sequence random number generation built-in function is included, and if it is not included, the control is returned to the innermost loop text detecting means 5, and if it is included, the deformable text detecting means 7 is included.
Pass control to.

When the innermost loop text detecting means 5 is returned to the control, it carries out the above-mentioned steps b to e.

Referring to steps h and i, the deformable text detecting means 7 to which the control is passed is the first innermost loop which is judged by the random number generating built-in function detecting means 6 to include the M-sequence random number generating built-in function. , It is determined whether or not the transformation by the second text transforming means 9 and 10 is possible. If it is not transformable, the control is returned to the innermost loop text detecting means 5, and if it is transformable, the control is determined by the number of loop iterations. It is passed to the detection means 8.

Here, the transformable text detecting means 7 is
There is a fear that the number of iterations may not reach the number specified by the DO statement, such as the innermost loop that contains a conditional branch instruction or the innermost loop that is the branch destination of a branch instruction that exists in another part. The inner loop is determined to be the undeformable innermost loop.

That is, the first and second text transforming means 9,
In 10, the intermediate text corresponding to the innermost loop is transformed so as to be processed in the innermost loop by using the M-series random number generated collectively by the vector operation immediately before the innermost loop. If the above-mentioned transformation is performed on the intermediate text corresponding to the innermost loop whose number of repetitions does not reach the number designated by the DO statement, the pre-transformation processing and the post-transformation processing have different meanings. Is.

Referring to steps j and k, the loop repeat count judgment detecting means 8 to which the control is passed determines whether or not the repeat count of the innermost loop judged to be deformable by the deformable text detecting means 7 is statically determined. If it is determined that it is statically determined, control is passed to the first text transformation means 9, and if it is determined that it is not statically determined, that is, if it is determined that it is determined when the program is executed, the second text Control is passed to the deforming means 10.

Referring to step l, the first text transforming means 9 to which the control is passed is first in the innermost loop where the loop iteration number decision detecting means 8 decides that the iteration number is statically determined. Then, the number N of M-series random numbers generated by the M-series random number generation built-in function is obtained.

Next, the first text transforming means 9 compares the number N with a predetermined threshold value S. When the number N is larger than the threshold value S, the intermediate text corresponding to the innermost loop is collectively generated by vector operation for the number of M-sequence random numbers specified immediately before the innermost loop, After the processing in the inner loop is modified so as to be performed by using the generated M-sequence random number, the control is returned to the innermost loop text detecting means 5, and the number N is the threshold value S.
In the following cases, control is returned to the innermost loop text detecting means 5 without performing transformation of the intermediate text.

Now, for example, if the intermediate text of the innermost loop portion to be transformed corresponds to the source program shown in FIG. 3, the first text transforming means 9 transforms the intermediate text to be transformed into, for example, It is transformed into an intermediate text corresponding to the source program shown in FIG.

The CALL RAMDM2 (TEM shown in FIG.
P, 2000) collectively generates the number (2000) of M-series random numbers designated by the second parameter of the actual argument by vector operation, and the generated M-series random numbers have the number of elements designated by the first parameter. 2 x 1000 2
Built-in subroutine RA to set in the three-dimensional array TEMP
It is a CALL statement that calls MDM2. Here, the two-dimensional array TEMP having the number of elements of 2 × 1000 is set as the first parameter of the actual argument, and the second parameter is set as 2000. In the example of FIG. The innermost loop repeats 1000 times, and the M-series random number generating built-in function RA existing in the innermost loop
This is because the number of NDM1 () is 2 and the number of M-sequence random numbers generated in the innermost loop is 2000.

Further, in FIG. 4, the portion of the M-sequence random number generating built-in function RANDM1 () in the innermost loop in FIG. 3 is replaced with the reference of the two-dimensional array TEMP.

That is, the source program of FIG.
Immediately before the innermost loop, 2000 M-series random numbers are collectively generated by vector operation, then the generated 2000 M-series random numbers are set in a two-dimensional array TEMP. Processing of two-dimensional array TE
It is performed by referring to MP to obtain the values of A (1) to A (1000) and C (1) to C (1000). At that time, the values of A (1) to (A (1000) are the two-dimensional array T.
Obtained using EMP (1,1) to TEMP (1,1000), the values of C (1) to C (1000) are two-dimensional array TE.
Since it is obtained using MP (2,1) to TEMP (2,1000), it is possible to obtain the same processing result when vectorized as when not vectorized.

As described above, by collectively generating the M-series random numbers by the vector operation, the generation speed of the M-series random numbers can be increased. Further, by replacing the M-sequence random number generation built-in function RANDM1 () in the innermost loop with a reference of the two-dimensional array TEMP and eliminating the processing using the M-sequence random number generation built-in function RANDM1 () in the innermost loop, It is possible to increase the program execution speed. That is, when the M-series random number generation built-in function RANDM1 () in the innermost loop is replaced with an array reference, the M-series random number generation built-in function RA
The process of saving the value of each register at that time, which is necessary when executing NDM1 () to generate the M-sequence random number, and the process of restoring the value saved in the memory to each register are unnecessary. Because.

Further, referring to step m, the second text transforming means 10 to which the control is passed receives the control, and the loop repeat count determination detecting means 8 determines that the repeat count is not statically determined. If the number N ′ of generated M-series random numbers determined when the program is executed is larger than the threshold value S, the text is stored in the innermost loop by using the M-series random numbers collectively generated by vector operation immediately before the innermost loop. When the number N ′ is equal to or smaller than the threshold value S, the process is modified so that the process in the innermost loop is performed as it is, and then the control is returned to the innermost loop text detecting means 5.

Now, for example, assuming that the intermediate text of the innermost loop portion to be transformed corresponds to the source program shown in FIG. 5, the second text transforming means 10 transforms the intermediate text to be transformed into, for example, It is transformed into an intermediate text corresponding to the source program shown in FIG.

In the source program of FIG. 6, RAM
DM2 is the name of a built-in subroutine that generates the number of M-series random numbers specified by the second parameter of the actual argument and sets the generated M-series random number in the array specified by the first parameter of the actual argument. Further, the built-in subroutine having the subroutine name RAMDM2 is for generating M-sequence random numbers by vector processing.

In the case of this example, the number of iterations of the innermost loop designated by the DO statement is K times, as shown in FIG.
Since the number of M-sequence random number generation built-in functions RANDM1 () existing in the innermost loop is 2, and the number of M-sequence random number generations is 2 × K, as shown in FIG. The two-dimensional array TEMP having the number of elements of 2 × K is set in one parameter, and 2 × K is set in the second parameter.

That is, the source program shown in FIG.
Number of generated M-series random numbers determined when the program is executed (2
XK) is larger than the threshold value S described above, a process of collectively generating 2 × K M-sequence random numbers by vector operation immediately before the innermost loop, and the generated 2 × K M-sequences A process for setting a random number in the two-dimensional array TEMP,
The process of obtaining A (I) and C (I) is sequentially performed by referring to the two-dimensional array TEMP. If the threshold value is S or less, A (I), using the M-sequence random number generation built-in function RANDM1 (),
The processing for obtaining C (I) is performed.

When the processing of the first and second text transforming means 9 and 10 is completed, the control is returned to the innermost loop text detecting means 5.

Referring to steps b and c, the innermost loop detecting means 5 which is returned to the control extracts the intermediate text from the intermediate text group 4 and there is an intermediate text which has not been extracted (when step c is yes). Passes control to the random number generating built-in function detecting means 6 and passes control to the object program generating means 11 when all intermediate texts are taken out (when step c is no).

Referring to step o, the target program generating means 11 to which the control is passed generates the target program 12 based on the intermediate text group 4. At that time, if the innermost loop in which the M-series random number generating built-in function part is replaced by the array reference by the first and second text transforming means 9 and 10 is vectorizable, the object program generating means 11 Vectorize.

[0048]

As described above, according to the present invention, the intermediate text corresponding to the innermost loop including the M-series random number generating built-in function is collected by the vector operation of the M-series random numbers immediately before the innermost loop. The M-sequence random number generation built-in function is provided in the innermost loop because the process in the innermost loop is performed using the M-sequence random number generated immediately before the innermost loop. Even if there are a plurality of them, they can be vectorized, and there is an effect that the generation processing speed of the M-series random number can be improved, and
There is an effect that the execution speed of the target program can be improved.

[Brief description of drawings]

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

FIG. 2 is a flowchart illustrating a processing example of an embodiment.

FIG. 3 is a diagram showing an example of a source program.

FIG. 4 is a diagram showing an example of a source program that makes the source program of FIG. 3 equivalent by optimization.

FIG. 5 is a diagram showing an example of a source program.

FIG. 6 is a diagram showing an example of a source program that makes the source program of FIG. 5 equivalent by optimization.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ... Source program 2 ... Compiler 3 ... Text generation means 4 ... Intermediate text group 5 ... Inner loop text detection means 6 ... Random number generation built-in function detection means 7 ... Deformable text detection means 8 ... Loop repetition number determination detection means 9 ... First text transforming means 10 ... Second text transforming means 11 ... Objective program generating means 12 ... Objective program

Claims (2)

[Claims] 1. In a compiler of an electronic computer system having a vector operation function, a text generating means for generating an intermediate text group from a source program, and an intermediate inner text loop from the intermediate text group generated by the text generating means. An innermost loop text detecting means for detecting the corresponding intermediate text, and it is determined whether the intermediate text corresponding to the innermost loop detected by the innermost loop text detecting means includes an M-sequence random number generating built-in function. The random number generating built-in function detecting means and the intermediate text corresponding to the innermost loop determined to include the M-series random number generating built-in function by the random number generating built-in function detecting means are set to M immediately before the innermost loop.
Deformable text detecting means for determining whether or not it is possible to transform the sequence random numbers so that they can be generated collectively by vector operation, and the maximum corresponding to the intermediate text determined by the transformable text detecting means to be transformable. When the number of iterations of the inner loop is statically determined, M in the innermost loop
The number of generated sequence random numbers is obtained, and the generated number is larger than the maximum value of the number of times that the processing speed is faster if the intermediate text is not transformed. Therefore, the intermediate text corresponding to the innermost loop is set to the innermost loop. Immediately before, the M-series random number is collectively generated by a vector operation, and the text is transformed such that the process in the innermost loop is performed by using the M-series random number generated immediately before the innermost loop. A method for optimizing an M-sequence random number generation built-in function, comprising: means and a target program generating means for generating a target program using the intermediate text group transformed by the text transforming means. 2. In a compiler of an electronic computer system having a vector operation function, a text generating means for generating an intermediate text group from a source program, and an innermost loop from the intermediate text group generated by the text generating means. An innermost loop text detecting means for detecting the corresponding intermediate text, and it is determined whether the intermediate text corresponding to the innermost loop detected by the innermost loop text detecting means includes an M-sequence random number generating built-in function. The random number generating built-in function detecting means and the intermediate text corresponding to the innermost loop determined to include the M-series random number generating built-in function by the random number generating built-in function detecting means are set to M immediately before the innermost loop.
Deformable text detecting means for determining whether or not it is possible to transform the sequence random numbers so that they can be generated collectively by vector operation, and the maximum corresponding to the intermediate text determined by the transformable text detecting means to be transformable. When the number of iterations of the inner loop is determined at the time of execution of the program, the processing speed of the intermediate text corresponding to the innermost loop is higher when the number of M-sequence random numbers determined at the time of execution of the program does not transform the intermediate text. If the number is faster than the maximum value of the number, the M-sequence random numbers are generated collectively by vector operation immediately before the innermost loop, and then the processing in the innermost loop is performed immediately before the innermost loop. The generated M-sequence random number is used to transform the intermediate text depending on the number of M-sequence random numbers generated when the program is executed. If it is less than the maximum value of the number that the processing speed becomes faster if it is not, the target program using the text transforming means for transforming to perform the original processing and the intermediate text group transformed by the text transforming means A method for optimizing an M-series random number generation built-in function, comprising: