Optimizing Workflow Engines

• US 20120311595A1
• Filed: 08/13/2012
• Published: 12/06/2012
• 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 Ranjan
• Granted Patent: US 9,003,425 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• 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

Techniques for implementing a workflow are provided. The techniques 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-implemented method for implementing a workflow, wherein the method comprises:

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.

2. The method 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.

3. The method 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.

4. The method of claim 1, wherein merging a workflow comprises:

identifying two or more similar jobs;

marking the two or more similar jobs with a same label; and

assigning the two or more similar jobs to a same virtual node.

5. The method 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 method of claim 5, wherein maximizing a number of nodes in the two or more DAGs having a same numerical label comprises searching for an unmapped node with a same computation as a mapped node.

7. The method of claim 1, wherein using a message passing scheme to implement a computation via the one or more physical nodes comprises:

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

putting the message in a corresponding buffer;

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.

8. The method of claim 7, wherein beginning a process of executing the message comprises:

finding a compute node corresponding to the DAG ID of the message; and

sending the message as a job.

9. The method of claim 1, further comprising using a message passing scheme to queue one or more computations in a node depending on resources and licenses available in the node.

10. The method of claim 1, further comprising using a directory-based system in a virtual node directory to keep track of one or more merging operations that have been performed.

11. The method of claim 10, wherein each directory comprises a buffer corresponding to each DAG identification (ID) to store one or more messages.

12. The method of claim 1, further comprising using a message ID to track one or more messages in one or more merged DAGs.

13. The method of claim 1, further comprising optimizing implementation of the workflow, wherein optimizing implementation of the workflow comprises:

using a cache, wherein the cache saves message contents and a message output; and

servicing a new message from the cache upon arrival of the new message if the new message comprises a value in the cache.

14. The method of claim 1, further comprising providing a system, wherein the system comprises one or more distinct software modules, each of the one or more distinct software modules being embodied on a tangible computer-readable recordable storage medium, and wherein the one or more distinct software modules comprise a directory module, a neighborhood map module, a virtual node map module, a directory cache module, a successor list module, a message buffer module, a message count list module and a virtual node cache module executing on a hardware processor.