Repository: incubator-systemml Updated Branches: refs/heads/master b3120ce24 -> 640df186a
[SYSTEMML-1418] Additional codegen plan selector: fuse-no-redundancy This patch adds a second codegen plan selection heuristic: fuse_no-redundancy, which creates non-overlapping fused operators, i.e., without any redundant computation. Furthermore, we now also do proper memoization of processed hop nodes in both existing plan selectors to improved optimization time. Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/640df186 Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/640df186 Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/640df186 Branch: refs/heads/master Commit: 640df186afeaf3b52741cef670da7911b9d6d9a5 Parents: b3120ce Author: Matthias Boehm <[email protected]> Authored: Sat Mar 25 22:04:51 2017 -0700 Committer: Matthias Boehm <[email protected]> Committed: Sat Mar 25 22:05:23 2017 -0700 ---------------------------------------------------------------------- .../sysml/hops/codegen/SpoofCompiler.java | 25 ++++- .../hops/codegen/template/CPlanMemoTable.java | 12 +- .../hops/codegen/template/PlanSelection.java | 35 +++++- .../codegen/template/PlanSelectionFuseAll.java | 13 ++- .../template/PlanSelectionFuseNoRedundancy.java | 110 +++++++++++++++++++ 5 files changed, 182 insertions(+), 13 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/640df186/src/main/java/org/apache/sysml/hops/codegen/SpoofCompiler.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/codegen/SpoofCompiler.java b/src/main/java/org/apache/sysml/hops/codegen/SpoofCompiler.java index 17e2fcf..273e790 100644 --- a/src/main/java/org/apache/sysml/hops/codegen/SpoofCompiler.java +++ b/src/main/java/org/apache/sysml/hops/codegen/SpoofCompiler.java @@ -45,6 +45,9 @@ import org.apache.sysml.hops.codegen.template.TemplateBase; import org.apache.sysml.hops.codegen.template.TemplateBase.CloseType; import org.apache.sysml.hops.codegen.template.TemplateBase.TemplateType; import org.apache.sysml.hops.codegen.template.CPlanMemoTable; +import org.apache.sysml.hops.codegen.template.PlanSelection; +import org.apache.sysml.hops.codegen.template.PlanSelectionFuseAll; +import org.apache.sysml.hops.codegen.template.PlanSelectionFuseNoRedundancy; import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry; import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntrySet; import org.apache.sysml.hops.codegen.template.TemplateUtils; @@ -82,10 +85,10 @@ public class SpoofCompiler public static boolean LDEBUG = false; public static final boolean RECOMPILE_CODEGEN = true; public static PlanCache PLAN_CACHE_POLICY = PlanCache.CSLH; - public static final PlanSelection PLAN_SEL_POLICY = PlanSelection.FUSE_ALL; + public static final PlanSelector PLAN_SEL_POLICY = PlanSelector.FUSE_ALL; public static final boolean PRUNE_REDUNDANT_PLANS = true; - public enum PlanSelection { + public enum PlanSelector { FUSE_ALL, //maximal fusion, possible w/ redundant compute FUSE_NO_REDUNDANCY, //fusion without redundant compute FUSE_COST_BASED, //cost-based decision on materialization points @@ -567,4 +570,22 @@ public class SpoofCompiler } return ret; } + + /** + * Factory method for alternative plan selection policies. + * + * @return plan selector + */ + public static PlanSelection createPlanSelector() { + switch( PLAN_SEL_POLICY ) { + case FUSE_ALL: + return new PlanSelectionFuseAll(); + case FUSE_NO_REDUNDANCY: + return new PlanSelectionFuseNoRedundancy(); + case FUSE_COST_BASED: + default: + throw new RuntimeException("Unsupported " + + "plan selector: "+PLAN_SEL_POLICY); + } + } } http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/640df186/src/main/java/org/apache/sysml/hops/codegen/template/CPlanMemoTable.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/CPlanMemoTable.java b/src/main/java/org/apache/sysml/hops/codegen/template/CPlanMemoTable.java index 9a66f09..cbafc2a 100644 --- a/src/main/java/org/apache/sysml/hops/codegen/template/CPlanMemoTable.java +++ b/src/main/java/org/apache/sysml/hops/codegen/template/CPlanMemoTable.java @@ -172,19 +172,13 @@ public class CPlanMemoTable } //core plan selection - switch( SpoofCompiler.PLAN_SEL_POLICY ) { - case FUSE_ALL: - new PlanSelectionFuseAll().selectPlans(this, roots); - break; - case FUSE_NO_REDUNDANCY: - case FUSE_COST_BASED: - throw new RuntimeException("Not implemented yet."); - } + PlanSelection selector = SpoofCompiler.createPlanSelector(); + selector.selectPlans(this, roots); if( SpoofCompiler.LDEBUG ) LOG.info("#2: Memo after plan selection ("+size()+" plans)\n"+this); } - + public List<MemoTableEntry> get(long hopID) { return _plans.get(hopID); } http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/640df186/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelection.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelection.java b/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelection.java index e7bc554..4abe760 100644 --- a/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelection.java +++ b/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelection.java @@ -21,14 +21,18 @@ package org.apache.sysml.hops.codegen.template; import java.util.ArrayList; import java.util.Comparator; +import java.util.HashSet; import org.apache.sysml.hops.Hop; import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry; import org.apache.sysml.hops.codegen.template.TemplateBase.TemplateType; import org.apache.sysml.hops.rewrite.HopRewriteUtils; +import org.apache.sysml.runtime.util.UtilFunctions; public abstract class PlanSelection { + private final HashSet<VisitMark> _visited = new HashSet<VisitMark>(); + /** * Given a HOP DAG G, and a set of partial fusions plans P, find the set of optimal, * non-conflicting fusion plans P' that applied to G minimizes costs C with @@ -54,11 +58,19 @@ public abstract class PlanSelection || (me.type == TemplateType.CellTpl); } + public boolean isVisited(long hopID, TemplateType type) { + return _visited.contains(new VisitMark(hopID, type)); + } + + public void setVisited(long hopID, TemplateType type) { + _visited.add(new VisitMark(hopID, type)); + } + /** * Basic plan comparator to compare memo table entries with regard to * a pre-defined template preference order and the number of references. */ - protected class BasicPlanComparator implements Comparator<MemoTableEntry> { + protected static class BasicPlanComparator implements Comparator<MemoTableEntry> { @Override public int compare(MemoTableEntry o1, MemoTableEntry o2) { //for different types, select preferred type @@ -70,4 +82,25 @@ public abstract class PlanSelection 3-o1.countPlanRefs(), 3-o2.countPlanRefs()); } } + + private static class VisitMark { + private final long _hopID; + private final TemplateType _type; + + public VisitMark(long hopID, TemplateType type) { + _hopID = hopID; + _type = type; + } + @Override + public int hashCode() { + return UtilFunctions.longlongHashCode( + _hopID, (_type!=null)?_type.hashCode():0); + } + @Override + public boolean equals(Object o) { + return (o instanceof VisitMark + && _hopID == ((VisitMark)o)._hopID + && _type == ((VisitMark)o)._type); + } + } } http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/640df186/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseAll.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseAll.java b/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseAll.java index e615f0b..5d8c9ce 100644 --- a/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseAll.java +++ b/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseAll.java @@ -30,7 +30,13 @@ import org.apache.sysml.hops.Hop; import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry; import org.apache.sysml.hops.codegen.template.TemplateBase.TemplateType; - +/** + * This plan selection heuristic aims for maximal fusion, which + * potentially leads to overlapping fused operators and thus, + * redundant computation but with a minimal number of materialized + * intermediate results. + * + */ public class PlanSelectionFuseAll extends PlanSelection { private HashMap<Long, List<MemoTableEntry>> _bestPlans = @@ -49,6 +55,9 @@ public class PlanSelectionFuseAll extends PlanSelection private void rSelectPlans(CPlanMemoTable memo, Hop current, TemplateType currentType) { + if( isVisited(current.getHopID(), currentType) ) + return; + //step 1: prune subsumed plans of same type if( memo.contains(current.getHopID()) ) { HashSet<MemoTableEntry> rmSet = new HashSet<MemoTableEntry>(); @@ -81,5 +90,7 @@ public class PlanSelectionFuseAll extends PlanSelection TemplateType pref = (best!=null && best.isPlanRef(i))? best.type : null; rSelectPlans(memo, current.getInput().get(i), pref); } + + setVisited(current.getHopID(), currentType); } } http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/640df186/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseNoRedundancy.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseNoRedundancy.java b/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseNoRedundancy.java new file mode 100644 index 0000000..71b74b2 --- /dev/null +++ b/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseNoRedundancy.java @@ -0,0 +1,110 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.sysml.hops.codegen.template; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.Map.Entry; +import java.util.HashSet; +import java.util.List; + +import org.apache.sysml.hops.Hop; +import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry; +import org.apache.sysml.hops.codegen.template.TemplateBase.TemplateType; + +/** + * This plan selection heuristic aims for fusion without any redundant + * computation, which, however, potentially leads to more materialized + * intermediates than the fuse all heuristic. + * <p> + * NOTE: This heuristic is essentially the same as FuseAll, except that + * any plans that refer to a hop with multiple consumers are removed in + * a pre-processing step. + * + */ +public class PlanSelectionFuseNoRedundancy extends PlanSelection +{ + private HashMap<Long, List<MemoTableEntry>> _bestPlans = + new HashMap<Long, List<MemoTableEntry>>(); + + @Override + public void selectPlans(CPlanMemoTable memo, ArrayList<Hop> roots) { + //pruning and collection pass + for( Hop hop : roots ) + rSelectPlans(memo, hop, null); + + //take all distinct best plans + for( Entry<Long, List<MemoTableEntry>> e : _bestPlans.entrySet() ) + memo.setDistinct(e.getKey(), e.getValue()); + } + + private void rSelectPlans(CPlanMemoTable memo, Hop current, TemplateType currentType) + { + if( isVisited(current.getHopID(), currentType) ) + return; + + //step 0: remove plans that refer to a common partial plan + if( memo.contains(current.getHopID()) ) { + HashSet<MemoTableEntry> rmSet = new HashSet<MemoTableEntry>(); + List<MemoTableEntry> hopP = memo.get(current.getHopID()); + for( MemoTableEntry e1 : hopP ) + for( int i=0; i<3; i++ ) + if( e1.isPlanRef(i) && current.getInput().get(i).getParent().size()>1 ) + rmSet.add(e1); //remove references to hops w/ multiple consumers + memo.remove(current, rmSet); + } + + //step 1: prune subsumed plans of same type + if( memo.contains(current.getHopID()) ) { + HashSet<MemoTableEntry> rmSet = new HashSet<MemoTableEntry>(); + List<MemoTableEntry> hopP = memo.get(current.getHopID()); + for( MemoTableEntry e1 : hopP ) + for( MemoTableEntry e2 : hopP ) + if( e1 != e2 && e1.subsumes(e2) ) + rmSet.add(e2); + memo.remove(current, rmSet); + } + + //step 2: select plan for current path + MemoTableEntry best = null; + if( memo.contains(current.getHopID()) ) { + if( currentType == null ) { + best = memo.get(current.getHopID()).stream() + .filter(p -> isValid(p, current)) + .min(new BasicPlanComparator()).orElse(null); + } + else { + + best = memo.get(current.getHopID()).stream() + .filter(p -> p.type==currentType || p.type==TemplateType.CellTpl) + .min(Comparator.comparing(p -> 3-p.countPlanRefs())).orElse(null); + } + } + + //step 3: recursively process children + for( int i=0; i< current.getInput().size(); i++ ) { + TemplateType pref = (best!=null && best.isPlanRef(i))? best.type : null; + rSelectPlans(memo, current.getInput().get(i), pref); + } + + setVisited(current.getHopID(), currentType); + } +}
