You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemml.apache.org by lr...@apache.org on 2015/11/19 21:47:01 UTC
[19/50] [abbrv] incubator-systemml git commit: New simplification
rewrite 'fuse leftindexing chain to append', for glm
New simplification rewrite 'fuse leftindexing chain to append', for glm
Example: Y_prob[,1]=A; Y_prob[,2]=B --> Y_prob = cbind(A,B);
This rewrite prevents the unnecessary creation of a dense intermediate
and thus improves performance due to less write and potential buffer
pool evictions.
This change also includes a cleanup wrt recompilation of append, which
was unnecessarily marked always for recompilation. Given correct size
inference over loops and complex control structures, this special case
is not required.
Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/ca1a0604
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/ca1a0604
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/ca1a0604
Branch: refs/heads/master
Commit: ca1a060490e3428c70af546b24f5f045bbeb4e6d
Parents: aecc398
Author: Matthias Boehm <mb...@us.ibm.com>
Authored: Sat Oct 31 14:19:59 2015 -0700
Committer: Matthias Boehm <mb...@us.ibm.com>
Committed: Sat Oct 31 14:19:59 2015 -0700
----------------------------------------------------------------------
src/main/java/com/ibm/bi/dml/hops/BinaryOp.java | 6 +-
.../bi/dml/hops/rewrite/HopRewriteUtils.java | 51 ++++++++++++++
.../RewriteAlgebraicSimplificationDynamic.java | 71 ++++++++++++++++++++
3 files changed, 124 insertions(+), 4 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/ca1a0604/src/main/java/com/ibm/bi/dml/hops/BinaryOp.java
----------------------------------------------------------------------
diff --git a/src/main/java/com/ibm/bi/dml/hops/BinaryOp.java b/src/main/java/com/ibm/bi/dml/hops/BinaryOp.java
index c2c111b..da7a72f 100644
--- a/src/main/java/com/ibm/bi/dml/hops/BinaryOp.java
+++ b/src/main/java/com/ibm/bi/dml/hops/BinaryOp.java
@@ -991,11 +991,9 @@ public class BinaryOp extends Hop
//pull unary scalar operation into spark
_etype = ExecType.SPARK;
}
-
+
//mark for recompile (forever)
- if( OptimizerUtils.ALLOW_DYN_RECOMPILATION && ((!dimsKnown(true)&&_etype==REMOTE)
- || ((op == OpOp2.CBIND || op == OpOp2.RBIND) && getDataType()!=DataType.SCALAR) ) )
- {
+ if( OptimizerUtils.ALLOW_DYN_RECOMPILATION && !dimsKnown(true) && _etype==REMOTE ) {
setRequiresRecompile();
}
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/ca1a0604/src/main/java/com/ibm/bi/dml/hops/rewrite/HopRewriteUtils.java
----------------------------------------------------------------------
diff --git a/src/main/java/com/ibm/bi/dml/hops/rewrite/HopRewriteUtils.java b/src/main/java/com/ibm/bi/dml/hops/rewrite/HopRewriteUtils.java
index 2aa6355..2b1a785 100644
--- a/src/main/java/com/ibm/bi/dml/hops/rewrite/HopRewriteUtils.java
+++ b/src/main/java/com/ibm/bi/dml/hops/rewrite/HopRewriteUtils.java
@@ -36,6 +36,7 @@ import com.ibm.bi.dml.hops.Hop.ParamBuiltinOp;
import com.ibm.bi.dml.hops.Hop.ReOrgOp;
import com.ibm.bi.dml.hops.Hop.VisitStatus;
import com.ibm.bi.dml.hops.HopsException;
+import com.ibm.bi.dml.hops.LeftIndexingOp;
import com.ibm.bi.dml.hops.LiteralOp;
import com.ibm.bi.dml.hops.MemoTable;
import com.ibm.bi.dml.hops.ParameterizedBuiltinOp;
@@ -519,6 +520,24 @@ public class HopRewriteUtils
/**
*
+ * @param input1
+ * @param input2
+ * @param op
+ * @return
+ */
+ public static BinaryOp createBinary(Hop input1, Hop input2, OpOp2 op)
+ {
+ BinaryOp bop = new BinaryOp(input1.getName(), input1.getDataType(),
+ input1.getValueType(), op, input1, input2);
+ HopRewriteUtils.setOutputBlocksizes(bop, input1.getRowsInBlock(), input1.getColsInBlock());
+ HopRewriteUtils.copyLineNumbers(input1, bop);
+ bop.refreshSizeInformation();
+
+ return bop;
+ }
+
+ /**
+ *
* @param left
* @param right
* @return
@@ -773,6 +792,38 @@ public class HopRewriteUtils
* @param hop
* @return
*/
+ public static boolean isFullColumnIndexing(LeftIndexingOp hop)
+ {
+ boolean colPred = hop.getColLowerEqualsUpper(); //single col
+
+ Hop rl = hop.getInput().get(2);
+ Hop ru = hop.getInput().get(3);
+
+ return colPred && rl instanceof LiteralOp && getDoubleValueSafe((LiteralOp)rl)==1
+ && ru instanceof LiteralOp && getDoubleValueSafe((LiteralOp)ru)==hop.getDim1();
+ }
+
+ /**
+ *
+ * @param hop
+ * @return
+ */
+ public static boolean isFullRowIndexing(LeftIndexingOp hop)
+ {
+ boolean rowPred = hop.getRowLowerEqualsUpper(); //single row
+
+ Hop cl = hop.getInput().get(4);
+ Hop cu = hop.getInput().get(5);
+
+ return rowPred && cl instanceof LiteralOp && getDoubleValueSafe((LiteralOp)cl)==1
+ && cu instanceof LiteralOp && getDoubleValueSafe((LiteralOp)cu)==hop.getDim2();
+ }
+
+ /**
+ *
+ * @param hop
+ * @return
+ */
public static boolean isBasic1NSequence(Hop hop)
{
boolean ret = false;
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/ca1a0604/src/main/java/com/ibm/bi/dml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java
----------------------------------------------------------------------
diff --git a/src/main/java/com/ibm/bi/dml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java b/src/main/java/com/ibm/bi/dml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java
index 23e06f1..04505cd 100644
--- a/src/main/java/com/ibm/bi/dml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java
+++ b/src/main/java/com/ibm/bi/dml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java
@@ -139,6 +139,7 @@ public class RewriteAlgebraicSimplificationDynamic extends HopRewriteRule
hi = removeUnnecessaryRightIndexing(hop, hi, i); //e.g., X[,1] -> X, if output == input size
hi = removeEmptyLeftIndexing(hop, hi, i); //e.g., X[,1]=Y -> matrix(0,nrow(X),ncol(X)), if nnz(X)==0 and nnz(Y)==0
hi = removeUnnecessaryLeftIndexing(hop, hi, i); //e.g., X[,1]=Y -> Y, if output == input dims
+ hi = fuseLeftIndexingChainToAppend(hop, hi, i); //e.g., X[,1]=A; X[,2]=B -> X=cbind(A,B), iff ncol(X)==2 and col1/2 lix
hi = removeUnnecessaryCumulativeOp(hop, hi, i); //e.g., cumsum(X) -> X, if nrow(X)==1;
hi = removeUnnecessaryReorgOperation(hop, hi, i); //e.g., matrix(X) -> X, if output == input dims
hi = removeUnnecessaryOuterProduct(hop, hi, i); //e.g., X*(Y%*%matrix(1,...) -> X*Y, if Y col vector
@@ -305,6 +306,76 @@ public class RewriteAlgebraicSimplificationDynamic extends HopRewriteRule
* @param pos
* @return
*/
+ private Hop fuseLeftIndexingChainToAppend(Hop parent, Hop hi, int pos)
+ {
+ boolean applied = false;
+
+ //pattern1: X[,1]=A; X[,2]=B -> X=cbind(A,B)
+ if( hi instanceof LeftIndexingOp //first lix
+ && HopRewriteUtils.isFullColumnIndexing((LeftIndexingOp)hi)
+ && hi.getInput().get(0) instanceof LeftIndexingOp //second lix
+ && HopRewriteUtils.isFullColumnIndexing((LeftIndexingOp)hi.getInput().get(0))
+ && hi.getInput().get(0).getParent().size()==1 //first lix is single consumer
+ && hi.getInput().get(0).getInput().get(0).getDim2() == 2 ) //two column matrix
+ {
+ Hop input2 = hi.getInput().get(1); //rhs matrix
+ Hop pred2 = hi.getInput().get(4); //cl=cu
+ Hop input1 = hi.getInput().get(0).getInput().get(1); //lhs matrix
+ Hop pred1 = hi.getInput().get(0).getInput().get(4); //cl=cu
+
+ if( pred1 instanceof LiteralOp && HopRewriteUtils.getDoubleValueSafe((LiteralOp)pred1)==1
+ && pred2 instanceof LiteralOp && HopRewriteUtils.getDoubleValueSafe((LiteralOp)pred2)==2
+ && input1.getDataType()==DataType.MATRIX && input2.getDataType()==DataType.MATRIX )
+ {
+ //create new cbind operation and rewrite inputs
+ HopRewriteUtils.removeChildReference(parent, hi);
+ BinaryOp bop = HopRewriteUtils.createBinary(input1, input2, OpOp2.CBIND);
+ HopRewriteUtils.addChildReference(parent, bop, pos);
+
+ hi = bop;
+ applied = true;
+ }
+ }
+
+ //pattern1: X[1,]=A; X[2,]=B -> X=rbind(A,B)
+ if( !applied && hi instanceof LeftIndexingOp //first lix
+ && HopRewriteUtils.isFullRowIndexing((LeftIndexingOp)hi)
+ && hi.getInput().get(0) instanceof LeftIndexingOp //second lix
+ && HopRewriteUtils.isFullRowIndexing((LeftIndexingOp)hi.getInput().get(0))
+ && hi.getInput().get(0).getParent().size()==1 //first lix is single consumer
+ && hi.getInput().get(0).getInput().get(0).getDim1() == 2 ) //two column matrix
+ {
+ Hop input2 = hi.getInput().get(1); //rhs matrix
+ Hop pred2 = hi.getInput().get(2); //rl=ru
+ Hop input1 = hi.getInput().get(0).getInput().get(1); //lhs matrix
+ Hop pred1 = hi.getInput().get(0).getInput().get(2); //rl=ru
+
+ if( pred1 instanceof LiteralOp && HopRewriteUtils.getDoubleValueSafe((LiteralOp)pred1)==1
+ && pred2 instanceof LiteralOp && HopRewriteUtils.getDoubleValueSafe((LiteralOp)pred2)==2
+ && input1.getDataType()==DataType.MATRIX && input2.getDataType()==DataType.MATRIX )
+ {
+ //create new cbind operation and rewrite inputs
+ HopRewriteUtils.removeChildReference(parent, hi);
+ BinaryOp bop = HopRewriteUtils.createBinary(input1, input2, OpOp2.RBIND);
+ HopRewriteUtils.addChildReference(parent, bop, pos);
+
+ hi = bop;
+ applied = true;
+
+ LOG.debug("Applied fuseLeftIndexingChainToAppend2 (line "+hi.getBeginLine()+")");
+ }
+ }
+
+ return hi;
+ }
+
+ /**
+ *
+ * @param parent
+ * @param hi
+ * @param pos
+ * @return
+ */
private Hop removeUnnecessaryCumulativeOp(Hop parent, Hop hi, int pos)
{
if( hi instanceof UnaryOp && ((UnaryOp)hi).isCumulativeUnaryOperation() )