JPH0421900B2 - - Google Patents

Description

[Detailed Description of the Invention] [Technical Field of the Invention] The present invention relates to a matching operation based on dynamic programming, which is used, for example, when matching patterns in speech recognition or character recognition. The present invention relates to an array processor used to perform operations on all combinations of variables of different types, and to perform operations on recurrence formulas with local data dependence using the results of the operations.

[Prior art]

As a representative example, an example of a matching operation based on dynamic programming, which consists of an operation between two types of vector variables and a recurrence formula of an accumulation operation using the operation results, will be shown below.

D _ij =｜c _i −r _j | ² = _n 〓 ^k=1 ｜c _K i−r _K ｜j｜ ² …(1) S _ij =D _ij +mmS _i,j-1 S _i-1,j-1 S _i-1,j …(2) S _pj =∞, S _ip =∞, S _pp =O …(3) Here, c _i and r _j are I vector sequences C = {c ₁ , c ₂ , ..., c ₁ }, N vectors R=
These are the i-th and j-th elements of {r ₁ , r ₂ , ..., r _N }. Also, m represents the order of each vector, and c _i
= (c ₁ ⁱ , c ₂ ⁱ , ..., c _n ⁱ ), r _j = (r ₁ ^j , r ₂ ^j , ..., r
_n
^j ). D _ij and S _ij represent the distance between vectors and the cumulative distance, respectively. Equation (3) is the initial condition of recurrence equation (2).

Conventionally, as an array processor that can process this type of operation in parallel, when the number of data of two types of vector strings is I and N, respectively, (I × N) processing elements (processing elements; hereinafter referred to as PE
) are arranged in two dimensions. This configuration is shown in FIG. 1, and examples of its operation are shown in FIGS. 2 to 5. In Figure 1, 100 is PE, 200
indicates a data bus, and 300 indicates a control bus. Further, 400 indicates an input terminal, and 500 indicates an output terminal.

Each PE 100 has means for executing vector distance calculation (1) and comparison/accumulation calculation (2) consisting of product-sum calculations, as well as means for executing comparison calculation results, cumulative results S _ij , and vector data c between adjacent PEs. It has means for sending and receiving _i and r _j . Note that each PE is given a number indicating its position on the two-dimensional array, and the PE in row i and j is PE _ij
Expressed as , the above (1), (2), and (3) can be executed by the following operations.

Left-adjacent PEs _i-1 , _j and lower-adjacent PEs _i , _j-1 (or the leftmost input terminal and the bottommost input terminal)
Input two types of vector data c _i and r _j from
The distance between the vectors is determined by executing equation (1).

To the right neighboring PE _i+1 , _j and the upper neighboring PE _i , _j+1 ,
Transfer vector data c _i and r _j respectively.

The cumulative operation result S i _-1 , _j from the left adjacent PE i- ₁ , _j is
Input the comparison operation results of mm (S _i , _{j -1} , S _i-1 , _ji ) from the lower adjacent PE _i , j-1 , respectively, and calculate these comparison operations mm [S _i-1 , _j , mm ( S _i , _j-1 , S _i-1 , _j-1 )] and add D _ij obtained in to this result to obtain S _ij .

Execute the comparison operation mm (S _ii , S _i-1 , _j ), transfer the operation result to the upper neighboring PE _i , _j+1 , and apply the cumulative operation result S _ij
is transferred to the right-adjacent PEs _i+1 and _j .

Here, , indicates the process of executing the comparison/accumulation operation (2). That is, among the three types of cumulative results S _i , _j-1 , S _i-1 , _j , S _i-1 , _j-1 necessary to execute cumulative operation (2) in PE _ij , S _i , _j-1 ,
S _i-1 , _j are PE _i , _j below the PE _ij to be transferred, respectively
₋₁ and the left adjacent PE _i-1 , _j , whereas
S _i-1 , _j-1 are diagonally adjacent to PE _ij
Exists in PE _i-1 , _j-1 . Therefore, the former two data require one transfer, and the latter requires two transfers via PE _i and _j-1 . However, in PE _i , _j-1 that intervenes in the transfer of S _i-1 , _j-1, S _i , _j-1 and
S _i-1 , _j-1 ) and transfer the result to PE _ij ,
If a comparison operation is performed between this data and the transfer data S i _-1 , _j from PE _i-1 , _j , then at PE _ij ,
(2) This is equivalent to performing a comparison operation on three data as shown in formula (2).

A method of performing each of these operations as a parallel processing unit of PEs for all PEs on each diagonal line shown by the solid line in FIG. 1, or,
The final cumulative result S _I , _N is computed while calculating the inter-vector distance D _ij and the cumulative result S _ij by using two types of operations as parallel processing units and executing them alternately on adjacent diagonal PEs. can be found. In the case of the latter execution method, the effective number of dynamic steps between the two parallel processing units is different, so (no operation) NOP
Although the number of execution steps must be adjusted depending on the instruction, detailed explanation will be omitted here. Second
5 to 5 show the operation on the two-dimensional array in this latter case from time t to time t+3. Here, the time is the time required for each PE to execute all the processes of and, and each figure a and b shows the data enclosed in the rectangle calculated in each PE during the above unit time. It shows the state that has been applied.

In such a two-dimensional array configuration, parallel processing can be executed by taking advantage of the locality and regularity of operations. However, for example, if the matching calculation formula (2) based on the dynamic programming described above is a complex calculation formula as shown in formula (4), the cumulative results of formula (4) S _i-1 , _{j- 1} , S _i-1 , _j-2 , S _i-2 , _{j-1 ,} operations that generate three data to be subjected to the transfer and comparison operations must be performed via two PEs,
The comparison operation in PE _ij converts these three data into PE _ij
Each PE
Not only does the content of the processing unit that should be executed in parallel become complicated, but it is also impossible to execute parallel processing using all PEs efficiently.

S _ij =D _ij mmS _i-2,j-1 +2D _i-1,j S _i-1,j-1 +D _ij S _i-1,j-2 +2D _i,1-j …(4) Also, the target positive integers N and I that represent the number of data of two types of vector sequences to be processed in a matching operation based on dynamic programming.
Since _the number _of PEs must _be determined depending on ^both _of
^u , ..., c _1u ^u }; u=1, 2..., l _c ) and various vector sequences R _v (R _v = {r ₁ ^v , r ₂ ^v ..., r _Nv ^v }; v=
In order to perform a matching operation based on dynamic programming with 1, 2..., l _r ),
As positive integers N and I, Nmax=( max 1≦v≦lrNv), Imax=( max 1≦v≦lrIu) must be selected, and the number of PEs is (Nmax×
Imax) pieces are required. Therefore, the vector sequence
When processing C _u and R _v , Cmax,
For all combinations of vector sequences other than the Rmax combination, there are many PEs that do not need to perform matching calculation processing based on dynamic programming, making it impossible to use hardware effectively.

Furthermore, the fact that the number of required PEs must be determined from the maximum number of data to be processed is a major hindrance when attempting to downsize using LSI technology. The number of PEs that can be mounted on one LSI is
It depends on the PE function, but for example, one LSI
About 4 PEs can be installed in the Nmax
60. In the case of Imax60, as many as 900 LSIs must be arranged and connected in two dimensions.

[Object and structure of the invention]

Therefore, an object of the present invention is to perform two-way matching operations based on dynamic programming.
The calculations for all combinations of variables of different types and the calculation of recurrence formulas with local data dependence using the calculation results are adapted to the target amount of calculations.
The object of the present invention is to provide an array processor that can realize highly efficient parallel processing while effectively operating each PE in an array configuration consisting of a number of PEs.

In order to achieve such an objective, the present invention
Two types of input data strings C = each from the outside
{c _i }(i=1,2,...,I) and R={r _j }
Means for inputting each data c _i , r _j of (j=1, 2, ..., N), performing each desired operation such as addition/subtraction, comparison operation, and product-sum operation between two types of data and outputting the results. N processing elements each having storage means, means for transmitting and receiving input data c _i and operation results between adjacent processing elements, and means for outputting the final operation results to the outside are arranged in a ring, and Each processing element is connected in a circular manner via a multiplexer that switches between a data transfer path and an external input path for exchanging data with adjacent processing elements, and all processing elements transmit their processing results to adjacent processing elements. Means for executing the process of transferring (m o ⁿ dN) times in parallel with the normal processing unit in each processing element every time n consecutive pieces of input data in the input data string C are replaced, and each of these processes It is equipped with means for controlling the elements.

Here, modN represents the remainder when N is divided by n. Note that I, N, and n are arbitrary positive integers, but in reality, the relationship between N and n is m o ⁿ
It is defined within the range where dN holds true. Hereinafter, the present invention will be explained in detail using Examples.

〔Example〕

The above equations (1), (2), and (3), which are examples of matching operations based on dynamic programming, can be transformed into 2
vector sequences C _u , R _v (u=1, 2,..., l _c ,
The case of execution for v=1, 2, . . . , l _r ) will be described. FIG. 6 shows the configuration of an embodiment of the present invention.

Figure 6 shows the case where the number of PEs is n, and 1 is this processing element PE, which performs addition, subtraction, and comparison to execute matching calculation formulas (1), (2), and (3) based on dynamic programming. It has a built-in arithmetic unit that performs arithmetic operations and sum-of-products operations, registers for exchanging data with adjacent PEs and external devices, and memory that stores operational results and transferred data. 2-1 to 2-n are external input data c _i
When ^u (i=1, 2, ..., I _u ) are input to the array n pieces (for the number of PEs), and when input data c _i ^u (i=1, 2) are transferred cyclically from adjacent PEs. ,…
..., I _u ). For example, when n input data strings c ₁ ^u , c ₂ ^u , ..., c _o ^u of each PE in the array are input from PE 1, only the multiplexer 2-1 selects input data bus 3 from the outside. , this is used as ^the input port for _the external ^input data _string c ₁ ^u , c ₂ ^u . Individual data c ₁
Assign one ^u , c ₂ ^u , ..., c _o ^u to each PE.
Otherwise, all multiplexers 2-1 to 2-n select the inter-PE data transfer bus 5,
The input data strings c ₁ ^u , c ₂ ^u , ..., c _o ^u are transferred cyclically between PEs. In addition, as described later, each PE is configured to be able to simultaneously transfer each processing result to the adjacent PE in parallel with the normal processing unit modN times for each exchange of the above n input data patterns. It is becoming. 4 is the other input vector data string R _V = {r ₁ ^V , r ₂ ^V , ... r _NV ^V } (k = 1,
2,...l _r ) are input sequentially to each PE, and the final calculation results S _I1 , _N1 , S _I1 , _N2
...S _Iu , _NV ...S _Ilc , _Nlr are I/O buses for outputting them to the outside. 5 above involves the circular transfer of vector data c _i ^u between PEs and the cumulative operation result S _ij
This is a data transfer bus for executing transfers.
6 is an I/O terminal of each PE connected to the I/O bus. In addition, 7, 8, and 9 are input vector data c _i ^u , r ₁ ^V (i=1, 2,...I _u ; j=
1,2,...,N _v ;u=1,2,...l _c ;v=
1, 2, ... l _r ) and the final calculation results S _I1 , _N1 ,
S _I1 , _N2 ... S _IuNV ... S _Ilc , N _lr are shown. 10 more
is a control unit that performs control operations for the entire system, including determining the timing of exchanging the input data and counting the number of transfers of processing results.

FIG. 7 shows an example of the configuration of each PE. In the figure,
The part surrounded by the dashed line indicates one PE1,
1 is the vector data r _j ^V (j=1, 2,
..., N _V ) and the final calculation result S _Iu N _v
An external I/O bus 12 indicates an I/O terminal for exchanging data with the external I/O bus 11. Further, 13 indicates a data transfer bus terminal from the left adjacent PE, and 14 indicates a data transfer bus terminal to the right adjacent PE. 15 is a buffer register for inputting vector data r _j from the external I/O bus 11; 16 is a buffer register for outputting the final calculation results S _Iu , N _V to the external I/O bus 11; 17 is vector data from adjacent PE
A register for inputting data necessary for inputting c _i ^u (i = 1, 2, ... I _u ) and calculating the cumulative operation S _ij executed in processing operations b○, c○ described later;
18 is a register for transferring vector data c _i ^u and data necessary for calculating the cumulative operation S _ij to an adjacent PE, and 19 is an internal bus. 20, 21
_are all components r _k ^vj , c _k ^ui ( ^k = ¹ , 2 _, ...,
22 is an arithmetic unit having addition/subtraction, comparison, and product-sum operation functions for executing the operations of formulas (1) and (2); 23 is a buffer memory for storing (2),
(3) This is a work memory for holding the data required when executing the formula. Work memory 23
is divided into two types of areas 23-1 and 23-2 due to the nature of the data it holds. That is, 2
3-1 is an area for holding data necessary for executing processing operations a○, b○, c○ during circular transfer of input vector data c _i ^u , which will be described later _; C ₂ , . . . Cl This is a storage area for data required when executing processing operations b○ and c○ immediately after exchanging n vector sequences of _c . 24 is a control unit, which performs control according to a built-in microprogram or external instructions. 25
is the input terminal for the control signal from the control unit 10 in FIG. 26 and 27 indicate address lines to the work memory. Of these, 26 is for accessing the area 23-2 in which the counter 28 holds the intermediate results of calculations, while 27 corresponds to, for example, a direct address from the microprogram, and is used to access each of the above processing operations b○ and c○. The storage area 23-1 for data necessary for processing is accessed.

As mentioned above, the calculation results in the calculation unit 22 are held in the work memory 23, but the
It is equipped with registers 17 and 18 for data transfer between PEs, and while the above calculation result is fetched from the work memory 23 into the register 18 and transferred from there to the register 17 of the adjacent PE, the calculation unit 22 The configuration is such that the following calculations can be performed. Therefore, in parallel with the normal processing unit of transferring input data c _i consisting of a○, b○, c○, calculating D _ij and S _ij , and transferring the results, that is, normal When replacing input data patterns, each
It is possible to simultaneously transfer m o ⁿ dN processing results to adjacent PEs, as will be described later, while the PE is executing the above calculation.

Next, a method of executing the matching operation based on dynamic programming shown by the above-mentioned arithmetic expressions (1), (2), and (3) with this configuration will be explained. The matching operation based on dynamic programming consists of 2
Equations (1) and (2) are used for each grid point on each two-dimensional grid plane created by the different vector data sequences C _u and R _v .
This corresponds to executing the calculation. Figure 8 shows two types of vector data strings in this configuration, namely l _c
vector data string C _u = {c ₁ ^u , c ₂ ^u , ..., c _Iu
^u } (u = 1, 2, ...l _c ) and l _r vector data string R _v = {r ₁ ^V , r ₂ ^V , ... y _Nv ^v } (v = 1, 2, ...
It shows how matching operations (1), (2), and (3) based on dynamic programming for (... _l r ) are executed continuously. In the figure, each diagonal broken line and diagonal solid line on the lattice plane represent time when the PE processing unit is a time unit, and arrow A indicates the direction in which time progresses. This means that grid points on the same broken line and solid line are processed simultaneously. Since the number of PEs is n, n grid points on the diagonal are always processed simultaneously during processing.

FIG. 9 shows the data input operation in this configuration. Figure 9 shows the case where n=6, 31 is PE,
32 is vector data c _i (i=1, 2, ..., I)
and a data transfer bus for transferring the cumulative result S _ij to the adjacent PE; 33 is vector data c _i (i=1, 2,
..., I) flow, 34 is each processing time at each processing time.
Vector data on the I/O bus to be input to PE
Indicates r _j (i=1, 2, ..., N). The number of PEs, that is, 6 vector data sequences c ₁ , c ₂ ,...
..., c ₆ are input sequentially from PE ₁ , and each vector data is input to the right adjacent PE each time the processing in each PE is completed.
Until the first data c ₁ returns to PE ₁ , the data c _i
The number of data transfer buses where (i = 1, 2, ..., 6) appears increases one by one, but when data c _i is transferred from PE ₆
After the time when data is transferred to PE ₁ , the data c ₁ to _{c 6} existing in each PE is simultaneously transferred to the adjacent PE at each time.
will be forwarded to. On the other hand, data r _j (j=1, 2,...
..., N) is the data c _i (i=1, 2,
..., 6) are input to each PE in turn in synchronization with the transfer operation. Then, while performing regulatory data exchange between each PE, calculation formulas are calculated for all grid points.
Execute (1), (2), and (3).

The group of broken lines in FIG. 8 indicates that only the multiplexer 2-1 is set to the selection mode of the input data bus from the outside, and the input vector data string c ^1/1 of the number of PEs is n.
c ^1/2 , ..., c ^1/n are input in order, and each time PE ₂ to _{PE o} completes a processing unit, vector data c ^1/x (x = 1, 2, ...) with the adjacent PE is input. , n-1) are transferred simultaneously. The solid line group following this broken line group 1 indicates that after data c ^1/1 is input to PE _o , all multiplexers 2-1 to 2-n are in the selection mode of the data transfer bus between PEs, and the input vector data string c This shows that equations ( ¹ ), (2), and (3) are executed while cyclically transferring 1/1, c ^1/2 , ..., c ^1/n between each PE. The following group of broken lines indicates that the input vector data strings c ^1/1 , c ^1/2 , ..., c ^1/n are converted into the next n vector data strings c ^1/n+1 , ... c ^1/ It shows the process of continuing the calculation while exchanging ^I1 , ... c _i ^u .

By the way, each PE has two types of vector data c _i ^u . Since r _j ^v is input, calculation formula (1) is executed independently and in parallel on each PE, but calculation formula
(2) is executed while exchanging data with neighboring PEs. For example, FIG. 10 shows the processing of each PE when all combinations of vector data sequences C ₁ , C ₂ , and vector data sequences R ₁ , R ₂ are sequentially processed with the number of PEs n=5. Steps and each
This shows the distribution of grid points handled by a PE. In the figure, grid points surrounded by ⊂⊃ mean that they are processed by the same PE, and the number on the left side indicates the number.
The PE number is shown, but in the same figure, for example, S _7,8
When calculating S 7,8 at time t ₁ , the data required to calculate S _7,8 at time t 1 is S _6,7 , S _7,7 , S _6,8 determined by PE ₄ and PE ₅ at times t ₂ and t ₃ . . Since times t ₂ and t ₃ are in the past with respect to time t ₁ , data S _6,8 exists in PE ₅ that calculates S _7,8 , and data S _6,7 and S _7,7 exist in PE 5. Present in ₄ . That is, the required data is always contiguous.
Since it exists in PE, when performing the comparison operation of equation ( ₂ ) for S _7,8 , mm(S _6,7 ,
S _7,7 ) and transfer the result _to PE ₅
Perform mm [S _6,8 mm (S _6,7 , S _7,7 )] at

In this case, as mentioned above, the input vector data strings C ₁ , C _{2 .} . .
Corresponding to the hatched grid points as shown in the figure
S _ij must be transferred to a predetermined PE before the exchange of input vector data begins. For example, S _5,1 present in PE ₁ goes to PE ₃ , PE ₂
S _5,2 present in PE _{4 goes to PE 4} , S _5,3 present in PE ₃ goes to
S _5,4 existing in PE ₄ must be transferred _{to PE 1 ,} and S _5,5 existing in PE ₅ must be transferred to PE ₂ . Generally, from the time before the start of the replacement of n vector data strings (mod _lr 〓 ^v=1 N _v ), that is, from the time before m o ⁵ d17 = 2 times in the example of Fig. 10, the total PE is as follows. The accumulated results S _po,j (p = 1, 2, ...) stored at each time are calculated by the adjacent PEs.
At the same time, data transfer is started in parallel with the normal processing operations of a○, b○, and c○, which will be described later. By performing this once for each processing unit of the PE, the necessary data S _po,j can be transferred to a predetermined PE immediately before the n input vector data strings are replaced. In the example shown in FIG. ₁₀ , in parallel with the processing for the grid points ₍ c ^1/1 , _r ^2/6 ) of PE _{1 , the} work memories 23- Data S _5,1 , S _5,2 , S _5,3 , S _5,4 , S _5,5 existing at the same address of 2 are adjacent
It is transferred to PE and placed at PE ₂ , PE ₃ , PE ₄ , PE ₅ , PE ₁ , and in the processing for PE ₁ 's grid points (c ^1/2 , r ^2/5 , PE ₃ , PE ₄ , The transfer is completed by placing it at PE ₅ , PE ₁ , PE ₂ , and the next grid point of PE ₁ (c ^1/3 ,
In the process immediately after replacing the next input vector data sequence c ^1/5 , c ^1/6 , c ^1/1 , c ^2/1 at the processing time for r ^2/6 ), PE ₃ , PE ₄ , PE ₅ , PE ₁ , PE ₂ are the above 2
Data obtained by transfer times S _5,1 , S _5,2 , S _5,3 ,
Processing operations a○, b○, and c○ are executed using S _5,4 and S _5,5 . By repeatedly executing such processing, each PE can regularly and continuously execute matching calculation formulas (1), (2), and (3) based on dynamic programming.

As described above, the input vector sequence C _u (u=1, 2,
..., l _c ) and cyclic transfer of n vector data strings, and input and cyclic transfer of the vector data c _i ^u (i=1, 2, . . . I _u ). vector data r _j in sync with
While inputting ^v (j = 1, 2, ..., N _v ) to each PE, each PE calculates calculation formulas (1), (2), (3) for each grid point.
By repeatedly executing , the processing for all grid points is completed.

Summarizing the above, PE when executing equations (1) and (2) is
The general processing operation (normal processing unit) is as follows.

a○ Vector data c _i (i=1, 2, ...,
At the same time as I) is input, vector data c _i-1 is transferred to the right-adjacent PE, and in synchronization with the transfer of these vector data, vector data r _j (j = 1, 2, ... N ) and execute the above equation (1) to find D _ij .

b○ Comparison operation mm [S _i-1 , _j , mm (S _j-1 , _j-1 , S _i , _j-1
)〕
Execute and add D _ij to this result to find S _ij .

c○ Execute the comparison operation mm [S _i-1 , _j , S _ij ) and transfer the operation result to the right adjacent PE, and at the same time, the comparison operation result mm (S _i , _j-1 , S _i+1 , _j-1 ) of the left neighbor
Input from PE.

a○ corresponds to the execution of calculation formula (1), b○ and c○ are calculation formulas
This corresponds to executing (2) and (3). Each PE is a○, b○, c○
When performing a○ simultaneously in the order of
When a PE performs a○ and b○, all PEs perform b○, and so on.

The fundamental difference between this operation and the operation of the two-dimensional array configuration lies in the data transfer operation when executing equation (2). In the operation of the two-dimensional array configuration, the cumulative results S _i-1 , _j-
1 to the left-adjacent PE and then performs the comparison operation mm(S _i , _j-
1 , S _i-1 , _j-1 ), in this operation, S _i-1 ,
Since _j-1 is in the same PE as S _i and _j-1 to be determined at the next time, the comparison operation can be performed without performing data transfer.

Note that when executing equation (4), at each PE,
``d○ Input the cumulative result from the adjacent PE, add twice the value of the distance between vectors executed within that PE, and output it to the adjacent PE'' one input/output operation and ``e ○ Enter cumulative results from adjacent PEs,
By performing two types of simple operations: ``adding and holding distances between vectors,'' cumulative results can be obtained regularly in the same way as described above.

As explained above, according to the present invention, the number of PEs does not depend at all on the positive integers I _u and N _v representing the number of each vector data to be processed, and is determined appropriately according to the expected amount of data processing. can be set to a value that
Matching calculations based on dynamic programming can be executed through pipeline parallel processing, which utilizes the hardware to the maximum extent possible by operating the PE at full capacity by repeating regular processing operations. Therefore, when realized on LSI, conventional positive integers I _u , N _v
Compared to a two-dimensional array configuration in which the number of PEs must be determined depending on n, the implementation scale is much smaller and the hardware can be used more effectively. In addition, the number of PEs is expandable in that no matter how many PEs are set, processing can be executed on vector data strings with arbitrary numbers of _Nv and _Iu .

Next, the efficiency of the two-dimensional array configuration and this configuration is
Let's compare the throughput per PE/unit time considering the average operating rate of PE.

The above processing operation in a two-dimensional array configuration,
The larger number of steps among the two processing units of and is Usquare, and the processing operations of this configuration are a○, b○,
The number of dynamic steps in the processing unit consisting of c○ is
Let's call it Uring. In a two-dimensional array configuration, to complete a matching operation based on dynamic programming on a set of vector data,
If we take the method of executing two types of processing units alternately, 2Usquare steps are required.
In the matching operation based on dynamic programming targeted here, PE _ij executes calculation formulas (1), (2), and (3) for one vector data string R to obtain the cumulative result S _ij . For example, PE _i ′ _j ′(i′＞
i, j'>j) is executing the above arithmetic expression, PE _ij does not need to execute processing on this vector data string R. Therefore, when processing is executed on a certain vector data string R _v , PEs that do not contribute to the processing are added to another vector data string.
It can be assigned to processing for R _v ′. In other words, while calculating the cumulative result S _ij for the first vector data sequence R ₁ , the cumulative result S _ij is also calculated for the second vector data sequence R ₂ with a phase difference of 2Usquare steps. can do. The number of dynamic steps required to obtain S _ij before obtaining the final operation results S _Iu and _Nv between the vector data sequence I _u and the vector data sequence R _v
Since (Nmax+Imax) steps are required in units of 2Usquare, (Nmax+Imax) types of final cumulative results S _Iu and _Nv can be obtained within the time of this (Nmax+Imax) step. On the other hand, in the configuration according to the present invention, the input vector data string C ₁ ,
By repeating the processing with the input vector data strings R ₁ , R ₂ ..., Rl _r for every n vector data strings of C 2 , ...Cl _c , the final cumulative results S _{Io , Nv} can be obtained. .

Based on the processing operations for the entire array as described above, processing is executed for all combinations of vector data C ₁ , C ₂ , ...Cl _c and vector data sequences R ₁ , R ₂ ...Rl _r . If we find the efficiency of PE in the case,
It will look like this:

In the case of a two-dimensional array configuration: To obtain l _r ·l _c final results, (Nmax+Imax+l _r ·l _c ) steps are required in units of 2Usquare. Since the number of PEs is Nmax・Imax,
PE efficiency n _sq is η _sq = l _r・l _c / (Nmax + Imax + l _r・l _c )・2Usquare/Nm
ax・Imax…(5) In the case of the present invention; The process of exchanging n input vector data strings using Uring as a unit is n steps, and the process executed while circularly transferring input vector data is ( _lr 〓 ^v=1 N _vo ) step. This is equivalent to processing the input vector data strings C ₁ , C ₂ , ... C _lc as one input vector data string, so to obtain l _r , l _c final results, Steps are required. The first term in equation (6) is the number of steps during circular transfer, the second term is the number of steps when exchanging data, and the third term is the number of steps at the start and end of processing. Moreover, rI= ^mon d _lc 〓 ^u=1 I _u . P.E.
Since the number is n, the efficiency ηring of PE is Here, the average value of N ₁ , N ₂ , ..., N _lr is N _av ,
Rewriting equation (7) by setting the average value of I ₁ , I ₂ , ..., I _lc as I _av , _lr 〓 ^v=1 N _v = lr・N _av , _lc 〓 ^u=1 I _u ＝le・I _av , ηring/η _sq = Nmax/N _av・Imax/I _av ; (1+Nmax+Imax/lrlc)/(1+n−rI/leIav+n
² /lcIav)・2Usquare/Uring...(8) The terms other than 1 in the denominator and numerator of the third term in equation (8) are related to the efficiency of starting and ending processing in each configuration. Therefore, during processing
The PE efficiency ratio is ηring/η _sq Nmax/N _av・Imax/I _av・2Usquare/Urin
It is expressed as g...(9).

Assuming that each PE in a two-dimensional array configuration has a means to perform input/output operations simultaneously, 2Usquare
Since Nmax>Nav _and Imax> _Iav , the configuration of the present invention is always efficient for two-dimensional array configurations, for example, when _Nav = 3/4Nmax, _Iav = 3/4Imax. is approximately 1.8 times more efficient. Additionally, if each PE only has a means to alternately execute input/output operations for each processing unit,
2Usquare<Uring, and the efficiency ratio of the present invention for a two-dimensional array configuration is even greater.

In the case of a two-dimensional array configuration, the minimum (Nmax ×
Imax) PEs must be arranged and connected, resulting in a very large implementation scale. Conventionally, the scale of each PE was reduced by executing input/output of each PE in bit serial format. things were being done. However, the data in the matching operation based on dynamic programming, which is the target here, is (1)
As shown in the formula, it is vector data that treats a data string of a certain number of dimensions as one piece of data, so when inputting and outputting data in bit serial format,
The number of transfer steps between PEs becomes very large, and the entire calculation takes a very long time. On the other hand, in this configuration, the number of PEs can be significantly reduced, so even if data transfer between PEs is realized using parallel transfer, there will be no problem with the implementation scale, and the dynamic It is unsuitable for processing vector data such as matching operations based on programming.

Although the above description has focused on the case of dynamic programming operations shown in equations (1), (2), and (3), the present invention is not limited thereto. When is Equation (4), it is similarly applicable to the execution of operations on all combinations of two types of variables and recurrence expressions with local dependence of data using the results of the operations.

〔Effect of the invention〕

As explained above, according to the present invention, processing elements each having a predetermined input/output means and calculation means are switched between a data transfer bus and an external input bus for exchanging data with adjacent processing elements. The system is connected in a ring via a multiplexer, and all processing elements simultaneously transfer their processing results to adjacent processing elements, which can be executed a predetermined number of times in parallel with the normal processing unit of each processing element. As a result, two methods, represented by matching operations based on dynamic programming,
Calculate calculations for all combinations of variables of different types and calculations of recurrence formulas with local data dependence using the calculation results in an appropriate manner according to the amount of calculations to be performed.
With an array configuration consisting of a number of PEs, it is possible to achieve highly efficient parallel processing while effectively operating each processing element.

[Brief explanation of drawings]

FIG. 1 is a diagram showing an example of the configuration of a conventional two-dimensional array processor; FIGS. 2a, b to 5 a, b are diagrams for explaining an example of its processing operation; FIG. 7 is a block diagram showing an example of the structure of each processing element, and FIG. 8 is a block diagram showing an example of the structure of each processing element.
FIG. 9 is a diagram for explaining an example of processing operation in the configuration shown in the figure. FIG. 9 is also a diagram for explaining data input from the outside and data transfer between processing elements. FIG. FIG. 3 is a diagram for explaining an example of a processing operation. 1, 31... Processing element, 2-1 to 2-n... Multiplexer, 3... External input data bus, 4,
11... External I/O bus, 5, 32... Data transfer bus, 6, 12... I/O terminal, 7, 8, 3
3, 34...Input vector data, 9...Final calculation result, 10...Control unit, 13,
14... Data transfer bus terminal, 15, 16... Buffer register, 17, 18... Register, 2
0, 21... Buffer memory, 22... Arithmetic unit, 23... Work memory, 24... Control unit, 26, 27... Address line, 28... Counter.

Claims (1)

[Claims] 1 n processing elements PE are arranged in a ring, and each processing element receives two types of external input data strings C=
{ci} (i=1,2,...,I) and R={rj}
Means for inputting each data ci, rj of (j=1, 2, ..., N), and means for performing desired operations such as addition/subtraction, comparison operation, and product-sum operation between two types of data and storing the results. and input data ci (i=1,2
..., I), means for transmitting and receiving calculation results between adjacent processing elements, and means for outputting the final calculation results to the outside, and between each processing element, input data ci from the outside is provided. is connected in a ring via a multiplexer that switches between a data transfer path and an external input path for exchanging data with adjacent processing elements so that the data can be input from any processing element, and all processing elements can input their respective processing results. is transferred to the adjacent processing element (m o ⁿ dN) times for each replacement of n consecutive pieces of input data in the input data string C, in parallel with the processing unit in each processing element. What is claimed is: 1. An array processor comprising means for controlling each of these processing elements.