Method of automatically controlling the allocation of resources of a parallel processor computer system by calculating a minimum execution time of a task and scheduling subtasks against resources to execute the task in the minimum time

• US 5,325,525 A
• Filed: 04/04/1991
• Issued: 06/28/1994
• Est. Priority Date: 04/04/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Murphy, Marguerite C., Shan, Ming-Chien
• Primary Examiner(s): Chan, Eddie P.
• Application Number:
  US07/680,223
• Time in Patent Office: 1,181 Days
• Field of Search: 395/650, 395/725
• US Class Current: 718/104
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A method of controlling the allocation of resources in a parallel processor computer. A critical path for executing a task such as evaluating a database query is determined. The minimum time to execute the task assuming infinite resources such as processors and memory buffers is calculated. Resources are scheduled against subtasks so as to execute the task in the calculated minimum time. The number of resources would be required to meet the schedule is determined and if the computer has that many resources the schedule is carried out. Otherwise a revised execution time is calculated, preferably by using as a scaling factor the ratio between the number of required resources and the number of available resources. Then the schedule is adjusted so that the task can be executed in the revised time and the number of resources that would be required to meet the adjusted schedule is determined. If the computer has that many resources the schedule is carried out, otherwise the process is repeated. Preferably the process is halted if two iterations result in the same number of resources being needed.

Claims

1. A method of automatically controlling the operation of a computer system to execute a task, the computer system being of the kind that has a plurality of simultaneously operable resources, the task being of the kind that has a plurality of subtasks more than one of which could be executed simultaneously given enough resources, the method comprising the following steps executed automatically in the computer:

(a) calculating a minimum execution time that would be required to execute the task assuming the computer system has enough resources to simultaneously perform all the subtasks that could be performed simultaneously;

(b) preparing a subtask-resource schedule in which it is assumed that each said subtask will be provided with whatever resources would be necessary to execute that subtask such that adherence to the schedule would result in executing the task in the minimum execution time;

(c) determining how many resources would be required to satisfy the subtask-resource schedule;

(d) determining whether the computer system has the number of resources determined in the preceding step;

(e) responsive to a determination in the preceding step that the computer system has said number of resources, assigning the resources to the subtasks according to the subtask-resource schedule; and

responsive to a determination in the preceding step that the computer system does not have said number of resources, (1) calculating a revised execution time that has a longer duration than the minimum execution time, (2) adjusting the subtask-resource schedule by reducing the number of resources such that adherence to the adjusted schedule would result in executing the task in the revised execution time, (3) determining how many resources would be required to satisfy the adjusted schedule, and (4) looping back to step (d) to perform steps (d) and (e) again.

2. A method according to claim 1 wherein calculating the minimum execution time in step (a) comprises determining a critical path of substeps which must be executed sequentially, each such substep comprising one or more of the subtasks, determining the minimum time to execute each such substep if there were enough resources to execute all subtasks of that substep simultaneously, and summing the minimum times to get the minimum execution time.

3. A method according to claim 1 wherein calculating a revised execution time in step (e)(1) comprises forming a time scaling factor by taking the ratio of the number of resources that are available and the number of resources that are required, and scaling the execution time by the scaling factor to obtain the revised execution time.

4. A method according to claim 1 wherein a plurality of simultaneously operable resources comprises a plurality of processors and a plurality of memory buffers.

5. A method according to claim 4 wherein calculating a revised execution time in step (e)(1) comprises:

calculating an equivalence factor between processors and buffers,

using the equivalence factor to calculate a first number representative of the numbers of processors and buffers that are available and a second number representative of the requisite numbers of processors and buffers,

forming a time scaling factor by taking the ratio of the first and second numbers, and

scaling the execution time by the scaling factor to obtain the revised execution time.

6. A method of automatically controlling the operation of a computer system to evaluate a query, the computer system being of the kind that has a plurality of memory buffers, a plurality of processors, a plurality of storage devices, and a plurality of pages of data in the storage devices, the system characterized by a minimum page transfer time required to transfer a page of data from a storage device into a memory buffer, the query being of the kind that has a plurality of subqueries more than one of which could be executed simultaneously given enough resources, the method comprising the following steps executed automatically in the computer:

(a) providing a plan for evaluating the query;

(b) calculating a minimum evaluation time that would be required to evaluate the query according to the plan in consideration of the minimum page transfer time assuming the computer system had enough processors and buffers to simultaneously evaluate all the subqueries that could be evaluated simultaneously according to the plan;

(c) preparing a schedule of subqueries to processors and buffers in which schedule it is assumed that each subquery will be provided with whatever processors and buffers would be necessary to evaluate that subquery such that adherence to the schedule would result in evaluating the query in the minimum evaluation time;

(d) determining how many processors and how many buffers would be required to satisfy the schedule;

(e) determining whether the computer system has the number of processors and buffers determined in the preceding step; and

(f) responsive to a determination in step (e) that the computer system has said number of processors and buffers, assigning the processors and buffers to the subqueries according to the schedule; and

responsive to a determination in step (e) that the computer system does not have said number of processors and buffers;

(1) calculating a revised evaluation time that is longer than the minimum evaluation time,

(2) adjusting the schedule by reducing the number of processors and buffers such that adherence to the adjusted schedule would result in evaluating the query in the revised evaluation time,

(3) determining how many processors and buffers would be required to satisfy the adjusted schedule, and

(4) looping back to step (e) to perform steps (e) and (f) again.

7. A method according to claim 6 wherein calculating the minimum evaluation time in step (b) comprises determining a critical path of partial queries which must be evaluated sequentially, each such partial query comprising one or more of the subqueries, determining the minimum time to evaluate each such partial query if there were enough resources to execute all portions of that partial query simultaneously, and summing the minimum times to get the minimum execution time.

8. A method according to claim 6 wherein calculating a revised evaluation time in step (f)(1) comprises:

calculating a first number representative of the numbers of processors and buffers that are available and a second number representative of the requisite numbers of processors and buffers;

forming a time scaling factor by taking the ratio of the first and second numbers; and

scaling the evaluation time by the scaling factor to obtain the revised evaluation time.

9. A method according to claim 8 and further comprising calculating an equivalence factor between processors and buffers and using said equivalence factor to calculate the first and second numbers.

10. A method of automatically controlling the operation of a computer system to evaluate a query, the computer system being of the kind that has a plurality of memory buffers, a plurality of processors, a plurality of storage devices, and a plurality of pages of data in the storage devices, the system characterized by a minimum page transfer time required to transfer a page of data from a storage device into a memory buffer, the query being of the kind that has a plurality of subqueries more than one of which could be executed simultaneously given enough resources, the method comprising the following steps executed automatically in the computer:

(a) providing a plan for evaluating the query;

(b) calculating a minimum evaluation time that would be required to evaluate the query according to the plan in consideration of the minimum page transfer time assuming the computer system had enough processors and buffers to simultaneously evaluate all the subqueries that could be evaluated simultaneously according to the plan;

(c) preparing a schedule of subqueries to processors and buffers in which schedule it is assumed that each subquery will be provided with whatever processors and buffers would be necessary to evaluate that subquery such that adherence to the schedule would result in evaluating the query in the minimum evaluation time;

(d) determining how many processors and how many buffers would be required to satisfy the schedule;

(e) determining whether the computer system has the number of processors and buffers determined in the preceding step; and

(f) responsive to a determination in step (e) that the computer system has said number of processors and buffers, assigning the processors and buffers to the subqueries according to the schedule; and

responsive to a determination in step (e) that the computer system does not have said number of processors and buffers;

(1) calculating a revised evaluation time that is longer than the minimum evaluation time,

(2) adjusting the schedule by reducing the number of processors and buffers such that adherence to the adjusted schedule would result in evaluating the query in the revised evaluation time,

(3) determining how many processors and buffers would be required to satisfy the adjusted schedule,

(4) determining whether the computer system has the number of processors and buffers determined in the preceding substep,

(5) responsive to a determination in substep (4) that the computer system has said number of processors and buffers, assigning the processors and buffers to the subqueries according to the adjusted schedule,

(6) responsive to a determination in substep (4) that the computer system does not have said number of processors and buffers, determining whether the number of processors and buffers determined in substep (3) is smaller than the number of processors and buffers determined in any previous iteration of step (d) and of substep (3), and, if not, assigning the subqueries according to the adjusted schedule to as many processors and buffers as are available for parallel execution,

(7) responsive to a determination in substep (4) that the computer system does not have said number of processors and buffers and responsive to a determination in substep (6) that the number of processors and buffers determined in substep (3) is smaller than the number of processors and buffers determined in any substep (3) is smaller than the number of processors and buffers determined in any previous iteration of step (d) and of substep (3), looping back to step (f)(1) to perform steps (f)(1) through (f)(7) again.

11. A method according to claim 10 wherein calculating the minimum evaluation time in step (b) comprises determining a critical path of partial queries which must be evaluated sequentially, each such partial query comprising one or more of the subqueries, determining the minimum time to evaluate each such partial query if there were enough resources to execute all portions of that partial query simultaneously, and summing the minimum times to get the minimum execution time.

12. A method according to claim 10 wherein calculating a revised evaluation time in step (f)(1) comprises:

calculating a first number representative of the numbers of processors and buffers that are available and a second number representative of the requisite numbers of processors and buffers;

forming a time scaling factor by taking the ratio of the first and second numbers; and

scaling the evaluation time by the scaling factor to obtain the revised evaluation time.

13. A method according to claim 12 and further comprising calculating an equivalence factor between processors and buffers and using said equivalence factor to calculate the first and second numbers.