JPH0612395A - Task allocating method in multiprocessor system - Google Patents

Abstract

PURPOSE:To determine a processor to which a generated task is allocated so that the processing efficiency by the processor is good when the generated task is allocated to the processor. CONSTITUTION:When a cache memory 9 is accessed while a CPU 8 performs processing, an access counter 10 counts the frequency of access. Further, a hit counter 11 counts the frequency of the presence of desired information in the cache memory 9 at the time of access. The rate of the presence of the desired information in the cache memory 9 is obtained from the values of the access counter 10 and hit counter 11. The above-mentioned procedure is performed for all CPUs 8 constituting the system and the task which is newly generated is allocated to the CPU 8 which has the lowest rate.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multiprocessor system for allocating tasks in consideration of the operating state of a CPU.

[0002]

2. Description of the Related Art Conventionally, in a computer system having a plurality of CPUs (hereinafter referred to as "multiprocessor system"), when each CPU is composed of one master CPU and slave CPUs subordinate thereto, the processing of each CPU is performed. The content was decided. Further, when the CPUs are of the same rank, if there is a vacant CPU, a task to be newly executed is assigned thereto. At this time, if all CPU
If is being processed, the execution task is switched from the comparison result of the priority of the task to be newly processed and the priority of the task being executed, or if the compared tasks have the same priority, it is forcibly forced. It is configured to be assigned to one of the CPUs and execute while switching a plurality of tasks by a time sharing method.

[0003]

However, in the multiprocessor system of the master-slave configuration of the above conventional example, when a certain task is executed, the CP depending on the processing content is used.
Due to the allocation of U, even if there is a vacant CPU, it may be necessary to execute it on a specific CPU without fail. For example, in the case of a task such as interrupt processing, there is a drawback that the master CPU must always perform processing even if the slave CPU is free, which increases the load on the master CPU and reduces the overall system throughput.

On the other hand, in a multiprocessor system in which each CPU has the same rank, when execution of another task is newly requested while all CPUs are performing processing, the priority order of the task being executed and the new task If the priorities are the same, the CPUs are assigned according to a predetermined rule such as the order of device numbers of each CPU. The new task is executed by time-sharing with the task already executed on the assigned CPU. Therefore, C
Since it is assigned regardless of the operating state of the PU and task control is performed by the time sharing method, the assignment of the new task to the CPU does not consider the processing efficiency.
There was the drawback that inefficient allocation could be done.

The present invention has been made in view of the above conventional example, and an object of the present invention is to provide a task allocation method capable of determining task allocation so that the CPU can be used efficiently by referring to the operating state of the CPU. And

[0006]

In order to achieve the above object, a task allocation method in a multiprocessor system of the present invention has the following configuration.

A task allocation method for allocating a task generated in a multiprocessor system having a paired cache memory for each processor constituting the system to the processor, wherein each processor accesses the paired cache memory. A first counting step for counting the number of times, a second counting step for counting the number of times that the information desired by the access exists in the paired cache memory, and a number for the first counting step. Based on the number of times of the second counting step, a calculation step for calculating a hit rate in which desired information exists in the cache memory and a processor for executing the generated task based on the hit rate are selected. And a selection process.

[0008]

With the above configuration, a processor that allocates a newly generated task by calculating the rate at which desired information exists in the cache memory when each processor that constitutes the multiprocessor system accesses the cache memory is calculated. Determine according to the rate.

[0009]

【Example】

[Embodiment 1] FIG. 1 shows the configuration of the first embodiment of the present invention. In this embodiment, a multiprocessor system having two CPU sections will be described for the sake of simplicity.

<Structure> In the figure, 1 is a system bus for connecting resources such as CPU and memory in the system, and 2
Is a CPU unit A, and 3 is a CPU unit B. 4 is a memory unit that can be accessed in common by each CPU unit, 5 is a keyboard for inputting commands, 6 is a mouse for inputting, 7 is a disk for storing programs and data, and 15 is a display unit. is there. The CPU section A and the CPU section B have the same configuration, and the same components are designated by the same numbers in the drawings. The configuration of the CPU unit A will be described.

The CPU section A counts the number of accesses to the cache memory by a CPU 8, a cache memory 9 for storing local data of the CPU 8 for high-speed memory access, and a memory access signal 16 from the CPU 8. Access counter 10 and C
In response to a memory access request from the PU 8, a hit signal 12 indicating that there is corresponding data in the cache memory 9 is taken, and a hit counter 11 for counting the number of cache hits is configured. The value of the counter 10 and the value of the counter 11 are mapped on the system bus 1 so that each CPU can access them.
The cache memory 9 issues a hit signal 12 if data exists in response to a memory access request from the CPU 8 and outputs the value to the CPU 1. If it does not exist, the cache memory 9 does not output the hit signal 12,
The corresponding data is loaded from the memory 4 or the disk 7 into the cache memory 9, and the requested data is returned to the CPU 8. The access counter 10 and the hit counter 11 are both cleared to 0 when a new task is assigned to the CPU, and are cleared to 0 each time a predetermined time elapses by means such as a timer of each CPU unit (not shown).

<Assignment of Tasks> In the multiprocessor system having the above-mentioned configuration, when the task A is executed by the CPU A and the task B is executed by the CPU B, the user can input by the keyboard 5 or the mouse 6. Consider a case in which task C must be newly executed by a request or by an external interrupt (not shown).

FIG. 2 shows an example of changes in the counters of task A and task B. According to FIG. 2, 20 indicates that the access counter 10 and the hit counter 11 of the CPU unit A at time t ₁ are 100 and 50, respectively, and the hit rate is 50.
It can be seen that / 100 = 50%. Similarly, the hit rate of the CPU section B is 50 / 150≈33%. The processing when a further time elapses and a new task C execution request is generated will be described with reference to the flowchart of FIG.

When a task C execution request is issued at time t ₂ , the presence / absence of a CPU that is idle at that time is tested, and if there is a free CPU, the newly generated task is executed by that CPU. All CPUs (in this case CP
If some tasks are processed in U section A and CPU section B), the optimum CPU must be selected from them.

First, the CPU 8 of the CPU section A reads the values of the access counter 10 and the hit counter 11 (S601).
-S602), the hit rate is calculated (S603). CP
The cache hit rate in U part A is 150/20 from the table
0 = 75%. This value is stored in the cache memory 9, and then the hit rate is calculated for the CPU B (S604-NO). When calculated in the same manner as the CPU unit A, the cache hit rate of the CPU unit 2 is 270/300.
= 90%, which is also stored in the cache memory 9. This completes the calculation of the hit rate for all CPUs (S604-YES). Next, the hit rates of 75% and 90% of each CPU unit are compared, and the smaller hit rate is determined as the CPU to which the new task is assigned (S605).
Finally, the task C is assigned to the CPU having a small hit rate, that is, the CPU unit A (S606). This means that if the cache hit rate is higher, the read from the external storage device to the cache memory is less and the CPU is more efficient.
Is running. On the other hand, when the hit rate is low, the load from the external storage to the cache memory is more frequent, so the overhead when executing multiple tasks by time sharing is higher the overall processing efficiency when the hit rate is higher. Does not affect For this reason, a new task is assigned to a CPU with a low hit rate so that processing with higher efficiency can be prioritized.

As a result, the CPU unit A executes the tasks A and C by the time-sharing method according to the priority of each task, and the CPU unit B executes the task B as it is.

[0017]

Other Embodiments In the first embodiment, the case where each CPU unit executes one task at a time has been described, but in this embodiment, each CPU unit has already executed a plurality of tasks. Consider the case. In this case, it is assumed that the task A and the task B are being executed in the CPU unit A, and the task C and the task D are being executed in the CPU unit B, and a case in which an execution request for the task E is generated will be described.

[Second Embodiment] In the second embodiment, each CPU is
According to the cache hit rate of each PCU part, without being aware of how many tasks are currently being executed in each part.
A method of determining which CPU the task E is assigned to will be described. In this case, as in the first embodiment, as shown in the table of FIG. 3, the number of memory accesses for each CPU unit and the number of cache hits may be stored in the configuration shown in FIG. Further, the method of determining the CPU unit to which the task is allocated may be determined by the method shown in the first embodiment.

In FIG. 3, an access counter and a hit counter are recorded for the CPU section A and the CPU section B, and the hit rate can be derived by the same procedure as in the first embodiment.
The task allocation destination is determined to be the CPU unit A.

[Embodiment 3] In a third embodiment, a method of calculating a cache hit ratio for each task and assigning a new task to which CPU unit will be described.
FIG. 4 shows a block diagram of this embodiment. In FIG. 4, components having the same operations as in FIG. 1 are given the same numbers. The counter control unit 30 stores the count information output from the access counter 10 which is a memory access number counter and the hit counter 11 which is a cache hit number counter in each CPU unit on a signal line 33 and a signal, respectively. Input from line 34, and count information of each CPU unit is stored. Further, a signal 35 notifying that the execution task has been switched in each CPU is also input from each CPU. The counter memory 32 is a memory for accumulating the number of memory accesses and the number of cache hits of all tasks being executed by each CPU.

A detailed description will be given below.
A task is identified by using a unique identifier (hereinafter referred to as a task ID) for identifying a task used in an OS such as Unix. Of the four tasks being executed, task A is 100, task B is 102, task C is 101,
The task D is 103. Counter controller 31
C is for all CPUs at system startup.
When the counter information is input from the PU, the access counter 10 and the hit counter 11 of the CPU are cleared to 0. When the task A is executed by the CPU 1 and a predetermined time elapses, the CPU 1 tells the counter controller 31 its own CPU number, the task ID being executed, the access counter 10 and the hit counter 1 which are count information.
Send a value of 1. Similar processing is performed for tasks B, C, and D. Then, the counter controller 31 creates table information in which the counters at a certain time are recorded in the counter memory 32, as shown in FIG. Figure 4
The fields of the access counter 10 and the hit counter 11 are the same as those in the first embodiment. Here, in the state of FIG. 4, it is assumed that an execution request for task E is issued. Then, the counter controller calculates the cache hit rate for each task. That is, task 100: 60/100 = 60% ... CPU part A task 102: 140/200 = 70% ... CPU part A task 101: 240/300 = 80% ... CPU part B task 103: 60/200 = 30% ... Find the CPU section B. Here, from the perspective of finding the highest cache hit rate among the four cache hit rates, in this case 80% of the tasks 101, and executing the efficient task first,
Since the task 101 is executed by the CPU part B, the CPU
Judge that task E is to be assigned to part A, and assign task E to C
Assign to PU unit A. This is the CP of the procedure of the first embodiment.
This is a change from the U unit to the task unit. Therefore, if step S605 of the flowchart of FIG. 6 is set to "exclude CPUs executing a task with a high hit rate in order and select the last remaining CPU", this embodiment can be applied.

In the task allocation method realized in this way, the CP is set as the execution state of the task being executed by each CPU.
By providing a procedure for monitoring the cache hit ratio between U and the cache, when the execution priority of the task being executed by each CPU is the same when another task execution request occurs, By allocating this task to the lowest CPU, the task with high cache hit rate can continue processing at high speed,
By processing by a CPU with a low cache hit rate by the time-share method, the task with a low cache hit rate originally makes a memory access that does not hit the cache memory so much that a cache hit by a task switch occurs. The decrease in the rate is small,
Resources such as CPU can be efficiently allocated. Also, the hardware scale for obtaining the cache hit rate can be reduced.

In the above description, the timer unit of the CPU is used to measure a predetermined unit time and the cache hit ratio within the unit time is calculated. However, the task is passed from the start to the end. A method of obtaining the cache hit rate may be used. For example, in the case of a task that sequentially processes a large amount of image data, the cache hit rate is considered to be small for the task as a whole, and since it is a time-consuming process, You can share it with other tasks in time.

Further, the cache hit rate is calculated by the CPU A2 in the first and second embodiments and by the counter controller 30 in the third embodiment, but it is not limited to this.

In the above description of the embodiments, the CPU
Although two units have been described, the present invention is not limited to this, and a device having more CPUs may be used. Also, each C
Although the case where the number of tasks being executed on the PU is the same has been described, the present invention is not limited to this, and if there is a vacant CPU, it can be easily assigned to that CPU. Also, it has been explained that the task with a high cache hit rate is executed preferentially, but it is not limited to this, and the task that does not hit the cache too much takes time, so it is executed with priority. That is, a control method opposite to the above-described embodiments can be easily considered.

The present invention may be applied to a system composed of a plurality of devices or an apparatus composed of a single device. Further, it goes without saying that the present invention can be applied to the case where it is achieved by supplying a program to a system or an apparatus.

[0027]

As described above, the task allocation method according to the present invention can determine the task allocation so that the CPU can be used efficiently by referring to the operating state of the CPU.

[Brief description of drawings]

FIG. 1 is a block diagram of a first embodiment.

FIG. 2 is a table for calculating a cache hit rate in the first embodiment.

FIG. 3 is a table for calculating a cache hit rate in the second embodiment.

FIG. 4 is a block diagram of a third embodiment.

FIG. 5 is a table for calculating a cache hit rate according to the third embodiment.

FIG. 6 is a flowchart of the first embodiment.

Claims (7)

[Claims] 1. A task allocation method for allocating to a processor a task generated in a multiprocessor system having a paired cache storage for each processor constituting the system, wherein each processor has the paired cache storage. A first counting step of counting the number of times of access to the second counting step, a second counting step of counting the number of times that the information desired by the access exists in the paired cache memory, and the first counting step. A calculation process for calculating a hit rate at which desired information exists in the cache memory based on the number of times and the number of times by the second counting process, and a processor for executing the generated task based on the hit ratio. A task allocation method comprising: a selection process to be selected. 2. The task allocation method according to claim 1, wherein the hit ratio is calculated for each task in the calculation step. 3. The task according to claim 2, wherein the selection step selects a processor that executes a task with the lowest hit rate among tasks with the highest hit rate in each of the processors. Allocation method. 4. The task allocation method according to claim 1, wherein the calculation step calculates the hit rate for each processor. 5. The task allocation method according to claim 4, wherein the processor having the lowest hit rate is selected in the selection step. 6. The task allocation method according to claim 1, wherein the calculation of the hit ratio is performed for access within a time from the start to the end of the task. 7. The task allocation method according to claim 1, wherein the hit ratio is calculated for an access selected within a certain period of time.