Method and system for scheduling of jobs

• US 7,958,509 B2
• Filed: 12/21/2005
• Issued: 06/07/2011
• Est. Priority Date: 12/21/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yom-Tov, Elad, Aridor, Yariv, Harper, Richard Edwin
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): Kawsar; Abdullah Al
• Application Number:
  US11/313,395
• Publication Number:
  US 20070143765A1
• Time in Patent Office: 1,994 Days
• Field of Search: None
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/503 Resource availability
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals

Abstract

A method and system of resource allocation for execution of a job are provided. The method includes receiving feedback (134) regarding the execution of previously submitted jobs on one or more resource nodes (101-104), and estimating the resources required for execution of a submitted job based on the feedback (134) and the parameters of the job. One, or a plurality of resource nodes in parallel, having the estimated resources are allocated the job. The feedback may be implicit feedback indicating the success or failure of the execution of a job. The one or more resource nodes (101-104) allocated for execution of a job may have less than a user requested resource allocation for the job.

Claims

1. A method of resource allocation for execution of a job, the method comprising:

collecting feedback regarding resource allocation and execution of previously submitted job requests to a clustered network, wherein resources of a plurality of computers are clustered together in form of one or more source nodes for the purpose of servicing submitted job requests;

receiving a request for execution of a job including parameters associated with the job, wherein the parameters are provided by a user as an estimation of resources to be utilized to successfully execute the job;

allocating one or more resources to the job according to the provided user estimate without regard to the collected feedback information, if the job is determined to be a job distinguishable from a previously submitted job in accordance with a measurable similarity threshold;

otherwise, estimating the resources utilized for execution of the job based on the collected feedback and state of currently available resources in the clustered network such that the estimated resources are less than the provided user estimate or a previously calculated estimated associated with a previously submitted similar job, if the collected feedback indicates that the previously allocated resources to a previously submitted similar job were adequate to service the previously submitted similar job; and

continuing the estimating process to calculate final estimated resources by successively reducing level of estimated resources to be utilized for execution of the submitted job, provided that the level of estimated resources does not fall below a lowest successful resource allocation level;

allocating the job to one or more resource nodes that provide a final calculated estimated resources according to the estimating process.

2. A method as claimed in claim 1, wherein the feedback is implicit feedback indicating the success or failure of the execution of a job or explicit feedback indicating actual resources used by the job.

3. A method as claimed in claim 1, wherein the one or more resource nodes allocated for execution of a job have less than a user requested resource allocation for the job.

4. A method as claimed in claim 1, wherein the allocation process for allocating the job to one or more resource nodes is performed by way of a reinforcement learning scheme which is based on a reward and penalty application depending on success rate of an allocation.

5. A method as claimed in claim 1, wherein a job is similar to a previously submitted job by comparing by one or more of:

user identifier, application number, requested memory, or other relevant parameter in the corresponding job request.

6. A method as claimed in claim 1, wherein reducing level of estimated resources includes reducing the resource allocation by a predetermined factor.

7. A method as claimed in claim 1, wherein an optimization algorithm such as a line search algorithm is used limited to a set of repeating jobs with a maximum parameter of the user requested resource allocation.

8. A system for resource allocation for execution of a job, the system comprising:

at least one processor;

a feedback mechanism for collecting feedback regarding resource allocation and data about execution of previously submitted job requests to a clustered network, wherein resources of a plurality of computers are clustered together in form of one or more source nodes for the purpose of servicing submitted job requests;

a job scheduler for receiving a request for executing a job including parameters associated with the job, wherein the parameters are provided by a user as an estimation of resources to be utilized to successfully execute the job;

a resource allocator for allocating one or more resources to the job according to the provided user estimate without regard to the collected feedback information, if the job is determined to be a job distinguishable from a previously submitted job in accordance with a measurable similarity threshold;

an estimator for estimating the resources utilized for execution of the job based on the collected feedback and state of currently available resources in the clustered network such that the estimated resources are less than the provided user estimate or a previously calculated estimated associated with a previously submitted similar job, if the collected feedback indicates that the previously allocated resources to a previously submitted similar job were adequate to service the previously submitted similar job; and

continuing the estimating process to calculate final estimated resources by successively reducing level of estimated resources to be utilized for execution of the submitted job, provided that the level of estimated resources does not fall below a lowest successful resource allocation level;

wherein the resource allocator allocates the job to one or more resource nodes that provide a final calculated estimated resources according to the estimating process.

9. A system as claimed in claim 8, wherein the feedback is implicit feedback indicating the success or failure of the execution of a job or explicit feedback indicating actual resources used by the job.

10. A system as claimed in claim 8, wherein the one or more resource nodes allocated for execution of a job have less than a user requested resource allocation for the job.

11. A system as claimed in claim 8, wherein the allocation process for allocating the job to one or more resource nodes is performed by way of a reinforcement learning scheme which is based on a reward and penalty application depending on success rate of an allocation.

12. A system as claimed in claim 8, wherein a job is similar to a previously submitted job by comparing by one or more of:

user identifier, application number, requested memory, or other relevant parameter in the corresponding job request file.

13. A system as claimed in claim 8, wherein reducing level of estimated resources includes reducing the resource allocation by a predetermined factor.

14. A system as claimed in claim 8, wherein an optimization algorithm such as a line search algorithm is used limited to a set of repeating jobs with a maximum parameter of the user requested resource allocation.

15. A method of resource allocation for execution of a job, the method comprising:

collecting feedback regarding success data about execution of previously submitted job requests to a clustered network, wherein resources of a plurality of computers are clustered together in form of one or more source nodes for the purpose of servicing submitted job requests;

receiving a request for executing a job including parameters associated with the job, wherein the parameters are provided by a user as an estimation of resources to be utilized to successfully execute the job;

allocating one or more resources to the job according to the provided user estimate without regard to the collected feedback information, if the job is determined to be a job distinguishable from a previously submitted job in accordance with a measurable similarity threshold;

otherwise, estimating the resources utilized for execution of the job based on the collected feedback and state of currently available resources in the clustered network such that;

(1) the estimated resources are larger than the provided user estimate or a previously calculated estimate associated with a previously submitted similar job, if the collected feedback indicates that the previously allocated resources to the previously submitted similar job were inadequate to service the previously submitted similar job, and

(2) the estimated resources are less than the provided user estimate or a previously calculated estimated associated with a previously submitted similar job, if the collected feedback indicates that the previously allocated resources to a previously submitted similar job were adequate to service the previously submitted similar job; and

continuing to successively update level of estimated resources according to the above conditions until the estimated resources are adequate to service the request below an upper limit threshold, or the estimated resources are not below a lowest successful resource allocation level; and

allocating the job to one or more resource nodes having the estimated resources according to the estimating process.