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/08/10 06:32:10 UTC
systemml git commit: [SYSTEMML-2479] Extended bitset estimator for
rbind, various cleanups
Repository: systemml
Updated Branches:
refs/heads/master 04bc667f3 -> ff4dbb3ee
[SYSTEMML-2479] Extended bitset estimator for rbind, various cleanups
Closes #824.
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/ff4dbb3e
Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/ff4dbb3e
Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/ff4dbb3e
Branch: refs/heads/master
Commit: ff4dbb3ee893b2609fa8111717d71f1bbfd46fa2
Parents: 04bc667
Author: Johanna Sommer <jo...@mail-sommer.com>
Authored: Thu Aug 9 19:12:28 2018 -0700
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Thu Aug 9 23:29:03 2018 -0700
----------------------------------------------------------------------
.../sysml/hops/estim/EstimatorBasicAvg.java | 13 +---
.../sysml/hops/estim/EstimatorBasicWorst.java | 13 +---
.../sysml/hops/estim/EstimatorBitsetMM.java | 73 ++++++++++++++++----
.../sysml/hops/estim/EstimatorDensityMap.java | 3 +
.../sysml/hops/estim/EstimatorLayeredGraph.java | 2 +-
.../hops/estim/EstimatorMatrixHistogram.java | 6 +-
.../sysml/hops/estim/SparsityEstimator.java | 37 ++++++++++
7 files changed, 108 insertions(+), 39 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/systemml/blob/ff4dbb3e/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 6448f70..10ff0f7 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicAvg.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicAvg.java
@@ -70,24 +70,13 @@ public class EstimatorBasicAvg extends SparsityEstimator
OptimizerUtils.getNnz(mc1.getRows(), mc1.getCols(),
mc1.getSparsity() + mc2.getSparsity() - mc1.getSparsity() * mc2.getSparsity()));
case EQZERO:
- return new MatrixCharacteristics(mc1.getRows(), mc1.getCols(),
- (long) mc1.getRows() * mc1.getCols() - mc1.getNonZeros());
case DIAG:
- return (mc1.getCols() == 1) ?
- new MatrixCharacteristics(mc1.getRows(), mc1.getRows(), mc1.getNonZeros()) :
- new MatrixCharacteristics(mc1.getRows(), 1, Math.min(mc1.getRows(), mc1.getNonZeros()));
- // binary operations that preserve sparsity exactly
case CBIND:
- return new MatrixCharacteristics(mc1.getRows(),
- mc1.getCols() + mc2.getCols(), mc1.getNonZeros() + mc2.getNonZeros());
case RBIND:
- return new MatrixCharacteristics(mc1.getRows() + mc2.getRows(),
- mc1.getCols(), mc1.getNonZeros() + mc2.getNonZeros());
- // unary operation that preserve sparsity exactly
case NEQZERO:
case TRANS:
case RESHAPE:
- return mc1;
+ return estimExactMetaData(mc1, mc2, op);
default:
throw new NotImplementedException();
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/ff4dbb3e/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 e99b55d..81877dd 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicWorst.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorBasicWorst.java
@@ -74,24 +74,13 @@ public class EstimatorBasicWorst extends SparsityEstimator
OptimizerUtils.getNnz(mc1.getRows(), mc1.getCols(),
Math.min(mc1.getSparsity() + mc2.getSparsity(), 1)));
case EQZERO:
- return new MatrixCharacteristics(mc1.getRows(), mc1.getCols(),
- (long) mc1.getRows() * mc1.getCols() - mc1.getNonZeros());
case DIAG:
- return (mc1.getCols() == 1) ?
- new MatrixCharacteristics(mc1.getRows(), mc1.getRows(), mc1.getNonZeros()) :
- new MatrixCharacteristics(mc1.getRows(), 1, Math.min(mc1.getRows(), mc1.getNonZeros()));
- // binary operations that preserve sparsity exactly
case CBIND:
- return new MatrixCharacteristics(mc1.getRows(),
- mc1.getCols() + mc2.getCols(), mc1.getNonZeros() + mc2.getNonZeros());
case RBIND:
- return new MatrixCharacteristics(mc1.getRows() + mc2.getRows(),
- mc1.getCols(), mc1.getNonZeros() + mc2.getNonZeros());
- // unary operation that preserve sparsity exactly
case NEQZERO:
case TRANS:
case RESHAPE:
- return mc1;
+ return estimExactMetaData(mc1, mc2, op);
default:
throw new NotImplementedException();
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/ff4dbb3e/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 a898147..0bb4e5d 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java
@@ -23,6 +23,7 @@ import java.util.BitSet;
import java.util.stream.IntStream;
import org.apache.commons.lang.NotImplementedException;
+import org.apache.sysml.hops.HopsException;
import org.apache.sysml.hops.OptimizerUtils;
import org.apache.sysml.runtime.controlprogram.parfor.stat.InfrastructureAnalyzer;
import org.apache.sysml.runtime.matrix.MatrixCharacteristics;
@@ -41,7 +42,8 @@ import org.apache.sysml.runtime.matrix.data.SparseBlock;
* Multiplication for Irregular Data. In IPDPS, pages 370–381, 2014.
*
*/
-public class EstimatorBitsetMM extends SparsityEstimator {
+public class EstimatorBitsetMM extends SparsityEstimator
+{
@Override
public MatrixCharacteristics estim(MMNode root) {
// recursive density map computation of non-leaf nodes
@@ -53,32 +55,51 @@ public class EstimatorBitsetMM extends SparsityEstimator {
new BitsetMatrix1(root.getLeft().getData());
BitsetMatrix m2Map = !root.getRight().isLeaf() ? (BitsetMatrix) root.getRight().getSynopsis() :
new BitsetMatrix1(root.getRight().getData());
-
- // estimate output density map and sparsity via boolean matrix mult
- BitsetMatrix outMap = m1Map.matMult(m2Map);
- root.setSynopsis(outMap); // memoize boolean matrix
+ BitsetMatrix outMap = estimInternal(m1Map, m2Map, root.getOp());
+ root.setSynopsis(outMap); // memorize boolean matrix
return root.setMatrixCharacteristics(new MatrixCharacteristics(
outMap.getNumRows(), outMap.getNumColumns(), outMap.getNonZeros()));
}
@Override
public double estim(MatrixBlock m1, MatrixBlock m2) {
- BitsetMatrix m1Map = new BitsetMatrix1(m1);
- BitsetMatrix m2Map = (m1 == m2) ? //self product
- m1Map : new BitsetMatrix1(m2);
- BitsetMatrix outMap = m1Map.matMult(m2Map);
- return OptimizerUtils.getSparsity( // aggregate output histogram
- outMap.getNumRows(), outMap.getNumColumns(), outMap.getNonZeros());
+ return estim(m1, m2, OpCode.MM);
}
@Override
public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) {
- throw new NotImplementedException();
+ if( isExactMetadataOp(op) )
+ return estimExactMetaData(m1.getMatrixCharacteristics(),
+ m2.getMatrixCharacteristics(), op).getSparsity();
+ BitsetMatrix m1Map = new BitsetMatrix1(m1);
+ BitsetMatrix m2Map = (m1 == m2) ? //self product
+ m1Map : new BitsetMatrix1(m2);
+ BitsetMatrix outMap = estimInternal(m1Map, m2Map, op);
+ return OptimizerUtils.getSparsity(outMap.getNumRows(),
+ outMap.getNumColumns(), outMap.getNonZeros());
}
@Override
public double estim(MatrixBlock m, OpCode op) {
- throw new NotImplementedException();
+ return estim(m, null, op);
+ }
+
+ private BitsetMatrix estimInternal(BitsetMatrix m1Map, BitsetMatrix m2Map, OpCode op) {
+ switch(op) {
+ case MM: return m1Map.matMult(m2Map);
+ case RBIND: return m1Map.rbind(m2Map);
+ //TODO implement all as bitset operations in both BitsetMatrix1 and BitsetMatrix2
+ case MULT:
+ case PLUS:
+ case CBIND:
+ case TRANS:
+ case NEQZERO:
+ case EQZERO:
+ case DIAG:
+ case RESHAPE:
+ default:
+ throw new NotImplementedException();
+ }
}
private abstract static class BitsetMatrix {
@@ -143,6 +164,8 @@ public class EstimatorBitsetMM extends SparsityEstimator {
protected abstract void buildIntern(MatrixBlock in, int rl, int ru);
protected abstract long matMultIntern(BitsetMatrix bsb, BitsetMatrix bsc, int rl, int ru);
+
+ protected abstract BitsetMatrix rbind(BitsetMatrix bsb);
}
/**
@@ -240,6 +263,18 @@ public class EstimatorBitsetMM extends SparsityEstimator {
return lnnz;
}
+ @Override
+ public BitsetMatrix rbind(BitsetMatrix bsb) {
+ if( !(bsb instanceof BitsetMatrix1) )
+ throw new HopsException("Incompatible bitset types: "
+ + getClass().getSimpleName()+" and "+bsb.getClass().getSimpleName());
+ BitsetMatrix1 b = (BitsetMatrix1) bsb;
+ BitsetMatrix1 ret = new BitsetMatrix1(getNumRows()+bsb.getNumRows(), getNumColumns());
+ System.arraycopy(_data, 0, ret._data, 0, _rlen*_rowLen);
+ System.arraycopy(b._data, 0, ret._data, _rlen*_rowLen, b._rlen*_rowLen);
+ return ret;
+ }
+
private void set(int r, int c) {
int off = r * _rowLen;
int wordIndex = wordIndex(c); //see BitSet.java
@@ -354,5 +389,17 @@ public class EstimatorBitsetMM extends SparsityEstimator {
}
return lnnz;
}
+
+ @Override
+ public BitsetMatrix rbind(BitsetMatrix bsb) {
+ if( !(bsb instanceof BitsetMatrix2) )
+ throw new HopsException("Incompatible bitset types: "
+ + getClass().getSimpleName()+" and "+bsb.getClass().getSimpleName());
+ BitsetMatrix2 b = (BitsetMatrix2) bsb;
+ BitsetMatrix2 ret = new BitsetMatrix2(getNumRows()+bsb.getNumRows(), getNumColumns());
+ System.arraycopy(_data, 0, ret._data, 0, _rlen); //shallow copy
+ System.arraycopy(b._data, 0, ret._data, _rlen, b._rlen); //shallow copy
+ return ret;
+ }
}
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/ff4dbb3e/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 66c5826..b6fca0f 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java
@@ -80,6 +80,9 @@ public class EstimatorDensityMap extends SparsityEstimator
@Override
public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) {
+ if( isExactMetadataOp(op) )
+ return estimExactMetaData(m1.getMatrixCharacteristics(),
+ m2.getMatrixCharacteristics(), op).getSparsity();
DensityMap m1Map = new DensityMap(m1, _b);
DensityMap m2Map = (m1 == m2) ? //self product
m1Map : new DensityMap(m2, _b);
http://git-wip-us.apache.org/repos/asf/systemml/blob/ff4dbb3e/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 e24886a..d103359 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java
@@ -68,7 +68,7 @@ public class EstimatorLayeredGraph extends SparsityEstimator {
}
@Override
- public double estim(MatrixBlock m1, MatrixBlock m2){
+ public double estim(MatrixBlock m1, MatrixBlock m2) {
LayeredGraph graph = new LayeredGraph(m1, m2, _rounds);
return OptimizerUtils.getSparsity(m1.getNumRows(),
m2.getNumColumns(), graph.estimateNnz());
http://git-wip-us.apache.org/repos/asf/systemml/blob/ff4dbb3e/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 a299c45..26b3df0 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java
@@ -68,7 +68,6 @@ public class EstimatorMatrixHistogram extends SparsityEstimator
//estimate output sparsity based on input histograms
double ret = estimIntern(h1, h2, root.getOp());
-
MatrixHistogram outMap = MatrixHistogram.deriveOutputHistogram(h1, h2, ret, root.getOp());
root.setSynopsis(outMap);
return root.setMatrixCharacteristics(new MatrixCharacteristics(
@@ -83,6 +82,9 @@ public class EstimatorMatrixHistogram extends SparsityEstimator
@Override
public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) {
+ if( isExactMetadataOp(op) )
+ return estimExactMetaData(m1.getMatrixCharacteristics(),
+ m2.getMatrixCharacteristics(), op).getSparsity();
MatrixHistogram h1 = new MatrixHistogram(m1, _useExcepts);
MatrixHistogram h2 = (m1 == m2) ? //self product
h1 : new MatrixHistogram(m2, _useExcepts);
@@ -91,6 +93,8 @@ public class EstimatorMatrixHistogram extends SparsityEstimator
@Override
public double estim(MatrixBlock m1, OpCode op) {
+ if( isExactMetadataOp(op) )
+ return estimExactMetaData(m1.getMatrixCharacteristics(), null, op).getSparsity();
MatrixHistogram h1 = new MatrixHistogram(m1, _useExcepts);
return estimIntern(h1, null, op);
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/ff4dbb3e/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 a37372f..2941959 100644
--- a/src/main/java/org/apache/sysml/hops/estim/SparsityEstimator.java
+++ b/src/main/java/org/apache/sysml/hops/estim/SparsityEstimator.java
@@ -19,8 +19,10 @@
package org.apache.sysml.hops.estim;
+import org.apache.commons.lang.ArrayUtils;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
+import org.apache.sysml.hops.HopsException;
import org.apache.sysml.runtime.matrix.MatrixCharacteristics;
import org.apache.sysml.runtime.matrix.data.MatrixBlock;
@@ -33,6 +35,11 @@ public abstract class SparsityEstimator
public static boolean MULTI_THREADED_ESTIM = false;
public static final int MIN_PAR_THRESHOLD = 10 * 1024;
+ private static OpCode[] EXACT_META_DATA_OPS = new OpCode[] {
+ OpCode.EQZERO, OpCode.NEQZERO, OpCode.CBIND,
+ OpCode.RBIND, OpCode.TRANS, OpCode.DIAG, OpCode.RESHAPE
+ };
+
public static enum OpCode {
MM,
MULT, PLUS, EQZERO, NEQZERO,
@@ -77,4 +84,34 @@ public abstract class SparsityEstimator
* @return sparsity
*/
public abstract double estim(MatrixBlock m, OpCode op);
+
+ protected boolean isExactMetadataOp(OpCode op) {
+ return ArrayUtils.contains(EXACT_META_DATA_OPS, op);
+ }
+
+ protected MatrixCharacteristics estimExactMetaData(MatrixCharacteristics mc1, MatrixCharacteristics mc2, OpCode op) {
+ switch( op ) {
+ case EQZERO:
+ return new MatrixCharacteristics(mc1.getRows(), mc1.getCols(),
+ (long) mc1.getRows() * mc1.getCols() - mc1.getNonZeros());
+ case DIAG:
+ return (mc1.getCols() == 1) ?
+ new MatrixCharacteristics(mc1.getRows(), mc1.getRows(), mc1.getNonZeros()) :
+ new MatrixCharacteristics(mc1.getRows(), 1, Math.min(mc1.getRows(), mc1.getNonZeros()));
+ // binary operations that preserve sparsity exactly
+ case CBIND:
+ return new MatrixCharacteristics(mc1.getRows(),
+ mc1.getCols() + mc2.getCols(), mc1.getNonZeros() + mc2.getNonZeros());
+ case RBIND:
+ return new MatrixCharacteristics(mc1.getRows() + mc2.getRows(),
+ mc1.getCols(), mc1.getNonZeros() + mc2.getNonZeros());
+ // unary operation that preserve sparsity exactly
+ case NEQZERO:
+ case TRANS:
+ case RESHAPE:
+ return mc1;
+ default:
+ throw new HopsException("Opcode is not an exact meta data operation: "+op.name());
+ }
+ }
}