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/08 05:23:48 UTC
systemml git commit: [SYSTEMML-2479] Rework DensityMap sparsity
estimator and mult/plus ops
Repository: systemml
Updated Branches:
refs/heads/master 1d13c8bbc -> f35cb6005
[SYSTEMML-2479] Rework DensityMap sparsity estimator and mult/plus ops
Closes #821.
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/f35cb600
Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/f35cb600
Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/f35cb600
Branch: refs/heads/master
Commit: f35cb6005b81d0360defd30fe154afbe2190b734
Parents: 1d13c8b
Author: Johanna Sommer <jo...@mail-sommer.com>
Authored: Tue Aug 7 22:24:59 2018 -0700
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Tue Aug 7 22:25:00 2018 -0700
----------------------------------------------------------------------
.../sysml/hops/estim/EstimatorDensityMap.java | 299 +++++++++++++------
1 file changed, 207 insertions(+), 92 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/systemml/blob/f35cb600/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 1246978..d752fe7 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java
@@ -59,93 +59,38 @@ public class EstimatorDensityMap extends SparsityEstimator
estim(root.getLeft()); //obtain synopsis
if( !root.getRight().isLeaf() )
estim(root.getLeft()); //obtain synopsis
- MatrixBlock m1Map = !root.getLeft().isLeaf() ?
- (MatrixBlock)root.getLeft().getSynopsis() : computeDensityMap(root.getLeft().getData());
- MatrixBlock m2Map = !root.getRight().isLeaf() ?
- (MatrixBlock)root.getRight().getSynopsis() : computeDensityMap(root.getRight().getData());
+ DensityMap m1Map = !root.getLeft().isLeaf() ?
+ (DensityMap)root.getLeft().getSynopsis() :
+ new DensityMap(root.getLeft().getData(), _b);
+ DensityMap m2Map = !root.getRight().isLeaf() ?
+ (DensityMap)root.getRight().getSynopsis() :
+ new DensityMap(root.getRight().getData(), _b);
//estimate output density map and sparsity
- MatrixBlock outMap = estimIntern(m1Map, m2Map,
- false, root.getRows(), root.getLeft().getCols(), root.getCols());
+ DensityMap outMap = estimIntern(m1Map, m2Map, root.getOp());
root.setSynopsis(outMap); //memoize density map
return root.setMatrixCharacteristics(new MatrixCharacteristics(
- root.getLeft().getRows(), root.getRight().getCols(), (long)outMap.sum()));
+ root.getLeft().getRows(), root.getRight().getCols(), outMap.getNonZeros()));
}
@Override
public double estim(MatrixBlock m1, MatrixBlock m2) {
- MatrixBlock m1Map = computeDensityMap(m1);
- MatrixBlock m2Map = (m1 == m2) ? //self product
- m1Map : computeDensityMap(m2);
- MatrixBlock outMap = estimIntern(m1Map, m2Map,
- true, m1.getNumRows(), m1.getNumColumns(), m2.getNumColumns());
- return OptimizerUtils.getSparsity( //aggregate output histogram
- m1.getNumRows(), m2.getNumColumns(), (long)outMap.sum());
+ return estim(m1, m2, OpCode.MM);
}
@Override
public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) {
- throw new NotImplementedException();
+ DensityMap m1Map = new DensityMap(m1, _b);
+ DensityMap m2Map = (m1 == m2) ? //self product
+ m1Map : new DensityMap(m2, _b);
+ DensityMap outMap = estimIntern(m1Map, m2Map, OpCode.MM);
+ return OptimizerUtils.getSparsity( //aggregate output histogram
+ outMap.getNumRowsOrig(), outMap.getNumColumnsOrig(), outMap.getNonZeros());
}
@Override
public double estim(MatrixBlock m, OpCode op) {
- throw new NotImplementedException();
- }
-
- private MatrixBlock computeDensityMap(MatrixBlock in) {
- int rlen = (int)Math.ceil((double)in.getNumRows()/_b);
- int clen = (int)Math.ceil((double)in.getNumColumns()/_b);
- MatrixBlock out = new MatrixBlock(rlen, clen, false);
-
- //fast-path empty input
- if( in.isEmptyBlock(false) )
- return out;
-
- //allocate dense output block
- DenseBlock c = out.allocateBlock().getDenseBlock();
-
- //fast-path fully dense input
- if( in.getLength() == in.getNonZeros() ) {
- c.set(1); //set sparsity 1.0 into all cells
- out.setNonZeros(in.getLength());
- return out;
- }
-
- //compute nnz histogram
- if( in.isInSparseFormat() ) {
- SparseBlock sblock = in.getSparseBlock();
- for(int i=0; i<in.getNumRows(); i++) {
- if( sblock.isEmpty(i) ) continue;
- int alen = sblock.size(i);
- int apos = sblock.pos(i);
- int[] aix = sblock.indexes(i);
- for(int k=apos; k<apos+alen; k++)
- c.incr(i/_b, aix[k]/_b);
- }
- }
- else {
- for(int i=0; i<in.getNumRows(); i++) {
- for(int j=0; j<in.getNumColumns(); j++) {
- double aval = in.quickGetValue(i, j);
- if( aval != 0 )
- c.incr(i/_b, j/_b);
- }
- }
- }
-
- //scale histogram by block size, w/ awareness of boundary blocks
- for(int i=0; i<rlen; i++){
- int lrlen = UtilFunctions.computeBlockSize(in.getNumRows(), i+1, _b);
- for(int j=0; j<clen; j++) {
- double cval = c.get(i, j);
- if( cval == 0 ) continue;
- int lclen = UtilFunctions.computeBlockSize(in.getNumColumns(), j+1, _b);
- c.set(i, j, cval/lrlen/lclen);
- }
- }
- out.recomputeNonZeros();
- return out;
+ return estim(m, null, op);
}
/**
@@ -153,29 +98,42 @@ public class EstimatorDensityMap extends SparsityEstimator
*
* @param m1Map density map left-hand-side operand
* @param m2Map density map right-hand-side operand
- * @param retNnz return number of non-zeros instead of sparsity per cell
- * @param mOrig number of rows of output matrix, required for returning nnz
- * @param cdOrig common dimension of original matrix multiply
- * @param nOrig number of columns of output matrix, required for returning nnz
* @return density map
*/
- private MatrixBlock estimIntern(MatrixBlock m1Map, MatrixBlock m2Map, boolean retNnz, int mOrig, int cdOrig, int nOrig) {
+ private DensityMap estimIntern(DensityMap m1Map, DensityMap m2Map, OpCode op) {
+ switch(op) {
+ case MM: return estimInternMM(m1Map, m2Map);
+ case MULT: return estimInternMult(m1Map, m2Map);
+ case PLUS: return estimInternPlus(m1Map, m2Map);
+
+ case RBIND:
+ case CBIND:
+ //TODO simple append not possible due to partial blocks at end of m1Map
+
+ case TRANS:
+ case DIAG:
+ case RESHAPE:
+ //TODO add missing estimators
+ default:
+ throw new NotImplementedException();
+ }
+ }
+
+ private DensityMap estimInternMM(DensityMap m1Map, DensityMap m2Map) {
final int m = m1Map.getNumRows();
final int cd = m1Map.getNumColumns();
final int n = m2Map.getNumColumns();
- MatrixBlock out = new MatrixBlock(m, n, false);
- if( m1Map.isEmptyBlock(false) || m2Map.isEmptyBlock(false) )
- return out;
-
- //compute output density map with IKJ schedule
+ MatrixBlock out = new MatrixBlock(m1Map.getNumRows(), m2Map.getNumColumns(), false);
DenseBlock c = out.allocateBlock().getDenseBlock();
+ m1Map.toSparsity();
+ m2Map.toSparsity();
for(int i=0; i<m; i++) {
for(int k=0; k<cd; k++) {
- int lbk = UtilFunctions.computeBlockSize(cdOrig, k+1, _b);
- double sp1 = m1Map.quickGetValue(i, k);
+ int lbk = m1Map.getColBlockize(k);
+ double sp1 = m1Map.get(i, k);
if( sp1 == 0 ) continue;
for(int j=0; j<n; j++) {
- double sp2 = m2Map.quickGetValue(k, j);
+ double sp2 = m2Map.get(k, j);
if( sp2 == 0 ) continue;
//custom multiply for scalar sparsity
double tmp1 = 1 - Math.pow(1-sp1*sp2, lbk);
@@ -184,16 +142,173 @@ public class EstimatorDensityMap extends SparsityEstimator
c.set(i, j, tmp1+tmp2 - tmp1*tmp2);
}
}
- //scale to non-zeros instead of sparsity if needed
- if( retNnz ) {
- int lbm = UtilFunctions.computeBlockSize(mOrig, i+1, _b);
- for( int j=0; j<n; j++ ) {
- int lbn = UtilFunctions.computeBlockSize(nOrig, j+1, _b);
- c.set(i, j, c.get(i, j) * lbm * lbn);
+ }
+ out.recomputeNonZeros();
+ return new DensityMap(out, m1Map.getNumRowsOrig(),
+ m2Map.getNumColumnsOrig(), _b, true);
+ }
+
+ private DensityMap estimInternMult(DensityMap m1Map, DensityMap m2Map) {
+ MatrixBlock out = new MatrixBlock(m1Map.getNumRows(), m1Map.getNumColumns(), false);
+ DenseBlock c = out.allocateBlock().getDenseBlock();
+ m1Map.toSparsity();
+ m2Map.toSparsity();
+ for(int i=0; i<m1Map.getNumRows(); i++)
+ for(int j=0; j<m1Map.getNumColumns(); j++)
+ c.set(i, j, m1Map.get(i, j) * m2Map.get(i, j));
+ out.recomputeNonZeros();
+ return new DensityMap(out, m1Map.getNumRowsOrig(),
+ m1Map.getNumColumnsOrig(), _b, true);
+ }
+
+ private DensityMap estimInternPlus(DensityMap m1Map, DensityMap m2Map) {
+ MatrixBlock out = new MatrixBlock(m1Map.getNumRows(), m1Map.getNumColumns(), false);
+ DenseBlock c = out.allocateBlock().getDenseBlock();
+ m1Map.toSparsity();
+ m2Map.toSparsity();
+ for(int i=0; i<m1Map.getNumRows(); i++)
+ for(int j=0; j<m1Map.getNumColumns(); j++) {
+ double sp1 = m1Map.get(i, j);
+ double sp2 = m2Map.get(i, j);
+ c.set(i, j, sp1 + sp2 - sp1 * sp2);
+ }
+ out.recomputeNonZeros();
+ return new DensityMap(out, m1Map.getNumRowsOrig(),
+ m1Map.getNumColumnsOrig(), _b, true);
+ }
+
+ private static class DensityMap {
+ private final MatrixBlock _map;
+ private final int _rlen;
+ private final int _clen;
+ private final int _b;
+ private boolean _scaled; //false->nnz, true->sp
+
+ public DensityMap(MatrixBlock in, int b) {
+ _rlen = in.getNumRows();
+ _clen = in.getNumColumns();
+ _b = b;
+ _map = init(in);
+ _scaled = false;
+ }
+
+ public DensityMap(MatrixBlock map, int rlenOrig, int clenOrig, int b, boolean scaled) {
+ _rlen = rlenOrig;
+ _clen = clenOrig;
+ _b = b;
+ _map = map;
+ _scaled = scaled;
+ }
+
+ public int getNumRows() {
+ return _map.getNumRows();
+ }
+
+ public int getNumColumns() {
+ return _map.getNumColumns();
+ }
+
+ public int getNumRowsOrig() {
+ return _rlen;
+ }
+
+ public int getNumColumnsOrig() {
+ return _clen;
+ }
+
+ public long getNonZeros() {
+ if( _scaled ) toNnz();
+ return (long)Math.round(_map.sum());
+ }
+
+ public int getRowBlockize(int r) {
+ return UtilFunctions.computeBlockSize(_rlen, r+1, _b);
+ }
+
+ public int getColBlockize(int c) {
+ return UtilFunctions.computeBlockSize(_clen, c+1, _b);
+ }
+
+ public double get(int r, int c) {
+ return _map.quickGetValue(r, c);
+ }
+
+ public void toSparsity() {
+ if( _scaled ) return;
+ //scale histogram by block size, w/ awareness of boundary blocks
+ int rlen = _map.getNumRows();
+ int clen = _map.getNumColumns();
+ DenseBlock c = _map.getDenseBlock();
+ for(int i=0; i<rlen; i++){
+ int lrlen = getRowBlockize(i);
+ for(int j=0; j<clen; j++) {
+ double cval = c.get(i, j);
+ if( cval == 0 ) continue;
+ c.set(i, j, cval/lrlen/getColBlockize(j));
}
}
+ _scaled = true;
+ }
+
+ public void toNnz() {
+ if( !_scaled ) return;
+ //scale histogram by block size, w/ awareness of boundary blocks
+ int rlen = _map.getNumRows();
+ int clen = _map.getNumColumns();
+ DenseBlock c = _map.getDenseBlock();
+ for(int i=0; i<rlen; i++){
+ int lrlen = getRowBlockize(i);
+ for(int j=0; j<clen; j++) {
+ double cval = c.get(i, j);
+ if( cval == 0 ) continue;
+ c.set(i, j, cval * lrlen * getColBlockize(j));
+ }
+ }
+ _scaled = false;
+ }
+
+ private MatrixBlock init(MatrixBlock in) {
+ int rlen = (int)Math.ceil((double)_rlen/_b);
+ int clen = (int)Math.ceil((double)_clen/_b);
+ MatrixBlock out = new MatrixBlock(rlen, clen, false);
+
+ //fast-path empty input
+ if( in.isEmptyBlock(false) )
+ return out;
+
+ //allocate dense output block
+ DenseBlock c = out.allocateBlock().getDenseBlock();
+
+ //fast-path fully dense input
+ if( in.getLength() == in.getNonZeros() ) {
+ c.set(1); //set sparsity 1.0 into all cells
+ out.setNonZeros(in.getLength());
+ return out;
+ }
+
+ //compute nnz histogram
+ if( in.isInSparseFormat() ) {
+ SparseBlock sblock = in.getSparseBlock();
+ for(int i=0; i<in.getNumRows(); i++) {
+ if( sblock.isEmpty(i) ) continue;
+ int alen = sblock.size(i);
+ int apos = sblock.pos(i);
+ int[] aix = sblock.indexes(i);
+ for(int k=apos; k<apos+alen; k++)
+ c.incr(i/_b, aix[k]/_b);
+ }
+ }
+ else {
+ for(int i=0; i<_rlen; i++) {
+ for(int j=0; j<_clen; j++) {
+ double aval = in.quickGetValue(i, j);
+ if( aval != 0 )
+ c.incr(i/_b, j/_b);
+ }
+ }
+ }
+ out.recomputeNonZeros();
+ return out;
}
- out.recomputeNonZeros();
- return out;
}
}