Repository: systemml Updated Branches: refs/heads/master 42071989c -> 9ea71d534
[MINOR] Performance sparse matrix-vector multiply w/ dense rows This patch improves the performance of sparse matrix-vector multiplication for the case where the sparse matrix contains fully dense rows. The trick is to dispatch dense dot product operations for any dense row. Since matrix-vector multiplication (dense and sparse) is memory bandwidth bound, we gain performance by not reading the column indexes. Even if the matrix fits into caches, this is beneficial by avoiding unnecessary gather operations. On a scenario of a 1M x 1K matrix with 30% dense and otherwise empty rows, this patch improved the MV multiply performance from 140ms to 95s because we read 8B instead of 12B per non-zero. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/9ea71d53 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/9ea71d53 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/9ea71d53 Branch: refs/heads/master Commit: 9ea71d534a7ee544e380992652ba3f792dc01e35 Parents: 4207198 Author: Matthias Boehm <[email protected]> Authored: Sat Apr 28 13:26:00 2018 -0700 Committer: Matthias Boehm <[email protected]> Committed: Sat Apr 28 13:26:00 2018 -0700 ---------------------------------------------------------------------- .../sysml/runtime/matrix/data/LibMatrixMult.java | 16 ++++++++++------ 1 file changed, 10 insertions(+), 6 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/9ea71d53/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixMult.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixMult.java b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixMult.java index ddf063f..92a6b7a 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixMult.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixMult.java @@ -1182,7 +1182,7 @@ public class LibMatrixMult c.set(0, 0, dotProduct(a.values(0), b.values(0), a.indexes(0), a.pos(0), 0, a.size(0))); } else if( n==1 && cd<=2*1024 ) { //MATRIX-VECTOR (short rhs) - matrixMultSparseDenseMVShortRHS(a, b, c, rl, ru); + matrixMultSparseDenseMVShortRHS(a, b, c, cd, rl, ru); } else if( n==1 ) { //MATRIX-VECTOR (tall rhs) matrixMultSparseDenseMVTallRHS(a, b, c, cd, xsp, rl, ru); @@ -1220,13 +1220,17 @@ public class LibMatrixMult } } - private static void matrixMultSparseDenseMVShortRHS(SparseBlock a, DenseBlock b, DenseBlock c, int rl, int ru) { + private static void matrixMultSparseDenseMVShortRHS(SparseBlock a, DenseBlock b, DenseBlock c, int cd, int rl, int ru) { double[] bvals = b.valuesAt(0); double[] cvals = c.valuesAt(0); - for( int i=rl; i<ru; i++ ) - if( !a.isEmpty(i) ) - cvals[i] = dotProduct(a.values(i), bvals, - a.indexes(i), a.pos(i), 0, a.size(i)); + for( int i=rl; i<ru; i++ ) { + if( a.isEmpty(i) ) continue; + int alen = a.size(i); + int apos = a.pos(i); + double[] avals = a.values(i); + cvals[i] = (alen==cd) ? dotProduct(avals, bvals, apos, 0, cd) : + dotProduct(avals, bvals, a.indexes(i), apos, 0, alen); + } } private static void matrixMultSparseDenseMVTallRHS(SparseBlock a, DenseBlock b, DenseBlock c, int cd, long xsp, int rl, int ru) {
