Dedicated heterogeneous node scheduling including backfill scheduling

• US 20020194248A1
• Filed: 04/30/2002
• Published: 12/19/2002
• Est. Priority Date: 05/01/2001
• Status: Active Grant

• Current Assignee: Lawrence Livermore National Security LLC (Government of the United States of America)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Wood, Robert R., Hommes, Gregg, Eckert, Philip D.
• Granted Patent: US 7,082,606 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• 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

Abstract

A method and system for job scheduling (including backfill scheduling) dedicated heterogeneous nodes in a multi-node computing environment. Heterogeneous nodes in the computing environment are first discovered and grouped into homogeneous node sub-pools. For each sub-pool, a free node schedule is created so that the number of free nodes in the sub-pool may be charted over time. For each job in order of priority, using the free node schedules of only those sub-pools having nodes which may be used by a particular job, to determine the earliest time range capable of running the job. Once the earliest time range is determined for a particular job, scheduling the job to run in that earliest time range. If the earliest time range determined for a lower priority job has a start time occurring earlier than a higher priority job, then the lower priority job is scheduled to run in that earliest time range if doing so would not disturb the anticipated start times of any higher priority job previously scheduled to run at a future time. In this manner, the overall efficient utilization and throughput of dedicated heterogeneous multi-node computers may be increased without degrading utilization or throughput of higher priority jobs by utilizing resources that would otherwise remain idle.

Claims

1. A method for job scheduling in a dedicated heterogeneous multi-node computing environment, the method comprising:

grouping the nodes into homogeneous node sub-pools each comprising nodes of equal capacity;

for each sub-pool, creating a corresponding free node schedule which charts the number of free nodes in the sub-pool over time;

receiving a plurality of jobs to be scheduled;

ordering the jobs by job priority;

for each job in order of job priority,

(a) identifying a conforming sub-pool set comprising conforming nodes of sufficient capacity suitable for use by the job,

(b) determining an earliest available time range from the free node schedule(s) of the conforming sub-pool set, where the earliest available time range has a sufficient duration and a sufficient number of conforming free nodes to complete the job, and

(c) scheduling the job for execution in the earliest available time range; and

executing the jobs at their respective earliest available time ranges.

2. The method as in claim 1,

wherein, upon a determination that the earliest available time range of the job starts at the present time, the step of scheduling the job comprises presently scheduling the job for immediate execution by allocating as many conforming free nodes to the job as required thereby in order of increasing node capacity starting with the conforming free nodes of a lowest order conforming sub-pool.

3. The method as in claim 1,

wherein, upon a determination that the earliest available time range of the job starts at a future time, the step of scheduling the job comprises pseudo-scheduling the job for future execution by marking for dedication to the job as many conforming free nodes in the earliest available time range as required by the job, in order of increasing node capacity starting with the conforming free nodes of a lowest order conforming sub-pool.

4. The method as in claim 3,

wherein, upon a determination that a start time of the earliest available time range of a lower priority job to be scheduled occurs prior to a future start time of the earliest available time range of at least one of a set of higher priority jobs previously pseudo-scheduled for future execution, the step of scheduling the lower priority job comprises backfill scheduling the lower priority job for execution starting ahead of the future start time of the at least one higher priority job, whereby anticipated future start times of the previously pseudo-scheduled set of higher priority jobs are not delayed by the backfill scheduling.

5. The method as in claim 1,

wherein each free node schedule comprises at least one entry having a timestamp value specifying an end time of a corresponding time slot, and a scalar value specifying the number of free nodes in the corresponding sub-pool during the time slot.

6. The method as in claim 5,

wherein each free node schedule includes an initialization entry having an infinite timestamp value, and a maximum scalar value specifying the total number of nodes in the corresponding sub-pool.

7. The method as in claim 6,

wherein each free node schedule further includes at least one additional entry, where the entries are arranged in order of increasing timestamp value with the initialization entry designated as a last entry.

8. The method as in claim 7,

wherein the step of creating each free node schedule includes normalizing the free node schedules of the sub-pools so that every free node schedule has the same number of entries, and same rank entries have identical timestamp values.

9. The method as in claim 8,

wherein the step of creating each free node schedule further includes converting the timestamp value of each entry to a time duration value of the time slot.

10. The method as in claim 5,

wherein the earliest available time range is determined by further determining a least number of entries to cover an expected execution time of the job.

11. The method as in claim 5,

wherein, upon determining that the earliest available time range includes the time slot of a first entry of any of the free node schedule(s) of the conforming sub-pool set, the step of scheduling the job comprises presently scheduling the job for immediate execution by allocating as many conforming free nodes to the job as required thereby in order of increasing node capacity starting with the conforming free nodes of a lowest order conforming sub-pool.

12. The method as in claim 5,

wherein, upon determining that the earliest available time range does not include the time slot of a first entry of any of the free node schedule(s) of the conforming sub-pool set, the step of scheduling the job comprises pseudo-scheduling the job for future execution by marking for dedication to the job as many conforming free nodes in the earliest available time range as required by the job, in order of increasing node capacity starting with the conforming free nodes of a lowest order conforming sub-pool.

13. The method as in claim 12,

wherein, upon determining that a start time of the earliest available time range of a lower priority job to be scheduled occurs prior to a future start time of the earliest available time range of at least one of a set of higher priority jobs previously pseudo-scheduled for future execution, the step of scheduling the lower priority job comprises backfill scheduling the lower priority job for execution starting ahead of the future start time of the at least one higher priority job, whereby anticipated future start times of the previously pseudo-scheduled set of higher priority jobs are not delayed by the backfill scheduling.

14. The method as in claim 1,

wherein each job received to be scheduled includes a set of job specifications provided by a user for executing the job, including minimum node capacity, expected job execution time, and number of nodes needed.

15. The method as in claim 1,

further comprising discovering the nodes to be grouped in the dedicated heterogeneous multi-node computing environment including discovering the capacities of the discovered nodes.

16. The method as in claim 1,

further comprising grouping the sub-pools into pools for partitioning the computing environment.

17. A method for job scheduling in a dedicated heterogeneous multi-node computing environment, the method comprising:

grouping the nodes into homogeneous node sub-pools each comprising nodes of equal capacity;

for each sub-pool, creating a corresponding free node schedule which charts the number of free nodes in the sub-pool over time;

receiving a plurality of jobs to be scheduled;

ordering the jobs by job priority;

for each job in order of job priority,

(a) identifying a conforming sub-pool set comprising conforming nodes of sufficient capacity suitable for use by the job,

(b) determining an earliest available time range from the free node schedule(s) of the conforming sub-pool set, where the earliest available time range has a sufficient duration and a sufficient number of conforming free nodes to complete the job, and

(c) scheduling the job for execution in the earliest available time range, including, (1) upon a determination that the earliest available time range of the job starts at the present time, presently scheduling the job for immediate execution by allocating as many conforming free nodes to the job as required thereby in order of increasing node capacity starting with the conforming free nodes of a lowest order conforming sub-pool, (2) upon a determination that the earliest available time range of the job starts at a future time, pseudo-scheduling the job for future execution by marking for dedication to the job as many conforming free nodes in the earliest available time range as required by the job, in order of increasing node capacity starting with the conforming free nodes of a lowest order conforming sub-pool, and (3) upon a determination that a start time of an earliest available time range of a lower priority job to be scheduled occurs prior to a future start time of an earliest available time range of at least one of a set of higher priority jobs previously pseudo-scheduled for future execution, backfill scheduling the lower priority job for execution starting ahead of the future start time of the at least one of the set of higher priority jobs, whereby anticipated future start times of the previously pseudo-scheduled set of higher priority jobs are not delayed by the backfill scheduling; and

executing the jobs at their respective earliest available time ranges.

18. A computer system for job scheduling in a dedicated heterogeneous node computer environment, the computer system comprising:

a data mining component that discovers the nodes and node capacities in the scheduling environment;

a node grouping component that groups the discovered nodes into homogeneous node sub-pools each comprising nodes of equal capacity;

a free node schedule forming component that creates for each sub-pool a corresponding free node schedule which charts the number of free nodes in the corresponding sub-pool over time;

a user interface for receiving a plurality of jobs to be scheduled;

an ordering component for ordering the jobs by job priority;

a job analyzing component that, for each job in order of job priority,

(a) identifies a conforming sub-pool set comprising conforming nodes of sufficient capacity suitable for use by the job, and

(b) determines an earliest available time range from the free node schedule(s) of the conforming sub-pool set, where the earliest available time range has a sufficient duration and a sufficient number of conforming free nodes to complete the job; and

a job scheduling component for scheduling each job for execution in the respective earliest available time range.

19. A computer-readable medium containing instructions for controlling a computer system to schedule jobs in a dedicated heterogeneous multi-node computing environment, by:

grouping the nodes into homogeneous node sub-pools each comprising nodes of equal capacity;

for each sub-pool, creating a corresponding free node schedule which charts the number of free nodes in the sub-pool over time;

receiving a plurality of jobs to be scheduled;

ordering the jobs by job priority;

for each job in order of job priority,

(a) identifying a conforming sub-pool set comprising conforming nodes of sufficient capacity suitable for use by the job,

(b) determining an earliest available time range from the free node schedule(s) of the conforming sub-pool set, where the earliest available time range has a sufficient duration and a sufficient number of conforming free nodes to complete the job, and

(c) scheduling the job for execution in the earliest available time range; and

executing the jobs at their respective earliest available time ranges; and

20. A computer-readable medium containing instructions for controlling a computer system to schedule jobs in a dedicated heterogeneous multi-node computing environment, by:

grouping the nodes into homogeneous node sub-pools each comprising nodes of equal capacity;

for each sub-pool, creating a corresponding free node schedule which charts the number of free nodes in the sub-pool over time;

receiving a plurality of jobs to be scheduled;

ordering the jobs by job priority;

for each job in order of job priority,

(a) identifying a conforming sub-pool set comprising conforming nodes of sufficient capacity suitable for use by the job,

(b) determining an earliest available time range from the free node schedule(s) of the conforming sub-pool set, where the earliest available time range has a sufficient duration and a sufficient number of conforming free nodes to complete the job, and

(c) scheduling the job for execution in the earliest available time range, including, (1) upon a determination that the earliest available time range of the job starts at the present time, presently scheduling the job for immediate execution by allocating as many conforming free nodes to the job as required thereby in order of increasing node capacity starting with the conforming free nodes of a lowest order conforming sub-pool, (2) upon a determination that the earliest available time range of the job starts at a future time, pseudo-scheduling the job for future execution by marking for dedication to the job as many conforming free nodes in the earliest available time range as required by the job, in order of increasing node capacity starting with the conforming free nodes of a lowest order conforming sub-pool, and (3) upon a determination that a start time of an earliest available time range of a lower priority job to be scheduled occurs prior to a future start time of an earliest available time range of at least one of a set of higher priority jobs previously pseudo-scheduled for future execution, backfill scheduling the lower priority job for execution starting ahead of the future start time of the at least one of the set of higher priority jobs, whereby anticipated future start times of the previously pseudo-scheduled set of higher priority jobs are not delayed by the backfill scheduling; and

executing the jobs at their respective earliest available time ranges.