Optimizing Compiler Which Generates Multiple Instruction Streams to Be Executed in Parallel

The present invention relates to compiler systems of electronic computer systems having parallel processors that execute two or more procedures in parallel, and more particularly to a parallel execution system related to the optimization of object programs.

When a plurality of different objects can be produced using a plurality of algorithms for a certain portion of a source program and it cannot be determined beforehand which of the objects can be executed in a minimum time, the compiler selects one of the objects on the basis of an arbitrary criterion or the user is asked to select one of the objects with an optional directive. However, problems exist in that objects produced by the conventional techniques sometimes cannot be executed with optimal algorithms.

It is therefore an object of the present invention to provide a parallel execution system which will execute in all cases by using the optimal algorithm.

According to the present invention, a parallel execution system is provided in regards to a compiler which produces and supplies an object program from a given source program to an electronic computer system.

In the computer system with parallel processors capable of executing two or more procedures in parallel, the compiler is comprised of: a syntax analysis unit for interpreting the statement of the source program and translating into the intermediate code; an optimization unit for optimizing the use of the parallel processors at the level of intermediate codes, including an automatic parallelization unit for identifying parts executable in parallel and performing a conversion of the intermediate code; and a unit for producing the object program.

The automatic parallelization unit is comprised of: a detection unit for detecting and recording the intermediate code corresponding to one part of the source program that is convertible to other different intermediate codes resulting in the same result of calculation but is not possible to determine the one providing the object program which can calculate the result more quickly than the other object programs unless that part of the object programs is executed; and a conversion unit for converting to an intermediate code which adds a different intermediate code resulting in the same result of calculation to the intermediate code detected by the detection unit, executes the original and the added intermediate codes in parallel, stops the execution of the other intermediate codes when the execution of one of the intermediate codes terminates before the other, and executes return to the original execution control.

The computer system may be a computer system having a vector processing processor for executing a vector processing instruction. The optimization unit of the compiler may be comprised of: a vectorization unit for analyzing whether the intermediate code is vectorizable or not and, if vectorizable, converting the vectorizable intermediate code to an intermediate code corresponding to a vector instruction; a detection unit for detecting a collection of intermediate codes which is determined as being vectorizable by the vectorization unit, said collection of intermediate codes being convertible to the intermediate codes corresponding to vector instructions in which priority is given to the vector length thereof or the intermediate codes corresponding vector instructions in which priority is given to the vector continuity thereof but is not possible to determine the one as providing the object program which can calculate its result more quickly than others; and a conversion means for converting to a second intermediate code which executes the intermediate codes vectorized by handling the vector length thereof preferentially and the intermediate codes vectorized by handling the vector continuity thereof preferentially in parallel, stops the execution of the other when the result is obtained from the one of the intermediate codes before the other, and executes return to the original execution control.

In the computer system having a vector processing processor for executing a vector processing instruction, another optimization unit of the compiler may be comprised of: a vectorization unit for analyzing whether the intermediate code is vectorizable or not and, if vectorizable, converting the vectorizable intermediate code to an intermediate code corresponding to a vector instruction; a detection unit for detecting a collection of intermediate codes determined as being vectorizable by the vectorization unit but is not possible to determine whether the vectorized or the unvectorized intermediate code provides the object program which can calculate its result more quickly than others; and a conversion unit for converting to a second intermediate code which executes the vectorized and the unvectorized intermediate codes in parallel, stops the execution of the other when the result is obtained from the one of the intermediate codes before the other, and executes return to the original execution control.

In regards to a subprogram, an optimization unit of the compiler may be comprised of: a detection unit for detecting the intermediate code indicating the start of a subprogram; and a conversion unit for converting to the intermediate code which adds a different intermediate code to the intermediate code of the whole subprogram detected by the detection unit, the different intermediate code storing the values of the corresponding actual arguments in an area allocated to dummy arguments immediately before the subprogram is executed, the allocated area thereafter used for the access and the definition of dummy arguments, and returning from the area to the corresponding actual argument the values of dummy arguments that may have been defined in the subprogram immediately before the subprogram is terminated, executes the original and the added intermediate codes in parallel, and stops the execution of the other intermediate code when the execution of one of the intermediate codes terminates before the other.

The above and other objects and advantages of the present invention will be understood from the following description of preferred embodiments of the present invention when taken in conjunction with the accompanying drawings .

FIG. 1 is a schematic of the parallel execution system used in the explanation of one embodiment of the present invention.

FIG. 2 shows the overall structure of the compiler to which the present invention is applied.

FIG. 3 shows the intermediate code used to illustrate the present invention.

FIG. 4 illustrates the source program of the present invention.

FIG. 5 illustrates the intermediate code output in the second embodiment of the present invention.

FIG. 6 illustrates the intermediate code output in the third embodiment of the present invention.

FIG. 7 illustrates the subprogram output example used in the fourth embodiment of the present invention.

FIG. 8 illustrates the intermediate code output example in the fourth embodiment of the present invention.

One embodiment of a FORTRAN compiler according to the present invention will be described in detail with reference to the drawings.

FIG. 2 shows the overall structure of the compiler to which the present invention is applied. In FIG. 2, a syntax analyzer 22 converts a source program 21 which is a FORTRAN program to an intermediate code 25. An optimizing unit 24 will take this as input and performs optimization, vectorization and parallelization, and converts it into an intermediate code 25, using a vectorizing unit 241 and an automatic parallelization unit 1. Then, a code producing unit 26 produces an object code 27. The present invention relates to the automatic parallelization unit I which increases the execution efficiency of the object code 27. The operation of the part of the optimizing unit 24, which pertains to the present invention will be described hereinafter.

FIG. 1 is a schematic of the parallel execution system as one embodiment of the present invention. In FIG. 1, a parallelizing intermediate code detection unit 11 is a detector which detects a collection of intermediate codes which corresponds to a part of a source program which is convertible to other intermediate codes that bring about the same result of calculation but cannot be determined as bringing about the object program from one of the intermediate codes which can calculate the result more quickly than the others unless that part of the object program is executed. An intermediate code parallelizing and conversion unit 12 adds a different collection of intermediate codes which brings about the same result of calculation to the original collection of intermediate codes detected by the parallelizing intermediate code detection unit 11, executes the original and added intermediate codes in parallel, and converts the intermediate codes to such that when the result is obtained from one of the original and added intermediate codes, the execution of the other is stopped. The intermediate codes 13 and 14 correspond to the temporary intermediate codes converted from the intermediate code 23 to the intermediate code 25 by the optimizing unit 24.

FIG. 3 shows an example of the intermediate code used to describe the invention. In FIG. 3, the intermediate code 31 is an intermediate code which instructs another processor M to execute intermediate codes from the one with the label L. The intermediate code 32 is an intermediate code which stops the procedure under execution in processor M. The intermediate code 33 is an intermediate code corresponding to the vector instruction by which LA number of elements starting at the FA.sup.th element at intervals of every SA number of elements are transferred from the arrangement A to the arrangement B starting at the FB.sup.th element at intervals of every SB number of elements. The intermediate code 34 is an intermediate code which means the intermediate codes up to the label L are repeatedly executed H times. The intermediate code 35 is an intermediate code which transfers the execution control to the intermediate code with label L. The intermediate code 36 is an intermediate code which substitutes the contents of A into B. The intermediate code 37 is an intermediate code which describes the entry of a subprogram. The intermediate code 38 is an intermediate code which describes the return of the execution control from a subprogram to the calling program.

FIG. 4 illustrates an example of the source program of the present invention. In FIG. 4, the source program 41 is a FORTRAN program example of the input source program in FIG. 2. The intermediate code 42 is an intermediate code corresponding to the source program 41. The intermediate code 43 is another intermediate code which gives the same result as the intermediate code 42. The source program 44 is a source program corresponding to the intermediate code 43 to illustrate the intermediate code 43. Optimization such as the conversion of the source program 41 to the source program 44 will be referred to as loop interchanging.

FIG. 5 illustrates the intermediate code output in the second embodiment. Generally, a vector instruction is said to be more efficient as the vector length of its operand is longer. However, in a program which is executed in a virtual storage space which handles the auxiliary storage as if it were the main storage, the efficiency of the vector instruction will be reduced if the interval of the vectors is longer even if the operand is longer since the number of times of copying from the auxiliary storage to the main storage increases.

For example, in a FORTRAN source program of the source program 41 of FIG. 4, it is possible in the optimizing unit 24 to convert to an intermediate code such as the intermediate code 42 which has a long vector length and a small number of vector instruction repetitions by interchanging the DO loop, but it cannot actually be determined during compilation time which of the intermediate codes 42 or 4S can calculate the result more quickly.

The parallelizing intermediate code detection unit 11 receives the intermediate code 1S as input and detects and records a loop structure in which a multiple DO loop is interchangeable and both the vector length and the interval of vectors as the result of the interchange increase or decrease respectively. The intermediate code parallelizing and conversion unit 12 converts the recorded intermediate codes to an intermediate code 14 as shown in FIG. 5.

Referring to FIG. 5, the converted intermediate code 14 in the present embodiment includes the intermediate codes 42 and 4S corresponding to the source programs 41 and 44, respectively, of FIG. 4, the intermediate code 51 which executes the intermediate codes 42 and 43 in parallel, the intermediate code 52 which stops the execution of the other intermediate code depending on which one of the intermediate codes 42 and 43 has obtained its result earlier, and the intermediate code 53 which executes subsequent return to the original execution control.

FIG. 6 illustrates the intermediate code outputs in the third embodiment.

When a loop is executed, preparations for the execution are required. As the time required for these preparations are generally longer for the vectorized loop, if the vector length is shorter, vectorization renders the processing speed to be lower. However, if the vector length is sufficiently long, vectorization brings about a higher processing speed. Therefore, there is a vector length at which the vectorized and unvectorized loops require the same execution time. Such a vector length is referred to as the intersecting vector length.

If N>M where N is the vector length and M is the intersecting vector length, the processing speed is higher for a vector instruction. When N cannot be determined during compilation time, it cannot be determined which of the object programs derived from a vectorized or an unvectorized intermediate code will be achieve a higher processing speed.

The parallelizing intermediate code detection unit 11 detects and records the vectorizable portion of the intermediate code detected by the vectorizing unit 241 that is not possible to determine the vector length until the time of execution. The intermediate code parallelizing and conversion unit 12 converts the recorded intermediate code to the intermediate code 14 as shown in FIG. 6.

Referring to FIG. 6, the converted intermediate code in the present embodiment includes the vectorized intermediate code 61, the unvectorized intermediate code 62, the intermediate code 63 which executes these intermediate codes in parallel, the intermediate code 64 which stops the execution of the other intermediate code depending on which one of the intermediate codes 61 and 62 has obtained its result earlier, and the intermediate code 65 which executes subsequent return to the original execution control.

FIG. 7 illustrates the subprogram of the fourth embodiment. Generally, access to the data in contiguous memory locations is obtained more quickly than that in noncontiguous locations. Therefore, when a subprogram is executed, a conversion such as that of FIG. 7 can reduce the processing time.

Referring to FIG. 7, immediately before the subprogram is executed, the statement 73 is inserted such that the values of the corresponding actual arguments are stored in an area allocated to dummy arguments, and as shown in the statement 74, this area is used thereafter for the access and the definition of dummy arguments. Immediately before the subprogram is terminated, the statement 75 is inserted to return from this area to the corresponding actual argument the values of dummy arguments that may have been defined in the subprogram.

However, if the processing time for storage into a temporary area is considered, whether the processing time is reduced or not depends on such things as the number of times the transferred actual arguments and dummy arguments are accessed. Therefore, it cannot be determined whether such a conversion will increase the processing speed unless executed.

The parallelizing intermediate code detection unit 11 detects and records the intermediate code indicating the start of the subprogram. The intermediate code parallelizing and conversion unit 12 performs the conversion to the intermediate code 14 of FIG. 8.

Referring to FIG. 8, the converted intermediate code 14 in the present embodiment includes the intermediate code 83 which executes in parallel the intermediate code 81 corresponding to the source program 71 of FIG. 7 and the intermediate code 82 corresponding to the source program 72 of FIG. 7 in which the conversion performed includes the storage to a temporary area, the intermediate code 84 which stops the execution of the other intermediate code depending on which one of the intermediate codes 81 and 82 has obtained its result earlier, and the intermediate code 85 which executes subsequent return to the original execution control.

In the conventional techniques, if the production of an object could be considered using a plurality of algorithms for a certain type of procedures, the algorithm which produces the optimal object could not be determined unless all the objects produced either by using a plurality of compilers or by changing the compilation option were executed.

According to the present invention, by producing a plurality of different objects for a certain part of the source program and executing them in parallel, it becomes possible to use the superior and excellent object as a result and has the effect of reducing the time required for program execution.

It is to be understood that the above-described arrangement is simply illustrative of the invention. Other arrangements may be devised by those skilled in the art which will embody the principles of the invention and fall within the spirit and scope thereof.