Compute cluster with balanced resources

Patent metadata

Field	Value
Publication number	US-9069610-B2
Application number	US-90345610-A
Country	US
Kind code	B2
Filing date	Oct 13, 2010
Priority date	Oct 13, 2010
Publication date	Jun 30, 2015
Grant date	Jun 30, 2015

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.

First claim

What is claimed is:

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;
determining that an executing job of the plurality of jobs is using more than the minimum number of computing resources for that job which are usable by one of the plurality of jobs which has not yet been allocated computing resources;
de-allocating an allocated resource from the executing job allocated in excess of the minimum number of computing resources of the executing job, in an attempt to meet the minimum number of computing resources of the one of the plurality of jobs which has not yet been allocated computing resources;
allocating the de-allocated resource to the one of the plurality of jobs;
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, 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, wherein identifying the second job comprises evaluating the plurality of jobs in reverse order of priority, with lowest priority jobs being evaluated first; and
de-allocating the resource from the second job comprises de-allocating the resource usable by the first job.

2. 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.

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

4. 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.

5. 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.

6. The method of claim 1 , 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.

7. A computer storage memory 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, wherein the at least one ready job has not yet been allocated resources, the resources being allocated to each of the at least one ready job based on a minimum resource requirement specified for the ready job including in order to meet the minimum resource requirement of the at least one ready job, de-allocating an allocated resource from another job allocated in excess of the minimum resource requirement of the another job, and, allocating the de-allocated resource to the at least one 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, wherein adjusting the resource usage comprises processing executing jobs in inverse order of priority and inverse order of length of time already executing, 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.

8. The computer storage memory of claim 7 , 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.

9. The computer storage memory of claim 7 , 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.

10. The computer storage memory of claim 7 , 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.

11. The computer storage memory of claim 10 , wherein the first mode comprises allocating resources to each ready job in the queue for which resources are available.

12. The computer storage memory of claim 7 , wherein the first mode and the second mode are performed repetitively.

13. The computer storage memory of claim 12 , wherein a repetition of the first mode is performed when a job has been submitted and is ready for execution but has not yet been allocated resources.

14. The computer storage memory of claim 12 , wherein a repetition of the second mode is performed in response to events during execution of jobs.

15. A system comprising:
a plurality of computing nodes providing computing resources, at least one of the computing nodes comprising a processor;
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 comprising:
allocating available computing resources to ready jobs in a ready queue, wherein ready jobs have not yet been allocated resources, the resources being allocated to each of the ready jobs base

Assignees

• Chakravorty Sayantan
• Barnard Joshua B
• Watson Colin
• Burgess Gregory
• Microsoft Technology Licensing Llc

Inventors

• Chakravorty Sayantan
• Barnard Joshua B
• Watson Colin
• Burgess Gregory

Classifications

• Y02B60/142

  Cross-Sectional Technologies · mapped topic

• G06F9/50 Primary

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title

• G06F2209/504

  Resource capping · CPC title

• Y02D10/00

  Energy efficient computing, e.g. low power processors, power management or thermal management · CPC title