JP2945726B2 - Parallel processing system - Google Patents

Description

Description: BACKGROUND OF THE INVENTION (Industrial Application Field) The present invention relates to a parallel processing system configured by connecting a plurality of processor elements each having a processor and a memory. It relates to broadcast transfer for transferring the same data.

(Prior Art) Many parallel processing systems composed of a plurality of processor elements have been conventionally proposed. FIG. 6 shows the basic configuration of these parallel processing systems. In FIG. 6, the parallel processing system is obtained by connecting a plurality of processor elements 102 to 110 by a connecting means 100. Is a memory, 114 is an output buffer, 115 is an input buffer, 116 is an address bus, and 117 is a data bus. Then, the data is transferred between the processor elements 102 to 110 using the coupling means 100.

At this time, the processor element 1
The information passed between 02 and 110 is made according to a convention called a fixed protocol 120 as shown in FIG. The protocol 120 includes an address unit 122 for storing a destination of data, a data unit 124 for storing data, and a control unit 126 for storing control information. And protocol 1
In a parallel processing system that exchanges data at 20, there are four steps in the broadcast transfer.

First, the protocol 120 is set in all the processor elements 102 to 110.

In one processor element 102, the data is read from the broadcast data memory 113 and is taken into the output buffer 114.

The data in the output buffer 114 is output to the combining means 100, and each of the processor elements 102 to 110
Data is read from 0 into the input buffer 115.

Each of the processor elements 102 to 110 writes the data of the input buffer 115 to the memory 113.

Here, consider a case where a product of matrix vectors repeatedly performed in a part of the finite element method program is obtained.

First, assuming that the matrix is n × n and the vector is n × 1, as shown in FIG. 3, each of the processors 102 to 110 is provided with an i-row matrix component (j = 1, n) and an i-row vector component (j = 1) is stored. The following is a description of a program written in FORTRAN. However, in the following description, it is assumed that n = 5 and the symbol * means multiplication.

DO 10 i = 1, N APV = 0,0 DO 12 j = 1, N 12 APV = APV + AU (i, j) * X (j, i) 10 B (i, 1) = APV In this program, the matrix A data AU (i, j)
And the data (j, 1) of the vector X are in different processor elements 102 to 110, so that parallel calculation cannot be performed.

Therefore, a part of the program is rewritten and changed to the following program.

Then, the control operation is divided into two, that is, the broadcast transfer of (1) and the parallel calculation of (2). That is, first, the processor element in which i is 1 to n
Broadcast the vector components of j = 1 from 102 to 110 to the respective processor elements 102 to 110. here,
An array X (i, 1) represents an vector, and XC (j, i) represents an array enabled after broadcast transfer.

Next, the stored data array XC (j, i) and matrix A
Multiply the components by and sum them. Where AU
(I, j) represents an array for taking the product, B (i, 1) represents a vector for storing the result, and APV represents an intermediate sum of the product. And
The parallel calculation of FIG. 3 is as follows.

B1 = a11 * X1 + a12 * X2 + a13 * X3 + a14 * X4 + a15 * X5 B2 = a21 * X1 + a22 * X2 + a23 * X3 + a24 * X4 + a25 * X5 B3 = a31 * X1 + a32 * X2 + a33 * X3 + a34 * X4 + a35 * X4 + a35 * X4 + a35 * X4 + a35 * X4 * X5 B5 = a51 * X1 + a52 * X2 + a53 * X3 + a54 * X4 + a55 * X5 To perform high-speed parallel calculation of the product of the matrix A and the vector X, high-speed broadcasting between processor elements is necessary.

If the broadcast transfer is performed at high speed, the product of the matrix A and the vector X can be obtained at high speed. However, when the matrix A is a sparse matrix, the above method is not very effective. That is, as shown in FIG. 4, there are many components of 0 in the matrix A, and it is meaningless to perform a product of the matrix component of 0 and the vector component. In particular, when n of the matrix component becomes large, There is a meaningless 0 component, and the memory 113 is not effectively used.
Furthermore, data may not be completely stored.

For this, a list vector is used. As shown in FIG. 5, this list vector indicates that the non-zero component in the i-th row is in the j-th column. Product reduction and memory 113
Is effectively used. This is described as follows in a FORTRAN program.

DO 10 i = 1, N APV = 0.0 DO 12 j = 1, NZU (i, 1) 12 APV = APV + AU (i, 1) * X (IU (i, j), 1) 10 B (i, 1) = APV where NZU (i, 1) is the number of non-zero components in row i, IU (i, 1)
j) indicates in which column of the i-th row there is a non-zero component, and
j) is the corresponding component.

However, in this state, the data AU (i, j) of the matrix A and the data X (i, 1) of the vector X are in different processor elements 102 to 110, as in the above-described example, so that parallel calculation cannot be performed.

Therefore, the program is converted as follows to perform the parallel calculation.

This (3) is a step of performing a broadcast transfer,
(4) is a step of performing parallel calculation. And when using a list vector, the first step is
The vector X (IU (i, j),
1) Select only each processor element 102 ~
It is to take in 110. Next, parallel calculation is performed by each of the processor elements 102 to 110.

 The parallel calculation of FIG. 4 is as follows.

B1 = a11 * X1 + a13 * X3 + a15 * X5 B2 = a22 * X2 + a24 * X4 B3 = a31 * X1 + a33 * X3 + a15 * X5 B4 = a42 * X2 + a44 * X4 B5 = a53 * X3 + a55 * X5 Therefore, the data shown as a list vector By high-speed transfer to each of the selective processor elements 102 to 110, the product of the matrix A and the vector X using the list vector can be calculated in parallel at high speed.

In other words, by enabling high-speed broadcasting between the processor elements 102 to 110 and selectively performing this, the product of the matrix A and the vector X can be performed at high speed. High-speed parallel calculation of element method programs becomes possible.

(Problems to be Solved by the Invention) However, in the above-described conventional parallel processing system, the above operations (1) to (5) are performed in order, and each of the processor elements 102 to 110 accesses the memory every time the operation (1) is performed. Broadcast transmission cannot be performed. Further, there is a problem that data represented by a list vector used in the finite element method cannot be selectively taken in, and a product of the matrix A vector X and a finite element cannot be calculated at high speed. .

The present invention has been made to solve such problems.
In a parallel processing system in which a plurality of processor elements are combined, a high-speed broadcast transfer and the broadcast transfer can be performed between arbitrary processor elements, and a risk vector used in a part of the finite element method is used. It is an object of the present invention to provide a parallel processing system capable of performing a product of a matrix and a vector at high speed.

(Means for Solving the Problems) In order to achieve the above-mentioned object, means according to the first aspect of the present invention comprises a processor and a memory for storing data for the processor to perform processing. A plurality of processor elements, coupling means for connecting the processor elements so that data can be mutually transferred between the processor elements, and a transfer source processor in broadcast transfer for transferring the same data to the plurality of processor elements The present invention is directed to a parallel processing system including a first address generator that generates an element number, a variable address corresponding to data, and a control signal indicating that a broadcast transfer is to be performed.

The processor element compares an output buffer for outputting data from the memory to the combining means with a processor element number from the first address generator and its own processor element number, and outputs the result to the output section. A first comparator for outputting to the buffer.

Further, the processor element includes a storage means for updating and storing a variable address corresponding to the data in the output buffer each time the data in the output buffer changes, a variable address in the storage means and a variable address from the first address generator. And a second comparator for outputting the result to the output buffer.

In addition, each of the processor elements has an input buffer for inputting data loaded on the coupling means, and a second address generator for generating an address for writing data of the input buffer to the memory. .

The measures taken by the invention according to claim 2 correspond to claim 1.
In the parallel processing system described above, each processor element includes a first-in first-out memory that stores a processor element number of a processor element that outputs necessary data among data broadcast-transmitted to the processor element, and a processor mounted on a coupling unit. An element number is compared with the processor element of the advance memory, and a third comparator for outputting the result to an input buffer and a second address generator is provided.

(Operation) With the above configuration, in the invention according to claim 1, first,
When performing a broadcast transfer, the first address generator outputs a processor element number, a variable address, and a control signal indicating the broadcast transfer. Each processor element receives the signal from the first address generator, retrieves data corresponding to the variable address from the memory, stores the data in the output buffer, and stores the variable address of the data in the storage means. Subsequently, only the processor element corresponding to the processor element number from the first address generator outputs the data of the output buffer, and each processor element takes the data into the input buffer and stores it in the memory. Thereafter, the first address generator sequentially changes the processor element number, the processor element of the processor element number outputs the data of the output buffer, and each processor element sequentially stores the data in the memory.

Therefore, since each data is output without accessing the memory, the broadcast transfer can be performed at high speed.

In the invention according to claim 2, the first-in first-out memory stores the processor element number of the processor element that outputs necessary data, and stores the processor element number and the processor element number from the first address generator in the first-in first-out memory. The three comparators compare and if they match, take in the data from the processor element,
Store in memory.

Therefore, since data can be selectively taken in, the memory can be effectively used.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

First Embodiment FIG. 1 is a block diagram illustrating a parallel processing system according to a first embodiment. In FIG. 1, reference numerals 2, 4, 6, 8, and 10 denote processor elements, 50 denotes a first address generator, and the first address generator 50 is a processor element 2 of a transfer source by broadcast transfer. , A variable element 62 indicating transfer data, and a control signal indicating that a broadcast transfer is to be performed. 52 is a control line, 54 is an address bus, 56 is a data bus, and the control line 52, the address bus 54, and the data bus 56 are
Coupling means for connecting each of the processor elements 2 to 10 and the first address generator 50 is configured to enable mutual data transfer and the like.

On the other hand, 12 is a processor, 13 is a memory, 14 is an output buffer for outputting data from the memory 13 to a data bus 56, 15
Is an input buffer for inputting data of the data bus 56, 16 is an address bus, and 17 is a data bus, which are provided in the processor elements 2 to 10, respectively. Reference numeral 30 denotes a first comparator, 32 denotes a second comparator, 34 denotes a processor element number register for storing a processor element number, and 36 denotes storage means for changing and storing a variable address corresponding to data in the output buffer 14. Variable address registers provided in the processor elements 2 to 10, respectively. The first comparator 30 stores the processor element number 60 from the first address generator 50 and the processor element number stored in the processor element number register 34. Processor element number (for example, the first processor element 2
1, the second processor element 4 is set in order as 2. ) And compare the result to output buffer 14
On the other hand, the second comparator 32 compares the variable address 62 from the first address generator 50 with the variable address stored in the variable address register 36, and outputs the result to the output buffer 14. I do.

Further, reference numeral 42 denotes a second address generator provided in each of the processor elements 2 to 10, which generates an address for writing data input to the input buffer 15 to the memory 12.

Next, a broadcast transfer operation in the above-described parallel processing system will be described.

Therefore, a broadcast transfer for obtaining a product of a matrix and a vector represented by a program by FORTRAN as described in (1) below will be described.

First, the first address generator 50 first sets the processor element number 60 (having a value of 1) in the upper part and the variable address 62 (X (*, 1), where * indicates any) as the lower part. A control signal indicating that a broadcast is to be performed is provided on an address bus 54 and a control line 52.

On the other hand, each processor element 2 to 10 receives each signal from the first address generator 50 and
At 30, the processor element number 60 from the first address generator 50 is compared with the value of the processor element number register 34. At the second comparator 32, the first address generator
The variable address 62 from 50 is compared with the value of the variable address register 36 to confirm whether the corresponding data exists in the output buffer 14. When the processor element number 60 and the variable address 62 match, the data in the output buffer 14 is output as described later.

In this case, the output buffer 14 and the variable address register
Since there is no corresponding data in 36, each processor element 2 to 10 is connected to the memory via the address bus 16.
13 is accessed and data is written to the output buffer 14.
That is, the variable address 62 from the first address generator 50
Is arbitrary in X (*, 1), each processor element 2 to 10 has data X (j,
1) is retrieved from the memory 13. Then, in the output buffer 14 after the access, X (1,1) in the first processor element 2 and X (2,1) in the second processor element 4.
1) each processor element 2-10
Stores the data of X (j, 1) (j = 1,5). At the same time, each of the processor elements 2 to 10 stores the variable address register 36 at the variable address 62. As a result, the second comparator 32 includes all the processor elements 2 to
At 10, the variable address 62 from the first address generator 50 matches the value of the variable address register 36.

Furthermore, the first in each of the processor elements 2 to 10
Processor element 2 (in which the processor element number from the first address generator 50 matches the value in the processor element number register 34 among all the processor elements 2 to 10 based on the result of the comparator 30). 4
10) output the data of the output buffer 14 to the data bus 56. In this case, the processor element number 60 is 1
And the data X (1,1) of the first processor element 2
1) is output to the data bus 56.

Finally, all the processor elements 2 to 10 fetch the data X (1,1) into the input buffer 15, and furthermore, fetch this data X (1,1) with the address of the second address generator 42, XC (i , 1) is stored in the memory 13.

Next, the first address generator 50 changes the processor element number 60 to two. At this time, X (1,1), X (2,1), X (3,1), X (4,1) are output to the output buffers 14 of the respective processor elements 2 to 10 by the above-described operation.
1) and X (5,1), and the variable address register 36 of each processor element 2 to 10 may store a variable address corresponding to each data X (j, 1). Therefore, each processor element 2
The second comparator 32 in .about.10 always outputs a coincidence signal. Since the processor element number 60 matches only the second processor element 4, the second
Outputs the data X (2,1) of the output buffer 14 to the data bus 56 without accessing the memory 13.

This operation is similarly performed when the processor element number 60 is changed to 3, 4, and 5 by the first address generator 50. Therefore, the respective row components of the vector X shown in FIG. 3 are stored in the respective processor elements 2 to 10, and the access time to the memory 13 is reduced as compared with the conventional example. It is performed 4/3 times faster than in the case. Then, in each of the processor elements 2 to 10, the parallel calculation of the product of the matrix A and the vector X shown in FIG. 3 is performed.

<Second Embodiment> FIG. 2 is a block diagram showing a parallel processing system according to a second embodiment, in which broadcast transfer for obtaining a product of a sparse matrix A and a vector X shown in FIG. 4 is performed. is there.

That is, the first-in first-out memory 40 and the third comparator 44 are provided in each of the processor elements 2 to 10. The first-in first-out memory 40 stores processor element numbers 60 of processor elements 2 to 10 that output necessary data among data to be broadcast-transferred. For example, in FIG. In the processor element 2 of the first row, the third row, and the fifth row,
The processor element numbers (1), (2), and (3) corresponding to X1, X2, and X3 are stored in correspondence with the columns, and the second column in the second processor element 4 corresponding to the second row is stored. The processor element numbers (2) and (4) corresponding to X2 and X4 are stored in correspondence with and the fourth column.

The third comparator 44 is provided with the processor element number 60 on the address bus 54, that is, the processor element number 60 from the first address generator 50 and the processor element number stored in the first-in first-out memory 40. And outputs the result to the input buffer 15 and the second address generator 42.

Next, the broadcast transfer operation of this parallel processing system will be described.

At this time, the transfer data is as shown in the following (2) in a FORTRAN program.

First, similarly to the first embodiment, the first address generator 50 has a processor element number 62 (value is 1) at a higher level.
And an address indicating a variable address 62 (X (*, 1), * indicates an arbitrary value) is placed on the address bus 54, and a control signal indicating that broadcasting is performed is placed on the control line 52. .

On the other hand, each processor element 2 to 10 receives each signal from the first address generator 50 and
At 30, the processor element number 60 from the first address generator 50 is compared with the value of the processor element number register 34. At the second comparator 32, the first address generator
The variable address 62 from 50 is compared with the value of the variable address register 36 to check whether the corresponding data exists in the output buffer 14, and when each of the comparators 30, 32 outputs a coincidence signal, as described below. The data in the output buffer 14 is output.

In this case, the output buffer 14 and the variable address register
Since there is no corresponding data in 36, each processor element 2 to 10 is connected to the memory via the address bus 16.
13 is accessed and data is written to the output buffer 14. That is, similarly to the first embodiment, each of the processor elements 2 to
10 stores data X (j, 1) corresponding to its value j in the memory 13
Take out from. Then, the output buffer 14 after the access
Is X (j, 1) in each of the processor elements 2 to 10, such as X (1,1) in the first processor element 2 and X (2,1) in the second processor element 4.
(J = 1,5) is stored. At the same time, each of the processor elements 2 to 10 stores the variable address 62 in the variable address register 36. As a result, the variable addresses from the first address generator 20 and the value of the variable address register 36 match in the processor elements 2 to 10 of all the second comparators 32.

Further, based on the result of the first comparator 30 in each of the processor elements 2 to 10, the processor element number 60 and the processor element number register from the first address generator 50 among all the processor elements 2 to 10 are used. Processor element 2 with a value of 34 or matching
(4 to 10) only use the data bus of the output buffer 14
Output to 56. In this case, processor element number 60
Is 1 and the data X of the first processor element 2
(1, 1) is output to the data bus 56.

Finally, all the processor elements 2 to 10 fetch the data X (1,1) into the input buffer 15. Then, as a feature of this embodiment, the third comparator 44 determines that the processor element number of the first-in first-out memory 40 matches the processor element number 60 from the first address generator 50 on the current address bus 54. The third comparator 44 outputs a coincidence signal only in the processor elements 2 to 10 that coincide with each other, and outputs the data X (1,1) to the second address generator 42. X by address
The data of C (i, 1) is also stored in the memory 13. At that time, the value of the second address generator 42 is updated only for the matching processor elements 2 to 10. 4 and 5, only the first and third processor elements 2 and 6 store data XC (i, 1) in the memory 13.

Next, the first address generator 50 changes the processor element number 60 to two. At this time, X (1,1), X (2,1), X (3,1), X (4,1) are output to the output buffers 14 of the respective processor elements 2 to 10 by the above-described operation.
1) and X (5,1) are fetched, and the second comparator 32 in each of the processor elements 2 to 10 always outputs a coincidence signal. Since the processor element number 60 matches only the second processor element 4, the second processor element 4 accesses the data X (2,2,
1) is output to the data bus 56. In this case, taking FIGS. 4 and 5 as examples, the second and fourth processor elements 4, 8 store the data XC (i, 2) in the memory 13.

This operation is similarly performed when the processor element number 60 in the first address generator 50 is changed to 3, 4, and 5. Therefore, each processor element 2 to 10 stores each row component of the vector X corresponding to the non-O component of the matrix A shown in FIG. 4, and the access time to the memory 13 is reduced as compared with the conventional example. As a result, the broadcast transfer can be performed 4/3 times faster than the conventional case.

Further, each of the processor elements 2 to 10 is provided with a first-in first-out memory 40 for storing a processor element number corresponding to a vector indicated by a list vector (see FIG. 5). Processor element number at address 54
60 and the matching processor elements 2 to 2
By taking in the data bus 56 only for the data 10, selective data taking-in at the time of broadcast transfer is performed. Then, in each of the processor elements 2 to 10, the parallel calculation of the product of the matrix A and the vector X shown in FIG. 4 is performed.

(Effect of the Invention) As described above, according to the first aspect of the present invention, the first address generator puts the address indicating the processor element number and the variable address on the combining means, and changes only the processor number. Since the broadcast transfer is performed, the memory access time can be reduced and the speed of the broadcast transfer can be increased where it is not necessary to access the memory for each data as in the related art.

According to the second aspect of the present invention, each processor element is provided with a first-in first-out memory for storing a processor element number corresponding to a vector indicated by a list vector. Since the processor element numbers on the linking means are compared with each other and the data on the linking means are fetched only when they match, it is possible to selectively fetch data at the time of broadcast transfer. As a result, the memory can be effectively used, and the calculation of the product of the sparse matrix and the vector can be performed at high speed.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a parallel processing system according to a first embodiment of the present invention, and FIG. 2 is a block diagram illustrating a parallel processing system according to a second embodiment of the present invention. FIG. 3 is a diagram showing data assigned to each processor element when obtaining a product of a matrix and a vector, FIG. 4 is a diagram showing data when obtaining a product of a sparse matrix and a vector, FIG.
The figure shows a state in which data of a sparse matrix using a list vector is compressed. FIG. 6 is a block diagram showing a conventional parallel processing system, and FIG. 7 is a diagram showing data used in the conventional system. 2,4,6,8,10 ... processor element, 12 ... processor, 13 ... memory, 14 ... output buffer, 15 ... input buffer, 16 ... address bus, 17 ... data bus, 30 ...
... first comparator, 32 ... second comparator, 34 ... processor element number register, 36 ... variable address register, 40 ... first-in first-out memory, 42 ... second address generator, 44 ... Third comparator 50, first address generator 52, control line 54, address bus 56
…… Data bus, 60 …… Processor element number, 62
... Variable address.

──────────────────────────────────────────────────続 き Continued on the front page (58) Field surveyed (Int.Cl. ⁶ , DB name) G06F 15/163 G06F 17/16 G06F 15/177

Claims (2)

(57) [Claims] A plurality of processor elements each having a processor and a memory for storing data for the processor to perform processing, and a connection for connecting the processor elements so that data can be mutually transferred between the processor elements. Means for generating a control signal indicating that a broadcast transfer is to be performed and a variable address corresponding to a transfer source processor element number and data in the broadcast transfer for transferring the same data to the plurality of processor elements. A parallel processing system including an address generator, wherein each of the processor elements includes: an output buffer that outputs data from the memory to the coupling unit; a processor element number from the first address generator; Processor element number Compared to,
A first comparator for outputting the result to the output buffer; storage means for updating and storing a variable address corresponding to data in the output buffer each time data in the output buffer changes; and a variable address in the storage means. And a variable address from the first address generator, and a second comparator for outputting the result to the output buffer; an input buffer for inputting the data loaded on the combining means; A second address generator for generating an address for writing buffer data to the memory. 2. The parallel processing system according to claim 1, wherein each processor element includes a first-in first-out memory storing a processor element number of a processor element that outputs necessary data among data broadcast-transmitted to the processor element; A third comparator for comparing the processor element number loaded on the coupling means with the processor element number of the first-in first-out memory and outputting the result to an input buffer and a second address generator; A parallel processing system characterized by the following.