[SYSTEMML-2025] Improved codegen optimizer (search space layout) This patch makes a minor improvement to the codegen optimizer. So far we linearized the search space by sorting cutsets by their scores and appending all other interesting points. Now, we sort the remaining interesting points decreasing according to their size, which can improve the pruning efficiency by skipping larger sub spaces.
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/723acfc0 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/723acfc0 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/723acfc0 Branch: refs/heads/master Commit: 723acfc09da95f9a2d490b4c48452799383e54fc Parents: 38162d2 Author: Matthias Boehm <mboe...@gmail.com> Authored: Wed Nov 22 15:37:48 2017 -0800 Committer: Matthias Boehm <mboe...@gmail.com> Committed: Wed Nov 22 20:32:05 2017 -0800 ---------------------------------------------------------------------- .../hops/codegen/opt/ReachabilityGraph.java | 24 ++++++++++++++++---- 1 file changed, 20 insertions(+), 4 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/723acfc0/src/main/java/org/apache/sysml/hops/codegen/opt/ReachabilityGraph.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/codegen/opt/ReachabilityGraph.java b/src/main/java/org/apache/sysml/hops/codegen/opt/ReachabilityGraph.java index 90079a3..c6ca0a9 100644 --- a/src/main/java/org/apache/sysml/hops/codegen/opt/ReachabilityGraph.java +++ b/src/main/java/org/apache/sysml/hops/codegen/opt/ReachabilityGraph.java @@ -69,7 +69,9 @@ public class ReachabilityGraph //short-cut for partitions without cutsets if( tmpCS.isEmpty() ) { _cutSets = new CutSet[0]; - _searchSpace = part.getMatPointsExt(); + //sort materialization points in decreasing order of their sizes + //which can improve the pruning efficiency by skipping larger sub-spaces. + _searchSpace = sortBySize(part.getMatPointsExt(), memo, false); return; } @@ -120,7 +122,7 @@ public class ReachabilityGraph .map(p -> p.getLeft()).toArray(CutSet[]::new); //created sorted order of materialization points - //(cut sets in predetermined order, all other points appended) + //(cut sets in predetermined order, other points sorted by size) HashMap<InterestingPoint, Integer> probe = new HashMap<>(); ArrayList<InterestingPoint> lsearchSpace = new ArrayList<>(); for( CutSet cs : _cutSets ) { @@ -128,7 +130,9 @@ public class ReachabilityGraph for( InterestingPoint p : cs.cut ) probe.put(p, probe.size()); } - for( InterestingPoint p : part.getMatPointsExt() ) + //sort materialization points in decreasing order of their sizes + //which can improve the pruning efficiency by skipping larger sub-spaces. + for( InterestingPoint p : sortBySize(part.getMatPointsExt(), memo, false) ) if( !probe.containsKey(p) ) { lsearchSpace.add(p); probe.put(p, probe.size()); @@ -258,7 +262,19 @@ public class ReachabilityGraph return cutSets; } - + + private InterestingPoint[] sortBySize(InterestingPoint[] points, CPlanMemoTable memo, boolean asc) { + return Arrays.stream(points) + .sorted(Comparator.comparing(p -> (asc ? 1 : -1) * + getSize(memo.getHopRefs().get(p.getToHopID())))) + .toArray(InterestingPoint[]::new); + } + + private static long getSize(Hop hop) { + return Math.max(hop.getDim1(),1) + * Math.max(hop.getDim2(),1); + } + public static class SubProblem { public int offset; public int[] freePos;
