ALLOCATION OF COMPUTATIONAL RESOURCES WITH POLICY SELECTION

• US 20130246208A1
• Filed: 03/16/2012
• Published: 09/19/2013
• Est. Priority Date: 03/16/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jain, Navendu, Menache, Ishai, Shamir, Ohad
• Granted Patent: US 9,652,288 B2
• Time in Patent Office: Days
• US Class Current: 705/26.3
• CPC Class Codes: G06F 2209/501 Performance criteria
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

Abstract

A method for adaptively allocating resources to a plurality of jobs. The method comprises selecting a first policy from a plurality of policies for a first job in the plurality of jobs by using a policy selection mechanism, allocating at least one resource to the first job in accordance with the first policy, and in response to completion of the first job, updating the policy selection mechanism to obtain an updated policy selection mechanism by using at least one processor. Updating the policy selection mechanism comprises evaluating the performance of the first policy with respect to the first job by calculating a value of a metric of utility for the first policy based on conditions associated with execution of the first job and updating the policy selection mechanism based on the calculated value and a delay of execution of the first job.

Claims

1. A method for adaptively allocating resources to a plurality of jobs, the method comprising:

selecting a first policy from a plurality of policies for a first job in the plurality of jobs by using a policy selection mechanism;

allocating at least one resource to the first job in accordance with the first policy; and

in response to completion of the first job, updating the policy selection mechanism to obtain an updated policy selection mechanism by using at least one processor,

wherein updating the policy selection mechanism comprises evaluating the performance of the first policy with respect to the first job by calculating a value of a metric of utility for the first policy based on conditions associated with execution of the first job and updating the policy selection mechanism based on the calculated value and a delay of execution of the first job.

2. The method of claim 1, wherein the method further comprises:

selecting a second policy from the plurality of policies for a second job in the plurality of jobs by using the updated selection mechanism, wherein the second job is different from the first job; and

allocating at least one resource to the second job based on the second policy.

3. The method of claim 1, wherein each policy in the plurality of policies is associated with a weight, and wherein selecting the first policy by using the policy selection mechanism comprises:

selecting the first policy according to a distribution defined by weights corresponding to policies in the plurality of policies.

4. The method of claim 3, wherein updating the policy selection mechanism further comprises updating the distribution defined by the weights corresponding to policies by calculating an updated weight for each policy in the plurality of policies, wherein calculating an updated weight for a particular policy comprises:

calculating a value for a metric of utility with respect to the particular policy based on conditions associated with execution of the first job; and

calculating the updated value based on the calculated value and the delay of execution of the first job.

5. The method of claim 1, wherein the delay of execution of the first job is indicative of a time delay between selecting the first policy for the first job and evaluating the performance of the first policy with respect to the first job.

6. The method of claim 1, wherein the first policy specifies an amount to bid on the at least one resource based on a history of prices for the at least one resource, and wherein

allocating the at least one resource in accordance with the first policy comprises charging the amount for the at least one resource when a bid for the amount is accepted.

7. The method of claim 1, wherein the at least one resource comprises a first resource and a second resource, wherein the first policy specifies purchasing the first resource using on-demand pricing and purchasing the second resource using spot pricing, and wherein:

allocating the at least one resource in accordance with the first policy comprises charging an on-demand price for the first resource.

8. The method of claim 1, wherein the at least one resource is a computing resource of a cloud computing environment.

9. A system for allocating cloud computing platform resources, the system comprising:

at least one processor configured to;

select a first policy from a plurality of policies for a first job in the plurality of jobs by using a policy selection mechanism;

allocate at least one computing resource to the first job in accordance with the first policy; and

in response to completion of the first job, update the policy selection mechanism to obtain an updated policy selection mechanism by using at least one processor,

wherein updating the policy selection mechanism comprises evaluating the performance of the first policy with respect to the first job by calculating a value for a metric of utility for the first policy based on conditions associated with execution of the first job and updating the policy selection mechanism based on the calculated value and a delay of execution of the first job.

10. The system of claim 9, wherein the at least one processor is further configured to:

select a second policy from the plurality of policies for a second job in the plurality of jobs by using the updated policy selection mechanism, wherein the second job is different from the first job; and

allocate at least one computing resource to the second job based on the second policy.

11. The system of claim 10, wherein the at least one processor is configured to update the policy selection mechanism by updating the distribution defined by the weights corresponding to policies by calculating an updated weight for each policy in the plurality of policies, wherein the at least one processor is configured to calculate an updated weight for a particular policy by:

calculating a value for a metric of utility with respect to the particular policy based on conditions associated with execution of the first job; and

calculating the updated value based on the calculated value and the delay of execution of the first job.

12. The system of claim 11, wherein the at least one processor is configured to select the second policy according to a distribution defined by the updated weights.

13. The system of claim 9, wherein the delay of execution of the first job is an upper bound on the number of jobs arriving during execution of the first job.

14. The system of claim 9, wherein the first job is specified by an arrival time parameter, a deadline time

parameter, a job size parameter, and a parallelism constraint parameter and a utility valuation function of a value obtained by finishing the job as a function of due date.

15. At least one tangible computer-readable storage medium storing processor-executable instructions that, when executed by at least one processor, cause the at least one processor to perform a method of determining a selection mechanism for a policy from a pool of policies, the method comprising:

executing each of a plurality of jobs in accordance with a policy in the pool of policies;

upon completion of execution of each of the plurality of jobs;

determining conditions associated with execution of the job and a delay of execution of the job;

computing a plurality of metrics of utility based on the determined conditions and the delay of execution of the job, each metric of utility being associated with a policy of the pool of policies; and

updating a policy selection mechanism for a policy from the pool of policies based on the metric of utility computed for the policy and the delay of execution of the job.

16. The at least one tangible computer-readable storage medium of claim 15, wherein executing each of the plurality of jobs comprises:

selecting a first policy by using the policy selection mechanism; and

executing a first job in the plurality of jobs in accordance with the first policy.

17. The at least one tangible computer-readable storage medium of claim 16, wherein the first policy specifies renting at least one computing resource in accordance with at least one of on-demand pricing, spot pricing, or reserved pricing.

18. The at least one tangible computer-readable storage medium of claim 15, wherein deter mining the conditions associated with execution of the job comprises determining whether the job execution completed by a deadline associated with the job and a cost associated with executing the job.

19. The at least one tangible computer-readable storage medium of claim 15, wherein executing a job in the plurality of jobs comprises allocating at least one cloud computing resource to the job.

20. The at least one tangible computer-readable storage medium of claim 15, wherein the pool of policies comprises at least one fixed-bid policy and at least one variable-bid policy.