This is an automated email from the ASF dual-hosted git repository.
mboehm7 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/systemml.git
The following commit(s) were added to refs/heads/master by this push:
new 01da6a6 [SYSTEMML-2468] Extended MNC exact propagation of sketch
counts
01da6a6 is described below
commit 01da6a6fef8bbfe68734da64604943547f45ae79
Author: Matthias Boehm <mboe...@gmail.com>
AuthorDate: Tue Feb 19 14:13:04 2019 +0100
[SYSTEMML-2468] Extended MNC exact propagation of sketch counts
This patch extends the MNC sketch propagation by a special case, where
we can exactly infer (in an inexpensive manner) the output column count
histogram, if the lhs has one non-zero per row and the rhs is leaf node
and sparse. However, initial experiments were not fully conclusive and
hecnce, this is still disabled.
---
.../sysml/hops/estim/EstimatorMatrixHistogram.java | 30 +++++++++++++++++++---
1 file changed, 27 insertions(+), 3 deletions(-)
diff --git
a/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java
b/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java
index a82feed..5f1abff 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java
@@ -42,6 +42,7 @@ public class EstimatorMatrixHistogram extends
SparsityEstimator
{
//internal configurations
private static final boolean DEFAULT_USE_EXTENDED = true;
+ private static final boolean ADVANCED_SKETCH_PROP = false;
private final boolean _useExtended;
@@ -71,6 +72,7 @@ public class EstimatorMatrixHistogram extends
SparsityEstimator
}
//sketch propagation for intermediates other than final result
+ h2.setData(root.getRight().isLeaf() ? root.getRight().getData()
: null);
MatrixHistogram outMap = MatrixHistogram
.deriveOutputHistogram(h1, h2, ret, root.getOp(),
root.getMisc());
root.setSynopsis(outMap);
@@ -227,6 +229,7 @@ public class EstimatorMatrixHistogram extends
SparsityEstimator
private final int rNonEmpty, cNonEmpty; //number of non-empty
rows/cols (w/ empty is nnz=0)
private final int rNdiv2, cNdiv2; //number of rows/cols
with nnz > #cols/2 and #rows/2
private boolean fullDiag; //true if there exists
a full diagonal of nonzeros
+ private MatrixBlock _data = null; //optional leaf data
public MatrixHistogram(MatrixBlock in, boolean useExcepts) {
// 1) allocate basic synopsis
@@ -348,6 +351,10 @@ public class EstimatorMatrixHistogram extends
SparsityEstimator
IntStream.range(0, getCols()).mapToLong(i->
cNnz[i]).sum();
}
+ public void setData(MatrixBlock mb) {
+ _data = mb;
+ }
+
public static MatrixHistogram
deriveOutputHistogram(MatrixHistogram h1, MatrixHistogram h2, double spOut,
OpCode op, long[] misc) {
switch(op) {
case MM: return deriveMMHistogram(h1, h2,
spOut);
@@ -396,6 +403,7 @@ public class EstimatorMatrixHistogram extends
SparsityEstimator
}
}
+ @SuppressWarnings("unused")
private static MatrixHistogram
deriveMMHistogram(MatrixHistogram h1, MatrixHistogram h2, double spOut) {
//exact propagation if lhs or rhs full diag
if( h1.fullDiag ) return h2;
@@ -416,9 +424,25 @@ public class EstimatorMatrixHistogram extends
SparsityEstimator
rMaxNnz = Math.max(rMaxNnz, rNnz[i]);
}
int[] cNnz = new int[h2.getCols()];
- for( int i=0; i<h2.getCols(); i++ ) {
- cNnz[i] = probRound(nnzOut/nnz2 * h2.cNnz[i],
rn);
- cMaxNnz = Math.max(cMaxNnz, cNnz[i]);
+ if( ADVANCED_SKETCH_PROP && h1.rMaxNnz <= 1
+ && h2._data != null &&
h2._data.isInSparseFormat() ) {
+ SparseBlock rhs = h2._data.getSparseBlock();
+ for( int j=0; j<h1.getCols(); j++ ) {
+ if( h1.cNnz[j] == 0 || h2.rNnz[j] == 0 )
+ continue;
+ int apos = rhs.pos(j);
+ int alen = rhs.size(j);
+ int[] aix = rhs.indexes(j);
+ int scale = h1.cNnz[j];
+ for(int k=apos; k<apos+alen; k++ )
+ cNnz[aix[k]] += scale;
+ }
+ }
+ else {
+ for( int i=0; i<h2.getCols(); i++ ) {
+ cNnz[i] = probRound(nnzOut/nnz2 *
h2.cNnz[i], rn);
+ cMaxNnz = Math.max(cMaxNnz, cNnz[i]);
+ }
}
//construct new histogram object
