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 2019/01/14 17:15:24 UTC
[systemml] branch master updated: [SYSTEMML-2486] Fix memoization
of sparsity sketches for DAG leafs
This is an automated email from the ASF dual-hosted git repository.
mboehm7 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/systemml.git
The following commit(s) were added to refs/heads/master by this push:
new b2fa1af [SYSTEMML-2486] Fix memoization of sparsity sketches for DAG leafs
b2fa1af is described below
commit b2fa1af0c9919c0d703b1eddc32c3cd493e82bf2
Author: Matthias Boehm <mb...@gmail.com>
AuthorDate: Mon Jan 14 18:06:52 2019 +0100
[SYSTEMML-2486] Fix memoization of sparsity sketches for DAG leafs
This patch improves the performance of sparsity estimation for DAGs
where leaf nodes are reachable multiple times. So far, we redundantly
created the leaf sketches from the base data on each access. Instead, we
now properly memoize these sketches similar to inner nodes.
---
.../apache/sysml/hops/estim/EstimatorBitsetMM.java | 20 +++++++++++++------
.../sysml/hops/estim/EstimatorDensityMap.java | 21 ++++++++++++--------
.../sysml/hops/estim/EstimatorMatrixHistogram.java | 23 ++++++++++++----------
.../apache/sysml/hops/estim/SparsityEstimator.java | 7 -------
4 files changed, 40 insertions(+), 31 deletions(-)
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 07d4cdc..e26dd49 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorBitsetMM.java
@@ -46,12 +46,9 @@ public class EstimatorBitsetMM extends SparsityEstimator
{
@Override
public MatrixCharacteristics estim(MMNode root) {
- estimateInputs(root);
- BitsetMatrix m1Map = !root.getLeft().isLeaf() ? (BitsetMatrix) root.getLeft().getSynopsis() :
- new BitsetMatrix1(root.getLeft().getData());
- BitsetMatrix m2Map = root.getRight() == null ? null :
- !root.getRight().isLeaf() ? (BitsetMatrix) root.getRight().getSynopsis() :
- new BitsetMatrix1(root.getRight().getData());
+ BitsetMatrix m1Map = getCachedSynopsis(root.getLeft());
+ BitsetMatrix m2Map = getCachedSynopsis(root.getRight());
+
BitsetMatrix outMap = estimInternal(m1Map, m2Map, root.getOp());
root.setSynopsis(outMap); // memorize boolean matrix
return root.setMatrixCharacteristics(new MatrixCharacteristics(
@@ -86,6 +83,17 @@ public class EstimatorBitsetMM extends SparsityEstimator
outMap.getNumColumns(), outMap.getNonZeros());
}
+ private BitsetMatrix getCachedSynopsis(MMNode node) {
+ if( node == null )
+ return null;
+ //ensure synopsis is properly cached and reused
+ if( node.isLeaf() && node.getSynopsis() == null )
+ node.setSynopsis(new BitsetMatrix1(node.getData()));
+ else if( !node.isLeaf() )
+ estim(node); //recursively obtain synopsis
+ return (BitsetMatrix) node.getSynopsis();
+ }
+
private BitsetMatrix estimInternal(BitsetMatrix m1Map, BitsetMatrix m2Map, OpCode op) {
switch(op) {
case MM: return m1Map.matMult(m2Map);
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 260df5d..8a78a9e 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorDensityMap.java
@@ -55,14 +55,8 @@ public class EstimatorDensityMap extends SparsityEstimator
@Override
public MatrixCharacteristics estim(MMNode root) {
- estimateInputs(root);
- DensityMap m1Map = !root.getLeft().isLeaf() ?
- (DensityMap)root.getLeft().getSynopsis() :
- new DensityMap(root.getLeft().getData(), _b);
- DensityMap m2Map = root.getRight()==null ? null:
- !root.getRight().isLeaf() ?
- (DensityMap)root.getRight().getSynopsis() :
- new DensityMap(root.getRight().getData(), _b);
+ DensityMap m1Map = getCachedSynopsis(root.getLeft());
+ DensityMap m2Map = getCachedSynopsis(root.getRight());
//estimate output density map and sparsity
DensityMap outMap = estimIntern(m1Map, m2Map, root.getOp());
@@ -94,6 +88,17 @@ public class EstimatorDensityMap extends SparsityEstimator
return estim(m, null, op);
}
+ private DensityMap getCachedSynopsis(MMNode node) {
+ if( node == null )
+ return null;
+ //ensure synopsis is properly cached and reused
+ if( node.isLeaf() && node.getSynopsis() == null )
+ node.setSynopsis(new DensityMap(node.getData(), _b));
+ else if( !node.isLeaf() )
+ estim(node); //recursively obtain synopsis
+ return (DensityMap) node.getSynopsis();
+ }
+
/**
* Computes the output density map given the density maps of the input operands.
*
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 37ad4a9..57fc97e 100644
--- a/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java
+++ b/src/main/java/org/apache/sysml/hops/estim/EstimatorMatrixHistogram.java
@@ -60,16 +60,8 @@ public class EstimatorMatrixHistogram extends SparsityEstimator
private MatrixCharacteristics estim(MMNode root, boolean topLevel) {
//NOTE: not estimateInputs due to handling of topLevel
- if( !root.getLeft().isLeaf() )
- estim(root.getLeft(), false); //obtain synopsis
- if( root.getRight()!=null && !root.getRight().isLeaf() )
- estim(root.getRight(), false); //obtain synopsis
- MatrixHistogram h1 = !root.getLeft().isLeaf() ?
- (MatrixHistogram)root.getLeft().getSynopsis() :
- new MatrixHistogram(root.getLeft().getData(), _useExtended);
- MatrixHistogram h2 = root.getRight() != null ? !root.getRight().isLeaf() ?
- (MatrixHistogram)root.getRight().getSynopsis() :
- new MatrixHistogram(root.getRight().getData(), _useExtended) : null;
+ MatrixHistogram h1 = getCachedSynopsis(root.getLeft());
+ MatrixHistogram h2 = getCachedSynopsis(root.getRight());
//estimate output sparsity based on input histograms
double ret = estimIntern(h1, h2, root.getOp(), root.getMisc());
@@ -110,6 +102,17 @@ public class EstimatorMatrixHistogram extends SparsityEstimator
return estimIntern(h1, null, op, null);
}
+ private MatrixHistogram getCachedSynopsis(MMNode node) {
+ if( node == null )
+ return null;
+ //ensure synopsis is properly cached and reused
+ if( node.isLeaf() && node.getSynopsis() == null )
+ node.setSynopsis(new MatrixHistogram(node.getData(), _useExtended));
+ else if( !node.isLeaf() )
+ estim(node, false); //recursively obtain synopsis
+ return (MatrixHistogram) node.getSynopsis();
+ }
+
public double estimIntern(MatrixHistogram h1, MatrixHistogram h2, OpCode op, long[] misc) {
double msize = (double)h1.getRows()*h1.getCols();
switch (op) {
diff --git a/src/main/java/org/apache/sysml/hops/estim/SparsityEstimator.java b/src/main/java/org/apache/sysml/hops/estim/SparsityEstimator.java
index 2636be0..1286b85 100644
--- a/src/main/java/org/apache/sysml/hops/estim/SparsityEstimator.java
+++ b/src/main/java/org/apache/sysml/hops/estim/SparsityEstimator.java
@@ -115,11 +115,4 @@ public abstract class SparsityEstimator
throw new HopsException("Opcode is not an exact meta data operation: "+op.name());
}
}
-
- protected void estimateInputs(MMNode root) {
- if (!root.getLeft().isLeaf())
- estim(root.getLeft()); // obtain synopsis
- if (root.getRight()!=null && !root.getRight().isLeaf())
- estim(root.getRight()); // obtain synopsis
- }
}