JP2743865B2 - Job scheduling method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a job scheduling method in a hierarchical shared distributed memory multiprocessor system in which a conventional shared memory multiprocessor system is used as one cluster and a plurality of clusters are connected by a network.

[0002]

2. Description of the Related Art A conventional job scheduling method in a shared memory type multiprocessor system includes a method having one common job queue in the entire system and a method having each processor having its own job queue.

[0003]

In an attempt to construct a system using more processors than in the prior art, the above-described 1
When a method having a common job queue for books is adopted, contention for memory access frequently occurs. In addition, the number of processors that access the common job queue via the network increases, and network access competition also occurs. Further, when each processor has its own job queue, there is no access contention problem for accessing the common job queue, but there is a problem that the load state of each processor becomes uneven. In order to solve this problem, there is a method in which a processor that has no jobs to be processed checks the load state of another processor and moves and executes the job from the processor with a high load state, but the number of processors increases. Therefore, access competition between the network and the common job queue frequently occurs due to this operation.

In view of the above problems, the present invention provides a shared memory type multiprocessor system as one cluster, divides a plurality of clusters into groups for each job allocation unit, and connects each cluster via a network. It is an object of the present invention to provide a job scheduling method in which access conflict between a network and a common job queue hardly occurs even when many processors are used by configuring a memory type multiprocessor system.

[0005]

According to the job scheduling method of the present invention, a shared memory multiprocessor system is used as one cluster, a plurality of clusters are divided into groups for each job allocation unit, and each cluster is connected via a network. A job scheduling method for a hierarchical shared distributed memory type multiprocessor system, comprising: a primary job queuing means for managing jobs input to the system in FIFO order; and a cluster configuration of the hierarchical shared distributed memory type multiprocessor system. Secondary job queuing means for managing jobs assigned to the job allocation units, one for each job allocation unit set in consideration, and managing the jobs in FIFO order;
The primary job queuing unit refers to the load status inquiry unit for storing the load status of each job allocation unit and the load status stored by the load status inquiry unit.
And a job scheduling means for appropriately allocating the job to the next job queuing means.

Also, a job to be input to the system can be identified by a job class, the job class is stored in a job class inquiry unit, and the job scheduling unit distributes the job into different job allocation units according to the job class. Is preferred.

[0007]

A secondary job queuing unit is associated with each job allocation unit. The job scheduling means detects the job allocation unit with the least load with respect to the job received from the primary job queuing means, by referring to the load state inquiring means.
The job is input to the secondary job queue corresponding to the detected job allocation unit. The processor of each cluster sequentially processes the jobs of the secondary job queuing unit corresponding to the job allocation unit to which the cluster belongs. Only when processing jobs belonging to different job allocation units,
Access via network.

[0008]

Next, embodiments of the present invention will be described with reference to the drawings. FIG. 1 is a block diagram showing a configuration of a job scheduling method of the present invention employing a hierarchical shared distributed memory type multiprocessor system. Each cluster 10
Has a configuration similar to that of a conventional shared memory type multiprocessor system, and includes a plurality of processors 11 and a shared memory 12 shared by the processors 11. Each cluster 10 is connected to the network 2 and constitutes a hierarchical shared distributed memory multiprocessor system as a whole. In the hierarchical shared distributed memory type multiprocessor system, information transmission between processors belonging to the same cluster is performed via the shared memory 12.
Information transmission between processors belonging to different clusters is performed by communication via the network 2.

The job allocation units 31 to 3n are set in consideration of the cluster configuration of the hierarchical shared distributed memory type multiprocessor system.
Secondary job queuing means 61 to 6n are associated with n. The job input to the primary job queuing means 4 is
It is passed to the next job queuing means 61-6n.

At this time, the job schedule means 5 acquires the load state of each of the allocation units 31 to 3n and the job class of the job to be scheduled by the load state inquiry means 7 and the job class inquiry means 8, and divides this information into each job allocation. It is used for distributing jobs to the units 31 to 3n. Each job allocation unit 31
3n receive the jobs from the secondary job queuing units 61 to 6n and process them.

As shown in FIG. 2, the primary job queuing means 4 comprises a primary job queue 41, a primary job enqueue means 42, and a primary job dequeue means 43. The primary job queue 41 manages jobs submitted to the system in FIFO order. The primary job enqueue unit 42 performs an operation of adding a job input to the system to the end of the primary job queue 41.
The primary job dequeue means 43 includes a primary job queue 41
From the beginning of the job.

Similarly, secondary job queuing means 61
6 to 6n include a secondary job queue 71, a secondary job enqueue unit 72, and a secondary job dequeue unit 73. The secondary job queue 71 manages the jobs passed from the job scheduling means 5 in FIFO order. The secondary job enqueue unit 72 performs an operation of adding a job to the end of the secondary job queue 71. The secondary job dequeue unit 73 performs an operation of taking out a job from the head of the secondary job queue 71.

Next, the operation of the job scheduling means 5 will be described with reference to FIG. The job scheduling means 5 takes out the job input to the system and put in the primary job queue 41 from the primary job queue 41 (step S1). Next, in order to select a job allocation unit for executing the extracted job, the load status of each job allocation unit is acquired by the load status inquiry unit 7 (step S2). In the conventional job scheduling, in which each processor has its own job queue, when the number of processors increases, the load status of other processors is checked, so that access competition occurs. As a result, access contention is reduced, and a decrease in system performance can be suppressed. That is, a job allocation unit with the least load is selected (step S3), and a job is input to the secondary job queue 71 of the job allocation unit selected by the enqueue unit 72 (step S3).
4). On the other hand, each processor takes out a job from a job queue corresponding to a job allocation unit to which the processor belongs, and executes the job. In this case, a common area called the secondary job queue 71 is accessed by a plurality of processors.
Processors accessing one common area (secondary job queue 71) are limited to processors in the job allocation unit. Therefore, compared with the conventional scheduling method having only one job queue in the entire system, the access contention is reduced, so that the performance of the system can be prevented from deteriorating.

FIG. 4 shows a job scheduling method when a job can be identified by a job class.
This will be described with reference to FIG. The job allocation unit is set in consideration of the cluster configuration, and different job allocation units 301 to 30n are provided for each job class. Further, the secondary job queue 91 existing in the secondary job queuing means 81 to 8n corresponding to each job allocation unit is also changed for each job class. For example, the secondary job queue 91 for a job having a low priority is set to be long. As a result, the number of jobs waiting to be executed in the queue increases, but jobs can be scheduled in job allocation units for other job classes, and interference with the execution of other jobs can be prevented.

Next, the operation of the job scheduling means 50 will be described with reference to FIGS. The job extracted from the primary job queue 4 in step S11 acquires a job class using the job class inquiry means 8 in step S12. In step S13, the load status is obtained from the load status inquiry means 7 for the job allocation unit given to the job class obtained in step S12. Step S1
In step S4, a job allocation unit with the least load is selected, and in step S15, a job is input to the secondary job queue. Here, since the job allocation unit for inquiring about the load state is limited to the one given to the job class, access conflicts generated for inquiring about the impossible state are reduced, and the scheduling overhead is reduced.

[0016]

As described above, according to the present invention, clusters are grouped into job allocation units, and each cluster is connected via a network to form a hierarchical shared distributed memory type multiprocessor system. In addition, it is possible to reduce the contention of memory access and the contention of network access, and to perform job scheduling that can sufficiently exhibit the performance of the system.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a configuration of a job scheduling method of the present invention employing a hierarchical shared distributed memory type multiprocessor system.

FIG. 2 is a block diagram showing primary and secondary job queuing means of the embodiment of FIG. 1 in detail;

FIG. 3 is a flowchart illustrating a process of a job scheduling unit of the embodiment of FIG. 1;

FIG. 4 is a block diagram showing another embodiment of the present invention, in which a job can be identified by a job class.

FIG. 5 is a block diagram showing details of primary and secondary job queuing means in the embodiment of FIG. 4;

FIG. 6 is a flowchart illustrating a process of a job scheduling unit in FIG. 4;

[Explanation of symbols]

2 Network 4 Primary job queuing means 5, 50 Job scheduling means 7 Load status inquiry means 8 Job class inquiry means 10 Cluster 11 Processor 12 Shared memory 31 to 3n Job allocation unit 41 Primary job queue 42, 72, 92 Enqueue means 43, 73, 93 Dequeue means 61 to 6n, 81 to 8n Secondary job queuing means 71, 91 Secondary job queue

Claims (3)

(57) [Claims] 1. A hierarchical shared distributed memory multiprocessor system in which a shared memory multiprocessor system is a single cluster, a plurality of clusters are divided into groups for each job allocation unit, and each cluster is connected via a network. A job scheduling method for managing jobs submitted to a system in FIFO order 1
A second job queuing means, one for each job allocation unit set in consideration of the cluster configuration of the hierarchical shared distributed memory type multiprocessor system, and manages jobs allocated to the job allocation unit in FIFO order. Next job queuing means, load state inquiry means for storing the load state of each job allocation unit, and load state stored by the load state inquiry means,
A job scheduling means for appropriately allocating a job from the primary job queuing means to the secondary job queuing means. 2. A job input to a system can be identified by a job class, a job class inquiry unit stores the job class, and the job scheduling unit sorts the job into different job allocation units according to the job class. The job scheduling method according to claim 1. 3. The job scheduling method according to claim 2, wherein said job class is at least one of a priority order, a distinction between interactive and batch, and presence or absence of parallel processing.