Managing computing resources in graph-based computations

• US 20070271381A1
• Filed: 05/16/2006
• Published: 11/22/2007
• Est. Priority Date: 05/16/2006
• Status: Active Grant

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Inventors: Vishniac, Ephraim Meriwether, Sherb, Igor, Wholey, Joseph Skeffington
• Granted Patent: US 7,870,556 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Executing graph-based computations includes: accepting a specification of a computation graph in which data processing elements are joined by linking elements; dividing the data processing elements into sets, at least one of the sets including multiple of the data processing elements; assigning to each set a different computing resource; and processing data according to the computation graph, including performing computations corresponding to the data processing elements using the assigned computing resources.

Claims

1. A method for executing graph-based computations, the method including:

accepting a specification of a computation graph in which data processing elements are joined by linking elements;

dividing the data processing elements into sets, at least one of the sets including multiple of the data processing elements;

assigning to each set a different computing resource; and

processing data according to the computation graph, including performing computations corresponding to the data processing elements using the assigned computing resources.

2. The method of claim 1, wherein at least one computing resource assigned to a set includes a process.

3. The method of claim 1, wherein each of the linking elements is associated with a data flow from an output of an upstream data processing element to an input of a downstream data processing element

4. The method of claim 3, wherein processing the data includes, for at least one of the sets performing computations corresponding to the data processing elements in the set according to a sequence defined by linking elements joining the data processing elements in the set.

5. The method of claim 4, wherein a computing resource assigned to a set passes work elements associated with a data flow from an output of an upstream data processing element to an input of a downstream data processing element in the same set as the upstream data processing element by calling a function associated with the downstream data processing element.

6. The method of claim 5, wherein the function reads the work elements from a storage location in which the work elements were written by a function associated with the upstream data processing element.

7. The method of claim 6, wherein the function associated with the upstream data processing element and the function associated with the downstream data processing element are invoked by the same process.

8. The method of claim 1, wherein processing data further includes maintaining information characterizing respective quantities of activity associated with the individual data processing elements in each set.

9. The method of claim 8, wherein the respective quantities of activity include quantities of data processed according to the respective data processing elements.

10. The method of claim 8, wherein the respective quantities of activity include amounts of time spent by a computing resource assigned to a set performing computations corresponding to the respective data processing elements.

11. The method of claim 1, wherein the data processing elements in a set form a connected directed subgraph of the computation graph.

12. The method of claim 11, wherein the subgraph includes a tree.

13. The method of claim 11, wherein for each data processing element in a set that has multiple inputs, all of the upstream data processing elements linked to the inputs of that data processing element are also in the set.

14. The method of claim 11, further including, in response to receiving a control message for a data processing element in the subgraph that does not have an upstream element in the subgraph, calling functions associated with each of the other data processing elements in the subgraph to save state information for each data processing element in the subgraph in non-volatile storage before propagating the control message outside of the subgraph.

15. The method of claim 14, wherein the state information for each of the data processing elements in the subgraph is saved in a single file.

16. The method of claim 1, wherein the data processing elements have a specified degree of parallelism.

17. The method of claim 16, wherein each of the data processing elements in a set have the same degree of parallelism.

18. The method of claim 1, wherein the specification of the computation graph indicates a phase of execution associated with each of the data processing elements.

19. The method of claim 18, wherein each of the data processing elements in a set are associated with the same phase of execution.

20. A computer program, stored on a computer-readable medium, for executing graph-based computations, the computer program including instructions for causing a computer system to:

accept a specification of a computation graph in which data processing elements are joined by linking elements;

divide the data processing elements into sets, at least one of the sets including multiple of the data processing elements;

assign to each set a different computing resource; and

process data according to the computation graph, including performing computations corresponding to the data processing elements using the assigned computing resources.

21. The computer program of claim 20, wherein at least one computing resource assigned to a set includes a process.

22. The computer program of claim 20, wherein processing data further includes maintaining information characterizing respective quantities of activity associated with the individual data processing elements in each set.

23. A system for executing graph-based computations, the system including:

a pre-execution module including circuitry to

accept a specification of a computation graph in which data processing elements are joined by linking elements, and

divide the data processing elements into sets, at least one of the sets including multiple of the data processing elements; and

an execution module including circuitry to

assign to each set a different computing resource, and

process data according to the computation graph, including performing computations corresponding to the data processing elements using the assigned computing resources.

24. The system of claim 23, wherein at least one computing resource assigned to a set includes a process.

25. The system of claim 23, further including a runtime monitoring module including circuitry to maintain information characterizing respective quantities of activity associated with the individual data processing elements in each set.

26. A system for executing graph-based computations, the system including:

means for accepting a specification of a computation graph in which data processing elements are joined by linking elements;

means for dividing the data processing elements into sets, at least one of the sets including multiple of the data processing elements;

means for assigning to each set a different computing resource; and

means for processing data according to the computation graph, including performing computations corresponding to the data processing elements using the assigned computing resources.

27. The system of claim 26, wherein at least one computing resource assigned to a set includes a process.

28. The system of claim 26, further including means for maintaining information characterizing respective quantities of activity associated with the individual data processing elements in each set.