Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1993-02-16
2001-06-26
Banankhah, Majid A. (Department: 2151)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C709S241000
Reexamination Certificate
active
06253371
ABSTRACT:
BACKGROUND OF THE INVENTION
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.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a parallelization supporting method, in which a dataflow in a procedure is analyzed by using information outside the procedure, and a program which can not be parallelized by an analysis of a single program is parallelized if possible. When there is a dependency relationship that can not be analyzed statically, the dependency relationship is established by having questions and answers between a system and the user or executing the program to thereby judge whether or not the program is parallelizable. Thus, the user dose not need to make decision and therefore the risk of an erroneous decision can be avoided or madeless. When a parallelizable loop or a program conversion that is necessary for a parallelization has been detected, the user can know the result and this can be reflected into a source program so that the compiler can produce a parallelizable object program.
REFERENCES:
patent: 5093916 (1992-03-01), Karp et al.
patent: 5146594 (1992-09-01), Iitsuka
patent: 5151991 (1992-09-01), Iwasawa et al.
patent: 5179702 (1993-01-01), Spix et al.
patent: 5230053 (1993-07-01), Zaiki
patent: 5237691 (1993-08-01), Robinson et al.
Padua et al, Advanced Compiler Optimizations for Supercomputers, Communications of the ACM, 1986, pp. 1184-1201.*
Levesque, John M. “Transforming Existing Fortran Programs for Parallel Execution,” 4th ISR Supercomputing Workshop—The Road to Parallel Applications, Aug. 29-31, 1990, (English).
Iwasawa Kyoko
Kikuchi Sumio
Kurosawa Takashi
Banankhah Majid A.
Hitachi , Ltd.
Mattingly Stanger & Malur, P.C.
LandOfFree
Method for supporting parallelization of source program does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for supporting parallelization of source program, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for supporting parallelization of source program will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2442830