Repository: incubator-systemml Updated Branches: refs/heads/master aa83a6f44 -> cb7feae74
[SYSTEMML-753][SYSTEMML-633] Extended loop update-in-place left indexing This patch generalizes the existing rewrite for marking loop left indexing as update-in-place. We now additionally tolerate (1) statement blocks where the respective variable is not used as all, and (2) safe nrow/ncol operations in the same DAG. Further, the for/while runtime update-in-place is now also used by parfor, which is useful if the parfor optimizer cannot pin the variables for update in place due to unknown sizes, e.g., with complex UDF functions. Furthermore, this patch also makes smaller improvements to CSR in-place indexing (ensure exponential allocation in all cases, efficiency set index range, no special append on copy dense-sparse if not MCSR). Finally, the explain util has been fixed to output the function call DAG just once (not on every function) and output update-in-place variables for parfor loops as well. Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/cb7feae7 Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/cb7feae7 Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/cb7feae7 Branch: refs/heads/master Commit: cb7feae743c54a0db9046fdbb80ffbc8629b7b3f Parents: aa83a6f Author: Matthias Boehm <[email protected]> Authored: Sun Jun 19 01:20:22 2016 -0700 Committer: Matthias Boehm <[email protected]> Committed: Sun Jun 19 01:20:22 2016 -0700 ---------------------------------------------------------------------- .../RewriteMarkLoopVariablesUpdateInPlace.java | 27 ++++++++---- .../controlprogram/ParForProgramBlock.java | 6 ++- .../controlprogram/caching/ByteBuffer.java | 8 +--- .../sysml/runtime/matrix/data/MatrixBlock.java | 44 +++++++++----------- .../runtime/matrix/data/SparseBlockCSR.java | 25 +++++++++-- .../java/org/apache/sysml/utils/Explain.java | 28 +++++++------ 6 files changed, 83 insertions(+), 55 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/cb7feae7/src/main/java/org/apache/sysml/hops/rewrite/RewriteMarkLoopVariablesUpdateInPlace.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/rewrite/RewriteMarkLoopVariablesUpdateInPlace.java b/src/main/java/org/apache/sysml/hops/rewrite/RewriteMarkLoopVariablesUpdateInPlace.java index ce8c255..9be0408 100644 --- a/src/main/java/org/apache/sysml/hops/rewrite/RewriteMarkLoopVariablesUpdateInPlace.java +++ b/src/main/java/org/apache/sysml/hops/rewrite/RewriteMarkLoopVariablesUpdateInPlace.java @@ -25,8 +25,10 @@ import org.apache.sysml.api.DMLScript; import org.apache.sysml.api.DMLScript.RUNTIME_PLATFORM; import org.apache.sysml.hops.DataOp; import org.apache.sysml.hops.Hop; +import org.apache.sysml.hops.Hop.OpOp1; import org.apache.sysml.hops.HopsException; import org.apache.sysml.hops.LeftIndexingOp; +import org.apache.sysml.hops.UnaryOp; import org.apache.sysml.parser.ForStatement; import org.apache.sysml.parser.ForStatementBlock; import org.apache.sysml.parser.IfStatement; @@ -102,13 +104,14 @@ public class RewriteMarkLoopVariablesUpdateInPlace extends StatementBlockRewrite //recursive invocation boolean ret = true; for( StatementBlock sb : sbs ) { - if (sb instanceof WhileStatementBlock || sb instanceof ForStatementBlock ) - { + if( !sb.variablesRead().containsVariable(varname) ) + continue; //valid wrt update-in-place + + if( sb instanceof WhileStatementBlock || sb instanceof ForStatementBlock ) { ret &= sb.getUpdateInPlaceVars() .contains(varname); } - else if (sb instanceof IfStatementBlock) - { + else if( sb instanceof IfStatementBlock ) { IfStatementBlock isb = (IfStatementBlock) sb; IfStatement istmt = (IfStatement)isb.getStatement(0); ret &= rIsApplicableForUpdateInPlace(istmt.getIfBody(), varname); @@ -141,10 +144,20 @@ public class RewriteMarkLoopVariablesUpdateInPlace extends StatementBlockRewrite //valid if read/updated by leftindexing //CP exec type not evaluated here as no lops generated yet - return hop instanceof DataOp + boolean validLix = hop instanceof DataOp && hop.getInput().get(0) instanceof LeftIndexingOp && hop.getInput().get(0).getInput().get(0) instanceof DataOp - && hop.getInput().get(0).getInput().get(0).getName().equals(varname) - && hop.getInput().get(0).getInput().get(0).getParent().size()==1; + && hop.getInput().get(0).getInput().get(0).getName().equals(varname); + + //valid if only safe consumers of left indexing input + if( validLix ) { + for( Hop p : hop.getInput().get(0).getInput().get(0).getParent() ) { + validLix &= ( p == hop.getInput().get(0) //lix + || (p instanceof UnaryOp && ((UnaryOp)p).getOp()==OpOp1.NROW) + || (p instanceof UnaryOp && ((UnaryOp)p).getOp()==OpOp1.NCOL)); + } + } + + return validLix; } } http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/cb7feae7/src/main/java/org/apache/sysml/runtime/controlprogram/ParForProgramBlock.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/controlprogram/ParForProgramBlock.java b/src/main/java/org/apache/sysml/runtime/controlprogram/ParForProgramBlock.java index e9aef4b..45435fa 100644 --- a/src/main/java/org/apache/sysml/runtime/controlprogram/ParForProgramBlock.java +++ b/src/main/java/org/apache/sysml/runtime/controlprogram/ParForProgramBlock.java @@ -719,6 +719,7 @@ public class ParForProgramBlock extends ForProgramBlock for( int i=0; i<_numThreads; i++ ) { //create parallel workers as (lazy) deep copies + //including preparation of update-in-place variables workers[i] = createParallelWorker( _pwIDs[i], queue, ec ); threads[i] = new Thread( workers[i] ); threads[i].setPriority(Thread.MAX_PRIORITY); @@ -1417,9 +1418,12 @@ public class ParForProgramBlock extends ForProgramBlock cpChildBlocks = ProgramConverter.rcreateDeepCopyProgramBlocks(_childBlocks, pwID, _IDPrefix, new HashSet<String>(), fnNames, false, false); } - //deep copy execution context + //deep copy execution context (including prepare parfor update-in-place) ExecutionContext cpEc = ProgramConverter.createDeepCopyExecutionContext(ec); + //prepare basic update-in-place variables (vars dropped on result merge) + prepareUpdateInPlaceVariables(cpEc); + //copy compiler configuration (for jmlc w/o global config) CompilerConfig cconf = ConfigurationManager.getCompilerConfig(); http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/cb7feae7/src/main/java/org/apache/sysml/runtime/controlprogram/caching/ByteBuffer.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/controlprogram/caching/ByteBuffer.java b/src/main/java/org/apache/sysml/runtime/controlprogram/caching/ByteBuffer.java index 28ec6f5..31f7a00 100644 --- a/src/main/java/org/apache/sysml/runtime/controlprogram/caching/ByteBuffer.java +++ b/src/main/java/org/apache/sysml/runtime/controlprogram/caching/ByteBuffer.java @@ -69,17 +69,11 @@ public class ByteBuffer } else //SPARSE/DENSE -> DENSE { - //special handling sparse matrix blocks whose serialized representation - //is dense; change representation (if required), incl. free sparse - if( cb instanceof MatrixBlock && ((MatrixBlock)cb).isInSparseFormat() ) - ((MatrixBlock)cb).examSparsity(); - //shallow serialize _cdata = cb; } } - catch(Exception ex) - { + catch(Exception ex) { throw new IOException("Failed to serialize cache block.", ex); } http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/cb7feae7/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 e92cdf9..54cba0f 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 @@ -1581,8 +1581,7 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab throws DMLRuntimeException { //handle empty src and dest - if( src.isEmptyBlock(false) ) - { + if( src.isEmptyBlock(false) ) { if( awareDestNZ && denseBlock != null ) { nonZeros -= recomputeNonZeros(rl, ru, cl, cu); copyEmptyToDense(rl, ru, cl, cu); @@ -1591,8 +1590,7 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab } if(denseBlock==null) allocateDenseBlock(); - else if( awareDestNZ ) - { + else if( awareDestNZ ) { nonZeros -= recomputeNonZeros(rl, ru, cl, cu); copyEmptyToDense(rl, ru, cl, cu); } @@ -1620,30 +1618,29 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab private void copyDenseToSparse(int rl, int ru, int cl, int cu, MatrixBlock src, boolean awareDestNZ) { //handle empty src and dest - if( src.isEmptyBlock(false) ) - { + if( src.isEmptyBlock(false) ) { if( awareDestNZ && sparseBlock != null ) copyEmptyToSparse(rl, ru, cl, cu, true); return; } - if(sparseBlock==null) { - sparseBlock=SparseBlockFactory - .createSparseBlock(DEFAULT_SPARSEBLOCK, rlen); - } + + //allocate output block //no need to clear for awareDestNZ since overwritten + allocateSparseRowsBlock(false); //copy values SparseBlock a = sparseBlock; for( int i=0, ix=0; i<src.rlen; i++, ix+=src.clen ) { int rix = rl + i; - if( a.isEmpty(rix) ) + if( a instanceof SparseBlockMCSR + && a.isEmpty(rix) ) //special case MCSR append { for( int j=0; j<src.clen; j++ ) { double val = src.denseBlock[ix+j]; if( val != 0 ) { a.allocate(rix, estimatedNNzsPerRow, clen); - sparseBlock.append(rix, cl+j, val); + a.append(rix, cl+j, val); } } @@ -1675,20 +1672,20 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab private void copyDenseToDense(int rl, int ru, int cl, int cu, MatrixBlock src, boolean awareDestNZ) throws DMLRuntimeException - { + { //handle empty src and dest - if( src.isEmptyBlock(false) ) - { + if( src.isEmptyBlock(false) ) { if( awareDestNZ && denseBlock != null ) { nonZeros -= recomputeNonZeros(rl, ru, cl, cu); copyEmptyToDense(rl, ru, cl, cu); } return; } - if(denseBlock==null) - allocateDenseBlock(); + + //allocate output block //no need to clear for awareDestNZ since overwritten - + allocateDenseBlock(false); + if( awareDestNZ ) nonZeros = nonZeros - recomputeNonZeros(rl, ru, cl, cu) + src.nonZeros; @@ -2796,8 +2793,8 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab @Override public boolean isShallowSerialize() { - //shallow serialize if dense in serialized form or already in CSR - return !evalSparseFormatOnDisk() + //shallow serialize if dense, dense in serialized form or already in CSR + return !sparse || !evalSparseFormatOnDisk() || (sparse && sparseBlock instanceof SparseBlockCSR); } @@ -3961,15 +3958,12 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab //result = (MatrixBlockDSM) zeroOutOperations(result, new IndexRange(rowLower,rowUpper, colLower, colUpper ), false); MatrixBlock src = (MatrixBlock)rhsMatrix; - - if(rl==ru && cl==cu) //specific case: cell update - { + if(rl==ru && cl==cu) { //specific case: cell update //copy single value and update nnz result.quickSetValue(rl, cl, src.quickGetValue(0, 0)); } - else //general case - { + else { //general case //copy submatrix into result result.copy(rl, ru, cl, cu, src, true); } http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/cb7feae7/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java index 5108a2f..b6bcb5f 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java @@ -340,7 +340,8 @@ public class SparseBlockCSR extends SparseBlock @Override public void setIndexRange(int r, int cl, int cu, double[] v, int vix, int vlen) { //delete existing values in range if necessary - deleteIndexRange(r, cl, cu); + if( !isEmpty(r) ) + deleteIndexRange(r, cl, cu); //determine input nnz int lnnz = 0; @@ -506,10 +507,28 @@ public class SparseBlockCSR extends SparseBlock double tmpCap = _values.length * RESIZE_FACTOR1; int newCap = (int)Math.min(tmpCap, Integer.MAX_VALUE); - resize(newCap); + resizeCopy(newCap); } - private void resize(int capacity) { + /** + * + * @param minsize + */ + private void resize(int minsize) { + //compute new size until minsize reached + double tmpCap = _values.length; + while( tmpCap < minsize ) + tmpCap *= RESIZE_FACTOR1; + int newCap = (int)Math.min(tmpCap, Integer.MAX_VALUE); + + resizeCopy(newCap); + } + + /** + * + * @param capacity + */ + private void resizeCopy(int capacity) { //reallocate arrays and copy old values _indexes = Arrays.copyOf(_indexes, capacity); _values = Arrays.copyOf(_values, capacity); http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/cb7feae7/src/main/java/org/apache/sysml/utils/Explain.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/utils/Explain.java b/src/main/java/org/apache/sysml/utils/Explain.java index 6e8b4f6..3a24786 100644 --- a/src/main/java/org/apache/sysml/utils/Explain.java +++ b/src/main/java/org/apache/sysml/utils/Explain.java @@ -241,21 +241,21 @@ public class Explain // Explain functions (if exists) boolean firstFunction = true; - for (String namespace : prog.getNamespaces().keySet()){ - for (String fname : prog.getFunctionStatementBlocks(namespace).keySet()){ + for (String namespace : prog.getNamespaces().keySet()) { + for (String fname : prog.getFunctionStatementBlocks(namespace).keySet()) { if (firstFunction) { sb.append("--FUNCTIONS\n"); firstFunction = false; + + //show function call dag + sb.append("----FUNCTION CALL DAG\n"); + sb.append("------MAIN PROGRAM\n"); + HashSet<String> fstack = new HashSet<String>(); + HashSet<String> lfset = new HashSet<String>(); + for( StatementBlock sblk : prog.getStatementBlocks() ) + sb.append(explainFunctionCallDag(sblk, fstack, lfset, 3)); } - //show function call dag - sb.append("----FUNCTION CALL DAG\n"); - sb.append("------MAIN PROGRAM\n"); - HashSet<String> fstack = new HashSet<String>(); - HashSet<String> lfset = new HashSet<String>(); - for( StatementBlock sblk : prog.getStatementBlocks() ) - sb.append(explainFunctionCallDag(sblk, fstack, lfset, 3)); - //show individual functions FunctionStatementBlock fsb = prog.getFunctionStatementBlock(namespace, fname); FunctionStatement fstmt = (FunctionStatement) fsb.getStatement(0); @@ -589,8 +589,12 @@ public class Explain else if (sb instanceof ForStatementBlock) { ForStatementBlock fsb = (ForStatementBlock) sb; builder.append(offset); - if (sb instanceof ParForStatementBlock) - builder.append("PARFOR (lines "+fsb.getBeginLine()+"-"+fsb.getEndLine()+")\n"); + if (sb instanceof ParForStatementBlock) { + if( !fsb.getUpdateInPlaceVars().isEmpty() ) + builder.append("PARFOR (lines "+fsb.getBeginLine()+"-"+fsb.getEndLine()+") [in-place="+fsb.getUpdateInPlaceVars().toString()+"]\n"); + else + builder.append("PARFOR (lines "+fsb.getBeginLine()+"-"+fsb.getEndLine()+")\n"); + } else { if( !fsb.getUpdateInPlaceVars().isEmpty() ) builder.append("FOR (lines "+fsb.getBeginLine()+"-"+fsb.getEndLine()+") [in-place="+fsb.getUpdateInPlaceVars().toString()+"]\n");
