Multi-objective allocation of computational jobs in client-server or hosting environments

• US 8,205,205 B2
• Filed: 03/16/2007
• Issued: 06/19/2012
• Est. Priority Date: 03/16/2007
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Franke, Carsten
• Primary Examiner(s): To, Jennifer
• Application Number:
  US11/724,706
• Publication Number:
  US 20080229318A1
• Time in Patent Office: 1,922 Days
• Field of Search: 718/103
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A method of processing a computational job with a plurality of processors is disclosed. A request to process a job is received, where the job has a priority level associated with the job. A first group of the processors is designated as being available to process the job, where the number of processors in the first group is based on the priority level associated with the job. A second group of the processors is designated as being available to process the job, where for each processor in the second group a current utilization rate of the processor is less than a second predetermined utilization rate. Then, the job is processed with one or more of the processors selected from the first group of processors and the second group of processors.

Claims

1. A method of processing a computational job with a plurality of processors, the method comprising:

receiving a request to process a job, wherein a priority level is associated with the job;

designating a first group of the processors as being available to process the job, wherein the first group of processors is designated for processing high priority jobs and wherein the number of processors in the first group is based on the priority level associated with the job;

designating a second group of the processors as being available to process the job, wherein the second group of processors is designated for processing high or low priority jobs and wherein for each processor in the second group a current utilization rate of the processor is less than a second predetermined utilization rate;

determining a number of processors (N) to process the job, wherein N>

1; and

processing the job with the N processors including one or more of the processors selected from the first group of processors and one or more of the processors selected from the second group of processors, wherein at least some of the N processors are selected from the first and second groups based on the selected processors having the lowest current utilization rates of the processors in the respective groups.

2. The method of claim 1, wherein the second predetermined utilization rate is based on the priority level of the job and on a subset of processors to which the processor belongs.

3. The method of claim 1, further comprising:

processing the job with the N processors selected from the first and second groups having the lowest current utilization rates of processors in the respective groups.

4. The method of claim 3, wherein determining the number of processors to process the job comprises receiving a request to process the job with at least N processors.

5. The method of claim 1, further comprising:

designating a third group of processors as being available to process the job, wherein for each processor in the third group, a current utilization rate of the processor is less than a third predetermined utilization rate, wherein the third predetermined utilization rate is lower than the second predetermined utilization rate; and

processing the job with one or more of the processors selected from the first, second, and third groups of processors.

6. The method of claim 1, further comprising:

queuing the request when the sum of the number of the processors in the first and second groups is less than N; and

when the sum of the number of the processors in the first and second groups is greater than or equal to N, processing the job with the N processors selected from the first and second groups having the lowest current utilization rates.

7. The method of claim 1, further comprising:

determining a current utilization rate for processors in the first group;

re-designating the first group of processors to exclude those processors having a current utilization rate greater than a predetermined first utilization rate;

queuing the request when the sum of the number of the processors in the re-designated first group and in the second groups is less than N; and

when the sum of the number of the processors in the re-designated first group and in the second groups is greater than or equal to N, processing the job with the N processors selected from the re-designated first group and from the second group having the lowest current utilization rates.

8. The method of claim 1, further comprising:

determining a new current utilization rate for processors in the second group; and

then

re-designating the second group of processors to exclude those processors having a new current utilization rate greater than the second predetermined utilization rate; and

then

processing the job with one or more of the processors selected from the first group of processors and the re-designated second group of processors.

9. The method of claim 1, wherein the request is received through a wide area network.

10. A method of processing a plurality of computational jobs with a plurality of processors, the method comprising:

designating a first group of the processors as being available to process a first job, wherein the first group of processors is designated for processing high priority jobs and wherein the number of processors in the first group is based on a priority level associated with the first job;

designating a second group of the processors as being available to process the job, wherein the second group of processors is designated for processing high or low priority jobs and wherein for each processor in the second group an initial utilization rate of the processor is less than or equal to an predetermined utilization rate that is based on the priority level and on a processor subset to which the processor belongs;

determining a number of processors (N) to process the first job, wherein N>

1;

processing the first job with the N processors including one or more of the processors selected from the first group of processors and one or more of the processors selected from the second group of processors, wherein at least some of the N processors are selected from the first and second groups based on the selected processors having the lowest current utilization rates of the processors in the respective groups;

determining that a processor in the second group that is processing the first job has an updated utilization rate that is greater than the predetermined utilization rate; and

then in response to the determination, processing the first job with a plurality of processors selected from the first group of processors and the second group, not including the processor that had a utilization rate greater than the first predetermined utilization rate.

11. The method of claim 10, further comprising, for each computational job being processed with the plurality of processors:

designating a primary group of the plurality of processors as being available to process the job, wherein the number of processors in the primary group for each job is based on a priority level associated with the job,

processing the job with a group of processors selected from the primary group of processors for the job and a supplemental set of the plurality of processors not belonging to the primary group;

determining that a processor in the supplemental set used to process the job has a utilization rate greater than a utilization rate determined by the priority level of the job; and

in response to the determination, processing the job with a plurality of processors selected from the first group of processors and the second group, not including the processor that had a utilization rate greater than the first predetermined utilization rate.

12. A system for processing a computational job, the system comprising:

an input queue adapted for receiving a computational job to process, wherein a priority level is associated with the job;

a plurality of processors;

a utilization rate service engine adapted to determine a utilization rate of the processors;

a processor grouping engine configured for grouping processors of the plurality of processors into;

a first group of processors designated as being available to process the job, wherein the number of processors in the first group is based on the priority level associated with the job and wherein the first group of processors is designated for processing high priority job, and

a second group of processors, for which a current utilization rate is less than a second predetermined utilization rate and designated as being available to process the job, wherein the second group of processors is designated for processing high or low priority jobs; and

a scheduling engine adapted to receive information about the priority level of the job and about the utilization rates of the processors and to schedule the job to be processed by a number (N) of processors, wherein N>

1, including one or more of the processors selected from the first group of processors and one or more of the processors selected from the second group of processors, wherein at least some of the N processors are selected from the first and second groups based on the selected processors having the lowest current utilization rates of the processors in the respective groups.

13. The system of claim 12, wherein the first group consists of one processor.

14. The system of claim 12, wherein the scheduling engine is adapted to schedule the job to be processed with the N processors selected from the first and second groups having the lowest current utilization rates.

15. The system of claim 12, wherein the determination of the number of processors (N) to process the job is based on the request.

16. The system of claim 12, wherein the processor grouping engine configured for grouping processors of the plurality of processors into a third group of processors for which a current utilization rate of the processor is less than a third predetermined utilization rate is designating as being available to process the job,

wherein the third predetermined utilization rate is lower than the second predetermined utilization rate and

wherein the scheduling engine is further adapted to schedule the job to be processed by one or more of the processors selected from the first, second, and third groups of processors.

17. The system of claim 12, wherein the scheduling engine is further adapted to:

hold the job in the queue when the sum of the number of the processors in the first and second groups is less than N; and

release the job for processing by the N processors selected from the first and second groups having the lowest current utilization rates of the job when the sum of the number of the processors in the first and second groups is greater than or equal to N.

18. The system of claim 12, wherein the utilization rate service engine is further adapted to determine a current utilization rate for processors in the first group;

and wherein the processor grouping engine is further adapted to re-designate the first group of processors to exclude those processors having a current utilization rate greater than a predetermined first utilization rate;

wherein the scheduling engine is further adapted to hold the job in the queue when the sum of the number of the processors in the re-designated first group and in the second group is less than N; and

wherein the scheduling engine is further adapted to release the job for processing by the N processors selected from the re-designated first group and from the second group having the lowest current utilization rates when the sum of the number of the processors in the re-designated first group and in the second groups is greater than or equal to N.

19. The system of claim 12,

wherein the utilization rate service engine is further adapted to determine a new current utilization rate for processors in the second group;

wherein the processor grouping engine is further adapted to re-designate the second group of processors to exclude those processors having a new current utilization rate greater than the second predetermined utilization rate; and

wherein the scheduling engine is further adapted to schedule the job to be processed by one or more of the processors selected from the first group of processors and the re-designated second group of processors.

20. The system of claim 12, wherein a plurality of processors are adapted to process the job in parallel.