System for Calculation of Sum of Products by Repetitive Input of Data

(a) Field of the Invention

The present invention relates to a system for calculation of a sum of products in which data items of a time- or space-based array such as image data are multiplied individually by coefficients corresponding to a distribution curve and then the products obtained are added together.

(b) Description of the Related Art

There exists several known systems for calculation of a sum of products, such as a convolution integrator used for enhancement of the sharpness of image data, spatial filtering and the like, wherein n data items are sequentially fetched from a time-or space-based array of data and are multiplied individually by coefficients corresponding to a distribution curve. The n data multiplied by the coefficients are then added to output the sum. In such a system, the products of the n data items and the respective coefficients are obtained at one time, then added together, and finally the sum of the products is output. Subsequently, the data items are shifted, so that the shifted n data items can be multiplied by the corresponding coefficients. The obtained products are added together, and the sum is output. The operation described is executed successively. In this case, the n data items need to be multiplied at one time by their corresponding coefficients. To this end, an arithmetic unit for the sum-of-products operation of a systolic array type is used having n processors which are arranged in parallel for multiplication.

Assuming that n data items are fetched sequentially from a sequence of data a.sub.1, a.sub., a.sub.3, . . . a.sub.m, . . . and are multiplied at one time by coefficients k.sub.1 to k.sub.n, respectively, the products obtained are added together, and the sum is delivered as output Y. In this case, the output Y of the arithmetic unit for sum-of-products operation is as follows:

Output Y1 obtained first is

Second output Y2 produced next is

and i-th output Yi is

Since the products of the n data items and their respective coefficients must be obtained at the same time, a systolic array is employed in which n processors serving as multipliers are connected in parallel. 4

The processors which are used as multipliers are required to perform at high-speed and are therefore expensive. Consequently, there is a problem in that if the number of coefficients to be multiplied is large, the arithmetic unit required for sum-of-products operation becomes very expensive.

It is therefore an object of the present invention to provide a system for calculation of a sum of products in which the number of the processors used as multipliers is reduced. Accordingly, the system provides an inexpensive arithmetic unit for the sum-of-products operation.

To achieve the above object, the present invention provides a system for calculation of the sum of products in which n coefficients are multiplied by corresponding data items and the products obtained are then added together. The system comprises a processor array including n/d processors to which data items of a data sequence are input while being shifted. The processors multiply the input data items individually by the coefficients. The processor array adds together the outputs of the processors and outputs the sum obtained; an adder for adding the output of the processor array to a value stored in an intermediate storage unit which corresponds to a respective shift; and the intermediate storage unit stores the output of the adder in an address thereof corresponding to a respective shift. The same data sequence is input to the processor array d times, and the coefficients set in the processors are varied to respective predetermined values each time the data sequence is input. The reading of data from the intermediate storage unit and the writing of the output supplied from the adder being delayed by n/d cycles each time the data sequence is input. The output of the adder is then the result of addition of the products of the n coefficients and the data items.

Assuming that the sequence of data to be processed is a.sub.1, a.sub.2, a.sub.3, . . . , and that the number of processors in the processor array is n/d=m. According to the present invention, first, coefficients k.sub.1, k.sub.2, . . . k.sub.m are set in respective processors, and the data sequence is input (hereinafter the term "pass" is used to indicate inputting of the data sequence a.sub.1, a.sub.2, a.sub.3, . . . to all the processors). The output P.sub.1-1 of the aforementioned adder in the first cycle is as follows. (Meanwhile, the values stored at the individual addresses of the intermediate storage unit have been cleared to "zero" by initialization.)

The output P.sub.1--1 is stored in the intermediate storage unit at a corresponding address A1. In the subsequent cycle after a shift of the input data, the adder delivers the output P.sub.1-2 :

This output is stored in a corresponding address A2 of the intermediate storage unit. This operation is repeated thereafter and, in the i-th cycle, the adder produces the output P.sub.1-i :

The output P.sub.1-i is stored in the intermediate storage at the address Ai.

Upon completion of all the necessary shifts of the data sequence a.sub.1, a.sub.2, . . . which is to be subjected to the sum-of-products operation, coefficients k.sub.m+1 to k.sub.2m corresponding processors of the processor array. The data sequence a.sub.1, a.sub.2, . . . is again input to the processor array so that the above-described operation is executed. In this second pass, the reading and writing of data from and into the intermediate storage unit is delayed by m cycles. That is, from the (m+1)th shift, data starts to be read from the intermediate storage, sequentially from the address A1. The data read from the address A1 is added to the value output from the processor array at the time of the (m+1)th shift. The sum obtained is then sequentially stored in the intermediate storage unit beginning at the address A1.

More specifically, in the second pass, output P.sub.2-1 of the adder in the (m+1)th shift is ##EQU1## The output in the next cycle is ##EQU2## and the output obtained in the i-th cycle is ##EQU3## These outputs P.sub.2-2 . . . P.sub.2-i of the adder are respectively stored at the addresses A2 through Ai of the intermediate storage unit.

The above-described operation is repeated thereafter and, at the time of the last data input, i.e., in the d-th pass, coefficients k.sub.n-m+1, k.sub.n-m+1 . . . k.sub.n are set in the respective processors of the processor array (since d.multidot.m=n, m coefficients are set in one pass, and accordingly in the d-th pass, coefficient k.sub.dm =k.sub.n is set in the last processor of the processor array). In this case, the reading and writing of data for the intermediate storage unit is delayed by (d-1)m cycles. Thus, it is from the (d-1)m+1 shift that data starts to be read from the intermediate storage unit, sequentially from the address A1. The data read is added to the output of the processor array. The sum is output from the adder as output Y. Accordingly, the output Y1 obtained first is ##EQU4## Output Yi obtained in the i-th cycle is given in the following equation (5): ##EQU5##

The above equations (4) and (5) are This means that a sum-of-products operation was performed by multiplying n data items fetched sequentially from the data sequence by the coefficients k.sub.1 to k.sub.n, respectively, while shifting the data items, and by summing the products obtained.

As described, according to the present invention, a sum-of-products operation can be performed with processors whose number is smaller than the number of data items to be subjected to sum-of-products operation (the number of the processors is a measure of the number of the data items). Thus, the processors used for multiplication, which are costly, can be reduced in number, and sum-of-products operations can be executed with an inexpensive unit.

FIG. 1 is a block diagram illustrating a principal part of an apparatus to which a sum-of-products calculation system is applied according to an embodiment of the present invention.

In the accompanying drawing, reference number 1 denotes a memory, such as a dynamic RAM or the like, which stores a time- or space-based array of data to be processed, such as image data. In the case of image data, for example, 256 memory cells each for storing 8-bit data corresponding to one picture element are assigned for one scanning of an object by a CCD camera or the like, and 256.times.256 memory cells in total are provided for 256 scannings. Designated at 2 is a processor array which includes a plurality of processors serving as multipliers for multiplying items from memory 1 individually by coefficients corresponding to a distribution curve. The processor array 2 comprises, in addition to the processors, shift registers for sequentially shifting data to be processed, a coefficient memory area for storing the coefficients, coefficient switching means for switching the coefficients, and an adder for summing up the outputs of the processors (i.e., the products of the data items and the coefficients). Reference numeral 3 designates an adder for adding the output of the processor array 2 (i.e., the sum of the products of the data items and the coefficients) to the data stored in an intermediate storage unit 4.

The intermediate storage unit 4 serves to temporarily store data which is obtained during intermediate processing prior to output of the result Y of a sum-of-products operation. Reference numerals 5, 6 and 7 denote gate circuits. The processing of the present invention includes inputting data to the processor array 2 from the memory 1; shifting, multiplying, and adding the data; switching of the coefficients in the processor array 2; controlling the gate circuits 5, 6 and 7; and controlling the writing and reading to and from the intermediate storage unit 4. Such processing is executed by a control apparatus, not shown, in accordance with a microprogram.

A sum-of-products operation is performed on a sequence of data items. For example, in the case of the image data mentioned above, a data sequence a.sub.1, a.sub.2, . . . corresponding to 256 picture elements for one scanning, the sum-of-products operation is performed by multiplying n data items individually by coefficients k.sub.1 to k.sub.n corresponding to a distribution curve while shifting the data sequence and by summing up the products obtained to produce the output Y, as shown in equations (3) and (5).

According to the present invention, the number m of the processors used for multiplication is set to n/d (where d is a measure of n) and the data sequence is passed (input) d times. In this embodiment, explanation is given on the assumptions that n=4, d=2, and m=4/2=2. Accordingly, the number m of the processors in the processor array 2 is equal to 2. Four data items a.sub.i, a.sub.i+1, a.sub.i+2, a.sub.i+e (i=1, 2, 3, . . . ) are multiplied individually by coefficients k.sub.1, k.sub.2, k.sub.3 and k.sub.4, and the products obtained are added together, thereby performing the sum-of-products operation as shown in equation (6).

First, the coefficient k.sub.1 and k.sub.2 are set respectively in the two processors of the processor array 2, and the data sequence a.sub.1, a.sub.2, . . . , which is to be subjected to a sum-of-products operation, is sequentially input to the processor array 2 from the memory 1 while being shifted. In the case where data of 256 picture elements a.sub.1 -a.sub.256 is input to the processor array, for example, first, data items a.sub.1 and a.sub.2 are input to the two processors of the processor array 2 to be multiplied by the coefficients k.sub.1 and k.sub.2 respectively set in the processors. The obtained products k.sub.1 a.sub.1 and k.sub.2 a.sub.2 are added together and output. The output k.sub.1 a.sub.1 +k.sub.2 a.sub.2 is applied to the adder 3, to be added to the data from the intermediate storage unit 4. In the first pass, however, the gate circuits 5 and 7 are closed, and only the gate circuit 6 is opened by application of a signal S1 from the control apparatus of a microprogram control unit. As a result, the adder 3 delivers the output k.sub.1 a.sub.1 +k.sub.2 a.sub.2 of the processor array 2 as its output P.sub.1-1.

The output P.sub.1-i is delivered, through the gate 4 circuit 6, to the intermediate storage unit 4 and written in the address A1.

Next, the data is shifted so that data items a.sub.2 and a.sub.3 are input to the respective processors of the processor array 2 and multiplied by the coefficients k.sub.1 and k.sub.2, respectively. The products obtained are added together, and the sum is output from the processor array 2. Since at this time the adder 3 has no data input from the intermediate storage unit 4, it delivers output P.sub.1-i z, shown in equation (8), which is stored at the address A2 of the intermediate storage unit 4.

In this manner, the data items a1, a.sub.2, . . . are multiplied sequentially by the coefficients k.sub.1 and k.sub.2 as the data items are shifted. The sum of the two products is then stored in the corresponding address of the intermediate storage unit 4. Consequently, in the i-th cycle, the output P.sub.1-i : of the adder 3 is

This output is stored at the address Ai of the intermediate storage unit 4.

When all the data items to be subjected to sum-of-products operation are passed once to the processor array, for example, when image data corresponding to all of the 256 picture elements is passed, the calculated values P.sub.1-1 to P.sub.1-256, obtained by the sum-of-products operations of the first pass, are stored respectively in the addresses A1 to A256 of the intermediate storage unit 4. (In practice, the calculated value P.sub.1-256 is not stored because doing so is meaningless.)

Subsequently, coefficients k.sub.3 and k.sub.4 are set in the respective processors of the processor array 2. The same data sequence is then passed to the processor array 2 again. In this case, the output of the processor array 2 in the first cycle is k.sub.3 a.sub.1 +k.sub.4 a.sub.2, which is input to the adder 3. At this time, all the gate circuits are closed so that the output P.sub.2-1 =k.sub.3 a.sub.1 +k.sub.4 a.sub.2 of the adder 3 is neither input to the intermediate storage unit 4 nor delivered as the output Y. Then, the data is shifted and, also in this cycle, the output P.sub.2-2 =k.sub.3 a.sub.2 +k.sub.4 a.sub.3 of the adder 3 is not input to the intermediate storage unit 4 or delivered as the output Y. From the third cycle, which is delayed by two cycles (i.e., from the cycle delayed by the number of cycles equal to the number (m=2) of the processors in the processor array 2), the control apparatus delivers signals S2 and S3 to open the gate circuits 5 and 6. Consequently, in this third cycle, the data P.sub.1-1 =k.sub.1 a.sub.1 +k.sub.2 a.sub.2 is stored in the address A1 of the intermediate storage unit 4, shown in equation (7), is applied to the adder 3.

As a result, the adder 3 adds the sum of products, k.sub.3 a.sub.3 +k.sub.4 a.sub.4, output from the processor array 2, to the value P.sub.1-1 which is obtained by the sum-of-products operation performed in the first cycle of the first pass. The resulting sum is delivered as the output Y1 through the gate circuit 7. ##EQU6##

In the next cycle, the output k.sub.3 a.sub.4 +k.sub.4 a.sub.5 of the processor array 2 is added to the data P.sub.1-2 stored in the address A2 of the intermediate storage unit 4, and the sum is delivered as output Y2. ##EQU7##

Similarly, in the i-th cycle, the output k.sub.3 a.sub.i+2 +k.sub.4 a.sub.i+3 of the processor array 2 is added to the data P.sub.1-i stored in the address Ai of the intermediate storage unit 4. The resulting sum is delivered as output Yi. ##EQU8##

It is noted that equation (12) is equivalent to equation (6). This indicates that the four data items a.sub.i, a.sub.i+1, a.sub.i+2 and a.sub.i+3 are respectively multiplied by the coefficients k.sub.1, k.sub.2, k.sub.3 and k.sub.4 (i=1, 2, . . . , and in the case of the above-mentioned image data corresponding to 256 picture elements, i=1, . . . 253, since Y254 to Y256 are meaningless) and the resulting sum of the products is output in each cycle.

The foregoing embodiment was explained on the assumption that the number n of data items to be subjected to sum-of-products operation is 4, the number m of the processors is 2, and the number d of times the data sequence is passed is 2. Now, assume that the number n of the data items is 6, the number n of the processors is 2, and that the number of times d for passing the data sequence is 3. In this case, during the first pass of the data sequence, the sums of products, which are obtained by the processor array 2 and the adder 3, are stored in the intermediate storage sequentially from the address A1. Then, in the second pass, the gate circuits 5 and 6 are opened from the third cycle, which is delayed by the number of cycles equal to the number of the processors (i.e., m=2) Therefore, in the third cycle, the adder 3 adds the output of the processor array 2 to the data read from the address A1, and the sum obtained is stored in the same address A1. In the following cycles, the data stored in the intermediate storage unit 4 is sequentially read out in order beginning with the address A2 and added to the corresponding output from the processor array 2. The resulting output of the adder 3 is stored in the corresponding address from which data has just been read out. In the third pass of data sequence, the gate circuits 5 and 7 are opened from the cycle which is further delayed by two cycles, i.e., from the fifth cycle delayed by m.times.2=2.times.2=4 cycles. Hence, the stored data is read sequentially from the address A1 and added by the adder 3 to the output from the processor array 2 for each subsequent data shift. In this manner, the output Y is delivered sequentially.

As will be noted, the number n of data items to be subjected to the sum-of-products operation is divided by the number n of processors provided in the processor array 2, and the data sequence is passed n/m=d times. In the first pass of the data sequence, the sum of the products of the data from the processors of the processor array 2 and the respective coefficients are stored in the corresponding address of the intermediate storage unit 4. In the second pass, the reading and writing of data from and to the address A1 of the intermediate storage unit 4 are delayed by the number of cycles equal to the number n of the processors. The output of the processor array 2 is added to the data read from the intermediate storage unit 4, and the resulting sum is stored in the intermediate storage unit 4 sequentially from the address A1. In the subsequent passes, the reading and writing of the data from and to the address A1 of the intermediate storage 4 are further delayed by the number of cycles equal to the number of the processors. In the last pass, the output of the adder 3 is output through the gate circuit 7 as the sum-of-products output Y.

Thus, although the process time is d times longer than that of a sum-of-products calculation system including processors whose number is equal to the number n of data items, the present invention enables the reduction in the number of processors required, which are expensive, to n/d.

The many features and advantages of the invention are apparent from the detailed specification and thus it is intended by the appended claims to cover all such features and advantages of the invention which fall within the true spirit and scope thereof. Further, since numerous modifications and changes will readily occur to those skilled in the art, it is not desired to limit the invention to the exact construction and operation illustrated and described, and accordingly all suitable modifications and equivalents may be resorted to as falling within the scope of the invention.