Determining operator partitioning constraint feasibility

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.

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.

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.