System and method for efficiently executing directed acyclic graphs

• US 5,423,040 A
• Filed: 01/14/1994
• Issued: 06/06/1995
• Est. Priority Date: 07/24/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gilley, Glenn G., McAuliff, Kevin P., Epstein, David A.
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): Toplu, Lucien
• Application Number:
  US08/181,457
• Time in Patent Office: 508 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2
• US Class Current: 718/102
• CPC Class Codes: G06F 8/311 Functional or applicative languages; Rewrite languages

Abstract

A system and method for efficiently evaluating and executing unresolved data variables used as input for functional processes in a previously defined acyclic dataflow graph (or sequence of instructions which may be so represented). Embodiments of the present invention also contemplate maintaining previously computed values of data elements so that re-evaluation of the entire data flow graph or portions thereof may not be necessary.

Claims

1. A computer-implemented system for evaluating and executing a plurality of functional processes operating in a directed and acyclical manner, each of the plurality of functional processes receiving one or more data element inputs, the one or more data element inputs including a computed data element having a computed data element value generated by a generating functional process and a constant data element having a constant data element value, the system comprising:

a function cache for storing data element values of the one or more data element inputs;

signature generator means, coupled to said function cache, for generating a signature for each of the data element values, wherein said signature is a function of a selected aspect of the generating functional process and signatures of the data element inputs received by the generating functional process, said signature indicating a location of the data element value in said function cache;

function evaluator means, coupled to said signature generator means and said function cache, for recursively evaluating uncomputed dam elements in a depth-first manner, and for retrieving a previously computed dam element value associated with said uncomputed data element from said function cache when a signature of said previously computed data element value is identical to a signature of said uncomputed data element value; and

functional executor means, coupled to said function evaluator means, for executing the generating functional process when said previously computed data element value associated with said data element does not exist in said function cache.

2. The system of claim 1, wherein said function evaluator means and said function executor means operate in parallel with each other, and wherein said function evaluator means further comprises means for activating said function executor means.

3. The system of claim 1, further comprising:

sequencing means coupled to said signature generator means and said function evaluator means, for imposing an additional sequencing of the one or more functional processes, said additional sequencing indicating which of the one or more data element inputs upon which said one or functional processes do not depend upon.

4. The system of claim 3, wherein said signatures are utilized as keys to locate said data element in said function cache.

5. The system of claim 4, wherein said function evaluator means further comprises means for activating said function executor means.

6. The system of claim 5, further comprising:

a descriptor block associated with each of the data elements, said descriptor block including;

a computational status indicator indicating whether said associated data element is resolved,

wherein said function evaluator means scans said associated descriptor block to determine the computational status of said associated data element.

7. The system of claim 6, wherein said signatures are stored in said descriptor block of the plurality of data elements.

8. A computer-implemented method for evaluating and executing a plurality of functional processes, each of the plurality of functional processes utilizing one or more of a plurality of data elements as inputs, the plurality of functional processes including one or more generating functional processes configured to generate data elements, the generating functional processes having one or more data element inputs, the plurality of functional processes operating in a directed and acyclical manner wherein each of the plurality of data elements inputs utilized by a utilizing functional process is resolved by the one or more generating functional processer which determines an associated value of the data element before the utilizing functional process is processed, the method comprising the steps of:

(a) storing values of each of the plurality of data elements in a functional cache;

(b) generating, by a signal generator coupled to said functional cache, a signature associated with each of the values of the plurality of each data elements, each said signature being a function of a selected aspect of the generating functional process and signatures of all data element inputs to the generating functional process, each said signature identifying a location in said a functional cache of the associated value of the data element;

(c) determining, by a function evaluator coupled to said signal generator, whether data element inputs to a selected generating functional process have constant or computed data element values;

(d) if the data element value is computed, searching said functional cache for a previously computed dam element value associated with said signature, thereby preventing recomputation of previously computed data element values; and

(e) if said previously computed data element value is not located in said functional cache, executing the generating functional process to generate said computed data element value.

9. The method of step 8, wherein said step (c) comprising the steps of:

(1) determining whether said evaluated functional processes are executable, said functional processes being executable when all of the data elements utilized by said particular functional process are resolved;

(2) determining whether each of said executable functional processes is required to be recomputed, wherein a particular functional process is required to be recomputed when said data element inputs are resolved; and

(3) scanning said functional cache and determining if said data element inputs has a previously generated value.

10. The method of step 9, further comprising the step of:

(4) performing said steps (1)-(3) on the plurality of functional processes which generate data elements having values which have changed and which are not available in said function cache.

11. The method of step 10, further comprising the steps of:

(5) automatically updating said signature associated with the one or more data elements by said signature generator means when any relied-upon data elements has changed.

12. The method of step 11, further comprising the steps of:

(6) generating an available status indication associated with said each of the plurality of functional processes, said available status indication indicating whether said each of the plurality of functional processes is executable.