Method and system for merging directed acyclic graphs representing data flow codes

• US 8,578,389 B1
• Filed: 05/04/2004
• Issued: 11/05/2013
• Est. Priority Date: 05/04/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Boucher, Michael L.
• Primary Examiner(s): Kawsar, Abdullah Al
• Application Number:
  US10/837,607
• Time in Patent Office: 3,472 Days
• Field of Search: 718/1, 718100-108
• US Class Current: 718/106
• CPC Class Codes: G06F 9/4494 data driven

Abstract

Methods and systems facilitating a programmer to program parts of a program in data flow programming to produce directed acyclic graphs (“DAGs”), and then merge the graphs at runtime for efficiency and scalability. Large merged DAG can typically be processed with greater efficiency than the collection of smaller DAGs. As a result, smaller DAGs may be created while the execution of the program realizes the increased efficiency of executing a larger DAG based on the merging of the smaller DAGs. In accordance with methods and systems consistent with the present invention, a programmer creates individual data flow directed acyclic graphs in a program.

Claims

1. A method in a data processing system, comprising the steps of:

generating a plurality of individual directed acyclic graphs, wherein each of the plurality of individual directed acyclic graphs comprise a plurality of nodes representing executable tasks and each of the plurality of individual directed acyclic graphs comprise dependencies between the plurality of nodes representing the executable tasks;

merging the individual directed acyclic graphs at runtime to create a merged directed acyclic graph, wherein the merged directed acyclic graph includes at least one dependency between nodes from different individual directed acyclic graphs wherein the step of merging the individual directed acyclic graphs at runtime further comprises;

comparing a node in a first one of the individual directed acyclic graphs with a node in a second one of the individual directed acyclic graphs to determine if there is a merged dependency between the compared nodes, and

creating a directed arc in the merged directed acyclic graph to reflect the merged dependency, wherein the merged dependency did not exist in the first one or the second one of the individual directed acyclic graphs individually; and

executing the merged directed acyclic graph while the merged directed acyclic graph is being constructed.

2. The method of claim 1, further comprising the steps of:

inserting a first function in a program to indicate a first of the generated individual directed acyclic graphs to be merged; and

inserting a second function in the program to indicate a last of the individual generated directed acyclic graphs to be merged.

3. The method of claim 2, wherein the step of merging the individual directed acyclic graphs at runtime further comprises the step of:

merging at runtime the individual directed acyclic graphs between the indicated first individual directed acyclic graph and last individual directed acyclic graph.

4. The method of claim 1, wherein the comparing step further includes:

comparing each node in the first one of the individual directed acyclic graphs with each node in the second one of the individual directed acyclic graphs to determine if there are dependencies between the compared nodes.

5. A data processing system, comprising:

a memory storing a program that;

generates a plurality of individual directed acyclic graphs, wherein each of the plurality of individual directed acyclic graphs comprise a plurality of nodes representing executable tasks and each of the plurality of individual directed acyclic graphs comprise dependencies between plurality of nodes representing the executable tasks,

merges the individual directed acyclic graphs at runtime to create a merged directed acyclic graph, wherein the merged directed acyclic graph includes at least one dependency between nodes from different individual directed acyclic graphs, and

compares a node in a first one of the individual directed acyclic graphs with a node in a second one of the individual directed acyclic graphs to determine if there is a merged dependency between the compared nodes, and creates a directed arc in the merged directed acyclic graph to reflect the merged dependency, wherein the merged dependency did not exist in the first one or the second one of the individual directed acyclic graphs individually; and

a processor for running the program, wherein the program further executes the merged directed acyclic graph while the merged directed acyclic graph is being constructed.

6. The data processing system of claim 5, further including a second program having a first function in the second program to indicate a first of the generated individual directed acyclic graphs to be merged, and a second function in the second program to indicate a last of the generated individual directed acyclic graphs to be merged.

7. The data processing system of claim 6, wherein the program further merges at runtime the individual directed acyclic graphs between the indicated first individual directed acyclic graph and last individual directed acyclic graph.

8. The data processing system of claim 5, wherein the program further compares each node in the first one of the individual directed acyclic graphs with each node in the second one of the individual directed acyclic graphs to determine if there are dependencies between the compared nodes.

9. A tangible, non-transitory computer-readable medium containing instructions for controlling a data processing system to perform a method, the method comprising the steps of:

generating a plurality of individual directed acyclic graphs, wherein each of the plurality of individual directed acyclic graphs comprise a plurality of nodes representing executable tasks and each of the plurality of individual directed acyclic graphs comprise dependencies between the plurality of nodes representing the executable tasks; and

merging the individual directed acyclic graphs at runtime to create a merged directed acyclic graph, wherein the merged directed acyclic graph includes at least one dependency between nodes from different individual directed acyclic graphs;

comparing each node in a first one of the individual directed acyclic graphs with each node in a second one of the individual directed acyclic graphs to determine if there are merged dependencies between the compared nodes;

creating a directed arc in the merged directed acyclic graph to reflect the merged dependency, wherein the merged dependency did not exist in the first one or the second one of the individual directed acyclic graphs individually; and

executing the merged directed acyclic graph while the merged directed acyclic graph is being constructed.

10. The computer-readable medium of claim 9, wherein the method further comprises the steps of:

inserting a first function in a program to indicate a first of the generated individual directed acyclic graphs to be merged; and

inserting a second function in the program to indicate a last of the generated individual directed acyclic graphs to be merged.

11. The computer-readable medium of claim 10, wherein the step of merging the individual directed acyclic graphs at runtime further comprises the step of:

merging at runtime the individual directed acyclic graphs between the indicated first individual directed acyclic graph and last individual directed acyclic graph.

12. A data processing system, comprising:

means for generating a plurality of individual directed acyclic graphs, wherein each of the plurality of individual directed acyclic graphs comprise a plurality of nodes representing executable tasks and each of the plurality of individual directed acyclic graphs comprise dependencies between the plurality of nodes representing the executable tasks; and

means for merging the individual directed acyclic graphs at runtime to create a merged directed acyclic graph, wherein the merged directed acyclic graph includes at least one dependency between nodes from different individual directed acyclic graphs, wherein the means for merging the individual directed acyclic graphs at runtime is operable to;

compare a node in a first one of the individual directed acyclic graphs with a node in a second one of the individual directed acyclic graphs to determine if there is a merged dependency between the compared nodes, and

create a directed arc in the merged directed acyclic graph to reflect the merged dependency, wherein the merged dependency did not exist in the first one or the second one of the individual directed acyclic graphs individually; and

means for executing the merged directed acyclic graph while the merged directed acyclic graph is being constructed.