Repository: systemml Updated Branches: refs/heads/master 7d007e7b2 -> 30cff5e22
[SYSTEMML-2291] Extended sparsity estimator layered graph for mm chains Closes #829. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/30cff5e2 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/30cff5e2 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/30cff5e2 Branch: refs/heads/master Commit: 30cff5e22ed992f9a3ab2447f26e9053b5e513bc Parents: 7d007e7 Author: Johanna Sommer <[email protected]> Authored: Sat Oct 6 16:52:39 2018 +0200 Committer: Matthias Boehm <[email protected]> Committed: Sat Oct 6 16:52:39 2018 +0200 ---------------------------------------------------------------------- .../sysml/hops/estim/EstimatorLayeredGraph.java | 27 +++++++++++++++----- .../functions/estim/SelfProductTest.java | 11 ++++++++ .../estim/SquaredProductChainTest.java | 11 ++++++++ .../functions/estim/SquaredProductTest.java | 11 ++++++++ 4 files changed, 53 insertions(+), 7 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/30cff5e2/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java b/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java index d103359..6130143 100644 --- a/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java +++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorLayeredGraph.java @@ -54,7 +54,10 @@ public class EstimatorLayeredGraph extends SparsityEstimator { @Override public MatrixCharacteristics estim(MMNode root) { - throw new NotImplementedException(); + List<MatrixBlock> leafs = getMatrices(root, new ArrayList<>()); + long nnz = new LayeredGraph(leafs, _rounds).estimateNnz(); + return root.setMatrixCharacteristics(new MatrixCharacteristics( + leafs.get(0).getNumRows(), leafs.get(leafs.size()-1).getNumColumns(), nnz)); } @Override @@ -69,20 +72,30 @@ public class EstimatorLayeredGraph extends SparsityEstimator { @Override public double estim(MatrixBlock m1, MatrixBlock m2) { - LayeredGraph graph = new LayeredGraph(m1, m2, _rounds); - return OptimizerUtils.getSparsity(m1.getNumRows(), - m2.getNumColumns(), graph.estimateNnz()); + LayeredGraph graph = new LayeredGraph(Arrays.asList(m1,m2), _rounds); + return OptimizerUtils.getSparsity( + m1.getNumRows(), m2.getNumColumns(), graph.estimateNnz()); + } + + private List<MatrixBlock> getMatrices(MMNode node, List<MatrixBlock> leafs) { + //NOTE: this extraction is only correct and efficient for chains, no DAGs + if( node.isLeaf() ) + leafs.add(node.getData()); + else { + getMatrices(node.getLeft(), leafs); + getMatrices(node.getRight(), leafs); + } + return leafs; } private static class LayeredGraph { private final List<Node[]> _nodes; //nodes partitioned by graph level private final int _rounds; //length of propagated r-vectors - public LayeredGraph(MatrixBlock m1, MatrixBlock m2, int r) { + public LayeredGraph(List<MatrixBlock> chain, int r) { _nodes = new ArrayList<>(); _rounds = r; - buildNext(m1); - buildNext(m2); + chain.forEach(i -> buildNext(i)); } public void buildNext(MatrixBlock mb) { http://git-wip-us.apache.org/repos/asf/systemml/blob/30cff5e2/src/test/java/org/apache/sysml/test/integration/functions/estim/SelfProductTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/estim/SelfProductTest.java b/src/test/java/org/apache/sysml/test/integration/functions/estim/SelfProductTest.java index d609f41..1d96e49 100644 --- a/src/test/java/org/apache/sysml/test/integration/functions/estim/SelfProductTest.java +++ b/src/test/java/org/apache/sysml/test/integration/functions/estim/SelfProductTest.java @@ -26,6 +26,7 @@ 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.EstimatorLayeredGraph; import org.apache.sysml.hops.estim.EstimatorMatrixHistogram; import org.apache.sysml.hops.estim.EstimatorSample; import org.apache.sysml.hops.estim.SparsityEstimator; @@ -129,6 +130,16 @@ public class SelfProductTest extends AutomatedTestBase runSparsityEstimateTest(new EstimatorSample(0.2), m, sparsity2); } + @Test + public void testLayeredGraphCase1() { + runSparsityEstimateTest(new EstimatorLayeredGraph(), m, sparsity1); + } + + @Test + public void testLayeredGraphCase2() { + runSparsityEstimateTest(new EstimatorLayeredGraph(), m, sparsity2); + } + private void runSparsityEstimateTest(SparsityEstimator estim, int n, double sp) { MatrixBlock m1 = MatrixBlock.randOperations(m, n, sp, 1, 1, "uniform", 3); MatrixBlock m3 = m1.aggregateBinaryOperations(m1, m1, http://git-wip-us.apache.org/repos/asf/systemml/blob/30cff5e2/src/test/java/org/apache/sysml/test/integration/functions/estim/SquaredProductChainTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/estim/SquaredProductChainTest.java b/src/test/java/org/apache/sysml/test/integration/functions/estim/SquaredProductChainTest.java index 0f4dad5..df2f3b4 100644 --- a/src/test/java/org/apache/sysml/test/integration/functions/estim/SquaredProductChainTest.java +++ b/src/test/java/org/apache/sysml/test/integration/functions/estim/SquaredProductChainTest.java @@ -23,6 +23,7 @@ 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.EstimatorLayeredGraph; import org.apache.sysml.hops.estim.EstimatorMatrixHistogram; import org.apache.sysml.hops.estim.MMNode; import org.apache.sysml.hops.estim.SparsityEstimator.OpCode; @@ -126,6 +127,16 @@ public class SquaredProductChainTest extends AutomatedTestBase runSparsityEstimateTest(new EstimatorMatrixHistogram(true), m, k, n, n2, case2); } + @Test + public void testLayeredGraphCase1() { + runSparsityEstimateTest(new EstimatorLayeredGraph(), m, k, n, n2, case1); + } + + @Test + public void testLayeredGraphCase2() { + runSparsityEstimateTest(new EstimatorLayeredGraph(), m, k, n, n2, case2); + } + private void runSparsityEstimateTest(SparsityEstimator estim, int m, int k, int n, int n2, double[] sp) { MatrixBlock m1 = MatrixBlock.randOperations(m, k, sp[0], 1, 1, "uniform", 1); MatrixBlock m2 = MatrixBlock.randOperations(k, n, sp[1], 1, 1, "uniform", 2); http://git-wip-us.apache.org/repos/asf/systemml/blob/30cff5e2/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 cd423af..77c0b1d 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 @@ -24,6 +24,7 @@ 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.EstimatorLayeredGraph; import org.apache.sysml.hops.estim.EstimatorMatrixHistogram; import org.apache.sysml.hops.estim.EstimatorSample; import org.apache.sysml.hops.estim.SparsityEstimator; @@ -144,6 +145,16 @@ public class SquaredProductTest extends AutomatedTestBase runSparsityEstimateTest(new EstimatorSample(0.2), m, k, n, case2); } + @Test + public void testLayeredGraphCase1() { + runSparsityEstimateTest(new EstimatorLayeredGraph(), m, k, n, case1); + } + + @Test + public void testLayeredGraphCase2() { + runSparsityEstimateTest(new EstimatorLayeredGraph(), 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", 7);
