COMPUTE CLUSTER WITH BALANCED RESOURCES

• US 20120096468A1
• Filed: 10/13/2010
• Published: 04/19/2012
• Est. Priority Date: 10/13/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Barnard, Joshua B., Chakravorty, Sayantan, Watson, Colin, Burgess, Gregory
• Granted Patent: US 9,069,610 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/504 Resource capping
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A scheduler for a compute cluster that allocates computing resources to jobs to achieve a balanced distribution. The balanced distribution maximizes the number of executing jobs to provide fast response times for all jobs by, to the extent possible, assigning a designated minimum for each job. If necessary to achieve this minimum distribution, resources in excess of a minimum previously allocated to a job may be de-allocated, if those resources can be used to meet the minimum requirements of other jobs. Resources above those used to meet the minimum requirements of executing jobs are allocated based on a computed desired allocation, which may be developed based on respective job priorities. To meet the desired allocation, resources may be de-allocated from jobs having more than their desired allocation and re-allocated to jobs having less than their desired allocation of resources.

Claims

1. A method of operating a scheduler within a computing cluster to schedule a plurality of jobs for concurrent execution on resources of the computing cluster, the method comprising:

with at least one processor;

receiving for each of a plurality of jobs, a request for a minimum number of computing resources;

computing for each of the plurality of jobs a respective desired allocation of the resources;

adjusting resources among the plurality of jobs by;

identifying a first job of the plurality of jobs using less than the respective desired allocation of resources;

identifying a second job of the plurality of jobs using more than the respective desired allocation of resources;

de-allocating a resource from the second job and allocating the de-allocated resource to the first job.

2. The method of claim 1, wherein:

identifying a second job of the plurality of jobs more than the respective desired allocation of resources comprises identifying as the second job a job using a resource usable by the first job; and

de-allocating the resource from the second job comprises de-allocating the resource usable by the first job.

3. The method of claim 1, further comprising:

adding to the plurality of jobs a ready job from a queue of ready jobs, the ready job comprising a minimum resource requirement associated therewith, and the adding comprising assigning to the ready job a number of resources based on the minimum resource requirement.

4. The method of claim 3 further comprising, following adding the ready job to the plurality of jobs, repeating the act of adjusting resources among the plurality of jobs.

5. The method of claim 1, wherein the method comprises balancing resources by repeatedly performing the act of adjusting resources among the plurality of resources until:

no further job is identified that is using less than the respective desired allocation of resources is identified;

or

no further job is identified that is using more than the respective desired allocation of resources and that is using a resource usable by a job using less than the respective desired allocation of resources.

6. The method of claim 1 wherein:

identifying the first job comprises evaluating the plurality of jobs in order of priority, with highest priority jobs being evaluated first.

7. The method of claim 1 wherein:

identifying the second job comprises evaluating the plurality of jobs in reverse order of priority, with lowest priority jobs being evaluated first.

8. The method of claim 7, wherein:

the plurality of jobs comprises executing jobs;

the method further comprises, initiating execution of each of the plurality of jobs by assigning to each of a plurality of selected jobs in a ready queue a number of resources determined based on a minimum requirement associated of the selected job, the selected jobs being selected in order of priority and length of time in the ready queue.

9. A non-transitory computer-readable storage medium comprising computer-executable instructions that, when executed by a processor, perform a method of scheduling resources in a computing cluster, the method comprising:

in a first mode;

allocating resources to at least one ready job in a ready queue, the resources being allocated to each of the at least one ready jobs based on a minimum resource requirement specified for the ready job;

in a second mode;

determining a desired respective allocation of resources for each of the plurality of executing jobs; and

adjusting resource usage by de-allocating a resource from at least one job using more than the respective desired allocation of resources and allocating the de-allocated resource to a job using less than the respective desired allocation of resources.

10. The computer-readable medium of claim 9, wherein determining a desired respective allocation of resources for each of the plurality of resources comprises:

determining a number of resources available for allocation among the plurality of executing jobs;

determining a weight for each of the plurality of executing jobs;

computing a value representing the aggregate of the weights of the plurality of executing jobs;

computing an amount of resources for each of the plurality of executing jobs as a fraction of the resources available for allocation, the fraction being based on the ratio of the weight of the executing job to the value representing the aggregate weights.

11. The computer-readable medium of claim 10, wherein determining a weight for each of the plurality of executing jobs comprises evaluating a non-linear function of respective priorities assigned to the plurality of executing jobs.

12. The computer-readable medium of claim 9, wherein determining a number of resources available for allocation comprises summing:

an amount of resources that are not assigned to any executing job; and

an amount of resources assigned to executing jobs in excess of the minimum resource requirement specified for the respective executing jobs.

13. The computer-readable medium of claim 9, wherein adjusting the resource usage comprises processing executing jobs in inverse order of priority and inverse order of length of time already executing.

14. The computer-readable medium of claim 13, wherein processing executing jobs comprises:

identifying whether the job being processed is using a resource usable by a job using less than the respective desired allocation of resources;

when a usable resource is identified, de-allocating the identified resource from the job being processed; and

allocating the de-allocated resource to a job using less than the respective desired allocation of resources.

15. The computer-readable medium of claim 14, wherein the first mode comprises allocating resources to each ready job in the queue for which resources are available.

16. A system comprising:

a plurality of computing nodes providing computing resources;

a scheduler, the scheduler comprising;

a ready queue holding jobs received from a plurality of clients;

an allocator, executing on at least one processor, operating in a first mode and a second mode,

the first mode comprising;

allocating available computing resources to ready jobs in a ready queue, the resources being allocated to each of the ready jobs based on a minimum resource requirement specified for the ready job, the available computing resources comprising un-allocated resources and resources allocated to executing jobs in excess of respective minimum requirements for the executing jobs; and

the second mode comprising;

determining a desired respective allocation of resources for each of the plurality of executing jobs; and

adjusting resource usage by de-allocating a resource from at least one job using more than the respective desired allocation of resources and allocating the de-allocated resource to a job using less than the respective desired allocation of resources.

17. The system of claim 16, wherein:

the first mode comprises identifying executing jobs having assigned resources that are in excess of a respective minimum for the job and that are usable by a job in the ready queue.

18. The system of claim 16, wherein the first mode comprises assigning resources based on a respective minimum associated with all ready jobs for which the respective minimum resources are available.

19. The system of claim 16, wherein assigning resources to all ready jobs for which the respective minimum resources are available comprises processing the ready jobs in the ready queue primarily in order of priority and secondarily based on time in the ready queue.

20. The system of claim 16, wherein the second mode is initiated in response to an event, the event comprising at least a ready job being assigned resources and an executing job freeing up resources upon termination.