Data-driven process generator6141776Abstract A method of analyzing process steps and creating a data-driven process is disclosed. A data-driven process is a process that has its steps sequenced according to data relationships among the process steps, and the rule that a step is placed in the sequence only when all of its inputs exist. A data-driven process can only be created when all steps may be placed in the sequence according to this rule. The method determines if a process is data-driven by checking to see if any of the individual steps causes one or more errors which would prevent data-driven sequencing, and, if any errors are found, error correction is attempted in order to create a data-driven process. Claims The embodiments of the invention in which an exclusive property or privilege is claimed are defined as follows: Description FIELD OF THE INVENTION
TABLE 1
______________________________________
Error #1
Pass-Through Data Items
Data items that are both an input
and an output will prevent data-
driven sequencing.
Error #2 Redundant Data Generation Two or more process steps having
a particular data item in their lists
of outputs or initial outputs will
prevent data-driven sequencing.
Error #3 Tight-Loop Iteration Two steps that feed each other,
will prevent data-driven
sequencing. This occurs when
Step A has an output that is an
input of Step B, and Step B has an
output that is an input of Step A.
Error #4 Connected Iteration A single step located at the end of
one iteration loop and also at the
start of another iteration loop will
prevent data-driven sequencing.
Error #5 Non-Converging Iteration An iteration loop between two
steps constructed such that it is not
possible for any data to flow
between the step at the start of the
loop and the step at the end of the
loop data-driven sequencing. The
data does not have to flow directly
between the two steps. The data
may involve other steps.
Error #6 Inconsistent Iteration A step at the end of an iteration
loop having output data items that
appear in the list of inputs of the
step at the start of the iteration loop
will prevent data-driven
sequencing.
Error #7 Incomplete Iteration A step having a data item in its list
of initial inputs that does not
appear in the list of outputs of any
step in the process will prevent
data-driven sequencing.
______________________________________
Error checking according to the preferred embodiment of the present invention is divided into two phases: a pre-sequencing phase during which the system analyzes for Errors 1-3; and a post-sequencing phase during which the system analyzes for Errors 4-7. Each of the two phases is followed by a sequencing phase of operation. After the pre-sequencing phase, a trial data-driven sequence is created so that the system running an embodiment of the invention can check for Errors 4-7. During this trial sequencing, the system also checks for an additional error, the Implied Iteration, which will be discussed more fully below. Final sequencing is performed after post-sequencing error processing to create a final data-driven process. The four phases of operation are described more fully in the following discussion. FIG. 2A is a functional flow diagram illustrating in a general way how a computer system is programmed according to the invention to analyze processes to determine if they are data-driven and to resequence processes that are not data-driven so that they become data-driven, if possible. The program begins, at block 205, by creating a list, designated List A, of all process steps in a sequence to be analyzed. Each of the process steps in a sequence to be analyzed has four associated lists: an INPUTS list containing the names of data items that are used by the process step as input data; an INITIAL INPUTS list containing the names of data items that are used by the step as initial values in an iteration loop; an OUTPUTS list containing names of data items which are created by the process step; and an INITIAL OUTPUTS list containing the names of data items that are created by the process step and used by other process steps as initial inputs. At block 210, four collective lists are created: a list containing all data items that are inputs to process steps; a list containing all data items that are outputs of process steps; a list of all data items that are used as initial values in iteration loops; and a list of all data items that are initial outputs, i.e., a collective INPUTS list; a collective INITIAL INPUTS list; a collective OUTPUTS list; and a collective INITIAL OUTPUTS list. In a present embodiment of the invention, the collective lists of data items are maintained as unique lists; however, those skilled in the art will recognize that lists containing redundant data items could be employed without departing from the spirit of the invention. The creation of the collective lists can take place any time from during the creation of List A to the beginning of error processing or even not at all. The system of the present invention need not create four new, collective, lists, but could operate using the four lists of each individual step in List A. Pre-sequencing error processing is performed at block 215. Details of the pre-sequencing error processing are illustrated in FIG. 3A, and described below. After pre-sequencing error processing has been performed, a check is made to determine whether all the errors of Types 1-3 (see Table 1) have been corrected. See block 220. If not, at block 225, a determination is made as to whether or not it is possible to correct those errors. This determination is generally made by a human user based on decision and determinations made by the user during the pre-sequencing error processing at block 215, but rule-based systems or other ways making of this determination could be employed without departing from the spirit of the invention. If it is determined, at block 225, that it is possible to correct the errors, then the pre-sequencing error processing steps at block 215 are repeated. This sequence reoccurs until either all Type 1-3 errors have been corrected, or it is determined that it is not possible to do so. If, at block 225, it is determined that it is not possible to correct all errors, the program determines that data-driven sequencing is not possible with the given information and system operation terminates. See block 230. If, at block 220, it is determined that all Type 1-3 errors have been corrected, the program enters, at block 235, the process sequencing phase of operation. Since, at this stage, Errors 4-7 have not been addressed, only a trial data-driven sequence is created, rather than a final one. Details of the initial sequencing operation are illustrated in FIG. 2B, and described below. After the trial data-driven sequence has been created, post-sequencing error processing is conducted. See block 240. Details of the post-sequencing error processing are illustrated in FIG. 3B, and described below. After post-sequencing error processing has been performed, a check is made to determine whether all the errors of Types 4-7 (see Table 1) have been corrected. See block 245. If not, at block 250, a determination is made as to whether or not it is possible to correct those errors. As in the pre-sequencing phase, this determination is generally made by a human user, but other ways making of this determination could be employed without departing from the spirit of the invention. If it is determined, at block 245, that it is possible to correct the errors, then the pre-sequencing error processing steps at block 240 are repeated. This sequence reoccurs until either all Type 4-7 errors have been corrected, or it is determined that it is not possible to do so. If, at block 250, it is determined that it is not possible to correct all errors, the program determines that data-driven sequencing is not possible with the given information and system operation terminates. See block 230. If, at block 245, it is determined that all Type 4-7 errors have been corrected, then final data-driven sequencing is performed. See block 255. Details of the final sequencing operation are illustrated in FIG. 2B, and described below. As noted above, the pre-sequencing error processing performed at block 215 is depicted in FIG. 3A, which is described next. FIG. 3A is an overall flow of the pre-sequencing error processing performed at of block 215 in FIG. 2A. Pre-sequencing error processing is performed to detect and attempt to correct Errors 1-3 described in Table 1. Referring to FIG. 3A, at block 310, each process step in List A is checked for any pass-through data items. If a process step has outputs which are also inputs, the process step is said to have a pass-through data item. In a present embodiment of the invention, checking for pass-through data items is accomplished by performing an exclusive-OR (XOR) operation on the INPUTS and OUTPUTS lists for each process step. If the result from the XOR operation is other than a null or empty set, then pass-through data items have been detected. Those skilled in the art will readily appreciate that other methods of comparing the INPUTS and OUTPUTS lists may be used other than the exclusive-OR without departing from the spirit and scope of the invention. Since data items cannot be input to and output from the same process step, this situation results in a process that cannot be data driven if the situation is not corrected. In a present embodiment of the invention, all process steps are analyzed at block 310 prior to making a determination as to whether any pass-through data items are detected; however, those skilled in the art will recognize that each process step may be examined individually, entering the error correction procedure immediately upon detection of an error, such that for each error, detection and correction is an iterative process for each process step. If, at block 310, any pass-through data items were detected, error correction processing of FIG. 4 is initiated. See block 312. Referring to FIG. 4, at block 405, the user is informed that Error 1 has been detected. The user is then presented with the data items that are on both the INPUTS and OUTPUTS lists of the process steps, so that the user can select a list from which to delete each data item. See block 410. The user may elect to delete a data item from the INPUTS list or the OUTPUTS list. If, at block 415, the user is able to choose a list from which to delete a data item from one list for each process step having a pass-through data item, processing returns with no error to block 312 of FIG. 3A. See block 420. If the user is unable to do so, or unwilling to make a decision at this time, then processing is returned with an error to block 312 of FIG. 3A. See block 425. Alternatively, the return with error could return to block 220 of FIG. 2A. Returning to FIG. 3A, if at block 310, no pass-through data items were detected, or after a return from error correction processing at block 312, processing proceeds to block 315. At block 315 the process steps in List A are analyzed for redundant data generation. In a present embodiment of the invention, the collective OUTPUTS list is exclusive-ORed (XORed) with the OUTPUTS list of each process step to determine the process steps which generate each data item. If the analysis determines that a data item is generated by more than one process step, error correction processing of FIG. 5 is initiated. Referring to FIG. 5, first the user is informed that Error 2 has been detected. See block 455. The user is then presented with all the process steps which generate each particular data item, and asked to select a single process step to be the generator for the data item. See block 460. After the user has selected a single process step as a generator for each data item, at block 465, the data item is deleted from the OUTPUTS lists of all the other process steps. If, at block 470, the user was able to select a single process step as a generator for each data item having more than one generator, processing returns with no error to block 317 in FIG. 3A. See block 475. If the user is unable to select a single process step as the generator for any data item, or is unwilling to make a decision at this time, processing returns with an error to block 317 in FIG. 3A. See block 480. Alternatively, the return with error could return to block 220 of FIG. 2A. Returning to FIG. 3A, if, at block 315, no redundant data generation was detected, or after a return from error correction processing at block 317, processing proceeds to block 320. At block 320, each combination of process step pairs in List A is analyzed for any tight-loop iteration. Tight-loop iteration is present when a first step (A) has input data items created by a second step (B) and step B has input data items created by step A, but no iteration has been specified, and the sequencing logic is unable to determine which of the two steps is to be executed first. In a present embodiment of the invention, each process step in List A is compared with every other process step. The INPUTS list of step A is exclusive-ORed with the OUTPUTS list of step B, and the OUTPUTS list of step A is exclusive-ORed with the INPUTS list of step B. If both exclusive-OR operations result in non-empty sets, then a tight-loop iteration has been detected. This situation must be resolved by the user specifying whether step A precedes step B or the other way around. Once this decision is made, the data items being sent from the second step back to the first will be changed from input data items into initial input data items for the first step. When resolved in this way, the result is iteration between steps A and B. Where three or more steps are involved, an implied iteration situation, similar to the tight-loop iteration may result. This will be detected during the sequencing of a process when none of the remaining process steps have all their inputs available, and no tight-loop iteration is present. Implied iteration will be discussed more in the description of the sequencing phase below. This must be resolved by selecting one of the process steps as the one to execute first among the steps in the implied iteration. This has the effect of setting all unavailable inputs of that one step to initial inputs, and putting this step at the start of one or more iteration loops. When resolved in this way, iteration is the result. If, at block 320, tight-loop iteration is detected, the error correction processing shown in FIG. 6 is initiated. Referring to FIG. 6, the user is informed that Error 3 has been detected. See block 505. The user is then presented with the step pairs resulting in tight-loop iterations, and asked to select one step of each pair to be sequenced before the other. See block 510. After the user selects the step to be sequenced before the other, all data items which are input to the selected step and output from the other step are moved from the INPUTS list to the INITIAL INPUTS list of the selected step. See block 515. If, at block 520, the user was able to select a step to be sequenced before the other, processing returns with no error to block 322 of FIG. 3A. See block 525. On the other hand, if the user was unable to choose a step, or was unwilling to make a decision at this time, at block 520, then at block 530, processing is returned with an error to block 322 at FIG. 3A. Alternatively, the return with error could return to block 220 of FIG. 2A. Returning to FIG. 3A, if at block 320, no tight-loop iteration was detected, or after a Return from error correction processing at block 322, processing returns to block 215 of FIG. 2A. While the illustrated embodiment of the invention processes for Errors 1-3 sequentially, it is to be understood that other processing orders could be used, and certain combinations of Errors 1-3 could be processed concurrently, without departing from the spirit and scope of the invention. Returning to FIG. 2A, once all the pre-sequencing errors have been corrected, an initial trial sequencing phase, depicted in FIG. 2B, is entered at block 235. Referring to FIG. 2B, during this initial sequencing phase of operation, a list, designated as List B, is created. See block 262. List B contains all data items which are an input to a process step in List A, but are not output by any process step in List A, i.e., data items which are included in an INPUTS list of a process step, but are not included in any OUTPUTS lists of any process steps are placed in List B. Next, at block 264, another list, designated as List C, is created, if it has not already been created. List C is created by examining all the process steps in List A to locate those steps for which all input data items are in List B. These steps are placed in List C. Then, at block 266, List C is checked to see if there is at least one process step contained therein. If not, List A is displayed to the user at block 268, and the user is asked to choose a step from the list to be the next step of the process. If, at block 270, the user is unable to choose a process step to be the next step, then datadriven sequencing is deemed not possible, and the process will terminate. See block 272. At this stage of trial sequencing, an additional error, implied iteration, can be detected. Implied iteration is similar to the Tight-Loop Iteration of Error 3, except that three or more steps are involved. This will be detected when none of the remaining process steps have their inputs available, but no Tight-Loop Iteration is present. For example, if only steps A, B and C remain to be sequenced, and step A has inputs generated by step C, step B has inputs generated by step A, and step C has inputs generated by step B, then an Implied Iteration is present. Implied iteration must be resolved by selecting, at block 270, one of the process steps as the one to execute first among the steps in the implied iteration. This has the effect of setting all unavailable inputs of that one step to initial inputs, and putting this step at the start of one or more iteration loops. When resolved in this way, iteration is the result. If, at block 270, the user can and does choose a step from List A to be the next step, the chosen step is modified to account for any iteration, as noted above, and then inserted in List C. See block 274. Modifying a step to account for iteration means that at least one input is changed to an initial input for that step. If at least one process step was determined to be in List C at block 266, or after the modification for iteration and insertion of a process step into List C at block 274, all process steps from List C are moved to the trial data-driven sequence as concurrent steps, i.e., as steps which may be performed concurrently. See block 276. At block 278, all the data items in the OUTPUTS and INITIAL OUTPUTS lists of the concurrent steps from List C are moved to List B. The concurrent steps are then deleted from List A, at block 280. Next, at block 282, List A is examined to see if any process steps remain to be sequenced. If so, the trial data-driven sequencing phase is complete, and processing returns to block 240 of FIG. 2A. See block 284. If, at block 282, List A still contains steps to be sequenced, processing returns to block 264 and the steps from this point on are repeated. Returning to FIG. 2A, after the trial data-driven sequence has been created, post-sequencing error processing is performed. See block 240. As noted above, the post-sequencing error processing performed at block 240 is depicted in FIG. 3B, which is described next. FIG. 3B is an overall flow of the post-sequencing error processing performed at of block 240 in FIG. 2A. Post-sequencing error processing is performed to detect and attempt to correct Errors 4-7 described in Table 1. Referring. to FIG. 3B, after the trial data-driven sequence has been created, the sequenced steps are analyzed for Errors 4-7. Beginning at block 326, each step having data items in its INITIAL INPUTS list is analyzed for any connected iteration. A connected iteration is present when a single process step is at the end of one iteration loop and also at the beginning of another iteration loop. This typically occurs when process steps are modeled at a high level, disguising the fact that there are actually two steps inside of one process step. If the high level process step was shown as two steps, the iteration loops would no longer be connected. If connected iteration is detected at block 326, processing proceeds to the error correction processing depicted in FIG. 7. See block 328. Referring to FIG. 7, first, at block 555, the user is informed that Error 4 has been detected. Then, at block 560, the process step involved in the connected iteration is then split into two steps. One step is sequenced at the end of the first loop and the other step is sequenced at the beginning of the second loop. See block 565. The connected iteration is then presented to the user, and it is left up to the user to split the high level process step into two steps. If, at block 570, it was possible to split the process step into two steps, and resequence the two steps, processing returns with no error to block 328 in FIG. 3B. See block 575. If, on the other hand, the user was unable to do so, at block 580, processing is returned with an error to block 328 in FIG. 3B. Alternatively, the return with error could be to block 245 of FIG. 2A. Returning to FIG. 3B, if, at block 326, no connected iteration was detected, or after a return from error correction processing at block 328, processing proceeds to block 330. At block 330, each step having data items in its INITIAL INPUTS list is analyzed for non-converging iteration. Non-converging iteration occurs when an iteration loop fails to pass any data from the start of the loop to the end of the loop. If the process step that initiates an iteration loop does not, by some means, convey data to the step which generates new data item values for the iteration, the iteration loop has no ability to converge. If non-converging iteration is detected at block 330, error correction processing depicted in FIG. 8 is initiated. See block 332. Referring to FIG. 8, the user is informed that Error 5 has been detected. See block 605. Then, one or more steps are modified to create a data flow path from the beginning of the iteration loop to the end to either remove the iteration loop if one should not exist, or to modify the iteration loop such that it converges. See block 615. This is accomplished by the user either determining that the iteration loop should not exist, or adding data items to some steps, which will send data from the starting step to the ending step. If, at step 620, it was possible to correct the non-converging iteration, processing is returned with no error to block 332 in FIG. 3B. See block 625. If, on the other hand, it was not possible to correct the non-converging iteration at block 630, processing is returned with an error to block 332 in FIG. 3B. Alternatively, the return with error could be to block 245 of FIG. 2A. Returning to FIG. 3B, if at block 330, no non-converging iteration was detected or after a return from error correction processing at block 332, processing proceeds to block 334. At block 334, each process step which has a data item which is in both its OUTPUTS list and also in the INITIAL INPUTS list of another process step is analyzed for any inconsistent iteration. If a valid iteration relationship exists between two steps, as well as a normal output to input relationship, the relationship is inconsistent. This happens when step B generates data for initial inputs of step A as well as for inputs of step A. One case implies that step B should come after step A in the sequence and the other case implies the opposite. If, at block 334, an inconsistent iteration is detected, error correction processing depicted in FIG. 9 is initiated. Referring to FIG. 9, the user is informed that Error 6 has been detected. See block 655. Next, at block 660, the OUTPUTS list of the last step of the iteration loop is analyzed to search for data items which are also in the INPUTS list of the first step of the iteration loop. At block 665, the data items which are common to the OUTPUTS list of the last step of the iteration loop and the INPUTS list of the first step of the iteration loop are presented to the user. If the established iteration data items are valid from the user's standpoint, it may be that the other items were simply overlooked. This can be remedied by changing them to initial inputs, i.e., by moving them to INITIAL INPUTS lists. If the user does not wish to make these data items into initial inputs, then the only choice is to eliminate them or eliminate the iteration. If, at block 670, it was possible for the user to eliminate the inconsistent iteration, processing returns with no error to block 336 in FIG. 3B. See block 675. If, on the other hand, the user was unable to eliminate the inconsistent iteration, at block 680, processing is returned with an error to block 336 in FIG. 3B. Alternatively, the return with error could be to block 245 of FIG. 2A. Returning to FIG. 3B, if, at block 334, no inconsistent iteration was detected, or after a return from error correction processing at block 336, processing proceeds to block 338. At block 338, each process step which has data items in its INITIAL INPUTS list is analyzed for incomplete iteration. During the building of a process, the user can end up with iteration specifications that are not totally consistent. A first type of incomplete iteration is where a data item may be specified as in initial input, but no process step generates the data item. A second type of incomplete iteration is when a data item may be specified as an initial output, but no step uses it as an initial input, nor does any step generate it as an output. If an incomplete iteration is detected, processing proceeds to the error correction processing depicted in FIG. 10. Referring to FIG. 10, the user is informed that Error 7 has been detected. See block 705. At block 710, addressing the first type of incomplete iteration, the INITIAL INPUTS list is searched for data items that do not appear in any OUTPUTS list. Incomplete iteration information is presented to the user to make modifications in order to eliminate the situation. See block 715. This may be done by the user selecting a process step as the generator for the data item and placing that data item in the OUTPUTS list of the selected process step. Additionally, to address the second type of incomplete iteration at block 710, the INITIAL OUTPUTS list is searched for any data items that do not appear in any INITIAL INPUTS list. This incomplete iteration information is presented to the user to make modifications to eliminate the situation. See block 715. This may be done by adding the data item to the INITIAL INPUTS list of another step, or by removing it from the INITIAL OUTPUTS list. If, at block 720, it was possible for the user to make the necessary modifications, processing returns with no error to block 340 in FIG. 3B. See block 725. If, on the other hand, it was not possible for the user to eliminate the incomplete iteration, processing returns with an error to block 340 in FIG. 3B. See block 730. Alternatively, the return with error could be to block 245 of FIG. 2A. Returning to FIG. 3B, if, at block 338, no incomplete iteration was detected, or after a Return from error correction processing at block 340, processing returns to block 245 in FIG. 2A. See block 342. Returning to FIG. 2A, once all errors have been corrected at block 245, a final data-driven sequencing phase depicted in FIG. 2B is entered. Referring to FIG. 2B, final sequencing is essentially the same as initial sequencing, except that Inconsistent Iteration errors have already been addressed. Final sequencing occurs as described for the trial data-driven sequencing phase described above, with the resulting sequence being the final data-driven sequence. While the error processing has been described to process for Errors 1-7 shown in Table 1, other embodiments of the present invention may additionally or alternatively process for overlapping iterations and intersecting iterations (not shown). An overlapping iteration is present when the start and end points of one iteration loop completely surround the start and end points of another loop. In other words, one loop is completely nested within the other loop. The primary problem with this situation is that the inside loop may be re-executed each time the outside loop is executed. The user may control the schedule impact of overlapping iterations by specifying a weak or strong coupling between the loops. Weak coupling means that re-entering the inside loop will never cause it to iterate; strong coupling means that re-entering the inside loop will always cause it to iterate. Intersecting iteration is present when the beginning of one iteration loop is inside a second iteration loop, but the end of the second loop is outside the first iteration loop. The primary problem with this situation is that the first loop may be re-executed each time the second loop is executed. The user may control the schedule impact of intersecting iterations by specifying a weak or strong coupling between the loops. Weak coupling means that re-entering the first loop from the second loop will never cause it to iterate; strong coupling means that re-entering the first loop from the second will always cause it to iterate. Overlapping iteration and intersecting iterations will not prevent data-driven sequencing, but should be considered because they may result in undesirable scheduling implications. While the preferred embodiment of the invention has been illustrated and described, it will be appreciated that within the scope of the appended claims various changes can be made therein without departing from the spirit of the invention.
|
Same subclass Same class Consider this |
||||||||||