Dedicated heterogeneous node scheduling including backfill scheduling

• US 7,082,606 B2
• Filed: 04/30/2002
• Issued: 07/25/2006
• Est. Priority Date: 05/01/2001
• Status: Expired due to Fees

• 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: Hommes, Gregg, Eckert, Philip D., Wood, Robert R.
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): To, Jennifer N.
• Application Number:
  US10/137,014
• Publication Number:
  US 20020194248A1
• Time in Patent Office: 1,547 Days
• Field of Search: 718100-108, 703/20, 714/47, 709213-232, 710/200, 700/100
• 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 backfill scheduling dedicated heterogeneous nodes in a multi-node computing environment. Heterogeneous nodes are grouped into homogeneous node sub-pools. For each sub-pool, a free node schedule (FNS) is created so that the number of to chart the free nodes over time. For each prioritized job, using the FNS of sub-pools having nodes useable by a particular job, to determine the earliest time range (ETR) capable of running the job. Once determined for a particular job, scheduling the job to run in that ETR. If the ETR determined for a lower priority job (LPJ) has a start time earlier than a higher priority job (HPJ), then the LPJ is scheduled in that ETR if it would not disturb the anticipated start times of any HPJ previously scheduled for a future time. Thus, efficient utilization and throughput of such computing environments may be increased by utilizing resources otherwise remaining 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 a 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 a 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 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.

6. The method as in claim 1,

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

7. The method as in claim 1,

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

8. 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, each free node schedule comprising 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;

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.

9. The method as in claim 8,

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

10. The method as in claim 9,

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.

11. The method as in claim 10,

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.

12. The method as in claim 11,

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.

13. The method as in claim 8,

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.

14. The method as in claim 8,

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.

15. The method as in claim 8,

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.

16. The method as in claim 15,

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.

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

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