Method, system and computer program for distributing a plurality of jobs to a plurality of computers

• US 8,185,902 B2
• Filed: 08/31/2008
• Issued: 05/22/2012
• Est. Priority Date: 10/31/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Deidda, Paolo, Benedetti, Fabio
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): KIM, SISLEY NAHYUN
• Application Number:
  US12/202,289
• Publication Number:
  US 20090113442A1
• Time in Patent Office: 1,360 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/5014 Reservation
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

Method and system for providing a mechanism for determining an optimal workload distribution, from a plurality of candidate workload distributions, each of which has been determined to optimize a particular aspect of a workload-scheduling problem. More particularly, the preferred embodiment determines a workload distribution based on resource selection policies. From this workload distribution, the preferred embodiment optionally determines a workload distribution based on job priorities. From either or both of the above parameters, the preferred embodiment determines a workload distribution based on a total prioritized weight parameter. The preferred embodiment also determines a workload distribution which attempts to match the previously determined candidate workload distributions to a goal distribution. Similarly, the preferred embodiment calculates a further workload distribution which attempts to maximize job throughput.

Claims

1. A method of distributing a plurality of jobs to a plurality of computers, the method comprising:

determining a plurality of possible pairing of jobs to computers, in order to produce provisional distributions;

producing a first ranking that ranks the provisional distributions according to the extent to which they satisfy the individual requirements of each job among the plurality of jobs by calculating a normalized total weight which provides a measure of merits of a solution based on individual job resource distributions;

producing a second ranking that ranks the provisional distributions according to the extent to which they match a predefined distribution by calculating a normalized delta from a goal distribution which provides a measure of the provisional distributions from a goal distribution;

producing a third ranking that ranks the provisional distributions according to the extent to which they maximize a throughput of the computers, wherein producing the third ranking comprises calculating a percentage of a total number of jobs for each of the provisional distributions over a total number of jobs for all of the provisional distributions;

determining an optimal distribution from the rankings based on a one of the provisional distributions having a maximally valued combination of the first ranking, the second ranking and the third ranking, wherein the optimal solution is a maximum valued combination for all of the three identified rankings; and

deploying each of said plurality of jobs to a respective one of the plurality of the computers in accordance with the optimal distribution.

2. The method of claim 1, wherein determining a plurality of possible pairing of the jobs to the computers, further comprises

determining the plurality of possible pairing of jobs by pairing each of the plurality of jobs to a respective one of the plurality of computers, the method further comprising:

producing a first provisional distribution, by allocating a first job to a computer whose resources satisfy the requirements of the first job and allocating the remaining jobs to the rest of the computers whose resources satisfy the requirements of the remaining jobs; and

repeating the step of producing the first provisional distribution for every computer whose resources satisfy the requirements of the first job.

3. The method of claim 1, wherein producing the first ranking that ranks the provisional distributions according to the extent to which they satisfy the individual requirements of each job, further comprises:

determining a plurality of first parameters for each provisional distribution in accordance with a resource selection policy of each job, and/or determining a plurality of second parameters for each provisional distribution in accordance with a priority of each job; and

determining a ranking for each provisional distribution from either or both of the first and second parameters.

4. The method of claim 3, wherein determining a plurality of first parameters for each provisional distribution, further comprises:

identifying a resource attribute associated with a resource selection policy of each job;

determining a value of the resource attribute for each computer; and

ranking the computers according to the extent to which each computer'"'"'s resource attribute satisfies the resource selection policy, as compared with the resource attributes of the other computers.

5. The method of claim 1 wherein producing the second ranking that ranks the provisional distributions according to the extent to which they match a predefined distribution, further comprises:

combining a number of jobs allocated to each computer with a number of jobs currently running on each computer; and

subtracting the combined number of jobs for each computer, with the number of jobs allocated thereto in the predefined distribution.

6. The method of claim 1, wherein producing the third ranking that ranks the provisional distributions according to the extent to which they maximize a throughput of the computers, further comprises:

calculating a first allocation parameter being the total number of jobs allocated by each provisional distribution to the computers;

calculating a second allocation parameter being the total number of jobs allocated to all of the computers by all of the provisional distributions; and

calculating the percentage of the second allocation parameter formed by the first allocation parameter.

7. The method of claim 1 wherein the plurality of possible pairing includes every possible pairing of the jobs among said plurality of jobs to the computers.

8. A system for distributing a plurality of jobs to a plurality of computers, the system comprising:

a processor;

a data bus coupled to said processor; and

a computer-usable medium embodying computer code, said computer-usable medium being coupled to said data bus, said computer program code comprising instructions executable by said processor and configured for;

determining a plurality of possible pairing of jobs to computers, in order to produce provisional distributions;

producing a first ranking that ranks the provisional distributions according to the extent to which they satisfy the individual requirements of each job among the plurality of jobs by calculating a normalized total weight which provides a measure of merits of a solution based on individual job resource distributions;

producing a second ranking that ranks the provisional distributions according to the extent to which they match a predefined distribution by calculating a normalized delta from a goal distribution which provides a measure of the provisional distributions from a goal distribution;

producing a third ranking that ranks the provisional distributions according to the extent to which they maximize a throughput of the computers, wherein producing the third ranking comprises calculating a percentage of a total number of jobs for each of the provisional distributions over a total number of jobs for all of the provisional distributions;

determining an optimal distribution from the rankings based on a one of the provisional distributions having a maximally valued combination of the first ranking, the second ranking and the third ranking, wherein the optimal solution is a maximum valued combination for all of the three identified rankings; and

deploying each of said plurality of jobs to a respective one of the plurality of the computers in accordance with the optimal distribution.

9. The system of claim 8, wherein determining a plurality of possible pairing of the jobs to the computers, further comprises determining the plurality of possible pairing of jobs by pairing each of the plurality of jobs to a respective one of the plurality of computers, the system further comprising said computer program code configured for:

producing a first provisional distribution, by allocating a first job to a computer whose resources satisfy the requirements of the first job and allocating the remaining jobs to the rest of the computers whose resources satisfy the requirements of the remaining jobs; and

repeating the step of producing the first provisional distribution for every computer whose resources satisfy the requirements of the first job.

10. The system of claim 8, wherein producing the first ranking that ranks the provisional distributions according to the extent to which they satisfy the individual requirements of each job, further comprises:

determining a plurality of first parameters for each provisional distribution in accordance with a resource selection policy of each job and/or determining a plurality of second parameters for each provisional distribution in accordance with a priority of each job; and

determining a ranking for each provisional distribution from either or both of the first and second parameters.

11. The system of claim 10, wherein determining a plurality of first parameters for each provisional distribution, further comprises:

identifying a resource attribute associated with a resource selection policy of each job;

determining a value of the resource attribute for each computer; and

ranking the computers according to the extent to which each computer'"'"'s resource attribute satisfies the resource selection policy, as compared with the resource attributes of the other computers.

12. The system of claim 8, wherein producing the second ranking that ranks the provisional distributions according to the extent to which they match a predefined distribution, further comprises:

combining a number of jobs allocated to each computer with a number of jobs currently running on each computer; and

subtracting the combined number of jobs for each computer, with the number of jobs allocated thereto in the predefined distribution.

13. The system of claim 8, wherein producing the third ranking that ranks the provisional distributions according to the extent to which they maximize a throughput of the computers, further comprises:

calculating a first allocation parameter being the total number of jobs allocated by each provisional distribution to the computers, calculating a second allocation parameter being the total number of jobs allocated to all of the computers by all of the provisional distributions; and

calculating the percentage of the second allocation parameter formed by the first allocation parameter.

14. A non-transitory computer-usable medium embodying computer program code, said computer program code comprising computer executable instructions configured for:

determining a plurality of possible pairing of jobs to computers, in order to produce provisional distributions;

producing a first ranking that ranks the provisional distributions according to the extent to which they satisfy the individual requirements of each job among the plurality of by calculating a normalized total weight which provides a measure of merits of a solution based on individual job resource distributions;

producing a second ranking that ranks the provisional distributions according to the extent to which they match a predefined distribution by calculating a normalized delta from a goal distribution which provides a measure of the provisional distributions from a goal distribution;

producing a third ranking that ranks the provisional distributions according to the extent to which they maximize a throughput of the computers, wherein producing the third ranking comprises calculating a percentage of a total number of jobs for each of the provisional distributions over a total number of jobs for all of the provisional distributions;

determining an optimal distribution from the rankings based on a one of the provisional distributions having a maximally valued combination of the first ranking, the second ranking and the third ranking, wherein the optimal solution is a maximum valued combination for all of the three identified rankings; and

deploying each of said plurality of jobs to a respective one of the plurality of the computers in accordance with the optimal distribution.

15. The computer-usable medium of claim 14, wherein determining a plurality of possible pairing of the jobs to the computers, further comprises determining the plurality of possible pairing of jobs by pairing each of the plurality of jobs to a respective one of the plurality of computers, the computer-usable medium further comprising computer executable instructions configured for:

producing a first provisional distribution, by allocating a first job to a computer whose resources satisfy the requirements of the first job and allocating the remaining jobs to the rest of the computers whose resources satisfy the requirements of the remaining jobs; and

repeating the step of producing the first provisional distribution for every computer whose resources satisfy the requirements of the first job.

16. The computer-usable medium of claim 14, wherein producing the first ranking that ranks the provisional distributions according to the extent to which they satisfy the individual requirements of each job, further comprises:

determining a plurality of first parameters for each provisional distribution in accordance with a resource selection policy of each job, and/or determining a plurality of second parameters for each provisional distribution in accordance with a priority of each job; and

determining a ranking for each provisional distribution from either or both of the first and second parameters.

17. The computer-usable medium of claim 16, wherein determining a plurality of first parameters for each provisional distribution, further comprises:

identifying a resource attribute associated with a resource selection policy of each job;

determining a value of the resource attribute for each computer; and

ranking the computers according to the extent to which each computer'"'"'s resource attribute satisfies the resource selection policy, as compared with the resource attributes of the other computers.

18. The computer-usable medium of claim 14, wherein producing the second ranking that ranks the provisional distributions according to the extent to which they match a predefined distribution, further comprises:

combining a number of jobs allocated to each computer with a number of jobs currently running on each computer; and

subtracting the combined number of jobs for each computer, with the number of jobs allocated thereto in the pre-defined distribution.

19. The computer-usable medium of claim 14, wherein producing the third ranking that ranks the provisional distributions according to the extent to which they maximize a throughput of the computers, further comprises:

calculating a first allocation parameter being the total number of jobs allocated by each provisional distribution to the computers;

calculating a second allocation parameter being the total number of jobs allocated to all of the computers by all of the provisional distributions; and

calculating the percentage of the second allocation parameter formed by the first allocation parameter.