1. Field of the Invention
The present invention relates to a method for supporting parallelization of a source program, and more specifically, to a method in which it can be decided whether or not a part of the source program is parallelizable and in which a result of the decision is reflected into a source program in the form of directive statements that can be compiled by a compiler.
2. Description of the Related Art
A parallelizing compiler is mounted on a memory-sharing-type parallel computer such as CRAY, CONVEX or Alliant. The compiler produces object programs that can be executed in parallel, in accordance with parallelization directive statements described by a user or when the compiler has decided that a program is parallelizable as a result of a static analysis within one procedure. A compiler for producing a parallelized object program based on an interprocedural dataflow analysis is discussed in the U.S. Pat. No. 5,146,594. As a currently available parallelizaton supporting tool, in which a program is inputted and outputted in the form of source program, there is FORGE commercialized by Pacific-Sierra Research. This tool is described in a reference document, "Transforming Existing Fortran Programs for Parallel Execution", by John M. Levesque, at the 4th ISR Supercomputing Workshop --The Road to Parallel Applications, Aug 29-31, 1990. This parallelization supporting tool displays the result of accesses to common variables and argument data in calling and called procedures in accordance with user's instructions. Although this tool has no function of analyzing dataflow of an array by taking in the relationship between definitions and use of variables accessed in the calling and called procedures, it has a function of displaying the result of accesses to the array when executing the procedures in case that it is not possible to analyze the dataflow and therefore it is not possible to decide whether or not a program can be parallelizable, i.e., parallelizability. In any case, this tool can only display the access result and has no function of deciding parallelizability from the displayed result, so that the decision of parallelizability is made by the user.
There are following problems which are common to the above-described compilers. It is not possible to analyze dataflow in procedures even in a case of taking in information outside the procedures including a program portion to be parallelized. The information outside the procedures means names and values of common or actual argument variables which are used only in a called procedure and the values of which are never updated and names, or names and values of common and dummy argument variable which are always constant when the procedure is called. This can be explained as follows with reference to FIG. 2. There is an actual argument variable J in a CALL statement 26 within a subroutine SUBA. If it is known based on the interprocedural dataflow information that the value of this variable will never be updated in a called subroutine (SUBX) 29, this variable can be analyzed as an induction variable. Thus, this variable does not take a same value within a DO 10 loop of the subroutine (SUBA) 28, so that it can be known that a definition 27 of an array (J) is executed as substitution into an element which is always different and accordingly does not prevent a parallelization. According to the above-mentioned techniques, however, it is regarded in the analysis of the loop of the subroutine SUBA that a value of the array B(J) is updated in the CALL statement 26 and it is also regarded that this value of the variable J can not be predicted and has a possibility that a same value is taken within the loop. When the substitution statement 27 of the array, B (J), sets values at the same address for plural times, since an abnormal result is obtained if the repetitions of the loop are parallelized, an impossibility of parallelization is decided by the compiler.
In the case where parallelizability is checked by the compiler, as discussed in the above-described U.S. Pat. No. 5,146,594, since control flow or dataflow is decided at the time when a user program is executed, there is generally a dependency relationship of data that can not be analyzed at the compile time even if an interprocedural analysis has been carried out. When there is the dependency relationship that can not be analyzed, there is a risk of incurring an abnormal result as a result of a parallelizaton, and therefore, the compiler produces an object program for sequential execution without parallelizing the program. Accordingly, even if a program is parallelizable if there is user's knowledge or information at the time of the execution, this program is decided as unparallelizable because it can not be analyzed. Further, since the compiler produces only object codes, the user can not know exactly what kind of program conversions have been carried out.
The FORGE has a function of displaying an access result of array variables by actually executing a program. However, since it does not have a function of deciding parallelizability of the program, the user must decide the parallelizability based on the overlap of accesses to array variables by looking at the displayed data. Particularly, when there is a large volume of displayed access data for the array variables, there is a risk that the user makes an erroneous decision, leading to a parallelization with an abnormal result.
USPTO Backgrounds
USPTO Backgrounds