JPH012176A - Product-sum calculation method - 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 Field of the Invention The present invention relates to a product-sum operation method in which time-series and spatially arranged data such as image data is multiplied by a coefficient corresponding to a certain distribution curve and then added.

Conventional technology A convolution integrator used for image data sharpening, spatial filtering, etc. sequentially captures n pieces of data from time-series and spatial array data, and applies a certain distribution curve to these n pieces of data. In the product-sum operation method, which multiplies each coefficient by a coefficient corresponding to , and then adds and outputs n data multiplied by a gold coefficient, the product of nlJ data and each coefficient is simultaneously calculated, and these are added. Then, the data is shifted by one, the product of the n shifted data and each coefficient is simultaneously determined, and these are added and output. In this case, since it is necessary to simultaneously multiply n pieces of data by respective coefficients, processing is performed using a systolic array of product-sum P# mouthpieces in which n multiplication processors are provided in parallel.

That is, the data strings are al, a2 . a3...am
.

. . . , and if n data are sequentially taken in and multiplied by 1-ko for each at the same time, then added t) and output Y, the product is The output Y of the summation unit is as follows.

The output Y1 of 1st [1 is Yl-=k a + k a + 3a3...
・・・ka ・・・・・・(1)n The second output Y2 is Y 2 −− k 1 a 2 +
k 2 a 3 -) k 3 a
a...+knan+1...
(2) The first output Yi is 1at for Y i = 2a for +, 3a for +1+.

・・・・・・＋ka−・・・・・・(3) nn ÷ huge 1 As mentioned above, n products of count and data must be calculated simultaneously, so n processors are used as multipliers. It uses systolic arrays arranged in parallel.

Problems to be Solved by the Invention However, the processor used as a multiplier is required to operate at high speed and is therefore expensive. Therefore, the disadvantage is that the more the number of coefficients to be multiplied, the more expensive the product-sum calculator becomes.

SUMMARY OF THE INVENTION Therefore, an object of the present invention is to provide a product-sum calculation method that can reduce the number of processors as multipliers and configure a product-sum calculation unit at a low cost.

Means for Solving the Problem In the product-sum operation method of multiplying corresponding data by n coefficients and adding n multiproducts, each () - ta of the data string is input while being shifted, and the input data is It has n/d processors that multiply the output of each processor by a coefficient, and has a block array that multiplies the output of each processor and outputs the output.
It has an adder that processes the output of the Iztusa array and the stored value of the address of the intermediate storage corresponding to each shift, and an intermediate storage that stores the output of the adder for each shift in the corresponding address, The same data string is processed by the above processor.
The data is input to the array six times, and each time the data string is input, the coefficient value set in each processor is changed to a predetermined value, and each time the data string is input, the data is read from the intermediate storage and [ The pile of output from the record is n
/d cycles tI'ii, and the output of the above adder for the sixth time is n
By configuring the present invention to output the result of adding the products of coefficients and data, the number of processors serving as multipliers for multiplying data by coefficients is reduced, thereby solving the above problem.

The operation data string is a, a, a3..., the processor array's output? Assume that the number of tufts is n/d == rrl, and at first, each processor has 2.・
...When k is set and a data string is input (
(Hereinafter, inputting all data strings a, a2, a3, . . . to the processor array is called a pass).

The output P1-1 of the first cycle of the adder is as follows (note that the values stored at each address of the intermediate storage are cleared to rOJ during initialization).

1) 1-1=to 1a1+to 2a2+river...+kIllaI
This output P1-1 is then stored as 1 in the corresponding address of the intermediate storage. Then, in the next shift period after the input data is shifted, the output P1 of the adder is
~2 is Pl-2- to 1a2+ to 2a3+ °°°゛°°klall. 1 and is stored at the corresponding address in the intermediate storage as 2. Processing is performed in the same manner thereafter, and in the first cycle, the output P1-i of the adder is as follows.

1a to Pl-i-, ai+1+”” ”” to Pl-i-
km a i+a-f And this value '1-i is the address A of the intermediate storage
stored in i.

Thus, the data strings a1, a2, etc. to be subjected to the product-sum operation
After completing the shift of ..., the coefficients of each processor in the block [1 setter array are kIIl+1~2]
Ilk: Change data string a again.1. a2...
... is input to the processor array and the same processing as described above is performed.

That is, in this second pass, the reading and writing of data from the intermediate storage is delayed by m cycles, and the address A1 of the intermediate storage is sequentially changed from shift 1 to the m+ith shift.
The data is read out, the output value of the processor array at the time of shift of 1 is added to this data m+1 times, and the sum is stored in order starting from address A1.

That is, at the time of the first shift from m in the second data input, the output P2-1 of the adder becomes as follows.

P2-1-'-[)1-1 ki+1 am+1
10k11) 2 al11+2-1°""" 2n+
82m = ka 10ka +...-...+k
2. a...

Then, in the next shift period, P −P +k a 10, ll+2am, 3
2-2 1-2 m÷1111÷2” ”’ ”
・k2m a2m+ 1 = k 1 a 2 + k 2 a 3+”” ”'
10 to 2i a2m+ 1 Also, in the period of the i-th shift, P2-i ” Pl-i 10k111) 1 a
II++i+ k a ・°= =゛+ k 2
．． a 2Il+H-11+2 l+1+1 -- k 1 a 1+ k 2 a i+1""""
k2ma2a+i-1, and the outputs of these Kaaku devices P2-2...
P2-+... are intermediate storage addresses A2 and 2, respectively.
. . . Stored in Δi . . .

Processing is performed in the same manner thereafter, and in the final data input 5, that is, at the d-th pass, the coefficients to be set for each processor of the setter array are set to k, k.
・・・・・・ko (dm=n so n-11+I
n-1 ÷ 2, m coefficients are set in one pass, and at the dth time, the last prorena of the processor array has kdl, 1=kn
is set), reading and writing data from the intermediate storage 1-storage is delayed by (d-1)m cycles, and the addresses of the intermediate storage are set sequentially from the (d-1)m+1st shift. Read data from A1, add it to the output of the processor array, and output it as an output.

That is, the first output Y1 is as follows.

Yl"Pd-1"" p(d-1) -1+kn-m
+1” a (d-1)l+1+ kn-142a
(d-1)+2”' ””+kna (d-1
)e+m= pl al + k2 a2 =-°”
+ k(d-1)m+k a ” a(d-1)s n-a+ (d-
1) sul”” ”” 10kna a(d-1)its”
-k 1 a 1 -k 2 a 2 +
°°゛ °゛° k n-I a n-steel...
・ka” kn-m+I n-m+I n.

= k a 10k a t・・・・−tk
n aol 1 2 2 (4) Similarly, the output Yi in the period of the i-th shift is expressed by the following equation (5).

Yi""'-P(d-1)-i+kn-t)1d-+"" (d-t)m+i+ kn-m+2 a(
d-1) m+country+”' ”” n E”(d-1)a+
i+ 1-1- 1at 10-2 ” tit ”””
kn an+i-1...(5) The above equations (4) and (5) are the equations (1) and (3), respectively.
) is the same as the formula, and a sum-of-products operation is performed to obtain the output by sequentially taking in 11 data from the data string, shifting l-L, multiplying each data by a coefficient of 1 to kn, and adding the products. It means something.

The embodiment diagram is a block diagram of one embodiment of the present invention, and 1 is a memory configured with a dynamic RAM etc. in which time-series or spatially arranged data to be processed such as image data is stored. , there are 256 memory cells that store 8-bit data for one pixel when the object is scanned by a CCD camera, etc., and 256 x 256 memory cells are provided for 25611 scans. has been done. 2 is a processor array in which a large number of processors are arranged as multipliers that multiply each piece of data 1 to be processed by a coefficient corresponding to a distribution curve, and at least 6 shift registers that sequentially shift each piece of data 1 to be processed. , a coefficient storage section for storing coefficients, a coefficient switching f stage for switching coefficients, and a q adder for adding up the output of each processor, that is, the product of data and coefficients. 3 is an adder that adds the output of the processor array 2, that is, the sum of the products of each data and coefficient, and the data stored in the intermediate storage 4; 4 is an intermediate until output as the output Y of the product-sum operation; Intermediate storage 5, 6.7 is a gate circuit for temporarily storing data at a processing stage. Then, the input of data from the processed data 1 to the processor array 2, the processing of data in the TSAR array 2, the multiplication, the addition processing, the switching of coefficients, the addition processing of the adder, the gate 5.6. 7
control, and write data to intermediate storage 4.

Control of reading and the like is performed by microprogram control by a III control device (not shown).

For a group of data strings to be processed on which a product-sum operation is to be performed, for example, in the above image data, data strings for 256 pixels for one scan are sequentially shifted. For n pieces of data, multiply the coefficient corresponding to the distribution curve by 1 to kn, add the product, and calculate the output Y as shown in equations (3) and (5). a, +k a, 10-koao,.

1 1 2 1+1 (i=1.2.3...) In the present invention, the number m of processors to be integrated is n/d (d is a divisor of n). ), the data string input to the processor array 2 is passed (input) six times. In this embodiment, n=4. d=2. Assuming that m=4÷2=2, the number of processors in the array 2 is 2, and there are 4 a, aH+3 (i-1.

data ai ・ai+1 ・++2 2.3...), coefficient k, k, 3, respectively
．． By adding various products multiplied by 4, we obtain the product-sum operation n shown in the following equation 6.
The case where this is done will be explained below.

Y + = 1 a H+ k2 a country + k3a
++2→-4ai+3...
(6) First, set the coefficients to 2 for each of the two processors of the processor array 2, and calculate a group of data a-, a2, etc. by product-sum operation n'TJ from the data to be processed 1.・
・Input while shifting sequentially to the blow array. For example, 256 pixel data a "a256"
When inputting to the array, first, the two processors of the processor Φ array 2 each have a1. a2 is input and the relation r! set for each processor υ! ik, k and this data a 1. a 2 (7) 梢k 1a 1. k
2 a 2 is calculated, added, and output. This output 1a1→・k2a2 is input to the adder 3 and added to the data from the intermediate storage 4, but during the first data pass, the gate circuit 5.7 is closed and the gate circuit Only 6 is controlled by microprogram control method.
The signal S1 is input from the device and is delayed, and as a result, the adder 3 outputs 1 to the output of the 4j.7 ray 2.
Output 2a2 to a1+ through output P.

Pl-1-= kl a1+ k2a2 ””
(7) This output P1-1 is written to the address A1 of the intermediate storage 4 via the gate circuit 6.

Then, the data is shifted by one, and the data of a 2 and a 3 is input to each processor of the processor array 2, and this data is given a coefficient of 1. are respectively multiplied by 2, added, and output from the grosser array 2. As a result of step A, there is no data from the intermediate storage 4, so the output P1-2 of the adder 3 becomes as shown in the following equation (8) and is stored at address Δ2 of the intermediate storage 4.

P 1-2 = k 1a 2 + k2a 3""...
(8) In this way, data a, a2, etc. are sequentially shifted, each coefficient is multiplied by 2, and the sum of the two products is stored in each address of the intermediate storage 4. , in the i-th period, the adder output P1-i
is expressed as the following equation (9) and is stored at address Ai of intermediate storage 4.

P, = k a, + to 2ai + t -...
...<9>1-tl+ If all the data to be subjected to the multiply-accumulate operation are passed to the processor array once, for example, in the image data example above, all 256 pixel data will be passed. Then, the calculations ll1p -p of the sum of products operation in the first pass are stored in A1 to A256 of the intermediate storage 4, respectively.

(Note that the calculated value P has no meaning, so it is not actually stored.) Next, change the coefficients set for each processor in the processor array to 4, and block the same data string again. Let Morguchina Array 2 bus.

In this case, in the first cycle, the output of the pro U-tree array 2 is 3a1-k, s a 2,
It will be input to the adder 3, but at this time, all the circuits are closed and the output P of the adder 3 is
=, k a −+−, 4a2 is the intermediate st−L/−
It is not input to Y4, nor is it output as output Y. Then, the data is shifted by one] and the output of the adder in this period is P ・−k 3a 2 +k 4a
3 is not input to the intermediate storage 4, and the output Y is not outputted either. Then, from the third cycle delayed by two cycles II, that is, the number of blocks in the processor array 2 (m=
From the next cycle delayed by 2), S, S
3, the gate circuit 5.6 is opened, and from the 3rd period, the adder 3 receives data P = k a + 2a as shown in equation (7) stored at the address A1 of the intermediate storage 4.
Run 1-11 without entering 2.

As a result, in the adder 3, 4a4 and the value P1-1 of the product-sum operator of the first cycle of the first bus are added to the sum of products k a + output from the processor array 2, and this is added to the sum k a + of the products output from the processor array 2. It is output via circuit 7 as output Y1.

That is, Yl = P2. ==P1. + to 3a3+ to 4a4=to 1
a1+ to 2a2+ 3a3 + to 4a4 (10) In the next cycle, the output of processor array 2 is 3a4+ to 4a5 and the data P1- stored at address A2 of intermediate storage 4
2 is added and the next output Y2 is output.

Y2==P=P+k
a +k 4 as=-k 1a 2 +
k 2 a 3+ k 3a a + k 4a s (11) Similarly, in the i-th period, the output k a of processor array 2 is 4a, and the intermediate 3 1+
2 Data P1-i stored at address Ai of storage 4
are added and the next output Y1 is output.

Yi==P --=P ・+3a1+22-+
1-+ + k 4 a 1 +3 = k a, + 2a, +1 10 kaai + 20 4a1 + 3 ...... (11) (i=1.2...) That is, the (th) Equation 11) and Equation (6) are the same, and 4a.
, ai+3 (i six data ai , ai+1 , ++21.2...
...and the above 256 pixel data is Y254'~Y
Since 256 has no meaning, i=1 to 253.

) to each coefficient of 1. 2. is multiplied by 3°k4, and the sum of the products is output for each cycle.

In the above embodiment, the number n of data to be subjected to the product-sum operation is 4 degrees, and the number m of processors is 2 degrees. The number of times d of busing the data string was set to 2, but the number of data n was set to 6. Let the number m of processors be 2. If the number of times d of busing the data string is 3, then during the first bus, the values summed by the products in the processor array 2 and the adder 3 are stored in the order of addresses A 1 J: of the intermediate storage, and the values are transferred twice. When the bus is opened, the number of processors is 2 (
Gate circuit 5.6 from the third period after delaying by = m)
, the adder 3 adds the output of each processor in the third cycle and the data at address A1, and stores it at address A1.
The following groups are sequentially read from address A2 of the intermediate storage every cycle, the data stored at the address and the output from each processor in the processor array are added, the output of adder 3 is written to the read address, and the third bus In some cases, the circuit is delayed by two more cycles, that is, mX2=2X2=4 cycles, and from the fifth cycle, the circuit 5.7 is opened and the address Δ
1, the stored data may be sequentially read out, and the adder 3 may add the output from the processor array at each shift to the read stored data, and the output Y may be output in sequence.

That is, the number n of data to be subjected to the product-sum operation is divided by the number m of processors provided in the processor array 2, the data string is bused only n/m = 6 times, and in the first bus, the data string is bused to the processor array 2. The sum of the products of each data and coefficient from each processor is stored in each address of the intermediate storage 4,
On the second bus, reading and writing from address A1 of intermediate storage 4 are performed with a delay of several m of processors, and the output of processor array f and the read from intermediate storage are added to Q, and the output from intermediate storage 1 to storage Δ1 is From then on, address Δ1 of intermediate storage 4 is stored for each path.
It is only necessary to sequentially read out the signals from 1 and 2, delay the input timing sequentially by the number of processors m, and output the output of the adder 3 through the circuit 7 at the time of the last bus.

As a result, compared to the sum-of-products method, which has a number of 1s equal to the number of data n, the processing time will be d times as much.
The number of processors is n/d, which allows the number of expensive processors to be reduced.

Effects of the Invention As described above, the present invention can perform multiplication processing using a smaller number of processors (a divisor of the number of data) than the number of data that performs processing. The number of processors required can be reduced, and the product-sum calculation can be performed using inexpensive equipment.

[Brief explanation of the drawing]

The figure is a block diagram of one embodiment of the present invention. 1... Processed data, 2... Processor array,
3...Kakuchi device, 4...Intermediate storage, 5,6.7
...Gate circuit.

Claims (1)

[Claims] In the product-sum calculation method in which n coefficients are multiplied by corresponding data and the respective products are added, each data in a data string is input while being shifted, and there are n/d processors that multiply the input data by a coefficient. , a processor array that adds and outputs the output of each processor, an adder that adds the output of the processor array and the stored value of the intermediate storage address corresponding to each shift, and the output of the adder for each shift. and intermediate storage for storing data at corresponding addresses, input the same data string to the processor array d times, and change the coefficient value set in each processor to a predetermined value each time the data string is input. Then, for each data string input, reading data from the intermediate storage and writing the output from the adder is delayed by n/d cycles, and the output of the adder is calculated as the result of adding the product of n coefficients and data. A product-sum calculation method that outputs as .