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/11/23 04:31:29 UTC
[2/2] systemml git commit: [SYSTEMML-2025] Improved codegen optimizer
(search space layout)
[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 <mb...@gmail.com>
Authored: Wed Nov 22 15:37:48 2017 -0800
Committer: Matthias Boehm <mb...@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;