# US 2015/0178124 A1 · Backfill scheduling for embarrassingly parallel jobs

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0178124 A1
- Document ID: US20150178124A1
- Status: Published application
- Kind: A1
- Application number: 14/138,239
- Filed: 2013-12-23
- Published: 2015-06-25
- Earliest claimed: 2013-12-23
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Manish Modani; Giridhar M. Prabhakar; Ravindra R. Sure
- Web page: https://patentgrep.com/patent/US20150178124A1

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 2209/483: Multiproc
- G06F 2209/5017: Task decomposition
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

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.

## Claims

### Claim at position 1

1-6. (canceled)

### Claim 7

A computer program product comprising software stored on a software storage device, 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 first 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;
third program instructions programmed to split the first job into the plurality of sub-tasks; and
fourth program instructions programmed to move a first sub-task from its position in the initial schedule to a new position to yield a first revised schedule;
wherein:
the software is stored on a software storage device in a manner less transitory than a signal in transit.

### Claim 8 (depends on 7)

The computer program product of claim 7 further comprising:
fifth program instructions programmed to receive job information for the first 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 the splitting action is based upon the job information.

### Claim 9 (depends on 7)

The computer program product of claim 7 further comprising:
fifth program instructions programmed to determine a backfill window having a first length; and
sixth program instructions programmed to, responsive to determining a backfill window, move a set of the plurality of sub-tasks having a second length from a position in the initial schedule to the backfill window to yield a revised schedule;
wherein:
the second length is less than or equal to the first length.

### Claim 10 (depends on 7)

The computer program product of claim 7 further comprising:
fifth program instructions programmed to combine two or more sub-tasks of the plurality of sub-tasks into one longer sub-task having one launch point and one completion point.

### Claim 11 (depends on 7)

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

### Claim 12 (depends on 7)

The computer program product of claim 7 further including:
fifth program instructions programmed to move a second sub-task from its position in the initial schedule to a position that is non-contiguous to the new position of the first sub-task to yield a second revised schedule.

### Claim 13

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 first 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;
third program instructions programmed to split the first job into the plurality of sub-tasks; and
fourth program instructions programmed to move a first sub-task from its position in the initial schedule to a new position to yield a first revised schedule.

### Claim 14 (depends on 13)

The computer system of claim 13 further comprising:
fifth program instructions programmed to receive job information for the first 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 the splitting action is based upon the job information.

### Claim 15 (depends on 13)

The computer system of claim 13 further comprising:
fifth program instructions programmed to determine a backfill window having a first length; and
sixth program instructions programmed to, responsive to determining a backfill window, move a set of the plurality of sub-tasks having a second length from a position in the initial schedule to the backfill window to yield a revised schedule;
wherein:
the second length is less than or equal to the first length.

### Claim 16 (depends on 13)

The computer system of claim 13 further comprising:
fifth program instructions programmed to combine two or more sub-tasks of the plurality of sub-tasks into one longer sub-task having one launch point and one completion point.

### Claim 17 (depends on 13)

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

### Claim 18 (depends on 13)

The computer system of claim 13 further including:
fifth program instructions programmed to move a second sub-task from its position in the initial schedule to a position that is non-contiguous to the new position of the first sub-task to yield a second revised schedule.
