PROCESSOR AND METHOD FOR EXECUTING MATRIX MULTIPLICATION OPERATION ON PROCESSOR

• US 20180107630A1
• Filed: 05/09/2017
• Published: 04/19/2018
• Est. Priority Date: 10/13/2016
• Status: Active Grant

• Current Assignee: Kunlunxin Technology Company Limited
• Original Assignee: Beijing Baidu Netcom Science and Technology Company Limited (Baidu Incorporated)
• Inventors: Zhou, Ni, Qi, Wei, Wang, Yong, Ouyang, Jian
• Granted Patent: US 10,140,251 B2
• Time in Patent Office: Days
• 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 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• 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/3887 controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: G06F 9/3895 for complex operations, e.g. multidimensional or interleaved address generators, macros
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A processor and a method for executing a matrix multiplication operation on a processor. A specific implementation of the processor includes a data bus and an array processor having k processing units. The data bus is configured to sequentially read n columns of row vectors from an M×N multiplicand matrix and input same to each processing unit in the array processor, read an n×k submatrix from an N×K multiplier matrix and input each column vector of the submatrix to a corresponding processing unit in the array processor, and output a result obtained by each processing unit after executing a multiplication operation. Each processing unit in the array processor is configured to execute in parallel a vector multiplication operation on the input row and column vectors. Each processing unit includes a Wallace tree multiplier having n multipliers and n-1 adders. This implementation improves the processing efficiency of a matrix multiplication operation.

Claims

1. A processor comprising:

a data bus; and

an array processor having k processing units;

the data bus configured to sequentially read n columns of row vectors from an M×

N multiplicand matrix and input the n columns of row vectors to each processing unit in the array processor, read an n×

k submatrix from an N×

K multiplier matrix and input each column vector of the submatrix to a corresponding processing unit in the array processor, and output a result obtained by each processing unit after executing a multiplication operation; and

the each processing unit in the array processor configured to execute in parallel a vector multiplication operation on the input row and column vectors, and the each processing unit comprising a Wallace tree multiplier having n multipliers and n-1 adders,

wherein n, k, M, and N are integers greater than 1.

2. The processor according to claim 1, wherein the processor further comprises a first on-chip memory unit, a second on-chip memory unit, and a third on-chip memory unit;

and

the data bus is further configured to;

buffer the multiplicand matrix and the multiplier matrix to the first on-chip memory unit and the second on-chip memory unit respectively;

sequentially read a corresponding row vector and a column vector respectively from the first on-chip memory unit and the second on-chip memory unit to the each processing unit;

output a result obtained by the each processing unit after executing a multiply-add operation to the third on-chip memory unit; and

buffer data of the third on-chip memory unit.

3. The processor according to claim 2, wherein the buffer operations of the data bus and the vector multiplication operations of the processing units in the array processor are executed in parallel in a back-and-forth manner.

4. The processor according to claim 2, wherein the first on-chip memory unit stores data in units of rows, and the second on-chip memory unit stores data in units of columns.

5. The processor according to claim 4, wherein the third on-chip memory unit stores data in units of rows.

11. The method according to claim 3, wherein the first on-chip memory unit stores data in units of rows, and the second on-chip memory unit stores data in units of columns.

6. A method for executing a matrix multiplication operation on a processor, the processor comprising an array processor having k processing units, the method comprising:

reading n columns of row vectors in an M×

N multiplicand matrix to each processing unit in the array processor, the each processing unit comprising a Wallace tree multiplier having n multipliers and n-1 adders;

reading each of n rows of column vectors in an n×

k submatrix in an N×

K multiplier matrix to a corresponding processing unit in the array processor respectively;

executing in parallel a vector multiplication operation on each column vector and the row vector by using the processing units, the Wallace tree multiplier in the each processing unit being configured to execute in parallel a multiplication operation and an addition operation in the vector multiplication operation; and

outputting a result obtained by the each processing unit after executing the multiplication operation,

wherein n, k, M, and N are integers greater than 1.

7. The method according to claim 6, wherein the processor further comprises a first on-chip memory unit, a second on-chip memory unit, and a third on-chip memory unit;

the reading n columns of row vectors in an M×

N multiplicand matrix to the each processing unit comprises;

buffering the multiplicand matrix to the first on-chip memory unit, and

sequentially reading a row vector from the first on-chip memory unit to the each processing unit in the array processor;

the reading each of n rows of column vectors in an n×

k submatrix in an N×

K multiplier matrix to a corresponding processing unit respectively comprises;

buffering the multiplier matrix to the second on-chip memory unit, and

sequentially reading a corresponding submatrix from the second on-chip memory unit and outputting column vectors in the submatrix to corresponding processing units in the array processor respectively; and

the outputting a result obtained by the each processing unit after executing the multiplication operation comprises;

outputting a result obtained by the each processing unit after executing a multiply-add operation to the third on-chip memory unit, and

buffering data of the third on-chip memory unit.

8. The method according to claim 7, wherein the vector multiplication operations and the data buffer operations are executed in parallel in a back-and-forth manner.

9. The method according to claim 7, wherein the method further comprises:

storing data on the first on-chip memory unit in units of rows; and

storing data on the second on-chip memory unit in units of columns.

10. The method according to claim 9, wherein the method further comprises:

storing data on the third on-chip memory unit in units of rows.

12. The method according to claim 8, wherein the method further comprises:

storing data on the first on-chip memory unit in units of rows; and

storing data on the second on-chip memory unit in units of columns.