Optimized matrix multiplication using vector multiplication of interleaved matrix values

Patent metadata

Field	Value
Publication number	US-10073817-B1
Application number	US-201715792077-A
Country	US
Kind code	B1
Filing date	Oct 24, 2017
Priority date	Mar 11, 2015
Publication date	Sep 11, 2018
Grant date	Sep 11, 2018

Abstract

The present disclosure relates to optimized matrix multiplication using vector multiplication of interleaved matrix values. Two matrices to be multiplied are organized into specially ordered vectors, which are multiplied together to produce a portion of a product matrix.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
for each adjacent pair of columns in a first intermediate matrix, which includes values from a first matrix ordered such that values at a same column index in adjacent pairs of columns from the first matrix are included at concurrent column indices within a same column of the first intermediate matrix, selecting adjacent pairs of rows in a second intermediate matrix, which includes values from a second matrix ordered such that values at a same row index in adjacent pairs of rows from the second matrix are included at concurrent row indices within a same row of the second intermediate matrix, and for each selected adjacent pair of rows:
obtaining a product based on multiplying a row vector that includes a repeating pattern of a pair of row values at the same index in the adjacent pair of rows and column vectors from the adjacent pair of columns containing column values at the same index as the pair of row values; and
increasing numeric values in a column of a result matrix, which is the product of the first matrix and the second matrix, corresponding to the adjacent pair of columns based on the product.

2. The method of claim 1 , comprising:
identifying the first matrix and the second matrix to be multiplied to produce the result matrix, wherein the first matrix is defined by columns, each column including a plurality of column values at corresponding column indices, and the second matrix is defined by rows, each row including a plurality of row values at correspond row indices;
generating the first intermediate matrix to include the column values from the first matrix ordered such that column values at the same index in adjacent pairs of columns from the first matrix are included at concurrent indices within a same column of the first intermediate matrix, the first intermediate matrix including at least two columns; and
generating the second intermediate matrix to include the row values from the second matrix ordered such that row values at the same index in adjacent pairs of rows from the second matrix are included at concurrent indices within a same row of the second intermediate matrix, the second intermediate matrix including at least two rows.

3. The method of claim 1 , wherein multiplying the row vector and the column vectors comprises executing a vector multiplication instruction operable to multiply values at same indices in the row vector and each column vector together to produce a temporary vector, and to add pairs of adjacent values together to produce a product vector.

4. The method of claim 3 , wherein multiplying the row vector and the column vectors comprises converting each product vector into two larger product vectors, each larger product vector including twice as many bits as the product vector.

5. The method of claim 4 , wherein converting each product vector into two larger product vectors comprises multiplying each product vector by a vector including corresponding values of one for each value in the product vector.

6. A computer-implemented method, comprising:
for each adjacent pair of rows in a first intermediate matrix, which includes values from a first matrix ordered such that values at a same row index in adjacent pairs of rows from the first matrix are included at concurrent row indices within a same row of the first intermediate matrix, selecting adjacent pairs of columns in a second intermediate matrix, which includes values from a second matrix ordered such that values at a same column index in adjacent pairs of columns from the second matrix are included at concurrent column indices within a same column of the second intermediate matrix, and for each selected adjacent pair of columns:
obtaining a product based on multiplying a column vector that includes a repeating pattern of a pair of column values at the same index in the adjacent pair of columns and row vectors from the adjacent pair of rows containing row values at the same index as the pair of column values; and
increasing numeric values in a row of a result matrix, which is the product of the first matrix and the second matrix, corresponding to the adjacent pair of rows based on the product.

7. The method of claim 6 , comprising:
identifying the first matrix and the second matrix to be multiplied to produce the result matrix, wherein the first matrix is defined by rows, each row including a plurality of row values at corresponding row indices, and the second matrix is defined by columns, each column including a plurality of column values at corresponding column indices;
generating the first intermediate matrix to include the row values from the first matrix ordered such that row values at the same index in adjacent pairs of rows from the first matrix are included at concurrent indices within a same row of the first intermediate matrix, the first intermediate matrix including at least two rows; and
generating the second intermediate matrix to include the column values from the second matrix ordered such that column values at the same index in adjacent pairs of columns from the second matrix are included at concurrent indices within a same column of the second intermediate matrix, the second intermediate matrix including at least two columns.

8. The method of claim 6 , wherein multiplying the column vector and the row vectors comprises executing a vector multiplication instruction included in the one or more processors and operable to multiply values at same indices in the column vector and each row vector together to produce a temporary vector, and to add pairs of adjacent values together to produce a product vector.

9. The method of claim 8 , wherein multiplying the column vector and the row vectors comprises converting each product vector into two larger product vectors, each larger product vector including twice as many bits as the product vector.

10. The method of claim 9 , wherein converting each product vector into two larger product vectors comprises multiplying each product vector by a vector including corresponding values of one for each value in the product vector.

11. A system comprising:
one or more storage devices for storing data comprising instructions; and
one or more processors operable to execute the instructions to perform operations comprising:
for each adjacent pair of columns in a first intermediate matrix, which includes values from a first matrix ordered such that values at a same column index in adjacent pairs of columns from the first matrix are included at concurrent column indices within a same column of the first intermediate matrix, selecting adjacent pairs of rows in a second intermediate matrix, which includes values from a second matrix ordered such that values at a same row index in adjacent pairs of rows from the second matrix are included at concurrent row indices within a same row of the second intermediate matrix, and for each selected adjacent pair of rows:
obtaining a product based on multiplying a row vector that includes a repeating pattern of a pair of row values at the same index in the adjacent pair of rows and column vectors from the adjacent pair of columns containing column values at the same index as the pair of row values; and
increasing numeric values in a column of a result matrix, which is the product of the first matrix and the second matrix, corresponding to the adjacent pair of columns based on the product.

12. The system of claim 11 , the operations comprising:
identifying the first matrix and the second matrix to be multiplied to produce the result matrix, wherein the first matrix is defined by columns, each column including a plurality of column values at

Assignees

• Google Llc

Inventors

• Patil Nishant
• Sarett Matthew
• Govindaraju Rama Krishna
• Steiner Benoit
• Vanhoucke Vincent O

Classifications

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title