Repository: systemml Updated Branches: refs/heads/master 139ddfeed -> e6dfd89b1
[SYSTEMML-1908] Fix non-deterministic number of fused operators, GLM This patch fixes special cases with code generation, where deterministic algorithms such as GLM showed a non-deterministic number of compiled fused operators. So far, we order the inputs of fused operators by shape (matrices, vectors, scalars) and subsequently by their sparsity. In case of partial unknowns this can lead to non-deterministic behavior due to violated transitive comparisons results. We now only sort safe comparison scenarios by their sparsity and fall back to a comparison by hop id (within shape categories) otherwise. This fixes the non-deterministic behavior and increases operator reuse, which in turn reduces java and JIT compilation overheads. For example, on GLM, the number of compiled operators reduced from 69-72 to 53, without affected the resulting plan. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/e6dfd89b Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/e6dfd89b Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/e6dfd89b Branch: refs/heads/master Commit: e6dfd89b1156448e4862ca4ed68b0a0790ffae39 Parents: 139ddfe Author: Matthias Boehm <mboe...@gmail.com> Authored: Fri Sep 15 00:12:01 2017 -0700 Committer: Matthias Boehm <mboe...@gmail.com> Committed: Fri Sep 15 00:12:01 2017 -0700 ---------------------------------------------------------------------- src/main/java/org/apache/sysml/hops/Hop.java | 12 ++++++++++++ .../sysml/hops/codegen/template/TemplateCell.java | 17 ++++++++++------- .../sysml/hops/codegen/template/TemplateRow.java | 8 ++++---- 3 files changed, 26 insertions(+), 11 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/e6dfd89b/src/main/java/org/apache/sysml/hops/Hop.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/Hop.java b/src/main/java/org/apache/sysml/hops/Hop.java index 7495d4f..7ccfe2e 100644 --- a/src/main/java/org/apache/sysml/hops/Hop.java +++ b/src/main/java/org/apache/sysml/hops/Hop.java @@ -983,6 +983,10 @@ public abstract class Hop implements ParseInfo _dim2 = dim2; } + public long getLength() { + return _dim1 * _dim2; + } + public double getSparsity() { return OptimizerUtils.getSparsity(_dim1, _dim2, _nnz); } @@ -1013,6 +1017,14 @@ public abstract class Hop implements ParseInfo public void setDataType( DataType dt ) { _dataType = dt; } + + public boolean isScalar() { + return _dataType.isScalar(); + } + + public boolean isMatrix() { + return _dataType.isMatrix(); + } public void setVisited() { setVisited(true); http://git-wip-us.apache.org/repos/asf/systemml/blob/e6dfd89b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateCell.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateCell.java b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateCell.java index 9d0c7b5..b120bf5 100644 --- a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateCell.java +++ b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateCell.java @@ -355,17 +355,20 @@ public class TemplateCell extends TemplateBase @Override public int compare(Hop h1, Hop h2) { - long ncells1 = h1.getDataType()==DataType.SCALAR ? Long.MIN_VALUE : - h1.dimsKnown() ? h1.getDim1()*h1.getDim2() : Long.MAX_VALUE; - long ncells2 = h2.getDataType()==DataType.SCALAR ? Long.MIN_VALUE : - h2.dimsKnown() ? h2.getDim1()*h2.getDim2() : Long.MAX_VALUE; + long ncells1 = h1.isScalar() ? Long.MIN_VALUE : + h1.dimsKnown() ? h1.getLength() : Long.MAX_VALUE; + long ncells2 = h2.isScalar() ? Long.MIN_VALUE : + h2.dimsKnown() ? h2.getLength() : Long.MAX_VALUE; if( ncells1 > ncells2 || h1 == _driver ) return -1; else if( ncells1 < ncells2 || h2 == _driver) return 1; - return Long.compare( - h1.dimsKnown(true) ? h1.getNnz() : ncells1, - h2.dimsKnown(true) ? h2.getNnz() : ncells2); + if( h1.isScalar() && h2.isScalar() ) + return Long.compare(h1.getHopID(), h2.getHopID()); + return (h1.dimsKnown(true) && h2.dimsKnown(true) && h1.getNnz() != h2.getNnz() + && HopRewriteUtils.isSparse(h1) || HopRewriteUtils.isSparse(h1)) ? + Long.compare(h1.getNnz(), h2.getNnz()) : + Long.compare(h1.getHopID(), h2.getHopID()); } } } http://git-wip-us.apache.org/repos/asf/systemml/blob/e6dfd89b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateRow.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateRow.java b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateRow.java index 864dd33..1db01e4 100644 --- a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateRow.java +++ b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateRow.java @@ -433,12 +433,12 @@ public class TemplateRow extends TemplateBase @Override public int compare(Hop h1, Hop h2) { - long ncells1 = h1.getDataType()==DataType.SCALAR ? Long.MIN_VALUE : + long ncells1 = h1.isScalar() ? Long.MIN_VALUE : (h1==_X) ? Long.MAX_VALUE : (h1==_B1) ? Long.MAX_VALUE-1 : - h1.dimsKnown() ? h1.getDim1()*h1.getDim2() : Long.MAX_VALUE-2; - long ncells2 = h2.getDataType()==DataType.SCALAR ? Long.MIN_VALUE : + h1.dimsKnown() ? h1.getLength() : Long.MAX_VALUE-2; + long ncells2 = h2.isScalar() ? Long.MIN_VALUE : (h2==_X) ? Long.MAX_VALUE : (h2==_B1) ? Long.MAX_VALUE-1 : - h2.dimsKnown() ? h2.getDim1()*h2.getDim2() : Long.MAX_VALUE-2; + h2.dimsKnown() ? h2.getLength() : Long.MAX_VALUE-2; return (ncells1 > ncells2) ? -1 : (ncells1 < ncells2) ? 1 : 0; } }