Sparse matrix multiplication in associative memory device

Patent metadata

Field	Value
Publication number	US-10489480-B2
Application number	US-201815873002-A
Country	US
Kind code	B2
Filing date	Jan 17, 2018
Priority date	Jan 22, 2017
Publication date	Nov 26, 2019
Grant date	Nov 26, 2019

Abstract

A method for multiplying a first sparse matrix by a second sparse matrix in an associative memory device includes storing multiplicand information related to each non-zero element of the second sparse matrix in a computation column of the associative memory device; the multiplicand information includes at least a multiplicand value. According to a first linear algebra rule, the method associates multiplier information related to a non-zero element of the first sparse matrix with each of its associated multiplicands, the multiplier information includes at least a multiplier value. The method concurrently stores the multiplier information in the computation columns of each associated multiplicand. The method, concurrently on all computation columns, multiplies a multiplier value by its associated multiplicand value to provide a product in the computation column, and adds together products from computation columns, associated according to a second linear algebra rule, to provide a resultant matrix.

First claim

What is claimed is:

1. A method for multiplying a first sparse matrix by a second sparse matrix in an associative memory device, the method comprising:
storing multiplicand information related to each non-zero element of said second sparse matrix in a computation column of said associative memory device, said multiplicand information comprising at least a multiplicand value;
according to a first linear algebra rule, associating multiplier information related to a non-zero element of said first sparse matrix with each of its associated multiplicands, said multiplier information comprising at least a multiplier value;
concurrently storing said multiplier information in said computation columns of each said associated multiplicand;
concurrently in all computation columns, multiplying a multiplier value by its associated multiplicand value to provide a product in said computation column; and
adding together products from computation columns, associated according to a second linear algebra rule, providing a resultant matrix.

2. The method of claim 1 wherein said multiplicand information and said multiplier information also comprises a row index and a column index.

3. The method of claim 2 wherein said first linear algebra rule comprises a row index of said multiplier is equal to a column index of said multiplicand.

4. The method of claim 2 wherein said second linear algebra rule comprises according to the column index of the multiplicands in said computation columns.

5. The method of claim 2 wherein said first sparse matrix is a dense vector and said resultant matrix is a vector.

6. The method of claim 4 wherein:
each row of said first sparse matrix is a vector and each vector is computed separately; and
said second linear algebra rule also comprises according to an equal row index of multipliers in said computation columns.

7. The method of claim 2 wherein said associating comprises:
concurrently searching all computation columns associated with each multiplier of said first sparse matrix.

8. The method of claim 7 wherein said concurrently searching also comprises:
for each row of said first sparse matrix, concurrently comparing a column index of said multiplier with a row index of all said computation columns and marking all computation columns having a row index identical to said column index.

9. The method of claim 2 wherein said adding also comprises concurrently searching all computation columns having the same column index and calculating a sum of all products in computation columns having the same column index.

10. A system for multiplying a first sparse matrix comprising multiplier data by a second sparse matrix comprising multiplicand data, the system comprising:
an associative memory array arranged in rows and computation columns;
a data organizer to store data regarding each pair of multiplier and multiplicand in said computation columns, said data comprises at least a value and said multiplier and multiplicand associated according to a first linear algebra rule;
a multiplication unit to concurrently activate all computation columns, wherein said activation provides a product of a multiplication operation between a value of said multiplier and a value of said multiplicand in each computation column; and
an adder to concurrently add products in associated computation columns.

11. The system of claim 10 wherein said data also comprises a row index and a column index.

12. The system of claim 10 wherein said associated computation columns share the column of said second sparse matrix.

13. A method for multiplying a vector and a sparse matrix in an associative memory device, the method comprising:
for each non-zero matrix element of said sparse matrix, storing a matrix value of said matrix element, a matrix row index of said matrix element and a matrix column index of said matrix element in a computation column of said associative memory device;
storing a vector value from a vector index in said vector in computation columns having a matrix row index identical to said vector location;
concurrently, in all computation columns, multiplying a matrix value by a vector value to create a product; and
adding together all products in computation columns having a same matrix column index to provide a result vector.

14. The method of claim 13 wherein said storing a vector value also comprises:
concurrently searching all computation columns having matrix row index identical to each vector index and concurrently storing a vector value from said vector index in all computation columns found by said searching.

15. A method of in memory multiplication with a sparse matrix, the method comprising:
storing in a memory array a representation of each non-zero element of said sparse matrix as a value and at least one index;
selecting a multiplier from said non-zero elements and fetching a multiplier-index of said selected multiplier;
storing multiplicands to be multiplied by said sparse matrix in columns of said memory array, said multiplicands having a value and at least a multiplicand-index;
searching among said multiplicands for those having a multiplicand-index which matches said multiplier-index;
in parallel distributing said multiplier to columns of said matched multiplicands; and
in parallel multiplying said multipliers by said multiplicands and adding multiplication results from all said columns.

Assignees

• Gsi Technology Inc

Inventors

• Akerib Avidan

Classifications

• G06F17/16 Primary

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

• G06F7/57

  Arithmetic logic units [ALU], i.e. arrangements or devices for performing two or more of the operations covered by groups G06F7/483 – G06F7/556 or for performing logical operations {(G06F7/49, G06F7/491 take precedence)} · CPC title

• G06F7/5443

  Sum of products (for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00) · CPC title