Resource allocation in partial fault tolerant applications

Abstract

A method for allocating a set of components of an application to a set of resource groups includes the following steps performed by a computer system. The set of resource groups is ordered based on respective failure measures and resource capacities associated with the resource groups. An importance value is assigned to each of the components. The importance value is associated with an affect of the component on an output of the application. The components are assigned to the resource groups based on the importance value of each component and the respective failure measures and resource capacities associated with the resource groups. The components with higher importance values are assigned to resource groups with lower failure measures and higher resource capacities. The application may be a partial fault tolerant (PFT) application that comprises PFT application components. The resource groups may comprise a heterogeneous set of resource groups (or clusters).

1 . A method for allocating a set of one or more processing components of an application to a set of one or more resource groups, comprising the steps performed by a computer system of:
 ordering the set of one or more resource groups based on respective failure measures and resource capacities associated with the one or more resource groups;   assigning an importance value to each of the one or more components, wherein the importance value is associated with an affect of the component on an output of the application; and   assigning the one or more components to the one or more resource groups based on the importance value of each component and the respective failure measures and resource capacities associated with the one or more resource groups, wherein components with higher importance values are assigned to resource groups with lower failure measures and higher resource capacities.   
     
     
         2 . The method of  claim 1 , wherein the application is a partial fault tolerant (PFT) application that comprises a set of one or more PFT application components. 
     
     
         3 . The method of  claim 1 , wherein the set of one or more resource groups comprise a heterogeneous set of resource groups. 
     
     
         4 . The method of  claim 1 , wherein the ordering step comprises sorting the one or more resource groups in a decreasing order based on a ratio of a respective resource capacity of each of the one or more resource groups to a failure probability of each of the one or more resource groups. 
     
     
         5 . The method of  claim 1 , wherein the ordering step comprises sorting the one or more resource groups in a decreasing order based on a product of a respective resource capacity of each of the one or more resource groups and an availability measure of each of the one or more resource groups. 
     
     
         6 . The method of  claim 5 , wherein the availability measure for a given resource group is computed as one minus a failure probability of the given resource group. 
     
     
         7 . The method of  claim 1 , wherein the importance value assigned to a given component is based on a contribution that the given component makes to the application output. 
     
     
         8 . The method of  claim 1 , wherein the importance value assigned to a given component is based on a loss incurred in the application output value if the resource hosting the given component fails. 
     
     
         9 . The method of  claim 1 , wherein the step of assigning the one or more components to the one or more resource groups is also based on one or more specified constraints on the one or more components. 
     
     
         10 . The method of  claim 1 , wherein an order for assigning components is determined based on a data flow graph associated with the application such that a single resource group failure affects the minimal number of paths from a source to a sink in the data flow graph. 
     
     
         11 . The method of  claim 1 , wherein the step of assigning the one or more components to the one or more resource groups is performed responsive to a failure of at least one of the resources, making unavailable at least one of the components assigned thereto. 
     
     
         12 . The method of  claim 1 , wherein the effect of a given component on the output of the application comprises an effect of the given component on an output quality of the application. 
     
     
         13 . The method of  claim 12 , wherein the effect of a given component on the application output quality is based on the given component being in one or more paths of a data flow graph associated with the application. 
     
     
         14 . The method of  claim 1 , wherein the step of assigning the one or more components to the one or more resource groups comprises defining, within a data flow graph associated with the application, a connected sub-graph of components assigned to a given resource group. 
     
     
         15 . An article of manufacture for allocating a set of one or more components of an application to a set of one or more resource groups, the article comprising a non-transitory computer readable storage medium containing one or more programs, which when executed by a computer implement the steps of  claim 1 . 
     
     
         16 . Apparatus for allocating a set of one or more components of an application to a set of one or more resource groups, comprising:
 a memory; and   at least one processor coupled to the memory and operative to perform the steps of:   ordering the set of one or more resource groups based on respective failure measures and resource capacities associated with the one or more resource groups;   assigning an importance value to each of the one or more components, wherein the importance value is associated with an effect of the component on an output of the application; and   assigning the one or more components to the one or more resource groups based on the importance value of each component and the respective failure measures and resource capacities associated with the one or more resource groups, wherein components with higher importance values are assigned to resource groups with lower failure measures and higher resource capacities.   
     
     
         17 . The apparatus of  claim 16 , wherein the application is a partial fault tolerant (PFT) application that comprises a set of one or more PFT application components. 
     
     
         18 . The apparatus of  claim 16 , wherein the ordering step comprises sorting the one or more resource groups in a decreasing order based on a ratio of a respective resource capacity of each of the one or more resource groups to a failure probability of each of the one or more resource groups. 
     
     
         19 . The apparatus of  claim 16 , wherein the ordering step comprises sorting the one or more resource groups in a decreasing order based on a product of a respective resource capacity of each of the one or more resource groups and an availability measure of each of the one or more resource groups. 
     
     
         20 . The apparatus of  claim 16 , wherein the importance value assigned to a given component is based on a contribution that the given component makes to the application output. 
     
     
         21 . The apparatus of  claim 16 , wherein the importance value assigned to a given component is based on a loss incurred in the application output value if the resource hosting the given component fails.