Scheduling system method and apparatus for a cluster

• US 20030135621A1
• Filed: 12/06/2002
• Published: 07/17/2003
• Est. Priority Date: 12/07/2001
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Romagnoli, Emmanuel
• Application Number:
  US10/313,903
• Publication Number:
  US 20030135621A1
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

The invention provides for a method of optimizing a task-scheduling system where the method comprises decomposing one or more parallel programs into its component tasks and dynamically redistributing the parallel programs tasks into any available idle nodes in such a way that the execution time of the parallel program is decreased. The parallel programs, or jobs, may be represented as unitary two-dimensional blocks equating to the amount of time that the job will take to execute for a specified number of processors, or nodes, wherein the jobs are queued in, or dropped into, in an array whose width corresponds to the total number of available nodes in any single time interval. In one embodiment, the first phase of the technique may implement an algorithm to position each job in the array. The invention also provides extensions to take into account real-world behavior such as finite inter-processor communication time and context switching between jobs. Applications include finite element analysis, computationally intensive numerical calculations, modeling and statistical analysis of experimental data.

Claims

1. A method of optimizing a task-scheduling system comprising decomposing one or more parallel programs into its component tasks and dynamically redistributing the parallel programs tasks into any available idle nodes in such a way that the execution time of the parallel program is decreased.

9. A method of optimizing a task-scheduling system as claimed in any one of claims 1 to 8 wherein the tasks may have variable duration from time-unitary, thus representing tasks that require varying computational power and when queued, are represented as distorted in the time axis.

10. A method of optimizing a task-scheduling system as claimed in any one of claims 1 to 9 wherein the horizontal axis of the queue bin representing the nodes is unequally dimensioned, thus representing a heterogeneous cluster of nodes where some nodes have different computational power.

11. A method of opting a task-scheduling system as claimed in any one of claims 1 to 10 wherein the nodes are unequally spaced, the resulting data flow graph includes tasks which have an apparent difference in duration.

12. A method of optimizing a task-scheduling system as claimed in claim 11 wherein the allocation of tasks to holes is adapted to take into account the apparent time-distortion of the tasks.

13. A method of optimizing a task-scheduling system as claimed in any preceding claims wherein the data flow graph is adapted to take into account the time required by the processor to change its working context.

14. A method of optimizing a task-scheduling system as claimed in claim 13 wherein the tasks are distorted in the time axis to allow for over-duration representing the time needed for the processor to change working context.

15. A network of computing resources configured to operate in accordance with any of claims 1 to 14.

16. A computing device adapted to operate a task scheduling system in accordance with the method as claimed in any of claims 1 to 14.

2. A method of optimizing a task-scheduling system comprising representing one or more parallel programs, or jobs, as unitary two-dimensional blocks equating to the amount of time that the job will take to execute for a specified number of processors, or nodes, wherein the jobs are queued in an array whose width corresponds to the total number of available nodes in any single time interval, wherein each job is positioned in the array according to a block packing algorithm.

3. A method of optimizing a task-scheduling system as claimed in claim 2 wherein the block packing algorithm is adapted such that the packing of the jobs at the block level of aggregation is substantially optimized for any arrangement of jobs in the array.

4. A method of optimizing a task-scheduling system as claimed in any one of claims 2 or 3 further including the step of decomposing one or more jobs into their component time-unitary tasks and dynamically redistributing the tasks into any available idle nodes in such a way as to exploit any idle nodes within the structure of any of the jobs in the array thereby decreasing the execution time of at least one of the jobs.

5. A method of optimizing a task-scheduling system as claimed in any one of claims 2 to 4 wherein the width of the block represents the needed computational power and the height of the block corresponds to the expected or required duration of the job.

6. A method of optimizing a task-scheduling system as claimed in any one of claims 2 to 5 wherein in order to represent a homogeneous cluster of nodes, the array is represented by a bin having a horizontal, equally dimensioned array of nodes, and a vertically, equally spaced, time increment.

7. A method of optimizing a task-scheduling system as claimed in any one of claims 2 to 6 wherein in order to represent a heterogeneous cluster of nodes, the array is represented by a bin having a horizontal, unequally dimensioned, array of nodes, and/or a vertically, unequally spaced, time increment.

8. A method of creating and/or modifying a data flow graph in a parallel multicomputer system, comprising the steps of:

characterizing one or more jobs in terms of expected execution duration and computational power needs;

placing the jobs in a queue, the queue viewed as a two-dimensional array of nodes versus time, according to a bin-packing algorithm;

locating idle computation periods, or holes, between the jobs;

scanning each of the jobs in order to build a data flow graph which includes reference to the holes;

scanning the queue from earliest to the last, and attempting to move each task down in the queue by analyzing the position of each task in comparison to the position of the lowest holes in the data structure and if the hole is lower than the task, moving the task in the queue to fill the hole and thus updating the data flow graph; and

repeating the scanning process until the maximum number of available holes have been filled and a modified data flow graph has been created.