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/05/02 03:54:23 UTC
[3/3] systemml git commit: [SYSTEMML-2288] Fix density-map sparsity
estimator, more tests
[SYSTEMML-2288] Fix density-map sparsity estimator, more tests
This patch fixes a correctness issue of the sparsity estimator based on
density maps along with new tests for squared uniformly distributed
matrices (for all estimators).
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/aa253eb7
Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/aa253eb7
Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/aa253eb7
Branch: refs/heads/master
Commit: aa253eb7eaf272175fbfe7e0e7b1a586cb18b68c
Parents: e21f840
Author: Matthias Boehm <mb...@gmail.com>
Authored: Tue May 1 20:55:05 2018 -0700
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Tue May 1 20:55:05 2018 -0700
----------------------------------------------------------------------
.../sysml/hops/estim/EstimatorDensityMap.java | 17 +--
.../functions/estim/OuterProductTest.java | 11 ++
.../functions/estim/SquaredProductTest.java | 117 +++++++++++++++++++
3 files changed, 137 insertions(+), 8 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/systemml/blob/aa253eb7/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 5e8d880..1883d59 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java
@@ -65,7 +65,7 @@ public class EstimatorDensityMap extends SparsityEstimator
//estimate output density map and sparsity
MatrixBlock outMap = estimIntern(m1Map, m2Map,
- true, root.getRows(), root.getCols());
+ true, root.getRows(), root.getLeft().getCols(), root.getCols());
root.setSynopsis(outMap); //memoize density map
return OptimizerUtils.getSparsity( //aggregate output histogram
root.getRows(), root.getCols(), (long)outMap.sum());
@@ -76,7 +76,7 @@ public class EstimatorDensityMap extends SparsityEstimator
MatrixBlock m1Map = computeDensityMap(m1);
MatrixBlock m2Map = computeDensityMap(m2);
MatrixBlock outMap = estimIntern(m1Map, m2Map,
- true, m1.getNumRows(), m2.getNumColumns());
+ true, m1.getNumRows(), m1.getNumColumns(), m2.getNumColumns());
return OptimizerUtils.getSparsity( //aggregate output histogram
m1.getNumRows(), m2.getNumColumns(), (long)outMap.sum());
}
@@ -135,11 +135,12 @@ 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 rlen number of rows of output matrix, required for returning nnz
- * @param clen number of columns of output matrix, required for returning nnz
+ * @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 rlen, int clen) {
+ private MatrixBlock estimIntern(MatrixBlock m1Map, MatrixBlock m2Map, boolean retNnz, int mOrig, int cdOrig, int nOrig) {
final int m = m1Map.getNumRows();
final int cd = m1Map.getNumColumns();
final int n = m2Map.getNumColumns();
@@ -151,7 +152,7 @@ public class EstimatorDensityMap extends SparsityEstimator
DenseBlock c = out.allocateBlock().getDenseBlock();
for(int i=0; i<m; i++) {
for(int k=0; k<cd; k++) {
- int lbk = UtilFunctions.computeBlockSize(cd, k+1, _b);
+ int lbk = UtilFunctions.computeBlockSize(cdOrig, k+1, _b);
double sp1 = m1Map.quickGetValue(i, k);
for(int j=0; j<n; j++) {
double sp2 = m2Map.quickGetValue(k, j);
@@ -164,9 +165,9 @@ public class EstimatorDensityMap extends SparsityEstimator
}
//scale to non-zeros instead of sparsity if needed
if( retNnz ) {
- int lbm = UtilFunctions.computeBlockSize(rlen, i+1, _b);
+ int lbm = UtilFunctions.computeBlockSize(mOrig, i+1, _b);
for( int j=0; j<n; j++ ) {
- int lbn = UtilFunctions.computeBlockSize(clen, j+1, _b);
+ int lbn = UtilFunctions.computeBlockSize(nOrig, j+1, _b);
c.set(i, j, c.get(i, j) * lbm * lbn);
}
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/aa253eb7/src/test/java/org/apache/sysml/test/integration/functions/estim/OuterProductTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/sysml/test/integration/functions/estim/OuterProductTest.java b/src/test/java/org/apache/sysml/test/integration/functions/estim/OuterProductTest.java
index 0392c7b..90f316c 100644
--- a/src/test/java/org/apache/sysml/test/integration/functions/estim/OuterProductTest.java
+++ b/src/test/java/org/apache/sysml/test/integration/functions/estim/OuterProductTest.java
@@ -22,6 +22,7 @@ package org.apache.sysml.test.integration.functions.estim;
import org.junit.Test;
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.runtime.instructions.InstructionUtils;
@@ -86,6 +87,16 @@ public class OuterProductTest extends AutomatedTestBase
runSparsityEstimateTest(new EstimatorDensityMap(7), m, k, n, case2);
}
+ @Test
+ public void testBitsetMatrixCase1() {
+ runSparsityEstimateTest(new EstimatorBitsetMM(), m, k, n, case1);
+ }
+
+ @Test
+ public void testBitsetMatrixCase2() {
+ runSparsityEstimateTest(new EstimatorBitsetMM(), m, k, n, case2);
+ }
+
private void runSparsityEstimateTest(SparsityEstimator estim, int m, int k, int n, double[] sp) {
MatrixBlock m1 = MatrixBlock.randOperations(m, k, sp[0], 1, 1, "uniform", 3);
MatrixBlock m2 = MatrixBlock.randOperations(k, n, sp[1], 1, 1, "uniform", 3);
http://git-wip-us.apache.org/repos/asf/systemml/blob/aa253eb7/src/test/java/org/apache/sysml/test/integration/functions/estim/SquaredProductTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/sysml/test/integration/functions/estim/SquaredProductTest.java b/src/test/java/org/apache/sysml/test/integration/functions/estim/SquaredProductTest.java
new file mode 100644
index 0000000..99b1b3b
--- /dev/null
+++ b/src/test/java/org/apache/sysml/test/integration/functions/estim/SquaredProductTest.java
@@ -0,0 +1,117 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysml.test.integration.functions.estim;
+
+import org.junit.Test;
+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.runtime.instructions.InstructionUtils;
+import org.apache.sysml.runtime.matrix.data.MatrixBlock;
+import org.apache.sysml.test.integration.AutomatedTestBase;
+import org.apache.sysml.test.utils.TestUtils;
+
+/**
+ * This is a basic sanity check for all estimator, which need
+ * to compute a reasonable estimate for uniform data.
+ */
+public class SquaredProductTest extends AutomatedTestBase
+{
+ private final static int m = 1000;
+ private final static int k = 1000;
+ private final static int n = 1000;
+ private final static double[] case1 = new double[]{0.0001, 0.00007};
+ private final static double[] case2 = new double[]{0.0006, 0.00007};
+
+ private final static double eps1 = 0.05;
+ private final static double eps2 = 1e-4;
+ private final static double eps3 = 0;
+
+
+ @Override
+ public void setUp() {
+ //do nothing
+ }
+
+ @Test
+ public void testBasicAvgCase1() {
+ runSparsityEstimateTest(new EstimatorBasicAvg(), m, k, n, case1);
+ }
+
+ @Test
+ public void testBasicAvgCase2() {
+ runSparsityEstimateTest(new EstimatorBasicAvg(), m, k, n, case2);
+ }
+
+ @Test
+ public void testBasicWorstCase1() {
+ runSparsityEstimateTest(new EstimatorBasicWorst(), m, k, n, case1);
+ }
+
+ @Test
+ public void testBasicWorstCase2() {
+ runSparsityEstimateTest(new EstimatorBasicWorst(), m, k, n, case2);
+ }
+
+ @Test
+ public void testDensityMapCase1() {
+ runSparsityEstimateTest(new EstimatorDensityMap(), m, k, n, case1);
+ }
+
+ @Test
+ public void testDensityMapCase2() {
+ runSparsityEstimateTest(new EstimatorDensityMap(), m, k, n, case2);
+ }
+
+ @Test
+ public void testDensityMap7Case1() {
+ runSparsityEstimateTest(new EstimatorDensityMap(7), m, k, n, case1);
+ }
+
+ @Test
+ public void testDensityMap7Case2() {
+ runSparsityEstimateTest(new EstimatorDensityMap(7), m, k, n, case2);
+ }
+
+ @Test
+ public void testBitsetMatrixCase1() {
+ runSparsityEstimateTest(new EstimatorBitsetMM(), m, k, n, case1);
+ }
+
+ @Test
+ public void testBitsetMatrixCase2() {
+ runSparsityEstimateTest(new EstimatorBitsetMM(), m, k, n, case2);
+ }
+
+ private void runSparsityEstimateTest(SparsityEstimator estim, int m, int k, int n, double[] sp) {
+ MatrixBlock m1 = MatrixBlock.randOperations(m, k, sp[0], 1, 1, "uniform", 3);
+ MatrixBlock m2 = MatrixBlock.randOperations(k, n, sp[1], 1, 1, "uniform", 3);
+ MatrixBlock m3 = m1.aggregateBinaryOperations(m1, m2,
+ new MatrixBlock(), InstructionUtils.getMatMultOperator(1));
+
+ //compare estimated and real sparsity
+ double est = estim.estim(m1, m2);
+ TestUtils.compareScalars(est, m3.getSparsity(),
+ (estim instanceof EstimatorBitsetMM) ? eps3 : //exact
+ (estim instanceof EstimatorBasicWorst) ? eps1 : eps2);
+ }
+}