Backfill scheduling for embarrassingly parallel jobs

1. A computer program product comprising software stored on a non-transitory computer storage medium, the software comprising:

first program instructions programmed to receive an initial schedule of jobs, including a plurality of jobs, scheduled over time on a plurality of nodes;

second program instructions programmed to determine that a future job from the plurality of jobs can be split into a plurality of sub-tasks that can respectively be performed in parallel on different nodes, each sub-task of the plurality of sub-tasks being defined individually by corresponding pre-defined durations and corresponding sub-task node counts;

third program instructions programmed to determine a backfill window in the initial schedule of jobs, the backfill window having a window duration and a window node count;

fourth program instructions programmed to separate the future job into the plurality of sub-tasks by their corresponding pre-defined durations;

fifth program instructions programmed to generate a set of backfill sub-tasks from the plurality of sub-tasks based on the corresponding pre-defined durations of each sub-task of the plurality of sub-tasks, each backfill sub-task having a combined pre-defined duration matching the window duration, and having sub-task node counts that match the window node count;

sixth program instructions programmed to remove the future job from the initial schedule of jobs;

seventh program instructions programmed to add the set of backfill sub-tasks into the backfill window to yield a revised schedule of jobs; and

eighth program instructions programmed to execute the plurality of jobs and the set of backfill sub-tasks according to the revised schedule of jobs.

2. The computer program product of claim 1 further comprising:

seventh program instructions programmed to receive job information for the future job including one of the following: a smallest sequential job length, a time required to run the smallest sequential job length, or a number of resources required to execute the smallest sequential job length; and

wherein generating the set of backfill sub-tasks is further based upon the job information.

3. The computer program product of claim 1 wherein:

the pre-defined durations add up to the combined pre-defined duration being less than or equal to the window duration.

4. The computer program product of claim 1 further comprising:

ninth program instructions programmed to combine two or more sub-tasks of the set of backfill sub-tasks into one sub-task having one launch point and one completion point.

5. The computer program product of claim 1 wherein the plurality of sub-tasks are of equal length.

6. The computer program product of claim 1 wherein:

a plurality of backfill windows are identified and the set of backfill sub-tasks are run in the plurality of backfill windows such that at least two backfill sub-tasks are run in is non-contiguous backfill windows.

7. The computer program product of claim 1 , wherein determining the backfill window in the initial schedule of jobs further includes determining a plurality of backfill windows and the set of backfill sub-tasks are run in the plurality of backfill windows such that at least portions of two backfill sub-tasks are run in parallel on parallel nodes.

8. A computer system comprising:

a processor(s) set; and

a software storage device;

wherein:

the processor set is structured, located, connected and/or programmed to run software stored on the software storage device; and

the software comprises:

first program instructions programmed to receive an initial schedule of jobs, including a plurality of jobs, scheduled over time on a plurality of nodes;

second program instructions programmed to determine that a future job from the plurality of jobs can be split into a plurality of sub-tasks that can respectively be performed in parallel on different nodes, each sub-task of the plurality of sub-tasks being defined individually by corresponding pre-defined durations and corresponding sub-task node counts;

third program instructions programmed to determine a backfill window in the initial schedule of jobs, the backfill window having a window duration and a window node count;

fourth program instructions programmed to separate the future job into the plurality of sub-tasks by their corresponding pre-defined durations;

fifth program instructions programmed to generate a set of backfill sub-tasks from the plurality of sub-tasks based on the corresponding pre-defined durations of each sub-task of the plurality of sub-tasks, each backfill sub-task having a combined pre-defined duration matching the window duration, and having sub-task node counts that match the window node count;

sixth program instructions programmed to remove the future job from the initial schedule of jobs;

seventh program instructions programmed to add the set of backfill sub-tasks into the backfill window to yield a revised schedule of jobs; and

eighth program instructions programmed to execute the plurality of jobs and the set of backfill sub-tasks according to the revised schedule of jobs.

9. The computer system of claim 8 further comprising:

ninth program instructions programmed to receive job information for the future job including one of the following: a smallest sequential job length, a time required to run the smallest sequential job length, or a number of resources required to execute the smallest sequential job length; and

wherein generating the set of backfill sub-tasks is further based upon the job information.

10. The computer system of claim 8 wherein:

the pre-defined durations add up to the combined pre-defined duration being less than or equal to the window duration.

11. The computer system of claim 8 further comprising:

ninth program instructions programmed to combine two or more sub-tasks of the set of backfill sub-tasks into one sub-task having one launch point and one completion point.

12. The computer system of claim 8 wherein the plurality of sub-tasks are of equal length.

13. The computer system of claim 8 wherein:

a plurality of backfill windows are identified and the set of backfill sub-tasks are run in the plurality of backfill windows such that at least two backfill sub-tasks are run in is non-contiguous backfill windows.

14. The computer system of claim 8 , wherein determining the backfill window in the initial schedule of jobs further includes determining a plurality of backfill windows and the set of backfill sub-tasks are run in the plurality of backfill windows such that at least portions of two backfill sub-tasks are run in parallel on parallel nodes.