Allocation of resources for tiers of a multi-tiered system based on selecting items from respective sets

• US 9,021,094 B1
• Filed: 04/28/2005
• Issued: 04/28/2015
• Est. Priority Date: 04/28/2005
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Zhou, Yunhong, Kothari, Anshul, Swaminathan, Ram, Tarjan, Robert E.
• Primary Examiner(s): SCOTT, RANDY A
• Application Number:
  US11/116,728
• Time in Patent Office: 3,652 Days
• Field of Search: 709/223, 709/224, 709/225, 709/226, 709/203, 705/5, 705/6, 705/7
• US Class Current: 709/226
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Plural sets of items corresponding to plural tiers of a multi-tiered system are defined, where the items represent amounts of resources to allocate to the tiers. Items from respective sets are selected based on a response time constraint and a target cost. Information is provided pertaining to allocation of amounts of resources to the respective tiers based on the selected items.

Claims

1. A method comprising:

defining, for a multi-choice knapsack problem, plural sets of items corresponding to plural tiers of a multi-tiered system, the items of each of the plural sets representing different amounts of resources to allocate to a corresponding one of the tiers, the defining comprising associating weights and costs with respective items, wherein a weight represents a response time for the amount of resources represented by the corresponding item, and a cost represents a cost of the amount of resources represented by the corresponding item, and wherein increasing the amount of resources allocated to each of the tiers causes a capacity of the corresponding tier to increase, wherein the amounts of resources are selected from the group consisting of;

(1) numbers of servers, and (2) numbers of central processing units (CPUs);

selecting, by one or more processors, items from the respective sets based on a response time constraint and a target cost, an item selected from a first of the plural sets specifying a respective amount of resources to allocate to a first of the plural tiers, and an item selected from a second of the plural sets specifying a respective amount of resources to allocate to a second of the plural tiers, the first set containing items for the first tier, and the second set containing items for the second tier;

providing, by the one or more processors, information pertaining to allocation of amounts of resources for the respective tiers based on the selected items;

scaling the costs in the sets, wherein scaling the costs comprises;

dividing the costs by a factor, wherein the costs divided by the factor produce fractional numbers,

rounding up the fractional numbers to provide the scaled costs; and

removing items having duplicate scaled costs to reduce sizes of the sets.

2. The method of claim 1, wherein selecting the items from the respective sets is based on solving the multi-choice knapsack problem.

3. The method of claim 1, wherein providing the information pertaining to allocation of amounts of resources based on selecting items associated with scaled costs comprises providing information pertaining to an approximate solution including allocation of amounts of resources to the respective tiers, the approximate solution associated with a total cost that is greater than a total cost associated with an optimal solution.

4. The method of claim 1, further comprising:

for at least one of the tiers, defining a lower bound value regarding an amount of resources and an upper bound value regarding an amount of resources,

wherein defining the set of items for a particular one of the tiers comprises defining the set for the particular tier to exclude items associated with amounts of resources less than the lower bound value or greater than the upper bound value.

5. The method of claim 4, wherein defining the lower bound value is based on a response time constraint.

6. The method of claim 4, wherein defining the upper bound value is based on a solution of an approximate server allocation algorithm that provides a solution having a cost less than twice an optimal cost value.

7. The method of claim 4, wherein the multi-tiered system has k tiers, wherein defining the lower bound value comprises defining a lower bound value having value

8. The method of claim 7, wherein defining the upper bound value comprises defining the upper bound value having value C^r−

Σ

<sub>j|j≠

i</sub>h_jn_j^l, where C^r represents a cost of an approximate solution produced by an approximate resource allocation algorithm, h₁ represents a cost of a resource at tier j, h_i represents a cost of a resource at tier i, and n_j^l represents the lower bound value.

9. The method of claim 1, wherein the defining, selecting, and providing are parts of a resource allocation algorithm, the method further comprising executing the server allocation algorithm in polynomial time.

10. The method of claim 9, wherein the resource allocation algorithm normally runs in exponential time, the method further comprising setting upper bounds for numbers of items in respective sets to enable the resource allocation algorithm to run in the polynomial time.

11. The method of claim 2, further comprising building a dynamic programming table having plural rows corresponding to the plural tiers, wherein solving the multi-choice knapsack problem uses the dynamic programming table, wherein the dynamic programming table has cells representing respective response times and has columns corresponding to respective costs associated with corresponding amounts of resources in respective tiers.

12. The method of claim 11, wherein the amounts of resources in respective tiers comprise numbers of servers in respective tiers, and wherein building the dynamic programming table comprises building a dynamic programming table having C^r columns, where C^r represents a total cost of an approximate server allocation algorithm.

13. A method comprising:

defining, for a multi-choice knapsack problem, plural sets of items corresponding to plural tiers of a multi-tiered system, the items representing corresponding numbers of servers to allocate to the tiers, the defining comprising associating weights and costs with respective items, wherein a weight represents a response time for the number of servers represented by the corresponding item, and a cost represents a cost of the number of servers represented by the corresponding item, each of the items of a first of the plural sets representing a corresponding different number of servers to allocate to a first of the tiers, and each of the items of a second of the plural sets representing a corresponding different number of servers to allocate to a second of the tiers;

selecting, based on solving the multi-choice knapsack problem by one or more processors, items from the respective sets based on a response time constraint and a target cost, wherein the selecting is based on an objective to pick one item from each of the plural sets according to an aggregate calculated on attribute values associated with corresponding ones of the items;

providing, by the one or more processors, information pertaining to allocation of numbers of servers for the respective tiers based on the selected items;

scaling the costs in the sets, wherein scaling the costs comprises;

dividing the costs by a factor, wherein the costs divided by the factor produce fractional numbers,

rounding up the fractional numbers to provide the scaled costs; and

removing items having duplicate scaled costs to reduce sizes of the sets.

14. A non-transitory machine-readable storage medium storing instructions that when executed effect resource allocation for a system having plural tiers, the resource allocation comprising:

providing, for a multi-choice knapsack problem, plural sets of items corresponding to the plural tiers of the system, wherein the items represent corresponding numbers of servers to allocate to the corresponding tiers, the defining comprising associating weights and costs with respective items, wherein a weight represents a response time for the number of servers represented by the corresponding item, and a cost represents a cost of the number of servers represented by the corresponding item;

selecting, based on solving the multi-choice knapsack problem, items from the respective sets based on a response time constraint and a target cost;

providing information pertaining to allocation of numbers of servers to respective ones of the plural tiers based on the selected items; and

scaling the costs in the sets, wherein scaling the costs comprises;

dividing the costs by a factor, wherein the costs divided by the factor produce fractional numbers,

rounding up the fractional numbers to provide the scaled costs; and

removing items having duplicate scaled costs to reduce sizes of the sets.

15. The machine-readable storage medium of claim 14, wherein an item selected from a first of the plural sets specifies a number of servers to allocate to a first of the tiers, and wherein an item selected from a second of the plural sets specifies a number of servers to allocate to a second of the tiers.

16. A system comprising:

at least one processor; and

a resource allocation module executable on the at least one processor to;

define, for a multi-choice knapsack problem, plural sets of items corresponding to plural tiers of a multi-tiered system, the items of each of the plural sets representing different amounts of resources to allocate to a corresponding one of the respective tiers, the defining comprising associating weights and costs with respective items, wherein a weight represents a response time for the amount of resources represented by the corresponding item, and a cost represents a cost of the amount of resources represented by the corresponding item, and wherein increasing the amount of resources allocated to each of the tiers causes a capacity of the corresponding tier to increase, and wherein a first of the plural sets contains items for a first of the plural tiers, and a second of the plural sets contains items for a second of the plural tiers;

select, by solving the multi-choice knapsack problem, items from respective sets based on a response time constraint time and an optimal cost, wherein an item selected from the first set specifies a respective amount of resources to allocate to the first tier, and wherein an item selected from the second set specifies a respective amount of resources to allocate the a second tier;

provide information pertaining to allocation of amounts of resources to the respective tiers based on the selected items;

scaling the costs in the sets, wherein scaling the costs comprises;

dividing the costs by a factor, wherein the costs divided by the factor produce fractional numbers,

rounding up the fractional numbers to provide the scaled costs; and

removing items having duplicate scaled costs to reduce sizes of the sets.