Method and system for scheduling of jobs

• US 20070143765A1
• Filed: 12/21/2005
• Published: 06/21/2007
• 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
• Granted Patent: US 7,958,509 B2
• Time in Patent Office: Days
• 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, comprising:

receiving feedback regarding the execution of previously submitted jobs on one or more resource nodes;

receiving a request for a job including parameters of the job;

estimating the resources required for execution of the job based on the feedback and the parameters of the job; and

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

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 estimating is carried out by a method of reinforcement learning.

5. A method of as claimed in claim 1, wherein estimating the resources required for execution of the job, includes:

comparing the job to previously submitted jobs;

identifying the job as a similar job to previously submitted job or jobs;

determining the user requested resource allocation for the job; and

starting from the user requested resource allocation, allocating lower resources for each submission of the similar job, until a lowest successful resource allocation is identified.

6. A method as claimed in claim 5, wherein the step of identifying a similar job includes jobs within a predefined similarity measure including repeating jobs.

7. A method as claimed in claim 5, 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 a request file.

8. A method as claimed in claim 5, wherein the step of estimating includes:

identifying a first instance of a job, wherein the job is outside a predetermined similarity measure of previously submitted jobs; and

allocating the user requested resources to the job.

9. A method as claimed in claim 5, wherein allocating lower resources for each submission of a similar job includes reducing the resource allocation by a predetermined factor.

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

11. A computer program product comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to carry out the steps of:

receiving feedback regarding the execution of previously submitted jobs on one or more resource nodes;

receiving a request for a job including parameters of the job;

estimating the resources required for execution of the job based on the feedback and the parameters of the job; and

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

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

a feedback module for receiving feedback regarding the execution of previously submitted jobs on one or more resource nodes;

an estimator for estimating the resources required for execution of a job based on the feedback and the parameters of a job; and

a resource allocator for allocating a job to one or more resource nodes having the estimated resources.

13. A system as claimed in claim 12, wherein the resource allocator allocates a job to one or a plurality of resource nodes in parallel, wherein the resource allocation is less than a user requested resource allocation for a job.

14. A system as claimed in claim 12, wherein the system includes:

a job similarity identifier for identifying a job similar to previously submitted job or jobs; and

the estimator starting from a user requested resource allocation, allocating lower resources for each submission of the similar job, until a lowest successful resource allocation is identified.

15. A system as claimed in claim 14, wherein the job similarity identifier identifies jobs within a predefined similarity measure including repeating jobs.

16. A system as claimed in claim 14, wherein the job similarity identifier compares jobs with previously submitted jobs by comparing by one or more of:

user identifier, application number, requested memory, or other relevant parameter in a request file.

17. A system as claimed in claim 12, wherein the system includes a plurality of heterogeneous resource nodes for execution of the jobs.

18. A system as claimed in claim 17, wherein the plurality of heterogeneous resource nodes is a dynamic cluster of computer processors.

19. A system as claimed in claim 17, wherein the plurality of heterogeneous resource nodes is a computing grid.

20. A system as claimed in claim 12, wherein the estimator and resource allocator are provided in a job scheduler.