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/10/06 14:55:03 UTC
systemml git commit: [SYSTEMML-2291] Extended sparsity estimator
layered graph for mm chains
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 <jo...@mail-sommer.com>
Authored: Sat Oct 6 16:52:39 2018 +0200
Committer: Matthias Boehm <mb...@gmail.com>
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);