Repository: systemml Updated Branches: refs/heads/master b00a66536 -> 2ddc84873
[SYSTEMML-2130] Fix pack correct sparse/dense representations and nnzs This fix pack includes a set of fixes that address various issues of operations that produces outputs in wrong sparse/dense representation or with incorrect nnz meta data: (1) Fix sparsity check in grouped aggregates (due to aggregation we now unconditionally check for a potential flip from dense to sparse) (2) Fix dense outputs or removeEmpty rows (the new special case for shallow CSR copies always output the result in sparse format - now we check for potential dense outputs and fall back to the default case) (3) Nnz maintenance in sparse-unsafe binary operations (the nnz computation in sparse-unsafe binary operations assumed that these operations always produced populated outputs which is not always the case) (4) Sparse-safe bitwise shift operations (the root cause of issue 3 was that the new bitwise shift operations were not correctly marked as sparse-safe operation yet) (5) Output sparsity estimates for outer operations (the sparsity estimate for outer operations assumed always strict multiply semantics which is not the case for other operations like comparisons) (6) Output sparsity estimates for div operations with NaN outputs (we now correctly compute the output sparsity by accounting for NaN outputs introduced by 0s in the right hand side) (7) Unconditional representation change for small outputs <8MB from binary operations. (8) Unconditional representation change for single block index lookups (rightindexing) and RDD collect operations. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/2ddc8487 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/2ddc8487 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/2ddc8487 Branch: refs/heads/master Commit: 2ddc84873e04880558b067e9c23e7be5f76e069c Parents: b00a665 Author: Matthias Boehm <[email protected]> Authored: Sat Mar 3 19:59:41 2018 -0800 Committer: Matthias Boehm <[email protected]> Committed: Sat Mar 3 20:00:15 2018 -0800 ---------------------------------------------------------------------- .../org/apache/sysml/hops/OptimizerUtils.java | 51 ++++++++++++++------ .../context/SparkExecutionContext.java | 1 + .../cp/ComputationCPInstruction.java | 6 ++- .../spark/MatrixIndexingSPInstruction.java | 1 + .../sysml/runtime/matrix/data/LibMatrixAgg.java | 4 ++ .../runtime/matrix/data/LibMatrixBincell.java | 10 ++-- .../runtime/matrix/data/LibMatrixReorg.java | 26 +++++----- .../sysml/runtime/matrix/data/MatrixBlock.java | 15 +++--- .../matrix/operators/ScalarOperator.java | 5 +- 9 files changed, 78 insertions(+), 41 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/2ddc8487/src/main/java/org/apache/sysml/hops/OptimizerUtils.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/OptimizerUtils.java b/src/main/java/org/apache/sysml/hops/OptimizerUtils.java index d56692c..b8150f8 100644 --- a/src/main/java/org/apache/sysml/hops/OptimizerUtils.java +++ b/src/main/java/org/apache/sysml/hops/OptimizerUtils.java @@ -98,6 +98,8 @@ public class OptimizerUtils public static final long MAX_NNZ_CP_SPARSE = (MatrixBlock.DEFAULT_SPARSEBLOCK == SparseBlock.Type.MCSR) ? Long.MAX_VALUE : Integer.MAX_VALUE; + public static final long SAFE_REP_CHANGE_THRES = 8 * 1024 *1024; //8MB + /** * Enables common subexpression elimination in dags. There is however, a potential tradeoff * between computation redundancy and data transfer between MR jobs. Since, we do not reason @@ -1066,11 +1068,10 @@ public class OptimizerUtils //NOTE: for matrix-scalar operations this estimate is too conservative, because //Math.min(1, sp1 + sp2) will always give a sparsity 1 if we pass sp2=1 for scalars. //In order to do better (with guarantees), we need to take the actual values into account - switch(op) - { + switch(op) { case PLUS: case MINUS: - case LESS: + case LESS: case GREATER: case NOTEQUAL: case MIN: @@ -1081,47 +1082,43 @@ public class OptimizerUtils case AND: ret = Math.min(sp1, sp2); break; case DIV: + ret = Math.min(1, sp1 + (1-sp2)); break; case MODULUS: case POW: case MINUS_NZ: - case LOG_NZ: - ret = sp1; break; + case LOG_NZ: + ret = sp1; break; //case EQUAL: //doesnt work on worstcase estimates, but on - // ret = 1-Math.abs(sp1-sp2); break; - + // ret = 1-Math.abs(sp1-sp2); break; default: ret = 1.0; } } else { - switch(op) { + switch(op) { case PLUS: case MINUS: // result[i,j] != 0 iff A[i,j] !=0 || B[i,j] != 0 // worst case estimate = sp1+sp2 - ret = (1 - (1-sp1)*(1-sp2)); + ret = (1 - (1-sp1)*(1-sp2)); break; - case MULT: // result[i,j] != 0 iff A[i,j] !=0 && B[i,j] != 0 // worst case estimate = min(sp1,sp2) - ret = sp1 * sp2; + ret = sp1 * sp2; break; - case DIV: ret = 1.0; // worst case estimate break; - - case LESS: + case LESS: case LESSEQUAL: case GREATER: case GREATEREQUAL: - case EQUAL: + case EQUAL: case NOTEQUAL: ret = 1.0; // purely data-dependent operations, and hence worse-case estimate break; - //MIN, MAX, AND, OR, LOG, POW default: ret = 1.0; @@ -1131,6 +1128,28 @@ public class OptimizerUtils return ret; } + public static long getOuterNonZeros(long n1, long n2, long nnz1, long nnz2, OpOp2 op) { + if( nnz1 < 0 || nnz2 < 0 ) + return n1 * n2; + switch(op) { + case PLUS: + case MINUS: + case LESS: + case GREATER: + case NOTEQUAL: + case MIN: + case MAX: + case OR: + return n1 * n2 + - (n1-nnz1) * (n2-nnz2); + case MULT: + case AND: + return nnz1 * nnz2; + default: + return n1 * n2; + } + } + public static double getSparsity( MatrixCharacteristics mc ) { return getSparsity(mc.getRows(), mc.getCols(), mc.getNonZeros()); } http://git-wip-us.apache.org/repos/asf/systemml/blob/2ddc8487/src/main/java/org/apache/sysml/runtime/controlprogram/context/SparkExecutionContext.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/controlprogram/context/SparkExecutionContext.java b/src/main/java/org/apache/sysml/runtime/controlprogram/context/SparkExecutionContext.java index 91c577b..86c3adc 100644 --- a/src/main/java/org/apache/sysml/runtime/controlprogram/context/SparkExecutionContext.java +++ b/src/main/java/org/apache/sysml/runtime/controlprogram/context/SparkExecutionContext.java @@ -814,6 +814,7 @@ public class SparkExecutionContext extends ExecutionContext out = list.get(0)._2(); else //empty (e.g., after ops w/ outputEmpty=false) out = new MatrixBlock(rlen, clen, true); + out.examSparsity(); } else //MULTIPLE BLOCKS { http://git-wip-us.apache.org/repos/asf/systemml/blob/2ddc8487/src/main/java/org/apache/sysml/runtime/instructions/cp/ComputationCPInstruction.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/instructions/cp/ComputationCPInstruction.java b/src/main/java/org/apache/sysml/runtime/instructions/cp/ComputationCPInstruction.java index 4dbdba4..aa66595 100644 --- a/src/main/java/org/apache/sysml/runtime/instructions/cp/ComputationCPInstruction.java +++ b/src/main/java/org/apache/sysml/runtime/instructions/cp/ComputationCPInstruction.java @@ -21,6 +21,7 @@ package org.apache.sysml.runtime.instructions.cp; import org.apache.sysml.api.DMLScript; import org.apache.sysml.api.DMLScript.RUNTIME_PLATFORM; +import org.apache.sysml.hops.OptimizerUtils; import org.apache.sysml.runtime.controlprogram.caching.CacheableData; import org.apache.sysml.runtime.matrix.data.MatrixBlock; import org.apache.sysml.runtime.matrix.operators.Operator; @@ -57,8 +58,9 @@ public abstract class ComputationCPInstruction extends CPInstruction { } protected boolean checkGuardedRepresentationChange( MatrixBlock in1, MatrixBlock in2, MatrixBlock out ) { - if( DMLScript.rtplatform == RUNTIME_PLATFORM.SINGLE_NODE - && !CacheableData.isCachingActive() ) + if( (DMLScript.rtplatform == RUNTIME_PLATFORM.SINGLE_NODE + && !CacheableData.isCachingActive()) + || out.getInMemorySize() < OptimizerUtils.SAFE_REP_CHANGE_THRES) //8MB return true; double memIn1 = (in1 != null) ? in1.getInMemorySize() : 0; double memIn2 = (in2 != null) ? in2.getInMemorySize() : 0; http://git-wip-us.apache.org/repos/asf/systemml/blob/2ddc8487/src/main/java/org/apache/sysml/runtime/instructions/spark/MatrixIndexingSPInstruction.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/instructions/spark/MatrixIndexingSPInstruction.java b/src/main/java/org/apache/sysml/runtime/instructions/spark/MatrixIndexingSPInstruction.java index 78486cb..d1e02ca 100644 --- a/src/main/java/org/apache/sysml/runtime/instructions/spark/MatrixIndexingSPInstruction.java +++ b/src/main/java/org/apache/sysml/runtime/instructions/spark/MatrixIndexingSPInstruction.java @@ -228,6 +228,7 @@ public class MatrixIndexingSPInstruction extends IndexingSPInstruction { UtilFunctions.computeCellInBlock(ixrange.rowEnd, mcIn.getRowsPerBlock()), UtilFunctions.computeCellInBlock(ixrange.colStart, mcIn.getColsPerBlock()), UtilFunctions.computeCellInBlock(ixrange.colEnd, mcIn.getColsPerBlock()), new MatrixBlock()); + mbout.examSparsity(); return mbout; } http://git-wip-us.apache.org/repos/asf/systemml/blob/2ddc8487/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixAgg.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixAgg.java b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixAgg.java index a81dd17..86ed4c4 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixAgg.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixAgg.java @@ -485,6 +485,10 @@ public class LibMatrixAgg AggregateOperator aggop = (AggregateOperator) op; groupedAggregateKahanPlus(groups, target, weights, result, numGroups, aggop, 0, target.clen); } + + //postprocessing sparse/dense formats + //(nnz already maintained via append) + result.examSparsity(); } public static void groupedAggregate(MatrixBlock groups, MatrixBlock target, MatrixBlock weights, MatrixBlock result, int numGroups, Operator op, int k) http://git-wip-us.apache.org/repos/asf/systemml/blob/2ddc8487/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java index 760d1ca..224221b 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixBincell.java @@ -1022,10 +1022,13 @@ public class LibMatrixBincell int n = m1.clen; //init dense result with unsafe 0-value - dc.set(op.executeScalar(0)); + double val0 = op.executeScalar(0); + boolean lsparseSafe = (val0 == 0); + if( !lsparseSafe ) + dc.set(val0); //compute non-zero input values - long nnz = m * n; + long nnz = lsparseSafe ? 0 : m * n; for(int bi=0; bi<dc.numBlocks(); bi++) { int blen = dc.blockSize(bi); double[] c = dc.valuesAt(bi); @@ -1038,7 +1041,8 @@ public class LibMatrixBincell for(int j=apos; j<apos+alen; j++) { double val = op.executeScalar(avals[j]); c[ cix+aix[j] ] = val; - nnz -= (val==0) ? 1 : 0; + nnz += lsparseSafe ? (val!=0 ? 1 : 0) : + (val==0 ? -1 : 0); } } } http://git-wip-us.apache.org/repos/asf/systemml/blob/2ddc8487/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixReorg.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixReorg.java b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixReorg.java index e7988c8..3f302a9 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixReorg.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixReorg.java @@ -1727,17 +1727,21 @@ public class LibMatrixReorg int lrlen = 0; for( int i=0; i<m; i++ ) lrlen += sblock.isEmpty(i) ? 0 : 1; - int[] rptr = new int[lrlen+1]; - for( int i=0, j=0, pos=0; i<m; i++ ) - if( !sblock.isEmpty(i) ) { - pos += sblock.size(i); - rptr[++j] = pos; - } - ret.reset(lrlen, in.clen, true); - ret.sparseBlock = new SparseBlockCSR(rptr, - sblock.indexes(), sblock.values(), (int)in.nonZeros); - ret.nonZeros = in.nonZeros; - return ret; + //check for sparse output representation, otherwise + //fall back to default pass to allocate in dense format + if( MatrixBlock.evalSparseFormatInMemory(lrlen, n, in.nonZeros) ) { + int[] rptr = new int[lrlen+1]; + for( int i=0, j=0, pos=0; i<m; i++ ) + if( !sblock.isEmpty(i) ) { + pos += sblock.size(i); + rptr[++j] = pos; + } + ret.reset(lrlen, in.clen, true); + ret.sparseBlock = new SparseBlockCSR(rptr, + sblock.indexes(), sblock.values(), (int)in.nonZeros); + ret.nonZeros = in.nonZeros; + return ret; + } } //Step 1: scan block and determine non-empty rows http://git-wip-us.apache.org/repos/asf/systemml/blob/2ddc8487/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java index 7de42a5..bf28b79 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java @@ -2449,7 +2449,7 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab //estimate dense output for all sparse-unsafe operations, except DIV (because it commonly behaves like //sparse-safe but is not due to 0/0->NaN, this is consistent with the current hop sparsity estimate) //see also, special sparse-safe case for DIV in LibMatrixBincell - if( !op.sparseSafe && !(op.fn instanceof Divide) ) { + if( !op.sparseSafe && !(op.fn instanceof Divide && m2.getSparsity()==1.0) ) { est.sparse = false; return est; } @@ -2465,16 +2465,16 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab long estnnz = 0; if( atype == BinaryAccessType.OUTER_VECTOR_VECTOR ) { - //for outer vector operations the sparsity estimate is exactly known - estnnz = nz1 * nz2; + estnnz = OptimizerUtils.getOuterNonZeros( + m, n, nz1, nz2, op.getBinaryOperatorOpOp2()); } else //DEFAULT CASE - { + { if( atype == BinaryAccessType.MATRIX_COL_VECTOR ) nz2 = nz2 * n; else if( atype == BinaryAccessType.MATRIX_ROW_VECTOR ) nz2 = nz2 * m; - + //compute output sparsity consistent w/ the hop compiler double sp1 = OptimizerUtils.getSparsity(m, n, nz1); double sp2 = OptimizerUtils.getSparsity(m, n, nz2); @@ -4879,9 +4879,8 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab public MatrixBlock removeEmptyOperations( MatrixBlock ret, boolean rows, boolean emptyReturn, MatrixBlock select ) throws DMLRuntimeException - { - MatrixBlock result = checkType(ret); - return LibMatrixReorg.rmempty(this, result, rows, emptyReturn, select); + { + return LibMatrixReorg.rmempty(this, ret, rows, emptyReturn, select); } public MatrixBlock removeEmptyOperations( MatrixBlock ret, boolean rows, boolean emptyReturn) http://git-wip-us.apache.org/repos/asf/systemml/blob/2ddc8487/src/main/java/org/apache/sysml/runtime/matrix/operators/ScalarOperator.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/operators/ScalarOperator.java b/src/main/java/org/apache/sysml/runtime/matrix/operators/ScalarOperator.java index 2c5885b..089c88f 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/operators/ScalarOperator.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/operators/ScalarOperator.java @@ -22,6 +22,8 @@ package org.apache.sysml.runtime.matrix.operators; import org.apache.sysml.runtime.DMLRuntimeException; import org.apache.sysml.runtime.functionobjects.And; +import org.apache.sysml.runtime.functionobjects.BitwShiftL; +import org.apache.sysml.runtime.functionobjects.BitwShiftR; import org.apache.sysml.runtime.functionobjects.Builtin; import org.apache.sysml.runtime.functionobjects.Builtin.BuiltinCode; import org.apache.sysml.runtime.functionobjects.Equals; @@ -85,6 +87,7 @@ public abstract class ScalarOperator extends Operator protected static boolean isSparseSafeStatic(ValueFunction fn) { return ( fn instanceof Multiply || fn instanceof Multiply2 || fn instanceof Power2 || fn instanceof And || fn instanceof MinusNz - || fn instanceof Builtin && ((Builtin)fn).getBuiltinCode()==BuiltinCode.LOG_NZ); + || fn instanceof Builtin && ((Builtin)fn).getBuiltinCode()==BuiltinCode.LOG_NZ) + || fn instanceof BitwShiftL || fn instanceof BitwShiftR; } }
