Determining operator partitioning constraint feasibility

1. A method for determining feasibility of a set of one or more operator partitioning constraints, wherein the method comprises:

receiving one or more sets of operator partitioning constraints, wherein each set of one or more constraints define one or more desired conditions for grouping together of operators into partitions and placing partitions on hosts, wherein each operator is embodied as software that performs a particular function, and wherein said receiving is carried out on a distinct software module executing on a hardware processor;

processing each set of one or more operator partitioning constraints to determine (i) a feasible partitioning of operators into a fusion of operators and (ii) an assignment of the fusion of operators to a host, such that all operator partitioning constraints are satisfied, wherein said processing is carried out on a distinct software module executing on a hardware processor;

creating and outputting one or more candidate partitions and one or more host placements for each set of feasible partitioning constraints, wherein said creating and outputting one or more candidate partitions is carried out on a distinct software module executing on a hardware processor; and

creating and outputting a certificate of infeasibility for each set of infeasible partitioning constraints, wherein the certificate of infeasibility outlines one or more reasons for infeasibility, wherein said creating and outputting a certificate is carried out on a distinct software module executing on a hardware processor, and wherein said outlining comprises:

identifying each operator and constraint causing infeasibility arising from at least one of partition co-location, partition ex-location, partition isolation and host ex-location constraint;

identifying each operator and constraint causing infeasibility arising from at least one of host co-location, resource matching, host ex-location and host isolation; and

identifying a Hall set arising from infeasibility of a bipartite matching problem arising from at least one of host isolation, host ex-location and resource matching constraint.

2. The method of claim 1 , further comprising outputting a message that no conclusion as to feasibility has been reached within a user-specified amount of computation time if a conclusion as to feasibility cannot be reached within the user-specified amount of computation time.

3. The method of claim 1 , wherein the set of one or more operator partitioning constraints comprise at least one of:

resource matching, wherein an operator can be assigned only to a particular subset of hosts;

partition co-location, wherein two or more operators are fused into a same partition;

partition ex-location, wherein two or more operators are fused into separate partitions;

host co-location, wherein two or more operators are assigned to a same host;

host ex-location, wherein two or more operators are assigned to separate hosts;

partition isolation, wherein an operator is fused into a single partition;

host isolation, wherein a partition containing an operator is placed on a host by itself; and

high availability (HA), comprising creating multiple sub-graph replicas with partitions respecting sub-graphs and host ex-location constraints for any partitions in a distinct replica.

4. The method of claim 1 , wherein determining feasibility of the set of one or more operator partitioning constraints comprises:

partition co-location by fusing one or more relevant operators into one or more partial partitions;

checking feasibility with partition and host ex-location constraints;

processing host co-location by bucketing relevant partitions into one or more host buckets;

processing each resource matching constraint by computing one or more intersections of resource matching constraints of operators in individual host buckets; and

processing host ex-location by iterative steps of bookkeeping and a bipartite matching scheme.

5. The method of claim 1 , wherein determining feasibility of the set of one or more operator partitioning constraints comprises determining feasibility of the set of one or more operator partitioning constraints in a heterogeneous processor environment.

6. The method of claim 1 , further comprising deriving one or more induced host level constraints for computed partitions if a feasibility solution can be determined.

7. The method of claim 1 , further comprising relaxing each constraint in an automated, pre-specified order, to automatically find a feasible set of one or more constraints.

8. The method of claim 1 , further comprising providing a user interface and enabling user-control of constraint relaxations and constraint revisions.

9. 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 partition co-location processor module, a partition feasibility checker module, a host co-location processor module, a host feasibility checker module, a bipartite matching algorithm module, a host ex-location checker module, a constraint relaxer module, and an induced host level constraints computer module executing on a hardware processor.

10. A computer program product comprising a tangible computer readable recordable storage memory including computer useable program code for determining feasibility of a set of one or more operator partitioning constraints, the computer program product including:

computer useable program code for receiving one or more sets of operator partitioning constraints, wherein each set of one or more constraints define one or more desired conditions for grouping together of operators into partitions and placing partitions on hosts, wherein each operator is embodied as software that performs a particular function;

computer useable program code for processing each set of one or more operator partitioning constraints to determine (i) a feasible partitioning of operators into a fusion of operators and (ii) an assignment of the fusion of operators to a host, such that all operator partitioning constraints are satisfied;

computer useable program code for creating and outputting one or more candidate partitions and one or more host placements for each set of feasible partitioning constraints; and

computer useable program code for creating and outputting a certificate of infeasibility for each set of infeasible partitioning constraints, wherein the certificate of infeasibility outlines one or more reasons for infeasibility, and wherein said outlining comprises:

identifying each operator and constraint causing infeasibility arising from at least one of partition co-location, partition ex-location, partition isolation and host ex-location constraint:

identifying each operator and constraint causing infeasibility arising from at least one of host co-location, resource matching, host ex-location and host isolation; and

identifying a Halt set arising from infeasibility of a bipartite matching problem arising from at least one of host isolation, host ex-location and resource matching constraint.

11. The computer program product of claim 10 , further comprising computer useable program code for outputting a message that no conclusion as to feasibility has been reached within a user-specified amount of computation time if a conclusion as to feasibility cannot be reached within the user-specified amount of computation time.

12. The computer program product of claim 10 , wherein the set of one or more operator partitioning constraints comprise at least one of:

resource matching, wherein an operator can be assigned only to a particular subset of hosts;

partition co-location, wherein two or more operators are fused into a same partition;

partition ex-location, wherein two or more operators are fused into separate partitions;

host co-location, wherein two or more operators are assigned to a same host;

host ex-location, wherein two or more operators are assigned to separate hosts;

partition isolation, wherein an operator is fused into a single partition;

host isolation, wherein a partition containing an operator is placed on a host by itself; and

high availability (HA), comprising creating multiple sub-graph replicas with partitions respecting sub-graphs and host ex-location constraints for any partitions in a distinct replica.

13. The computer program product of claim 10 , wherein the computer useable program code for determining feasibility of the set of one or more operator partitioning constraints comprises:

computer useable program code for partition co-location by fusing one or more relevant operators into one or more partial partitions;

computer useable program code for checking feasibility with partition and host ex-location constraints;

computer useable program code for processing host co-location by bucketing relevant partitions into one or more host buckets;

computer useable program code for processing each resource matching constraint by computing one or more intersections of resource matching constraints of operators in individual host buckets; and

computer useable program code for processing host ex-location by iterative steps of bookkeeping and a bipartite matching scheme.

14. The computer program product of claim 10 , further comprising computer useable program code for relaxing each constraint in an automated, pre-specified order, to automatically find a feasible set of one or more constraints.

15. The computer program product of claim 10 , wherein the computer useable program code comprises one or more distinct software modules, and wherein the one or more distinct software modules comprise a partition co-location processor module, a partition feasibility checker module, a host co-location processor module, a host feasibility checker module, a bipartite matching algorithm module, a host ex-location checker module, a constraint relaxer module, and an induced host level constraints computer module executing on a hardware processor.

16. A system for determining feasibility of a set of one or more operator partitioning constraints, comprising:

a memory; and

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

receive one or more sets of operator partitioning constraints, wherein each set of one or more constraints define one or more desired conditions for grouping together of operators into partitions and placing partitions on hosts, wherein each operator is embodied as software that performs a particular function;

process each set of one or more operator partitioning constraints to determine (i) a feasible partitioning of operators into a fusion of operators and (ii) an assignment of the fusion of operators to a host, such that all operator partitioning constraints are satisfied;

create and output one or more candidate partitions and one or more host placements for each set of feasible partitioning constraints; and

create and output a certificate of infeasibility for each set of infeasible partitioning constraints, wherein the certificate of infeasibility outlines one or more reasons for infeasibility, and wherein said outlining comprises:

identifying each operator and constraint causing infeasibility arising from at least one of partition co-location, partition ex-location, partition isolation and host ex-location constraint;

identifying each operator and constraint causing infeasibility arising from at least one of host co-location, resource matching, host ex-location and host isolation; and

identifying a Hall set arising from infeasibility of a bipartite matching problem arising from at least one of host isolation, host ex-location and resource matching constraint.

17. The system of claim 16 , wherein the at least one processor coupled to the memory is further operative to output a message that no conclusion as to feasibility has been reached within a user-specified amount of computation time if a conclusion as to feasibility cannot be reached within the user-specified amount of computation time.

18. The system of claim 16 , wherein the set of one or more operator partitioning constraints comprise at least one of:

resource matching, wherein an operator can be assigned only to a particular subset of hosts;

partition co-location, wherein two or more operators are fused into a same partition;

partition ex-location, wherein two or more operators are fused into separate partitions;

host co-location, wherein two or more operators are assigned to a same host;

host ex-location, wherein two or more operators are assigned to separate hosts;

partition isolation, wherein an operator is fused into a single partition;

host isolation, wherein a partition containing an operator is placed on a host by itself; and

high availability (HA), comprising creating multiple sub-graph replicas with partitions respecting sub-graphs and host ex-location constraints for any partitions in a distinct replica.

19. The system of claim 16 , wherein the at least one processor coupled to the memory operative to determine feasibility of the set of one or more operator partitioning constraints is further operative to:

partition co-location by fusing one or more relevant operators into one or more partial partitions;

check feasibility with partition and host ex-location constraints;

process host co-location by bucketing relevant partitions into one or more host buckets;

process each resource matching constraint by computing one or more intersections of resource matching constraints of operators in individual host buckets; and

process host ex-location by iterative steps of bookkeeping and a bipartite matching scheme.

20. The system of claim 16 , wherein the at least one processor coupled to the memory is further operative to relax each constraint in an automated, pre-specified order, to automatically find a feasible set of one or more constraints.

21. The system of claim 16 , further comprising a tangible computer-readable recordable storage medium having one or more distinct software modules embodied thereon, the one or more distinct software modules comprising a partition co-location processor module, a partition feasibility checker module, a host co-location processor module, a host feasibility checker module, a bipartite matching algorithm module, a host ex-location checker module, a constraint relaxer module, and an induced host level constraints computer module executing on a hardware processor.

22. An apparatus for determining feasibility of a set of one or more operator partitioning constraints, the apparatus comprising:

means for receiving one or more sets of operator partitioning constraints, wherein each set of one or more constraints define one or more desired conditions for grouping together of operators into partitions and placing partitions on hosts, wherein each operator is embodied as software that performs a particular function;

means for processing each set of one or more operator partitioning constraints to determine (i) a feasible partitioning of operators into a fusion of operators and (ii) an assignment of the fusion of operators to a host, such that all operator partitioning constraints are satisfied;

means for creating and outputting one or more candidate partitions and one or more host placements for each set of feasible partitioning constraints; and

means for creating and outputting a certificate of infeasibility for each set of infeasible partitioning constraints, wherein the certificate of infeasibility outlines one or more reasons for infeasibility, and wherein said outlining comprises:

identifying each operator and constraint causing infeasibility arising from at least one of partition co-location, partition ex-location, partition isolation and host ex-location constraint;

identifying each operator and constraint causing infeasibility arising from at least one of host co-location, resource matching, host ex-location and host isolation; and

identifying a Hall set arising from infeasibility of a bipartite matching problem arising from at least one of host isolation, host ex-location and resource matching constraint.