Electrical computers and digital processing systems: multicomput – Computer network managing
Reexamination Certificate
2000-02-14
2004-01-06
Dam, Tuan Q. (Department: 2122)
Electrical computers and digital processing systems: multicomput
Computer network managing
C717S120000, C706S048000, C709S223000, C709S239000
Reexamination Certificate
active
06675207
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a compiler apparatus and method for evaluating the possibility of execution of a plurality of processings executable in parallel in a distributed computer system, and creating a program for implementing such processings.
Specifically, the present invention relates to a compiler apparatus and method for evaluating the possibility of execution of a plurality of processings which are described by a PERT (Program Evaluation and Review Technique) method and can be executed in parallel, and creating a program for implementing such processings.
2. Prior Art
For instance, “Introduction to PERT” (Reference 1: written by Tokutaro Suzuki, and published by Japan Management Association, May 28, 1980) and “Process Control (New version)” (Reference 2: written and edited by Administrative Section of Industrial Structure Council by Ministry of International Trade and Industry, written by All Japan Management Federation, and published by the Nikkan Kogyo Shinbun Ltd., Aug. 30, 1972) disclose a method for using a PERT diagram for project management.
Further, many references such as Published Unexamined Patent Application Nos. 5-216643, 8-6816, 7-295855, and 6-161773 (References 3-6) disclose a method for creating programs executed in parallel.
Furthermore, NEC Corporation is selling “ESMPRO/JMSS” as a product of this type.
In this ESMPRO/JMSS, a processing flow can be defined by a GUI operation using a PERT diagram.
Since the parallel execution of a plurality of jobs, a queuing of executions and the like can be explicitly defined, the PERT diagram is suitable for defining a processing including a plurality of jobs executed in parallel, which is difficult to be defined by a procedure-oriented programming language such as C, if a new concept such as conditional branch is introduced and the synchronization method between processing nodes is previously determined.
However, the flowchart which has been conventionally used to define a processing flow and the PERT diagram are different in the point that, in the latter, the concepts of “parallel execution” and “queuing” are defined, while in the former, these concepts are not defined, so it is difficult to describe a processing flow defined by the PERT diagram with a procedure-oriented programming language suitable for describing a processing flow defined by a flowchart.
Further, if the use of conditional branch, which has originally been inhibited, is permitted in the PERT diagram for defining a wider processing flow, it is more difficult to express the definition of a job defined by the PERT diagram with a procedure-oriented programming language.
This difficulty becomes more remarkable as the processing size becomes greater, and as the processing flow becomes more complex.
The present invention was performed in view of the above-mentioned problems of the background art, and its object is to provide a possibility of execution evaluating apparatus and method which can evaluate the possibility of execution of a processing defined by a PERT diagram or a similar technique, and can assist the creation of a program for implementing the defined processing.
Moreover, it is an object of the present invention to provide a possibility of execution evaluating apparatus and method for evaluating whether or not a processing including a plurality of jobs executable in parallel and defined by a PERT diagram or a similar form can be described with a procedure-oriented programming language, and if the description is possible, pointing out the reason for it to assist the creation of a program for implementing the above-identified processing.
SUMMARY OF THE INVENTION
To attain the above objects, the possibility of execution evaluating apparatus related to the present invention is a possibility of execution evaluating apparatus for evaluating the possibility of execution of a processing flow including one or more jobs being executable in parallel, each of the jobs starting when accepting the processing result of a one or more previous jobs, comprising:
a simplification unit for simplifying a PERT network including one or more jobs included in the processing flow as is nodes, respectively, according to predetermined rules (simplification rules); and
a possibility of execution evaluating unit for evaluating the processing flow as being inexecutable when predetermined connection patterns are happening between the nodes in the part being not able to be simplified any more in the simplified network.
Preferably, it has a starting job determining unit for sequentially determining which of the previous jobs (starting job) provides a processing result that causes the jobs corresponding to the nodes forming the part being not simplified any more to start when accepting the processing result in the simplified network.
Preferably, the simplification rules include rules for transforming the PERT network to topologically equal simple form.
Preferably, the processing flow may include conditional branches as the jobs, and the simplification rules include: a first rule in which there are one or more starting jobs, and if there are a first job which outputs processing results to one or more next jobs, a second job which starts when accepting only the processing result of the first job and outputs a processing result only to one next job, and a third job which starts only upon the processing result of the second job and outputs a processing result to one or more next jobs, then in the PERT network, the node corresponding to the second job is removed, and the node corresponding to the first job and the node corresponding to the third job are directly connected to each other; a second simplification rule in which there are one or more starting jobs, and if there are a fourth job which outputs a processing result of the fourth job and does not output a processing result to the next job, then in the network, the node corresponding to the fifth job is removed; a third simplification rule in which, if there are the first job (a sixth job), and the third job (a seventh job) which starts when accepting a plurality of processing results of the sixth job, the plurality of processing results which are outputted from the sixth job to the seventh job are collected to one in the network; a fourth simplification rule in which, if there is a eighth job showing a conditional branch, and the third job (a ninth job) which starts when accepting the results of the conditional branch of the eighth job, then in the network, the node corresponding to the eighth job is converted to a node corresponding to the fourth job, and the node corresponding to the ninth job is converted to a node corresponding to the third job which starts when accepting the processing result of the fourth job obtained by the conversion of the eighth job; and a fifth simplification rule in which, if there are the first job (a tenth job) outputting two processing results, the third job (an eleventh job) which starts when accepting one of the processing results of the tenth job and outputs two processing results, the fourth job (a twelfth job) which starts when accepting only the other one of the processing results of the tenth job and one of the processing results of the eleventh job, and the first job (a thirteenth job) which starts when accepting only the other one of the processing results of the eleventh job, and the first job (a thirteenth job) which starts when accepting only the other one of the processing results of the eleventh job and the processing result of the twelfth job, then in the network, the node corresponding to the thirteenth job is converted to a node corresponding to the first job which starts when accepting any of the processing results of the tenth job and the processing result of the eleventh job.
Preferably, the predetermined connection patterns include a first connecting pattern which shows that a loop is happening in the processing between the above nodes in the network.
Preferably, the processing flow may include a conditional branch
Dam Tuan Q.
International Business Machines - Corporation
Kendall Chuck
Ludwin, Esq. Richard M.
Scully Scott Murphy & Presser
LandOfFree
Possibility of execution evaluating apparatus and method... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Possibility of execution evaluating apparatus and method..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Possibility of execution evaluating apparatus and method... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3247881