JP3512080B2 - Computing device and 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 computing device and method, and more particularly, to a computing task and data of a computing power remaining in a predetermined connection direction, and the computing task received in accordance with the received computing power data. The present invention relates to a computing device and method for processing or transferring data.

[0002]

2. Description of the Related Art In recent years, in order to reduce the cost of maintaining and operating a computer system, decentralization and downsizing have been performed, and a conventional large computer is connected with a plurality of inexpensive, small computers. Has been replaced by the network.

In distributed processing in such a network, conventionally, as shown in FIG. 9, a predetermined control processor 81 is provided, and this control processor 81 is used as a calculation processor 82-i (i = 1, 2, 1). , 3, ...) are distributed so that the calculation loads (the amount of calculation tasks) of the calculation tasks 83 become uniform.

However, when the control processor 81 distributes the calculation tasks 83 in this way, the calculation load is distributed by the control processor 81.
When a large number of calculation processors 82-i are used, the processing capacity of the control processor 81 reaches the limit, which makes it difficult to control the distributed processing.

Further, since the control processor 81 alone controls the distributed processing, if the control processor 81 fails, the whole computer system becomes inoperable.

Therefore, such a control processor 81
A method for autonomously distributing computational tasks without using is considered.

For example, in a processor 91-i connected in a one-dimensional manner as shown in FIG. 10 (a), each processor 91-i has an adjacent processor 91- (i-
1), 91- (i + 1) is monitored, and when it is determined that the load of the adjacent processors 91- (i-1), 91- (i + 1) is light, the processor is given a predetermined amount of calculation tasks 92. It is conceivable that the transfer is performed.

By doing so, as shown in FIG. 10B, the calculation task 93 is changed from the processor having a large number of calculation tasks 93 (the processor 91-2 in FIG. 10A). Not a processor (Fig. 10 (a))
Since the calculation task 93 moves to the processor 91-3) in the above, the load can be autonomously distributed.

[0009]

However, when the load is distributed as described above, a processor having a predetermined heavy load is adjacent to another processor even if two or more adjacent processors are lightly loaded. Has a certain load (calculation task), the calculation task cannot be moved. Therefore, there is a problem that the distribution of the calculation tasks is locally stabilized, some processors do not operate, and the optimum load distribution is not performed.

For example, as shown in FIG. 11, the calculation task 92 of the processor 91-2 is the processor 91-2.
3 has a certain number of calculation tasks 92, it is not transferred to the processor 91-3 even though the processors 91-4 and 91-5 do not have the calculation task 92.

The present invention has been made in view of the above circumstances, and each processor calculates a surplus calculation capacity, and each device calculates the sum of the calculation surplus capacity at a predetermined ratio in each connection direction. By transmitting the information, not only the status of the adjacent processors, but also the load amount in each connection direction is grasped, and the calculation task is transferred in the direction of the light load so that there are no inactive processors. In this way, optimal load distribution is performed.

[0012]

According to a first aspect of the present invention, there is provided a computing device, a receiving means for receiving data of a computing task and a computing capacity from another computing device connected adjacently, and receiving by the receiving means. Comparing the respective calculated surplus data and the self calculated surplus data, if the self calculated surplus is equal to or more than the respective calculated surplus of all other computing devices,
When the calculation means for processing the calculation task and each calculation surplus data received by the receiving means are compared with the self calculation surplus data, and the self calculation surplus is smaller than one of the other calculation devices. Is more than any other calculator
And a transmission means for transmitting the calculation task to another calculation device that has transmitted a large amount of calculation power, and the transmission means comprises:
Furthermore, the data of the new calculation power calculated from the data of the calculation power of itself and the data of the calculation power received by the receiving means are transmitted at a predetermined ratio to another adjacent calculation device. Is characterized by.

A calculation method according to a second aspect of the present invention receives a calculation task and data of a calculation remaining capacity from another calculation apparatus connected adjacent to the calculation task, and calculates the received calculation remaining capacity data and its own calculation remaining capacity. When comparing with the data, if the self-computation capacity is equal to or greater than the respective calculation capacity of all other computing devices, the calculation task is processed, and calculation is performed from the self-computation capacity data and the received calculation capacity data. The new calculation surplus data is transmitted at a predetermined rate to another adjacent computing device, and each received calculation surplus data is compared with the self calculation surplus data to calculate the self calculation. spare capacity is the smaller than any of the calculations available capacity of other computing devices, among other computer, and transmits the calculated task to another computing device that has transmitted the data of greater computational margin.

In the computing device according to the first aspect, the receiving means receives the data of the computing power from the computing task and another computing device adjacently connected, and the processing means receives the data by the receiving means. Comparing the calculated surplus calculation data with the self calculation surplus data, and when the self calculation surplus is equal to or more than the respective calculation surplus of all other computing devices, the calculation task is processed, and the transmission means is , The data of the new calculation power calculated from the data of the calculation power of itself and the data of the calculation power received by the receiving unit are transmitted to and received by another calculation device connected to the adjacent device at a predetermined ratio. of by comparing the data of the data and its own calculations margin of each calculation margin received when own account margin is smaller than any of the calculated reserve capacity of other computing devices, other computers by means, large and more Data have calculated margin to other computing devices that has transmitted the transmitting computational tasks.

In the calculation method according to the second aspect, the calculation task and data of the calculation remaining capacity from other adjacently connected calculation devices are received, and the received data of the calculation remaining capacity and the calculation remaining capacity of the self are received. If the self-computation capacity is equal to or greater than the respective calculation capacity of all the other computing devices by comparing the data of the above, the calculation task is processed, and the self-computation capacity data and the received calculation capacity data are compared. The new calculation surplus data to be calculated is transmitted at a predetermined ratio to another adjacently connected computing device, and each received calculation surplus data is compared with the self calculation surplus data to calculate If the calculated reserve capacity is smaller than any of the calculations available capacity of other computing devices, among other computer sends computing tasks to other computing devices which transmitted the data of greater computational margin.

[0016]

DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 shows a state in which a plurality of embodiments of a computer according to the present invention are connected. In this connection example, the computing device 1-i (i = 1, 2, 3, ...
.) Indicates processor 21-i and sub-processor 22
-I, and are connected in a one-dimensional manner. In the following description, the symbol -i is omitted unless it is necessary to make a distinction.

The processor 21 receives a calculation task 23 from another (adjacent) processor 21 and transmits the received calculation task 23 to another (adjacent) calculation device 1 according to a predetermined condition, or It is designed to hold, hold, and run.

The processor 21 calculates the computational capacity (the amount of load that can be processed in addition to the load currently being processed) from its own computing capacity and the current load status. Then, a virtual particle called Computon 24 is introduced as an index showing the calculation capacity, and the calculation capacity is calculated as
The number of Computon 24 expressed by the number of 4 and corresponding to the calculated spare capacity is virtually output to the sub-processor 22 (actually, the processor 21
Outputs the number of Computon 24 to the sub-processor 22 as data).

The sub-processor 22 virtually receives the Computons 24 from the processor 21 and the sub-processors 22 of the adjoining computing devices 1, and computes these Computons 24 by 1/3 in two directions. The output is output to the device 1 and the remaining 1/3 is output to the processor 21. It is assumed that the Computon 24 output to the processor 21 disappears in the processor 21 (actually, data of the number of Computon 24 is exchanged).

FIG. 2 shows a configuration example of an embodiment of the computer 1 of the present invention. The computing device 1 includes a processor 21
And a sub processor 22. Processor 2
In FIG. 1, the CPU 41 (processing means) is the ROM 42.
Various processes are performed in accordance with the programs stored in.

For example, the CPU 41 is adapted to calculate the number of Computon 24 according to the current load condition and output the number of Computon 24 to the sub processor 22 via the interface 45.

The RAM 43 is adapted to temporarily store data when the CPU 41 performs various processes.

The network interface 44 (reception means, transmission means) is connected to the network interface 44 of another computing device 1 to exchange the calculation task 23.

In the sub processor 22, the CPU 6
1 performs various kinds of processing according to the program stored in the ROM 62, and, for example, the number of Computon 24 received via the network interface 64 and the number of Computon 24 received via the interface 65 The number of Computon 24 to be transmitted to the computing device 1 is calculated.

The RAM 63 is adapted to temporarily store data when the CPU 61 performs various processes.

The network interface 64 (reception means, transmission means) is connected to the network interface 64 of another computing device 1 so as to exchange the number of Computon 24.

Next, the operation of the computer 1 will be described with reference to the flowcharts of FIGS.

First, the operation of the main routine of the processor 21 of the computer 1 will be described with reference to the flowchart of FIG.

In step S1, the CPU 41 determines whether or not the processor 21 has the calculation task 23. If it is determined that the processor 21 does not have the calculation task 23,
It waits until the computing task 23 is transferred from another computing device 1.

When the processor 21 has the calculation task 23, the CPU 41 proceeds to step S2, where the current R
Of the calculation tasks 23 held in the AM 43, the calculation tasks 23 are processed in a predetermined order. When the processing of all the calculation tasks 23 is completed, the CPU 41 returns to step S1 and waits until the calculation task 23 is transferred from another calculation device 1.

When a new calculation task 23 occurs in the processing of the calculation task 23 in step S2, the CPU 41 causes a task transfer interrupt.

Next, referring to the flowchart of FIG.
The operation of the processor 21 in this task transfer interrupt will be described.

First, in step S11, the CPU
41 is a Computon 24 supplied from an adjacent computing device 1 (computing device 1 connected in the right or left direction)
Find out the number of.

Next, in step S12, the CPU 4
1 is the number N _L of Computon 24 supplied from the computing device 1 connected in the left direction, the number N _{R of} Computon 24 supplied from the computing device 1 connected in the right direction,
And the number N of Computon 24 of its own computing device 1 is compared, and when it is determined that N is N _L or more and N is N _R or more, the new computation task 23 is held in step S13. Then, the process is performed in step S2 of the main routine.

The CPU 41, in step S12,
When it is determined that N is smaller than N _L or N is smaller than N _R , the process proceeds to step S14 and it is determined whether N _L is smaller than N _R. When the CPU 41 determines that N _L is smaller than N _R , the CPU 41 proceeds to step S15 and transfers the new calculation task 23 to the calculation device 1 connected rightward via the network interface 44.

In step S14, the CPU 41
If N _L is equal to or greater than N _R, the process proceeds to step S16, it is determined whether N _L is larger than N _R, if N _L is determined to be larger than N _R, the process proceeds to step S17, a new The specific computing task 23 is transferred to the computing device 1 connected leftward via the network interface 44.

The CPU 41, in step S16,
If N _L is equal to or less than N _R (i.e., if N _L and N _R are equal), the process proceeds to step S18, the interval (0,1)
, A random number is generated, and in step S19, it is determined whether the random number is smaller than 0.5.
If it is determined that it is smaller, the process proceeds to step S17,
The new calculation task 23 is transferred to the calculation device 1 connected leftward.

The CPU 41, in step S19,
When it is determined that the random number is 0.5 or more, step S1
In step 5, the new calculation task 23 is transferred to the calculation device 1 connected to the right.

When a new calculation task 23 is generated in this way, the CPU 41 of the new calculation task 23
Is transferred to another connected computing device 1 or held for processing by itself.

When this calculation task 23 is transferred, the processor 21 of the transfer destination similarly causes a task transfer interrupt to transfer the calculation task 23 to another connected computing device 1, or Or you can handle it yourself.

Thus, the newly generated calculation task 2
3 is the direction in which the calculation load is low (Computon 24
Is transferred in the direction in which the number of A. is larger, and is processed in the computing device 1 with the least computational load (the number of Computetons 24 in the left and right directions is the same).

Therefore, even when the distribution of the calculation tasks 23 is locally stable, if the calculation tasks 23 are not uniformly distributed as a whole, the calculation tasks 23 move in the direction in which the calculation load is small.

The processor 21 generates an interrupt at a predetermined time interval and calculates the number of Computon 24.

This interrupt will be described with reference to the flowchart of FIG.

In step S21, the CPU 41
From the current amount of calculation tasks 23, the number of Computon 24 corresponding to the calculation capacity of the processor 21 is calculated.

Then, in step S22, the CPU
41 transmits the number of the Computon 24 to the sub processor 22 via the interface 45.

In this way, the sub processor 22
Computon 2 from the processor 21 at predetermined time intervals
Supplied with a number of four.

Next, referring to the flowchart of FIG.
The operation of the sub processor 22 of the computing device 1 will be described.

The CPU 61, in step S31,
It waits until the number of Computon 24 is supplied from the processor 21 through the interface 65, and when the number of Computon 24 is supplied from the processor 21, the process proceeds to step S32.

In step S32, the CPU 61
The sum of the number of Computon 24 supplied from the processor 21 and the number of Computon 24 supplied from the other computing devices 1 connected in the left-right direction is calculated.

Then, in step S33, the CPU
Reference numeral 61 denotes another computing device 1 connected in the left-right direction, with the number of 1/3 of the total sum as the number of Computon 24.
, Via the network interface 64.

In step S34, the CPU 61
From another computing device 1 connected in the left-right direction, via the network interface 64, the Computon 2
The number of 4 is received and stored in the RAM 63. Further, the number of these Computon is supplied to the processor 21 via the interface 65 and used in the task transfer interrupt processing.

As described above, the sub processor 22
However, by propagating the Computon 24 at a predetermined rate in each connection direction, the calculation task 23 is transferred based on the overall load status, so that the distributed processing should be performed at a higher operation rate. You can

FIG. 7 shows an example of distribution of calculation load when this embodiment is used. In this example, a predetermined processor 21 sequentially generates a calculation task 23. Therefore, the periphery of the processor 21 (FIG. 7A)
The calculation load in the section a) becomes larger, and accordingly, the Computon 24 in the area (section a in FIG. 7B) becomes larger.
The number of is reduced.

As shown in FIG. 7B, the Computon 24
Is distributed, the calculation task 23 that occurred in section a
Are transferred to section b or section c in which the number of Computon 24 is large, and the load is distributed as shown in FIG.

FIG. 8 shows an example of the transition of the number of operating processors 21 when 80 computing devices 1 are connected in a one-dimensional ring and a predetermined number of computing tasks 23 are processed. Shows.

Eighty computing devices 1 are connected in a one-dimensional ring shape, and in each computing device 1, the processor 21 that is not processing the computing task 23 releases 16 Computon. Then, each time the calculation task 23 increases by one, the number of Computon 24 to be discharged decreases by two.

Now, let us say that the time interval at which the calculation task 23 occurs is t, and the discharge step of the Computon 24 and the movement step of the calculation task 23 are 0.01t. Then, if the calculation task 23 continues to move, the calculation task 23 stops the movement at a time of 0.8t and sets the processing time to 150t.

Under these conditions, the calculation task 23 is executed by 10
When 00 pieces are generated in a predetermined computing device 1, the operation status of the computing device 1 at that time is as shown by a curve a in FIG. 8, and after time 400t, about 56 out of 80 units are operated.
The platform is operating. Therefore, the operating rate is 70% (= 56 /
80 × 100%). The number of operating computing devices 1 is the average value of the operating numbers at each execution when such processing is executed 100 times.

Under the same conditions, when the calculation task 23 is moved in consideration of only the load of the adjacent processor 21 without using the Computon 24, the curve b in FIG.
As shown in, about 44 of 80 computing devices are in operation. Therefore, the operating rate is 55% (= 44/80 x 1
00%).

As described above, the computational capacity of each computing device 1 is represented by the Computon 24, and the Computon 24 is propagated in a predetermined ratio in each connection direction, so that the overall load condition can be met. The calculation task 23 is transferred to distribute the calculation load.

In this embodiment, the computer 1
Are connected in a one-dimensional form, but they can be connected in a two-dimensional or higher-order form.

In the above embodiment, the computing devices 1 having the same computing capacity are connected to each other, but the computing devices having different computing capabilities may be connected.

[0064]

As described above, according to the computing device and method of the present invention, each of the received computing power is received by receiving the data of the computing power from the computing task and the other computing device connected adjacently. If the self-computation capacity is equal to or greater than the respective calculation capacity of all the other computing devices by comparing the data of (1) and the self-computation capacity data, the calculation task is processed, and the self-computation capacity data, A new ratio of new calculation power calculated from the received calculation power data
Transmitting to another computing device connected adjacently, comparing the received calculation surplus data with the self computing surplus data, and the self computing surplus is smaller than one of the other computing devices. If, among other computer, since to send computing tasks to other computing devices which transmitted the data of greater computational reserve capacity, new calculation task occurs, the transfer in the direction the amount of load is small As a result, the load is processed by a processor with a small load, and optimum load distribution can be performed.

[Brief description of drawings]

FIG. 1 is a block diagram showing a state in which a plurality of embodiments of a computer according to the present invention are connected.

FIG. 2 is a block diagram showing the configuration of an embodiment of a computer according to the present invention.

3 is a flowchart illustrating an operation of the processor of FIG.

FIG. 4 is a flowchart illustrating an operation of the processor of FIG.

5 is a flowchart illustrating an operation of the processor of FIG.

FIG. 6 is a flowchart illustrating an operation of the sub processor of FIG.

FIG. 7 is a diagram showing a state in which calculation tasks are distributed in the connection example of the calculation apparatus in FIG.

8 is a diagram showing a transition of the number of operating computing devices in the connection example of the computing devices of FIG. 1;

FIG. 9 is a block diagram showing an example of a conventional distributed processing system having a control processor.

FIG. 10 is a block diagram showing another example of a conventional distributed processing system.

11 is a diagram showing distribution of calculation tasks when a stable state is locally achieved in the distributed processing system of FIG.

[Explanation of symbols]

1 computing device 21 processors 22 sub-processor 23 Calculation Task 24 Computon 41 CPU 42 ROM 43 RAM 44 network interface 45 interface 61 CPU 62 ROM 63 RAM 64 network interface 65 Interface 81 Control processor 82 Calculation Processor 83 Calculation Task 91 processor 92 Calculation task

Claims (2)

(57) [Claims] 1. A computing device, which is connected to each other and executes a plurality of computing tasks in a distributed manner, and a receiving means for receiving the data of the computing power from the computing task and another computing device connected adjacently thereto. When the data of each of the calculation surplus received by the receiving means and the data of the self calculation surplus are compared and the self calculation surplus is equal to or more than the respective calculation surplus of each of the other computing devices, the A processing means for processing a calculation task and comparing the data of each of the calculation surplus received by the receiving means with the data of the calculation surplus of the self to calculate the calculation surplus of one of the calculation surpluses of any of the other calculation devices. If less than, among the other computer, and a transmitting means for transmitting the computing tasks to the other computing device that has transmitted the data of greater computational available capacity, the Shin means further includes a self computational remaining power data,
A new computing capacity data calculated from the computing capacity data received by the receiving means is transmitted at a predetermined ratio to the other computing apparatus connected to the adjacent computing capacity. 2. A calculation method of a calculation device that executes a plurality of calculation tasks in a distributed manner, wherein the calculation task and data of a calculation remaining capacity from another calculation device adjacently connected are received and received. Comparing the data of each calculation surplus with the data of the calculation surplus of the self, if the calculation surplus of the self is equal to or more than the respective calculation surplus of each of the other computing devices, the calculation task is processed, and the self calculation Spare data and new calculation surplus data calculated from the received calculation surplus data are transmitted at a predetermined ratio to the other computing device connected adjacently, and the received calculation surplus by comparing the data with the own account remaining data if its own computation margin is smaller than any of the calculated available capacity of the other computing devices, among the other computer, the data of the greater computing margin Calculation method and transmits the calculated task to the other computing device that has been signal.