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/18 06:12:43 UTC
[1/2] systemml git commit: [SYSTEMML-2021] Fix robustness codegen
optimizer (opening heuristic)
Repository: systemml
Updated Branches:
refs/heads/master db3d54c1c -> d0ef4263e
[SYSTEMML-2021] Fix robustness codegen optimizer (opening heuristic)
This patch fixes the robustness of the codegen plan enumeration, which
got stuck for the perftest stratstats due to a large fusion partition
with 38 interesting points and very specific cost characteristics that
rendered the open heuristic fuse-all ineffective. We now run both
heuristics (fused-all and fuse-no-redundancy) as a consolidated opening
heuristics to quickly obtain a good lower bound. Furthermore, we also
avoid enumerating large partitions (w/ >20 interesting points) if the
opening heuristic already achieved costs that are in an epsilon
environment (1%) of the minimal static costs of this partition.
Together, these modifications greatly improve the robustness of the
codegen optimizer without missing any meaningful plans.
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/691c8f71
Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/691c8f71
Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/691c8f71
Branch: refs/heads/master
Commit: 691c8f71062cde4408902178baabba67f2008c44
Parents: db3d54c
Author: Matthias Boehm <mb...@gmail.com>
Authored: Fri Nov 17 21:32:25 2017 -0800
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Fri Nov 17 21:32:25 2017 -0800
----------------------------------------------------------------------
.../opt/PlanSelectionFuseCostBasedV2.java | 38 +++++++++++++++-----
1 file changed, 30 insertions(+), 8 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/systemml/blob/691c8f71/src/main/java/org/apache/sysml/hops/codegen/opt/PlanSelectionFuseCostBasedV2.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/opt/PlanSelectionFuseCostBasedV2.java b/src/main/java/org/apache/sysml/hops/codegen/opt/PlanSelectionFuseCostBasedV2.java
index 80013c5..721ffdd 100644
--- a/src/main/java/org/apache/sysml/hops/codegen/opt/PlanSelectionFuseCostBasedV2.java
+++ b/src/main/java/org/apache/sysml/hops/codegen/opt/PlanSelectionFuseCostBasedV2.java
@@ -96,6 +96,12 @@ public class PlanSelectionFuseCostBasedV2 extends PlanSelection
//sparsity estimate for unknown sparsity to prefer sparse-safe fusion plans
private static final double SPARSE_SAFE_SPARSITY_EST = 0.1;
+ //after evaluating the costs of the opening heuristics fuse-all and fuse-no-redundancy,
+ //remaining candidate plans of large partitions (w/ >= COST_MIN_EPS_NUM_POINTS) are
+ //only evaluated if the current costs are > (1+COST_MIN_EPS) * static (i.e., minimal) costs.
+ public static final double COST_MIN_EPS = 0.01; //1%
+ public static final double COST_MIN_EPS_NUM_POINTS = 20; //2^20 = 1M plans
+
//optimizer configuration
public static boolean COST_PRUNING = true;
public static boolean STRUCTURAL_PRUNING = true;
@@ -161,7 +167,7 @@ public class PlanSelectionFuseCostBasedV2 extends PlanSelection
for( Long hopID : part.getPartition() )
memo.pruneRedundant(hopID, true, part.getMatPointsExt());
}
-
+
//enumerate and cost plans, returns optional plan
boolean[] bestPlan = enumPlans(memo, part,
costs, rgraph, part.getMatPointsExt(), 0);
@@ -205,14 +211,28 @@ public class PlanSelectionFuseCostBasedV2 extends PlanSelection
//scan linearized search space, w/ skips for branch and bound pruning
//and structural pruning (where we solve conditionally independent problems)
//bestC is monotonically non-increasing and serves as the upper bound
- final long len = UtilFunctions.pow(2, matPoints.length-off);
- boolean[] bestPlan = null;
- double bestC = Double.MAX_VALUE;
+ final int Mlen = matPoints.length-off;
+ final long len = UtilFunctions.pow(2, Mlen);
long numEvalPlans = 0, numEvalPartPlans = 0;
- for( long i=0; i<len; i++ ) {
+ //evaluate heuristics fuse-all and fuse-no-redundancy to quickly obtain a good lower bound
+ final boolean[] plan0 = createAssignment(Mlen, off, 0); // fuse-all
+ final boolean[] planN = createAssignment(Mlen, off, len-1); //fuse-no-redundancy
+ final double C0 = getPlanCost(memo, part, matPoints, plan0, costs._computeCosts, Double.MAX_VALUE);
+ final double CN = getPlanCost(memo, part, matPoints, planN, costs._computeCosts, Double.MAX_VALUE);
+ boolean[] bestPlan = (C0 <= CN) ? plan0 : planN;
+ double bestC = Math.min(C0, CN);
+ final boolean evalRemain = (Mlen < COST_MIN_EPS_NUM_POINTS
+ || bestC > (1+COST_MIN_EPS) * costs.getMinCosts());
+ if( LOG.isTraceEnabled() )
+ LOG.trace("Enum opening: " + Arrays.toString(bestPlan) + " -> " + bestC);
+ if( !evalRemain )
+ LOG.warn("Skip enum for |M|="+Mlen+", C="+bestC+", Cmin="+costs.getMinCosts());
+
+ //evaluate remaining plans, except already evaluated heuristics
+ for( long i=1; i<len-1 & evalRemain; i++ ) {
//construct assignment
- boolean[] plan = createAssignment(matPoints.length-off, off, i);
+ boolean[] plan = createAssignment(Mlen, off, i);
long pskip = 0; //skip after costing
//skip plans with structural pruning
@@ -281,7 +301,7 @@ public class PlanSelectionFuseCostBasedV2 extends PlanSelection
LOG.trace("Enum: Optimal plan: "+Arrays.toString(bestPlan));
//copy best plan w/o fixed offset plan
- return (bestPlan==null) ? new boolean[matPoints.length-off] :
+ return (bestPlan==null) ? new boolean[Mlen] :
Arrays.copyOfRange(bestPlan, off, bestPlan.length);
}
@@ -1100,13 +1120,15 @@ public class PlanSelectionFuseCostBasedV2 extends PlanSelection
public final double _compute;
public final double _read;
public final double _write;
-
public StaticCosts(HashMap<Long,Double> allComputeCosts, double computeCost, double readCost, double writeCost) {
_computeCosts = allComputeCosts;
_compute = computeCost;
_read = readCost;
_write = writeCost;
}
+ public double getMinCosts() {
+ return Math.max(_read, _compute) + _write;
+ }
}
private static class AggregateInfo {
[2/2] systemml git commit: tweak
Posted by mb...@apache.org.
tweak
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/d0ef4263
Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/d0ef4263
Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/d0ef4263
Branch: refs/heads/master
Commit: d0ef4263e92de60cc18c54213c758c8e7bebb8e1
Parents: 691c8f7
Author: Matthias Boehm <mb...@gmail.com>
Authored: Fri Nov 17 22:13:21 2017 -0800
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Fri Nov 17 22:13:21 2017 -0800
----------------------------------------------------------------------
.../sysml/hops/codegen/opt/PlanSelectionFuseCostBasedV2.java | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/systemml/blob/d0ef4263/src/main/java/org/apache/sysml/hops/codegen/opt/PlanSelectionFuseCostBasedV2.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/opt/PlanSelectionFuseCostBasedV2.java b/src/main/java/org/apache/sysml/hops/codegen/opt/PlanSelectionFuseCostBasedV2.java
index 721ffdd..08d5e44 100644
--- a/src/main/java/org/apache/sysml/hops/codegen/opt/PlanSelectionFuseCostBasedV2.java
+++ b/src/main/java/org/apache/sysml/hops/codegen/opt/PlanSelectionFuseCostBasedV2.java
@@ -223,7 +223,7 @@ public class PlanSelectionFuseCostBasedV2 extends PlanSelection
boolean[] bestPlan = (C0 <= CN) ? plan0 : planN;
double bestC = Math.min(C0, CN);
final boolean evalRemain = (Mlen < COST_MIN_EPS_NUM_POINTS
- || bestC > (1+COST_MIN_EPS) * costs.getMinCosts());
+ || !COST_PRUNING || bestC > (1+COST_MIN_EPS) * costs.getMinCosts());
if( LOG.isTraceEnabled() )
LOG.trace("Enum opening: " + Arrays.toString(bestPlan) + " -> " + bestC);
if( !evalRemain )