Repository: systemml Updated Branches: refs/heads/master db0207900 -> f296f8f51
[SYSTEMML-2479] Extended sampling-based sparsity estimator, misc fixes Closes #828. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/f296f8f5 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/f296f8f5 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/f296f8f5 Branch: refs/heads/master Commit: f296f8f51e990ad6c2c3db9f9e5b2fc8e8108611 Parents: db02079 Author: Johanna Sommer <joha...@mail-sommer.com> Authored: Tue Aug 14 23:19:11 2018 -0700 Committer: Matthias Boehm <mboe...@gmail.com> Committed: Tue Aug 14 23:19:19 2018 -0700 ---------------------------------------------------------------------- .../sysml/hops/estim/EstimatorBitsetMM.java | 2 +- .../sysml/hops/estim/EstimatorDensityMap.java | 2 +- .../hops/estim/EstimatorMatrixHistogram.java | 26 +++--- .../sysml/hops/estim/EstimatorSample.java | 96 +++++++++++++++++--- .../instructions/gpu/DnnGPUInstruction.java | 2 +- .../functions/estim/OpElemWTest.java | 37 +++----- .../functions/estim/SquaredProductTest.java | 2 +- .../functions/estim/ZPackageSuite.java | 2 + 8 files changed, 117 insertions(+), 52 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/f296f8f5/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 16a8a3a..aacbf29 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java @@ -50,7 +50,7 @@ public class EstimatorBitsetMM extends SparsityEstimator if (!root.getLeft().isLeaf()) estim(root.getLeft()); // obtain synopsis if (!root.getRight().isLeaf()) - estim(root.getLeft()); // obtain synopsis + estim(root.getRight()); // obtain synopsis BitsetMatrix m1Map = !root.getLeft().isLeaf() ? (BitsetMatrix) root.getLeft().getSynopsis() : new BitsetMatrix1(root.getLeft().getData()); BitsetMatrix m2Map = !root.getRight().isLeaf() ? (BitsetMatrix) root.getRight().getSynopsis() : http://git-wip-us.apache.org/repos/asf/systemml/blob/f296f8f5/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 b6fca0f..3206ab6 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java @@ -58,7 +58,7 @@ public class EstimatorDensityMap extends SparsityEstimator if( !root.getLeft().isLeaf() ) estim(root.getLeft()); //obtain synopsis if( !root.getRight().isLeaf() ) - estim(root.getLeft()); //obtain synopsis + estim(root.getRight()); //obtain synopsis DensityMap m1Map = !root.getLeft().isLeaf() ? (DensityMap)root.getLeft().getSynopsis() : new DensityMap(root.getLeft().getData(), _b); http://git-wip-us.apache.org/repos/asf/systemml/blob/f296f8f5/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 26b3df0..cd4b397 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java @@ -58,7 +58,7 @@ public class EstimatorMatrixHistogram extends SparsityEstimator if( !root.getLeft().isLeaf() ) estim(root.getLeft()); //obtain synopsis if( !root.getRight().isLeaf() ) - estim(root.getLeft()); //obtain synopsis + estim(root.getRight()); //obtain synopsis MatrixHistogram h1 = !root.getLeft().isLeaf() ? (MatrixHistogram)root.getLeft().getSynopsis() : new MatrixHistogram(root.getLeft().getData(), _useExcepts); @@ -105,21 +105,21 @@ public class EstimatorMatrixHistogram extends SparsityEstimator case MM: return estimInternMM(h1, h2); case MULT: { - final long N1 = h1.getNonZeros(); - final long N2 = h2.getNonZeros(); + final double N1 = h1.getNonZeros(); + final double N2 = h2.getNonZeros(); final long scale = IntStream.range(0, h1.getCols()) .mapToLong(j -> (long)h1.cNnz[j] * h2.cNnz[j]).sum(); return IntStream.range(0, h1.getRows()) - .mapToLong(i -> (long)h1.rNnz[i] * h2.rNnz[i] * scale / N1 / N2) //collisions + .mapToDouble(i -> (long)h1.rNnz[i] * h2.rNnz[i] * scale / N1 / N2) //collisions .sum() / msize; } case PLUS: { - final long N1 = h1.getNonZeros(); - final long N2 = h2.getNonZeros(); + final double N1 = h1.getNonZeros(); + final double N2 = h2.getNonZeros(); final long scale = IntStream.range(0, h1.getCols()) .mapToLong(j -> (long)h1.cNnz[j] * h2.cNnz[j]).sum(); return IntStream.range(0, h1.getRows()) - .mapToLong(i -> (long)h1.rNnz[i] + h2.rNnz[i] //all minus collisions + .mapToDouble(i -> (long)h1.rNnz[i] + h2.rNnz[i] //all minus collisions - (long)h1.rNnz[i] * h2.rNnz[i] * scale / N1 / N2) .sum() / msize; } @@ -356,12 +356,12 @@ public class EstimatorMatrixHistogram extends SparsityEstimator } private static MatrixHistogram deriveMultHistogram(MatrixHistogram h1, MatrixHistogram h2) { - final long N1 = h1.getNonZeros(); - final long N2 = h2.getNonZeros(); - final long scaler = IntStream.range(0, h1.getCols()) - .mapToLong(j -> (long)h1.cNnz[j] * h2.cNnz[j]).sum(); - final long scalec = IntStream.range(0, h1.getRows()) - .mapToLong(j -> (long)h1.rNnz[j] * h2.rNnz[j]).sum(); + final double N1 = h1.getNonZeros(); + final double N2 = h2.getNonZeros(); + final double scaler = IntStream.range(0, h1.getCols()) + .mapToDouble(j -> (long)h1.cNnz[j] * h2.cNnz[j]).sum(); + final double scalec = IntStream.range(0, h1.getRows()) + .mapToDouble(j -> (long)h1.rNnz[j] * h2.rNnz[j]).sum(); int rMaxNnz = 0, cMaxNnz = 0; Random rn = new Random(); int[] rNnz = new int[h1.getRows()]; http://git-wip-us.apache.org/repos/asf/systemml/blob/f296f8f5/src/main/java/org/apache/sysml/hops/estim/EstimatorSample.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorSample.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorSample.java index 1df23dd..faf7d0e 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorSample.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorSample.java @@ -63,27 +63,89 @@ public class EstimatorSample extends SparsityEstimator @Override public double estim(MatrixBlock m1, MatrixBlock m2) { - //get sampled indexes - int k = m1.getNumColumns(); - int[] ix = UtilFunctions.getSortedSampleIndexes( - k, (int)Math.max(k*_frac, 1)); - //compute output sparsity - int[] cnnz = computeColumnNnz(m1, ix); - long nnzOut = 0; - for(int i=0; i<ix.length; i++) - nnzOut = Math.max(nnzOut, cnnz[i] * m2.recomputeNonZeros(ix[i], ix[i])); - return OptimizerUtils.getSparsity( - m1.getNumRows(), m2.getNumColumns(), nnzOut); + return estim(m1, m2, OpCode.MM); } @Override public double estim(MatrixBlock m1, MatrixBlock m2, OpCode op) { - throw new NotImplementedException(); + switch(op) { + case MM: { + int k = m1.getNumColumns(); + int[] ix = UtilFunctions.getSortedSampleIndexes( + k, (int)Math.max(k*_frac, 1)); + int[] cnnz = computeColumnNnz(m1, ix); + long nnzOut = 0; + for(int i=0; i<ix.length; i++) + nnzOut = Math.max(nnzOut, cnnz[i] * m2.recomputeNonZeros(ix[i], ix[i])); + return OptimizerUtils.getSparsity( + m1.getNumRows(), m2.getNumColumns(), nnzOut); + } + case MULT: { + int k = Math.max(m1.getNumColumns(), m1.getNumRows()); + int[] ix = UtilFunctions.getSortedSampleIndexes( + k, (int)Math.max(k*_frac, 1)); + double spOut = 0; + if( m1.getNumColumns() > m1.getNumRows() ) { + int[] cnnz1 = computeColumnNnz(m1, ix); + int[] cnnz2 = computeColumnNnz(m2, ix); + for(int i=0; i<ix.length; i++) + spOut += (double)cnnz1[i]/m1.getNumRows() + * (double)cnnz2[i]/m1.getNumRows(); + } + else { + int[] rnnz1 = computeRowNnz(m1, ix); + int[] rnnz2 = computeRowNnz(m2, ix); + for(int i=0; i<ix.length; i++) + spOut += (double)rnnz1[i]/m1.getNumColumns() + * (double)rnnz2[i]/m1.getNumColumns(); + } + return spOut/ix.length; + } + case PLUS: { + int k = Math.max(m1.getNumColumns(), m1.getNumRows()); + int[] ix = UtilFunctions.getSortedSampleIndexes( + k, (int)Math.max(k*_frac, 1)); + double spOut = 0; + if( m1.getNumColumns() > m1.getNumRows() ) { + int[] cnnz1 = computeColumnNnz(m1, ix); + int[] cnnz2 = computeColumnNnz(m2, ix); + for(int i=0; i<ix.length; i++) { + spOut += (double)cnnz1[i]/m1.getNumRows() + + (double)cnnz2[i]/m1.getNumRows() + - (double)cnnz1[i]/m1.getNumRows() + * (double)cnnz2[i]/m1.getNumRows(); + } + } + else { + int[] rnnz1 = computeRowNnz(m1, ix); + int[] rnnz2 = computeRowNnz(m2, ix); + for(int i=0; i<ix.length; i++) { + spOut += (double)rnnz1[i]/m1.getNumColumns() + + (double)rnnz2[i]/m1.getNumColumns() + - (double)rnnz1[i]/m1.getNumColumns() + * (double)rnnz2[i]/m1.getNumColumns(); + } + } + return spOut/ix.length; + } + case RBIND: + case CBIND: + case EQZERO: + case NEQZERO: + case TRANS: + case DIAG: + case RESHAPE: + MatrixCharacteristics mc1 = m1.getMatrixCharacteristics(); + MatrixCharacteristics mc2 = m2.getMatrixCharacteristics(); + return OptimizerUtils.getSparsity(estimExactMetaData(mc1, mc2, op)); + default: + throw new NotImplementedException(); + } } @Override public double estim(MatrixBlock m, OpCode op) { - throw new NotImplementedException(); + return estim(m, null, op); } private int[] computeColumnNnz(MatrixBlock in, int[] ix) { @@ -113,4 +175,12 @@ public class EstimatorSample extends SparsityEstimator ret[i] = nnz[ix[i]]; return ret; } + + private int[] computeRowNnz(MatrixBlock in, int[] ix) { + //copy nnz into reduced vector + int[] ret = new int[ix.length]; + for(int i=0; i<ix.length; i++) + ret[i] = (int) in.recomputeNonZeros(ix[i], ix[i]); + return ret; + } } http://git-wip-us.apache.org/repos/asf/systemml/blob/f296f8f5/src/main/java/org/apache/sysml/runtime/instructions/gpu/DnnGPUInstruction.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/instructions/gpu/DnnGPUInstruction.java b/src/main/java/org/apache/sysml/runtime/instructions/gpu/DnnGPUInstruction.java index 8d89032..e774dcd 100644 --- a/src/main/java/org/apache/sysml/runtime/instructions/gpu/DnnGPUInstruction.java +++ b/src/main/java/org/apache/sysml/runtime/instructions/gpu/DnnGPUInstruction.java @@ -577,7 +577,7 @@ public class DnnGPUInstruction extends GPUInstruction { } private void processNesterovUpdateInstruction(ExecutionContext ec) { - GPUStatistics.incrementNoOfExecutedGPUInst();; + GPUStatistics.incrementNoOfExecutedGPUInst(); MatrixObject input = getMatrixInputForGPUInstruction(ec, _input1.getName()); MatrixObject v = getMatrixInputForGPUInstruction(ec, _input2.getName()); MatrixObject v_prev = getMatrixInputForGPUInstruction(ec, _input3.getName()); http://git-wip-us.apache.org/repos/asf/systemml/blob/f296f8f5/src/test/java/org/apache/sysml/test/integration/functions/estim/OpElemWTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/estim/OpElemWTest.java b/src/test/java/org/apache/sysml/test/integration/functions/estim/OpElemWTest.java index 7867f26..69a7325 100644 --- a/src/test/java/org/apache/sysml/test/integration/functions/estim/OpElemWTest.java +++ b/src/test/java/org/apache/sysml/test/integration/functions/estim/OpElemWTest.java @@ -27,6 +27,7 @@ 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.EstimatorMatrixHistogram; +import org.apache.sysml.hops.estim.EstimatorSample; import org.apache.sysml.hops.estim.SparsityEstimator; import org.apache.sysml.hops.estim.SparsityEstimator.OpCode; import org.apache.sysml.runtime.functionobjects.Multiply; @@ -42,16 +43,9 @@ public class OpElemWTest extends AutomatedTestBase { private final static int m = 1600; private final static int n = 700; - private final static double[] sparsity = new double[]{0.1, 0.04}; + private final static double[] sparsity = new double[]{0.2, 0.4}; private final static OpCode mult = OpCode.MULT; private final static OpCode plus = OpCode.PLUS; -// private final static OpCode rbind = OpCode.RBIND; -// private final static OpCode cbind = OpCode.CBIND; -// private final static OpCode eqzero = OpCode.EQZERO; -// private final static OpCode diag = OpCode.DIAG; -// private final static OpCode neqzero = OpCode.NEQZERO; -// private final static OpCode trans = OpCode.TRANS; -// private final static OpCode reshape = OpCode.RESHAPE; @Override public void setUp() { @@ -103,12 +97,12 @@ public class OpElemWTest extends AutomatedTestBase //Bitset @Test - public void testBitsetCasemult() { + public void testBitsetMult() { runSparsityEstimateTest(new EstimatorBitsetMM(), m, n, sparsity, mult); } @Test - public void testBitsetCaseplus() { + public void testBitsetPlus() { runSparsityEstimateTest(new EstimatorBitsetMM(), m, n, sparsity, plus); } /* @@ -117,23 +111,22 @@ public class OpElemWTest extends AutomatedTestBase public void testLGCasemult() { runSparsityEstimateTest(new EstimatorLayeredGraph(), m, k, n, sparsity, mult); } - + @Test public void testLGCaseplus() { runSparsityEstimateTest(new EstimatorLayeredGraph(), m, k, n, sparsity, plus); - } + }*/ //Sample @Test - public void testSampleCasemult() { - runSparsityEstimateTest(new EstimatorSample(), m, k, n, sparsity, mult); + public void testSampleMult() { + runSparsityEstimateTest(new EstimatorSample(), m, n, sparsity, mult); } - - @Test - public void testSampleCaseplus() { - runSparsityEstimateTest(new EstimatorSample(), m, k, n, sparsity, plus); - }*/ + @Test + public void testSamplePlus() { + runSparsityEstimateTest(new EstimatorSample(), m, n, sparsity, plus); + } private void runSparsityEstimateTest(SparsityEstimator estim, int m, int n, double[] sp, OpCode op) { MatrixBlock m1 = MatrixBlock.randOperations(m, n, sp[0], 1, 1, "uniform", 3); @@ -146,20 +139,20 @@ public class OpElemWTest extends AutomatedTestBase bOp = new BinaryOperator(Multiply.getMultiplyFnObject()); m1.binaryOperations(bOp, m2, m3); est = estim.estim(m1, m2, op); - System.out.println(m3.getSparsity()); System.out.println(est); + System.out.println(m3.getSparsity()); break; case PLUS: bOp = new BinaryOperator(Plus.getPlusFnObject()); m1.binaryOperations(bOp, m2, m3); est = estim.estim(m1, m2, op); - System.out.println(m3.getSparsity()); System.out.println(est); + System.out.println(m3.getSparsity()); break; default: throw new NotImplementedException(); } //compare estimated and real sparsity - TestUtils.compareScalars(est, m3.getSparsity(), (estim instanceof EstimatorBasicWorst) ? 5e-1 : 1e-3); + TestUtils.compareScalars(est, m3.getSparsity(), (estim instanceof EstimatorBasicWorst) ? 5e-1 : 5e-3); } } http://git-wip-us.apache.org/repos/asf/systemml/blob/f296f8f5/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 index 917764b..cd423af 100644 --- 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 @@ -146,7 +146,7 @@ public class SquaredProductTest extends AutomatedTestBase 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 m2 = MatrixBlock.randOperations(k, n, sp[1], 1, 1, "uniform", 7); MatrixBlock m3 = m1.aggregateBinaryOperations(m1, m2, new MatrixBlock(), InstructionUtils.getMatMultOperator(1)); http://git-wip-us.apache.org/repos/asf/systemml/blob/f296f8f5/src/test_suites/java/org/apache/sysml/test/integration/functions/estim/ZPackageSuite.java ---------------------------------------------------------------------- diff --git a/src/test_suites/java/org/apache/sysml/test/integration/functions/estim/ZPackageSuite.java b/src/test_suites/java/org/apache/sysml/test/integration/functions/estim/ZPackageSuite.java index 2760063..3cf152b 100644 --- a/src/test_suites/java/org/apache/sysml/test/integration/functions/estim/ZPackageSuite.java +++ b/src/test_suites/java/org/apache/sysml/test/integration/functions/estim/ZPackageSuite.java @@ -26,7 +26,9 @@ import org.junit.runners.Suite; * won't run two of them at once. */ @RunWith(Suite.class) @Suite.SuiteClasses({ + OpBindChainTest.class, OpBindTest.class, + OpElemWChainTest.class, OpElemWTest.class, OpSingleTest.class, OuterProductTest.class,
