High Speed and Efficient Matrix Multiplication Hardware Module

• US 20090024685A1
• Filed: 07/19/2007
• Published: 01/22/2009
• Est. Priority Date: 07/19/2007
• Status: Active Grant

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: ITT Manufacturing Enterprises, Inc. (ITT, Inc.)
• Inventors: Fitzgerald, Dennis, Salama, Yassir, Salama, Assem
• Granted Patent: US 8,051,124 B2
• Time in Patent Office: Days
• US Class Current: 708/607
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/30109 having multiple operands in a single register

Abstract

A matrix multiplication module and matrix multiplication method are provided that use a variable number of multiplier-accumulator units based on the amount of data elements of the matrices are available or needed for processing at a particular point or stage in the computation process. As more data elements become available or are needed, more multiplier-accumulator units are used to perform the necessary multiplication and addition operations. To multiply an N×M matrix by an M×N matrix, the total (maximum) number of used MAC units is “2*N−1”. The number of MAC units used starts with one (1) and increases by two at each computation stage, that is, at the beginning of reading of data elements for each new row of the first matrix. The sequence of the number of MAC units is {1, 3, 5, . . . , 2*N−1} for computation stages each of which corresponds to reading of data elements for each new row of the left hand matrix, also called the first matrix. For the multiplication of two 8×8 matrices, the performance is 16 floating point operations per clock cycle. For an FPGA running at 100 MHz, the performance is 1.6 Giga floating point operations per second. The performance increases with the increase of the clock frequency and the use of larger matrices when FPGA resources permit. Very large matrices are partitioned into smaller blocks to fit in the FPGA resources. Results from the multiplication of sub-matrices are combined to form the final result of the large matrices.

Claims

1. A matrix multiplication device, comprising a plurality of multiplier-accumulator units each of which comprises a multiplier circuit that multiplies two data elements to produce a product value and an adder circuit that adds the product value with an addend value to produce a result value, wherein a number of multiplier-accumulator units used when a multiplication computation is performed on first and second matrices varies depending on which computation stage corresponding to which row of the first matrix the multiplication computation is executing.

2. The device of claim 1, and further comprising a storage unit comprising a plurality of storage locations, wherein the storage unit stores data elements of the first and second matrices that are applied to a multiplier-accumulator unit during a computation stage for use in a subsequent computation stage.

3. The device of claim 2, and further comprising first and second memories, the first memory storing data elements of the first matrix and the second memory storing data elements of the second matrix.

4. The device of claim 3, and further comprising a first input port and a second input port, a first bus that couples data between the first memory and the first input port and a second bus that couples data between the second memory and the second input port.

5. The device of claim 4, wherein each multiplier-accumulator unit comprises a first input that receives a data element of the first matrix and a second input that receives a data element of the second matrix.

6. The device of claim 5, during the jth computation stage corresponding to the jth row of the first matrix, the number of multiplier-accumulator units used is sufficient in order to multiply data elements for the jth row of the first matrix by data elements for the jth column of the second matrix and all preceding columns of the second matrix, and to multiply data elements for all rows of the first matrix preceding the jth row by data elements for the jth column of the second matrix.

7. The device of claim 6, wherein during the jth computation stage, data elements for the jth row of the first matrix and for all preceding rows are stored in respective storage locations of the storage unit for use in computation stages after the jth computation stage.

8. The device of claim 6, wherein during each computation stage, each multiplier-accumulator unit that is used is operated for a plurality of clock cycles equal in number to a number of rows of the first matrix.

9. The device of claim 8, wherein the adder circuit in each multiplier-accumulator unit adds the product value computed by the multiplier circuit at a current clock cycle with the result value computed by the adder circuit at a previous clock cycle for that computation stage.

10. The device of claim 5, wherein during a first computation stage corresponding to a first row of the first matrix, a single multiplier-accumulator unit is used to multiply data elements of the first row of the first matrix with data elements of the first column of the second matrix.

11. The device of claim 1, wherein when multiplying a first matrix comprising N×

M data elements by a second matrix comprising M×

N data elements, the number of multiplier-accumulator units used during a sequence of computation stages is {1, 3, 5, . . . , 2*N−

1}.

12. A matrix multiplication hardware core that multiplies first and second matrices, comprising:

a. a plurality of multiplier-accumulator units each of which multiplies a first data element from the first matrix with a second data element from the second matrix to produce a product value and adds the product value with an addend value to produce a result value, wherein a number of multiplier-accumulator units used when multiplying the first and second matrices increases as computations progress from a first row of the first matrix to remaining rows of the first matrix; and

b. a storage unit comprising a plurality of registers that store data elements for one or more rows of the first matrix and for one or more columns of the second matrix for subsequent supply as input to a multiplier-accumulator unit.

13. The device of claim 12, during a jth computation stage corresponding to a jth row of the first matrix, the number of multiplier-accumulator units used is sufficient in order to multiply data elements for the jth row of the first matrix by data elements for the jth column of the second matrix and all preceding columns of the second matrix, and to multiply data elements for all rows of the first matrix preceding the jth row by data elements for the jth column of the second matrix.

14. The device of claim 13, wherein during the jth computation stage, data elements for the jth row of the first matrix and for all preceding rows are stored in respective storage locations of the storage unit for use in computation stages after the jth computation stage.

15. The device of claim 13, wherein during each computation stage, each multiplier-accumulator unit that is used is operated for a plurality of clock cycles equal in number to a number of rows of the first matrix.

16. The device of claim 15, wherein each multiplier-accumulator circuit comprises an adder circuit that adds the product value computed by the multiplier circuit at a current clock cycle with the result value computed by the adder circuit at a previous clock cycle for that computation stage.

17. The device of claim 12, wherein when the first matrix comprises N×

M data elements and the second matrix comprises M×

N data elements, the number of multiplier-accumulator units used during a sequence of computation stages is {1, 3, 5, . . . , 2*N−

1}.

18. A method for multiplying first and second matrices, comprising:

a. providing a plurality of multiplier-accumulator units, each of which is capable of multiplying one data element of the first matrix with a data element of the second matrix to produce a product value and adding the product value with an addend value to produce a result value; and

b. using a number of said plurality of multiplier-accumulator units that increases as computation progresses from a first row of the first matrix to remaining rows of the first matrix.

19. The method of claim 18, wherein (b) using comprises, during a jth computation stage corresponding to a jth row of the first matrix, using a number of multiplier-accumulator units that is sufficient in order to multiply data elements for the jth row of the first matrix by data elements for the jth column of the second matrix and all preceding columns of the second matrix, and to multiply data elements for all rows of the first matrix preceding the jth row by data elements for the jth column of the second matrix.

20. The method of claim 19, and further comprising, during the jth computation stage, storing data elements for the jth row of the first matrix and for all preceding rows in respective storage locations for use in computation stages after the jth computation stage.

21. The method of claim 19, and further comprising during each computation stage, operating each multiplier-accumulator unit for a plurality of clock cycles equal in number to the number of rows of the first matrix.

22. The method of claim 21, and further comprising adding a product value computed by a multiplier-accumulator unit at a current clock cycle with the result value computed by the result computed by the multiplier-accumulator circuit at the previous clock cycle.

23. The method of claim 18, wherein when the first matrix comprises N×

M data elements and the second matrix comprises M×

N data elements, using comprises using the number of multiplier-accumulator units during a sequence of computation stages according to a sequence {1, 3, 5, . . . , 2*N−

1}.