Jobstream Planner Considering Network Contention & Resource Availability

• US 20080250420A1
• Filed: 06/18/2008
• Published: 10/09/2008
• Est. Priority Date: 03/22/2005
• Status: Active Grant

• Current Assignee: Kyndryl Incorporated
• Original Assignee: Bella Voldman, Creighton M. Hicks, Kyle Boon, Viktors Berstis
• Inventors: Berstis, Viktors, Boon, Kyle, Hicks, Creighton M., Voldman, Bella
• Granted Patent: US 8,640,132 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• 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
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

Disclosed is a computer-implemented planning process that aids a system administrator in the task of creating a job schedule. The process treats enterprise computing resources as a grid of resources, which provides greater flexibility in assigning resources to jobs. During the planning process, an administrator or other user, or software, builds a job-dependency tree. Jobs are then ranked according to priority, pickiness, and network centricity Difficult and problematic jobs then are assigned resources and scheduled first, with less difficult jobs assigned resources and scheduled afterwards. The resources assigned to the most problematic jobs then are changed iteratively to determine if the plan improves. This iterative approach not only increases the efficiency of the original job schedule, but also allows the planning process to react and adapt to new, ad-hoc jobs, as well as unexpected interruptions in resource availability.

Claims

1. A computer-implemented planning process for scheduling multiple jobs in a digital data processing system while considering network and processing resources in the digital data processing system, the planning process comprising:

steps for building a job-dependency tree;

steps for ranking each job;

steps for assigning processing resources to each job;

steps for scheduling each job so that each job executes by a user-requested time; and

steps for optimizing the schedule of jobs.

2. The process of claim 1 wherein the steps for ranking each job comprise:

steps for identifying all plannable jobs;

steps for calculating the pickiness of each plannable job;

steps for calculating the network centricity of each plannable job; and

steps for calculating a job rank for each job, where each job'"'"'s rank is equal to the sum of the job'"'"'s priority, pickiness, and network centricity.

3. A computer-implemented planning process for scheduling multiple jobs in a digital data processing system while considering network and processing resources in the digital data processing system, wherein each job has a user-assigned priority, the planning process comprising:

building a dependency tree;

identifying all plannable jobs;

calculating the pickiness of each plannable job;

calculating the network centricity of each plannable job;

calculating a job rank for each job, where each job'"'"'s rank is equal to the sum of the job'"'"'s priority, pickiness, and network centricity; and

assigning resources to the job with the highest job rank.

4. The process of claim 3 wherein the step of calculating a plannable job'"'"'s pickiness comprises the steps of:

estimating the job'"'"'s runtime;

determining the job'"'"'s time frame;

determining the number of machines in the digital data processing system that have sufficient capacity to execute the job within the job'"'"'s time frame; and

dividing the number of machines that have sufficient capacity by the total number of machines in the digital data processing system.

5. The process of claim 3 wherein the step of calculating a plannable job'"'"'s network centricity comprises the steps of:

determining the preferred path between each pair of machines in the digital data processing system;

determining the maximum bandwidth of each preferred path;

determining the tick value of each preferred path;

identifying each machine that could execute the job;

calculating the data transfer time between each machine that could execute the job and any remote machine with which the job must exchange data;

multiplying the result of the previous step by the maximum tick value of any preferred path; and

averaging the result of the previous step for all machines that could execute the job.

6. The process of claim 3 wherein the step of assigning resources to the job with the highest rank comprises:

calculating the job'"'"'s total execution time on each machine that could execute the job;

adding the job'"'"'s total execution time on each machine that could execute the job and the job'"'"'s network centricity; and

assigning the job to the machine on which the previous step produces the highest value.

7. The process of claim 3 further comprising the steps of:

repeating each step until all jobs are scheduled and resources are assigned to all jobs;

evaluating the schedule'"'"'s fitness;

switching resources assigned to a first job and a second job;

re-evaluating the schedule'"'"'s fitness with the resources switched; and

comparing the schedule'"'"'s fitness with the resources switched and the schedule'"'"'s fitness before switching resources; and

retaining the assignment of resources that produces the best schedule fitness.

8. The process of claim 4 further comprising the steps of:

repeating each step until all jobs are scheduled and resources are assigned to all jobs;

evaluating the schedule'"'"'s fitness;

switching resources assigned to a first job and a second job;

re-evaluating the schedule'"'"'s fitness with the resources switched; and

comparing the schedule'"'"'s fitness with the resources switched and the schedule'"'"'s fitness before switching resources; and

retaining the assignment of resources that produces the best schedule fitness.

9. The process of claim 5 further comprising the steps of.

repeating each step until all jobs are scheduled and resources are assigned to all jobs;

evaluating the schedule'"'"'s fitness;

switching resources assigned to a first job and a second job;

re-evaluating the schedule'"'"'s fitness with the resources switched; and

comparing the schedule'"'"'s fitness with the resources switched and the schedule'"'"'s fitness before switching resources; and

retaining the assignment of resources that produces the best schedule fitness.

10. The process of claim 6 further comprising the steps of:

repeating each step until all jobs are scheduled and resources are assigned to all jobs;

evaluating the schedule'"'"'s fitness;

switching resources assigned to a first job and a second job;

re-evaluating the schedule'"'"'s fitness with the resources switched; and

comparing the schedule'"'"'s fitness with the resources switched and the schedule'"'"'s fitness before switching resources; and

retaining the assignment of resources that produces the best schedule fitness.

11. The process of claim 7 wherein the steps of evaluating and re-evaluating the schedule'"'"'s fitness comprise evaluating each job'"'"'s fitness, and evaluating each job'"'"'s fitness comprises the steps of:

assigning an initial value to the job'"'"'s fitness;

multiplying the job'"'"'s priority by a user-specified weight and subtracting the resulting product from the initial value;

adding a value to the resulting product that is proportional to the time between the predicted end of the job'"'"'s execution and the job'"'"'s deadline; and

subtracting a value from the resulting sum that is proportional to the tick value of the preferred path between the machine assigned to execute the job and any remote machine with which the job must exchange data.

12. The process of claim 8 wherein the steps of evaluating and re-evaluating the schedule'"'"'s fitness comprise evaluating each job'"'"'s fitness, and evaluating each job'"'"'s fitness comprises the steps of:

assigning an initial value to the job'"'"'s fitness;

multiplying the job'"'"'s priority by a user-specified weight and subtracting the resulting product from the initial value;

adding a value to the resulting product that is proportional to the time between the predicted end of the job'"'"'s execution and the job'"'"'s deadline; and

subtracting a value from the resulting sum that is proportional to the tick value of the preferred path between the machine assigned to execute the job and any remote machine with which the job must exchange data.

13. The process of claim 9 wherein the steps of evaluating and re-evaluating the schedule'"'"'s fitness comprise evaluating each job'"'"'s fitness, and evaluating each job'"'"'s fitness comprises the steps of;

assigning an initial value to the job'"'"'s fitness;

multiplying the job'"'"'s priority by a user-specified weight and subtracting the resulting product from the initial value;

adding a value to the resulting product that is proportional to the time between the predicted end of the job'"'"'s execution and the job'"'"'s deadline; and

subtracting a value from the resulting sum that is proportional to the tick value of the preferred path between the machine assigned to execute the job and any remote machine with which the job must exchange data.

14. The process of claim 10 wherein the steps of evaluating and re-evaluating the schedule'"'"'s fitness comprise evaluating each job'"'"'s fitness, and evaluating each job'"'"'s fitness comprises the steps of;

assigning an initial value to the job'"'"'s fitness;

multiplying the job'"'"'s priority by a user-specified weight and subtracting the resulting product from the initial value;

adding a value to the resulting product that is proportional to the time between the predicted end of the job'"'"'s execution and the job'"'"'s deadline; and

subtracting a value from the resulting sum that is proportional to the tick value of the preferred path between the machine assigned to execute the job and any remote machine with which the job must exchange data.