[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 <[email protected]> Authored: Tue May 1 20:55:05 2018 -0700 Committer: Matthias Boehm <[email protected]> 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); + } +}
