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 2017/03/03 20:02:53 UTC
[2/2] incubator-systemml git commit: [SYSTEMML-1369] New loop
vectorization rewrite for indexed copies
[SYSTEMML-1369] New loop vectorization rewrite for indexed copies
As explained in https://issues.apache.org/jira/browse/SYSTEMML-1369,
this patch introduces an auto loop vectorization rewrite for indexed
copies. For example, we now rewrite the following loop
parfor (i in 1:ncol(labels))
topics[id, i] = labels[1, i];
to a simple left indexing of topics[id, 1:ncol(labels)] = labels[1,
1:ncol(labels)]. This applies to for and parfor loops. Furthermore, this
patch also fixes size update issues of the existing loop vectorization
rewrites vectorizeElementwiseBinary and vectorizeElementwiseUnary.
On a scenario of an 1K x 1K dense topics matrix, an outer loop over id,
and regular for loops, the runtime improved from 33s (3438s without
update-in-place) to 0.2s. Note that on large out-of-core matrices, the
improvements are even larger because we cannot apply update-in-place
there.
Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/ed3a1588
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/ed3a1588
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/ed3a1588
Branch: refs/heads/master
Commit: ed3a1588287e22ab3e8a3e9e971b505a9157ba59
Parents: cd6685a
Author: Matthias Boehm <mb...@gmail.com>
Authored: Thu Mar 2 23:01:28 2017 -0800
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Thu Mar 2 23:01:28 2017 -0800
----------------------------------------------------------------------
.../rewrite/RewriteForLoopVectorization.java | 177 ++++++++++++-------
1 file changed, 114 insertions(+), 63 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/ed3a1588/src/main/java/org/apache/sysml/hops/rewrite/RewriteForLoopVectorization.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/rewrite/RewriteForLoopVectorization.java b/src/main/java/org/apache/sysml/hops/rewrite/RewriteForLoopVectorization.java
index 991dedd..273436e 100644
--- a/src/main/java/org/apache/sysml/hops/rewrite/RewriteForLoopVectorization.java
+++ b/src/main/java/org/apache/sysml/hops/rewrite/RewriteForLoopVectorization.java
@@ -76,10 +76,20 @@ public class RewriteForLoopVectorization extends StatementBlockRewriteRule
|| csb instanceof IfStatementBlock
|| csb instanceof ForStatementBlock ) )
{
- //auto vectorization pattern
- sb = vectorizeScalarAggregate(sb, csb, from, to, incr, iterVar); //e.g., for(i){s = s + as.scalar(X[i,2])}
+ //AUTO VECTORIZATION PATTERNS
+ //Note: unnecessary row or column indexing then later removed via hop rewrites
+
+ //e.g., for(i in a:b){s = s + as.scalar(X[i,2])} -> s = sum(X[a:b,2])
+ sb = vectorizeScalarAggregate(sb, csb, from, to, incr, iterVar);
+
+ //e.g., for(i in a:b){X[i,2] = Y[i,1] + Z[i,3]} -> X[a:b,2] = Y[a:b,1] + Z[a:b,3];
sb = vectorizeElementwiseBinary(sb, csb, from, to, incr, iterVar);
+
+ //e.g., for(i in a:b){X[i,2] = abs(Y[i,1])} -> X[a:b,2] = abs(Y[a:b,1]);
sb = vectorizeElementwiseUnary(sb, csb, from, to, incr, iterVar);
+
+ //e.g., for(i in a:b){X[7,i] = Y[1,i]} -> X[7,a:b] = Y[1,a:b];
+ sb = vectorizeIndexedCopy(sb, csb, from, to, incr, iterVar);
}
}
}
@@ -91,19 +101,6 @@ public class RewriteForLoopVectorization extends StatementBlockRewriteRule
return ret;
}
- /**
- * Note: unnecessary row or column indexing then later removed via
- * dynamic rewrites
- *
- * @param sb statement block?
- * @param csb statement boock?
- * @param from high-level operator?
- * @param to high-level operator?
- * @param increment high-level operator?
- * @param itervar ?
- * @return statement block
- * @throws HopsException if HopsException occurs
- */
private StatementBlock vectorizeScalarAggregate( StatementBlock sb, StatementBlock csb, Hop from, Hop to, Hop increment, String itervar )
throws HopsException
{
@@ -206,19 +203,6 @@ public class RewriteForLoopVectorization extends StatementBlockRewriteRule
return ret;
}
- /**
- * Note: unnecessary row or column indexing then later removed via
- * dynamic rewrites
- *
- * @param sb ?
- * @param csb ?
- * @param from ?
- * @param to ?
- * @param increment ?
- * @param itervar ?
- * @return statement block
- * @throws HopsException if HopsException occurs
- */
private StatementBlock vectorizeElementwiseBinary( StatementBlock sb, StatementBlock csb, Hop from, Hop to, Hop increment, String itervar )
throws HopsException
{
@@ -291,8 +275,9 @@ public class RewriteForLoopVectorization extends StatementBlockRewriteRule
HopRewriteUtils.replaceChildReference(rix0, rix0.getInput().get(index2-1), to, index2-1);
HopRewriteUtils.replaceChildReference(rix1, rix1.getInput().get(index1-1), from, index1-1);
HopRewriteUtils.replaceChildReference(rix1, rix1.getInput().get(index2-1), to, index2-1);
+ updateLeftAndRightIndexingSizes(rowIx, lix, rix0, rix1);
bop.refreshSizeInformation();
- lix.refreshSizeInformation();
+ lix.refreshSizeInformation(); //after bop update
ret = csb;
//ret.liveIn().removeVariable(itervar);
@@ -302,19 +287,6 @@ public class RewriteForLoopVectorization extends StatementBlockRewriteRule
return ret;
}
- /**
- * Note: unnecessary row or column indexing then later removed via
- * dynamic rewrites
- *
- * @param sb ?
- * @param csb ?
- * @param from ?
- * @param to ?
- * @param increment ?
- * @param itervar ?
- * @return statement block
- * @throws HopsException if HopsException occurs
- */
private StatementBlock vectorizeElementwiseUnary( StatementBlock sb, StatementBlock csb, Hop from, Hop to, Hop increment, String itervar )
throws HopsException
{
@@ -342,30 +314,16 @@ public class RewriteForLoopVectorization extends StatementBlockRewriteRule
&& lixrhs.getInput().get(0) instanceof IndexingOp
&& lixrhs.getInput().get(0).getInput().get(0) instanceof DataOp )
{
- IndexingOp rix = (IndexingOp) lixrhs.getInput().get(0);
- //check for rowwise
- if( lix.getRowLowerEqualsUpper() && rix.getRowLowerEqualsUpper()
- && lix.getInput().get(2).getName().equals(itervar)
- && rix.getInput().get(1).getName().equals(itervar) )
- {
- apply = true;
- rowIx = true;
- }
- //check for colwise
- if( lix.getColLowerEqualsUpper() && rix.getColLowerEqualsUpper()
- && lix.getInput().get(4).getName().equals(itervar)
- && rix.getInput().get(3).getName().equals(itervar) )
- {
- apply = true;
- rowIx = false;
- }
+ boolean[] tmp = checkLeftAndRightIndexing(lix,
+ (IndexingOp) lixrhs.getInput().get(0), itervar);
+ apply = tmp[0];
+ rowIx = tmp[1];
}
}
}
//apply rewrite if possible
- if( apply )
- {
+ if( apply ) {
Hop root = csb.get_hops().get(0);
LeftIndexingOp lix = (LeftIndexingOp) root.getInput().get(0);
UnaryOp uop = (UnaryOp) lix.getInput().get(1);
@@ -378,14 +336,107 @@ public class RewriteForLoopVectorization extends StatementBlockRewriteRule
//modify right indexing
HopRewriteUtils.replaceChildReference(rix, rix.getInput().get(index1-1), from, index1-1);
HopRewriteUtils.replaceChildReference(rix, rix.getInput().get(index2-1), to, index2-1);
+ updateLeftAndRightIndexingSizes(rowIx, lix, rix);
uop.refreshSizeInformation();
- lix.refreshSizeInformation();
+ lix.refreshSizeInformation(); //after uop update
ret = csb;
- //ret.liveIn().removeVariable(itervar);
LOG.debug("Applied vectorizeElementwiseUnaryForLoop.");
}
return ret;
}
+
+ private StatementBlock vectorizeIndexedCopy( StatementBlock sb, StatementBlock csb, Hop from, Hop to, Hop increment, String itervar )
+ throws HopsException
+ {
+ StatementBlock ret = sb;
+
+ //check supported increment values
+ if( !(increment instanceof LiteralOp && ((LiteralOp)increment).getDoubleValue()==1.0) ) {
+ return ret;
+ }
+
+ //check for applicability
+ boolean apply = false;
+ boolean rowIx = false; //row or col
+ if( csb.get_hops()!=null && csb.get_hops().size()==1 )
+ {
+ Hop root = csb.get_hops().get(0);
+
+ if( root.getDataType()==DataType.MATRIX && root.getInput().get(0) instanceof LeftIndexingOp )
+ {
+ LeftIndexingOp lix = (LeftIndexingOp) root.getInput().get(0);
+ Hop lixlhs = lix.getInput().get(0);
+ Hop lixrhs = lix.getInput().get(1);
+
+ if( lixlhs instanceof DataOp && lixrhs instanceof IndexingOp
+ && lixrhs.getInput().get(0) instanceof DataOp )
+ {
+ boolean[] tmp = checkLeftAndRightIndexing(lix, (IndexingOp)lixrhs, itervar);
+ apply = tmp[0];
+ rowIx = tmp[1];
+ }
+ }
+ }
+
+ //apply rewrite if possible
+ if( apply ) {
+ Hop root = csb.get_hops().get(0);
+ LeftIndexingOp lix = (LeftIndexingOp) root.getInput().get(0);
+ IndexingOp rix = (IndexingOp) lix.getInput().get(1);
+ int index1 = rowIx ? 2 : 4;
+ int index2 = rowIx ? 3 : 5;
+ //modify left indexing bounds
+ HopRewriteUtils.replaceChildReference(lix, lix.getInput().get(index1), from, index1);
+ HopRewriteUtils.replaceChildReference(lix, lix.getInput().get(index2), to, index2);
+ //modify right indexing
+ HopRewriteUtils.replaceChildReference(rix, rix.getInput().get(index1-1), from, index1-1);
+ HopRewriteUtils.replaceChildReference(rix, rix.getInput().get(index2-1), to, index2-1);
+ updateLeftAndRightIndexingSizes(rowIx, lix, rix);
+
+ ret = csb;
+ LOG.debug("Applied vectorizeIndexedCopy.");
+ }
+
+ return ret;
+ }
+
+ private static boolean[] checkLeftAndRightIndexing(LeftIndexingOp lix, IndexingOp rix, String itervar) {
+ boolean[] ret = new boolean[2]; //apply, rowIx
+
+ //check for rowwise
+ if( lix.getRowLowerEqualsUpper() && rix.getRowLowerEqualsUpper()
+ && lix.getInput().get(2).getName().equals(itervar)
+ && rix.getInput().get(1).getName().equals(itervar) ) {
+ ret[0] = true;
+ ret[1] = true;
+ }
+ //check for colwise
+ if( lix.getColLowerEqualsUpper() && rix.getColLowerEqualsUpper()
+ && lix.getInput().get(4).getName().equals(itervar)
+ && rix.getInput().get(3).getName().equals(itervar) ) {
+ ret[0] = true;
+ ret[1] = false;
+ }
+
+ return ret;
+ }
+
+ private static void updateLeftAndRightIndexingSizes(boolean rowIx, LeftIndexingOp lix, IndexingOp... rix) {
+ //unset special flags
+ if( rowIx ) {
+ lix.setRowLowerEqualsUpper(false);
+ for( IndexingOp rixi : rix )
+ rixi.setRowLowerEqualsUpper(false);
+ }
+ else {
+ lix.setColLowerEqualsUpper(false);
+ for( IndexingOp rixi : rix )
+ rixi.setColLowerEqualsUpper(false);
+ }
+ for( IndexingOp rixi : rix )
+ rixi.refreshSizeInformation();
+ lix.refreshSizeInformation();
+ }
}