Creating Stream Processing Flows from Sets of Rules

• US 20140081896A1
• Filed: 03/09/2011
• Published: 03/20/2014
• Est. Priority Date: 03/09/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ranganathan, Anand, Riabov, Anton V., Udrea, Octavian
• Granted Patent: US 8,856,060 B2
• Time in Patent Office: Days
• US Class Current: 706/48
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

Techniques for creating a distributed application flow from a set of rules are provided. The techniques include creating a control-flow graph for each rule, creating one or more dependency links between two or more rules, partitioning a resulting graph, wherein the resulting graph comprises one or more control-flow graphs and one or more dependency links, into one or more operators by determining an optimal set of one or more cuts through the resulting graph such that a cost function is minimized, and generating stream processing flow code from the partitioned graph.

Claims

1. A method for creating a distributed application flow from a set of rules, wherein the method comprises:

creating a control-flow graph for each rule and creating one or more dependency links between two or more rules;

partitioning a resulting graph, wherein the resulting graph comprises one or more control-flow graphs and one or more dependency links, into one or more operators by determining an optimal set of one or more cuts through the resulting graph such that a cost function is minimized; and

generating stream processing flow code from the partitioned graph.

2. The method of claim 1, further comprising performing one or more optimizations on the resulting graph.

3. The method of claim 2, wherein the one or more optimizations comprise at least one of live variable analysis, constant propagation, constant folding and detection and merging of any identical statements on branches of the graph that are not in an ancestor-descendant relation.

4. The method of claim 2, wherein the one or more optimizations comprise elimination of one or more unnecessary dependency links between two or more rules based on at least one of static analysis and theorem proving.

5. The method of claim 1, wherein the set of rules comprises at least one of stateless rules and stateful rules.

6. The method of claim 5, wherein creating one or more dependency links between two or more rules comprises, for stateful rules, creating one or more dependency links based on pairing at least one of an assert statement a retract statement and an update statement in a first rule with at least one of a match statement and a collect-match statement in a second rule.

7. The method of claim 5, wherein creating one or more dependency links between two or more rules comprises, for stateless rules, creating one or more dependency links based on pairing two or more variables set by a first rule and used by a second rule.

8. The method of claim 1, wherein creating a control-flow graph for each rule comprises analyzing a set of rules and extracting a dependency graph of one or more computation operators from the set of rules.

9. The method of claim 1, wherein a cost function comprises a function for one of throughput, latency, computational and memory requirements, an estimated amount of communication between operators, or a combination thereof.

10. The method of claim 1, wherein a cost function comprises one of a linear cost function, a quadratic cost function and an arbitrary cost function.

11. The method of claim 1, wherein determining an optimal set of one or more cuts through the resulting graph comprises one of creating an equivalent quadratically constrained quadratic program, an equivalent linearly constrained quadratic program or an equivalent integer program, performing an exhaustive search through a set of non-overlapping cuts in a ruleset graph, and performing an incremental cut morphing according to a topological sort of the ruleset graph.

12. 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 ruleset parsing module, a static analysis/optimization module, a partitioning module and a code generation module executing on a hardware processor.

13. A computer program product comprising a tangible computer readable recordable storage medium including computer useable program code for creating a distributed application flow from a set of rules, the computer program product including:

computer useable program code for creating a control-flow graph for each rule and creating one or more dependency links between two or more rules;

computer useable program code for partitioning a resulting graph, wherein the resulting graph comprises one or more control-flow graphs and one or more dependency links, into one or more operators by determining an optimal set of one or more cuts through the resulting graph such that a cost function is minimized; and

computer useable program code for generating stream processing flow code from the partitioned graph.

14. The computer program product of claim 13, further comprising computer useable program code for performing one or more optimizations on the resulting graph, wherein the one or more optimizations comprise at least one of live variable analysis, constant folding and detection and merging of any identical statements on branches of the graph that are not in an ancestor-descendant relation.

15. The computer program product of claim 13, wherein the set of rules comprises at least one of stateless rules and stateful rules.

16. The computer program product of claim 15, wherein the computer useable program code for creating one or more dependency links between two or more rules comprises, for stateful rules, computer useable program code for creating one or more dependency links based on pairing at least one of an assert statement a retract statement and an update statement in a first rule with at least one of a match statement and a collect-match statement in a second rule.

17. The computer program product of claim 15, wherein the computer useable program code for creating one or more dependency links between two or more rules comprises, for stateless rules, computer useable program code for creating one or more dependency links based on pairing two or more variables set by a first rule and used by a second rule.

18. The computer program product of claim 13, wherein a cost function comprises a function for one of throughput, latency, computational and memory requirements, an estimated amount of communication between operators, or a combination thereof.

19. The computer program product of claim 13, wherein the computer useable program code for determining an optimal set of one or more cuts through the resulting graph comprises one of creating an equivalent quadratically constrained quadratic program, an equivalent linearly constrained quadratic program or an equivalent integer program, performing an exhaustive search through a set of non-overlapping cuts in a ruleset graph, and performing an incremental cut morphing according to a topological sort of the ruleset graph.

20. A system for creating a distributed application flow from a set of rules, comprising:

a memory; and

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

create a control-flow graph for each rule and create one or more dependency links between two or more rules;

partition a resulting graph, wherein the resulting graph comprises one or more control-flow graphs and one or more dependency links, into one or more operators by determining an optimal set of one or more cuts through the resulting graph such that a cost function is minimized; and

generate stream processing flow code from the partitioned graph.

21. The system of claim 20, wherein the at least one processor coupled to the memory is further operative to perform one or more optimizations on the resulting graph, wherein the one or more optimizations comprise at least one of live variable analysis, constant folding and detection and merging of any identical statements on branches of the graph that are not in an ancestor-descendant relation.

22. The system of claim 20, wherein the set of rules comprises at least one of stateless rules and stateful rules.

23. The system of claim 22, wherein the at least one processor coupled to the memory operative to create one or more dependency links between two or more rules is further operative to, for stateful rules, create one or more dependency links based on pairing at least one of an assert statement a retract statement and an update statement in a first rule with at least one of a match statement and a collect-match statement in a second rule.

24. The system of claim 22, wherein the at least one processor coupled to the memory operative to create one or more dependency links between two or more rules is further operative to, for stateless rules, create one or more dependency links based on pairing two or more variables set by a first rule and used by a second rule.

25. The system of claim 20, wherein a cost function comprises a function for one of throughput, latency, computational and memory requirements, an estimated amount of communication between operators, or a combination thereof.