Backfill scheduling for embarrassingly parallel jobs
Backfill scheduling for embarrassingly parallel jobs. A disclosed method includes: receiving an initial schedule having a plurality of jobs scheduled over time on a plurality of nodes, determining that a first job can be split into a plurality of sub-tasks that can respectively be performed in parallel on different nodes, splitting the first job into the plurality of sub-tasks, and moving a first sub-task from its position in the initial schedule to a new position to yield a first revised schedule.
1. A method comprising:
receiving an initial schedule of jobs, including a plurality of jobs, scheduled over time on a plurality of nodes;
determining 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;
determining a backfill window in the initial schedule of jobs, the backfill window having a window duration and a window node count;
separating the future job into a plurality of sub-tasks by their corresponding pre-defined durations:
generating 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;
removing the future job from the initial schedule;
adding the set of backfill sub-tasks into the backfill window to yield a revised schedule of jobs; and
executing the plurality of jobs and the set of backfill sub-tasks according to the revised schedule of jobs.
2. The method of claim 1 further comprising:
receiving job information for the future job including one of the following: the smallest sequential job length, the time required to run the smallest sequential job length, or the number of resources required to execute the smallest sequential job length; and
wherein generating a set of backfill sub-tasks is further based upon the job information.
3. The method 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 method of claim 1 further comprising:
combining 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 method of claim 1 wherein the plurality of sub-tasks are of equal length.
6. The method 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 non-contiguous backfill windows.
7. The method 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.