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 17:23:29 UTC
[1/2] systemml git commit: [SYSTEMML-2468] Improved MNC estimator
(avoid final sketch propagation)
Repository: systemml
Updated Branches:
refs/heads/master cca6356f8 -> 0a957e4c9
[SYSTEMML-2468] Improved MNC estimator (avoid final sketch propagation)
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/569806dc
Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/569806dc
Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/569806dc
Branch: refs/heads/master
Commit: 569806dcdf3c37bff59ad052884cf5f9af9bd598
Parents: cca6356
Author: Matthias Boehm <mb...@gmail.com>
Authored: Sun Oct 21 18:43:32 2018 +0200
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Sun Oct 21 18:43:32 2018 +0200
----------------------------------------------------------------------
.../hops/estim/EstimatorMatrixHistogram.java | 61 +++++++++++++++++---
1 file changed, 52 insertions(+), 9 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/systemml/blob/569806dc/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 83d918a..34f9cac 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java
@@ -55,11 +55,15 @@ public class EstimatorMatrixHistogram extends SparsityEstimator
@Override
public MatrixCharacteristics estim(MMNode root) {
+ return estim(root, true);
+ }
+
+ private MatrixCharacteristics estim(MMNode root, boolean topLevel) {
//recursive histogram computation of non-leaf nodes
if( !root.getLeft().isLeaf() )
- estim(root.getLeft()); //obtain synopsis
+ estim(root.getLeft(), false); //obtain synopsis
if( root.getRight()!=null && !root.getRight().isLeaf() )
- estim(root.getRight()); //obtain synopsis
+ estim(root.getRight(), false); //obtain synopsis
MatrixHistogram h1 = !root.getLeft().isLeaf() ?
(MatrixHistogram)root.getLeft().getSynopsis() :
new MatrixHistogram(root.getLeft().getData(), _useExcepts);
@@ -69,6 +73,12 @@ public class EstimatorMatrixHistogram extends SparsityEstimator
//estimate output sparsity based on input histograms
double ret = estimIntern(h1, h2, root.getOp(), root.getMisc());
+ if( topLevel ) { //fast-path final result
+ return MatrixHistogram.deriveOutputCharacteristics(
+ h1, h2, ret, root.getOp(), root.getMisc());
+ }
+
+ //sketch propagation for intermediates other than final result
MatrixHistogram outMap = MatrixHistogram
.deriveOutputHistogram(h1, h2, ret, root.getOp(), root.getMisc());
root.setSynopsis(outMap);
@@ -183,13 +193,15 @@ public class EstimatorMatrixHistogram extends SparsityEstimator
nnz = (long)(spOut * mnOut);
}
- //exploit upper bound on nnz based on non-empty rows/cols
- nnz = (h1.rNonEmpty >= 0 && h2.cNonEmpty >= 0) ?
- Math.min((long)h1.rNonEmpty * h2.cNonEmpty, nnz) : nnz;
-
- //exploit lower bound on nnz based on half-full rows/cols
- nnz = (h1.rNdiv2 >= 0 && h2.cNdiv2 >= 0) ?
- Math.max((long)h1.rNdiv2 * h2.cNdiv2, nnz) : nnz;
+ if( _useExcepts ) {
+ //exploit upper bound on nnz based on non-empty rows/cols
+ nnz = (h1.rNonEmpty >= 0 && h2.cNonEmpty >= 0) ?
+ Math.min((long)h1.rNonEmpty * h2.cNonEmpty, nnz) : nnz;
+
+ //exploit lower bound on nnz based on half-full rows/cols
+ nnz = (h1.rNdiv2 >= 0 && h2.cNdiv2 >= 0) ?
+ Math.max((long)h1.rNdiv2 * h2.cNdiv2, nnz) : nnz;
+ }
//compute final sparsity
return OptimizerUtils.getSparsity(
@@ -343,6 +355,37 @@ public class EstimatorMatrixHistogram extends SparsityEstimator
}
}
+ public static MatrixCharacteristics deriveOutputCharacteristics(MatrixHistogram h1, MatrixHistogram h2, double spOut, OpCode op, long[] misc) {
+ switch(op) {
+ case MM:
+ return new MatrixCharacteristics(h1.getRows(), h2.getCols(),
+ OptimizerUtils.getNnz(h1.getRows(), h2.getCols(), spOut));
+ case MULT:
+ case PLUS:
+ case NEQZERO:
+ case EQZERO:
+ return new MatrixCharacteristics(h1.getRows(), h1.getCols(),
+ OptimizerUtils.getNnz(h1.getRows(), h1.getCols(), spOut));
+ case RBIND:
+ return new MatrixCharacteristics(h1.getRows()+h1.getRows(), h1.getCols(),
+ OptimizerUtils.getNnz(h1.getRows()+h2.getRows(), h1.getCols(), spOut));
+ case CBIND:
+ return new MatrixCharacteristics(h1.getRows(), h1.getCols()+h2.getCols(),
+ OptimizerUtils.getNnz(h1.getRows(), h1.getCols()+h2.getCols(), spOut));
+ case DIAG:
+ int ncol = h1.getCols()==1 ? h1.getRows() : 1;
+ return new MatrixCharacteristics(h1.getRows(), ncol,
+ OptimizerUtils.getNnz(h1.getRows(), ncol, spOut));
+ case TRANS:
+ return new MatrixCharacteristics(h1.getCols(), h1.getRows(), h1.getNonZeros());
+ case RESHAPE:
+ return new MatrixCharacteristics((int)misc[0], (int)misc[1],
+ OptimizerUtils.getNnz((int)misc[0], (int)misc[1], spOut));
+ default:
+ throw new NotImplementedException();
+ }
+ }
+
private static MatrixHistogram deriveMMHistogram(MatrixHistogram h1, MatrixHistogram h2, double spOut) {
//exact propagation if lhs or rhs full diag
if( h1.fullDiag ) return h2;
[2/2] systemml git commit: [SYSTEMML-2479] Extended density map
estimator (additional operations)
Posted by mb...@apache.org.
[SYSTEMML-2479] Extended density map estimator (additional operations)
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/0a957e4c
Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/0a957e4c
Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/0a957e4c
Branch: refs/heads/master
Commit: 0a957e4c9a6aca0ef1cbf41e7dcdbdbc90ba4a04
Parents: 569806d
Author: Matthias Boehm <mb...@gmail.com>
Authored: Sun Oct 21 19:23:08 2018 +0200
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Sun Oct 21 19:23:08 2018 +0200
----------------------------------------------------------------------
.../sysml/hops/estim/EstimatorDensityMap.java | 60 +++++--
.../functions/estim/OpSingleTest.java | 159 +++----------------
2 files changed, 69 insertions(+), 150 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/systemml/blob/0a957e4c/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 144f7a7..e845a5b 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java
@@ -23,6 +23,7 @@ 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.LibMatrixReorg;
import org.apache.sysml.runtime.matrix.data.MatrixBlock;
import org.apache.sysml.runtime.matrix.data.SparseBlock;
import org.apache.sysml.runtime.util.UtilFunctions;
@@ -81,10 +82,10 @@ 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();
+ return estimExactMetaData(m1.getMatrixCharacteristics(), m2 != null ?
+ m2.getMatrixCharacteristics() : null, op).getSparsity();
DensityMap m1Map = new DensityMap(m1, _b);
- DensityMap m2Map = (m1 == m2) ? //self product
+ DensityMap m2Map = (m1 == m2 || m2 == null) ? //self product
m1Map : new DensityMap(m2, _b);
DensityMap outMap = estimIntern(m1Map, m2Map, op);
return OptimizerUtils.getSparsity( //aggregate output histogram
@@ -105,18 +106,19 @@ public class EstimatorDensityMap extends SparsityEstimator
*/
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 MM: return estimInternMM(m1Map, m2Map);
+ case MULT: return estimInternMult(m1Map, m2Map);
+ case PLUS: return estimInternPlus(m1Map, m2Map);
+ case NEQZERO: return m1Map;
+ case EQZERO: return estimInternEqZero(m1Map);
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
+ case TRANS: return estimInternTrans(m1Map);
+ case DIAG: return estimInternDiag(m1Map);
+ case RESHAPE: return estimInternReshape(m1Map);
default:
throw new NotImplementedException();
}
@@ -180,6 +182,40 @@ public class EstimatorDensityMap extends SparsityEstimator
m1Map.getNumColumnsOrig(), _b, true);
}
+ private DensityMap estimInternTrans(DensityMap m1Map) {
+ MatrixBlock out = LibMatrixReorg.transpose(m1Map.getMap(),
+ new MatrixBlock(m1Map.getNumColumns(), m1Map.getNumRows(), false));
+ return new DensityMap(out, m1Map.getNumColumnsOrig(),
+ m1Map.getNumRowsOrig(), _b, m1Map._scaled);
+ }
+
+ private DensityMap estimInternDiag(DensityMap m1Map) {
+ if( m1Map.getNumColumnsOrig() > 1 )
+ throw new NotImplementedException();
+ m1Map.toNnz();
+ MatrixBlock out = LibMatrixReorg.diag(m1Map.getMap(),
+ new MatrixBlock(m1Map.getNumRows(), m1Map.getNumRows(), false));
+ return new DensityMap(out, m1Map.getNumRowsOrig(),
+ m1Map.getNumRowsOrig(), _b, m1Map._scaled);
+ }
+
+ private DensityMap estimInternReshape(DensityMap m1Map) {
+ MatrixBlock out = new MatrixBlock(1,1,(double)m1Map.getNonZeros());
+ int b = Math.max(m1Map.getNumRowsOrig(), m1Map.getNumColumnsOrig());
+ return new DensityMap(out, m1Map.getNumRowsOrig(),
+ m1Map.getNumColumnsOrig(), b, false);
+ }
+
+ private DensityMap estimInternEqZero(DensityMap m1Map) {
+ MatrixBlock out = new MatrixBlock(m1Map.getNumRows(), m1Map.getNumColumns(), false);
+ m1Map.toSparsity();
+ for(int i=0; i<m1Map.getNumRows(); i++)
+ for(int j=0; j<m1Map.getNumColumns(); j++)
+ out.quickSetValue(i, j, 1-m1Map.get(i, j));
+ return new DensityMap(out, m1Map.getNumRowsOrig(),
+ m1Map.getNumColumnsOrig(), _b, m1Map._scaled);
+ }
+
public static class DensityMap {
private final MatrixBlock _map;
private final int _rlen;
@@ -207,6 +243,10 @@ public class EstimatorDensityMap extends SparsityEstimator
throw new RuntimeException("Invalid block size: "+_b);
}
+ public MatrixBlock getMap() {
+ return _map;
+ }
+
public int getNumRows() {
return _map.getNumRows();
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/0a957e4c/src/test/java/org/apache/sysml/test/integration/functions/estim/OpSingleTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/sysml/test/integration/functions/estim/OpSingleTest.java b/src/test/java/org/apache/sysml/test/integration/functions/estim/OpSingleTest.java
index fa567ed..72fccce 100644
--- a/src/test/java/org/apache/sysml/test/integration/functions/estim/OpSingleTest.java
+++ b/src/test/java/org/apache/sysml/test/integration/functions/estim/OpSingleTest.java
@@ -24,6 +24,7 @@ import org.apache.directory.api.util.exception.NotImplementedException;
import org.apache.sysml.hops.estim.EstimatorBasicAvg;
import org.apache.sysml.hops.estim.EstimatorBasicWorst;
import org.apache.sysml.hops.estim.EstimatorBitsetMM;
+import org.apache.sysml.hops.estim.EstimatorDensityMap;
import org.apache.sysml.hops.estim.SparsityEstimator;
import org.apache.sysml.hops.estim.SparsityEstimator.OpCode;
import org.apache.sysml.runtime.matrix.data.MatrixBlock;
@@ -49,17 +50,6 @@ public class OpSingleTest extends AutomatedTestBase
//do nothing
}
- //Average Case
-// @Test
-// public void testAvgEqzero() {
-// runSparsityEstimateTest(new EstimatorBasicAvg(), m, k, sparsity, eqzero);
-// }
-
-// @Test
-// public void testAvgDiag() {
-// runSparsityEstimateTest(new EstimatorBasicAvg(), m, k, sparsity, diag);
-// }
-
@Test
public void testAvgNeqzero() {
runSparsityEstimateTest(new EstimatorBasicAvg(), m, k, sparsity, neqzero);
@@ -74,95 +64,36 @@ public class OpSingleTest extends AutomatedTestBase
public void testAvgReshape() {
runSparsityEstimateTest(new EstimatorBasicAvg(), m, k, sparsity, reshape);
}
-
- //Worst Case
-// @Test
-// public void testWorstEqzero() {
-// runSparsityEstimateTest(new EstimatorBasicWorst(), m, k, sparsity, eqzero);
-// }
-
-// @Test
-// public void testWCasediag() {
-// runSparsityEstimateTest(new EstimatorBasicWorst(), m, k, sparsity, diag);
-// }
-
+
@Test
- public void testWorstNeqzero() {
+ public void testWCNeqzero() {
runSparsityEstimateTest(new EstimatorBasicWorst(), m, k, sparsity, neqzero);
}
@Test
- public void testWoestTrans() {
+ public void testWCTrans() {
runSparsityEstimateTest(new EstimatorBasicWorst(), m, k, sparsity, trans);
}
@Test
- public void testWorstReshape() {
+ public void testWCReshape() {
runSparsityEstimateTest(new EstimatorBasicWorst(), m, k, sparsity, reshape);
}
-// //DensityMap
-// @Test
-// public void testDMCaseeqzero() {
-// runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, eqzero);
-// }
-//
-// @Test
-// public void testDMCasediag() {
-// runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, diag);
-// }
-//
-// @Test
-// public void testDMCaseneqzero() {
-// runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, neqzero);
-// }
-//
-// @Test
-// public void testDMCasetrans() {
-// runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, trans);
-// }
-//
-// @Test
-// public void testDMCasereshape() {
-// runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, reshape);
-// }
-//
-// //MNC
-// @Test
-// public void testMNCCaseeqzero() {
-// runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, eqzero);
-// }
-//
-// @Test
-// public void testMNCCasediag() {
-// runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, diag);
-// }
-//
-// @Test
-// public void testMNCCaseneqzero() {
-// runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, neqzero);
-// }
-//
-// @Test
-// public void testMNCCasetrans() {
-// runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, trans);
-// }
-//
-// @Test
-// public void testMNCCasereshape() {
-// runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, reshape);
-// }
-//
- //Bitset
-// @Test
-// public void testBitsetCaseeqzero() {
-// runSparsityEstimateTest(new EstimatorBitsetMM(), m, k, sparsity, eqzero);
-// }
+ @Test
+ public void testDMapNeqzero() {
+ runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, neqzero);
+ }
+
+ @Test
+ public void testDMapTrans() {
+ runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, trans);
+ }
-// @Test
-// public void testBitsetCasediag() {
-// runSparsityEstimateTest(new EstimatorBitsetMM(), m, k, sparsity, diag);
-// }
+ @Test
+ public void testDMapReshape() {
+ runSparsityEstimateTest(new EstimatorDensityMap(), m, k, sparsity, reshape);
+ }
@Test
public void testBitsetNeqzero() {
@@ -179,58 +110,6 @@ public class OpSingleTest extends AutomatedTestBase
runSparsityEstimateTest(new EstimatorBitsetMM(), m, k, sparsity, reshape);
}
-// //Layered Graph
-// @Test
-// public void testLGCaseeqzero() {
-// runSparsityEstimateTest(new EstimatorLayeredGraph(), m, k, sparsity, eqzero);
-// }
-//
-// @Test
-// public void testLGCasediag() {
-// runSparsityEstimateTest(new EstimatorLayeredGraph(), m, k, sparsity, diag);
-// }
-//
-// @Test
-// public void testLGCaseneqzero() {
-// runSparsityEstimateTest(new EstimatorLayeredGraph(), m, k, sparsity, neqzero);
-// }
-//
-// @Test
-// public void testLGCasetans() {
-// runSparsityEstimateTest(new EstimatorLayeredGraph(), m, k, sparsity, trans);
-// }
-//
-// @Test
-// public void testLGCasereshape() {
-// runSparsityEstimateTest(new EstimatorLayeredGraph(), m, k, sparsity, reshape);
-// }
-//
-// //Sample
-// @Test
-// public void testSampleCaseeqzero() {
-// runSparsityEstimateTest(new EstimatorSample(), m, k, sparsity, eqzero);
-// }
-//
-// @Test
-// public void testSampleCasediag() {
-// runSparsityEstimateTest(new EstimatorSample(), m, k, sparsity, diag);
-// }
-//
-// @Test
-// public void testSampleCaseneqzero() {
-// runSparsityEstimateTest(new EstimatorSample(), m, k, sparsity, neqzero);
-// }
-//
-// @Test
-// public void testSampleCasetrans() {
-// runSparsityEstimateTest(new EstimatorSample(), m, k, sparsity, trans);
-// }
-//
-// @Test
-// public void testSampleCasereshape() {
-// runSparsityEstimateTest(new EstimatorSample(), m, k, sparsity, reshape);
-// }
-
private void runSparsityEstimateTest(SparsityEstimator estim, int m, int k, double sp, OpCode op) {
MatrixBlock m1 = MatrixBlock.randOperations(m, k, sp, 1, 1, "uniform", 3);
MatrixBlock m2 = new MatrixBlock();
@@ -255,6 +134,6 @@ public class OpSingleTest extends AutomatedTestBase
throw new NotImplementedException();
}
//compare estimated and real sparsity
- TestUtils.compareScalars(est, m2.getSparsity(), (estim instanceof EstimatorBasicWorst) ? 5e-1 : 1e-2);
+ TestUtils.compareScalars(est, m2.getSparsity(), 0);
}
}