JP2870494B2 - Irregular address data transfer apparatus 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 distributed memory type parallel processing system in which one program is distributed and executed by a plurality of nodes (processors) connected via a network, and more particularly to such a distributed memory type parallel processing system. The present invention relates to an irregular address data transfer device and method in a processing system.

[0002]

2. Description of the Related Art Conventionally, data transfer between a plurality of nodes in a distributed memory type parallel processing system of this kind has been described in, for example, Japanese Patent Application Laid-Open No. 3-240857. A multiprocessor system for processing a sent message by adding one index value representing a data processing function to be processed by the message and activating a data processing function corresponding to the index value on the receiving side. Has been proposed.

[0003]

However, in the conventional technique described in Japanese Patent Laid-Open No. 3-240857, the data processing function activated on the receiving side is a specific one defined in advance, and Since one index value corresponds to the entire message, when applied to transfer of irregular address data as in the present invention,
For example, it is necessary to transfer data as a message one element at a time.

[0004] However, when data is transferred as a message one element at a time, a message corresponding to the number of data elements is generated, resulting in a significant increase in communication overhead and a reduction in communication speed. There's a problem.

SUMMARY OF THE INVENTION Accordingly, the present invention has been made in view of the above-described problems, and has an irregular address data transfer device capable of reducing the execution time required for transferring irregular address data in a distributed memory type parallel processing system. And a method.

[0006]

In order to achieve the above-mentioned object, the present invention provides a distributed memory type parallel processing system having a plurality of nodes consisting of a processor and a memory connected via a network. A transmitting node that transmits data, a mask generating unit that generates mask data for each node from the address vector,
An address decomposing unit that decomposes and compresses the address vector from the address vector and the mask data in node units, an address transmitting unit that transmits the decomposed address to each node on the receiving side, and a data vector in node units according to the mask data. A data decomposer for decomposing and compressing, and a data transmitter for transmitting decomposed data to each node on the receiving side, while each node on the receiving side is transmitted from the node on the transmitting side. An address receiving unit for receiving an address; a data receiving unit for receiving data transmitted from the transmitting node; and a data storage unit for storing data received according to the received address. And an irregular address data transfer device.

Further, according to the present invention, in a distributed memory type parallel processing system having a plurality of nodes composed of a processor and a memory connected via a network, a receiving node for receiving irregular address data includes an address vector. , A mask generation unit that generates mask data for each node, an address decomposition unit that decomposes and compresses the address vector from the address vector and the mask data in node units, and transmits the decomposed address to each node on the transmission side. An address transmitting unit, a data receiving unit that receives data transmitted from each of the transmitting nodes, and a data merging unit that expands the received data according to the mask data and merges data from each of the transmitting nodes. And each of the transmitting-side nodes transmits from the receiving-side node. An address receiving unit that receives the read address, a data reading unit that reads data of the received address, and a data transmitting unit that transmits the read data to the receiving node. An irregular address data transfer device is provided.

Further, the present invention relates to a distributed memory type parallel processing system having a plurality of nodes composed of a processor and a memory connected via a network, wherein the plurality of nodes include a node from a certain node. When transmitting the irregular address data to the nodes, the mask data for each node is generated from the address vector,
There is provided an irregular address data transfer method characterized in that an address vector and a data vector are decomposed in units of nodes in accordance with the generated mask data, and the decomposed addresses and data are transmitted to each node as a continuous block.

Still further, according to the present invention, in a distributed memory type parallel processing system having a plurality of nodes composed of a processor and a memory connected via a network, one of the plurality of nodes includes the node. When receiving irregular address data from another node, mask data for each node is generated from the address vector, the address vector is decomposed into node units according to the generated mask data, and this decomposed address is After transmitting to the node as a continuous block, receiving data corresponding to the address from each node as a continuous block, expanding the received data according to the mask data and merging data from each of the nodes. A method for transferring irregular address data is provided.

As described above, according to the irregular address data transfer apparatus and method of the present invention, when data is transmitted, the address and data are packed and transferred for each node, and when the data is received. After transmitting a packed address, the received packed data is decompressed, so that continuous block transfer can be used for transferring irregular address data.

[0011]

Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing a configuration of an embodiment of the present invention.

Referring to FIG. 1, the preferred embodiment of the present invention is a distributed memory type parallel processing system including a plurality of nodes 2 and 2 ′ each having a processor and a memory independently, and a network 3. , Is configured as an irregular address data transfer device 1 for transmitting and receiving irregular address data between nodes.

More specifically, the irregular address data transfer device 1 transmits, as a configuration for transmitting irregular address data, the given address information in the node 2 on the transmitting side that transmits irregular address data. When each node has an address belonging to the node, a mask generation unit 20 that sets a mask at a corresponding position, and decomposes and compresses given address information according to the obtained mask information for each node An address resolving unit 21; an address transmitting unit 22 for transmitting the decomposed address to each corresponding node (2 ′) on the receiving side; and a data decomposing unit that decomposes and compresses given data according to the mask information for each node. And a data transmission unit 25 for transmitting the decomposed data to the corresponding receiving-side nodes (2 '). In each of the nodes (2 '), an address receiving unit 23 for receiving an address transmitted from the transmitting node 2; a data receiving unit 26 for receiving data transmitted from the transmitting node 2; A data storage unit 27 that stores data received according to the address in a memory.

The irregular address data transfer device 1
Is a configuration for receiving irregular address data,
In the receiving node 2 receiving the irregular address data, a mask generating unit 20 that looks up the given address information and sets a mask at a corresponding position when each node has an address belonging to that node; An address decomposing unit 21 that decomposes and compresses the given address information according to the obtained mask information for each node, and an address transmitting unit 22 that transmits the decomposed address to each corresponding node (2 ') on the transmitting side. A data receiving unit 26 for receiving data transmitted from each node (2 ') on the transmitting side, and expanding the received data in accordance with the mask information to merge data from each node (2') on the transmitting side. And a data merging unit 29 for transmitting data, while each node (2 ') on the transmission side
Is an address receiving unit 23 that receives an address transmitted from the receiving node 2, a data reading unit 28 that reads data of the received address, and a data that transmits the read data to the receiving node 2. A transmission unit 25;
Is provided.

Although FIG. 1 shows the case where two nodes 2 and 2 'are connected to the network 3, another node may be connected to the network 3 in addition to the nodes 2 and 2'. Of course. Also, as shown in FIG. 1, the nodes 2 and 2 'preferably have the same configuration so that they operate as both the transmitting side and the receiving side of the irregular address data.

Next, the operation of the embodiment of the present invention will be described.

FIG. 2 is a flowchart showing a flow of processing when transmitting irregular address data according to the embodiment of the present invention. Hereinafter, the operation of transmitting the irregular address data according to the embodiment of the present invention will be described with reference to FIGS.

Here, the transmission operation of the irregular address data means that the data array distributed to a plurality of nodes is designated from a specific node to each of the other nodes including the specific node. Data is transmitted by an irregular address.

The transmitting-side node 2 for transmitting the irregular address data sequentially transmits the destination nodes to the nodes 2, 2 ',.
The following steps 201 to 209 are changed while
Is performed.

That is, the transmitting node 2 (shown in the upper part of FIG. 2) performs an operation of setting a mask for an address belonging to the destination node by the mask generation unit 20 (step 201), and obtains the obtained mask information. And the address information is input to the address decomposing unit 21. Address decomposition unit 21
Collects and compresses the addresses on which the masks stand, and generates a decomposed address of the continuous vector (step 20).
2). The data decomposing unit 24 receives the mask information and the data as input, collects and compresses the data having the mask according to the mask information, and generates decomposed data of a continuous vector (step 203).

Here, when the destination node currently being processed is the transmitting node 2 itself, there is no need to perform data transfer. Therefore, the memory designated by the disassembly address by the data storage unit 27 in the own node is used. (Step 204).

On the other hand, if the destination node is different from the transmitting node 2, the address transmitting unit 22 of the transmitting node 2 transmits the disassembled address to the destination node (step 205). Further, the data transmission unit 25 of the transmission-side node 2 transmits the decomposed data to the destination node (step 206). Note that both address transmission and data transmission are continuous vector transmissions.

The destination node (shown in the lower part of FIG. 2) receives the transmitted address (received address) by the address receiver 23 (step 207), and receives the transmitted data (received data) by the data receiver 26. ) Is received (step 208). Since the receiving length of these vectors depends on the address, it cannot be determined in advance, but if the vector length is transmitted first and then the vector is transmitted, the receiving side receives the vector length first. This can solve this problem because the vector can be received by that length.

The destination node sequentially stores the reception data in the address area of the memory specified by the reception address by the data storage unit 27 (step 209).

FIG. 3 is a flowchart showing a flow of processing when receiving irregular address data according to the embodiment of the present invention. Hereinafter, the operation of receiving irregular address data according to the embodiment of the present invention will be described with reference to FIGS.

Here, the operation of receiving irregular address data refers to the operation of receiving data having a specified irregular address from each node including a specific node in a data array distributed in a plurality of nodes. Is transmitted, and the data of each node is received by the specific node.

The node 2 on the receiving side receiving the irregular address data sets the destination nodes in the order of nodes 2, 2 ',.
The following steps 301 to 309 while changing
Is performed.

That is, the receiving-side node 2 (shown in the upper part of FIG. 3) performs an operation of setting a mask for an address belonging to the destination node by the mask generation unit 20 (step 301), and obtains the obtained mask information. And the address information is input to the address decomposing unit 21. Address decomposition unit 21
Collects and compresses the addresses on which the masks stand, and generates a decomposed address of the continuous vector (step 30).
2).

Here, when the destination node currently being processed is the receiving node 2 itself, there is no need to perform data transfer, and therefore, the memory designated by the data readout unit 28 in the own node specifies the disassembly address. The own node data is read from the address area (step 303).

On the other hand, if the destination node is different from the receiving node 2, the address transmission unit 22 of the receiving node 2 transmits the disassembled address to the destination node (step 304). This address transmission is transmission of a continuous vector.

The destination node (shown in the lower part of FIG. 3) receives the transmitted address (received address) by the address receiving unit 23 (step 305). Since the reception length of these vectors depends on the address, it cannot be determined in advance. However, this problem is also caused by transmitting the vector length first, as in the case of the transmission of the irregular address data described above. This can be solved by:

The destination node sequentially reads data from the address area of the memory specified by the reception address by the data reading unit 28 (step 306), and sends the read data to the receiving node 2 by the data transmission unit 25. It is sent back (step 307). This data transmission is also transmission of a continuous vector.

When the transmitted data (received data) is received by the data receiving section 26 of the node 2 on the receiving side (step 308), the own node data and the received data read out in step 303 are generated in step 301. The data is expanded at the position where the mask stands according to the set mask information, and the data of all the nodes is merged by the data merging unit 29 (step 309).

[0035]

Next, in order to more specifically describe the above-described embodiment of the present invention, an embodiment of the present invention will be described in detail with reference to the drawings.

FIG. 4 is a diagram schematically showing the configuration of one embodiment of the present invention.

Referring to FIG. 4, one embodiment of the present invention is:
The network includes four nodes 0 to 3 and a network, and functions as a load equalizing device that equalizes the load of one program by transmitting and receiving irregular address data to and from each other.

The transmission operation of the irregular address data according to the embodiment of the present invention is executed by a program for updating an array using a list vector as shown in FIG. 5, for example. Here, it is assumed that the array A having 12 elements is divided into three elements as shown in FIG. 4 and distributed and arranged at each node. That is, the sequences A (1) to A (3)
At node 0, arrays A (4) to A (6) at node 1,
Arrays A (7) to A (9) are stored in node 2 and arrays A (10)
ＡA (12) are assigned to the node 3. It is assumed that all elements of the array B, which is data, and the array L representing an irregular address are assigned to the node 0.

It is to be noted that there is no problem even if the arrays B and L are distributed to each node similarly to the array A. This is because the transmitting operation may be performed on each of the nodes to which the array B and the array L belong.

On the other hand, the receiving operation of the irregular address data in one embodiment of the present invention is executed by a program for quoting an array using a list vector as shown in FIG. 6, for example. The allocation of the array A, array B, and array L to each node is the same as in the case of the above-described transmission operation.

Next, the operation of the embodiment of the present invention will be described with reference to the flowcharts of FIGS.

First, the transmission operation will be described.
FIG. 7 is a diagram for explaining the transmission operation of the irregular address data in one embodiment of the present invention.

As shown in FIG. 7, the contents of the array L are [7,
9, 11, 1, 4, 2, 6, 5, 12, 8, 3, 10]
Is assumed to be irregular. First, transmission from node 0 to node 1 will be described.

The mask generation unit of the node 0 looks at the address indicated by the array L and generates a mask of a portion belonging to the node 1 of the array A (step 201). The parts belonging to the node 1 in the array A are A (4), A (5), A
(6), the generated mask is [0, 0, 0,
0,1,0,1,1,0,0,0,0]. According to the mask, the address resolving unit resolves the address belonging to node 1 (step 202). The generated decomposition address is [4, 6, 5]. Similarly, data corresponding to the address belonging to node 1 is decomposed by the data decomposing unit in the data indicated by array B (step 203).
The generated decomposition data is [B (5), B (7), B
(8)]. The decomposed address is transmitted as a continuous block to the node 1 by the address transmission unit (step 205), and the decomposed data is also transmitted to the node 1 as a continuous block by the data transmission unit (step 2).
06).

On the node 1 side, the address [4, 6, 5] is received by the address receiving unit (step 207).
The data [B (5), B (7), B]
(8)] is received (step 208). Then, the received data is stored in the memory according to the address information (Step 209). Specifically, A (4) is B
The content of (5) is A (6) and the content of B (7) is A
(5) stores the contents of B (8).

Although transmission from node 0 to node 1 has been described above, transmission from node 0 to node 2 and transmission from node 0 to node 3 are similarly processed.

FIG. 8 shows the transmission operation from node 0 to node 0, that is, the transmission operation in the case of transfer within node 0.
Shown in Referring to FIG. 8, processing up to creation of a disassembled address and disassembled data is performed in the same manner as in the case shown in FIG. Is stored in the array A (step 204).

Next, the case of the receiving operation will be described.
FIG. 9 is a diagram for explaining the operation of receiving irregular address data in one embodiment of the present invention.

As shown in FIG. 9, the contents of array L are [7,
9, 11, 1, 4, 2, 6, 5, 12, 8, 3, 10]
Is assumed to be irregular. First, reception from node 1 at node 0 will be described.

The mask generation unit of node 0 looks at the address indicated by array L and generates a mask of a portion belonging to node 1 of array A (step 301). The parts belonging to the node 1 in the array A are A (4), A (5), A
(6), the generated mask is [0, 0, 0,
0,1,0,1,1,0,0,0,0]. According to the mask, the address resolving unit resolves the address belonging to node 1 (step 302). The generated decomposition address is [4, 6, 5]. The decomposed address is
The data is transmitted as a continuous block to the node 1 by the address transmitting unit (step 304).

On the node 1 side, the address [4, 6, 5] is received by the address receiving unit (step 30).
5). Then, data is read from the memory according to the address information (step 306). The read data is [A (4), A (6), A (5)]. This read data is transmitted to the node 0 by the data transmission unit of the node 1.
(Step 307), and received by the data receiving unit of the node 0 (step 308). The received data is expanded by the data merging unit according to the mask information, and stored in the array B (step 309). Specifically, the contents of A (4) are stored in B (5), and the contents of A (4) are stored in B (7).
The contents of (6) are stored in B (8), and the contents of A (5) are stored in B (8).

In the above, the reception from the node 1 at the node 0 has been described. However, the reception from the node 2 at the node 0 and the reception from the node 3 at the node 0 are similarly processed.

The reception from the node 0 at the node 0
That is, FIG. 10 shows a receiving operation in the case of transfer within the node 0. Referring to FIG. 10, processing is performed in the same manner as shown in FIG. 9 up to the generation of the disassembled address, but the subsequent transmission operation is unnecessary, and the data is immediately read from the memory according to the address information by the data reading unit of node 0 The data is read out (step 303) and stored in the array B according to the mask information by the data merging unit (step 309).

[0054]

As described above, according to the present invention,
Since a plurality of elements are blocked as continuous data and the overhead of data transfer during transmission or reception is reduced, the elapsed time of program execution is reduced as compared with the case where irregular address data is transmitted or received one element at a time. be able to.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a configuration of an embodiment of the present invention.

FIG. 2 is a flowchart showing a flow of processing when transmitting irregular address data according to the embodiment of the present invention.

FIG. 3 is a flowchart showing a processing flow when receiving irregular address data according to the embodiment of the present invention.

FIG. 4 is a diagram schematically showing the configuration of one embodiment of the present invention.

FIG. 5 is a diagram showing an example of a transmission program used in one embodiment of the present invention.

FIG. 6 is a diagram showing an example of a receiving program used in one embodiment of the present invention.

FIG. 7 is a diagram for explaining an operation of transmitting irregular address data (transmission operation to another node) in one embodiment of the present invention.

FIG. 8 is a diagram for explaining a transmission operation of irregular address data (transmission operation to the own node) in one embodiment of the present invention.

FIG. 9 is a diagram for explaining a receiving operation of irregular address data (a receiving operation from another node) in one embodiment of the present invention.

FIG. 10 is a diagram for explaining the operation of receiving irregular address data (the operation of receiving from the own node) in one embodiment of the present invention.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Irregular address data transfer device 2, 2 'node 3 Network 20 Mask generation unit 21 Address decomposition unit 22 Address transmission unit 23 Address reception unit 24 Data decomposition unit 25 Data transmission unit 26 Data reception unit 27 Data storage unit 28 Data read unit 29 Data Merging Section

Continuation of the front page (58) Field surveyed (Int.Cl. ⁶ , DB name) G06F 15/163 G06F 17/16

Claims (4)

(57) [Claims] In a distributed memory type parallel processing system having a plurality of nodes consisting of a processor and a memory connected via a network, a node on the transmitting side for transmitting irregular address data is provided on a node-by-node basis from an address vector. A mask generation unit for generating the mask data of the above, an address decomposition unit for decomposing and compressing the address vector from the address vector and the mask data in node units, and an address transmission unit for transmitting the decomposed address to each node on the receiving side. A data decomposer that decomposes and compresses a data vector in node units in accordance with the mask data, and a data transmitter that transmits the decomposed data to each node on the receiving side. An address receiving unit that receives an address transmitted from the transmitting node, An irregular address data transfer device, comprising: a data receiving unit that receives data transmitted from the transmitting node; and a data storage unit that stores data received according to a received address. 2. A distributed memory type parallel processing system having a plurality of nodes composed of a processor and a memory connected via a network, wherein a receiving node for receiving irregular address data is provided on a node-by-node basis from an address vector. A mask generation unit that generates the mask data of the above, an address decomposition unit that decomposes and compresses the address vector from the address vector and the mask data in node units, and an address transmission unit that transmits the decomposed address to each node on the transmission side. A data receiving unit that receives data transmitted from each of the transmitting nodes; and a data merging unit that expands the received data according to the mask data and merges data from each of the transmitting nodes. On the other hand, each node on the transmission side transmits an address transmitted from the node on the reception side. An address receiving unit that receives the data, a data reading unit that reads data of the received address, and a data transmitting unit that transmits the read data to the receiving node. Rule address data transfer device. 3. A distributed memory parallel processing system having a plurality of nodes consisting of a processor and a memory connected via a network, wherein one of the plurality of nodes is not connected to another node including the node. When sending rule address data,
Generating mask data for each node from the address vector, decomposing the address vector and the data vector into node units according to the generated mask data, and transmitting the decomposed addresses and data to each node as a continuous block. Characteristic irregular address data transfer method. 4. A distributed memory type parallel processing system having a plurality of nodes each including a processor and a memory connected via a network, wherein one of the plurality of nodes is insulated from another node including the node. When receiving the rule address data,
After generating mask data for each node from the address vector, decomposing the address vector into nodes in accordance with the generated mask data, transmitting the decomposed addresses to each node as a continuous block, An irregular address data transfer method, comprising: receiving data corresponding to an address as a continuous block; expanding the received data according to the mask data; and merging data from the respective nodes.