Repository: systemml Updated Branches: refs/heads/master 4916d454b -> 31610e36d
[SYSTEMML-2479] Extended MNC estimator for other operations, part 1 Closes #811. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/31610e36 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/31610e36 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/31610e36 Branch: refs/heads/master Commit: 31610e36db121bcfa289210fdff900682a6b96ec Parents: 4916d45 Author: Johanna Sommer <[email protected]> Authored: Wed Aug 1 18:45:50 2018 -0700 Committer: Matthias Boehm <[email protected]> Committed: Wed Aug 1 19:46:25 2018 -0700 ---------------------------------------------------------------------- .../sysml/hops/estim/EstimatorBasicAvg.java | 18 +++-- .../sysml/hops/estim/EstimatorBasicWorst.java | 18 +++-- .../sysml/hops/estim/EstimatorBitsetMM.java | 14 ++-- .../sysml/hops/estim/EstimatorDensityMap.java | 14 ++-- .../sysml/hops/estim/EstimatorLayeredGraph.java | 10 ++- .../hops/estim/EstimatorMatrixHistogram.java | 73 +++++++++++++++++--- .../sysml/hops/estim/EstimatorSample.java | 14 ++-- .../sysml/hops/estim/SparsityEstimator.java | 31 ++++++--- 8 files changed, 140 insertions(+), 52 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/31610e36/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicAvg.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicAvg.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicAvg.java index efd4195..259ab43 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicAvg.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicAvg.java @@ -19,8 +19,8 @@ package org.apache.sysml.hops.estim; +import org.apache.commons.lang.NotImplementedException; import org.apache.sysml.hops.OptimizerUtils; -import org.apache.sysml.runtime.matrix.MatrixCharacteristics; import org.apache.sysml.runtime.matrix.data.MatrixBlock; /** @@ -41,16 +41,20 @@ public class EstimatorBasicAvg extends SparsityEstimator @Override public double estim(MatrixBlock m1, MatrixBlock m2) { - return estim(m1.getMatrixCharacteristics(), m2.getMatrixCharacteristics()); + return estimIntern(m1.getSparsity(), m2.getSparsity(), + m1.getNumRows(), m1.getNumColumns(), m2.getNumColumns()); } @Override - public double estim(MatrixCharacteristics mc1, MatrixCharacteristics mc2) { - return estimIntern( - OptimizerUtils.getSparsity(mc1), OptimizerUtils.getSparsity(mc2), - mc1.getRows(), mc1.getCols(), mc2.getCols()); + public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) { + throw new NotImplementedException(); } - + + @Override + public double estim(MatrixBlock m, OpCode op) { + throw new NotImplementedException(); + } + private double estimIntern(double sp1, double sp2, long m, long k, long n) { return OptimizerUtils.getMatMultSparsity(sp1, sp2, m, k, n, false); } http://git-wip-us.apache.org/repos/asf/systemml/blob/31610e36/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicWorst.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicWorst.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicWorst.java index 2ca32a7..736affe 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicWorst.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicWorst.java @@ -19,8 +19,8 @@ package org.apache.sysml.hops.estim; +import org.apache.commons.lang.NotImplementedException; import org.apache.sysml.hops.OptimizerUtils; -import org.apache.sysml.runtime.matrix.MatrixCharacteristics; import org.apache.sysml.runtime.matrix.data.MatrixBlock; /** @@ -45,14 +45,18 @@ public class EstimatorBasicWorst extends SparsityEstimator @Override public double estim(MatrixBlock m1, MatrixBlock m2) { - return estim(m1.getMatrixCharacteristics(), m2.getMatrixCharacteristics()); + return estimIntern(m1.getSparsity(), m2.getSparsity(), + m1.getNumRows(), m1.getNumColumns(), m2.getNumColumns()); } - + + @Override + public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) { + throw new NotImplementedException(); + } + @Override - public double estim(MatrixCharacteristics mc1, MatrixCharacteristics mc2) { - return estimIntern( - OptimizerUtils.getSparsity(mc1), OptimizerUtils.getSparsity(mc2), - mc1.getRows(), mc1.getCols(), mc2.getCols()); + public double estim(MatrixBlock m, OpCode op) { + throw new NotImplementedException(); } private double estimIntern(double sp1, double sp2, long m, long k, long n) { http://git-wip-us.apache.org/repos/asf/systemml/blob/31610e36/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java index 98fb950..011975e 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java @@ -21,8 +21,8 @@ package org.apache.sysml.hops.estim; import java.util.BitSet; +import org.apache.commons.lang.NotImplementedException; import org.apache.sysml.hops.OptimizerUtils; -import org.apache.sysml.runtime.matrix.MatrixCharacteristics; import org.apache.sysml.runtime.matrix.data.DenseBlock; import org.apache.sysml.runtime.matrix.data.MatrixBlock; import org.apache.sysml.runtime.matrix.data.SparseBlock; @@ -66,11 +66,15 @@ public class EstimatorBitsetMM extends SparsityEstimator { return OptimizerUtils.getSparsity( // aggregate output histogram outMap.getNumRows(), outMap.getNumColumns(), outMap.getNonZeros()); } - + + @Override + public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) { + throw new NotImplementedException(); + } + @Override - public double estim(MatrixCharacteristics mc1, MatrixCharacteristics mc2) { - LOG.warn("Meta-data-only estimates not supported in EstimatorBitsetMM, falling back to EstimatorBasicAvg."); - return new EstimatorBasicAvg().estim(mc1, mc2); + public double estim(MatrixBlock m, OpCode op) { + throw new NotImplementedException(); } private static class BitsetMatrix { http://git-wip-us.apache.org/repos/asf/systemml/blob/31610e36/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java index b6d8bd4..c86ad21 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java @@ -19,8 +19,8 @@ package org.apache.sysml.hops.estim; +import org.apache.commons.lang.NotImplementedException; import org.apache.sysml.hops.OptimizerUtils; -import org.apache.sysml.runtime.matrix.MatrixCharacteristics; import org.apache.sysml.runtime.matrix.data.DenseBlock; import org.apache.sysml.runtime.matrix.data.MatrixBlock; import org.apache.sysml.runtime.matrix.data.SparseBlock; @@ -81,11 +81,15 @@ public class EstimatorDensityMap extends SparsityEstimator return OptimizerUtils.getSparsity( //aggregate output histogram m1.getNumRows(), m2.getNumColumns(), (long)outMap.sum()); } - + + @Override + public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) { + throw new NotImplementedException(); + } + @Override - public double estim(MatrixCharacteristics mc1, MatrixCharacteristics mc2) { - LOG.warn("Meta-data-only estimates not supported in EstimatorDensityMap, falling back to EstimatorBasicAvg."); - return new EstimatorBasicAvg().estim(mc1, mc2); + public double estim(MatrixBlock m, OpCode op) { + throw new NotImplementedException(); } private MatrixBlock computeDensityMap(MatrixBlock in) { http://git-wip-us.apache.org/repos/asf/systemml/blob/31610e36/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java index babffe8..dc79301 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java @@ -22,7 +22,6 @@ import org.apache.commons.lang.NotImplementedException; import org.apache.commons.math3.distribution.ExponentialDistribution; import org.apache.commons.math3.random.Well1024a; import org.apache.sysml.hops.OptimizerUtils; -import org.apache.sysml.runtime.matrix.MatrixCharacteristics; import org.apache.sysml.runtime.matrix.data.DenseBlock; import org.apache.sysml.runtime.matrix.data.MatrixBlock; import org.apache.sysml.runtime.matrix.data.SparseBlock; @@ -56,13 +55,18 @@ public class EstimatorLayeredGraph extends SparsityEstimator { public double estim(MMNode root) { throw new NotImplementedException(); } - + @Override - public double estim(MatrixCharacteristics mc1, MatrixCharacteristics mc2) { + public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) { throw new NotImplementedException(); } @Override + public double estim(MatrixBlock m, OpCode op) { + throw new NotImplementedException(); + } + + @Override public double estim(MatrixBlock m1, MatrixBlock m2){ LayeredGraph graph = new LayeredGraph(m1, m2, _rounds); return OptimizerUtils.getSparsity(m1.getNumRows(), http://git-wip-us.apache.org/repos/asf/systemml/blob/31610e36/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java ---------------------------------------------------------------------- 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 b2aad66..c7b7136 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java @@ -21,9 +21,10 @@ package org.apache.sysml.hops.estim; import java.util.Arrays; import java.util.Random; +import java.util.stream.IntStream; +import org.apache.directory.api.util.exception.NotImplementedException; import org.apache.sysml.hops.OptimizerUtils; -import org.apache.sysml.runtime.matrix.MatrixCharacteristics; import org.apache.sysml.runtime.matrix.data.DenseBlock; import org.apache.sysml.runtime.matrix.data.LibMatrixAgg; import org.apache.sysml.runtime.matrix.data.MatrixBlock; @@ -65,30 +66,74 @@ public class EstimatorMatrixHistogram extends SparsityEstimator new MatrixHistogram(root.getRight().getData(), _useExcepts); //estimate output sparsity based on input histograms - double ret = estimIntern(h1, h2); + double ret = estimIntern(h1, h2, OpCode.MM); //derive and memoize output histogram root.setSynopsis(MatrixHistogram.deriveOutputHistogram(h1, h2, ret)); return ret; } - - @Override + + @Override public double estim(MatrixBlock m1, MatrixBlock m2) { + return estim(m1, m2, OpCode.MM); + } + + @Override + public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) { MatrixHistogram h1 = new MatrixHistogram(m1, _useExcepts); MatrixHistogram h2 = (m1 == m2) ? //self product h1 : new MatrixHistogram(m2, _useExcepts); - return estimIntern(h1, h2); + return estimIntern(h1, h2, op); } - + @Override - public double estim(MatrixCharacteristics mc1, MatrixCharacteristics mc2) { - LOG.warn("Meta-data-only estimates not supported in " - + "EstimatorMatrixHistogram, falling back to EstimatorBasicAvg."); - return new EstimatorBasicAvg().estim(mc1, mc2); + public double estim(MatrixBlock m1, OpCode op) { + MatrixHistogram h1 = new MatrixHistogram(m1, _useExcepts); + return estimIntern(h1, null, op); } - private double estimIntern(MatrixHistogram h1, MatrixHistogram h2) { + private double estimIntern(MatrixHistogram h1, MatrixHistogram h2, OpCode op) { + double msize = h1.getRows()*h1.getCols(); + + switch (op) { + case MM: + return estimInternMM(h1, h2); + case MULT: + return Math.min( + IntStream.range(0, h1.getRows()).mapToDouble(i -> (double)h1.rNnz[i]/msize * (double)h2.rNnz[i]/msize).sum(), + IntStream.range(0, h1.getCols()).mapToDouble(i -> (double)h1.cNnz[i]/msize * (double)h2.cNnz[i]/msize).sum()); + case PLUS: + return Math.min( + IntStream.range(0, h1.getRows()).mapToDouble(i -> (double)h1.rNnz[i]/msize + + (double)h2.rNnz[i]/msize - (double)h1.rNnz[i]/msize * (double)h2.rNnz[i]/msize).sum(), + IntStream.range(0, h1.getCols()).mapToDouble(i -> (double)h1.cNnz[i]/msize + + (double)h2.cNnz[i]/msize - (double)h1.cNnz[i]/msize * (double)h2.cNnz[i]/msize).sum()); + case EQZERO: + return OptimizerUtils.getSparsity(h1.getRows(), h1.getCols(), + (long)h1.getRows() * h1.getCols() - h1.getNonZeros()); + case DIAG: + return (h1.getCols()==1) ? + OptimizerUtils.getSparsity(h1.getRows(), h1.getRows(), h1.getNonZeros()) : + OptimizerUtils.getSparsity(h1.getRows(), 1, Math.min(h1.getRows(), h1.getNonZeros())); + //binary operations that preserve sparsity exactly + case CBIND: + return OptimizerUtils.getSparsity(h1.getRows(), + h1.getCols()+h2.getCols(), h1.getNonZeros() + h2.getNonZeros()); + case RBIND: + return OptimizerUtils.getSparsity(h1.getRows()+h2.getRows(), + h1.getCols(), h1.getNonZeros() + h2.getNonZeros()); + //unary operation that preserve sparsity exactly + case NEQZERO: + case TRANS: + case RESHAPE: + return OptimizerUtils.getSparsity(h1.getRows(), h1.getCols(), h1.getNonZeros()); + default: + throw new NotImplementedException(); + } + } + + private double estimInternMM(MatrixHistogram h1, MatrixHistogram h2) { long nnz = 0; //special case, with exact sparsity estimate, where the dot product //dot(h1.cNnz,h2rNnz) gives the exact number of non-zeros in the output @@ -254,6 +299,12 @@ public class EstimatorMatrixHistogram extends SparsityEstimator return cNnz.length; } + public long getNonZeros() { + return getRows() < getCols() ? + IntStream.range(0, getRows()).mapToLong(i-> rNnz[i]).sum() : + IntStream.range(0, getRows()).mapToLong(i-> cNnz[i]).sum(); + } + public static MatrixHistogram deriveOutputHistogram(MatrixHistogram h1, MatrixHistogram h2, double spOut) { //exact propagation if lhs or rhs full diag if( h1.fullDiag ) return h2; http://git-wip-us.apache.org/repos/asf/systemml/blob/31610e36/src/main/java/org/apache/sysml/hops/estim/EstimatorSample.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorSample.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorSample.java index 6ed918a..ad2f6b7 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorSample.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorSample.java @@ -19,9 +19,9 @@ package org.apache.sysml.hops.estim; +import org.apache.commons.lang.NotImplementedException; import org.apache.sysml.hops.OptimizerUtils; import org.apache.sysml.runtime.DMLRuntimeException; -import org.apache.sysml.runtime.matrix.MatrixCharacteristics; import org.apache.sysml.runtime.matrix.data.DenseBlock; import org.apache.sysml.runtime.matrix.data.LibMatrixAgg; import org.apache.sysml.runtime.matrix.data.MatrixBlock; @@ -74,11 +74,15 @@ public class EstimatorSample extends SparsityEstimator return OptimizerUtils.getSparsity( m1.getNumRows(), m2.getNumColumns(), nnzOut); } - + + @Override + public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) { + throw new NotImplementedException(); + } + @Override - public double estim(MatrixCharacteristics mc1, MatrixCharacteristics mc2) { - LOG.warn("Meta-data-only estimates not supported by EstimatorSample, falling back to EstimatorBasicAvg."); - return new EstimatorBasicAvg().estim(mc1, mc2); + public double estim(MatrixBlock m, OpCode op) { + throw new NotImplementedException(); } private int[] computeColumnNnz(MatrixBlock in, int[] ix) { http://git-wip-us.apache.org/repos/asf/systemml/blob/31610e36/src/main/java/org/apache/sysml/hops/estim/SparsityEstimator.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/SparsityEstimator.java b/src/main/java/org/apache/sysml/hops/estim/SparsityEstimator.java index ddfed0e..61a7207 100644 --- a/src/main/java/org/apache/sysml/hops/estim/SparsityEstimator.java +++ b/src/main/java/org/apache/sysml/hops/estim/SparsityEstimator.java @@ -21,13 +21,19 @@ package org.apache.sysml.hops.estim; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; -import org.apache.sysml.runtime.matrix.MatrixCharacteristics; import org.apache.sysml.runtime.matrix.data.MatrixBlock; public abstract class SparsityEstimator { protected static final Log LOG = LogFactory.getLog(SparsityEstimator.class.getName()); + public static enum OpCode { + MM, + MULT, PLUS, EQZERO, NEQZERO, + CBIND, RBIND, + TRANS, DIAG, RESHAPE; + } + /** * Estimates the output sparsity of a DAG of matrix multiplications * for the given operator graph of a single root node. @@ -38,8 +44,7 @@ public abstract class SparsityEstimator public abstract double estim(MMNode root); /** - * Estimates the output sparsity of a single matrix multiplication - * for the two given matrices. + * Estimates the output sparsity for a single matrix multiplication. * * @param m1 left-hand-side operand * @param m2 right-hand-side operand @@ -48,13 +53,21 @@ public abstract class SparsityEstimator public abstract double estim(MatrixBlock m1, MatrixBlock m2); /** - * Estimates the output sparsity of a single matrix multiplication - * for the two given matrices represented by meta data only. + * Estimates the output sparsity for a given binary operation. * - * @param mc1 left-hand-side operand - * @param mc2 right-hand-side operand + * @param m1 left-hand-side operand + * @param m2 right-hand-side operand + * @param op operator code * @return sparsity */ - public abstract double estim(MatrixCharacteristics mc1, MatrixCharacteristics mc2); - + public abstract double estim(MatrixBlock m1, MatrixBlock m2, OpCode op); + + /** + * Estimates the output sparsity for a given unary operation. + * + * @param m1 left-hand-side operand + * @param op operator code + * @return sparsity + */ + public abstract double estim(MatrixBlock m, OpCode op); }
