Repository: incubator-systemml Updated Branches: refs/heads/master cd5499c54 -> 4c74a3434
[SYSTEMML-1545] Fix memory estimates leftindexing w/ empty inputs For a detailed problem description see https://issues.apache.org/jira/browse/SYSTEMML-1545 This patch overcomes the incorrect memory estimates by only considering the input nnz as output sparsity for empty left-hand-side matrices if the indexing identifiers are constant, e.g., during dynamic recompilation (after literal replacement); otherwise the sparsity is left as unknown. Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/30d4b1ee Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/30d4b1ee Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/30d4b1ee Branch: refs/heads/master Commit: 30d4b1eef85509c0f0cf646b15e4946d0eed3d32 Parents: cd5499c Author: Matthias Boehm <mboe...@gmail.com> Authored: Wed Apr 19 00:10:03 2017 -0700 Committer: Matthias Boehm <mboe...@gmail.com> Committed: Wed Apr 19 00:10:03 2017 -0700 ---------------------------------------------------------------------- .../org/apache/sysml/hops/LeftIndexingOp.java | 33 +++++++++++--------- .../recompile/SparsityRecompileTest.java | 8 ++--- 2 files changed, 23 insertions(+), 18 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/30d4b1ee/src/main/java/org/apache/sysml/hops/LeftIndexingOp.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/LeftIndexingOp.java b/src/main/java/org/apache/sysml/hops/LeftIndexingOp.java index 89c025b..f927af7 100644 --- a/src/main/java/org/apache/sysml/hops/LeftIndexingOp.java +++ b/src/main/java/org/apache/sysml/hops/LeftIndexingOp.java @@ -113,15 +113,7 @@ public class LeftIndexingOp extends Hop Lop bottom=getInput().get(3).constructLops(); Lop left=getInput().get(4).constructLops(); Lop right=getInput().get(5).constructLops(); - /* - //need to creat new lops for converting the index ranges - //original range is (a, b) --> (c, d) - //newa=2-a, newb=2-b - Lops two=new Data(null, Data.OperationTypes.READ, null, "2", Expression.DataType.SCALAR, Expression.ValueType.INT, false); - Lops newTop=new Binary(two, top, HopsOpOp2LopsB.get(Hops.OpOp2.MINUS), Expression.DataType.SCALAR, Expression.ValueType.INT, et); - Lops newLeft=new Binary(two, left, HopsOpOp2LopsB.get(Hops.OpOp2.MINUS), Expression.DataType.SCALAR, Expression.ValueType.INT, et); - //newc=leftmatrix.row-a+1, newd=leftmatrix.row - */ + //right hand matrix Lop nrow=new UnaryCP(getInput().get(0).constructLops(), OperationTypes.NROW, DataType.SCALAR, ValueType.INT); @@ -298,7 +290,9 @@ public class LeftIndexingOp extends Hop //(this is important for indexing sparse matrices into empty matrices). MatrixCharacteristics mcM1 = memo.getAllInputStats(getInput().get(0)); MatrixCharacteristics mcM2 = memo.getAllInputStats(getInput().get(1)); - if( mcM1.getNonZeros()>=0 && mcM2.getNonZeros()>=0 ) { + if( mcM1.getNonZeros()>=0 && mcM2.getNonZeros()>=0 + && hasConstantIndexingRange() ) + { long lnnz = mcM1.getNonZeros() + mcM2.getNonZeros(); _outputMemEstimate = computeOutputMemEstimate( _dim1, _dim2, lnnz ); _memEstimate = getInputSize(0) //original matrix (left) @@ -316,7 +310,7 @@ public class LeftIndexingOp extends Hop { Hop input1 = getInput().get(0); Hop input2 = getInput().get(1); - if( input1.dimsKnown() ) { + if( input1.dimsKnown() && hasConstantIndexingRange() ) { sparsity = OptimizerUtils.getLeftIndexingSparsity( input1.getDim1(), input1.getDim2(), input1.getNnz(), input2.getDim1(), input2.getDim2(), input2.getNnz()); @@ -351,8 +345,8 @@ public class LeftIndexingOp extends Hop double sparsity = OptimizerUtils.getLeftIndexingSparsity( mc1.getRows(), mc1.getCols(), mc1.getNonZeros(), mc2.getRows(), mc2.getCols(), mc2.getNonZeros()); - long lnnz = (long)(sparsity * mc1.getRows() * mc1.getCols()); - + long lnnz = !hasConstantIndexingRange() ? -1 : + (long)(sparsity * mc1.getRows() * mc1.getCols()); ret = new long[]{mc1.getRows(), mc1.getCols(), lnnz}; } @@ -442,7 +436,11 @@ public class LeftIndexingOp extends Hop setDim2( input1.getDim2() ); //refresh output nnz if exactly known; otherwise later inference - if( input1.getNnz() == 0 ) { + //note: leveraging the nnz for estimating the output sparsity is + //only valid for constant index identifiers (e.g., after literal + //replacement during dynamic recompilation), otherwise this could + //lead to underestimation and hence OOMs in loops + if( input1.getNnz() == 0 && hasConstantIndexingRange() ) { if( input2.getDataType()==DataType.SCALAR ) setNnz(1); else @@ -451,6 +449,13 @@ public class LeftIndexingOp extends Hop else setNnz(-1); } + + private boolean hasConstantIndexingRange() { + return (getInput().get(2) instanceof LiteralOp + && getInput().get(3) instanceof LiteralOp + && getInput().get(4) instanceof LiteralOp + && getInput().get(5) instanceof LiteralOp); + } private void checkAndModifyRecompilationStatus() { http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/30d4b1ee/src/test/java/org/apache/sysml/test/integration/functions/recompile/SparsityRecompileTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/recompile/SparsityRecompileTest.java b/src/test/java/org/apache/sysml/test/integration/functions/recompile/SparsityRecompileTest.java index 29ba76d..923dc47 100644 --- a/src/test/java/org/apache/sysml/test/integration/functions/recompile/SparsityRecompileTest.java +++ b/src/test/java/org/apache/sysml/test/integration/functions/recompile/SparsityRecompileTest.java @@ -138,15 +138,15 @@ public class SparsityRecompileTest extends AutomatedTestBase boolean exceptionExpected = false; runTest(true, exceptionExpected, null, -1); - //CHECK compiled MR jobs (changed 07/2015 due to better sparsity inference, 08/2015 due to better worst-case inference) + //CHECK compiled MR jobs int expectNumCompiled = (testname.equals(TEST_NAME2)?3:4) //reblock,GMR,GMR,GMR (one GMR less for if) - + ((testname.equals(TEST_NAME4) && !recompile)?2:0);//(+2 resultmerge) + + (testname.equals(TEST_NAME4)?2:0);//(+2 resultmerge) Assert.assertEquals("Unexpected number of compiled MR jobs.", expectNumCompiled, Statistics.getNoOfCompiledMRJobs()); - //CHECK executed MR jobs (changed 07/2015 due to better sparsity inference, 08/2015 due to better worst-case inference) + //CHECK executed MR jobs int expectNumExecuted = -1; - if( recompile ) expectNumExecuted = 0; //+ ((testname.equals(TEST_NAME4))?2:0); //(+2 resultmerge) + if( recompile ) expectNumExecuted = 0 + ((testname.equals(TEST_NAME4))?2:0); //(+2 resultmerge) else expectNumExecuted = (testname.equals(TEST_NAME2)?3:4) //reblock,GMR,GMR,GMR (one GMR less for if) + ((testname.equals(TEST_NAME4))?2:0); //(+2 resultmerge) Assert.assertEquals("Unexpected number of executed MR jobs.",