Executing computations expressed as graphs

• US 5,966,072 A
• Filed: 07/02/1996
• Issued: 10/12/1999
• Est. Priority Date: 07/02/1996
• Status: Expired due to Term

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Software Corporation
• Inventors: Stanfill, Craig W., Lordi, Robert D., Lasser, Clifford A.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/678,411
• Time in Patent Office: 1,197 Days
• Field of Search: 395/140, 395/141, 345/440, 345/441, 345/133, 345/117, 345/118
• US Class Current: 340/440
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/54 Interprogram communication

Abstract

A method and apparatus by which a graph can be used to invoke computations directly. Methods get information into and out of individual processes represented on a graph, move information between the processes, and define a running order for the processes. An application writer informs a system incorporating the invention how processes should access necessary data. The invention adds "adaptor processes", if necessary, to assist in getting information into and out of processes. In general, in one aspect, a method executes on a computer system a computation expressed as a graph comprising a plurality of vertices representing computational processes, each vertex having an associated access method, and a plurality of links, each connecting at least two vertices to each other and representing a flow of data between the connected vertices, comprising the steps of: (1) accepting the graph into the computer system as user input; (2) preparing the graph for execution by performing, on the computer system, graph transformation steps until each vertex is in a runnable state, and each link is associated with at least one communication method compatible with the access methods of the vertices connected by the link; (3) launching each link by creating, by means of the computer system, a combination of communication channels and/or data stores, as appropriate to the link'"'"'s communication method; and (4) launching each process by invoking execution of the process on the computer system.

Claims

1. A method for executing, on a computer system, a graph expressing a computation having a first vertex representing a first process of the computation, a second vertex representing a second process of the computation, and a link connecting the first vertex to the second vertex and representing a flow of data between the first process and the second process, where the first vertex and second vertex each has a state associated with it, the link has a communication method associated with it, the connection between the first vertex and the link has a first access method associated with it, and the connection between the second vertex and the link has a second access method associated with it, the method comprising:

(a) preparing the graph for execution by performing graph transformation steps on the computer system at least until the first vertex and the second vertex are each in a runnable state, and the link is associated with a particular communication method that is compatible with the first access method and the second access method;

(b) launching the link by creating, by means of the computer system, a combination of communication channels and/or data stores compatible with the communication method of the link; and

(c) launching the first process and the second process by invoking execution of the first process and the second process on the computer system.

2. A method for executing, on a computer system, a graph expressing a computation having a first vertex representing a first process of the computation, a second vertex representing a second process of the computation, and a link connecting the first vertex to the second vertex and representing a flow of data between the first process and the second process, where the first vertex and second vertex each has a state associated with it, the link has a communication method associated with it, the connection between the first vertex and the link has a first access method associated with it, and the connection between the second vertex and the link has a second access method associated with it, the method comprising:

(a) preparing the graph for execution by performing graph transformation steps including steps selected from the group of steps comprising;

inserting a vertex representing a file, inserting a vertex representing a copy process, setting the state of a vertex representing a file to a complete state, setting the state of a vertex representing a process to a runnable state, setting the state of a vertex representing a process to an unrunnable state, and setting a link'"'"'s communication method--at least until the first vertex and the second vertex are each in a runnable state, and the link is associated with a particular communication method that is compatible with the first access method and the second access method;

(b) launching the link by creating, by means of the computer system, a combination of communication channels and/or data stores compatible with the communication method of the link; and

(c) launching the first process and the second process by invoking execution of the first process and the second process.

3. The method of claim 2 where the graph further has a third vertex representing a file used by a process of the computation.

4. The method of claim 3 where the third vertex is a file vertex.

5. The method of claim 2 where the first vertex is a process vertex.

6. The method of claim 2 where the link is a data link.

7. The method of claim 2 where:

(a) the first process and the second process execute on different nodes of a computer system; and

(b) the particular communication method is an inter-processor communication method.

8. The method of claim 7 where the inter-processor communication method is TCP/IP.

9. A method for executing, on a computer system, a graph expressing a computation having a first vertex representing a first process of the computation, a second vertex representing a file read by the first process of the computation, and a link connecting the second vertex to the first vertex and representing a flow of data from the file to the first process, where the first vertex and second vertex each has a state associated with it, the link has a communication method associated with it, the connection between the first vertex and the link has a first access method associated with it, and the connection between the second vertex and the link has a second access method associated with it, the method comprising:

(a) preparing the graph for execution by performing graph transformation steps including steps selected from the group of steps comprising;

inserting a vertex representing a file, inserting a vertex representing a copy process, setting the state of a vertex representing a file to a complete state, setting the state of a vertex representing a process to a runnable state, setting the state of a vertex representing a process to an unrunnable state, and setting a link'"'"'s communication method--at least until the first vertex is in a runnable state and the second vertex is in a complete state, and the link is associated with a particular communication method that is compatible with the first access method and the second access method;

(b) launching the link by creating, by means of the computer system, a combination of communication channels and/or data stores compatible with the communication method of the link; and

(c) launching the first process by invoking execution of the first process.

10. The method of claim 9 where the graph further has a third vertex representing a file used by a process of the computation.

11. The method of claim 10 where the third vertex is a file vertex.

12. The method of claim 9 where the first vertex is a process vertex.

13. The method of claim 9 where the link is a data link.

14. The method of claim 9 where:

(a) the first process and the second process execute on different nodes of a computer system; and

(b) the particular communication method is an inter-processor communication method.

15. The method of claim 14 where the inter-processor communication method is TCP/IP.

16. A method for executing, on a computer system, a graph expressing a computation comprising a plurality of vertices representing computational processes, each vertex having an associated access method, and a plurality of links, each link connecting at least two vertices to each other and representing a flow of data between the connected vertices, comprising the steps of:

(a) accepting the graph into the computer system as user input;

(b) preparing the graph for execution by performing, on the computer system, graph transformation steps until at least some vertices are in a runnable state, and each link connecting such runnable state vertices are associated with a communication method compatible with the access methods of the runnable state vertices connected by the link;

(c) launching each link having an associated communication method by creating, by means of the computer system, a combination of communication channels and/or data stores compatible with the communication method of the link;

(d) launching each runnable state process by invoking execution of the process on the computer system; and

(e) repeating steps (b) through (d) until the entire computation expressed as a graph is executed on the computer system.

17. A system for executing, on a computer system, a graph expressing a computation the graph having links connecting vertices, process vertices each representing a process, and file vertices each representing a file, the system comprising:

(a) means for preparing the graph for execution;

(b) means for launching links of the graph; and

(c) means for launching processes represented by vertices of the graph.

18. The system of claim 17 where the means for preparing the graph for execution includes:

(a) means for inserting at least one vertex representing a file;

(b) means for inserting at least one vertex representing a copy process;

(c) means for setting the state of at least one vertex representing a file to a complete state;

(d) means for setting the state of at least one vertex representing a process to a runnable state;

(e) means for setting the state of at least one vertex representing a process to an unrunnable state; and

(f) means for setting a link'"'"'s communication method.