Method for performing sparse matrix-matrix multiplication

Patent metadata

Field	Value
Publication number	US-9971736-B2
Application number	US-201514945643-A
Country	US
Kind code	B2
Filing date	Nov 19, 2015
Priority date	Nov 19, 2015
Publication date	May 15, 2018
Grant date	May 15, 2018

Abstract

Embodiments include performing sparse matrix-matrix multiplication. Aspects include receiving a first matrix and a second matrix, providing a pseudo-space for the first and second matrices, and defining pseudo-space segments and assigning the pseudo-space segments to certain processes. Aspects also include assigning matrix elements of the first and second matrix to pseudo-space segments using a midpoint method thereby assigning the matrix elements to processes associated with the pseudo-space segments, assigning a result matrix element of a result matrix to a pseudo-space segment using a midpoint method thereby assigning the result matrix element to a further process associated with the pseudo-space segment and transmitting matrix elements of the first and second matrix required to establish a result matrix element to the further process which processes the result matrix element. Aspects further include performing a multiplication procedure by the further process based on the received matrix elements of the first and second matrix.

First claim

What is claimed is:

1. A computer-implemented method for performing sparse matrix-matrix multiplication, the method comprising:
receiving a first matrix and a second matrix, said matrices being matrices with decay;
providing a pseudo-space for said first and second matrices, the pseudo-space comprising pseudo particles indicative for mapping matrix elements of the first and second matrix into said pseudo-space;
defining pseudo-space segments based on a number of available processors and assigning said pseudo-space segments to certain processors of the available processors;
assigning matrix elements of said first and second matrix to pseudo-space segments using a midpoint method thereby storing the matrix elements in respective caches corresponding to the certain processors associated with said pseudo-space segments;
assigning a result matrix element of a result matrix to a pseudo-space segment using a midpoint method thereby assigning said result matrix element to a further processor associated with said pseudo-space segment;
transmitting matrix elements of the first and second matrix required to establish a result matrix element to said further processor which processes said result matrix element; and
performing a multiplication procedure by said further processor based on the received matrix elements of the first and second matrix.

2. The computer-implemented method of claim 1 , wherein defining a pseudo space comprises using an optimization procedure, specifically a constrained optimization procedure which maps the matrix elements of the first and second matrix to one of said pseudo particles or midpoints between said pseudo particles.

3. The computer-implemented method of claim 2 , wherein the optimization procedure uses a spatial decomposition method.

4. The computer-implemented method of claim 1 , the distance between two pseudo particles or midpoints between said pseudo particles being indicative for the interaction of the matrix elements associated with said pseudo particles or said midpoints between pseudo particles.

5. The computer-implemented method of claim 1 , the dimension of the pseudo space depending on the dimension of the problem underlying the first and/or second matrix.

6. The computer-implemented method of claim 1 , the step of defining pseudo space segments comprises dividing the pseudo space in a number of segments, said number of segments being equal to the number of processes provided for sparse matrix-matrix multiplication.

7. The computer-implemented method of claim 1 , each process provided for sparse matrix-matrix multiplication is handled by a separate processor or at least a portion of said processes being handled by a common processor.

8. The computer-implemented method of claim 1 , wherein assigning matrix elements of said first and second matrix to pseudo-space segments is performed by identifying a pair of pseudo particles corresponding to the matrix element, determining the midpoint between said pseudo particles and determining the pseudo-space segment in which said midpoint is located.

9. The computer-implemented method of claim 1 , wherein assigning matrix elements of said first and second matrix to pseudo-space segments is limited to those pseudo particle tuples for which the following inequation is fulfilled:
L≤R max ;

wherein: L is the distance between the pseudo particle tuple; and
R max is the characteristic radius.

10. The computer-implemented method of claim 1 , wherein assigning a result matrix element of a result matrix to a pseudo-space segment is performed by identifying a pair of pseudo particles corresponding to the result matrix element, determining the midpoint between said pseudo particles and determining the pseudo-space segment in which said midpoint is located.

11. The computer-implemented method of claim 1 , wherein at least one filtering step is performed in order to reduce the amount of data to be transmitted between different processes and/or to reduce the number of multiplication steps which do not contribute to the result matrix.

12. The computer-implemented method of claim 1 , performing a pre-filtering step which reduces the number of matrix elements involved in a certain multiplication step by considering the interaction of the matrix elements of the first or second matrix with respect to the result matrix elements.

13. The computer-implemented method of claim 1 , performing a pre-filtering step which suppresses transmission of matrix elements to the further process which have a distance to the boundaries of the pseudo space segment associated with said further process greater than the characteristic radius R max /2.

14. The computer-implemented method of claim 1 , wherein, after transmission of the matrix elements to the further process, a post-filtering is performed, said post filtering considering the spatial distribution of midpoints representing matrix elements of the first and second matrix involved in the calculation of a certain result matrix element.

15. The computer-implemented method of claim 1 , wherein, after transmission of the matrix elements to the further process, a post-filtering is performed, said post filtering suppressing the usage of those matrix elements of the first and second matrix for calculating a certain result matrix element, which are associated with midpoints that have a distance in the pseudo space to the respective mid point representing the result matrix element greater than the characteristic radius R max /2.

16. The computer-implemented method of claim 1 , the first and second matrices being matrices with exponential or approximately exponential decay.

17. The computer-implemented method of claim 1 , the values of the matrix elements of the first and second matrix being characterized by the in equation:



A
ij



<

const
·

e

r
ij
d

R
max

wherein: |A ij | is the absolute value of a matrix element A ij ;
r ij is the distance between pseudo particles i, j;
d is the dimensionality of the problem; and
R max is the characteristic radius of matrix A.

18. The computer-implemented method of claim 17 , wherein r ij , d and R max form upper bound values and are calculated by investigating all entries of the respective matrix A.

19. A computer program product for performing sparse matrix-matrix multiplication, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to execute the method comprising:
receiving a first matrix and a second matrix, said matrices being matrices with decay;
providing a pseudo-space for said first and second matrices, the pseudo-space comprising pseudo particles indicative for mapping matrix elements of the first and second matrix into said pseudo-space;
defining pseudo-space segments based on a number of available processors and assigning said pseudo-sp

Assignees

• IBM

Inventors

• Curioni Alessandro
• Laino Teodoro
• Weber Valery

Classifications

• G06F17/16 Primary

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