PERFORMANCE IN SPARSE MATRIX VECTOR (SpMV) MULTIPLICATION USING ROW SIMILARITY

Abstract

A technical solution to the technical problem of how to improve performance when performing SpMV multiplication uses sparse matrix row similarity to schedule SpMV multiplication operations. CSR representation metadata is generated for a CSR representation and indicates the locations of non-zero values in the rows of the corresponding sparse matrix or the cache locations of column data needed for SpMV multiplication operations. The CSR representation metadata is used to determine the similarity of rows in the sparse matrix based upon Cosine similarity, Jaccard similarity, Locality Sensitive Hashing (LSH) that approximates Jaccard similarity, or other measures of similarity. The row similarity is used to schedule SpMV multiplication operations to increase data locality, reduce cache misses, reduce time stalling on memory accesses, and reduce bandwidth consumption. Implementations include the use of similarity thresholds to schedule SpMV multiplication operations on particular threads and processing elements and load balancing to further improve performance.

What is claimed is: 
     
         1 . A processor comprising:
 a scheduler configured to schedule sparse matrix multiplication operations based at least upon similarity of two or more rows in a sparse matrix used for the matrix multiplication operations.   
     
     
         2 . The processor of  claim 1 , wherein the similarity of the two or more rows in the sparse matrix used for the sparse matrix multiplication operations is based upon locations of non-zero values in the two or more rows of the sparse matrix. 
     
     
         3 . The processor of  claim 2 , wherein the locations of non-zero values in the two or more rows in the sparse matrix are determined during generation of a Compressed Sparse Row (CSR) representation of the sparse matrix. 
     
     
         4 . The processor of  claim 1 , wherein the similarity of the two or more rows in the sparse matrix used for the sparse matrix multiplication operations is based upon locations of cached data used for the matrix multiplication operations. 
     
     
         5 . The processor of  claim 1 , wherein the similarity of the two or more rows in the sparse matrix used for the sparse matrix multiplication operations is determined using one or more of Cosine similarity or Jaccard similarity of the two or more rows in the sparse matrix. 
     
     
         6 . The processor of  claim 1 , wherein the similarity of the two or more rows in the sparse matrix used for the sparse matrix multiplication operations is determined by:
 determining a signature for each row from the two or more rows, and   determining that values in one or more portions of the signature for each row from the two or more rows are the same.   
     
     
         7 . The processor of  claim 6 , wherein the signature for each row from the two or more rows is a signature vector and is determined by:
 processing, using a plurality of permutation functions, metadata for the row to generate a plurality of permutations, wherein the metadata for the row indicates locations of non-zero values in the row, and   selecting, from each permutation from the plurality of permutations, a value that is included in the signature vector.   
     
     
         8 . The processor of  claim 1 , wherein the scheduler is further configured to:
 determine a signature for each row from the two or more rows,   compare one or more portions of the signatures for the two or more rows to identify a plurality of clusters of similar rows, and   sort the plurality of clusters based upon one or more of the number of rows in each cluster from the plurality of clusters or a total number of non-zero values in the rows of each cluster from the plurality of clusters.   
     
     
         9 . The processor of  claim 8 , wherein the scheduler is further configured to:
 sort two or more rows within a particular cluster, from the plurality of clusters, based upon a number of non-zero values in each of the two or more rows within the particular cluster.   
     
     
         10 . The processor of  claim 1 , wherein accesses to data in the two or more rows in the sparse matrix are scheduled together. 
     
     
         11 . The processor of  claim 1 , wherein the scheduler is further configured to cause two or more different threads accessing the two or more rows in the sparse matrix to execute on one or more of a core with a cache, or on two or more cores with a shared cache. 
     
     
         12 . The processor of  claim 11 , wherein the two or more rows in the sparse matrix have a similarity that satisfies a similarity threshold. 
     
     
         13 . The processor of  claim 1 , wherein the scheduler is further configured to assign the sparse matrix multiplication operations to one or more of: one or more threads or one or more wavefronts based upon the similarity of the two or more rows in the sparse matrix and load balancing. 
     
     
         14 . The processor of  claim 1 , wherein the processor is one or more of a central processing unit, a graphics processing unit, or a programmed controller. 
     
     
         15 . A method comprising:
 scheduling, by a scheduler for a processor, sparse matrix multiplication operations based at least upon similarity of two or more rows in a sparse matrix used for the matrix multiplication operations.   
     
     
         16 . The method of  claim 15 , wherein the similarity of the two or more rows in the sparse matrix used for the sparse matrix multiplication operations is based upon locations of non-zero values in the two or more rows of the sparse matrix. 
     
     
         17 . The method of  claim 15 , wherein the similarity of the two or more rows in the sparse matrix used for the sparse matrix multiplication operations is based upon locations of cached data used for the matrix multiplication operations. 
     
     
         18 . The method of  claim 15 , wherein the similarity of the two or more rows in the sparse matrix used for the sparse matrix multiplication operations is determined by:
 determining a signature for each row from the two or more rows, and   determining that values in one or more portions of the signature for each row from the two or more rows are the same.   
     
     
         19 . The method of  claim 15 , further comprising:
 determining, by the scheduler, a signature for each row from the two or more rows,   comparing, by the scheduler, one or more portions of the signatures for the two or more rows to identify a plurality of clusters of similar rows, and   sorting, by the scheduler, the plurality of clusters based upon one or more of the number of rows in each cluster from the plurality of clusters or a total number of non-zero values in the rows of each cluster from the plurality of clusters.   
     
     
         20 . The method of  claim 15 , wherein accesses to data in the two or more rows in the sparse matrix are scheduled together.