Processor and method for executing matrix multiplication operation on processor

• US 10,140,251 B2
• Filed: 05/09/2017
• Issued: 11/27/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
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US15/590,798
• Publication Number:
  US 20180107630A1
• Time in Patent Office: 567 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 1×

n row vectors from an M×

N multiplicand matrix and input the 1×

n row vectors to each processing unit in the array processor, read an n×

k submatrix from an N×

K multiplier matrix and input each of n×

1 column vectors of the n×

k submatrix to a corresponding processing unit in the array processor, and output a result obtained by each processing unit after executing a vector multiplication operation; and

the each processing unit in the array processor configured to execute in parallel the vector multiplication operation on the input 1×

n row vectors and the input n×

1 column vectors, and the each processing unit comprising a Wallace tree multiplier having n multipliers and n−

1 adders, 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,

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,

wherein the sequentially read 1×

n row vectors from an M×

N multiplicand matrix and input the 1×

n row vectors to each processing unit in the array processor comprises;

buffer the M×

N multiplicand matrix to the first on-chip memory unit;

sequentially read the 1×

n row vectors of the M×

N multiplicand matrix from the first on-chip memory unit and input the 1×

n row vectors to the each processing unit in the array processor,

wherein the read an n×

k submatrix from an N×

K multiplier matrix and input each of n×

1 column vectors of the n×

k submatrix to a corresponding processing unit in the array processor comprises;

buffer the N×

K multiplier matrix to the second on-chip memory unit;

read an n×

k submatrix of the N×

K multiplier matrix from the second on-chip memory unit and input each of the n×

1 column vectors of the n×

k submatrix to the corresponding processing unit in the array processor respectively,

wherein the output a result obtained by each processing unit after executing a vector multiplication operation comprises;

output a result obtained by the each processing unit after executing the vector multiplication 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.

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 1×

n 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×

1 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 of the n×

1 column vectors and each of the 1×

n row vectors 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 vector 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 1×

n row vectors in an M×

N multiplicand matrix to the each processing unit comprises;

buffering the M×

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

sequentially reading the 1×

n row vectors of the M×

N multiplicand matrix from the first on-chip memory unit to the each processing unit in the array processor;

the reading each of n×

1 column vectors in an n×

k submatrix in an N×

K multiplier matrix to a corresponding processing unit respectively comprises;

buffering the N×

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

sequentially reading the n×

k corresponding submatrix from the second on-chip memory unit and outputting the n×

1 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 vector multiplication operation comprises;

outputting the result obtained by the each processing unit after executing the vector multiplication 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.

11. The method according to claim 7, 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.

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.