JPH03105584A - Parallel data processing system - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Summary] Regarding parallel data processing methods that process data using a plurality of data processing units synchronously, ring systolic array methods and common bus coupled SIMD (Si
ngle Instruction Multi Da
ta) With the same hardware configuration as the combination method, it reduces the overhead due to data transfer, and is especially suitable for processing such as calculating the product of a rectangular matrix and a vector.
The purpose is to perform matrix operations or neurocomputer operations by making maximum use of the inherent degree of parallelism and obtaining a favorable number effect. , a plurality of trays each having a first input and an output and each holding and transmitting data,
Shifting means comprising: all or part of said trays each having a second output connected to a first input of said data processing unit; and said first input and output of said connected trays being connected. By synchronously performing data transfer on the shifting means, data transfer between the tray and the data processing unit, and data processing by the data processing unit, matrix calculations or neurocomputer calculations are performed. Configure it to do so.

[Industrial application field]

The present invention relates to a parallel data processing system, and more particularly to a parallel data processing system that processes data using a plurality of data processing units synchronously.

In recent years, with the expansion of the fields of application of data processing in systems such as electronic computers and digital signal processing devices, the amount of data being processed has become enormous.Especially in fields such as image processing and audio processing, high-speed data processing is required. Therefore, it is important to utilize parallelism in data processing, in which multiple data processing units are used synchronously to process data.

-i has a number-of-units effect, which is an important concept in processing using a plurality of processing units. This means that the data processing speed can be improved in proportion to the number of data processing units prepared, but in parallel processing systems, it is very important to obtain a favorable number effect.

The main reason for the deterioration of the number-of-units effect is that, apart from the limitation due to the parallelism of the problem itself, the time required for data transfer associated with data processing is added to the time required for original data processing, which reduces the total processing time. It lies in being postponed. Therefore, it is effective to make full use of the capacity of the data transmission path to improve the number of devices, but this is difficult. However, if the processing is regular, this regularity can be used to improve the number of devices. It is possible to raise it.

The data is arranged in a systolic array, that is, data is flowed cyclically, and an operation is performed when two pieces of data are aligned in the flow. Parallel processing that takes advantage of the regularity of processing is the systolic array method. Among these, the one-dimensional systolic array method called the ring cyst link array method uses multiple data processing units synchronously. It is a parallel data processing method that processes systolic data and is relatively easy to implement.

Examples of regular processing include matrix operations based on inner product operations of vectors and parallel processing that outputs output via nonlinear functions in neural network product-sum operations.

[Conventional technology]

FIG. 11(A) is a diagram showing the principle configuration of a conventional common bus coupling type parallel system. In the figure, 91 is a processor element, 4 is a memory, 93 is a common bus, 92 is a bus connected to the common bus, and 94 is an internal bus that connects each processor element and the memory 4 connected to it. . In this common bus-coupled parallel system, communication between processor elements (hereinafter referred to as PEs) is carried out via a common bus.
3. Since there is only one common bus number for a specific time zone, it is difficult to use the common bus. Communication must be synchronized across the common bus.

FIG. 11(B) is an operational flowchart of matrix-vector product using this common bus-coupled parallel method. Each PE multiplies data X from other PEs by Y in the internal register and adds the product to Y. Therefore, as shown in the flowchart, for the i-th PE, the contents of the internal register, that is, the value of Y■, are first set to 0. Then, repeat the following n times. That is, the common bus 93
When X is given to , the i-th PE multiplies the input from the bus 92 connected to the common bus by the input given from the memory 4 via the internal bus 94, and adds the product to Yi. Repeat this.

FIG. 12(A) is a diagram explaining the principle of the conventional ring systolic system. In the figure, 20 is a processor element (PE). Each PR is connected by a circular bus 22. Further, 21 is a memory that stores the coefficient WiJ. W,,,W,2... W33, etc. are elements of a coefficient matrix, and Wij is generally an ij component of the matrix.

This coefficient matrix W and vector x= (XI , X2 ,
When the operation of multiplying by X3) is performed using this ring systolic method, it is performed as follows.

FIG. 12(B) shows the i-th internal structure of the processor element. In the figure, 23 is a multiplier, 24 is an adder, 25 is an accumulator (ACC), and 21 is a register group for storing coefficient elements Wij. This register group is a so-called FIF○, and WiJ, that is, the element in the j-th column is about to be output as the coefficient for the i-th row of the coefficient matrix. This FIF○ circulates at the next clock output and is input again from the rear side via the bus 22. Therefore, as shown in the figure, W■,
..., Wi J-1 has already been circulated and stored at the rear.

On the other hand, each element of the vector is input via the bus 22. Currently, element X is being input. W,, XX, ten...+W+ are already in the accumulator 25.
The inner product result of J-I XXJ-1 is stored. This is now output from the accumulator 25 and input to one input of the adder 24.

The product of xj from the outside and Wij output from FIF○ is multiplied by the multiplier 23, the result is input to the other input of the adder 24, and the current contents of the accumulator 25 are added to the next clock. Same accumulator 2 with
It is added to 5. By repeating this, the inner product calculation of the i-th row vector of the coefficient matrix W and the X vector given from the outside is performed in W rows.
h) is for selecting whether to output the data Xi to the outside or take it inside and set it in the accumulator 25. When performing a matrix×vector product in such a PE, as shown in FIG. 12(A), PE-1 first multiplies Wll and X, and in the next clock period, Since W+2 is output from the memory 21, W12×X2 is calculated. Similarly, in the next clock, the product of w+i and x3 is executed, which causes the first column of the coefficient matrix to be ? is possible in PE-1. Also, the product of the second column and the vector is performed in PE-2.

That is, multiply W22 by X2, and in the next clock period,
Multiply W2ff by X3, and in the next clock period W2
1 and X+ returned cyclically will be multiplied. Similarly, the product of the third row and the vector is W33 and X3
This can be achieved by multiplying W31 by the circulating X, and multiplying W3 by the circulating and returning X2 to perform an inner product operation. Therefore, in this operation, the product of Wll and XI, and W2■ and X2, W33
The product of and x3 can be performed simultaneously. However, as shown in the figure, in order to achieve this simultaneity, the arrangement of the elements of the coefficient matrix is distorted. In such a ring systolic array method, by synchronizing data transfer between each PE and data processing at each PB, the data transfer path can be used effectively, thus achieving a good number of units. be able to.

FIG. 12(C) shows a multi-stage combination of the ring systolic structure shown in FIG. 12(A), and this structure makes it possible to perform the product of continuous matrices and vectors. Since such a systolic array method performs regular processing, it is possible to make full use of the capacity of the data transmission path, and therefore the number of devices can be improved.

[Problem to be solved by the invention]

In the conventional common bus coupling parallel system as shown in FIG. 11(A), processing elements, namely PE
Since the connection between them is through a common bus, only one piece of data can be transferred at a time. Also, coupling via a common bus requires synchronization across the common bus. Therefore, in the conventional common bus coupling type parallel system, there is a problem that there are few types of processing that can obtain a good number of units effect, and furthermore, coupling by a common bus causes the common bus to become longer as the number of PEs to be coupled increases. , the difficulty of synchronizing across a common bus, and
The problem arose that it was not suitable for large-scale parallelism. In addition, in the conventional ring systolic array system as shown in Fig. 12, the effect of the number of units can be obtained by synchronously executing data transfer between each PE and data processing in the PE. Then, it is necessary to match the timing of data transfer between each PE and the timing of data processing between each PE. In addition, in this method, if the optimal numbers of data processing units and data holding units are not equal, such as when calculating the product of a rectangular matrix and a vector, PEs that are not involved in actual data processing
In other words, there is a problem that the number of PEs to play increases, and the number effect worsens. In other words, there is a strong correspondence between the problem of efficient solving and the circuit configuration, and if the size of the problem differs from the optimal value, the number effect will worsen. Conversely, the problem of obtaining a good number of units effect has been identified, and it cannot be applied to a wide range of processing, lacks flexibility or versatility, and as a result, high-speed data that can be applied to a somewhat wide range of processing has been identified. This makes it difficult to implement a processing system.

The present invention is applicable to a ring systolic array method or a common bus-coupled type SIMD (Single Instrument
With a hardware configuration comparable to that of the combination method (MultiData), it reduces the overhead caused by data transfer, and allows maximum use of the original degree of parallelism, especially for processing such as calculating the product of a rectangular matrix and a vector. The purpose is to perform matrix calculations or neurocomputer calculations by obtaining a good number of units effect in this manner.

[Means to solve the problem]

FIG. 1 is a diagram explaining the principle of the present invention. In the figure, 1 is a data processing unit, 2 is a tray that holds and transfers data, 3 is a shift register formed by interconnecting each tray, 11 is the first input of the data processing unit,
12 is the second input of the data processing unit, 21 is the first input of the tray, 22 is the first output of the tray, and 23 is the second output of the tray 2.

Data processing unit 1 processes data and tray 2
performs a transfer operation, leaving the shift register 3 free and performing a cyclic shift of data. In the present invention, when calculating the product of an mxn matrix 8 and a vector The product can be performed using m data processing units and n trays with a processing time proportional to n, and therefore a good number effect can be obtained. That is, as shown in FIG. 1(A), m data processing units 1 each have two inputs and perform a multiplication function between the inputs and an accumulation function of the multiplication results, that is, an inner product operation, and n In a structure consisting of two trays 2, if the cumulative register in the unit is Y, the data processing unit multiplies the input from 11 and the input from 12, adds the product to the cumulative Y, and then,
Shift the elements of vector X between adjacent trays in shift register 3. By repeating this operation n times, the multiplication of the m×n matrix A by the n-dimensional vector can be performed using m data processing units in a processing time proportional to n. That is, unlike the conventional system, the present invention separates the data processing unit 1 and the tray 2 having a data holding function, so that even if m and n are different from each other, processing for synchronizing the timing can be performed. It is possible to obtain a good number of units without the need for Furthermore, in the present invention, the data transfer between the trays 2 and the data processing by the data processing unit 1 are performed simultaneously in parallel, so that the data transfer time is generally shorter than the time taken by the data processing unit for data processing. Therefore, by hiding the data transfer time behind the data processing time, it is essentially possible to reduce the processing time to zero. This allows matrix calculations or neurocomputer calculations to be performed.

[For production]

By separating the data processing unit and the tray with data holding function, the number of data processing units m
Regardless of whether and the number of trays n are the same or different,
The product of the nXm matrix A and the vector X with n elements can be performed by data transfer and simultaneous parallel data processing.

〔Example〕

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1(B) is an operation flowchart of the system shown in FIG. 1(A) which is a diagram of the principle configuration of the present invention. As shown in FIG. 1(A), in the present invention, a data processing unit 1 and a tray 2 having a data holding function are separated, and the trays are connected between adjacent trays for circular connection, thereby creating a system linked to the system. It consists of When the number of data processing units is n and the number of trays is m, when calculating the product of mxn matrix A and vector
) The operation is shown in the flowchart.

Set Xi in the i-th position of tray 2. The value of Ys is O
Make it. That is, the value of the accumulation register in the i-th data processing unit is initialized. The i-th processing unit 1N multiplies the input from 11< by the input from 121, and adds the product to the accumulator Ys. Then, shift register 3 is shifted. This inner product and shift operation are n
Repeat times.

In this process, the product of the rectangular matrix A and the vector term is formed. In this case, data transfer between trays and data processing in the data processing unit are simultaneous and parallel processes.

FIG. 1(C) is a conceptual diagram of the operation of the system of the present invention.

In the figure, it is assumed that data X+ to xn in tray 2 are elements of vector X, and the number thereof is n.

Furthermore, there are m data processing units, each of which has an accumulator Y+, Yz, . . . , Y. The elements of the m×n rectangular matrix are from A■ to A. There are m×n pieces up to. 1 of the data processing unit. is the first row of the coefficient matrix, Az. AH, ...+AIn is 12 synchronously
It is input from the input bus No. 1. Further, the data processing unit 12 is sequentially given A22, A23, . . . A 2 1 at each timing of the systolic operation. Also, what about the data processing unit 1lI? ffilW+ A
ll ll+. 1+'...r All I1-1 is given synchronously.

FIG. 1(D) is a timing chart of the operation of FIG. 1(C). The operations from time T+ to Tn are shown in the respective diagrams in FIG. 1(C) and times T,, T2, . . . in FIG. 1(D).
・,T,, correspond. At time timing T1, as shown in FIG. 1(C), 21.2 of the tray is
2, ..., 2n has X+ , Xz , X ■, ...
・．． There is a unit} 11, 12, ..., l
m has coefficient matrix elements All, ADZ,
...61 has been input. Therefore, at this timing, the data processing unit calculates the product of A1 and the data X1 on the tray 21, and calculates the product of X2 on the tray 22 corresponding to the data processing unit and A2 given from the memory.
Find the product of 2 and 6 in the same way, and for tray 2m, A1 and X. Find the product of This timing is performed at the timing T1 in FIG. 1(D). In other words, in the synchronous clock for calculating the sum of products, bus 1h has X1, bus 121 has A■, bus 112 has X2, 122
has A22, 113 has X3, 123 has A33, 11. has XII, and 12 has A all1. Therefore, the inner product calculation is performed as shown in the diagram at T and time in FIG. 1(C). Since the value of the accumulator Y is 0 at this time, the value multiplied by O is added to the inner product result. When the product-sum operation is completed, a shift operation begins. That is, as shown in FIG. 1(D), a shift operation occurs between T1 and T2, and data is shifted between adjacent trays. That is, a left shift is performed in this case. Then, the process moves to timing T2 in FIG. 1(C). Similarly, in the operation timing shown in FIG. 1 (CD), the time area is the sum of products of T2. Then, since they have been shifted, X2 is stored in tray 21, X3 is stored in tray 22, and x-1 is stored in tray 2m, and the elements of the coefficient matrix are also stored in trays 1, 2, . −・'、
AI2, A23, and Am mo+ are input to m, respectively. This is also shown in the timing T2 of FIG. 1(D) for each data on the bus. Therefore, in the timing of T2, A12? The product with X2 is taken and the sum with the previous accumulator Y is determined. Therefore, unit 1. In , A 1 . found at TI. and X,
The sum of the product of A I Z and X2 obtained at T2 is calculated, and the result is stored in the accumulator. Similarly, in unit 1z, the previous result A22XX
The result of 2+A23XX3 is stored in the accumulator. Unit l-1. The same applies to . Then, it shifts again and moves to timing T3. Tray 1 has X3, tray 2
X4 for tray m, X4 for tray m. (2) X2 enters tray n, and the inner product calculation as shown in the diagram at time T3 in FIG. 1(C) is executed.

In the time period T3 of the operation timing of FIG. 1(D), the symbols of the inputs to be entered into the data processing unit are shown. As such calculations proceed, the time area T is reached. If the process is performed up to the time zone T in FIG. 1(C).

As shown in , when A + nX
The sum of the products of A I3 X X 3 etc. found in step 3 is found,
Since the inner product result up to 'rn-+ is stored in the accumulator Y, A, fiX×n are added to the result and 1
The inner product of the row and the vector X is performed. Similarly, in tray 2, the inner product calculation of the row vector of the second row of matrix 8 and vector , is executed. Therefore, by performing processing in such a time series, multiplication of an m×n rectangular matrix by an n-dimensional vector can be performed using m data processing units in a processing time proportional to n. Therefore, it is possible to obtain a good effect on the number of units. The important thing here is that
The data processing unit that processes data and the tray that has the data holding function are separated, and the number of each corresponds to the rows and columns of a rectangular matrix, so that even if their dimensions are different, the time series operation is synchronous. This is possible. Note that even if n is smaller than m, the processing time will be extended by using m trays 2, that is, it will be proportional to m.
Effective processing of the number of units is possible.

FIG. 2(A) is a detailed block diagram of the structure of FIG. 1,
This is to find the product V (number of elements m) of a matrix A of m×n (n≧m≧1) and a vector X of n elements. In the figure, the same components as those shown in FIG.
2b is a data transfer circuit for tray 2, such as a bus driver, and 2C is a control means for tray 2, such as a logic circuit. 4 is a storage device which is part of the means for supplying data to the data processing unit 1 and at the same time is part of the means for controlling the data processing unit 1, such as RAM (Rangular Access Memory). 5 is a means for synchronizing the data processing unit 1 and the tray 2, 5a is a clock generation circuit, for example, a crystal oscillation circuit, and 5b is a clock distribution circuit, for example, from a buffer circuit. configured.

The operation of this embodiment is almost the same as the operation explained in the principle diagram of the present invention.

FIG. 2(B) is an operation flowchart of the system of the present invention shown in FIG. 2(A). As shown in FIG. 2(A), in the present invention, a data processing unit 1 and a tray 2 having a data holding function are separated, and the trays are connected between adjacent trays for circular connection, thereby creating a systolic system. It consists of When the number of data processing units is m and the number of trays is n, when calculating the product of mxn matrix A and vector . Set Xi on tray 2i. Set the YiO value to O. That is, the value of the accumulation register in the i-th data processing unit is initialized. The i-th processing unit II multiplies the input from 11, by the input from 12i, and the product is added to the accumulator Yi.
Add to. Then, shift register 3 is shifted. This inner product and shift operation is repeated n times. In this process, the product of the rectangular matrix A and the vector A is determined.

? In this case, data transfer between trays and data processing in the data processing unit are simultaneous and parallel processes.

FIG. 2(C) is a conceptual diagram of the operation of the system of the present invention.

In the figure, it is assumed that data X+ to Xfl in tray 2 are elements of vector X, and the number thereof is n.

Furthermore, there are m data processing units, each of which has an accumulator Y+, Y2, . . . , Y. There is. The elements of the m×n rectangular matrix are m×n from All to AllIn.
Individuals exist. The data processing unit 11 has the first row of the coefficient matrix A H H, A12,...+Al11.
are input synchronously from the 12+ input buses. Moreover, the data processing unit 12 has A22% A23,...A2
1 is given in turn at each timing of the systolic operation. The data processing unit 1 also includes A, . ,A■
．． ,,..., An+ +a-l are given synchronously.

FIG. 2(D) is a timing chart of the operation of FIG. 2(C). From time T1 to T. The operation of each diagram in Figure 1 (C) and the time in Figure 1 CD)? , , 'rz ,
..., Tn correspond to each other. time timing T
, as shown in FIG. 2(C), the trays 21, 22, . . . , 2n have XI, x2, X.
, − − ・, Xfl is ant, unit ll, 12,
..., Im respectively have coefficient matrix elements A++. A
zz. A■ has been input.

Therefore, in this timing, the data processing unit 1
The product of AII of 1 and the data XI of tray 21 is calculated, and in the data processing unit 12,
and A22 given from memory, and similarly, for tray m, the product of 80 and X1 is found. This timing is performed at the timing of TI in FIG. 2(D). That is, in the synchronous clock for calculating the sum of products, bus 11I has X+, bus 12. A. 1, bus 112 has X2, 1 2z 6: has A22, 1
lx d has X3, 12:l has A33, 111
xm for 121, A. is on it. Therefore, the second
The inner product calculation is performed as shown in the diagram at the TI time in Figure (C). Since the value of the accumulator Y is 0 at this time, the value multiplied by O is added to the inner product result. When the product-sum operation is completed, a shift operation begins. That is, as shown in FIG. 2(D), the shift operation is between T and T2,
Data is shifted between adjacent trays. That is, a left shift is performed in this case. Then, the process moves to timing T2 in FIG. 2(C). Similarly, the operation timing shown in FIG. 2(D) corresponds to the time area of the sum of products of T2.

Then, since it has been shifted, tray 21 has X2, tray 22 has X3, and tray 2m has X. l is stored, and the elements of the coefficient matrix are also stored in trays 21, 22, -
, 2m respectively have A + z , A 2 3 ,
A. 11141 is input. This is T in Figure 2 (CD)
Also at timing 2, the data on the bus is shown. Therefore, at timing T2, AI
2 is multiplied by x2 and summed with the previous accumulator Y. Therefore, in unit 1l, A. A 1 found at the product of and X1 and Tz
The product of 2 and X2 is summed and the result is stored in an accumulator. Similarly? In unit 12, the previous result, A 22 X X Z A23XX3, is stored in the accumulator. The same applies to unit 1ffi. Then, it shifts again and moves to timing ξ. X3 is placed in tray 21, X4 is placed in tray 22, X2 is placed in tray 2m, and x2 is placed in tray 2n, and the inner product calculation as shown in the diagram at time T2 in FIG. 2(C) is executed. .

Time zone T3 in the operation timing of FIG. 2(D)
In , the symbols of the inputs to be entered into the data processing unit are shown. As this calculation progresses, the time area T0
If the process is performed up to the time zone T in FIG. 2(C). When AIfl××n is added to the value with the previous accumulator as shown in
In tray 1, At+XX+ % T, calculated by T.
A12×Xz at z, A H 3 X found at Tz
The sum of the products of X 3 etc. is found, T, . ．． Since the inner product results up to I are stored in the accumulator Y,
．． nXXfl is added and the inner product of the I-th row of the 8th matrix and the vector X is performed.

Similarly, in the tray 2, the inner product calculation of the second row vector of the matrix A and the vector is executed. Therefore, by performing processing in such a time series, multiplication of an m×nO rectangular matrix by an n-dimensional vector can be performed using m data processing units in a processing time proportional to n. Therefore, it is possible to obtain a good effect on the number of units.

FIG. 3 is an explanatory diagram of a second embodiment of the present invention. m×n
1 is a diagram illustrating the structure of a systolic system for operations when the product of matrix A of 1 and vector 1 of n elements is subsequently multiplied by matrix B of kXm from the left. Components in FIG. 3(A) that are the same as those shown in FIG. 1 are indicated by the same symbols. That is, 1a is a processing device of the data processing unit 1, for example, a digital signal processor. 2
2b is a data transfer circuit for tray 2, such as a bus driver, and 2C is a control means for tray 2, such as a logic circuit. It consists of Reference numeral 4 denotes a storage device which is part of the means for supplying data to the data processing unit 1 and at the same time is part of the means for controlling the data processing unit 1, and is composed of, for example, a RAM (random access memory). . 5 is a means for synchronizing the data processing unit 1 and the tray 2, 5a inside is a clock generation circuit, for example, a crystal oscillation circuit, and 5b is a clock distribution circuit, for example, from a buffer circuit to configured.

6 is a selection circuit that selects between systically returned data, data to be input into the tray, and external data;
is a selection circuit that bypasses systolic data from the middle.

This embodiment is exactly the same as the first embodiment up to the point where the intermediate result Ax is obtained, and from a state in which each element of the intermediate result Ax has been obtained in each data processing unit, (a) the intermediate result is transferred to the tray. (b) Turn on the bias selection circuit 7 and set the length of the shift register to m.
(C) From then on, in the first embodiment of the present invention, if matrix A is changed to matrix B, n is changed to m, and m is changed to k, the operation will be exactly the same.

FIG. 3(B) is an operation flowchart of the second embodiment, FIG. 3(C) is an operation overview diagram of the second practical example, and FIG. 3(D)
is an operation time chart of the second embodiment.

First, the product of m×n matrix A and vector X with n elements,
Then, when multiplying the matrix B of kXm from the left, Fig. 3 (
The operation is shown in the flowchart B). Set the Xi on the tray 21. Set the YiO value to O. That is, the value of the accumulation register in the i-th data processing unit is initialized. The i-th processing unit 1l multiplies the input from lit by the input of 121, and adds the product to the accumulator Yi. Then, shift register 3 is shifted. This inner product and shift operation is repeated n@. In this process, the product of rectangular matrix A and vector X is expressed.

Next, change the length of the shift register to m and Y1? Transfer to tray 21. And Z, (i=1,...,k
) to O. Next, in order to multiply the B matrix, first, the inputs from the i-th processing units ll and lit are multiplied by the input of 12t, and the product is added to the accumulator Zl. Then, the 20 inner product and shift operation for shifting the shift register 3 are repeated k times.

FIG. 3(C) is a conceptual diagram of the above operation. In the figure, it is assumed that data X1 to XI in tray 2 are true elements of a vector, and the number thereof is n.

In addition, m data processing units are initially effective, and each of them has an accumulator Y+, Yz, . . . , Y. Suppose there is. First, there are m×n elements of an m×n rectangular matrix A, from A■ to A■. data processing unit h
is the first row of the grandchild matrix, A++. Adz,
H + +, AIn are synchronously input from the input bus 12. Moreover, the data processing unit 12 is A 2 2
, A 2 3 , . . . + All are given in turn at each timing of the systolic operation. The data processing unit 1■ also includes A, . , A. , ■Kado. ...? ．． ■1 is given synchronously.

FIG. 3(D) is a timing chart of the operation of FIG. 3(C). Time TI to T. The operations are shown in the respective diagrams in FIG. 3(C) and at times T+, Tz, and Tz in FIG. 3(D).
..., Tn correspond to each other. At time timing T1, as shown in FIG. 3(C), one of the trays
．． 2. ... n has X+, Xz, ...+Xk+
..., Xll, and units 1, 2, ...,
k, . . . , m are coefficient matrix elements All, A, respectively.
2■,..., Ahh. ..., A,, are input. Therefore, at this timing, the data processing unit processes the A-th disk and the disk X of tray 1.
, and in the data processing unit 2, the product of X2 in tray 2 and A2■ given from the memory is found.Similarly, in tray k, the product of Akk and X, is found, and in tray m In A. Find the product of and Xm.

This timing is performed at the timing T1 in FIG. 3(D). In other words, in the synchronous clock that calculates the sum of products, xl? Yes, there is A+ for bus 12+.
+, bus llz has X2, 122 has Azz,
1 1 k has Xh, 12k has Akk, 11
．． has Xllll on it, and A1■ on l21I. Therefore, as shown in the diagram at T+time in FIG. 3(C), an inner product calculation is performed. Since the value of the accumulator Y is 0 at this time, the value multiplied by O is added to the inner product result.

When the product-sum operation is completed, a shift operation begins. That is, as shown in FIG. 3(D), a shift operation is performed between T+ and T2, and data is shifted between adjacent trays. That is, a left shift is performed in this case. Then, the process moves to tying T2 in FIG. 3(C). Third
Similarly, the operation timing shown in FIG. 3D also corresponds to the time area of the sum of products of T2. Then, since they have been shifted, X2 is stored in tray 1, X3 is stored in tray 2, XIl+1% is stored in tray k, and X1.1 is stored in tray m, and the elements of the coefficient matrix are also stored in trays 1, 2, etc.・, k, ..., m each have AI2+ A23+ ...Akk+heavy, ...
- AI111141 is input. This is Figure 3 (D)
The data on the bus is also shown in the timing T2. Therefore, at the timing of T2, A
, 2 and x2, and the sum with the previous accumulator Y is determined. Therefore, for tray 1, the product of A 1 1 and X, found at T1, and A1 found at T2
The product of 2 and x2 is summed and the result is stored in the accumulator. Similarly, in tray 2, the previous result A
The result of 22XX2 +A23XX3 is stored in the accumulator. The same applies to trays k and m. Then, it shifts again and moves to timing T3. X3 for tray 1, X4 for tray 2, Xw k42 for tray k. ．．
}Xllmh2 is entered into ray m, and X2 is entered into tray n, and an inner product calculation as shown in the diagram at time T3 in FIG. 3(C) is executed.

When such calculations proceed until the time area Tn is reached, the time area T. shown in FIG. 3(C) is reached. A + n X as shown in
X (Tray 1 when @ is added to the value with the previous accumulator
In this case, A11XX1-. determined by T+. A 1 z X X 2 at Tz, Alkx determined at T k
The sum of products such as Xk is calculated, and the inner product results up to Tn-+ are stored in the accumulator Y, so A, . x×n
is added, and the inner product of the first row of matrix A and vector X is performed. Similarly, in tray 2, the inner product calculation of the row vector of the second row of matrix 8 and vectors is performed in n clock cycles, and similarly, the inner product of the row vector of the k-th row and the vector is calculated in data processing unit 1k. executed.

The effective number of data processing units is k, and the effective number of trays is m.
In this case, matrix B of kXm and vector y of m elements
The operation is to find the product of . Set Yt on tray 2 h. Set the ZiO value to O. That is, the value of the accumulation register in the i-th data processing unit is initialized.

The i-th processing unit h multiplies the input from 1h by the input of 121, and adds the product to the accumulator Zi. Then, shift register 3 is shifted.

This inner product and shift operation is repeated m@. In this process, rectangular matrix B and vector! The product of is expressed as

? In Figure 3 (C), data Y1 to Ym in tray 2
is an element of vector y, and the number of elements is m. Further, the effective number of data processing units is k, and each of them has an accumulator Zl, Z2, . . . Zk. The old kXm rectangular matrix has kXm elements from B++ to Bh. The first row of the coefficient matrix B, Bll, B+z, . . . +BI+m, is synchronously input to the data processing unit h from the 121 input bus. Moreover, the data processing unit lz is B2■, B23, ..., B2
1 is given in turn at each timing of the systolic operation. In addition, the data processing unit l-1 has Bkk. B
k k. 1,...Bk k-1 are given synchronously.

Similar symbols are used in the timing chart of FIG. 3(D) and the operation of FIG. 3(C'). Time T n +
The operations from 1 to T n + @ + l correspond to the respective diagrams in FIG. 3(C) and the times in FIG. 3(D).

Time timing T. In +I, as shown in FIG. 3(C), trays I, 2, ..., m have Y+, Y
2,...,Y. is moved and unit 1,? 、・
..., k are the elements Bz, B2■, of the coefficient matrix B, respectively.
..., Bkk are input. next timing'r
At n*z, the data processing unit 1 calculates the product of Bl+ and the data Y1 of the tray ■, and the data processing unit 2 calculates the product of Y2 in the tray 2 and B2■ given from the memory, and similarly the unit In I-k, the product of Bkk and Yk is calculated. This timing is the fifth
Tn in figure (d). This is done at the timing of 2. In other words, in the synchronous clock that calculates the sum of products, bus 11+ has Y1, bus 12+ has B, and bus 112
Y2 for 122, B22 for 1l3, Y3, 123 for 1l3
has B33, 11k has Yk, 12k has Bkk
is on it. Therefore, T, l in FIG. 3(C). The inner product operation is performed as shown in the diagram in FIG. Since the value of the accumulator Z is O at this time, the value multiplied by O is added to the inner product result. When the product-sum operation is completed, a shift operation begins.

That is, Tn as shown in the diagram of FIG. 3(D). 2 and T. +3 is a shift operation, and data is shifted between adjacent trays. will be held. That is, a left shift is performed in this case. Then, the process moves to the tying T n + 3 in FIG. 3(C). Similarly, the operation timing shown in FIG. 3(D) corresponds to the time area of the sum of products of T n +3.

Then, since they have been shifted, Y2 is stored in tray 1, Y3 is stored in tray 2, and Y k + + is stored in tray k, and the elements of coefficient matrix B are also stored in trays 1, 2, .・・・
・．． B1■, B23, ...+ for k, respectively
Bk k+1 is input. This is T in Figure 3 (D)
Data on the bus is also shown at timing n+3. Therefore, at the timing of T n + 3, BI2 is multiplied by Y2, and the sum with the previous accumulator Z is obtained. Therefore, in unit 1, T
7. B. found in 2. The product of Y+ and T n
* The sum of the product of B1 and Y2 obtained in step 3 is obtained and the result is stored in the accumulator Z. Similarly, in unit 2, the previous result B22XY2 +Bz
The result of 3×Y3 is stored in accumulator Z. The same applies to tray k. Then shift again, timing T
Move to n+4.

As such calculations proceed, the time area T is reached. *If you proceed up to @+l, you will get the time area T n + I1 in Figure 3(C). B IIIX Y. as shown directly. When N is added to the value of the previous accumulator Z, in unit 1 T, . BX Y + −. B at T n + 2
BX Y2 , the sum of the products of B , ,
Since it is stored in , the result is BIm X Y y
3 is added and the inner product of the first row of matrix B and vector y is performed. Similarly, in unit 2, an inner product operation is performed between the row vector of the second row of matrix B and vector l, and similarly, an inner product operation of the row vector of the k-th row and vector l is performed in data processing unit 1k. Therefore, by performing the processing in such a time series, it becomes possible to perform the processing on the kXm rectangular matrix B in a processing time proportional to m, and therefore it becomes possible to obtain a good effect on the number of units.

In this embodiment, it is important that the length of the shift register 3 can be changed and that intermediate results can be written to the tray 2 and processed as new data. If the length of the shift register 3 cannot be changed, it will take n units of time to cycle through all the data. Additionally, by being able to process intermediate results as new data, it is possible to perform a wider range of processing than with the ring systolic array method using small-scale hardware. Furthermore, it is important that the time required for writing is short and constant.

FIG. 4 is an explanatory diagram of a third embodiment of the present invention.

In this system, the transposed matrix AT of the mxn rectangular matrix A,
That is, it calculates the product of an (nXm) matrix and a vector X having m elements. In the figure, the same parts as shown in FIG. 1 are indicated by the same symbols.

When calculating the product of the transposed matrix AT and hector The data on the shift register 3 is circulated while being accumulated on the data holding circuit 2a.

FIG. 4(A) is a detailed block diagram of the structure of the third embodiment, and the product 1 (number of elements n) of the matrix AT of nXm (n≧m≧1) and the vector X of m elements is calculated. It is something. In the figure, the same components as those shown in FIG. 2b is a data transfer circuit for the tray 2, which is composed of, for example, a bus driver; 2C is a control means for the tray 2, which is composed of, for example, a logic circuit;
5 is a storage device which is part of the means for supplying data to the data processing unit 1 and at the same time is part of the means for controlling the data processing unit 1, and is composed of, for example, a RAM (random access memory); It is a means for synchronizing the processing unit 1 and the tray 2, and 5a is a clock generation circuit, which is composed of, for example, a crystal oscillation circuit.
5b is a clock distribution circuit, which is composed of, for example, a buffer circuit.

FIG. 4(B) is an operation flowchart of the third embodiment. Sesoto X+ into unit It (i=1, . . . m). Yi (i = 1,...,n)
Set the value to O. Each unit 11 multiplies A J ( and
．． Go to n and shift.

Repeat this operation for j=1,...,m. The multiplication of a transposed matrix and a vector can be calculated by leaving each partial row vector of the matrix 8 stored in the storage device 4 unchanged, and this is done using backpropagation, which is one of the neural network learning algorithms described later. This is extremely important in execution. Also, the amount of network is of order n
That's all.

It is a ring network. Furthermore, since the data transfer time is hidden by the processing time, there is no overhead to the transfer time. Moreover, it is a SIMD method.

FIG. 4(C) is a schematic diagram of the operation of the third embodiment. Unit h is given sequentially from A11 to A1L,l. Unit 12 has A22 to A23. ?・,A2.
is given, and the k-th unit is given Ah
h, Ak kl + .... Give Ah + in order. The mth is A■, Am m++ +
...A. ．． 1 in order. Further, those circulating on the tray are Y1 to Yn.

FIG. 4(D) is an operation time chart of the third embodiment. Time zone MT. The data on the bus from T1 to Tn are shown, which respectively correspond to the diagram from time period T1 to Tn in FIG. 6(C).

In time area T+, all from Y1 to Y7 are O.
It is. Mo and A. The product of and X1 is calculated in unit 11 and added to Y+. At the same time, A22 and X
2 is added to Y2, Akk×Xk is added to Yk, A×X. is Y. It is added to. Then, when the shift operation starts, timing T2 occurs. In other words, the Y data circulates. In the first unit, A H 2 X X 1 is calculated and added to Y2, which is T
Since the value of A 22 X X 2 found in I is stored, it is added to this. Therefore, A22X
The result of X2 +AI2XXI is Y2. Similarly, in unit 2, A 23 X X is added to the previous result of Y3.
2 is added.

Akk for Y k* 1 in the kth unit. 1
×X, is added. Also, the m-th unit has Y.
. AIls in 1. Ixx. will be added.

When Y data is circulated in this way, the mth time area Tn
For example, in the first unit 1, A 1 nX X 1 is added to Yn determined up to that point. Further, A 2 1 X X 2 is added to Y+. Looking at this as a whole, for example, the first element X+ of the vector demon is multiplied with A■ at T+, and A I I X X l is calculated. That is Y1
is stored in Also, the second element A21XX2 in the first row of transposed matrix 80 is actually the last clock cycle! tlI
Calculated at Tn. This is stored in the same Y. In addition, the product of A11, which is the last element in the first row of the transposed matrix A7, and X1 is shown in Figure 4 (C
) is calculated in the mth unit of clock period T n − v* * 2. In other words, is the product of A1 and X1 obtained by adding it to Y+? It will be done. The same applies to the second row of the transposed matrix A7, and the product of AI2 and X1 is calculated in unit 1 at the clock of T2. Further, A2.times.X2 is performed in the second unit of clock period T1. Then, Y2 is circulated again and the product is performed in the time area Tn-
T.I. It is 2. After that time period, a multiplication is performed and a shift operation is performed. In the time area Tfl, the value added to Y2 is the third unit, Y
The value added to 2 is A3■XX3. Therefore, T
7, the inner product of the second row of the transposed matrix AT and the vector X is calculated. Generally, for the kth unit, k
Since the data line from the th tray is llm, it is sufficient to follow the line 11k as shown in FIG. 4(D). That is, at T1, Y,
+AHXXm, Y k* r + A at Tz
h k+ +×χ,, Yk+z +A at T3
h k+2 Xh is calculated, and in 'rn-+ Y
k−■+Al k−z Xk is calculated, and the time domain Tn
In this case, Yk-1+Akk-I Xk is calculated. As a result, the product of the transposed matrix AT and the m-dimensional vector X is executed. That is, when calculating the product of transposed matrix A7 and vector The data is accumulated on the data holding circuit in tray 2 and circulated on the shift register. By this method, matrix A
When calculating the product of the transpose AT of matrix 8 and the vector true following the product Processing can be performed using each sub-row vector of matrix 8 stored in matrix 8 as is, that is, without transferring the sub-matrix of transposed matrix 80 to each data processing unit 1. This saves time and further reduces processing time.

FIG. 4(E) is a flowchart showing a detailed breakdown of the repeated portion of FIG. 4(B).

FIG. 5 is a diagram showing a fourth embodiment of the present invention. This embodiment is a diagram showing the structure of a neurocomputer using the present invention.

In this figure, the same parts as those shown in FIG. 4 are indicated by the same symbols. In the figure, 1a is a processing device of the data processing unit 1, which is composed of, for example, a digital signal processing sensor. Reference numeral 2a denotes a data holding circuit for the tray 2, which is composed of, for example, a latch circuit. 2b is a data transfer circuit for the tray 2, which is composed of, for example, a bus driver. Reference numeral 2c denotes a control means for the tray 2, which is composed of, for example, a logic circuit. A storage device 4 is part of the means for supplying data to the data processing unit 1 and is also part of the means for controlling the data processing unit 1. For example, it is composed of RAM. 5a is data processing unit 1
5a is a means for performing synchronized operation of the tray 2 and the tray 2, and 5a is constituted by a clock generation circuit, for example, a crystal oscillation circuit. 5b is a Cronk distribution circuit, which is composed of, for example, a buffer circuit. In addition, 101 is a sigmoid function unit that calculates a monotonically non-decreasing continuous function called a sigmoid function and its differential coefficient, and is realized by, for example, an approximate expression using a polynomial. l03 is a means for determining the end of learning, and for example, a host computer connected to each of the processing units 1 through a communication means and an output error calculated by each processing unit (2) is notified to the host computer through the communication means. and means for determining the end of learning based on the plurality of output error values and stopping the neurocomputer. Note that 102 is the entire neurocomputer.

FIG. 5(B) is an example diagram of a neuron model which is a basic element in processing calculations in the neurocomputer of the present invention. The neuron model has input X. ,XZ,
. . , X1 has a weight W as a synaptic connection. , W2, . A nonlinear function f is applied to this U to obtain an output Y. Here, as the nonlinear function f, an S-type sigmoid function as shown in the figure is generally used.

FIG. 5(C) is a conceptual diagram of a hierarchical neural network that uses a plurality of the neuron models shown in FIG. 5(D) to form a neurocomputer with a 3N structure of an input layer, an intermediate layer, and an output layer. The input layer of the IN-th is the input signal I+, I
Input z, ..., IN+11. In the intermediate layer of the second layer, each unit, that is, each neuron model, is connected to all the neuron models of the first layer, and the connecting branches thereof are synaptic connections, and are given weight values Wij. Similarly, each unit of the output layer of the third layer is connected to all of the neuron models of the intermediate layer. The output is output to the outside. In this neural network, during learning, the error between the teacher signal corresponding to the input pattern signal given to the input layer and the output signal of the output layer is calculated, and the error between the intermediate layer and the output layer is determined so that this difference is very small. This algorithm, which determines the weight between the two layers and the weight between the first layer and the second layer, is called the pack propagation law, that is, the backpropagation learning rule. When storing the weight values determined by the backpropagation learning rule and performing associative processing such as pattern recognition, if an incomplete pattern slightly deviated from the pattern to be recognized is given as input to the first layer, An output signal corresponding to the pattern is output from the output layer, and this signal is very similar to the teacher signal corresponding to the pattern given during learning. If the difference from the teacher signal is very small,
You have recognized that imperfect pattern.

The operation of this neural network can be realized engineeringly using the neurocomputer 102 shown in FIG. 5(A). In this embodiment, a three-layer network configuration as shown in FIG. 5(C) is used, but as explained below, this number of layers has no essential influence on the operation of this embodiment. In the figure, N(1) is the number of neurons in the first layer. In addition, since the output of each neuron in the first layer, that is, the input layer, is usually equal to the input, the actual processing is necessary.
Not good. FIG. 5(D) shows normal operation, that is, forward-looking processing when performing pattern recognition.

FIG. 5(D) is a forward processing flowchart of the fourth embodiment. In the forward processing, it is assumed that in the network shown in FIG. 5(C), the weighting coefficients on the connection branches between each layer are fixed. When the network of FIG. 5(C) is realized by the neurocomputer of FIG. 5(A), the following processing is performed. The basic operation of the forward movement is a process of multiplying the inputs with weights and taking the summation as U, and applying a nonlinear function to that U in the neuron model shown in FIG. 5(B). This will be done for each layer. Therefore, first, in step 70, the input data, that is, I
1 to ■8. , and set the data up to , into the shift register. Then, when the number of layers is represented by L, all the following processes are repeated for each layer. For example, if L is 3, then 3
Repeat times. The repeated layer is one layer of forward processing.

Then, the process ends. The forward processing of the IN portion is shown at the bottom. Now, if we focus on the middle layer, l is 2. In step 72, the length of the shift register is set to N(/2-1). That is, since f=2, N
(1), that is, the number of input layers. Step 73 is processing of the neuron model in the intermediate layer. The index j is varied from 1 to the number of units in the input layer N(1). Wij(f) is a weighting factor in the connection between the input layer and the hidden layer. That is, f=2. Y, (f
-1) is the output from the j-th unit of the input layer.

i means the i-th unit of the intermediate layer. The state Ui(2) of the i-th unit is calculated from the sum of the output Yj of the input layer, that is, the j-th Y, multiplied by the weight Wi. Proceeding to step 74, the i-th state Ui(2) of the intermediate layer is input to a nonlinear function, ie, a sigmoid function, and its output becomes Yi(2). That is, the calculation of the inner product in step 73 is performed within the unit shown in FIG. In step 75, for example, the output yi(2) of the i-th unit of the intermediate layer is output to the i-th tray. Then the process ends. The above forward processing is performed in the input layer, middle layer,
This will be done for the output layer. In this way, the forward processing of each layer is completed. In other words, the processing required to simulate a single neuron is the calculation shown in the equation shown in Figure 5 (B), which consists of the inner product calculation of the weight and the input vector, and the calculation of the sigmoid function value for the result of the calculation. Value calculation is performed by sigmoid function unit 101
This is realized by Therefore, as shown in FIG. 5(C), the processing of one layer in the network is to perform calculations for a single neuron for all neurons in that layer.

Therefore, the inner product operation is a matrix W (I!.) = (WIJ
(ffi): vector tJ (f) = (ui (f)), which is the product of l and the vector x (j2) one (XJ (I!.)), which is a list of the inputs to that layer, and this is the result of the present invention. This can be executed by the method described in the third embodiment. Also, sigmoid function operations are performed using each sigmoid function unit}
101 is done by inputting each element of the product vector, ut(p), and outputting the corresponding function value Y1(f)=f (Ut(f)). Successive layers i.e.
l+1) layer exists, each function value output Yi(
/! ) is written in each tray, and in the processing of the (f+1)th layer, this is input and the above process is repeated.

Next, a case will be described in which a learning operation, that is, a backblopage algorithm is executed using the neurocomputer shown in FIG. 5(A).

FIG. 5(E) is a learning process flowchart of the fourth embodiment. Learning in a neurocomputer involves modifying the weights of each neuron until the network satisfies the desired input-output relationship. The learning method is to prepare a plurality of pairs of a desired input signal vector and a teacher signal vector, that is, for a set of teacher signals, and select one from them.
A pair is selected, the input signal I, is input to the learning target network, and the output of the network for the input is compared with the correct output signal, that is, the teacher signal ○ corresponding to the input signal. This difference is called an error, but is it based on that error and the values of the input and output signals at this time? , which will modify the weight of each neuron.

This process is repeated until learning converges over all elements in the set of teacher signals. That is, the number of input patterns are all stored as weight values in a distributed manner. In this weight correction process called backward processing, the error obtained in the output layer is propagated toward the input layer in the opposite direction to the normal signal flow direction, while being modified along the way. This is the backpropagation algorithm.

First, the error D is defined recursively as follows. Di
(I!.) is the error propagated backward from the i-th neuron of the first layer, and L is the number of layers of the network.

Di (L) 1V (Ui (L)) (Yi (L)
)-Opi) (Final layer) (1) Di
(42-1)=f' (Ui (42-1))Σ,8
1,■j,Wj i (j2) Dj (A) (A=2
, ・ ・ , L) (2) (i=1,
・ ・ ・, N (f)) where f' (U)
is the differential coefficient r' of the sigmoid function f (X) with respect to X
It is the value of (x) when X=U, for example, f (X) = tanhX (
3), then f' (X) = d (tanhX) /d X=
1-tanh2X=1-f2 (X)
(4), so r' (Ui)=1-f2 (Ui)=1-Yi''(5
).

Based on this Di(!:Yi), the weights are updated as follows. Basically, the following formula is used. Here, η is the increment width for updating the weights, and if it is small, the convergence will converge to stable learning. It is a variable parameter that has the property that it becomes slow, and if it is too large, it will not converge.

Wi j (j2) (t”' １Wi j (/
! ) (L) 1ΔW i j (42) LL'
(6)ΔWij(41!)(Lゝ -ηDi(
e) Yj(ffi-1) (f=2, ・
..., L) (7) However, the following formula is also often used. This means that ΔWi j (ff)'' in the above equation is passed through a digital low-pass filter in the first order, and α
is the parameter that determines the time constant.

ΔWi j (e) (L″1〉=ηDi(j!)Y
j(1-1)+αΔWi j(j2)”
(8) The operations required in this backward processing process are operations between vectors, or operations between matrices and vectors, and in particular, the center is the transposition of the weight matrix W, whose elements are the weights of neurons in each layer. This is a multiplication of the matrix W7 and the error vector DJ (-e). This error vector is a vector in the general case where there are multiple neurons in the engineering layer. The flowchart on the left side of FIG. 5(E) will be explained.

Forward processing and backward processing for one layer are performed. First, input data Ip is set on a shift register, and the system performs forward processing for one layer.

This is done for each layer, so this forward processing is repeated for as many layers as possible. Then, output data Op is output, so this is set on the shift register. Then, from step 7, the following steps are executed in parallel for as many units as the output layer. That is, the error D, (L) = Yi (L) Op
(i) and set this error to the i-th tray. Then, backward processing is performed for each layer from the output layer to the input layer.

This backward processing is shown on the upper right side of FIG. 5(E). Regarding the Lth layer, since the number of layers is N(l), the shift register length is set to N (f). Then, the following operations are executed in parallel for the number of units in the previous layer.

That is, the above equation (2) is executed in step 83. What is important here is the weight wJz(z), which is an element of the transposed matrix WT of the weight matrix. Then, in step 84, the above (6), (7)
Alternatively, equation (8) is calculated and the weights are updated. In step 85, the error D. Output (f-1) to the i-th tray. This is necessary for the operation of step 84 in order to calculate the next error. The lower right of Figure 5 (A) is the 5th
This is a flowchart on the left side of FIG. 3(E), which means that sequential processing of forward processing and backward processing is repeated until learning is mastered. In addition, in order to stabilize weight updating and learning in such processing, there is processing such as smoothing the amount of weight correction, but these all involve scalar multiplication of matrices and addition and subtraction between matrices, and as expected, This can be done on this neurocomputer. Further, although the sigmoid function unit 101 is assumed to be realized by hardware, it may be realized by software. Also,
The learning end reversal means 103 may be realized by software on the host computer.

The above neurocomputer will be further explained using FIG. 5(F). FIG. 5(F) is a processing flow diagram when learning error backpropagation. Vector representation is used here. In the same figure, X (/!
) is the neuron vector of the lth layer, and W is the coupling coefficient, that is, the weight matrix. r is the sigmoid function e, (
f) is the error vector propagated in the opposite direction from the output side of the depleted layer, and ΔW is the weight correction amount. When an input signal is given, first, in the case of three layers, forward processing of the hidden layer is performed, assuming that there is no input layer.

That is u=Wx(f). If a nonlinear function is applied to this U, it becomes the input for the next layer, that is, (j2+1)l'iJ. Since this is the input of the output layer, forward processing is performed on it. A teacher signal is then input, and backward processing begins.

In the output layer, the error e between the teacher signal and the output signal is multiplied by the differential of r for backward processing. Furthermore, the error between the intermediate layers and the like is obtained by multiplying the variable obtained by differentiating the back-propagated error signal by the transposed matrix W7 of the weight matrix. ΔW may be obtained by multiplying the value obtained by multiplying each element of the error vector by the sigmoid differential by the element of the previous WT, and W may be updated. In this way, backward processing of the output layer and backward processing of the hidden layer are performed. The calculation performed in forward processing is the product of the weight matrix W and the input vector X, and the calculation of the value of the sigmoid function of each element of the resulting vector. This calculation can be performed in parallel in each neuron. In addition, there are two main tasks in backward processing: the first is to sequentially transform the error between the teacher signal and the output signal and propagate it backwards from the back to the front, and the second is to propagate the error based on the error. The solution is to modify the weights. In this inverse calculation, the transposed matrix w of the weight matrix W
Multiplication by T is required. The product of the transposed matrix WT and the vector is described in the previous embodiment. In other words, an important point in realizing backbroadcasting learning is an efficient method of realizing vector multiplication with the transpose matrix WT of the weight matrix.

Further, using Figure 5 (G) and (H), calculate the forward sum of products,
An example of backward product-sum calculation will be explained. The forward product-sum operation is a matrix×vector calculation, and in particular, the matrix is a weight matrix W. In the present invention, when calculating the matrix-vector product Ll=WX, for example, the rows of the weight matrix and the vector X are simultaneously multiplied for the following equation (9). This processing method is explained using Figure 7 (chains).

The weight matrix W is a rectangular matrix. For example, it is a 3×4 matrix. Each element of the vector truth is entered on the tray. T
At time 1, X, and W. , X2 and W2, and X3 and W33 are calculated in each unit. Moving to T2, each element of vector X is cyclically shifted upward. At T2, the product of W,2 and X2 is added to U+. Therefore U1
is X IX W + + + X z X at this time
W +. becomes. Also, in the second unit W23 and X3 are multiplied, and in the third unit W,,XX4
is multiplied. At T,, W,3 and X3 are multiplied and added to Ul. W24 and X4 are multiplied and added to U2. W31 and X1 are multiplied and added to U3. At this time, X2 is excluded from the calculation target. T4
In, W, 4 and Xa, Wz+ and X I, W3■
and X2 are multiplied simultaneously and U+, Uz, U3
are added to each. In this case, X3 is not subject to calculation. The product of a rectangular matrix and a vector is performed by taking into consideration what is not subject to this operation.

? The partial vector Wi2 is stored in the local memory of PE-2 in a skewed manner so that Wii is at the beginning. Xi gets on the tray and rotates counterclockwise around the ring. Ui is accumulated on a register inside PE-.

It starts from the state of Ui=O in the leftmost state.

PE-z multiplies Xj and Wij in front of it, and adds the result to Ui. At the same time, Xj is adjacent to the next tray (circulating counterclockwise on the ring).

By repeating this four times, all Ui's can be found at the same time.

Wit is skewed, χi starts from a state where all are in the tray, and Ui are all found at the same time.

FIG. 5(H) is an explanation of backward product-sum calculation.

This is a timing diagram when calculating the transposed matrix and the row vector product, e=W''v. In this case, the vector V is a vector consisting of elements obtained by multiplying the error vector of the previous layer by the derivative of the nonlinear function. .e is the error hector for backpropagation in the next layer to be determined.What is important in the present invention is that even if the transposed matrix Wt is It is possible to perform calculations with the same arrangement as W.

That is, in the present invention, this is done by cyclically shifting the vector of C to be determined. The formula of the transposed matrix W'' and vector V to be calculated follows the formula 00).

As shown in the above equation, matrix W is transposed and is a rectangular matrix. e, is W. Xv, +W21XV2
+W31XVl. To perform this operation, the fifth
In the diagram (H), in the time period T+, the product of W11 and v1 is calculated in the first unit (DSP). This is inserted into e, which is O. and,
Cyclic shift moves to T2, but is el an operation at time T2? Not targeted. When it becomes T3,
It is the object of calculation in the third unit.

That is, since the value obtained by multiplying W3I by v3 is added to the previous value, W,,Xv. It is added to. Therefore, in time area T3, the result of e is W11×v,+W3■
It becomes XV. When the process moves to T4, e1 becomes a calculation target in the second unit as a cyclic shift. Here, since W2 and XV2 are added to e, an inner product operation between the first row of the matrix of equation 00 and the vector V is executed, and the result of the operation is stored in e.

Similarly, the product of the second row and the vector can be obtained by following e2.

W22XV2 at time T1, WI2XVI at T2,
In Tl, e2 becomes idle, and in T4, W32XV. The product is calculated as the sum of each product. W7 3rd
The product of the row and the vector V can be obtained by following e3. W33Xv3 in TI, W23X in T2
V2 is added, and at T3, W, . Xv, is added. For T4, e4 is a play. The product of the fourth row of WT and the vector ■ can be obtained by following e4. At time T+, e4 is idle. Wz4XVi is added at T2, W24Xv2 is added at T3, and W,4 is added at T4.
Xv, is added and calculation can be done. Thus, in the present invention, the partial vector Wi9 of W is PE. are stored skewed so that Wii is at the top of the local hierarchy. It is ei and Vi that are replaced with the previous ones. That is, ei is accumulated while circulating counterclockwise on the tray, and Vi resides inside PE-1.

Start from e j=o in the leftmost state. PE-t multiplies Vi and Wij and adds the result to ej in front of him. At the same time, this updated ej is transferred to the adjacent tray (circulating counterclockwise on the ring). By repeating this four times, all ej can be found at the same time.

In this way, the neurocomputer of the present invention can be realized with any number of layers, and not only has the flexibility of having a high degree of freedom in the learning algorithm, but also can utilize the speed of the DSP as it is, and moreover, in the calculation of the DSP. No overhead, high speed, and DSP-based SIM
D can be executed.

FIG. 6 is an explanatory diagram of a fifth embodiment of the present invention, which calculates the product of matrices using analog data. In the figure, the second
Components that are the same as those shown in the figure are indicated by the same symbols, and 1d is a processing device of the data processing unit l, which is composed of, for example, an analog multiplier 1e and an integrator 1f, and 2d is a data holding unit of tray 2. The circuit is composed of, for example, a sample/hold circuit 2r, 2e is a data transfer circuit for the tray 2, which is composed of, for example, an analog switch 2g and a buffer amplifier 2h, 6 is means for setting data in the tray 2, For example, it is composed of an analog switch 6d.

The operation of this embodiment is the same as that described in the principle diagram of the present invention (FIG. 1).

FIG. 7 is an explanatory diagram of a sixth embodiment of the present invention, showing the multiplication of a band matrix and a vector. In the figure, the same parts as those shown in FIG. 2 are indicated by the same symbols.

The operation of this embodiment will be explained with reference to FIG. 7(B).

In the present invention, a band matrix A of m×n (n≧m≧1) and width k
When calculating the multiplication result of the vector X with the number of elements n (vector with the number of elements m!), as shown in Fig. 7(A),
m data processing units 1 each having two inputs and having a multiplication function and an approximate multiplication result accumulation function, n trays 2, and input data supply means for each of the data processing units 1; In the configuration consisting of
), the processing is performed in chronological order as shown in FIGS. 7(C) and 7(D). Therefore, multiplication of a band matrix of width k by a vector can be performed in a processing time proportional to k.

What is important in this embodiment is that the vector It is a good idea to keep it. That is, when starting the process from the start position of the band, if the product-sum calculation is performed while shifting in a certain direction, the process will be completed in a time proportional to k. However, if for some reason (not shown) you start processing from a state where the band is placed in the middle of the band, it is obvious that it is sufficient to first shift the vector view to one end, and in that case, the shift register 3 shifts in both directions. It is meaningful that it is possible.

That is, for example, when starting processing from the center of the band, first shift it to the right by k/2 (round down to the decimal point), and then perform the product-sum operation while shifting it in the opposite direction (in this case, to the left), resulting in a total of 372k. The process will complete in a proportional amount of time.

If the shift register 3 is not capable of shifting in both directions, the vector must be rotated once, which requires a time proportional to the size nl of the banded matrix rather than the width k. For large-scale banded matrices, this difference is very large, and the advantage of the method of the present invention is that the multiplication of a banded matrix and a vector can be performed in a processing time proportional to the width k of the banded matrix. .

FIG. 8 specifically shows the structure of the tray.

Tray is basically just a one word latch, but DS
Access from P and transfer to the adjacent tray can be executed in one cycle (post shift).

Function switching is performed simultaneously with data access using the lower bits of the address line, improving speed.

One tray is a gate array with approximately 1200 Ba
It is the scale of a SIC cell, and it is also possible to put 2 to 4 pieces in a chip.

It is also possible to incorporate several words of work registers in the tray.

FIG. 9 is a block diagram of a neurocomputer actually constructed using an embodiment of the present invention.

It is a SIMD type multiprocessor based on Sandy's basic structure or a one-dimensional torus (ring) combination of DSPs.

A distinctive feature is that it operates as a SIMD, even though its coupling topology and operation are similar to a one-dimensional systolic array.

The “tray” is connected to each DSP via a bidirectional bus.
These latches have a transfer function and are connected to each other in a ring shape, making up a cyclic shift register as a whole. Hereinafter, this shift register will be referred to as a ring.

Each DSP has 2K words of internal memory and 64 words of external RAM
, the internal memory takes one cycle, and the external memory takes l~
It can be accessed in 2 cycles.

The external RAM is connected to the host computer's VMEW bus via a common bus for initial loading of programs and data. External inputs are also connected to the host computer via breadboard memory.

FIG. 10 is a time-space chart during learning in the embodiment of the present invention, where the vertical direction shows the number of processors and the horizontal direction shows time. 2 corresponds to the number of processors in the input layer, H corresponds to the number of processors in the hidden layer, and 2 corresponds to the time for the product-sum operation of the processors.

The time required for the input signal to perform the forward product-sum of the hidden layer is proportional to the product of the number 1 of processors in the input layer and the time I corresponding to the product-sum of one processor. Next, a sigmoid calculation is performed. Also in the output layer, the output layer's forward sum of products (2H
r) and sigmoid can be performed. Here, since the number of processors in the output layer is smaller than the number of processors in the hidden layer, the size of the ring itself is also smaller. Next, it receives the teacher signal input, calculates the error, and performs back propagation of the error. Note that in this error calculation, the error calculation in the sigmoid of the output layer is also performed by backward product sum of the service output layer, and the weight update of the output layer is performed via gradient vector calculation and a low-pass filter. Then, after calculating the error using the sigmoid in the hidden layer, only the weights of the hidden layer are updated without performing the backward sum of products.

〔Effect of the invention〕

As explained above, according to the present invention, data can be processed in parallel for a wider range of processing than conventional methods without the overhead of data transfer associated with data processing, and it is proportional to the number of data processing units. The ability to realize high-speed data processing greatly contributes to improving the performance of data processing devices that perform matrix operations or neurocomputer operations.

[Brief explanation of drawings]

FIG. 1(A) is a principle block diagram of the present invention, FIG. 1(B) is an operation flowchart of the present invention, FIG. 1(C) is a schematic diagram of the operation of the present invention, and FIG. 1(D) is an operation time chart of the present invention, FIG. 2(A) is a configuration diagram of the first embodiment, FIG. 2(B) is an operation flowchart of the first embodiment, and FIG. 2(C) is an operation flowchart of the first embodiment. , a schematic diagram of the operation of the first embodiment, FIG.
D) is an operation time chart of the first embodiment, FIG. 3(A) is a configuration diagram of the second embodiment, FIG. 3(B)
is an operation flowchart of the second embodiment, FIG. 3(C) is an operation overview diagram of the second embodiment, and FIG.
D) is an operation time chart of the second embodiment, FIG. 4(A) is a configuration diagram of the third embodiment, FIG. 4(B)
is an operation flowchart of the third embodiment, FIG. 4(C) is an operation overview diagram of the third embodiment, and FIG.
D) is an operation time chart of the third embodiment, FIG. 4E is a detailed operation flowchart of the third embodiment, and FIG. 5A is a configuration diagram of the fourth embodiment. Figure 5 (B)
is a neuron model of the fourth embodiment, FIG. 5(C) is a network of the fourth embodiment, FIG. 5(D) is a forward processing flowchart of the fourth embodiment, and FIG. ) is a learning process flowchart of the fourth embodiment, FIG. 5(F) is a process flowchart when error back propagation learning is performed on Sandy, and FIG.
G) is a time chart when calculating matrix-vector product = Wx in Sandy, Figure 5 (H) is a time chart when calculating matrix-vector product e = W''v in a transposed matrix, Figure 6 (A) is a configuration diagram of the fifth embodiment;
FIG. 6(B) is an operation flowchart of the fifth embodiment, FIG. 6(C) is a schematic diagram of the operation of the fifth embodiment, and FIG.
D) is an operation time chart of the fifth embodiment, FIG. 7(A) is a configuration diagram of the sixth embodiment, FIG. 7(B)
is an operation flowchart of the sixth embodiment, FIG. 7(C) is an operation overview diagram of the sixth embodiment, and FIG.
D) is an operation time chart of the sixth embodiment, FIG. 8 is a diagram specifically showing the structure of the tray, and FIG. 9 is:
FIG. 10 is a block diagram of a neurocomputer actually constructed using an embodiment of the present invention, and FIG. 11 (A) is a time-space chart during learning in the embodiment of the present invention. The principle configuration diagram, Figure 11 (B) is an operational flowchart of matrix-vector product using the common bus SMD method, Figure 12 (A), and Figure 1
FIG. 2(B) is a diagram of the principle of operation of matrix-vector product using the ring systolic method, and FIG. 12(C) is a diagram of the principle of operation of matrix-vector product using the ring systolic method. DESCRIPTION OF SYMBOLS 1... Data processing unit, 2... Tray, 3... Shift register, 4... Storage device, 5... Synchronization means, 6... Data setting means, 7... Length change means, 1l...input of data processing unit 1, 12...second input of data processing unit 1, 21...tray 2;
22...First output of tray 2, 23...Second output of tray 2, 24...Second input of tray 2, 82 83 84 85 91 92 93 1 First input, first output of l, second input of l, second output of l, ・PE9 ・PE9 ・PE9 ・PE9 ・PE, ・I/O of PE9 1, ・Common bus.

Claims (1)

[Claims] 1) a plurality of data processing units (1) each having at least one input (11), each having a first input (21) and an output (22) and each having a data storage and a data processing unit; Multiple trays (2
), wherein all or part of said trays (2) are each connected to a first input (11) of said data processing unit (1).
a second output (23) connected to the tray; and shifting means (3) comprising a first input (21) and an output (22) of the connecting tray (2). , data transfer on said shifting means (3) and said tray (
Parallel data characterized in that matrix operations or neurocomputer operations are performed by synchronously performing data transfer between 2) and the data processing unit (1) and data processing by the data processing unit (1). Processing method. 2) The parallel data processing system according to claim 1, wherein the shift means (3) is a cyclic shift register. 3) The parallel data processing system according to claim 1 or 2, further comprising means for changing the length of the shift means (3). 4) The parallel data processing system according to claim 3, wherein the means for changing the length of the shift means (3) is input switching means. 5) The parallel data processing system according to claim 3, wherein the means for changing the length of the shift means (3) comprises external data supply means and input selection means. 6) said data processing unit (1) outputs a first output (21);
), said tray (2) having a second input (24) connected to said first output (21), means for writing data from said data processing unit (1) to said tray (2). A parallel data processing method according to any one of claims 1 to 5, characterized in that it has the following. 7) The data processing unit (1) and the tray (2)
7. The parallel data processing system according to claim 6, wherein the data transfer path between the two is a bus commonly used for input and output. 8) When further processing the data processing result, the processing result is transferred to the tray (2) using the writing means.
Parallel data processing method described in Section. 9) said tray (2) is provided with a third input (25) and an output (26) each interconnected, said shifting means (
9. The parallel data processing system according to claim 1, wherein 3) is a bidirectional shift register. 10) Parallel data according to claim 9, characterized in that the data transfer path between the trays (2) constituting the bidirectional shift register is a bus commonly used for input and output. Processing method. 11) The parallel data processing method according to claim 9 or 10, wherein data is transferred bidirectionally on the bidirectional shift register. 12) Shifting means for circulating each element of the vector, the tray means (2) having an internal function of holding and transferring each element, and a tray means (2) corresponding to each row of the matrix and having at least two inputs. data processing unit means (1) having a function of multiplying between and accumulating the multiplication results; and a storage means (4) present in each data processing unit and capable of sequentially reading out elements of each row of the matrix. and by separating the data processing unit means (1) and said tray means (2) for cyclically shifting data,
Each data processing unit means (1) multiplies the elements of the cyclically shifted vector by the corresponding matrix elements from the storage means (4), and accumulates the multiplication results to determine the number of rows and columns. A parallel data processing method characterized by performing matrix operations or neurocomputer operations by calculating the product of rectangular matrices and vectors with different values. 13) A parallel data processing system according to claim 12, characterized in that said tray means (2) comprises bypass means (7) for changing the length of the cyclic shift. 14) The length of the shift register in the tray means (2) is set to n, and a vector consisting of elements equal to the number of n is set in each of the trays, and each of the data processing unit means (1) corresponds to the vector. Receiving vector elements and matrix elements from the tray and storage means (4), multiplying and accumulating them, and then repeating the operation of cycling through the vector elements n times, the results are stored in the tray means (2).
), the shift length of the cyclic shift is changed from n to m, and the same operation is repeated m times to further multiply the product of the rectangular matrix and the vector by a different rectangular matrix. Parallel data processing method according to 12. 15) When calculating the product of a transposed matrix of a rectangular matrix and a vector, partial row vectors constituting the matrix are stored in the storage means (4) connected to each data processing unit means (1).
The partial sum generated during the calculation is accumulated on the data holding circuit in each tray of the tray means (2), and the product of the data on each tray and the data from the storage means (4) is calculated. 13. The parallel data processing system according to claim 12, wherein the product of the transposed matrix and the vector can be calculated by transferring the partial sum onto a tray and performing cyclic shifting. 16) In the neural network, when the elements of each row of the rectangular matrix are made to correspond to the weights of the connecting branches connecting to the neuron model, the data processing unit means (1)
By multiplying each of the input variables in each data holding circuit of the tray means (2) by the weight from the corresponding storage means (4) and repeating the cyclic shifting operation within the tray means (2), A processing unit (103) that calculates the sum of the products of the weights of connected branches connected to the neuron model and input variables to the connected branches, and then applies a nonlinear function to perform forward processing of the neural network. 13. The parallel data processing method according to claim 12, wherein the parallel data processing method enables the following. 17) The parallel data processing method according to claim 16, wherein the nonlinear function is a sigmoid function. 18) The parallel data processing method according to claim 12, wherein the neural network is a hierarchical neural network having at least three layers. 19) Backward processing of the backpropagation learning rule in a hierarchical neural network, which is a process in which the error between the output signal from the output layer and the teacher signal is propagated toward the input layer in the opposite direction to the normal signal flow direction. In the method described in claim 15, a vector whose elements are back-propagated error signals and a transposed matrix W^T of a weighting coefficient matrix W whose elements are weights in the forward processing are combined using the method according to claim 15, that is, the transposed matrix of the matrix and the vector. While cyclically shifting the partial sum in the middle of the calculation on the tray means (2),
The product of each element of the weighting coefficient matrix stored in the storage means (4) and each element of the error vector in the data processing unit means (1) is calculated and added to the partial sum, and the result is stored as the partial sum in the tray. Claim 12, characterized in that by leaving it on the means (2), it is possible to execute the backpropagation learning rule by executing the process of calculating the product of the transposed matrix×vector as a backward product-sum calculation. 19. Parallel data processing method according to 18. 20) When the data is analog, the processing device of the data processing unit means (1) is composed of an analog multiplier and an integrator, and the data holding circuit of each tray of the tray means (2) is configured to store samples. Consists of a hold circuit,
20. A parallel data processing system according to claim 1, wherein the data transfer circuit of the tray means (2) comprises an analog switch and a buffer amplifier. 21) When multiplying a band matrix A with a matrix of m×n and a width k by a vector x with the number of elements n, the element tray means (2) of the vector x is performed without rotating the vector x once by cyclic shift. Claims 1 to 20 characterized in that the starting point from which the band of the matrix starts can be arbitrarily specified when shifting within the matrix.
Parallel data processing method described. 22) The parallel data processing method according to claim 21, wherein the direction of the shift can be bidirectional. 23) By separating the data processing unit means (1) and the tray having a data holding function, data transfer between the tray means (2) and data processing by the data processing unit means (1) can be performed simultaneously. The data transfer time is hidden behind the data processing time by performing the data transfer in parallel and making the time required for data transfer between the tray means (2) shorter than the time that the data processing unit means (1) has for data processing. 23. The parallel data processing method according to claim 1, wherein the parallel data processing method is characterized in that: