Repository: systemml Updated Branches: refs/heads/master 58f4ea9fe -> 7b56f6131
[SYSTEMML-2053] Fix dense-sparse conversions for large dense blocks With the introduction of large dense matrix blocks, the unconditional dense-sparse conversion into CSR format (with max int nnz) might cause an overflow. This patch fixes this potential overflow by conditionally converting into CSR with a fallback to MCSR if the nnz exceed max int. Furthermore, this also modifies both dense-sparse and sparse-dense conversion to properly handle large dense blocks. Furthermore, this patch also includes some minor cleanups regarding primitives for row-wise nnz computation and unnecessary reset after allocating new sparse blocks. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/7b56f613 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/7b56f613 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/7b56f613 Branch: refs/heads/master Commit: 7b56f613132febcc321f178e8386db15542ead77 Parents: 58f4ea9 Author: Matthias Boehm <[email protected]> Authored: Fri Dec 29 19:10:40 2017 -0800 Committer: Matthias Boehm <[email protected]> Committed: Fri Dec 29 19:10:40 2017 -0800 ---------------------------------------------------------------------- .../sysml/runtime/matrix/data/MatrixBlock.java | 112 +++++++++++-------- .../runtime/matrix/data/SparseBlockCOO.java | 9 +- .../runtime/matrix/data/SparseBlockCSR.java | 10 +- .../runtime/matrix/data/SparseRowVector.java | 5 +- .../sysml/runtime/util/UtilFunctions.java | 7 ++ 5 files changed, 84 insertions(+), 59 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/7b56f613/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 c20d347..caf024e 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 @@ -368,21 +368,23 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab return reset; } - public void allocateSparseRowsBlock() { - allocateSparseRowsBlock(true); + public boolean allocateSparseRowsBlock() { + return allocateSparseRowsBlock(true); } - public void allocateSparseRowsBlock(boolean clearNNZ) { + public boolean allocateSparseRowsBlock(boolean clearNNZ) { //allocate block if non-existing or too small (guaranteed to be 0-initialized) //but do not replace existing block even if not in default type - if( sparseBlock == null || sparseBlock.numRows()<rlen ) { - sparseBlock = SparseBlockFactory.createSparseBlock(DEFAULT_SPARSEBLOCK, rlen); + boolean reset = sparseBlock == null || sparseBlock.numRows()<rlen; + if( reset ) { + sparseBlock = SparseBlockFactory + .createSparseBlock(DEFAULT_SPARSEBLOCK, rlen); } - //clear nnz if necessary if( clearNNZ ) { nonZeros = 0; } + return reset; } public void allocateAndResetSparseRowsBlock(boolean clearNNZ, SparseBlock.Type stype) @@ -1087,7 +1089,7 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab private void denseToSparse() { - double[] a = getDenseBlockValues(); + DenseBlock a = getDenseBlock(); //set target representation, early abort on empty blocks sparse = true; @@ -1097,31 +1099,53 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab final int m = rlen; final int n = clen; - //allocate target in memory-efficient CSR format - int lnnz = (int) nonZeros; - int[] rptr = new int[m+1]; - int[] indexes = new int[lnnz]; - double[] values = new double[lnnz]; - for( int i=0, pos=0, aix=0; i<m; i++ ) { - for(int j=0; j<n; j++, aix++) { - double aval = a[aix]; - if( aval != 0 ) { - indexes[pos] = j; - values[pos] = aval; - pos++; + if( nonZeros <= Integer.MAX_VALUE ) { + //allocate target in memory-efficient CSR format + int lnnz = (int) nonZeros; + int[] rptr = new int[m+1]; + int[] indexes = new int[lnnz]; + double[] values = new double[lnnz]; + for( int i=0, pos=0; i<m; i++ ) { + double[] avals = a.values(i); + int aix = a.pos(i); + for(int j=0; j<n; j++) { + double aval = avals[aix+j]; + if( aval != 0 ) { + indexes[pos] = j; + values[pos] = aval; + pos++; + } } + rptr[i+1]=pos; + } + sparseBlock = new SparseBlockCSR( + rptr, indexes, values, lnnz); + } + else { + //fallback to less-memory efficient MCSR format, + //which however allows much larger sparse matrices + if( !allocateSparseRowsBlock() ) + reset(); //reset if not allocated + SparseBlock sblock = sparseBlock; + for( int i=0; i<m; i++ ) { + double[] avals = a.values(i); + int aix = a.pos(i); + //compute nnz per row (not via recomputeNonZeros as sparse allocated) + int lnnz = UtilFunctions.computeNnz(avals, aix, clen); + if( lnnz <= 0 ) continue; + //allocate sparse row and append non-zero values + sblock.allocate(i, lnnz); + for( int j=0; j<n; j++ ) + sblock.append(i, j, avals[aix+j]); } - rptr[i+1]=pos; } - sparseBlock = new SparseBlockCSR( - rptr, indexes, values, lnnz); //update nnz and cleanup dense block denseBlock = null; } public void sparseToDense() - throws DMLRuntimeException + throws DMLRuntimeException { //set target representation, early abort on empty blocks sparse = false; @@ -1139,18 +1163,20 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab //copy sparse to dense SparseBlock a = sparseBlock; - double[] c = getDenseBlockValues(); + DenseBlock c = getDenseBlock(); - for( int i=0, cix=0; i<rlen; i++, cix+=clen) - if( !a.isEmpty(i) ) { - int apos = a.pos(i); - int alen = a.size(i); - int[] aix = a.indexes(i); - double[] avals = a.values(i); - for(int j=apos; j<apos+alen; j++) - if( avals[j] != 0 ) - c[ cix+aix[j] ] = avals[j]; - } + for( int i=0; i<rlen; i++ ) { + if( a.isEmpty(i) ) continue; + int apos = a.pos(i); + int alen = a.size(i); + int[] aix = a.indexes(i); + double[] avals = a.values(i); + double[] cvals = c.values(i); + int cix = c.pos(i); + for( int j=apos; j<apos+alen; j++ ) + if( avals[j] != 0 ) + cvals[cix+aix[j]] = avals[j]; + } //cleanup sparse rows sparseBlock = null; @@ -1254,10 +1280,8 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab } @Override - public void copy(MatrixValue thatValue) - { + public void copy(MatrixValue thatValue) { MatrixBlock that = checkType(thatValue); - //copy into automatically determined representation copy( that, that.evalSparseFormatInMemory() ); } @@ -1536,12 +1560,10 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab && c.isEmpty(rix) ) //special case MCSR append { //count nnz per row (fits likely in L1 cache) - int lnnz = 0; - for( int j=0; j<src.clen; j++ ) - lnnz += (a[ix+j]!=0) ? 1 : 0; - + int lnnz = UtilFunctions.computeNnz(a, ix, src.clen); + //allocate row once and copy values - if( lnnz > 0 ) { + if( lnnz > 0 ) { c.allocate(rix, lnnz); for( int j=0; j<src.clen; j++ ) { double val = a[ix+j]; @@ -1879,9 +1901,9 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab private void readSparseBlock(DataInput in) throws IOException - { - allocateSparseRowsBlock(false); - resetSparse(); + { + if( !allocateSparseRowsBlock(false) ) + resetSparse(); //reset if not allocated if( in instanceof MatrixBlockDataInput ) { //fast deserialize MatrixBlockDataInput mbin = (MatrixBlockDataInput)in; http://git-wip-us.apache.org/repos/asf/systemml/blob/7b56f613/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java index d8b5326..4f60625 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java @@ -24,6 +24,7 @@ import java.util.Arrays; import java.util.Iterator; import org.apache.sysml.runtime.util.SortUtils; +import org.apache.sysml.runtime.util.UtilFunctions; /** * SparseBlock implementation that realizes a traditional 'coordinate matrix' @@ -345,12 +346,10 @@ public class SparseBlockCOO extends SparseBlock 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); - + //determine input nnz - int lnnz = 0; - for( int i=vix; i<vix+vlen; i++ ) - lnnz += ( v[i] != 0 ) ? 1 : 0; - + int lnnz = UtilFunctions.computeNnz(v, vix, vlen); + //prepare free space (allocate and shift) int lsize = _size+lnnz; if( _values.length < lsize ) http://git-wip-us.apache.org/repos/asf/systemml/blob/7b56f613/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 c3496ec..9019c06 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 @@ -25,6 +25,7 @@ import java.io.IOException; import java.util.Arrays; import org.apache.sysml.runtime.util.SortUtils; +import org.apache.sysml.runtime.util.UtilFunctions; /** * SparseBlock implementation that realizes a traditional 'compressed sparse row' @@ -507,10 +508,8 @@ public class SparseBlockCSR extends SparseBlock deleteIndexRange(r, cl, cu); //determine input nnz - int lnnz = 0; - for( int i=vix; i<vix+vlen; i++ ) - lnnz += ( v[i] != 0 ) ? 1 : 0; - + int lnnz = UtilFunctions.computeNnz(v, vix, vlen); + //prepare free space (allocate and shift) int lsize = _size+lnnz; if( _values.length < lsize ) @@ -546,8 +545,7 @@ public class SparseBlockCSR extends SparseBlock //step 1: determine output nnz int nnz = _size - (int)size(rl, ru, cl, cu); if( v != null ) - for( int i=vix; i<vix+vlen; i++ ) - nnz += (v[i]!=0) ? 1: 0; + nnz += UtilFunctions.computeNnz(v, vix, vlen); //step 2: reallocate if necessary if( _values.length < nnz ) http://git-wip-us.apache.org/repos/asf/systemml/blob/7b56f613/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowVector.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowVector.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowVector.java index 1d71448..1510b7d 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowVector.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseRowVector.java @@ -24,6 +24,7 @@ import java.io.Serializable; import java.util.Arrays; import org.apache.sysml.runtime.util.SortUtils; +import org.apache.sysml.runtime.util.UtilFunctions; public final class SparseRowVector extends SparseRow implements Serializable { @@ -288,9 +289,7 @@ public final class SparseRowVector extends SparseRow implements Serializable } //determine input nnz - int lnnz = 0; - for( int i=vix; i<vix+len; i++ ) - lnnz += ( v[i] != 0 ) ? 1 : 0; + int lnnz = UtilFunctions.computeNnz(v, vix, len); //prepare free space (allocate and shift) int lsize = size+lnnz-(end-start); http://git-wip-us.apache.org/repos/asf/systemml/blob/7b56f613/src/main/java/org/apache/sysml/runtime/util/UtilFunctions.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/util/UtilFunctions.java b/src/main/java/org/apache/sysml/runtime/util/UtilFunctions.java index 199108b..b876300 100644 --- a/src/main/java/org/apache/sysml/runtime/util/UtilFunctions.java +++ b/src/main/java/org/apache/sysml/runtime/util/UtilFunctions.java @@ -559,6 +559,13 @@ public class UtilFunctions return (!sobj.equals("0") && !sobj.equals("0.0")); } } + + public static int computeNnz(double[] a, int ai, int len) { + int lnnz = 0; + for( int i=ai; i<ai+len; i++ ) + lnnz += (a[i] != 0) ? 1 : 0; + return lnnz; + } public static ValueType[] nCopies(int n, ValueType vt) { ValueType[] ret = new ValueType[n];
