Title: Sparse Matrix Multiplication On An Associative Processor,
Abstract: Sparse matrix multiplication is an important component of linear algebra
computations. Implementing sparse matrix multiplication on an associative
processor (AP) enables high level of parallelism, where a row of one matrix is
multiplied in parallel with the entire second matrix, and where the execution
time of vector dot product does not depend on the vector size. Four sparse
matrix multiplication algorithms are explored in this paper, combining AP and
baseline CPU processing to various levels. They are evaluated by simulation on
a large set of sparse matrices. The computational complexity of sparse matrix
multiplication on AP is shown to be an O(nnz) where nnz is the number of
nonzero elements. The AP is found to be especially efficient in binary sparse
matrix multiplication. AP outperforms conventional solutions in power
efficiency.