Optimizing workflow engines

• US 8,510,751 B2
• Filed: 03/18/2010
• Issued: 08/13/2013
• Est. Priority Date: 03/18/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Saha, Dhrubajyoti, Sarangi, Smruti R.
• Primary Examiner(s): DAO, TUAN C.
• Application Number:
  US12/726,798
• Publication Number:
  US 20110231849A1
• Time in Patent Office: 1,244 Days
• Field of Search: None
• US Class Current: 719/313
• 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

Abstract

A system and computer program product for implementing a workflow include merging a workflow to create a virtual graph, wherein the workflow comprises two or more directed acyclic graphs (DAGs), mapping each of one or more nodes of the virtual graph to one or more physical nodes, and using a message passing scheme to implement a computation via the one or more physical nodes.

Claims

1. A computer program product comprising a tangible computer readable recordable storage memory including computer useable program code for implementing a workflow, the computer program product including:

computer useable program code for merging a workflow to create a virtual graph, wherein the workflow comprises two or more directed acyclic graphs (DAGs), wherein said merging comprises;

applying a label to each node of the two or more directed acyclic graphs, wherein nodes representing a same computation in each directed acyclic graph have a same label applied thereto;

assigning each node in the two or more directed acyclic graphs with a unique label to a unique node in the virtual graph; and

assigning each node in the two or more directed acyclic graphs that shares the same label with one or more additional nodes are assigned to a same node in the virtual graph;

computer useable program code for mapping each of one or more nodes of the virtual graph to one or more physical nodes; and

computer useable program code for using a message passing scheme to implement a computation via the one or more physical nodes.

2. The computer program product of claim 1, wherein the computer useable program code for using a message passing scheme to implement a computation via the one or more physical nodes comprises:

computer useable program code for parsing a message to determine a DAG identification (ID) of the message;

computer useable program code for putting the message in a corresponding buffer;

computer useable program code for beginning a process of executing a job if a size of the buffer is equal to a number of messages the buffer has to have before beginning its execution.

3. The computer program product of claim 1, wherein merging a workflow to create a virtual graph comprises merging two or more DAGs even if the two or more DAGs do not have a same predecessor.

4. The computer program product of claim 1, wherein merging a workflow to create a virtual graph comprises merging two or more DAGs even if the two or more DAGs do not have a same successor.

5. The computer program product of claim 1, wherein merging a workflow to create a virtual graph comprises maximizing a number of nodes in the two or more DAGs having a same numerical label.

6. The computer program product of claim 1, further comprising computer useable program code for using a message passing scheme to queue one or more computations in a node depending on resources and licenses available in the node.

7. The computer program product of claim 1, further comprising computer useable program code for using a directory-based system in a virtual node directory to keep track of one or more merging operations that have been performed.

8. The computer program product of claim 1, further comprising computer useable program code for using a message ID to track one or more messages in one or more merged DAGs.

9. A system for implementing a workflow, comprising:

a memory; and

at least one processor coupled to the memory and operative to;

merge a workflow to create a virtual graph, wherein the workflow comprises two or more directed acyclic graphs (DAGs), wherein said merging comprises;

applying a label to each node of the two or more directed acyclic graphs, wherein nodes representing a same computation in each directed acyclic graph have a same label applied thereto;

assigning each node in the two or more directed acyclic graphs with a unique label to a unique node in the virtual graph; and

assigning each node in the two or more directed acyclic graphs that shares the same label with one or more additional nodes are assigned to a same node in the virtual graph;

map each of one or more nodes of the virtual graph to one or more physical nodes; and

use a message passing scheme to implement a computation via the one or more physical nodes.

10. The system of claim 9, wherein the at least one processor coupled to the memory operative to use a message passing scheme to implement a computation via the one or more physical nodes is further operative to:

parse a message to determine a DAG identification (ID) of the message;

put the message in a corresponding buffer;

begin a process of executing a job if a size of the buffer is equal to a number of messages the buffer has to have before beginning its execution.

11. The system of claim 9, wherein merging a workflow to create a virtual graph comprises merging two or more DAGs even if the two or more DAGs do not have a same predecessor.

12. The system of claim 9, wherein merging a workflow to create a virtual graph comprises merging two or more DAGs even if the two or more DAGs do not have a same successor.

13. The system of claim 9, wherein merging a workflow to create a virtual graph comprises maximizing a number of nodes in the two or more DAGs having a same numerical label.

14. The system of claim 9, wherein the at least one processor coupled to the memory is further operative to use a message passing scheme to queue one or more computations in a node depending on resources and licenses available in the node.

15. The system of claim 9, wherein the at least one processor coupled to the memory is further operative to use a directory-based system in a virtual node directory to keep track of one or more merging operations that have been performed.

16. The system of claim 9, wherein the at least one processor coupled to the memory is further operative to use a message ID to track one or more messages in one or more merged DAGs.