Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-12-19
2004-06-15
Chaki, Kakali (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S159000, C719S313000
Reexamination Certificate
active
06751791
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an optimization method by a compiler that compiles a program using a message-passing interface (MPI), and particularly to an optimization method that realizes a reduction in the execution time of an MPI program.
2. Description of the Related Art
In compilers of the prior art, output of an object program is realized by carrying out optimization of a received source program that places an emphasis on either the code size or execution speed.
This type of compiler described in, for example, Japanese Patent Laid-open No. 120152/99, comprises a syntactic analysis section to analyze the syntax of the source program, and a code generation section that, following completion of syntactic analysis, selects commands based on the analysis results and instructions, generates output code, and outputs the object program.
However, since a message-passing interface (MPI) is a library that does not depend on language, the above-described compiler of the prior art typically incorporates a command to invoke a procedure into the object program as described without changing the MPI procedure invocation in the source program.
In other words, even though there is plenty of room for optimization regarding MPI procedure invocations, it was not considered to be an object of optimization.
Essentially, optimization in the above-described prior-art compiler suffers from a problem that since a command to invoke a procedure was incorporated into the object program as described without changing the MPI procedure invocation in the source program, the MPI procedure invocation is not considered to be object of optimization, the execution time of the MPI program could not be shortened.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an optimization method by a compiler that can realize a reduction in the program execution time by taking an MPI procedure invocation portion as an object of optimization by the compiler when compiling a program that employs message-passing interface (MPI).
To accomplish the aforementioned object, the present invention performs optimization of MPI procedures by detecting an MPI procedure invocation portion within a received source program and then altering it to another procedure or altering the execution sequence.
According to the present invention, a reduction in the execution time of an MPI program can be realized because an MPI procedure invocation portion is taken as an object of optimization and the MPI procedure is altered to a more efficient procedure or the execution sequence is altered for optimization such as simultaneous execution of communication and processing.
According to an embodiment of the present invention, when a correct type is being used as the argument of the invoked MPI procedure, an object program is outputted such that a procedure is invoked in which a type check is omitted.
According to this embodiment, if no errors are found when performing an error check of the argument when compiling, a reduction of execution time is realized by altering such that a high-speed MPI procedure is invoked in which an error check is not performed during execution.
According to another embodiment of the present invention, an argument relating to the communication data size of the invoked MPI procedure is checked, and if the communication data size can be determined during compiling, an object program is outputted such that the optimum procedure according to the communication data size is invoked.
According to this embodiment, when the communication size is found during compiling, a reduction of the execution time can be realized by altering such that an MPI routine is invoked that uses the optimum protocol according to the size.
According to yet another embodiment of the present invention, when a synchronous communication MPI procedure invocation is detected, statements preceding and following the statement of the MPI procedure invocation are analyzed, and if, based on the analysis, there is an execution statement that depends only on data that have no relation to communication data, and moreover, the meaning of the program is not changed by movement of the statement, the execution sequence of the execution statement is altered to follow the MPI procedure, a communication waiting procedure is inserted after the list of execution statement, and an object program is outputted in which the MPI procedure is altered to an asynchronous communication procedure.
According to this embodiment, by altering a synchronous communication MPI procedure to an asynchronous communication MPI procedure and moving an execution statement that is not relevant to communication data to immediately follow the MPI procedure, simultaneous execution of communication and processing is performed without placing a burden on the program developer to thereby realize a reduction in the execution time.
According to yet another embodiment of the present invention, when a barrier synchronization MPI procedure invocation is detected, the statements preceding and following the MPI procedure invocation statement are analyzed, and if, based on the analysis, it is determined that the MPI procedure is unnecessary, an object program is outputted in which the statement of the procedure invocation is eliminated.
According to this embodiment, the necessity of a barrier synchronization is determined, and if not necessary, the barrier synchronization invocation is eliminated so that a reduction in execution time is realized.
Finally, according to another embodiment, in an optimization method at the time of compiling the MPI program if one-to-one communication within a loop is detected, and the analysis of the communication pattern shows that the communication pattern corresponds to MPI group communication, an object program is outputted such that the group communication procedure is invoked instead.
According to this embodiment, a reduction in execution time can be realized by recognizing communication patterns in which specific group communication is performed using one-to-one communication and then replacing with a more efficient group communication.
The above and other objects, features, and advantages of the present invention will become apparent from the following description with reference to the accompanying drawings which illustrate examples of the present invention.
REFERENCES:
patent: 5649294 (1997-07-01), Ayerst et al.
patent: 5701489 (1997-12-01), Bates et al.
patent: 5832273 (1998-11-01), Mizuse
patent: 5920721 (1999-07-01), Hunter et al.
patent: 6016397 (2000-01-01), Ogasawara et al.
patent: 6085035 (2000-07-01), Ungar
patent: 6286136 (2001-09-01), Watanabe et al.
patent: 6477702 (2002-11-01), Yellin et al.
patent: 6487716 (2002-11-01), Choi et al.
patent: 6530079 (2003-03-01), Choi et al.
patent: 6539542 (2003-03-01), Cousins et al.
patent: 5-73449 (1993-03-01), None
patent: 11-120152 (1999-04-01), None
Hirotaka Ogawa and Satoshi Matsuoka, OMPI: Optimizing MPI programs using Partial Evaluation, 1996, Department of Information Engineering, The University of Tokyo.*
Hwansoo Han, Chau-Wen Tseng, Pete Keleher, Reducing Synchronization Overhead for Compiler-Parallelized Codes on Software DSMs, Aug. 1997, Proceedings of the Tenth Workshop on Languages and Compilers for Parallel Computing.
Chaki Kakali
Foley & Lardner LLP
NEC Corporation
Roche Trent J
LandOfFree
Method of optimizing an MPI procedure by altering to a... 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 of optimizing an MPI procedure by altering to a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of optimizing an MPI procedure by altering to a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3312319