Program execution control in parallel processor system for parallel execution of plural jobs by selected number of processors

• US 5,752,030 A
• Filed: 08/04/1993
• Issued: 05/12/1998
• Est. Priority Date: 08/10/1992
• Status: Expired due to Fees

• Current Assignee: Parker Hannifin Customer Support, Inc. (Parker-Hannifin Corporation)
• Original Assignee: Hitachi, Ltd.
• Inventors: Okochi, Toshio, Konno, Chisato
• Primary Examiner(s): Harrity, John E.
• Assistant Examiner(s): FOLLANSBEE, JOHN A
• Application Number:
  US08/101,993
• Time in Patent Office: 1,742 Days
• Field of Search: 395/650, 395/700, 395/800, 395/672, 395/673, 395/674, 395/671, 395/670, 395/676, 395/572
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/5014 Reservation
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals

Abstract

In submitting each job in a parallel processing system provided with a plurality of processors, execution conditions such as a requested minimum processor number, an upper limit used processor number and a requested execution time are designated for each job and the judgement of whether or not processors equal in number to the requested minimum processor number required by a leading one of execution waiting jobs are in idle states is made for the leading job by use of a table for managing the status of utilization of processors for each job executed and the number of idle processors, a table for managing processors occupied or used by each operating job and a lapse time and a table for managing the execution conditions of each execution waiting job. When idle processors to be assigned are lacking, information in the above tables is used to judge whether a wait until processors corresponding to a number required by that job become idle states is taken without activating a subsequent job or the subsequent job should be activated ahead.

Claims

1. A job execution control method in a parallel processor system provided with a plurality of processors, comprising the steps of:

(a) storing, for each of a plurality of jobs waiting for execution thereof in the parallel processor system,

a requested processor number which is designated with respect to that job and which represents a requested minimum processor number required for executing said each job,

an upper limit used processor number representative of an upper limit number of processors to be used for each of the execution waiting jobs, and

a requested execution time which represents a maximum job execution time when that job is executed by processors equal in number to the requested processor number stored for that job;

(b) judging, at a point of time when some idle processors are generated, whether or not the requested processor number stored for an earliest one of the plurality of execution waiting jobs for which a request for execution is issued earliest is not larger than the total number of generated idle processors;

(c) assigning processors not smaller in number than the requested processor number and not larger than the upper limit used processor number stored for the earliest job, to the earliest job to activate the earliest job in the case where said judging in said step (b) is that the requested processor number stored for the earliest job is not larger than the total number of generated idle processors;

(d) predicting an instant of time of completion of each of one or plural jobs under execution on the basis of a requested execution time stored for that job and an instant of time of start of execution of that job, where said judging in said step (b) is that the requested processor number stored for the earliest job is larger than the total number of generated idle processors by determining a corrected requested execution time representative of the maximum execution time of each job under execution when that job is executed by processors equal in number to not the requested processor stored for that job, but a processor number assigned to that job, on the basis of the requested minimum processor number stored for that job, the processor number assigned to that job and the requested execution time stored for that job;

(e) predicting a time of lapse from a present instant of time to a time when a generation of idle processors is not smaller in number than the requested processor number stored for the earliest job on the basis of a predicted completion time instant of each job under execution;

(f) judging, which of the earliest job and one of jobs subsequent to the earliest job should be activated preferentially for improved system throughput, on the basis of at least the predicted lapse time;

(g) waiting for the generation of idle processors not smaller in number than the requested processor number stored for the earliest job where said judging in said step (f) is that the earliest job should be activated preferentially;

(h) performing said steps (b) and (c) for the subsequent job where said judging in said step (f) is that the one subsequent job should be activated preferentially; and

(i) executing the jobs with the processors.

2. A job execution control method in a parallel processor system provided with a plurality of processors, comprising the steps of:

(a) storing, for each of a plurality of jobs waiting for execution thereof in the parallel processor system,

a requested processor number which is designated with respect to that job and which represents a requested minimum processor number required for executing said each job,

an upper limit used processor number representative of an upper limit number of processors to be used for each of the execution waiting jobs, and

a requested execution time which represents a maximum job execution time when that job is executed by processors equal in number to the requested processor number stored for that job;

(b) judging, at a point of time when some idle processors are generated, whether or not the requested processor number stored for an earliest one of the plurality of execution waiting jobs for which a request for execution is issued earliest is not larger than the total number of generated idle processors;

(c) assigning processors not smaller in number than the requested processor number and not larger than the upper limit used processor number stored for the earliest job, to the earliest job to activate the earliest job in the case where said judging in said step (b) is that the requested processor number stored for the earliest job is not larger than the total number of generated idle processors, wherein the assigning comprises assigning a smaller one of the number of idle processor and the upper limit used processor number stored for the earliest job to the earliest job;

(d) predicting an instant of time of completion of each of one or plural jobs under execution on the basis of a requested execution time stored for that job and an instant of time of start of execution of that job, where said judging in said step (b) is that the requested processor number stored for the earliest job is larger than the total number of generated idle processors by determining a corrected requested execution time representative of the maximum execution time of each job under execution when that job is executed by processors equal in number to not the requested processor stored for that job, but a processor number assigned to that job, on the basis of the requested minimum processor number stored for that job, the processor number assigned to that job and the requested execution time stored for that job;

(e) predicting a time of lapse from a present instant of time to a time when a generation of idle processors is not smaller in number than the requested processor number stored for the earliest job on the basis of a predicted completion time instant of each job under execution;

(f) judging, which of the earliest job and one of jobs subsequent to the earliest job should be activated preferentially for improved system throughput, on the basis of at least the predicted lapse time;

(g) waiting for the generation of idle processors not smaller in number than the requested processor number stored for the earliest job where said judging in said step (f) is that the earliest job should be activated preferentially;

(h) performing said steps (b) and (c) for the subsequent job where said judging in said step (f) is that the one subsequent job should be activated preferentially; and

,

(i) executing the jobs with the processors.

3. A job execution control method in a parallel processor system comprising the steps of:

(a) storing, for each of a plurality of jobs waiting for execution thereof in the parallel processor system,

a requested processor number which is designated with respect to that job and which represents a requested minimum processor number required for executing said each job,

an upper limit used processor number representative of an upper limit number of processors to be used for each of the execution waiting jobs, and

a requested execution time which represents a maximum job execution time when that job is executed by processors equal in number to the requested processor number stored for that job;

(b) judging, at a point of time when some idle processors are generated, whether or not the requested processor number stored for an earliest one of the plurality of execution waiting jobs for which a request for execution is issued earliest is not larger than the total number of generated idle processors;

(c) assigning processors not smaller in number than the requested processor number and not larger than the upper limit used processor number stored for the earliest job, to the earliest job to activate the earliest job in the case where said judging in said step (b) is that the requested processor number stored for the earliest job is not larger than the total number of generated idle processors, and further;

detecting a minimum value of the requested minimum processor numbers stored for a plurality of subsequent execution waiting jobs;

judging whether or not the detected minimum value is not larger than a difference between the total number of generated idle processors and the requested minimum processor number stored for the earliest job; and

,

assigning processors equal in number to a difference between the total number of generated idle processors and the detected minimum value to the earliest job in the case where the detected minimum value is not larger than the difference between the total number of generated idle processors and the requested minimum processor number stored for the earlier job;

(d) predicting an instant of time of completion of each of one or plural jobs under execution on the basis of a requested execution time stored for that job and an instant of time of start of execution of that job, where said judging in said step (b) is that the requested processor number stored for the earliest job is larger than the total number of generated idle processors by determining a corrected requested execution time representative of the maximum execution time of each job under execution when that job is executed by processors equal in number to not the requested processor stored for that job, but a processor number assigned to that job, on the basis of the requested minimum processor number stored for that job, the processor number assigned to that job and the requested execution time stored for that job;

(e) predicting a time of lapse from a present instant of time to a time when a generation of idle processors is not smaller in number than the requested processor number stored for the earliest job on the basis of a predicted completion time instant of each job under execution;

(f) judging, which of the earliest job and one of jobs subsequent to the earliest job should be activated preferentially for improved system throughput, on the basis of at least the predicted lapse time;

(g) waiting for the generation of idle processors not smaller in number than the requested processor number stored for the earliest job where said judging in said step (f) is that the earliest job should be activated preferentially;

(h) performing said steps (b) and (c) for the subsequent job where said judging in said step (f) is that the one subsequent job should be activated preferentially; and

,

(i) executing the jobs with the processors.

4. A job execution control method in a parallel processor system provided with a plurality of processors, comprising the steps of:

(a) storing, for each of a plurality of jobs waiting for execution thereof in the parallel processor system, a requested processor number which is designated with respect to that job and which represents a requested minimum processor number requested for the execution of that job, storing an upper limit used processor number representative of the upper limit number of processors to be used for each of the execution waiting jobs; and

storing, for each execution waiting job, a requested execution time which represents a maximum job execution time when that job is executed by processors equal in number to the requested processor number stored for that job;

(b) judging, at a point of time when some idle processors are generated, whether or not the requested processor number stored for the earliest one of the plurality of execution waiting jobs for which a request for execution is issued earliest is not larger than the total number of generated idle processors;

(c) assigning processors not smaller in number than the requested processor number to the earliest job to activate the earliest job where said judging in said second step is that the requested processor number stored for the earliest job is not larger than the total number of generated idle processors;

(d) predicting an instant of time of completion of each of one or plural jobs under execution on the basis of a requested execution time stored for that job and an instant of time of start of execution of that job, where said judging in said step (b) is that the requested processor number stored for the earliest job is larger than the total number of generated idle processors by determining a corrected requested execution time representative of the maximum execution time of each job under execution when that job is executed by processors equal in number to not the requested processor number stored for that job, but a processor number assigned to that job, on the basis of the requested minimum processor number stored for that job, the processor number assigned to that job and the requested execution time stored for that job, and predicting the instant of time of completion of each job under execution on the basis of the corrected requested execution time determined for that job and the instant of time of start of execution of that job;

(e) predicting a lapse of time from the present instant of time to the generation of generated idle processors not smaller in number than the requested processor number stored for the earliest job on the basis of the predicted completion time instant of each job under execution;

(f) judging, which of the earliest job and one of jobs subsequent to the earliest job should be activated preferentially for improved system throughput, on the basis of at least the predicted lapse of time and a cumulative wait time from the issuance of the request for execution of the earliest job to the present instant of time;

(g) waiting for the generation of the generated idle processors not smaller in number than the requested processor number stored for the earliest job where said judging in said step (f) is that the earliest job should be activated preferentially;

(h) performing said steps (b) and (c) for the subsequent job where said judging in said step (f) is that the one subsequent job should be activated preferentially; and

(i) executing the jobs with the processors.

5. A job execution control method in a parallel processor system comprising the steps of

(a) storing, for each of a plurality of jobs waiting for execution thereof in the parallel processor system, a requested processor number which is designated with respect to that job and which represents a requested minimum processor number requested for the execution of that job;

and

storing an upper limit used processor number representative of the upper limit number of processors to be used for each of the execution waiting jobs;

storing, for each execution waiting job, a requested execution time which represents a maximum job execution time when that job is executed by processors equal in number to the requested processor number stored for that job;

(b) judging, at a point of time when some idle processors are generated, whether or not the requested processor number stored for the earliest one of the plurality of execution waiting jobs for which a request for execution is issued earliest is not larger than the total number of generated idle processors;

(c) assigning processors not smaller in number than the requested processor number to the earliest job to activate the earliest job where said judging in said second step is that the requested processor number stored for the earliest job is not larger than the total number of generated idle processors, wherein the assigning comprises assigning a smaller one of the total number of generated idle processors and the upper limit used processor number stored for the earliest job to the earliest job;

(d) predicting an instant of time of completion of each of one or plural jobs under execution on the basis of a requested execution time stored for that job and an instant of time of start of execution of that job, where said judging in said step (b) is that the requested processor number stored for the earliest job is larger than the total number of generated idle processors by determining a corrected requested execution time representative of the maximum execution time of each job under execution when that job is executed by processors equal in number to not the requested processor number stored in that job, but a processor number assigned to that job, on the basis of the requested minimum processor number stored for that job, the processor number assigned to that job and the requested execution time stored for that job, and predicting the instant of time of completion of each job under execution on the basis of the corrected requested execution time determined for that job and the instant of time of start of execution of that job;

(e) predicting a lapse of time from the present instant of time to the generation of generated idle processors not smaller in number than the requested processor number stored for the earliest job on the basis of the predicted completion time instant of each job under execution;

f) judging, which of the earliest job and one of jobs subsequent to the earliest job should be activated preferentially for improved system throughput, on the basis of at least the predicted lapse of time and a cumulative wait time from the issuance of the request for execution of the earliest job to the present instant of time;

(g) waiting for the generation of the generated idle processors not smaller in number than the requested processor number stored for the earliest job where said judging in said step (f) is that the earliest job should be activated preferentially;

(h) performing said steps (b) and (c) for the subsequent job where said judging in said step (f) is that the one subsequent job should be activated preferentially; and

(i) executing the jobs with the processors.

6. A job execution control method in a parallel processor system comprising the steps of

(a) storing, for each of a plurality of jobs waiting for execution thereof in the parallel processor system, a requested processor number which is designated with respect to that job and which represents a requested minimum processor number requested for the execution of that job;

and

storing an upper limit used processor number representative of the upper limit number of processors to be used for each of the execution waiting jobs;

storing, for each execution waiting job, a requested execution time which represents a maximum job execution time when that job is executed by processors equal in number to the requested processor number stored for that job;

(b) judging, at a point of time when some idle processors are generated, whether or not the requested processor number stored for the earliest one of the plurality of execution waiting jobs for which a request for execution is issued earliest is not larger than the total number of generated idle processors;

(c) assigning processors not smaller in number than the requested processor number to the earliest job to activate the earliest job where said judging in said second step is that the requested processor number stored for the earliest job is not larder than the total number of generated idle processors, and further;

detecting a minimum value of the requested minimum processor numbers stored for a plurality of subsequent execution waiting jobs;

judging whether the detected minimum value is not larger than a difference between the total number of idle processors and the requested minimum processor number stored for the earliest job; and

assigning processors equal in number to a difference between the total number of generated idle processors and the detected minimum value to the earliest job in the case where the detected minimum value is not larger than the difference between the total number of generated idle processors and the requested minimum processor number stored for the earliest job;

(d) predicting an instant of time of completion of each of one or plural jobs under execution on the basis of a requested execution time stored for that job and an instant of time of start of execution of that job, where said judging in said step (b) is that the requested processor number stored for the earliest job is larger than the total number of generated idle processors by determining a corrected requested execution time representative of the maximum execution time of each job under execution when that job is executed by processors equal in number to not the requested processor number stored in that job, but a processor number assigned to that job, on the basis of the requested minimum processor number stored for that job, the processor number assigned to that job and the requested execution time stored for that job, and predicting the instant of time of completion of each job under execution on the basis of the corrected requested execution time determined for that job and the instant of time of start of execution of that job;

(e) predicting a lapse of time from the present instant of time to the generation of generated idle processors not smaller in number than the requested processor number stored for the earliest job on the basis of the predicted completion time instant of each job under execution;

(f) judging, which of the earliest job and one of jobs subsequent to the earliest job should be activated preferentially for improved system throughput, on the basis of at least the predicted lapse of time and a cumulative wait time from the issuance of the request for execution of the earliest job to the present instant of time;

(g) waiting for the generation of the generated idle processors not smaller in number than the requested processor number stored for the earliest job where said Judging in said step (f) is that the earliest job should be activated preferentially;

(h) performing said steps (b) and (c) for the subsequent job where said judging in said step (f) is that the one subsequent job should be activated preferentially;

(i) storing, for each execution waiting job, a requested execution time which represents a maximum job execution time when that job is executed by processors equal in number to the requested processor number stored for that job; and

,

(j) executing the jobs with the processors.