Method and apparatus for workflow validation and execution

• US 9,158,585 B2
• Filed: 11/29/2013
• Issued: 10/13/2015
• Est. Priority Date: 03/02/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aharoni, Ehud, Goldschmidt, Ya'ara, Lavee, Tamar, Neuvirth-Telem, Hani
• Primary Examiner(s): Truong, Camquy
• Application Number:
  US14/093,092
• Publication Number:
  US 20140089927A1
• Time in Patent Office: 683 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• 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: G06Q 10/103 Workflow collaboration or project management

Abstract

A computer program product comprising: a non-transitory computer readable medium; and a description of a first block comprising: a definition of one or more output port groups each comprising one or more output ports; a definition of two or more input ports, the input ports receive object streams of identical length; one or more instructions for processing input data received in the input ports and for outputting processed data in the output port groups, wherein the instructions are operative to output a same number of output objects to each output port in a same output port group, whereby the output ports of the output port group are operative to output objects stream of identical length, and wherein the instructions are operative to receive a same number of input objects from each input port, whereby the input ports are operative to receive object streams of identical length; and an indication of whether there is a constant ratio between a number of items in input streams received by the first block and a number of items in output streams outputted by the first block; and wherein said description of a first block is stored on said non-transitory computer readable medium.

Claims

1. A computer program product comprising,

a non-transitory computer readable medium;

and

a description of a first block comprising;

a definition of at least one output port group comprising one or more output ports;

a definition of at least two input ports, the at least two input ports receive object streams of identical length;

at least one instruction for processing input data received in the at least two input ports and for outputting processed data in the at least one output port group,

wherein the at least one instruction is operative to output a same number of output objects to each output port in a same output port group, whereby the output ports of the output port group are operative to output objects stream of identical length, and

wherein the at least one instruction is operative to receive a same number of input objects from each input port, whereby the at least two input ports are operative to receive object streams of identical length; and

an indication of whether there is a constant ratio between a number of items in input streams received by the first block and a number of items in output streams outputted by the first block; and

wherein said description of a first block is stored on said non-transitory computer readable medium;

wherein the non-transitory computer readable medium stores;

a workflow comprising at least the first block and a second block, the second block complying with the block description; and

an instruction for validating that the workflow can operate properly, using the constant ratio,

wherein during execution, each of the first block and the second block can keep an internal state and request to receive again data previously received as input.

2. The computer program product of claim 1 wherein:

execution of the workflow comprises processing data by at least one of the first block or the second block,

execution is performed until all blocks in the workflow finished processing, and

if the first block or the second block requests to receive again data previously received as input, the first block or the second block receive the data and re-perform the at least one instruction over the data with the internal state as kept.

3. The computer program product of claim 2 wherein no data overflow occurs between the first block and the second block during execution.

4. The computer program product of claim 2, wherein executing the workflow comprises repeating the following steps until all blocks are closed:

if there is a block that is entitled for a step, the block perform a step; and

otherwise perform;

determine at least one block that requires another iteration;

determine all upstream blocks of the at least one block; and

reset all upstream blocks.

5. The computer program product of claim 4, wherein a non-source block is closed when it has finished processing its input stream, received a delimiter and did not request to receive its input again.

6. The computer program product of claim 4, wherein a non-source block is entitled to a step if there is at least one object in each of its input ports, and wherein a non-sink block is entitled to a step if there are no objects at queues associated with any of its output ports.

7. The computer program product of claim 1, wherein none of the first block or the second block is required to store its inputs in memory.

8. The computer program product of claim 1, wherein validating that the workflow can operate properly refers to:

no deadlocks may occur between the first block and the second block, and no rate imbalance of information may occur between the first block and the second block.

9. The computer program product of claim 1, wherein:

the first block comprises at least one output port group comprising at least two output ports, wherein the at least two output ports output object streams having identical length, and

the second block comprises at least two input ports, the at least two input ports receive object streams of identical length.

10. The computer program product of claim 1 further comprising validating that:

each of the first block and the second block receives object streams of identical length, and

output ports of an output port group of each of the first block and the second block are operative to output objects stream of identical length.

11. The computer program product of claim 1, wherein validating the workflow comprises:

constructing a graph, wherein the graph is a directed graph and each node in the graph is associated with one block, and an edge exists from a first node to a second node if an output port of a block associated with the first node outputs information received through an input port of a block associated with the second node;

validating that the graph is acyclic;

determining at least one subgraph of the graph; and

validating the at least one subgraph.

12. The computer program product of claim 11, wherein validating the at least one subgraph comprises validating that:

the at least one subgraph has a single root, and

all nodes within the subgraph which are neither a root nor a leaf are associated with blocks that have a ratio of one between the number of input records and the number of output records.

13. The computer program product of claim 11, wherein determining the at least one subgraph comprises:

grouping edges having same rate of data flow; and

determining the at least one subgraph based on each group of edges and nodes adjacent to one edge of the group of edges.

14. The computer program product of claim 13, wherein edges are grouped based on existence of one condition selected from the group consisting of:

the edges are associated with output ports of one output group of one block;

the edges are input into one node; and

one of the edges ends at a node and another of the edges starts at the node, wherein the node is associated with a block whose ratio between the number of input records and the number of output records is one to one.