JPS60175181A - Parallel inner product operating method - Google Patents

Abstract

PURPOSE:To find out the inner product of the optional number of data having optional bit length by executing AND operation and total addition by an arithmetic element in which a control register is set up and executing half addition by an arithmetic element in which no control register is set up. CONSTITUTION:The product AB of a multiplicand A and a multiplier B is outputted from the right end of a multiplying circuit 120. To remove the influence of left end inputs d0-d3, f0, only upper 4X4 cells are set up in a register as ''1''. Although a multiplying circuit 121 is a similar circuit as the circuit 120, the circuit 121 finds out the product CD and also outputs the sum AB+CD from the right because the output, i.e. the product AB, of the circuit 120 is sent from the left side. Multiplying circuits 122-123 have similar functions. Consequently, the inner product AB+CD+EF+GH to be found out is outputted from the circuit 123, propagated through residual cells and finally outputted from the lower right of a parallel data processor.

Description

DETAILED DESCRIPTION OF THE INVENTION [Technical Field of the Invention] Jin's invention relates to an arithmetic method for performing inner product calculations at high speed using a parallel data processing device.

C. Prior Art] A conventional arithmetic method for performing this type of inner product calculation is a method using a circuit in which a plurality of multipliers each having a nine combinational circuit including an addition function are combined. For the sake of explanation, we will now consider an array type multiplier as a multiplier with these functions. 1st
The circuit (1) shown in the figure is a full adder (Full Adder).
') and gives the following function regarding the input Xs 7e El output s, c.

θ−X■y■2 0! x-y'+y-g+Z-X However, ■ represents an exclusive OR, . represents a multiplication, and + represents a smear. By regularly arranging the full adders (1) as shown in FIG. 2, an array type multiplier is constructed. That is, circuits 1 to 2 in FIG. 2 are all circuits similar to the full adder (1) in FIG. 1.

Here, the binary number without the sign is []2 ”n-lXn-2°°°XO I will express it as Namely.

[Xn-I In-2...' Xg ]2= Xn-I
X 2 n-' + In-2X 2°-2+...
+x oX2°-Σx121. Based on this representation, the multiplier in FIG.

Multiplicand A ” Ca , S a 2 &1a o ]
22 multiplier B! [b3b2b1bo]2 Number to be added P=rp7p6p5p4p,, p2p1
p□)2Q-rq,,q2q1qo)2 Result R” [rBr 7r6r5r4r45r2r1
Using rg12, it becomes R error AB+P+Q. That is, in the full adder circuits (21 to aη), the partial products created from the multiplicand and the multiplier are manually input, and the sum (S) and one-digit increment (0) from each full adder are sequentially propagated. , products are calculated.Full adders 08 to r2υ do not receive partial product inputs, and perform only carry propagation to calculate the final product.Also, full adders (21 to (51, +61
．． flQ, (141,(lie) does not have the sum (S) and carry-up (c) from the upper row, so the numbers P and Q to be added are input according to each digit.Now, this array type To consider performing inner product calculations using multipliers.

As an example, use the inner product below. In other words, the inner product that can be claimed is 8
and '.

B - AB + CD + EF + GH...
・■However, A ” CFLs &2&1ao]2B =
Cbs b21) 1 bo ]2C-CC, % C2
C1Q o ] 2D −Cdy, d 2 d, d
o ) 2 Ce 2 e113 o ] F
"" Cf 3 f 2 fl fo ] 2G-1"
g3g2g1go12. n=[h3h2h1ho)2
B ”” (898687E1685'841i138
28180)2 In this case, four array type multipliers τ shown in FIG. 2 are prepared. First, A and B are input as the multiplier and multiplicand of the first multiplier, and since they are added, 0 is input into the corresponding part. That is, the product AB is obtained at the output of the first multiplier. Next, the multiplier of the second multiplier, O, D as the multiplicand
is input, and the output of the first multiplier is input to the part corresponding to the number to be added. As shown in the example of Figure 2, this number to be added is P.

Q, there are two numbers, but in the second multiplier P
side, and the Q side is set to 0. As a result, AB + CD is obtained at the output of the second multiplier. Similarly, for the fourth multiplier, the output results of the second and third multipliers are input as the numbers to be added, and the multiplicand 9 and the multiplier are each E? , G and H, the inner product S can be served as the output of the fourth multiplier.

As described above, an arithmetic circuit for calculating an inner product can be obtained by preparing the array type multiplier shown in FIG. 2 as many as the product terms of the inner product and interconnecting them. however,
These have the following drawbacks. As an example, consider the case where the data length expressed by the above equation 0 is all 4 bits and the number of data is 81 (the number of product terms is 4).

(1) If even one data length exceeds 4 bits, the data of the inner product to be calculated will be divided into 4-bit units and the multiplier shown in Figure 2 will be used many times.
Retrieving data and setting data requires wasted time.

(21) Conversely, even if the data length is 1, for example all 2 bits, which is half the length, the number of data is limited to 8 and half of one multiplier is unused. In other words, usage efficiency deteriorates.

The above points apply only when the 1 multiplier is an array type multiplier.

Note that this does not apply to any combinational multiplier.

[Summary of the invention]

This invention has been made to solve these drawbacks, and provides an arithmetic method that can perform inner product calculations consisting of any number of product terms of any data length at high speed using a parallel data processing device defined below. It is something.

[Embodiments of the invention]

Embodiments of this invention will be shown in the drawings below and will be described in detail. I will clarify.

First, a parallel data processing device used in this invention will be defined. FIG. 3 shows a calculation element (2) according to an embodiment of the present invention, and hereinafter this calculation element will be referred to as a cell.

The specifications for cell marriage are as follows.
Bit) Output 5abc (1 bit each) out'i'j' out Internal register shift F (1 bit register) Function: i
f F-OthθnBout←8in■'1nout
in 1n aloal j if F-1then 8out+-8in■cin■
a1・bjCOut '78in"in"in"2L1
°bj+0in"i°b++ aloal 1) j4- bj However, θ, . . . + are the same as above.

That is, the F register (2) plays the role of a control register, and if this value is % g // then + a1 * 1)
The value of j is passed through, and the data of 8□□ and C1 are added. Also, if 11N, all 1) 8□ along with the passing of the value of 1. , ci. , al·bj are added. For each result, the sum is 8°ut and the 9-digit carry is outputted to C0ut.

Now, by arranging these cells in a two-dimensional grid, the parallel data processing device used in the embodiment of this invention can be configured. An example of this is shown in FIG.

FIG. 4 shows a case where 6×6 cells (C) are arranged. That is, cell Q4 to cell (s9) mountain cell (2
It is the same as 1.

A method for calculating the inner product using a data processing device in which such cells are arranged two-dimensionally will be described below. First, a modification of the array type multiplier shown in FIG. 2 will be considered.

That is, in FIG. 2, the full adders (21 to 21) propagate the same data in the same direction, but the full adders to Qυ propagate the carry ci to the left. This full adder fl11-;
t9υ is the full adder (21 to (Similar to I71, a severely deformed multiplier that propagates the carry toward the lower left. The connections are the same as the connections between full adders (2) and Oη in Figure 2. Full adders (76) to (89) are the same as the connections between full adders tUt to I2D in Figure 2. It was added because it was modified to be the same as the connection between the other full adders (21 to 21).
As input. ) Now, let's make a slight modification to the full adders that make up Figure 5. First, partial products were input to the full adders (6o) to (75), but these values can be input externally. ◇That is, 1, for example, is common to the full adder (6o) to (IS?). This is because the value is input.

This external human power is given to the full adder (6o), and input to the other full adders (61) to (63) is performed by propagating 1@ between cells from the left. Next, full adders (60) to (75) that require input of partial products and full adders (76) that do not require partial product input.
) to (89), a 1-bit control register (hereinafter referred to as F register) is provided. That is, if this F register is I11#, a partial product is created and added from the input data sent from the adjacent adder, and if the F register is %o, a 9-part product is created. Try not to do it.

When the above points are added to the full adder, the cell @ shown in FIG. 3 is obtained. Moreover, by replacing this cell @ with the full adder of the multiplier of FIG. 5, the multiplier of FIG. 6 is obtained. However, for the sake of explanation hereinafter, in FIG. 6, the entire multiplier of FIG. 5 is shown rotated 450 degrees in the opposite clockwise direction. In addition, only the lines to be used for connections between each cell are specified.

Furthermore, any part not specified as an external input is assumed to be a vkO input.

When the parallel data processing device shown in FIG. 4 is made to consist of 9×9 cells by transforming in this way,
Inside it can be found the 4-bit multiplier of FIG. That is, Fig. 4 7 is even larger 1 for example 21
If it consists of one cell, a 4-bit multiplier of 411ffi can be constructed, and the inner product calculation shown in equation (2) above can be performed.

The details will be described later using a specific example.

Next, I will explain how to use the F register.

When handling the multiplier shown in Fig. 6 as a single 4-bit multiplier, there is no problem in setting all F registers of cells (90) to (119) to 1N (because cells that do not require partial products have 101N). However, as will be described later, if there are multiple multipliers on the parallel data processing device, the F of cells (90) to (1os)
Close the register 11'# and close the other cells (106) to (11
9), all F registers must be set to 0. This is because the function of cells (90) to (1OS) is to add the partial product aibj with the input 6□. The function of (106) to (119) is to sequentially add only 'in' ins created in other cells.If the F register is 11, unrelated partial products If you create and perform addition, you will get 9 wrong results. For example.

The other operand e from the left end of the cell (106).

This value is input in sequential cell (106).
→ (107) −* (1os) → (1atp) is propagated as the value used in the other multiplier cells on the right side (naturally, data input is done from the end, so this kind of thing does not happen) obtain). In that case, what is the partial product in that multiplication and Ha in unrelated cells (106) to (109)? If the register is 11#, each incorrect partial product a39g
@a2e(1g a1eo+a(1θ) will be created and added.

That is, the cell whose F register is set to %1N is only the cell to which the multiplicand and multiplier necessary for the multiplication are sent.

Next, a parallel inner product calculation method using a parallel data processing device according to an embodiment of the present invention will be explained using a specific example. The object of the inner product calculation is #-t, which is expressed by the above equation (2). FIG. 7 shows an example of the use of the parallel data processing device used in the embodiment of the present invention.

The cells (to) in FIG. 3 are surrounded by each dotted line.

The number of cells is 21×21. Note that the connections between cells are omitted, but the cells [with] to (in Fig. 4)
59), all cells are connected to adjacent cells. Also, data is input from the top end and left end, and the result of the inner product is output from the bottom right end. However, all data inputs not specified are set to 10''.F registers are closed to 11# only for cells marked with diagonal lines, and all other cells are set to 'ON'.The items that perform each multiplication function are shown in Figure 9. Multiplication circuits (120) to (12) surrounded by thick solid lines in the middle
3).

First, let us consider the multiplication circuit (120). This is exactly the same as the circuit shown in Figure 6 (however, P, Qi
From the right end of the 0 or 1 multiplication circuit (120), the product AB of *multiplier A1 multiplier B is output. As shown above, the leftmost input is d. In order to eliminate the influence of ~d, , , fo, only the upper 4×4 cells have 111 set in the F register. The multiplier circuit (121) is also a circuit similar to the multiplier circuit (120), but at the same time as the product CD is calculated, the output single product AB of the multiplier circuit (120) is sent from the left, so the sum of these is IAB+CD. is output from the right side. The same holds true for the multiplication circuits (122) to (12-q).

In the end, 9 multiplication circuits (inner product AB + to be fitted from 12υ
CD + KF + GH is output, which propagates through the remaining cells, and is finally output from the lower right of the parallel data processing device in FIG.

The above explanation is based on the number of 4 pits, 8 jli! This is an example of inner product calculation for data a, but in the parallel inner product calculation method of the present invention, the data length and data reason can be easily changed. That is, by manipulating the F register in each cell of the parallel data processing device, an inner product operation consisting of an arbitrary amount of product terms with an arbitrary data length can be performed. As a result, the limitations of the conventional inner product calculation circuit due to the fixed data length and data can be removed, and a highly flexible inner product calculation circuit can be constructed.

〔Effect of the invention〕

As explained above, according to the parallel inner product calculation method according to the present invention, a plurality of calculation elements each having a full adder, an input AND element, and a control register for controlling the input of the full adder are arranged in a two-dimensional grid. By configuring a parallel data processing device and performing AND operation and full addition with the operation elements for which the control register is set, and half addition with the operation elements for which the control register is not set, arbitrary The inner product of the number of data can be calculated.

[Brief explanation of drawings]

FIG. 1 is a diagram showing a full adder. 2 is a diagram showing a 4-bit array type multiplier using the full adder of FIG. 1, FIG. 3 is a cell configuration diagram of a parallel data processing device used in an embodiment of the present invention, and FIG. A diagram showing a parallel data processing device with 6 x 6 g cells used in an embodiment of the invention, FIG. 5 is a diagram showing a multiplier that is a modification of the array type multiplier in FIG. 2, and FIG. 6 is a diagram showing the multiplier shown in FIG. FIG. 7 is an explanatory diagram for explaining an example of the use of the parallel inner product calculation method according to the embodiment of the present invention. In the figure, (1) is a full adder, 121-1'2a is a full adder used in an array type multiplier, 123 is an F register, and l'
21 is a cell constituting a parallel data processing device, @~(59
) are cells in the parallel data processing device, (6O) to (89)
is a modified full adder in an array multiplier @ (90)
~(119) are cells forming a multiplier, (120) ~(
123) is a multiplication circuit within the parallel data processing device. Note that the same reference numerals in FIG. 1 indicate the same or similar parts. Applicant Hirobe Kawata, Director of the Agency of Industrial Science and Technology 4 No. 6 Amendment of Figure Proceedings (Voluntary) Date of May 23, 1948 To the Commissioner of the Japan Patent Office 1 Indication of arc % Application No. 59-29486 2 Invention title Parallel Inner product calculation method λ Person making the amendment Column 5 of the detailed explanation of the invention in the specification, contents of the amendment fi+ Deleting “circuit” on page 3, line 16 of the specification 0 +2) Deleting “circuit” on line 16 of page 3 of the specification "Enter and add""Enter and add"
Correct to addition J. 131 In the same page 10, line 19, "all" is corrected to "nosusate".

Claims (1)

[Claims] +IJ A plurality of calculation elements each having a full adder, an input AND element, and at least a 1-bit control register for controlling the input of the full adder are arranged in a two-dimensional grid, and The multiplier of each product term of the inner product that should be claimed in a parallel data processing device that connects the input and output lines of adjacent calculation elements is shown from the left end. Input the multiplicand from the top, propagate the value among the calculation elements in order, and set the multiplier of each product term and each control register of the calculation element where the multiplicand intersects. AND operation and full addition are performed with the set calculation elements, half addition is performed with the calculation elements that are not set, the sum of the results is sent to the lower right calculation element, the increment by one digit is sent to the lower calculation element, and the inner product is A parallel inner product calculation method characterized in that the inner product of data of arbitrary length and/or between arbitrary lengths is calculated by outputting the calculation result from the lower right end of a parallel data processing device. (2) Dot product of data of arbitrary length and/or between arbitrary lengths. Parallel inner product calculation method 0 according to claim 1, characterized in that calculation is performed asynchronously.