Source: https://patents.google.com/patent/US9069610B2/en
Timestamp: 2020-01-26 06:00:33
Document Index: 39768509

Matched Legal Cases: ['Application No. 200880024896', 'Application No. 200880024896', 'Application No. 200880024896', 'Application No. 200880024896', 'Application No. 200880024896', 'Application No. 08', 'Application No. 2010', 'Application No. 2010']

US9069610B2 - Compute cluster with balanced resources - Google Patents
Compute cluster with balanced resources Download PDF
US9069610B2
US9069610B2 US12/903,456 US90345610A US9069610B2 US 9069610 B2 US9069610 B2 US 9069610B2 US 90345610 A US90345610 A US 90345610A US 9069610 B2 US9069610 B2 US 9069610B2
US12/903,456
US20120096468A1 (en
2010-10-13 Priority to US12/903,456 priority Critical patent/US9069610B2/en
2010-12-23 Assigned to MICROSOFT CORPORATION reassignment MICROSOFT CORPORATION ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: WATSON, COLIN, BARNARD, JOSHUA B., BURGESS, GREGORY, CHAKRAVORTY, SAYANTAN
2012-04-19 Publication of US20120096468A1 publication Critical patent/US20120096468A1/en
2015-06-30 Publication of US9069610B2 publication Critical patent/US9069610B2/en
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.
As computing needs of businesses and other organizations have grown, various computing architectures have been employed to meet these needs. One architecture involves the use of distributed computing clusters. A cluster contains multiple computers, each potentially with multiple processing cores, such that the cluster, as a whole, can provide substantial processing resources. A computer acting as a scheduler for the cluster can assign one or more of the cores to different jobs such that, at any time, the cluster can simultaneously execute multiple jobs, possibly from different clients.
Increased responsiveness for jobs executed on a computing cluster may be provided with a scheduler for the cluster that uses a balanced scheduling policy. The policy may be balanced in the sense that a goal of the policy is to enable to as many jobs as possible to execute with computing resources allocated across the executing jobs in a way that, as closely as possible, achieves resource usage in accordance with priority or other parameters of the jobs. The policy may be implemented in multiple modes of operation of the scheduler.
The inventors have recognized and appreciated that a balanced scheduling policy can provide significant benefits to businesses or other entities operating computing clusters. The scheduling policy for a cluster may affect response time of the cluster such that a balanced policy may provide for faster response times. A balanced policy may also enable an administrator of a cluster to make and keep service level commitments to those using the cluster, such as commitments relating to response time or availability of resources to clients accessing the cluster.
A balanced scheduling policy may improve a user experience for a service oriented architecture or other applications that include numerous tasks that frequently can be performed independently, for example. These applications may have on the order hundreds of thousands or millions of parallel tasks and are sometimes described as “embarrassingly parallel.” These tasks may be performed in multiple different jobs submitted to the compute cluster. In such applications, benefits, including shorter response times and greater usability, may be achieved by starting as many jobs as possible, even though each job may receive fewer resources than in a conventional scheduling policy.
In this context, a computing resource may be defined in units of “nodes,” or some other unit of computing power that can be allocated for executing a job, either alone or in combination with other computing resources. In some embodiments, the structure of a node may be determined based on the architecture of the computing devices, such as computers 40A, 40B and 40C, that provide the computing power. In some embodiments, for example, each node may be a computer and an executing job may be allocated one or more of the computers. In such an embodiment, the physical computers define the unit of computing resources that can be allocated. In other embodiments, each of the computers may contain multiple processor chips that can be independently allocated to jobs submitted for execution by the computing cluster. In that embodiment, a processor chip, or “socket,” may serve as the unit of computing resources. In yet other embodiments, one or more of the processor chips within computers, such as computers 40A, 40B and 40C, may contain multiple cores. The cores may be independently allocated to executing jobs submitted to the cluster. In that scenario, a core may define a unit of computing resources for the cluster.
It should be appreciated that a computing cluster may be operated according to embodiments of the invention using any suitable measure of computing resources. It should also be appreciated that, though a hardware component, such as a core, may be used as an example of a computing node, it is not a requirement that the resources be defined based on hardware partitions of the computers of the cluster. A node may be any limited resource that is used to do work within a computing system. In some embodiments, the computing resources may be virtualized, such that a direct relationship between a node, as managed by the cluster, and a physical component need not exist. As another example, a “node” may be a license to software that is license controlled such that a limited number of instances of that software may execute at one time.
Suitability of resources for a job may be determined in any suitable way. For example, each of the computing nodes may have a list of characteristics associated with it. The parameters associated with each job may include an indication of characteristics of suitable computing resources for that job. Such information may be provided by a cluster administrator, a programmer that defines a job or any other suitable way, including techniques as are known in the art. Further, suitability may be determined in accordance with a policy established by an administrator of the computing cluster or other suitable party. As a specific example, suitability may be defined based on location of data accessed during execution of a job. In the example of FIG. 1, a job may access during execution data in data store 42A. Though computer 40C may be able to access data store 42A over network 30, a policy of the cluster administrator may indicate that a job accessing data in data store 42A execute on a core within computer 40A in order to minimize network traffic on network 30. Such a requirement may be used to determine that nodes within computer 40C are unsuitable for allocation to a job that access data in data store 42A. In addition to location of data, any other criteria may alternatively or additionally be used to determine suitability of a node for allocation to a particular job. Moreover, it should be appreciated that “suitability” need not be binary. In some instances, one node may have characteristics that make it more suitable than other nodes for a particular task. When an available node is less suitable than others that are not available, a policy or other suitable criteria may be used to determine whether the available node will be allocated to a task or the scheduler will wait for a more suitable node to be available.
This processing may result in nodes allocated to already executing jobs may be de-allocated from those jobs such that those nodes can be reallocated to meet the designated minimum for a job in the queue awaiting execution. Deallocating a node from an executing job will result in canceling the computing tasks being performed on that node. Accordingly, the jobs in the queue for which resources are being sought may be regarded as “preempting” jobs. Jobs from which resources are de-allocated may be regarded as “target jobs.”
In scenarios in which multiple target jobs are assigned the same priority level, the target jobs at each level may be organized such that the newest executing job is ordered first. A “newer” executing job may be defined as a job that has been executing for a shorter time than an older executing job. This ordering may be based, for example, on a time from when execution of each target job was initiated. Though, this relative ordering need not be based on absolute time. In some embodiments, for example, the ordering may be based on a percentage of the job completed or other criteria that indicates a relative amount of computing resources that may be consumed when a resource associated with a target job is de-allocated from that job and tasks executing on that resource are rescheduled at a later time.
In processing at block 722, the nodes available for allocation may constitute a “grow pool.” The grow pool may contain nodes that are not currently allocated for execution of any job. In addition, the grow pool may contain nodes allocated to executing jobs that are in excess of the respective minimum resource requirements for the executing job.
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;
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.
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.
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:
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;
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.
a plurality of computing nodes providing computing resources, at least one of the computing nodes comprising a processor;
a scheduler, the scheduler comprising:
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 based on a minimum resource requirement specified for the ready job, the available computing resources comprising un-allocated resources and resources allocated and used by executing jobs in excess of respective minimum requirements for the executing jobs,
the allocator further operating in a second mode comprising:
adjusting resource usage by identifying at least one job using more than the respective desired allocation of resources by evaluating the plurality of executing jobs in reverse order of priority, with lowest priority jobs being evaluated first, de-allocating a resource from the 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 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.
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.
17. The system of claim 15, 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.
18. The system of claim 17, wherein assigning resources based on the respective minimum associated with 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.
19. The system of claim 15, wherein the first mode and the second mode are performed repetitively.
20. The system of claim 19, 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, and, a repetition of the second mode is performed in response to events during execution of jobs.
US12/903,456 2010-10-13 2010-10-13 Compute cluster with balanced resources Active 2032-05-25 US9069610B2 (en)
US12/903,456 US9069610B2 (en) 2010-10-13 2010-10-13 Compute cluster with balanced resources
US20120096468A1 US20120096468A1 (en) 2012-04-19
US9069610B2 true US9069610B2 (en) 2015-06-30
ID=45935263
US12/903,456 Active 2032-05-25 US9069610B2 (en) 2010-10-13 2010-10-13 Compute cluster with balanced resources
US (1) US9069610B2 (en)
US10412193B2 (en) 2016-12-02 2019-09-10 International Business Machines Corporation Usage-aware standby service in a grid environment
US20180300176A1 (en) * 2017-04-17 2018-10-18 Red Hat, Inc. Self-programmable and self-tunable resource scheduler for jobs in cloud computing
JP2003330734A (en) 2002-05-15 2003-11-21 Hewlett Packard Co <Hp> Method and system for allocating system resource to applications using weight
US20050237930A1 (en) 2004-04-26 2005-10-27 Boaz Patt-Shamir Computer method and apparatus for periodic scheduling with jitter-approximation tradeoff
US20060089922A1 (en) 2004-10-27 2006-04-27 International Business Machines Corporation Method, system, and apparatus for allocating resources to a software configurable computing environment
US20060190943A1 (en) 2005-02-22 2006-08-24 Northrop Grumman Corporation System and a method for scheduling tasks
US20100115526A1 (en) 2008-10-31 2010-05-06 Synopsys, Inc. Method and apparatus for allocating resources in a compute farm
US7756989B2 (en) * 2000-04-28 2010-07-13 International Business Machines Corporation Method and apparatus for dynamically adjusting resources assigned to plurality of customers, for meeting service level agreements (SLAs) with minimal resources, and allowing common pools of resources to be used across plural customers on a demand basis
2010-10-13 US US12/903,456 patent/US9069610B2/en active Active
CN1636191A (en) 2002-02-21 2005-07-06 国际商业机器公司 Apparatus and method of dynamically repartitioning a computer system in response to partition workloads
Ajay Gulati et al. "RePAIR: Reservation-Based Proportionate Allocation for I/O Resources", May 14, 2008; VMware Inc, HP Labs, Rice University; (Gulati-2008.pdf; pp. 1-20). *
Baratloo et al., "Mehanisms for Just-inTime Allocation of Resources to Adaptive Parallel Programs", IEEE, Apr. 12-16, 1999, pp. 1-7.
Baratloo et al., "Mehanisms for Just-inTime Allocation of Resources to Adaptive Parallel Programs", IEEE, Apr. 12-16, 1999, psges 1-7.
Buisson et al, "Scheduling Malleable Applications in Multicluster Systems", CoreGRID Technical Report No. TR-0092, May 22, 2007, pp. 1-15.
CN Application No. 200880024896X, Amended Claims Response to First Office Action, filed Sep. 25, 2012, 24 pages.
CN Application No. 200880024896X, Amended Claims Response to Second Office Action, filed Jan. 5, 2013, 36 pages.
CN Application No. 200880024896X, Notice on Deeming to Have Abandoned the Right to Obtain the Patent, mailed Jul. 12, 2013, 2 pages.
CN Application No. 200880024896X, Notice on the First Office Action, PCT Application in the National Phase, mailed Jun. 1, 2012, 13 pages.
CN Application No. 200880024896X, Notice on the Second Office Action, mailed Dec. 20, 2012, 9 pages.
EP Application No. 08 826 472.6, Response to Official Communication under Rules 70(2) and 70a(2) EPC dated Nov. 3, 2011, filed May 14, 2012, 21 pages.
European Search Report, Mailed Date: Oct. 20, 2011, Application No. EP 08 82 6472, Filed Date: Oct. 17, 2011, 7 pages.
How the Compute Cluster Server Works, Microsoft, TechNet, Jun. 2006 (http://technet.microsoft.com/en-us/library/cc720072.aspx). See Chapters "Terms and definitions", "Creating and submitting jobs"-"Run-time job and task management" and Content format, 16 pages.
International Search Report and Written Opinion for PCT Application No. PCT/US2008/070147, dated Feb. 10, 2009, 11 pages.
JP Application No. 2010-517131, Final Rejection, mailed May 31, 2013, 1 page.
JP Application No. 2010-517131, Notice of Final Rejection, mailed Jan. 4, 2013, 3 pages.
Michael Isard et al., "Quincy: Fair Scheduling for Distributed Computing Clusters", Microsoft Research, pp. 1-20, published 2009.
Streit "Self-Tuning Job Scheduling Strategies for the Resource Management of HPC Systems and Computational Grids", Paderborn, Oct. 2003, 166 pages.
Streit, "Self-Tuning Job Scheduling Strategies for the Resource Management of HPC Systems and Computational Grids", Paderborn, Oct. 2003, 166 pages.
U.S. Appl. No. 11/778,487, Final Office Action mailed Sep. 15, 2011, 17 pages.
U.S. Appl. No. 11/778,487, Non-Final Office Action mailed Jun. 20, 2013, 17 pages.
U.S. Appl. No. 11/778,487, Non-Final Office Action mailed Mar. 10, 2011, 22 pages.
U.S. Appl. No. 11/778,487, RCE-Response to Final Office Action mailed Sep. 15, 2011, filed Dec. 30, 2011, 13 pages.
U.S. Appl. No. 11/778,487, Response to Non-Final Office Action mailed Mar. 10, 2011, filed Jul. 13, 2011, 9 pages.
Vasupongayya et al., "On Job Fairness in Non-Preemptive Parallel Job Scheduling", Proceeding from Parallel and Distributed Computing and Systems, Nov. 14-16, 2005, 6 pages.
US20120096468A1 (en) 2012-04-19
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:CHAKRAVORTY, SAYANTAN;BARNARD, JOSHUA B.;WATSON, COLIN;AND OTHERS;SIGNING DATES FROM 20101011 TO 20101012;REEL/FRAME:025564/0428