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/15 06:20:27 UTC
systemml git commit: [SYSTEMML-2479] Extended sampling-based sparsity
estimator, misc fixes
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 <jo...@mail-sommer.com>
Authored: Tue Aug 14 23:19:11 2018 -0700
Committer: Matthias Boehm <mb...@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,