JPH07129546A - Matrix operation algorithm and circuit - Google Patents

Abstract

(57) [Summary] [Object] The present invention provides a matrix operation algorithm and a circuit design for processing at least 2 bits for each clock cycle by using a modified Booth algorithm to reduce the occupied area of the circuit. To aim. The present invention is directed to a plurality of processor elements (P) each including storage means for receiving and storing a plurality of sets of numerical values in columns of a first matrix and corresponding rows of a second matrix.
E) a plurality of processor elements (P
E) It is composed of a multiplication circuit including a column. Other P in PE row
Each of the PE units connected to the E unit sequentially transmits a set of numerical values between the storage means in time series. Each of the PE units further comprises multiplication means for receiving a plurality of bits of the set of numbers from the storage means, the multiplication means processing the plurality of bits to produce a partial processing result. At least one of the multiplying means utilizing the partial processing result produces a product of the set of numerical values, whereby each PE column performs a matrix multiplication of a column of the second matrix.

Description

Detailed Description of the Invention

[0001]

FIELD OF THE INVENTION The present invention relates generally to algorithms and circuit implementations for performing matrix operations. In particular, the present invention relates to matrix multiplication algorithms and circuit designs that are implemented on integrated circuit (IC) chips to reduce the occupied area on the IC chip and to perform faster multiplication operations.

[0002]

BACKGROUND OF THE INVENTION Matrix operations are usually performed under different circumstances depending on the application. In order to perform the multiplication efficiently, the multiplication algorithm is generally implemented in hardware using a special IC circuit design. The recent trend toward miniaturization of smaller electronic components has placed great demands on circuit design technology to minimize the area occupied by circuitry on an IC chip. The algorithms, which have the feature that they can be implemented by IC circuit designs with reduced circuit size on chip, can be applied to a wide range of applications to reduce the size of electronic components.

One typical application of matrix multiplication is
It is in the field of video image data compression where two-dimensional discrete cosine transform (DCT) is performed. For an NxN data matrix, the two-dimensional discrete cosine transform is defined as:

[0004]

[Equation 1]

The inverse transform is similarly performed as follows:

[0006]

[Equation 2]

Here, in the case of K = 0, C (x) = 1/2 ^** (0.5) and in the case of K ≠ 0, C (x) = 1. X (n ₁ , n ₂ ) is the input data matrix and Z (K ₁ , K ₂ ) is the transform coefficient matrix.

Expressing equation (1a) in matrix form, Z = CXC ^t (2), where C represents the cosine coefficient matrix and C ^t represents the transpose of C. In a more detailed form, equation (2) can be expressed as:

[0009]

[Equation 3]

Here, C ^t _ij = C _ij . There are three N × N matrices that multiply together. Thus, Matrix <br/> scan Y to Y = XC ^t, or,

[0011]

[Equation 4]

Defined by, the matrix is represented as:

[0013]

[Equation 5]

According to the 2-row, 2-column example, equation (4) is

[0015]

[Equation 6]

## EQU3 ## Equation (5) is transformed into

[0017]

[Equation 7]

It is transformed as follows. The prior art regarding DCT matrix multiplication has some limitations. When using the row-column decomposition method, transposed memory is required. The solution with a large amount of pipelined data flow is
It becomes extremely difficult to implement in the actual circuit design. In situations where a two-dimensional DCT is directly implemented, compared to the potential benefits of the intended hardware implementation,
Hardware design and manufacturing costs are too high. Moreover,
Since the proposed technology generally lacks modularization characteristics and requires a highly intricate and complicated circuit structure, it is very time-consuming and inefficient for actual implementation.

A circuit design modularized to implement matrix multiplication is provided by a prior patent by the inventor of the present invention (Patent Application No. 07/836, entitled "Fast Pipelined Matrix Multiplier"). , 07
No. 5). In patent application No. 07 / 836,075, a pipeline structure is used, in which a plurality of registers and multiplexers are arranged in a general architecture to form a plurality of bit multiplication elements, or processing elements (PEs). It Multiply is 1 for every processing element
It is executed in time series for each bit. In addition to the overall configuration, the multiplications are carried out in parallel, i.e. each element of the row corresponding to the column of the matrix to be multiplied is simultaneously processed in parallel in one of a number of overall processing rows. The multiplier further has the advantage that Due to the simplicity of the design and the pipelined, parallel processing architecture, the multipliers are very economically designed and manufactured. The cost of hardware implementation is greatly reduced compared to that of the prior art. The modular structure further allows it to be conveniently used to perform multi-stage matrix multiplications without major circuit design effort.

However, this pipeline multiplier may be subject to various potential hardware constraints under certain circumstances. Multiple bit multiplication elements, ie
Since each of the processing elements (PEs) processes one bit per clock period, the number of registers and multiplexers will increase as the number of bits of individual matrix elements and the number of rows and columns of the matrix increase. There is. The demand for miniaturization of electronic components limits the number of electronic circuit components on the IC chip. The interconnection lines associated with the large number of registers and multiplexers may occupy too much area on the IC chip, which may cause the hardware implementation to be incompatible with manufacturing specifications.

Therefore, there is still a need in the prior art to reduce the number of circuit components in a pipeline multiplier, which can further improve the pipeline / parallel multiplication configuration for implementation in a wider range of applications. .

[0022]

Accordingly, it is an object of the present invention to provide a Modified Booth Algorithm.
orithm) to process at least two bits every clock cycle, thereby providing a matrix operation algorithm and circuit design that reduces the occupied area of the circuit.

Another object of the present invention is to meet the accuracy benchmark requirement based on CCITT (International Telegraph and Telephone Advisory Committee) proposed standard for IDCT which uses a pipeline and parallel processing architecture in which the circuit area on the IC chip is reduced. It is to provide a matrix operation algorithm and a circuit design. Another object of the present invention is to provide a matrix operation algorithm and circuit design that enables an intermediate test function, whereby the multiplication accuracy can be more easily checked.

[0024]

Briefly, in accordance with a preferred embodiment, the present invention receives and stores multiple sets of numeric values in rows of a first matrix and corresponding columns of a second matrix. A multiplication circuit including a plurality of processor element (PE) columns each including a plurality of processor element (PE) units each including a storage unit. Each of the PE units sequentially transmits a set of numerical values connected to the other PE units in the PE column between the storage means in time series. PE
Each of the units further comprises multiplication means for receiving the plurality of bits of the set of numbers from the storage means, the multiplication means processing the plurality of bits to produce a partial processing result. At least one of the multiplying means utilizing the partial processing result produces a product of the set of numerical values, whereby each PE column performs a matrix multiplication of the columns of the second matrix and the matrix circuit performs the matrix multiplication. Run.

[0025]

An advantage of the present invention is that it provides a matrix operation algorithm and circuit design that utilizes a modified Booth algorithm to process at least two bits every clock cycle, thereby reducing the occupied area of the circuit. . Another advantage of the present invention is an ID that reduces the circuit area on the IC chip and utilizes a pipeline and parallel processing architecture.
It is an object of the present invention to provide a matrix operation algorithm and a circuit design that satisfy the accuracy benchmark requirement based on the CCITT proposed standard for CT.

Another advantage of the present invention is that it provides an intermediate test function, thereby providing a matrix operation algorithm and circuit design in which multiplication accuracy can be more easily checked. These and other objects and advantages of the present invention will no doubt become apparent to those skilled in the art upon reading the following detailed description of the preferred embodiments, which is set forth in various drawings.

[0027]

1 shows a matrix multiplication circuit 10 according to the present invention.
Indicates. The multiplication circuit 10 is a 2 × 2 matrix multiplication, that is,
Is used to implement A × B = C , where A , B and
C represents three matrices each having two rows and two columns. The multiplier 10 comprises two identical and parallel columns, column 16 and column 18, where column 16 is a matrix.
Column A performs the multiplication of the elements of A with the first column of matrix B , and column 18 performs the multiplication of the elements of matrix A with the elements of the second column of B. The operations in columns 16 and 18 can be performed in parallel. Column 1 as well as the multiplication performed by the pipeline multiplier disclosed in patent application Ser. No. 07 / 836,075
The structure of 6 and 18 is organized as a whole, where the multiplications are all performed sequentially.

Each processing element row, that is, rows 16 and 18 are PE1 (16-1) and PE2 (16-), respectively.
2), PE3 (16-4), and PE1 (18-1),
It is composed of a plurality of processing element (PE) units described as PE2 (18-2) and PE3 (18-4). P
The E1 and PE2 units are utilized to perform the multiplications in a sequential manner, where each processing unit performs a certain number of multiplications in pipeline form. At the beginning of each clock cycle, the contents of one level of processing unit are transferred to the next level for further processing, where the multiplication of the next set of bits is performed. Therefore, the total number of PE1 and PE2 units depends on the number of bits of the matrix element to be multiplied and the number of bits processed by each processing unit. For example, assuming that the number of bits processed by each processing unit is 2, the total number of processing units, that is, the total number of PE1 and PE2 is N / 2 when N is an even number of the matrix A and N is an even number. Then, when N is an odd number, it is (N + 1) / 2.

The multiplier 10 further includes a register string 20 including a plurality of registers. Processor element row, ie row 1
The operations of 6 and 18 are performed with the registers of register column 20, as described below. Since the calculation of the register train 18 is the same as the calculation of the register train 16, the following description regarding the register train 16 is also applicable to the register train 18. The matrix elements a ₁₁ , a ₁₂ , a ₂₁ , and a ₂₂ of the 2-row 2-column matrix A , one at a time,
It is input to the register string 20 from the line 20-1. At the same time, the matrix elements of one row of the matrix B b _11, b
₁₂ is the first processor row PE (16-
1) is input from the line 34-1. Parallel processing is carried out by configuring the architecture of the multiplier such that the multiplication of each column of matrix B is performed by each column simultaneously as in column 16. Since in matrix multiplication the first column of matrix B is multiplied by the first and second rows of matrix A , each matrix element is associated with line 34-1.
Is input twice from.

First matrix element a ₁₁ of matrix A
And the first matrix element b ₁₁ of the matrix B is input to the multiplier 10 during the same clock cycle via line 20-1 and line 34-1, respectively. The first and second bits of the element a ₁₁ are set to the first processor element PE1 (16-1).
The tap line 38-1 for supplying to
1 to the input lines of the first and second bits. a
_{The eleventh} first and second bits are transferred to the selector control input of multiplexer 36-1. Multiplexer 36-
1 also receives element b ₁₁ from line 34-1 as a data input. The modified Booth algorithm implements the multiplexer 3 to perform the multiplication of the first and second bits of a ₁₁ .
6-1 is applied. Table 1 shows a 3-bit modified Booth table, where two new bits are processed at each time. Of these two new bits, the lower bit is bit b (i) and the upper bit is bit b (i +
1), while the upper bits of the previous 2 bits are also used and denoted as b (i-1). For the first 2-bit operation, the value of b (i-1) is designated as zero.

[0031]

[Table 1]

The modified Booth table operation for the first two bits performed in PE1 is shown in FIG. Only two control values are selected from these two bits. By assigning the value 0 to bit b (i−1), the multiplexer operates according to the modified Booth table to compute * 0, *
Perform 1, * (-2), and * (-1). The output of the multiplexer is via the data transmission line 28-1.
It is transferred to the register (R) 24-1 stored at the falling edge of the clock cycle. Its value constitutes the partial product of the first two-input matrix elements a ₁₁ and b ₁₁ . On the other hand, at the end of the clock period, these two matrix elements, a ₁₁ and b _11, are transferred via lines 20-1 and 32-1 and stored in registers 21-1 and 30-1, respectively. It The operation of PE1 ends for the first two input elements.

At the beginning of the next clock cycle, the next two inputs a
₁₂ and b ₂₁ are received by PE1 (16-1) and a ₁₁
And b ₁₁ are processed in the same manner as performed. On the other hand, the multiplication of the next 2 bits of a ₁₁ and the matrix element b ₁₁ is executed by the next processor element PE2 (16-2). Tap line 38-2 transfers the second, third and fourth bits of a ₁₁ to the selector control input of multiplexer 36-2 of PE2 unit (16-2) and matrix element b ₁₁ also connects line 34-2. Through multiplexer 36
-2. Again, the modified Booth table, i.e. Table 1, is utilized in multiplexer 36-2 to perform the multiplication. Reference is made to FIG. 3 where the multiplexer utilized in the PE2 unit is shown. The first 3 bits of the input element a ₁₁ are used as the selector control input. Depending on the 3-bit value, there are 5 types of operations, namely * 0, * 1, * 2,
* (-1) and * (-2) are executed.

The output of the multiplexer 36-2 is sent to the register 2 of the PE1 unit 16-1 via the line 26-1.
It is transferred via line 28-2 to a carry save adder (CSA) 24-2 which also receives the partial product stored in 4-1. The output data of the multiplexer 36-2 of the PE2 unit represents the product resulting from the operation performed on the second, third and fourth bits of the data a ₁₁ , so that the output of the multiplexer 36-2 is initially First, it must be shifted two bits to the left with respect to the output from multiplexer 36-1. Instead of a standard adder, the CSA 24-2 "carries and adds" to increase the throughput of the processor element unit.
To use. The "carry and add" operation is an operation in which an "exclusive OR" operation is performed on each bit to calculate "sum" without carry, and an AND operation is applied to each bit to calculate "carry". , The true sum is obtained by adding the "sum" and the "carry".

At the falling edge of the second clock,
A new set of "ri" and "sum" is stored in the addition register 24-2.
And input a₁₁Is the line 20 of the storage register column 20.
-2 to the register 21-2. Similarly,
Matrix element b₁₁PE2 through line 32-2
Transferred to the register 30-2 of the unit 16-2,
It is stored there for processing. On the other hand, matrix required
The second pair of prime a₁₂And b _{twenty one}And carry and sum are registers
Column register 21-1, registers 30-1 and 24-1
Are memorized respectively.

At the beginning of each clock cycle, the data is pipelined throughout with each processor element unit performing the various stages of multiplication. PE3
The unit (16-3) is provided at the end of the processing element array 16. Similar to PE2, the modified Booth algorithm is implemented in multiplexer 36-3. Details of the multiplexer 36-3 are shown in FIG.

Continuing the operation of processing element array 16, when all bits of a ₁₁ have been processed, the last pair of "sum" and "carry" of the first pair of matrix elements a ₁₁ and b ₁₁ is the auxiliary register. 24-3. The value of a ₁₁ multiplied by b ₁₁ is the “sum” stored in the register 24-3.
And the last set of "carries" are added to the addition register 24-4.

The products a ₁₁ b ₁₁ are transferred to accumulator (ACC) 40 via line 26-3. The accumulator 40 has a feedback path 46 so that the first product a ₁₁ b ₁₁ loops back to the accumulator 40. One clock period after the end of the product a ₁₁ b ₁₁ , accumulator 40 receives the second product a ₁₂ b ₂₁ via line 26-3. These two products are added in the accumulator 40 and stored.

At the next clock cycle, the third product a ₂₁ b ₁₁ reaches the accumulator 40 via line 26-3. The contents of the accumulator 40, that is, the sum c _{11 of} a ₁₁ b ₁₁ and a ₁₂ b ₂₁ is transferred to the register (Rh) 44 via the line 42.
Register 44 is then connected either to the output port or to another processing circuit for further processing. Two clock cycles after c ₁₁ reaches register 44, the matrix
Another matrix element c ₂₁ of C is also transferred via line 42 to a register 44 ready for output or further processing.

The first matrix elements of the matrix C, that is, c ₁₁ are the sum of the product of the first column of the first row and the B of A, the register 44 associated therewith and accumulator 40 c ₁₁
Used to calculate the final value of. The details of the data processing in accumulator 40 and register 44 are the same as for patent application Ser. No. 07 / 836,075, incorporated herein by reference.

Thus, the processing element array 16 sequentially produces a series of products of a plurality of pairs of input data,
The sum of these products can be calculated. When the input data pairs are properly arranged, the processing element array 16 is
Matrix elements can be generated as a result of the multiplication of the rows of the first matrix and the columns of the second matrix.

By the same process, the processing element array 1
8 in turn receives the matrix elements of the second row of matrix B to generate the matrix elements of the second column of matrix C. The processing element trains 16 and 18 can perform multiplication tasks simultaneously in a synchronized manner. The outputs of columns 16 and 18 are the 2x2 discrete cosine transform (D
More available for CT) calculation. A second stage multiplier similar to multiplier 10 is utilized to perform another matrix multiplication. For details of the DCT multiplication circuit, see 8x8.
The DCT circuit will be described below.

FIG. 5 shows a module circuit 100 for performing 8 × 8 DCT processing. The DCT circuit 100 has two stages, the first stage 106 for calculating Y = XC ^t and Z = C.
It consists of a second stage 108 for calculating Y. The first stage is to input data, that is, the matrix elements from the top to the bottom in chronological order.
Register row 10 having a plurality of registers connected in a row so as to sequentially transfer one clock cycle per register
Including 2. The first stage 106 is further composed of eight processing element arrays 104-1 to 104-8. Each of the processing element arrays 104-1 to 104-8 corresponds to the PE1 units 16-1 and 18-1 of the circuit 10 shown in FIG.
With a PE1 unit 140 that matches The first stage is
It further comprises PE2 and PE3 units which also match the PE2 and PE3 units of the circuit 10 shown in FIG.

In performing the multiplication process, a modified Booth algorithm is used to process the two new bits in each PE unit. As described with respect to the multiplier 10, the total number of PE1 and PE2 units is equal to N / 2 when N is even and (N +
1) / 2, where N is the number of bits of the input element stored in register series 102.

Similar to the 2 × 2 multiplier circuit 10 of FIG.
Each of the process elements 04-1 to 104-8 receives two inputs. The elements of the first data matrix X are sequentially input to the register array 102, one element per cycle. These matrix elements are transferred to the next lower register of the register array 102, one register per cycle. In each clock cycle, two new bits from each register of register train 102 are transferred to the corresponding PE unit in each processing element unit 104-1 to 104-8. The partial product process is then pipelined in each PE unit simultaneously for each row and corresponding column. Each processing element array 104-1 to 104-8 produces one array of elements of the intermediate matrix Y. At the end of each processing element row, eight products are added to calculate the matrix elements of the intermediate matrix Y. After completion of the calculations for each matrix element, the matrix elements are transferred via lines 132-1 through 132-8 for further processing by the second stage multiplier 108.

Like the first stage 106, the second stage 108 also
Register array 110 and eight processing element arrays 124-
1 to 124-8, where each column also has PE1, PE2 and PE3 units to perform the matrix calculation Z = CY . By utilizing the modified Booth algorithm, the total number of PE1 and PE2 units is approximately half the number of bits of the matrix elements stored in the register column 110. The order of operations is the same as that of the first stage 106. The final product of each processing element array is line 13
8 adders (ADD) through 0-1 to 130-8
162-1 to 162-8, and carry and sum for obtaining the final value of the product are added.

The products calculated by the adders 162-1 to 162-8 are stored in accumulators (ACC) 164-1 to 16-16.
It is transferred to a 4-8 array for further processing. Matrix C
And matrix multiplication of matrix Y , each element of matrix Z is one row of matrix C and matrix Y.
Is the sum of products with one column of. However, the first stage 106
From the output of, a sequence of matrix elements is generated for each row of the matrix Y. Previous patent application No. 07 /
In 836,075, two switch array boxes and an accumulator array of 64 accumulators are used to accurately accumulate all 64 elements and compute the final 2D DCT element. FIG. 5 shows a simplified circuit that utilizes a less complex circuit design to further save the IC chip area occupied by the 8 × 8 DCT circuit 100.
An array of temporary storage registers 180-1 through 180-8 and an array of output registers 190-1 through 190-8 are utilized, where each temporary storage register and output register includes eight shift registers. Details of the temporary storage register are shown in FIG. 6 because each shift register has 26 bits.
Ff_26 in FIG. 7 and each of the shift registers has 18 bits.
Shown as 8.

The addition operation in the accumulators 164-1 to 164-8 is executed only every 8 clock cycles, and the sum obtained in the accumulators 164-1 to 164-8 is the temporary storage registers 180-1 to 180-1. First transferred to 180-8. The data stored in the first shift register of the temporary storage register 180 is looped back at the beginning of each ninth clock cycle, and the accumulators 164-1 to 164-8 are added.
Is added to the value of. On the other hand, when the value newly calculated by the accumulators 164-1 to 164-8 is stored in the first shift register at the beginning of each clock cycle, the data in the temporary storage registers 180-1 to 180-8 are It is shifted right to the next shift register. At the beginning of the 57th clock cycle, at the end of the calculation of the first row of the matrix Z , all matrix elements have the first output register 190-1.
Are transferred in parallel to. Similarly, at the end of the second row of matrix Z , the matrix elements are transferred in parallel to output register 190-2, and so on. These data are
It is further serially transferred via the serial output port to the rounding circuit 200 for final processing for use in high definition television (HDTV) systems or other types of applications.

The DCT circuit 100 further comprises a holding register 126 for the dual purpose of reading the input DCT matrix coefficients and performing the intermediate test. FIG. 8 shows a circuit of the holding register 126. At the end of the multiplication operation, the product values are stored in accumulators 125-1 through 125-8. In a preferred embodiment, the holding register has two serial bidirectional ports, a 10-bit serial port and a 12-bit serial port, as shown. These ports are used to read the DCT matrix coefficients to perform the second stage DCT calculation. At the same time, for testing purposes, the high order bits of the product for testing, ie bits 1 through 12 are read from the 12-bit serial port and the low order bits of the product for testing, ie bits 13 through 2 are read.
2 is read from the 10-bit serial port. Since there are 7 clock periods, the product of two matrix elements is temporarily stored before the addition operation is performed in the 8x8 DCT calculation. Data is read at a predetermined clock cycle without interfering with the normal operation of the DCT task and the input of matrix coefficients. By making the data input port a bidirectional serial port, the circuit 100 provides the additional ability to perform intermediate tests without adding cost to the circuit design.

In addition to the above circuit elements, two stages of 8 × 8D
The CT circuit 100 also has a clock generator 210 and coefficient supply means (not shown) for supplying DCT coefficients.
Details of these elements and carry-save adders (CSA) can be found in the previous patent application No. 07 /
Similar to that described in No. 836,075. Compared to the previous patent application, the number of processor element units, ie the total number of PE1 and PE2, has been reduced to about half in the present invention.

Similar to the patent application No. 07 / 836,075, a two-stage circuit is used to perform the DCT transform in a time-series pipeline system, in which the multiplication of each row of the second matrix is performed in parallel. Is processed. However, the present invention does not limit the number of processor element units, namely PE1 and P1.
It has the advantage that the number of E2s is reduced to about 50% in most cases. This is obtained by utilizing a modified Booth algorithm that allows each processor element unit to process a new 2 bits instead of 1 bit, so that it is required to process the same number of data. Reduce the circuit. Processor element unit PE
1 and PE2 process 2 bits per clock period, and CSA is used where a simple exclusive OR and a simple adder and OR without the carry ripple effect that often occurs in conventional adders. Data processing throughput is also increased by making AND operations more efficient because they are performed.

As the number of columns and rows in the matrix increases and the number of bits of data processed increases, the savings of "real estate" on the IC chip becomes more important. An IC that can be used by one type of circuit, for example, a circuit for DCT conversion, to integrate multiple functions on a single chip
The effective area on the chip is thus further constrained. The present invention teaches a pipelined multiplication circuit that can overcome the potential limitations of the prior art.

While the present invention has been described in terms of its presently preferred embodiments, it should be understood that such disclosure is not to be construed as limiting. Various substitutions and modifications will no doubt become apparent to those skilled in the art upon reading the above description. Therefore, it is intended that the appended claims cover all substitutions and modifications within the true spirit and scope of the invention.

[Brief description of drawings]

FIG. 1 is a diagram showing a 2 × 2 matrix multiplication circuit according to the present invention.

FIG. 2 shows a multiplexer for implementing the modified Booth algorithm in process element 1 (PE1).

FIG. 3 shows a multiplexer for implementing the modified Booth algorithm in process element 2 (PE2).

FIG. 4 shows a multiplexer for implementing the modified Booth algorithm in process element 3 (PE3).

FIG. 5 is a diagram showing a module circuit that executes 8-row by 8-column DCT processing.

FIG. 6 is a diagram showing an array ff_26 of temporary storage registers.

FIG. 7 is a diagram showing an array ff_18 of output registers.

FIG. 8 is a diagram showing an array of holding registers for executing an intermediate test.

[Explanation of symbols]

10 matrix multiplication circuit 16, 18 processing element array 16-1, 16-2, 16-3, 16-4, 18-1,
18-2, 18-4, 104-1 ,. ． , 104-8,
124-1. ． , 124-8 Processing element unit 20, 102, 110 Register sequence 20-1, 20-2, 26-1, 26-3, 32-1,
32-2, 34-1, 34-2, 42, 130-
1 ,. ． , 130-8, 132-1 ,. ． , 132-8
Lines 21-1, 21-2, 24-1, 30-1, 30-2,
44 register 24-2 carry save adder 24-3 auxiliary register 24-4 addition register 28-1, 28-2 data transmission line 36-1, 36-2, 36-3 multiplexer 38-1, 38-2 tap line 40, 125-1 ,. ． , 125-8, 164-
1 ,. ． , 164-8 Accumulator 46 Feedback path 100 Module circuit 106 First stage multiplier 108 Second stage multiplier 126 Holding register 140 PE1 unit 162-1 ,. ． ． , 162-8 adders 180-1 ,. ． ． , 180-8 Temporary storage registers 190-1 ,. ． ． , 190-8 Output register 200 Round circuit 210 Clock generator

─────────────────────────────────────────────────── ─── Continuation of the front page (51) Int.Cl. ⁶ Identification code Office reference number FI Technical display location H04N 7/30 H04N 7/133 Z

Claims (13)

[Claims] 1. A plurality of processor elements (P) each having storage means for storing at least two numbers to be multiplied.
E) unit, each of the PE units being connected to another PE unit that transmits the numerical value between the storage means in a predetermined order, each PE unit having a plurality of bits of the numerical value from the storage means. A multiplication circuit further comprising multiplication means for receiving and processing the plurality of bits to generate a partial processing result, wherein at least one of the PE units uses the partial processing result to generate a product of the numerical values. 2. The multiplication circuit according to claim 1, wherein the PE units are sequentially connected so that the numerical value is transmitted from one PE unit to an adjacent PE unit in time series. 3. The multiplication circuit according to claim 2, wherein the multiplication means includes a multiplexer. 4. The multiplier circuit of claim 3, wherein the multiplexer utilizes a modified Booth algorithm. 5. The multiplication means further comprises a carry save adder (CSA) for generating a sum and a carry for the partial processing result, the at least one PE unit and the carry so as to generate the product. The multiplying circuit according to claim 4, further comprising an adding unit that adds the carry. 6. The multiplication circuit according to claim 5, wherein the storage means further includes at least two registers for storing the carry and the sum. 7. A plurality of processor elements (P) each having storage means for receiving and storing a plurality of sets of numbers to be multiplied.
E) unit, each of the PE units being connected to another PE unit in which the set of numerical values is sequentially transmitted from one of the storage means to an adjacent storage means in time sequence according to a predetermined order, Each of the PE units further comprises multiplication means including a multiplexer for receiving the plurality of bits of the set of numbers from the storage means and processing the plurality of bits utilizing a modified Booth algorithm to generate a partial processing result. The multiplication means further includes a carry save adder (CSA) for generating a sum and a carry for the partial processing result, and at least one of the PE units adds the sum and the carry to generate a product. A multiplying circuit including adding means for performing. 8. The multiplier circuit of claim 7, wherein the multiplexer in each of the PE units utilizes a modified Booth algorithm to process 2 bits each time. 9. The set of numbers comprises a plurality of matrix elements of two matrices, thereby performing a multiplication of the matrix elements to generate a plurality of matrix elements of a third matrix, wherein 9. The multiplication circuit according to claim 8, wherein the third matrix is a product of the two matrices. 10. A method for pipeline-wise multiplying a plurality of sets of a first numerical value and a second numerical value, comprising: (a) first multiplying the first numerical value and the second numerical value by Receiving and storing by a storage means in a processing element (PE) unit of said (b) processing said plurality of bits of said first and second numerical values to obtain a partial product of said first and second numerical values; A multiplying means in one processing element (PE) unit, thus generating a carry and a sum, and (c) the carry and the partial product containing the sum and the first and second
Is transmitted from the first PE unit to a neighboring PE unit in a predetermined order and step (b) is repeated until all bits of the first and second numbers have been processed. Processing the further bits of the two numbers, (d) adding the carry and the sum to produce a product of the first and second numbers, and (e) each set of the first and second numbers. About step (a)
A multiplication method comprising the steps of repeating (d) to (d). 11. A plurality of processor elements (PEs) each including storage means for receiving and storing a plurality of sets of numerical values in columns of a first matrix and corresponding rows of a second matrix.
A multiplication circuit comprising a plurality of processor element (PE) sequences each including a unit, wherein each of the PE units is configured to time-sequentially output the set of numerical values connected to another PE unit of the PE sequence. Sequentially transmitting between the storage means, each of the PE units further comprising multiplication means for receiving the plurality of bits of the set of numbers from the storage means and processing the plurality of bits to generate a partial processing result. , Said at least one multiplication means utilizing said partial processing result produces a product of said set of numerical values, each said column of said second matrix having a corresponding PE column, said PE column being said product , Whereby each of the PE columns performs a matrix multiplication of the columns of the second matrix to matrix multiply the first matrix with the second matrix. 12. A plurality of processor element (PE) units each including a storage means for receiving and storing a plurality of sets of numerical values in a row of the first matrix and corresponding columns of the second matrix. A plurality of processor element (PE) columns, each of said PE columns having a corresponding column of said second matrix, each of said PE units being connected to another PE unit of said PE column; Transmit the sets of numbers sequentially between the storage means in time series, each of the PE units receiving a plurality of bits of the sets of numbers from the storage means and generating a partial processing result. Further comprising multiplying means for processing the plurality of bits, wherein at least one of the multiplying means utilizes the partial processing result,
Generating a product of the set of numbers, thus multiplying a corresponding element of a column of the second matrix by a corresponding element of a column of the second matrix; A plurality of processor element (PE) columns each including a plurality of processor element (PE) units each including storage means for receiving and storing matrix elements of corresponding columns of the three matrices. The product is the multiplication of the element of the row of the first matrix with the corresponding element of the column of the second matrix, each PE unit being connected to another PE unit of the PE column. , Sequentially transmitting the intermediate product from each first stage and the matrix element set of the corresponding column of the third matrix in chronological order between the storage means, each of the PE units Receiving a plurality of bits of the set of numbers from the storage means Further comprising multiplication means for processing the plurality of bits to generate a partial processing result, the at least one multiplication means utilizing the partial processing result being the intermediate product from the first stage and the third matrix. A second stage for producing a product of the matrix elements of the corresponding column of each of the PE columns of the second stage having accumulating means for adding the products, Causes the first stage and the second stage to move to the second stage.
A matrix circuit for performing matrix multiplication of the third matrix in parallel with the third matrix in a pipeline manner. 13. The accumulating means in each of the PE columns of the second stage further comprises a plurality of storage shift registers, wherein one of the storage shift registers is the intermediate product from the first stage. The accumulating means in each of the PE columns of the second stage corresponds to the column of one of the third matrices for temporarily storing the product of the corresponding column matrix element of the third matrix. 13. The multiplier circuit of claim 12, further comprising an accumulation register for sequentially adding the products received from the storage shift register.