System and method for dependent failure-aware allocation of distributed data-processing systems

• US 8,122,281 B2
• Filed: 04/13/2007
• Issued: 02/21/2012
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: International Business Machines SA (International Business Machines Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Bansal, Nikhil, Bhagwan, Ranjita, Park, Yoonho, Venkatramani, Chitra
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): BUTLER, SARAI E
• Application Number:
  US11/735,026
• Publication Number:
  US 20080256149A1
• Time in Patent Office: 1,775 Days
• Field of Search: 714 1- 57, 370/216, 370/233, 370/237, 370/325, 706/14, 709223-238
• US Class Current: 714/3
• CPC Class Codes: G06F 11/202 where processing functionality is redundant redundant communication control functionality G06F11/2005, redundant storage control functionality G06F11/2089
• CPC Class Codes: G06F 9/5044 considering hardware capabilities

Abstract

A system and method for allocating distributed processing systems includes inputting component descriptions in a distributed processing system and determining importance of each component. Capacity and failure characteristics of resource groups representing units of available processing capacity are also input. Components are assigned to a plurality of resource groups based on the capacity. Each resource group includes components where the failure characteristics permit simultaneous failures, such that in the event of such failures, an output value of the application is maximized.

Claims

1. A method for allocating distributed processing systems, comprising:

inputting an application graph having component descriptions and connections between the components in a distributed processing system;

determining an importance of each component;

inputting capacity of groups representing units of available processing capacity and failure characteristics associated with the units; and

assigning components based on importance and resource requirements, to a plurality of resource groups based on the capacity of the resource groups where failure characteristics of each resource group permit simultaneous failure, such that in the event of a failure, an output value is attainable,

wherein assigning components includes continuously selecting an unassigned component with a highest importance that is directly connected to an already-assigned component in the application graph.

2. The method as recited in claim 1, wherein inputting component descriptions includes inputting a data-flow graph topology of an application including components and interconnections associated with the components.

3. The method as recited in claim 1, wherein inputting component descriptions includes inputting a value of individual inputs to an application.

4. The method as recited in claim 1, wherein inputting component descriptions includes inputting operations performed by each component.

5. The method as recited in claim 1, wherein inputting component descriptions includes inputting resource requirements for each component.

6. The method as recited in claim 1, wherein determining importance of each component includes computing importance based upon a loss of output value of an application if the component fails.

7. The method as recited in claim 1, wherein assigning components includes grouping resources in accordance with failure characteristics associated with the components such that a failure of one component in a group results in a failure of all components in the group.

8. The method as recited in claim 1, wherein the distributed processing system executes an aggregation-based application and assigning components involves minimizing a number of resource groups in each path from a leaf to a sink.

9. The method as recited in claim 1, wherein components are continuously assigned to a resource group with a highest, available capacity until there is either insufficient resources or until there are no remaining components left to assign.

10. A computer program product for allocating distributed processing systems comprising a non-transitory computer readable storage medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:

inputting an application graph having component descriptions and connections between the components in a distributed processing system;

determining an importance of each component;

inputting capacity of groups representing units of available processing capacity and failure characteristics associated with the units; and

assigning components based on importance and resource requirements, to a plurality of resource groups based on the capacity of the resource groups where the failure characteristics of each resource group permit simultaneous failure, such that in the event of a failure, an output value is attainable,

wherein assigning components includes continuously selecting an unassigned component with a highest importance that is directly connected to an already-assigned component in the application graph.

11. The computer program product as recited in claim 10, wherein inputting component descriptions includes inputting a data-flow graph topology of an application.

12. The computer program product as recited in claim 10, wherein inputting component descriptions includes inputting a value of individual inputs to an application.

13. The computer program product as recited in claim 10, wherein inputting component descriptions includes inputting operations performed by each component.

14. The computer program product as recited in claim 11, wherein determining importance of each component includes traversing the data-flow graph topology of an application to determine correlated failure-aware allocations.

15. The computer program product as recited in claim 10, wherein assigning components includes grouping resources in accordance with failure characteristics associated with the components such that a failure of one component in the group results in the failure of all components in the group.

16. The computer program product as recited in claim 10, wherein determining importance of each component includes computing importance based upon a loss of output value of an application if the component fails.

17. A method for allocating distributed processing systems, comprising:

inputting an application graph having component descriptions and connections between the components in a distributed processing system;

determining importance of each component;

determining capacity of groups representing units of available processing capacity;

assigning components to a plurality of resource groups based on the capacity of each resource group, wherein assigning includes;

continuously selecting an unassigned component with a highest importance that is directly connected to an already-assigned component in the application graph;

grouping components in accordance with failure characteristics associated with the components such that a failure of one component in the group results in the failure of all components in the group; and

optimizing output value such that in the event of failures of resource groups, the output value is attainable.

18. The method as recited in claim 17, wherein the component descriptions include at least one of:

a data-flow graph topology of an application;

a value of individual inputs to an application;

operations performed by a component;

resource requirements for a component, and relationships with other components.

19. The method as recited in claim 17, wherein determining importance of each component includes computing importance based upon a loss of output value of an application if the component fails.

20. A computer program product for allocating distributed processing systems comprising a non-transitory computer readable storage medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform the steps recited in claim 17.