Data-driven process generator

• US 6,141,776 A
• Filed: 04/29/1998
• Issued: 10/31/2000
• Est. Priority Date: 04/29/1998
• Status: Expired due to Term

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Grose, David Lee, Redhed, David Dicken
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): ELISCA, PIERRE E
• Application Number:
  US09/070,115
• Time in Patent Office: 916 Days
• Field of Search: 714/37, 714/36, 714/38, 714/39, 714/48, 714/50, 714/746, 714/758, 714/791, 717/5, 717/6, 717/7, 717/8, 717/9, 712/241, 395/707, 395/708, 395/709, 395/712
• US Class Current: 714/37
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

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

1. A method for analyzing a sequence of process steps to determine whether the process steps can be re-sequenced as a data-driven process, the method comprising:

(a) analyzing each process step for pass-through data items;

(b) analyzing each data item output by a process step for redundant data generation;

(c) analyzing each combination of step pairs for tight-loop iteration;

(d) analyzing for implied iteration while creating a sequence of process steps;

(e) analyzing each process step in the sequence having initial input data items for connected iteration;

(f) analyzing each process step in the sequence having initial input data items for non-converging iteration;

(g) analyzing each process step in the sequence having output data items that are initial input data items to another process step for inconsistent iteration;

(h) analyzing each process step in the sequence having initial inputs for incomplete iteration; and

(i) if no pass-through data items, redundant data generation, tightloop iteration, implied iteration, connected iteration, non-converging iteration, inconsistent iteration, or incomplete iteration are detected, indicating that the sequence of process steps can be re-sequenced as a data-driven process.

2. A method for creating a data-driven process from a plurality of process steps, each process step having associated lists of data items which are inputs, initial inputs, outputs, and initial outputs, the method comprising:

(a) analyzing each process step in the sequence to detect passthrough data items;

(b) analyzing each data item output by a process step to detect redundant data generation;

(c) analyzing each combination of step pairs to detect tight-loop iteration;

(d) analyzing each process step in the sequence having initial input data items to detect connected iteration;

(e) analyzing each process step in the sequence having initial input data items to detect non-converging iteration;

(f) analyzing each process step in the sequence having output data items that are initial input data items to another process step to detect inconsistent iteration;

(g) analyzing each process step in the sequence having initial inputs to detect incomplete iteration; and

(h) modifying to eliminate all detected pass-through data items, redundant data generation, tight-loop iteration, connected iteration, non-converging iteration, inconsistent iteration, and incomplete iteration.

3. The method of claim 2, further comprising:

(a1) if a pass-through data item is detected, selecting the data item from one of the input list and the output list of the process step associated with the pass-through data item; and

(a2) deleting the data item from the selected list.

4. The method of claim 2, further comprising:

(b1) if redundant data generation is detected, locating all process steps which generate the data item associated with redundant generation;

(b2) selecting a single process step as the generator for the data item; and

(b3) deleting the data item from the output lists of all the other located process steps.

5. The method of claim 2, further comprising:

(c1) if tight-loop iteration is detected, selecting one process step of the process step pair associated with the tight-loop iteration to be scheduled before the other process step; and

(c2) changing the data items which are inputs to the selected process step to data items which are initial inputs to the selected step.

6. The method of claim 2, further comprising:

(d1) if connected iteration is detected, splitting the process step associated with the connected iteration into two steps;

(d2) sequencing one step at the end of a first iteration loop; and

(d3) sequencing the other substep at the beginning of a second iteration loop.

7. The method of claim 2, further comprising:

(e1) if non-converging iteration is detected, analyzing the process step associated with the non-converging iteration to select one or more process steps which will link the process step associated with the non-converging iteration to the last step of an iteration loop with which the process step associated with the non-converging iteration is associated; and

(e2) modifying the selected process steps to create a data flow path from the beginning of the iteration loop to the end to modify the iteration loop such that it converges.

8. The method of claim 2, further comprising:

(f1) if inconsistent iteration is detected, analyzing all data items which are outputs of process steps associated with the inconsistent iteration loop to locate data items which are also inputs to a first process step of the inconsistent iteration loop; and

(f2) changing the data items located data items from inputs for the first process step of the inconsistent iteration loop to initial inputs.

9. The method of claim 2, further comprising:

(g1) if incomplete iteration is detected, analyzing all data items which are initial inputs to detect those data items which are not generated by any process step;

(g2) selecting a process step to generate each detected data items; and

(g3) adding the detected data items to the outputs lists associated with the selected process steps.

10. A method for creating a data-driven process from a plurality of process steps, the method comprising:

(a) creating a first list comprising all process steps to be sequenced;

(b) processing the first list to correct for errors which would prevent data-driven sequencing;

(c) adding to a second list all data items which are an input to a process step, but are not output by any process step in the first list;

(d) adding to a third list all process steps in the first list for which all input data items are in the second list;

(e) moving all process steps from the third list to a sequenced list as concurrent steps;

(f) adding all data items which are outputs or initial inputs of the concurrent steps to the second list;

(g) deleting the concurrent steps from the first list; and

(h) repeating (d) through (g) until the first list is empty.

11. The method of claim 10, wherein creating a first list comprises:

(a1) collecting all process steps to be sequenced for data-driven processing;

(a2) creating, for each process step to be sequenced;

(1) a list of data items which are inputs to the process step;

(2) a list of data items which are used by the process step as initial values in an iteration loop;

(3) a list of data items which are generated by the process step; and

(4) a list of data items which are created by the process step and used by other process steps as initial inputs; and

(a3) storing the collected process steps as a first list.

12. The method of claim 11, wherein each list of data items comprises a list of names of data items.

13. The method of claim 10, wherein processing the list to correct for errors which would prevent data-driven sequencing comprises:

(b1) analyzing each process step in the sequence for pass-through data items;

(b2) analyzing each data item output by a process step for redundant data generation;

(b3) analyzing each combination of step pairs for tight-loop iteration;

(b4) analyzing each process step in the sequence having initial input data items for connected iteration;

(b5) analyzing each process step in the sequence having initial input data items for non-converging iteration;

(b6) analyzing each process step in the sequence having output data items that are initial input data items to another process step for inconsistent iteration; and

(b7) analyzing each process step in the sequence having initial inputs for incomplete iteration.

14. A method for creating a data-driven process from a plurality of process steps, the method comprising:

(a) creating a first list comprising all process steps to be sequenced, wherein an INPUTS list, an INITIAL INPUTS list, an OUTPUTS list, and an INITIAL OUTPUTS list is created for each process step;

(b) analyzing process steps of the first list and the INPUTS lists, INITIAL INPUTS lists, OUTPUTS lists, and INITIAL OUTPUTS lists of the process steps for errors which would prevent data-driven sequencing;

(c) correcting for errors which would prevent data-driven sequencing;

(d) adding to a second list, all data items which are an input to a process step, but are not output by any process step in the first list;

(e) adding to a third list, all process steps in the first list for which all input data items are in the second list;

(f) moving all process steps from the third list to a sequenced list as steps which may be performed in parallel;

(g) adding all data items which are outputs or initial inputs of the steps which may be performed in parallel to the second list;

(h) deleting the steps which may be performed in parallel from the first list; and

(i) repeating (e) through (h) until the first list is empty.

15. The method of claim 14, wherein analyzing for errors comprises:

(b1) analyzing each process step in the sequence for pass-through data items;

(b2) analyzing each data item output by a process step for redundant data generation; and

(b3) analyzing each combination of step pairs for tight-loop iteration.

16. The method of claim 14, wherein analyzing for errors comprises:

(b1) analyzing each process step in the sequence having initial input data items for connected iteration;

(b2) analyzing each process step in the sequence having initial input data items for non-converging iteration;

(b3) analyzing each process step in the sequence having output data items that are initial input data items to another process step for inconsistent iteration; and

(b4) analyzing each process step in the sequence having initial inputs for incomplete iteration.

17. A method for creating a data-driven process from a plurality of process steps, each process step having associated lists of data items which are inputs, initial inputs, outputs, and initial outputs, the method comprising:

(a) analyzing each process step to detect pass-through data items;

(b) analyzing each data item output by a process step to detect redundant data generation;

(c) analyzing each combination of step pairs to detect tight-loop iteration;

(d) creating a data-driven sequence and concurrently analyzing for implied iteration;

(e) modifying to eliminate all detected implied iteration;

(f) analyzing each process step in the sequence having initial input data items to detect connected iteration;

(g) analyzing each process step in the sequence having initial input data items to detect non-converging iteration;

(h) analyzing each process step in the sequence having output data items that are initial input data items to another process step to detect inconsistent iteration;

(i) analyzing each process step in the sequence having initial inputs to detect incomplete iteration; and

(j) modifying to eliminate all detected pass-through data items, redundant data generation, tight-loop iteration, connected iteration, non-converging iteration, inconsistent iteration, and incomplete iteration.