Repository: incubator-systemml
Updated Branches:
  refs/heads/master c3c6bccf5 -> 1729d13ae


[SYSTEMML-945] New IPA pass 'move checkpoint after update' (avoid cache)

Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: 
http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/1729d13a
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/1729d13a
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/1729d13a

Branch: refs/heads/master
Commit: 1729d13ae47da8f3d09f433e007a2053c94cf847
Parents: c3c6bcc
Author: Matthias Boehm <mbo...@us.ibm.com>
Authored: Mon Sep 19 19:00:46 2016 -0700
Committer: Matthias Boehm <mbo...@us.ibm.com>
Committed: Tue Sep 20 11:40:10 2016 -0700

----------------------------------------------------------------------
 .../sysml/hops/ipa/InterProceduralAnalysis.java | 85 +++++++++++++++++++-
 1 file changed, 82 insertions(+), 3 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/1729d13a/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java
----------------------------------------------------------------------
diff --git 
a/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java 
b/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java
index 849d8ff..11ee646 100644
--- a/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java
+++ b/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java
@@ -203,7 +203,11 @@ public class InterProceduralAnalysis
                if( REMOVE_UNNECESSARY_CHECKPOINTS 
                        && OptimizerUtils.isSparkExecutionMode() )
                {
+                       //remove unnecessary checkpoint before update 
                        removeUnnecessaryCheckpoints(dmlp);
+                       
+                       //move necessary checkpoint after update
+                       moveCheckpointAfterUpdate(dmlp);
                }
                
                //step 7: remove constant binary ops
@@ -1152,9 +1156,8 @@ public class InterProceduralAnalysis
                                for( String cand : cands2 )
                                        if( 
sb.variablesUpdated().containsVariable(cand) && sb.get_hops() != null) 
                                        {
-                                               ArrayList<Hop> hops = 
sb.get_hops();
-                                               Hop.resetVisitStatus(hops);
-                                               for( Hop root : hops )
+                                               
Hop.resetVisitStatus(sb.get_hops());
+                                               for( Hop root : sb.get_hops() )
                                                        if( 
root.getName().equals(cand) &&
                                                                
!HopRewriteUtils.rHasSimpleReadChain(root, cand) ) {
                                                                
chkpointCand.remove(cand);
@@ -1173,6 +1176,82 @@ public class InterProceduralAnalysis
                        
                }
        }
+
+       /**
+        * 
+        * @param dmlp
+        * @throws HopsException
+        */
+       private void moveCheckpointAfterUpdate(DMLProgram dmlp) 
+               throws HopsException
+       {
+               //approach: scan over top-level program (guaranteed to be 
unconditional),
+               //collect checkpoints; determine if used before update; move 
first checkpoint
+               //after update if not used before update (best effort move 
which often avoids
+               //the second checkpoint on loops even though used in between)
+               
+               HashMap<String, Hop> chkpointCand = new HashMap<String, Hop>();
+               
+               for( StatementBlock sb : dmlp.getStatementBlocks() ) 
+               {
+                       //prune candidates (used before updated)
+                       Set<String> cands = new 
HashSet<String>(chkpointCand.keySet());
+                       for( String cand : cands )
+                               if( sb.variablesRead().containsVariable(cand) 
+                                       && 
!sb.variablesUpdated().containsVariable(cand) ) 
+                               {       
+                                       //note: variableRead might include 
false positives due to meta 
+                                       //data operations like nrow(X) or 
operations removed by rewrites 
+                                       //double check hops on basic blocks; 
otherwise worst-case
+                                       boolean skipRemove = false;
+                                       if( sb.get_hops() !=null ) {
+                                               
Hop.resetVisitStatus(sb.get_hops());
+                                               skipRemove = true;
+                                               for( Hop root : sb.get_hops() )
+                                                       skipRemove &= 
!HopRewriteUtils.rContainsRead(root, cand, false);
+                                       }                                       
+                                       if( !skipRemove )
+                                               chkpointCand.remove(cand);
+                               }
+                       
+                       //prune candidates (updated in conditional control flow)
+                       Set<String> cands2 = new 
HashSet<String>(chkpointCand.keySet());
+                       if( sb instanceof IfStatementBlock || sb instanceof 
WhileStatementBlock 
+                               || sb instanceof ForStatementBlock )
+                       {
+                               for( String cand : cands2 )
+                                       if( 
sb.variablesUpdated().containsVariable(cand) ) {
+                                               chkpointCand.remove(cand);
+                                       }
+                       }
+                       //move checkpoint after update with simple read chain 
+                       //(note: right now this only applies if the checkpoints 
comes from a previous
+                       //statement block, within-dag checkpoints should be 
handled during injection)
+                       else
+                       {
+                               for( String cand : cands2 )
+                                       if( 
sb.variablesUpdated().containsVariable(cand) && sb.get_hops() != null) {
+                                               
Hop.resetVisitStatus(sb.get_hops());
+                                               for( Hop root : sb.get_hops() )
+                                                       if( 
root.getName().equals(cand) ) {
+                                                               if( 
HopRewriteUtils.rHasSimpleReadChain(root, cand) ) {
+                                                                       
chkpointCand.get(cand).setRequiresCheckpoint(false);
+                                                                       
root.getInput().get(0).setRequiresCheckpoint(true);
+                                                                       
chkpointCand.put(cand, root.getInput().get(0));
+                                                               }
+                                                               else
+                                                                       
chkpointCand.remove(cand);              
+                                                       }
+                                       }       
+                       }
+               
+                       //collect checkpoints
+                       ArrayList<Hop> tmp = collectCheckpoints(sb.get_hops());
+                       for( Hop chkpoint : tmp ) {
+                               chkpointCand.put(chkpoint.getName(), chkpoint);
+                       }
+               }
+       }
        
        /**
         * 

Reply via email to