You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemml.apache.org by mb...@apache.org on 2018/10/21 00:30:35 UTC
systemml git commit: [MINOR] Utility to obtain the exact output
sparsity of sparse products
Repository: systemml
Updated Branches:
refs/heads/master ab8cccdff -> cca6356f8
[MINOR] Utility to obtain the exact output sparsity of sparse products
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/cca6356f
Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/cca6356f
Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/cca6356f
Branch: refs/heads/master
Commit: cca6356f8de49dcb6aeb1f23cefd53930309fedb
Parents: ab8cccd
Author: Matthias Boehm <mb...@gmail.com>
Authored: Sun Oct 21 02:30:25 2018 +0200
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Sun Oct 21 02:30:25 2018 +0200
----------------------------------------------------------------------
.../sysml/hops/estim/EstimationUtils.java | 56 ++++++++++++++++++++
1 file changed, 56 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/systemml/blob/cca6356f/src/main/java/org/apache/sysml/hops/estim/EstimationUtils.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimationUtils.java b/src/main/java/org/apache/sysml/hops/estim/EstimationUtils.java
index d4d30bb..29de2f5 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimationUtils.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimationUtils.java
@@ -21,6 +21,7 @@ package org.apache.sysml.hops.estim;
import java.util.Arrays;
+import org.apache.sysml.runtime.DMLRuntimeException;
import org.apache.sysml.runtime.matrix.data.DenseBlock;
import org.apache.sysml.runtime.matrix.data.MatrixBlock;
import org.apache.sysml.runtime.matrix.data.SparseBlock;
@@ -106,4 +107,59 @@ public abstract class EstimationUtils
}
return retNnz;
}
+
+ public static long getSparseProductOutputNnz(MatrixBlock m1, MatrixBlock m2) {
+ if( !m1.isInSparseFormat() || !m2.isInSparseFormat() )
+ throw new DMLRuntimeException("Invalid call to sparse output nnz estimation.");
+
+ final int m = m1.getNumRows();
+ final int n2 = m2.getNumColumns();
+ long retNnz = 0;
+
+ SparseBlock a = m1.getSparseBlock();
+ SparseBlock b = m2.getSparseBlock();
+
+ SparseRowVector tmpS = new SparseRowVector(1024);
+ double[] tmpD = null;
+
+ for( int i=0; i<m; i++ ) {
+ if( a.isEmpty(i) ) continue;
+ int alen = a.size(i);
+ int apos = a.pos(i);
+ int[] aix = a.indexes(i);
+ double[] avals = a.values(i);
+
+ //compute number of aggregated non-zeros for input row
+ int nnz1 = (int) Math.min(UtilFunctions.computeNnz(b, aix, apos, alen), n2);
+ boolean ldense = nnz1 > n2 / 128;
+
+ //perform vector-matrix multiply w/ dense or sparse output
+ if( ldense ) { //init dense tmp row
+ tmpD = (tmpD == null) ? new double[n2] : tmpD;
+ Arrays.fill(tmpD, 0);
+ }
+ else {
+ tmpS.setSize(0);
+ }
+ for( int k=apos; k<apos+alen; k++ ) {
+ if( b.isEmpty(aix[k]) ) continue;
+ int blen = b.size(aix[k]);
+ int bpos = b.pos(aix[k]);
+ int[] bix = b.indexes(aix[k]);
+ double aval = avals[k];
+ double[] bvals = b.values(aix[k]);
+ if( ldense ) { //dense aggregation
+ for( int j=bpos; j<bpos+blen; j++ )
+ tmpD[bix[j]] += aval * bvals[j];
+ }
+ else { //sparse aggregation
+ for( int j=bpos; j<bpos+blen; j++ )
+ tmpS.add(bix[j], aval * bvals[j]);
+ }
+ }
+ retNnz += !ldense ? tmpS.size() :
+ UtilFunctions.computeNnz(tmpD, 0, n2);
+ }
+ return retNnz;
+ }
}