Processor for large graph algorithm computations and matrix operations

Patent metadata

Field	Value
Publication number	US-9529590-B2
Application number	US-201414281132-A
Country	US
Kind code	B2
Filing date	May 19, 2014
Priority date	Jun 11, 2010
Publication date	Dec 27, 2016
Grant date	Dec 27, 2016

Abstract

A node processor and method for performing matrix operations includes storing, in memory, non-zero matrix elements of a first sparse matrix, non-zero matrix elements of a second sparse matrix, and matrix elements of a sparse results matrix mapped to the node processor. A matrix communications module exchanges with other node processors, non-zero matrix elements of one or more of the first sparse matrix, second sparse matrix, and sparse results matrix. An arithmetic logic unit generates partial results based on the non-zero matrix elements of the first sparse matrix and on the non-zero matrix elements of the second sparse matrix stored in memory. The arithmetic logic unit further generates a final value for each matrix element of the sparse results matrix mapped to the node processor based on the partial results generated by the arithmetic logic unit and on partial results received from the other node processors.

First claim

What is claimed is:

1. A node processor for performing sparse matrix operations, comprising:
memory configured to store one or more non-zero matrix elements of a first sparse matrix, one or more non-zero matrix elements of a second sparse matrix, and one or more matrix elements of a sparse results matrix mapped to the node processor;
a matrix communications module adapted to communicate with other node processors, the matrix communications module exchanging, with the other node processors, non-zero matrix elements of one or more of the first sparse matrix, second sparse matrix, and sparse results matrix; and
an arithmetic logic unit generating, in accordance with a matrix operation being performed, partial results based on the non-zero matrix elements of the first sparse matrix and on the non-zero matrix elements of the second sparse matrix stored in the memory, the arithmetic logic unit further generating a final value for each of the matrix elements of the sparse results matrix mapped to the node processor based on the partial results generated by the arithmetic logic unit and on partial results received from the other node processors.

2. The node processor of claim 1 , wherein the matrix communications module sends, to other node processors, partial results generated by the arithmetic logic unit for matrix elements of the sparse results matrix mapped to those other node processors.

3. The node processor of claim 1 , wherein the matrix communications module sends, to another node processor, at least one of the one or more non-zero matrix elements of one or more of the first sparse matrix and second sparse matrix for use, by that other node processor , to generate a partial result.

4. The node processor of claim 1 , further comprising a sorter module to sort the partial results generated by the arithmetic logic unit and the partial results received from the other node processors before the arithmetic logic unit generates the final value for each matrix element of the sparse results matrix mapped to the node processor.

5. The node processor of claim 4 , wherein the sorter module sorts the partial results generated by the arithmetic logic unit and the partial results received from the other node processors based on matrix indices of the partial results.

6. The node processor of claim 5 , wherein the matrix operation is a sparse matrix-sparse matrix multiplication operation, the partial results generated by the arithmetic logic unit are partial products, and wherein the arithmetic logic unit generates the final value for each matrix element of the sparse results matrix mapped to the node processor by accumulating partial products that have identical matrix indices.

7. The node processor of claim 1 , wherein the arithmetic logic unit generates partial results by performing a matrix-element level operation based on the non-zero matrix elements of the first sparse matrix and on the non-zero matrix elements of the second sparse matrix.

8. The node processor of claim 7 , wherein the matrix-element level operation includes one of a Boolean operation, a dot add operation, a dot multiply operation, a minimum operation, and a maximum operation.

9. The node processor of claim 1 , wherein one of the first and second sparse matrices is a sparse vector.

10. The node processor of claim 1 , wherein one of the first and second sparse matrices is in column storage format and the other of the first and second sparse matrices is in row format.

11. The node processor of claim 1 , wherein the second sparse matrix is stored in the memory in a compressed column storage format, and further comprising a column reader that acquires an entire column of non-zero matrix elements of the second sparse matrix that is stored in the memory by acquiring column start address information for the column.

12. The node processor of claim 1 , wherein the second sparse matrix is stored in the memory in a compressed row storage format, and further comprising a row reader that acquires an entire row of non-zero matrix elements of the second sparse matrix that is stored in the memory by acquiring row start address information for the row.

13. The node processor of claim 1 , further comprising a plurality of matrix reader modules, each matrix reader module being dedicated to reading non-zero elements from a different one of the first and second sparse matrices.

14. The node processor of claim 1 , further comprising a matrix writer module that writes matrix elements of the sparse results matrix mapped to the node processor to the memory in a given matrix-storage format.

15. The node processor of claim 1 , further comprising a node controller that coordinates execution of the given matrix operation at the node processor.

16. A method of performing a matrix operation on first and second sparse matrices to produce a sparse results matrix, the method comprising:
storing in memory, by a node processor, one or more non-zero matrix elements of the first sparse matrix-and the second sparse matrix;
exchanging, by the node processor, non-zero matrix elements of one or more of the first sparse matrix and the_second sparse matrix with other node processors;
generating, by the node processor, in accordance with the matrix operation, partial results based on one or more of the non-zero matrix elements of the first sparse matrix and on one or more of the non-zero matrix elements of the second sparse matrix; and
generating, by the node processor, a final value for each matrix element of a sparse results matrix mapped to the node processor based on the partial results generated by the node processor for that matrix element and on the partial results received from the other node processors for that matrix element.

17. The method of claim 16 , further comprising transmitting, by the node processor, to one or more other node processors, partial results generated by the node processor and associated with matrix elements of the sparse results matrix that are mapped to the one or more other node processors.

18. The method of claim 16 , further comprising transmitting, by the node processor, to one or more other node processors, one or more matrix elements of one or more of the first and second sparse matrices that are needed by the one or more other node processors to generate partial results.

19. The method of claim 16 , further comprising sorting, by the node processor, the partial results generated by the node processor and the partial results received from the other node processors before generating the final value for each matrix element of the sparse results matrix mapped to the node processor.

20. The method of claim 16 , wherein the one or more non-zero elements of the first and second sparse matrices are stored in the memory in a compressed storage format.

Assignees

• Massachusetts Inst Technology

Inventors

• Song William S

Classifications

• G06F17/16

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

• G06F17/10 Primary

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06F9/3001 Primary

  Arithmetic instructions · CPC title