JP2000285081A - Data communication method between nodes - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To eliminate unnecessary memory access and realize high processing performance. SOLUTION: When performing data transfer in a ring shape between a master node 2 and a plurality of slave nodes 3 to 6 among a plurality of nodes 2 to 6 connected in a ring via a bus 1, a master node 2 instructs the slave nodes 3 to 6 to perform calculations, and when collecting the calculation results of the slave nodes 3 to 6, each slave node compares the data output by the immediately preceding node with the result calculated by itself. And performs a predetermined operation, and outputs data of the result of the operation to the next node. Therefore, when each slave node sends data,
A predetermined pipeline operation can be performed, unnecessary memory access can be omitted, and high processing performance can be realized.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data communication method between nodes, and more particularly, to a method for transmitting data between a master node and a plurality of slave nodes among a plurality of nodes connected in a ring via a bus. The present invention relates to an inter-node data communication method for performing data transfer in a ring.

[0002]

2. Description of the Related Art As one of means for improving the processing capability of a computer, there is a method of performing parallel processing using a plurality of processors. In order to perform parallel processing, it is necessary to transmit and receive data between processors when the originally one data flow is divided into many. The form of this inter-processor communication network is divided into a tightly-coupled type and a loosely-coupled type.Generally, a tightly-coupled network has a small variation in communication cost (communication time) between each processor and connects a small number of processors. On the other hand, a loosely-coupled network has a low communication cost between processors physically and logically located near each other, but has a high communication cost between processors distant from each other.

For an application requiring a huge amount of computation, an architecture in which a large number of processors are connected by a loosely-coupled network is effective. An example of such an example is Japanese Patent Application Laid-Open No. 7-58762, "Data Transfer Method". In this architecture, since a certain amount of data can be transferred at a time by the DMA control unit, a large amount of input data necessary for a large-scale operation and result data after processing can be efficiently transferred. However, since data transferred by the DMA control is limited between the main memory and the communication processing buffer in the same node, the capacity that can be transferred at one time is limited by the capacity of the communication processing buffer memory. Also, JP-A-9-9126
In the “multiprocessor system” described in Japanese Patent Publication No. 2
Since the MA control unit is directly involved in the data transfer between the ring bus and the main memory, a larger amount of data can be transferred at a time. When parallel processing is performed with this architecture, each distributed processing processor element (hereinafter, slave node)
Is stored in a local memory connected to each of the slave nodes, and ultimately requires a data processing (hereinafter referred to as a totaling process) to collect these data in one place and further combine the data into one. Sometimes. Conventionally, when performing this aggregation processing, a data transfer request is individually issued to each slave node in advance, and all data are stored in a local memory connected to a special control processor element (master node) that performs the aggregation processing. After the collection, the tally processing was performed only by this master node.

[0004]

In this system, in order to collect and collect the operation results, (1) (local memory read time of each slave node) (2) (from each slave node to the master node) (3) (Time to write the operation result collected from the slave node to the local memory of the master node) (4) (Time to read out the data written in (3) from the local memory of the master node in order to perform the aggregation processing (5) (Calculation time by master node) (6) Processing time including (calculation result writing time to local memory of master node) was required. However, this summation process is based on the sum of the operation results by each slave node.
In the case of a master-slave type inter-processor communication in which collision of communication packets does not occur as long as the communication packets flow in one direction, if the type of processing can be processed in a pipeline, the processing of storing the intermediate result in the local memory
(3) and (4) are obviously useless.

An object of the present invention is to provide an inter-processor communication system which realizes high processing performance by eliminating unnecessary memory access by performing a predetermined pipeline operation when each slave node transmits data. Is to do.

[0006]

According to the first aspect of the present invention, there is provided an apparatus for transmitting a signal between a master node and a plurality of slave nodes among a plurality of nodes connected in a ring via a bus. In the inter-node data communication method for performing data transfer in a state, the master node instructs the slave node to perform an operation, and when the operation result of the slave node is collected, the slave node to which the operation has been instructed transmits the immediately preceding operation. A predetermined operation is performed between the data output by the slave node and the result calculated by itself, and the data resulting from the operation is output to the next node.

That is, the present invention is an inter-node data communication method for transferring data in a ring between a master node and a plurality of slave nodes among a plurality of nodes connected in a ring via a bus. .

[0008] The master node instructs the slave node to perform an operation. In this case, the master node may instruct all the nodes (slave nodes) other than the master node among the plurality of slave nodes to perform the operation. The calculation may be instructed.

When the operation result of the slave node is collected, the slave node to which the operation is instructed performs a predetermined operation between the data output by the immediately preceding slave node and the result calculated by itself. The data resulting from the operation is output to the next node.

Here, the slave node to which the operation is instructed is all slave nodes when the operation of the master node is instructed to all the nodes other than the master node among the plurality of slave nodes. When the operation is selectively instructed to a plurality of slave nodes, the slave node to which the operation is instructed.

When the immediately preceding node is the master node and the slave node to which the operation is instructed receives data for performing the instructed operation from the master node, the slave node instructs this data and itself to perform the operation. A predetermined operation is performed with respect to the result of the calculation, and the data of the result of the operation is output to the next node. If the data is not input from the master node, the data of the result calculated by itself is output. Output to the next node.

As described above, according to the present invention, when retrieving the operation result of a slave node, the slave node instructed to perform the operation determines a predetermined value between the data output by the immediately preceding slave node and the result calculated by itself. Is performed, and the data resulting from the calculation is output to the next node, so that the data finally returned to the master node can be finally obtained. So, on the master node,
Since it is not necessary to write the operation result collected from the slave node to the local memory of the master node or to read out the written data from the local memory, these times can be omitted. That is, when each slave node transmits data, a predetermined pipeline operation is performed, unnecessary memory access can be omitted, and high processing performance can be realized.

Here, as described above, when the master node selectively instructs a plurality of slave nodes to perform an operation, the slave node of the plurality of nodes, for which the operation is not instructed, receives the immediately preceding operation. Output to the next node without changing the value of the data output by the slave node. In order to output the value of the data output by the immediately preceding slave node to the next node without changing the value, the data output by the immediately preceding slave node is directly output to the next node. 0 may be added or subtracted, and 1 may be multiplied or divided.

The above contents will be described in more detail with reference to FIG. The contents shown below are for making the above contents easy to understand, and the present invention is not limited thereto.

FIG. 1 shows a conceptual diagram of communication between processors according to the present invention. A plurality (in FIG. 1)
(Five) nodes (processor-local memory pairs) 2 to 6 are connected in a ring. Hereinafter, an operation in the case of performing interprocessor communication will be described.

First, a packet for collecting data while calculating data is transmitted from the master node 2. The packet at this time includes an instruction word for instructing each slave node to perform an operation, and initial data. The instruction word includes a code indicating an operation, a node identification code for designating a slave node to which this packet is applied, and the like. Here, it is assumed that the present invention is applied only to the slave node 3 and the slave node 5. The transmission of the initial data is performed so that the slave node connected in the direction in which the packet is transmitted, that is, the slave node performing the first operation does not need to perform any special processing.

Next, the slave node 3 receives this packet and interprets the instruction word. Slave node 3
Interprets the instruction word, reads the data from the local memory of the own node, and reads the immediately preceding node (master node 2).
It performs an operation on the data sent from, and knows that the result must be sent to the next node (slave node 4). The slave node 3 starts reading data from the local memory of its own node, and
Calculate the data sent every cycle from 2 and the data read every cycle from local memory,
The result is output to the slave node 4 every cycle. At this time, prior to the result data, the master node 2
The instruction code transmitted from the master node 2 is output, and the configuration of the output packet is made to match the configuration of the input packet transmitted from the master node 2.

The slave node 4 receives the packet output by the slave node 3, but refers to the node identification code of the instruction code, and knows that the own node is not a target.
The packet is transmitted to the slave node 5 as it is.

The slave node 5 performs the same operation as the slave node 3 with reference to the node identification code.

When the packet finally returns to the master node 2 through all the slave nodes, the result data is stored in the local memory of the master node 2. The result data at this time is data that has already been subjected to tabulation processing.

By processing as described above, data can be collected and counted in one packet, compared with a case where the results are once collected in the master node and the calculation is performed. The influence of the communication latency can be suppressed, the number of memory accesses can be further reduced, and the arithmetic unit of each slave node for which necessary arithmetic has been completed can be used effectively.

[0022]

Embodiments of the present invention will be described below in detail with reference to the drawings. Hereinafter, an embodiment when applied to a 64-bit ring bus will be described.

FIG. 4 shows a parallel processing system for performing the inter-node data communication method according to the present embodiment.
The system includes a host computer 10 used for developing a simulation program and analyzing result data, and a parallel simulation engine 11. The parallel simulation engine is configured by connecting one master node 12 and a plurality of slave nodes 13.1 to 13.n-1 in a ring shape by a ring bus 1. All nodes include a processor element (PE) 14 and a local memory 15. The master node includes an interface circuit 16 for connecting to a host computer.

FIG. 5 shows an internal configuration of a processor element for performing interprocessor communication according to the present invention. The processor element 17 includes a ring bus interface unit 18 that performs inter-processor communication processing using a ring bus, an integer operation unit 19 that performs control of the entire processor element and performs 32-bit integer arithmetic processing, and a floating-point arithmetic that performs 64-bit double-precision floating-point arithmetic Unit 20, integer operation unit 19
And a 2 KB instruction cache unit 21 that can supply instructions every cycle to the floating point arithmetic unit 20;
8K that can quickly respond to data access requests from the integer operation unit 19 or floating point operation unit 20
The B data cache unit 22 includes a memory interface unit 23 that provides an interface to a local memory outside the processor element. These functional units are interconnected by an internal data bus 26.

The floating-point operation unit 20 includes a pipeline adder / subtracter and a pipeline multiplier.
EE double-precision real number addition / subtraction and multiplication / division can be executed in a pipeline every cycle with a latency of 4 cycles. In addition, the ring bus interface unit 18 and the floating point arithmetic unit 20 are connected to the ring bus arithmetic input bus 24.
And a ring bus operation output bus 25. For this reason, even if the internal data bus 26 is being used by another unit, the floating-point arithmetic unit 20 receives 64-bit floating-point arithmetic data from the ring bus interface unit 18 every cycle and transfers the arithmetic result to the ring bus interface unit. Can be output.

The processor element 17 has many other signals (not shown) such as an instruction synchronous input / output signal for notifying the reception timing of the ring bus communication packet, and performs communication with other processor elements via the ring bus and high-speed communication. Arithmetic processing is possible.

FIG. 6 shows a data format of a packet used for communication between processors. The packet is 64 bits x
It consists of multiple words and is transmitted via the 64-bit ring bus, one word at a time from the beginning. The information constituting this packet is roughly divided into four types: an instruction word 31, an address word 32, a dummy word 33, and a data word.
The command word 31 includes information for identifying the packet so that the node receiving the packet can perform a predetermined operation. The address word 32 includes an address field 35 indicating an operand data storage address on the receiving side. The dummy word 33 is invalid data inserted to match the processing timing on the transmission side and the reception side. There is no. The data word 34 is operand data used for operation at the time of input, and becomes operation result data at the time of output. The instruction word 31 is further divided into four 16-bit information according to bit positions in the word. The 63rd to 48th bits are an instruction identification code field 36 (FRPA), and are assigned numerical values for the node that has received the packet to distinguish it from other packets. No.
The 47th to 32nd bits are the operation data length field 37 (l
en), and the number of subsequent data words is stored. The 31st to 16th bits are a transmission node ID field 38 (src), which stores the identification number of the node that transmitted this packet. The fifteenth bit to the zeroth bit are a receiving node ID field 39 (dest), which stores the identification number of the node that should receive this packet. In the receiving node ID field 39, a plurality of nodes can be designated in addition to a single node.

As shown in FIG. 7, the adjacent nodes are connected by command synchronization input / output control signals 40 to 41 in addition to the ring bus input / output. Activating the output signal informs the next node of the position of the instruction word (ie, the beginning of the packet). Next, the operation of the present embodiment will be described.

FIG. 2 shows a flowchart of a Monte Carlo simulator for a MOS transistor device, which is an application program to which the present embodiment is applied. That is, in step 80, pre-processing (initialization) is performed, and in step 82, the potential in the transistor device is calculated (calculation of Poisson equation). In step 84, the motion of the particles is calculated, and in step 86, it is determined whether or not the motion of the particles has become constant, thereby determining whether or not the convergence has been achieved. If not converged, the process returns to step 82 to execute the above processing.
In step 8, post-processing (this finally obtained data is stored).

Here, in the Monte Carlo simulation, it is necessary to track a large number of particles in order to obtain high accuracy, and in a single processor system, the time of the particle motion calculation processing in step 84 is mainly a problem. .

On the other hand, when the motion calculation of the particles is processed in parallel by the multiprocessor system, the calculation time can be greatly reduced, and the calculation time can be further shortened by also performing the potential calculation in parallel.

Therefore, in the present embodiment, a plurality of slave nodes perform calculations in a distributed manner, and the calculation results are returned to the master node. Figure 3 shows the flow of this process.
Shown in FIG. 3A shows a processing routine of the master node, and FIG. 3B shows a processing routine of the slave node.

First, the master node performs step 102
In step 104, particles are distributed to each slave node. The same amount of particles is distributed to each slave. This allows each slave node to:
As shown in step 124, the sorted particles are set.

Next, the master node determines in step 106
Indicates the calculation of the potential. Accordingly, the slave node calculates the potential in step 126. That is, the state of the electric field around each particle is calculated.

Next, the master node determines in step 108
Indicates the calculation of the motion of each particle. Accordingly, in step 128, the slave node calculates the motion of each particle in charge of itself.

The final data to be obtained is how much the potential distribution of each part of the transistor is obtained when a predetermined voltage is applied. For this purpose, each particle assigned to each slave node must You need to know where they are.

Therefore, the master node determines in step 11
At 0, the calculation result of each slave node is collected. That is,
The packet data described above is output in a ring shape.

Upon receiving the packet data from the immediately preceding node, each slave node rewrites the packet data in step 130. In other words, the particle motion calculation in the above step 128 makes it possible to grasp where in the transistor the particle in charge of itself exists.
That is, it is possible to grasp how many particles exist at each location (that is, charge amount data at each location). On the other hand, each data area of the data word 34 in the packet data (see FIG. 6) is an area for recording the number of particles (charge amount data) existing at the location corresponding to each location of the transistor.

Therefore, in step 128, for each data area of the data word 34, the value recorded in the data area is changed to the value recorded in the area (that is, the value added in the immediately preceding note). Is rewritten to a value obtained by adding the value of the particle obtained by the calculation, and the result is output to the next node.
Thus, when the packet data finally returns to the master node, the total of the charge amount data calculated by all the slave nodes is recorded in each data area of the data word 34. Therefore, the master node does not have to write the charge amount data collected from the slave node to the local memory of the master node for each slave node, and does not need to read or write the written data from the local memory. Can be omitted.

Then, the master node determines in step 11
In step 2, it is determined whether or not the convergence has been achieved as described above. If the convergence has not occurred, each slave node is informed of the convergence (thus, step 132 is negatively determined). on the other hand,
If the convergence has occurred, post-processing is performed in step 114 as described above.

FIG. 8 shows the packet output timing from the master node. When transmitting a packet from the master node, initial value data is inserted as a data word. The initial value data should be
Set to 0, and 1 for multiplication. By doing so, the slave node that directly receives the packet from the master node and the other slave nodes that receive the packet indirectly from the slave node may perform the same processing.

Here, if the operation data length is about the number of all nodes or more, the packet being transmitted by the master node may make a round of the ring bus and return to the master node again. At this time, if the initial data is generated by another unit such as the integer operation unit 19, or if an attempt is made to use the data string stored in the local memory as the initial data, the internal data bus 26 is used, and the ring bus input Even if it is attempted to store the operation result in the local memory, the user must wait until the internal data bus 26 is released. During this time, the result data is transmitted from the ring bus input every cycle. Therefore, if all the result data is to be stored in the input buffer inside the ring bus interface unit 17, a large-capacity input buffer is required.

To avoid this, the initial data is generated only by the ring bus interface unit 18.

FIG. 9 shows the packet reception timing at the slave node and the packet output timing after the operation. When the reception of the packet is confirmed by the slave node, one of the operation operands is changed to a floating-point operation unit.
Preparation for a burst transfer between the local memory and the internal data bus for sending to 20 is started. During this time, a dummy word is input to the ring bus input, and after several cycles,
The dummy cycle is adjusted in advance so that the other operand data dataA1 reaches the ring bus input at the timing when the first operand data dataB1 is read from the local memory onto the internal data bus.

The floating-point operation unit 20 receives two columns of operation operands dataAn and dataBn from the ring bus operation input bus 24 and the internal data bus 26 every cycle, respectively, and after pipeline operation, outputs the result to the ring bus operation output bus 25. Output every cycle. The ring bus interface unit 18 outputs the instruction word (FRPA) of the packet in advance so that the operation result dataCn can be transmitted from the ring bus output in the next cycle. By doing so, the subsequent nodes can receive the same type of packet, and there is no need for special timing adjustment processing depending on the position of the node.

FIG. 10 shows the reception timing of the packet finally returned to the master node. The received data is stored in the local memory via the internal data bus 26.
According to this embodiment, the calculation processing of the space charge distribution is improved as follows. Number of mesh divisions (in the above example, each number of transistors):
100 × 100 = 10,000 When the number of slave nodes is 100, according to the invention of JP-A-9-91262, communication (data transfer) time: (10,000 [pure data communication time] +100 [packet arrival time + recovery time] +10 [overhead]) x 100 [number of slave nodes] = 1,011,000 cycles Operation time: (1 [various overhead] +1 [pipeline load / addition / store] x 10,000 [number of operations]) x 100 [number of slave nodes] = 1,000,100 cycles Communication + operation time: 1,011,000 + 1,000,100 = 2,011,100 cycles, whereas according to this embodiment communication + operation time: 10,000 [data communication and operation time] +10
[Overhead] x 100 [the number of slave nodes] + 100 [packet return time] = 11,100 cycles, and the speed can be increased about 200 times. Furthermore, increasing the number of slave nodes (to improve processing speed),
Alternatively, by increasing the number of mesh divisions (for improving calculation accuracy), the effect of speeding up is further increased.

By the way, depending on the application,
In such data collection / aggregation processing after the operation is completed in each slave node, only addition and subtraction of 32-bit integers may be sufficient. At this time, as shown in FIG. 11, in addition to the bus 24.2 connecting the ring bus operation input bus 24 to the floating-point operation unit 20, a bus 24.1 connecting the integer operation unit 19 is provided. One of the bus 25.1 for outputting the operation result and the bus 25.2 for outputting the operation result by the floating-point operation unit 20 may be selected by the multiplexer 42 and connected to the ring bus operation output bus 25. In this case, since the integer data is 32 bits per word, a 64-bit ring bus and
Every cycle using 64-bit internal / external data bus
Can input and output 2-word data. In order to make use of this transfer capability, the addition of a 32-bit adder / subtractor in addition to the 32-bit ALU inside the integer operation unit 19 allows two additions / subtractions to be performed simultaneously.

As described above, according to the present embodiment, after the arithmetic processing distributed to each node is completed using the multiprocessor system connected by the ring bus, data is collected to one node. However, in applications that need to perform arithmetic processing that can be further pipelined, this final operation is not performed intensively by one node, but is performed in a pipelined manner when each node sends data. In this way, it is possible to effectively use arithmetic units inside many processor elements, reduce memory accesses concentrated on the master node, and increase processing efficiency.

[0049]

As described above, according to the present invention, when the operation result of the slave node is collected, the slave node to which the operation is instructed performs the operation between the data output by the immediately preceding slave node and the result calculated by itself. Performs a predetermined operation and outputs the data resulting from the operation to the next node, so that the data finally returned to the master node can be used as the data finally obtained, thereby reducing the processing time. Has the effect of being able to

[Brief description of the drawings]

FIG. 1 is a conceptual diagram of the present invention.

FIG. 2 is an original flowchart (single processor flowchart) of the Monte Carlo device simulation software used in the present embodiment.

FIG. 3 is a flowchart of parallelized Monte Carlo device simulation software used in the embodiment of the present invention.

FIG. 4 is an example of a multiprocessor system.

FIG. 5 is a diagram illustrating an internal configuration of a processor element.

FIG. 6 is a diagram illustrating a data format of a communication packet.

FIG. 7 is a diagram illustrating signal lines for synchronizing transmission and reception of communication packets and their connections.

FIG. 8 is a diagram illustrating a timing of outputting a packet from a master node.

FIG. 9 is a diagram illustrating a packet reception timing in a slave node and a packet output timing after a calculation.

FIG. 10 is a diagram illustrating reception timing of a packet that has finally returned to the master node.

FIG. 11 is a diagram showing an internal configuration of a processor element having means for connecting a plurality of arithmetic units and a ring bus interface unit.

[Explanation of symbols]

 1 Ring bus 2 Master node 3 to 6 Slave node 10… Host computer 11 Parallel simulation engine 12 Master node 13.1 to 13.n-1 Slave node 14 Processor element 15 Local memory 16 Host interface circuit

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Nobuaki Miyagawa 2274 Hongo, Ebina-shi, Kanagawa Fuji Xerox Co., Ltd. (72) Inventor Mitsumasa Koyanagi 1-22-5 Yurigaoka, Natori-shi, Miyagi F-term (reference) 5B045 AA07 BB13 BB47 GG17 5K031 AA02 BA02 CA05 DA02 DB02 DB10

Claims (2)

[Claims] 1. An inter-node data communication method for transferring data in a ring between a master node and a plurality of slave nodes among a plurality of nodes connected in a ring via a bus, wherein the master node comprises: When an operation is instructed to the slave node and the operation result of the slave node is collected, the slave node to which the operation is instructed performs a predetermined operation between the data output by the immediately preceding slave node and the result calculated by itself. And outputting data of the result of the operation to a next node. 2. The method according to claim 1, wherein the master node selectively instructs a plurality of slave nodes to perform an operation, and a slave node of the plurality of nodes, the operation of which is not instructed, outputs data output by the immediately preceding slave node. The data communication method between nodes according to claim 1, wherein the value is output to the next node without changing the value.