Repository: systemml Updated Branches: refs/heads/master c382386a0 -> 63ad279fd
[SYSTEMML-2046] Large dense matrix blocks in unary/binary operations This patch extends all unary, binary, and scalar operations to support large dense matrix blocks >16GB. Additionally, this also includes minor extensions of the new dense block abstraction and a cleanup of the matrix value abstraction. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/63ad279f Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/63ad279f Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/63ad279f Branch: refs/heads/master Commit: 63ad279fd8a1db216ba6a99b684eaf5d703db934 Parents: c382386 Author: Matthias Boehm <mboe...@gmail.com> Authored: Sat Dec 16 18:33:23 2017 +0100 Committer: Matthias Boehm <mboe...@gmail.com> Committed: Sun Dec 17 20:50:30 2017 +0100 ---------------------------------------------------------------------- .../runtime/compress/CompressedMatrixBlock.java | 8 - .../sysml/runtime/matrix/data/CM_N_COVCell.java | 6 - .../sysml/runtime/matrix/data/DenseBlock.java | 32 ++ .../runtime/matrix/data/DenseBlockDRB.java | 20 + .../runtime/matrix/data/DenseBlockLDRB.java | 30 +- .../runtime/matrix/data/LibMatrixBincell.java | 361 ++++++++++--------- .../sysml/runtime/matrix/data/MatrixBlock.java | 141 +------- .../sysml/runtime/matrix/data/MatrixCell.java | 6 - .../sysml/runtime/matrix/data/MatrixValue.java | 3 - .../sysml/runtime/matrix/data/WeightedCell.java | 6 - 10 files changed, 285 insertions(+), 328 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/63ad279f/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java b/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java index 81cc9cf..e5edada 100644 --- a/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java +++ b/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java @@ -1926,14 +1926,6 @@ public class CompressedMatrixBlock extends MatrixBlock implements Externalizable } @Override - public void unaryOperationsInPlace(UnaryOperator op) - throws DMLRuntimeException { - printDecompressWarning("unaryOperationsInPlace"); - MatrixBlock tmp = isCompressed() ? decompress() : this; - tmp.unaryOperationsInPlace(op); - } - - @Override public MatrixValue binaryOperations(BinaryOperator op, MatrixValue thatValue, MatrixValue result) throws DMLRuntimeException { printDecompressWarning("binaryOperations", (MatrixBlock)thatValue); http://git-wip-us.apache.org/repos/asf/systemml/blob/63ad279f/src/main/java/org/apache/sysml/runtime/matrix/data/CM_N_COVCell.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/CM_N_COVCell.java b/src/main/java/org/apache/sysml/runtime/matrix/data/CM_N_COVCell.java index cd9a995..b74ff10 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/CM_N_COVCell.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/CM_N_COVCell.java @@ -172,12 +172,6 @@ public class CM_N_COVCell extends MatrixValue implements WritableComparable } @Override - public void unaryOperationsInPlace(UnaryOperator op) - throws DMLRuntimeException { - throw new DMLRuntimeException("operation not supported fro WeightedCell"); - } - - @Override public void readFields(DataInput in) throws IOException { cm.w=in.readDouble(); cm.mean.read(in); http://git-wip-us.apache.org/repos/asf/systemml/blob/63ad279f/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlock.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlock.java b/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlock.java index 3d82969..574f508 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlock.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlock.java @@ -80,6 +80,21 @@ public abstract class DenseBlock implements Serializable public abstract int numBlocks(); /** + * Get the number of rows per block, except last one. + * + * @return number of rows in block + */ + public abstract int blockSize(); + + /** + * Get the number of rows of the given block. + * + * @param bix block index + * @return number of rows in block + */ + public abstract int blockSize(int bix); + + /** * Get the length of the dense block as the product * of row and column dimensions. * @@ -88,6 +103,15 @@ public abstract class DenseBlock implements Serializable public abstract long size(); /** + * Get the length of the given block. + * + * @param bix block index + * @return length + */ + public abstract int size(int bix); + + + /** * Get the total length of allocated blocks. * * @return capacity @@ -196,6 +220,14 @@ public abstract class DenseBlock implements Serializable public abstract void set(int r, double[] v); /** + * Copy the given dense block. + * + * @param db dense block + */ + public abstract void set(DenseBlock db); + + + /** * Get the value for a given row and column. * * @param r row index http://git-wip-us.apache.org/repos/asf/systemml/blob/63ad279f/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlockDRB.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlockDRB.java b/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlockDRB.java index e0d9443..d2eb5ca 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlockDRB.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlockDRB.java @@ -74,11 +74,26 @@ public class DenseBlockDRB extends DenseBlock public int numBlocks() { return 1; } + + @Override + public int blockSize() { + return rlen; + } + + @Override + public int blockSize(int bix) { + return rlen; + } @Override public long size() { return rlen * clen; } + + @Override + public int size(int bix) { + return rlen * clen; + } @Override public long capacity() { @@ -150,6 +165,11 @@ public class DenseBlockDRB extends DenseBlock public void set(int r, int c, double v) { data[pos(r, c)] = v; } + + @Override + public void set(DenseBlock db) { + System.arraycopy(db.values(0), 0, data, 0, rlen*clen); + } @Override public void set(int r, double[] v) { http://git-wip-us.apache.org/repos/asf/systemml/blob/63ad279f/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlockLDRB.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlockLDRB.java b/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlockLDRB.java index c6ded3a..926f7ff 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlockLDRB.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/DenseBlockLDRB.java @@ -86,11 +86,26 @@ public class DenseBlockLDRB extends DenseBlock public int numBlocks() { return data.length; } + + @Override + public int blockSize() { + return blen; + } + + @Override + public int blockSize(int bix) { + return Math.min(blen, rlen-bix*blen); + } @Override public long size() { return (long)rlen * clen; } + + @Override + public int size(int bix) { + return blockSize(bix) * clen; + } @Override public long capacity() { @@ -116,7 +131,8 @@ public class DenseBlockLDRB extends DenseBlock long nnz = 0; for(int bi=index(rl); bi<index(ru); bi++) { double[] a = data[bi]; - for(int i=pos(bi), ix=pos(bi)*clen; i<blen(bi); i++, ix+=clen) + int blen = blockSize(bi); + for(int i=pos(bi), ix=pos(bi)*clen; i<blen; i++, ix+=clen) for( int j=cl; j<cu; j++ ) nnz += (a[ix+j]!=0) ? 1 : 0; } @@ -171,7 +187,13 @@ public class DenseBlockLDRB extends DenseBlock @Override public void set(int r, double[] v) { - System.arraycopy(v, 0, data[index(r)], pos(r), v.length); + System.arraycopy(v, 0, data[index(r)], pos(r), clen); + } + + @Override + public void set(DenseBlock db) { + for(int bi=0; bi<numBlocks(); bi++) + System.arraycopy(db.values(bi), 0, data[bi], 0, size(bi)); } @Override @@ -193,10 +215,6 @@ public class DenseBlockLDRB extends DenseBlock } return sb.toString(); } - - private int blen(int bix) { - return Math.min(blen, rlen-bix*blen); - } private static int blocksize(int rlen, int clen) { return Math.min(rlen, Integer.MAX_VALUE / clen); http://git-wip-us.apache.org/repos/asf/systemml/blob/63ad279f/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 e515947..6353388 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 @@ -202,10 +202,10 @@ public class LibMatrixBincell throws DMLRuntimeException { boolean skipEmpty = (op.fn instanceof Multiply - || isSparseSafeDivide(op, m2) ); + || isSparseSafeDivide(op, m2) ); //skip empty blocks (since sparse-safe) - if( m1.isEmptyBlock(false) && m2.isEmptyBlock(false) + if( m1.isEmptyBlock(false) && m2.isEmptyBlock(false) || skipEmpty && (m1.isEmptyBlock(false) || m2.isEmptyBlock(false)) ) { return; @@ -265,64 +265,79 @@ public class LibMatrixBincell return; // skip entire empty block ret.allocateDenseBlock(); - double[] a = (m1.denseBlock != null) ? m1.getDenseBlockValues() : null; - double[] b = (m2.denseBlock != null) ? m2.getDenseBlockValues() : null; - double[] c = ret.getDenseBlockValues(); - int nnz = 0; + DenseBlock da = m1.getDenseBlock(); + DenseBlock dc = ret.getDenseBlock(); + long nnz = 0; if( atype == BinaryAccessType.MATRIX_COL_VECTOR ) { - for( int i=0, ix=0; i<rlen; i++, ix+=clen ) - { - //replicate vector value - double v2 = (b==null) ? 0 : b[i]; - if( skipEmpty && v2 == 0 ) //skip empty rows - continue; - - if( isMultiply && v2 == 1 ) { //ROW COPY - //a guaranteed to be non-null (see early abort) - System.arraycopy(a, ix, c, ix, clen); - nnz += m1.recomputeNonZeros(i, i, 0, clen-1); - } - else { //GENERAL CASE - if( a != null ) - for( int j=0; j<clen; j++ ) { - c[ix+j] = op.fn.execute( a[ix+j], v2 ); - nnz += (c[ix+j] != 0) ? 1 : 0; + double[] b = m2.getDenseBlockValues(); // always single block + + for( int bi=0; bi<dc.numBlocks(); bi++ ) { + double[] a = da.values(bi); + double[] c = dc.values(bi); + int len = dc.blockSize(bi); + int off = bi * dc.blockSize(); + for( int i=0, ix=0; i<len; i++, ix+=clen ) + { + //replicate vector value + double v2 = (b==null) ? 0 : b[off+i]; + if( skipEmpty && v2 == 0 ) //skip empty rows + continue; + + if( isMultiply && v2 == 1 ) { //ROW COPY + //a guaranteed to be non-null (see early abort) + System.arraycopy(a, ix, c, ix, clen); + nnz += m1.recomputeNonZeros(i, i, 0, clen-1); + } + else { //GENERAL CASE + if( a != null ) + for( int j=0; j<clen; j++ ) { + c[ix+j] = op.fn.execute( a[ix+j], v2 ); + nnz += (c[ix+j] != 0) ? 1 : 0; + } + else { + double val = op.fn.execute( 0, v2 ); + Arrays.fill(c, ix, ix+clen, val); + nnz += (val != 0) ? clen : 0; } - else { - double val = op.fn.execute( 0, v2 ); - Arrays.fill(c, ix, ix+clen, val); - nnz += (val != 0) ? clen : 0; } } } } else if( atype == BinaryAccessType.MATRIX_ROW_VECTOR ) { - if( a==null && b==null ) { //both empty + double[] b = m2.getDenseBlockValues(); // always single block + + if( da==null && b==null ) { //both empty double v = op.fn.execute( 0, 0 ); - Arrays.fill(c, 0, rlen*clen, v); - nnz += (v != 0) ? rlen*clen : 0; + dc.set(v); + nnz += (v != 0) ? (long)rlen*clen : 0; } - else if( a==null ) //left empty + else if( da==null ) //left empty { //compute first row + double[] c = dc.values(0); for( int j=0; j<clen; j++ ) { c[j] = op.fn.execute( 0, b[j] ); nnz += (c[j] != 0) ? rlen : 0; } //copy first to all other rows - for( int i=1, ix=clen; i<rlen; i++, ix+=clen ) - System.arraycopy(c, 0, c, ix, clen); + for( int i=1; i<rlen; i++ ) + dc.set(i, c); } else //default case (incl right empty) { - for( int i=0, ix=0; i<rlen; i++, ix+=clen ) - for( int j=0; j<clen; j++ ) { - c[ix+j] = op.fn.execute( a[ix+j], ((b!=null) ? b[j] : 0) ); - nnz += (c[ix+j] != 0) ? 1 : 0; - } + for( int bi=0; bi<dc.numBlocks(); bi++ ) { + double[] a = da.values(bi); + double[] c = dc.values(bi); + int len = dc.blockSize(bi); + for( int i=0, ix=0; i<len; i++, ix+=clen ) + for( int j=0; j<clen; j++ ) { + c[ix+j] = op.fn.execute( a[ix+j], ((b!=null) ? b[j] : 0) ); + nnz += (c[ix+j] != 0) ? 1 : 0; + } + } } } @@ -466,19 +481,17 @@ public class LibMatrixBincell if(isMultiply && v2 == 1) //ROW COPY { - for( int j=0; j<clen; j++ ) - { + for( int j=0; j<clen; j++ ) { double v1 = m1.quickGetValue(i, j); - ret.appendValue(i, j, v1); + ret.appendValue(i, j, v1); } } else //GENERAL CASE { - for( int j=0; j<clen; j++ ) - { + for( int j=0; j<clen; j++ ) { double v1 = m1.quickGetValue(i, j); double v = op.fn.execute( v1, v2 ); - ret.appendValue(i, j, v); + ret.appendValue(i, j, v); } } } @@ -492,34 +505,31 @@ public class LibMatrixBincell { //note: sparse block guaranteed to be allocated (otherwise early about) SparseBlock b = m2.sparseBlock; - if( !b.isEmpty(0) ) - { - int blen = b.size(0); //always pos 0 - int[] bix = b.indexes(0); - double[] bvals = b.values(0); - for( int i=0; i<rlen; i++ ) { - //for each row iterate only over non-zeros elements in rhs - for( int j=0; j<blen; j++ ) { - double v1 = m1.quickGetValue(i, bix[j]); - double v = op.fn.execute( v1, bvals[j] ); - ret.appendValue(i, bix[j], v); - } + if( b.isEmpty(0) ) return; + int blen = b.size(0); //always pos 0 + int[] bix = b.indexes(0); + double[] bvals = b.values(0); + for( int i=0; i<rlen; i++ ) { + //for each row iterate only over non-zeros elements in rhs + for( int j=0; j<blen; j++ ) { + double v1 = m1.quickGetValue(i, bix[j]); + double v = op.fn.execute( v1, bvals[j] ); + ret.appendValue(i, bix[j], v); } } } else //GENERAL CASE { for( int i=0; i<rlen; i++ ) - for( int j=0; j<clen; j++ ) - { + for( int j=0; j<clen; j++ ) { double v1 = m1.quickGetValue(i, j); double v2 = m2.quickGetValue(0, j); //replicated vector value double v = op.fn.execute( v1, v2 ); - ret.appendValue(i, j, v); + ret.appendValue(i, j, v); } } } - + //no need to recomputeNonZeros since maintained in append value } @@ -540,8 +550,7 @@ public class LibMatrixBincell else { for(int r=0; r<rlen; r++) { double v1 = m1.quickGetValue(r, 0); - for(int c=0; c<clen; c++) - { + for(int c=0; c<clen; c++) { double v2 = m2.quickGetValue(0, c); double v = op.fn.execute( v1, v2 ); ret.appendValue(r, c, v); @@ -629,72 +638,79 @@ public class LibMatrixBincell { //specific case in order to prevent binary search on sparse inputs (see quickget and quickset) ret.allocateDenseBlock(); - final int m = ret.rlen; final int n = ret.clen; - double[] c = ret.getDenseBlockValues(); + DenseBlock dc = ret.getDenseBlock(); //1) process left input: assignment - if( m1.sparse ) //SPARSE left + if( m1.sparse && m1.sparseBlock != null ) //SPARSE left { - if( m1.sparseBlock != null ) - { - SparseBlock a = m1.sparseBlock; - - for( int i=0, ix=0; i<m; i++, ix+=n ) { - 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 k = apos; k < apos+alen; k++) - c[ix+aix[k]] = avals[k]; - } + SparseBlock a = m1.sparseBlock; + for( int bi=0; bi<dc.numBlocks(); bi++ ) { + double[] c = dc.values(bi); + int blen = dc.blockSize(bi); + int off = bi * dc.blockSize(); + for( int i=0, ix=0; i<blen; i++, ix+=n ) { + int ai = off + i; + if( a.isEmpty(ai) ) continue; + int apos = a.pos(ai); + int alen = a.size(ai); + int[] aix = a.indexes(ai); + double[] avals = a.values(ai); + for(int k = apos; k < apos+alen; k++) + c[ix+aix[k]] = avals[k]; } } } - else //DENSE left + else if( !m1.sparse ) //DENSE left { if( !m1.isEmptyBlock(false) ) - System.arraycopy(m1.getDenseBlockValues(), 0, c, 0, m*n); + dc.set(m1.getDenseBlock()); else - ret.denseBlock.set(0); + dc.set(0); } //2) process right input: op.fn (+,-,*), * only if dense long lnnz = 0; - if( m2.sparse ) //SPARSE right + if( m2.sparse && m2.sparseBlock!=null ) //SPARSE right { - if(m2.sparseBlock!=null) - { - SparseBlock a = m2.sparseBlock; - - for( int i=0, ix=0; i<m; i++, ix+=n ) { - if( !a.isEmpty(i) ) { - int apos = a.pos(i); - int alen = a.size(i); - int[] aix = a.indexes(i); - double[] avals = a.values(i); + SparseBlock a = m2.sparseBlock; + for( int bi=0; bi<dc.numBlocks(); bi++ ) { + double[] c = dc.values(bi); + int blen = dc.blockSize(bi); + int off = bi * dc.blockSize(); + for( int i=0, ix=0; i<blen; i++, ix+=n ) { + int ai = off + i; + if( !a.isEmpty(ai) ) { + int apos = a.pos(ai); + int alen = a.size(ai); + int[] aix = a.indexes(ai); + double[] avals = a.values(ai); for(int k = apos; k < apos+alen; k++) c[ix+aix[k]] = op.fn.execute(c[ix+aix[k]], avals[k]); } //exploit temporal locality of rows - lnnz += ret.recomputeNonZeros(i, i, 0, n-1); + lnnz += ret.recomputeNonZeros(ai, ai, 0, n-1); } } } - else //DENSE right + else if( !m2.sparse ) //DENSE right { if( !m2.isEmptyBlock(false) ) { - double[] a = m2.getDenseBlockValues(); - for( int i=0; i<m*n; i++ ) { - c[i] = op.fn.execute(c[i], a[i]); - lnnz += (c[i]!=0) ? 1 : 0; + for( int bi=0; bi<dc.numBlocks(); bi++ ) { + double[] a = m2.getDenseBlock().values(bi); + double[] c = dc.values(bi); + int len = dc.size(bi); + for( int i=0; i<len; i++ ) { + c[i] = op.fn.execute(c[i], a[i]); + lnnz += (c[i]!=0) ? 1 : 0; + } } } else if(op.fn instanceof Multiply) ret.denseBlock.set(0); + else + lnnz = m1.nonZeros; } //3) recompute nnz @@ -705,18 +721,22 @@ public class LibMatrixBincell throws DMLRuntimeException { ret.allocateDenseBlock(); - final int m = ret.rlen; - final int n = ret.clen; - double[] a = m1.getDenseBlockValues(); - double[] b = m2.getDenseBlockValues(); - double[] c = ret.getDenseBlockValues(); + DenseBlock da = m1.getDenseBlock(); + DenseBlock db = m2.getDenseBlock(); + DenseBlock dc = ret.getDenseBlock(); ValueFunction fn = op.fn; //compute dense-dense binary, maintain nnz on-the-fly - int lnnz = 0; - for( int i=0; i<m*n; i++ ) { - c[i] = fn.execute(a[i], b[i]); - lnnz += (c[i]!=0)? 1 : 0; + long lnnz = 0; + for( int bi=0; bi<da.numBlocks(); bi++ ) { + double[] a = da.values(bi); + double[] b = db.values(bi); + double[] c = dc.values(bi); + int len = da.size(bi); + for( int i=0; i<len; i++ ) { + c[i] = fn.execute(a[i], b[i]); + lnnz += (c[i]!=0)? 1 : 0; + } } ret.setNonZeros(lnnz); } @@ -774,15 +794,15 @@ public class LibMatrixBincell * @param bOp binary operator * */ - private static void performBinOuterOperation(MatrixBlock mbLeft, MatrixBlock mbRight, MatrixBlock mbOut, BinaryOperator bOp) + private static void performBinOuterOperation(MatrixBlock m1, MatrixBlock m2, MatrixBlock ret, BinaryOperator bOp) throws DMLRuntimeException { - int rlen = mbLeft.rlen; - int clen = mbOut.clen; - double b[] = DataConverter.convertToDoubleVector(mbRight); - if(!mbOut.isAllocated()) - mbOut.allocateDenseBlock(); - double c[] = mbOut.getDenseBlockValues(); + int rlen = m1.rlen; + int clen = ret.clen; + double b[] = DataConverter.convertToDoubleVector(m2); + if(!ret.isAllocated()) + ret.allocateDenseBlock(); + DenseBlock dc = ret.getDenseBlock(); //pre-materialize various types used in inner loop boolean scanType1 = (bOp.fn instanceof LessThan || bOp.fn instanceof Equals @@ -794,31 +814,34 @@ public class LibMatrixBincell boolean eqNeq = (bOp.fn instanceof Equals || bOp.fn instanceof NotEquals); long lnnz = 0; - for( int r=0, off=0; r<rlen; r++, off+=clen ) { - double value = mbLeft.quickGetValue(r, 0); - int ixPos1 = Arrays.binarySearch(b, value); - int ixPos2 = ixPos1; - if( ixPos1 >= 0 ) { //match, scan to next val - if(scanType1) while( ixPos1<b.length && value==b[ixPos1] ) ixPos1++; - if(scanType2) while( ixPos2 > 0 && value==b[ixPos2-1]) --ixPos2; - } - else - ixPos2 = ixPos1 = Math.abs(ixPos1) - 1; - int start = lt ? ixPos1 : (lte||eqNeq) ? ixPos2 : 0; - int end = gt ? ixPos2 : (gte||eqNeq) ? ixPos1 : clen; - - if (bOp.fn instanceof NotEquals) { - Arrays.fill(c, off, off+start, 1.0); - Arrays.fill(c, off+end, off+clen, 1.0); - lnnz += (start+(clen-end)); - } - else if( start < end ) { - Arrays.fill(c, off+start, off+end, 1.0); - lnnz += (end-start); + for( int bi=0; bi<dc.numBlocks(); bi++ ) { + double[] c = dc.values(bi); + for( int r=bi*dc.blockSize(), off=0; r<rlen; r++, off+=clen ) { + double value = m1.quickGetValue(r, 0); + int ixPos1 = Arrays.binarySearch(b, value); + int ixPos2 = ixPos1; + if( ixPos1 >= 0 ) { //match, scan to next val + if(scanType1) while( ixPos1<b.length && value==b[ixPos1] ) ixPos1++; + if(scanType2) while( ixPos2 > 0 && value==b[ixPos2-1]) --ixPos2; + } + else + ixPos2 = ixPos1 = Math.abs(ixPos1) - 1; + int start = lt ? ixPos1 : (lte||eqNeq) ? ixPos2 : 0; + int end = gt ? ixPos2 : (gte||eqNeq) ? ixPos1 : clen; + + if (bOp.fn instanceof NotEquals) { + Arrays.fill(c, off, off+start, 1.0); + Arrays.fill(c, off+end, off+clen, 1.0); + lnnz += (start+(clen-end)); + } + else if( start < end ) { + Arrays.fill(c, off+start, off+end, 1.0); + lnnz += (end-start); + } } } - mbOut.setNonZeros(lnnz); - mbOut.examSparsity(); + ret.setNonZeros(lnnz); + ret.examSparsity(); } private static void unsafeBinary(MatrixBlock m1, MatrixBlock m2, MatrixBlock ret, BinaryOperator op) @@ -870,7 +893,7 @@ public class LibMatrixBincell } else // MATRIX - MATRIX { - //dense non-empty vectors + //dense non-empty vectors (always single block) if( m1.clen==1 && !m1.sparse && !m1.isEmptyBlock(false) && !m2.sparse && !m2.isEmptyBlock(false) ) { @@ -991,18 +1014,20 @@ public class LibMatrixBincell ret.allocateDenseBlock(); SparseBlock a = m1.sparseBlock; - double[] c = ret.getDenseBlockValues(); + DenseBlock dc = ret.getDenseBlock(); int m = m1.rlen; int n = m1.clen; //init dense result with unsafe 0-value - double cval0 = op.executeScalar(0); - Arrays.fill(c, cval0); + dc.set(op.executeScalar(0)); //compute non-zero input values - int nnz = m*n; - for(int i=0, cix=0; i<m; i++, cix+=n) { - if( !a.isEmpty(i) ) { + long nnz = m * n; + for(int bi=0; bi<dc.numBlocks(); bi++) { + int blen = dc.blockSize(bi); + double[] c = dc.values(bi); + for(int i=bi*dc.blockSize(), cix=i*n; i<blen && i<m; i++, cix+=n) { + if( a.isEmpty(i) ) continue; int apos = a.pos(i); int alen = a.size(i); int[] aix = a.indexes(i); @@ -1027,15 +1052,19 @@ public class LibMatrixBincell //allocate dense block (if necessary), incl clear nnz ret.allocateDenseBlock(true); - double[] a = m1.getDenseBlockValues(); - double[] c = ret.getDenseBlockValues(); + DenseBlock da = m1.getDenseBlock(); + DenseBlock dc = ret.getDenseBlock(); //compute scalar operation, incl nnz maintenance - int limit = m1.rlen*m1.clen; - int nnz = 0; - for( int i=0; i<limit; i++ ) { - c[i] = op.executeScalar( a[i] ); - nnz += (c[i] != 0) ? 1 : 0; + long nnz = 0; + for( int bi=0; bi<da.numBlocks(); bi++) { + double[] a = da.values(bi); + double[] c = dc.values(bi); + int limit = da.size(bi); + for( int i=0; i<limit; i++ ) { + c[i] = op.executeScalar( a[i] ); + nnz += (c[i] != 0) ? 1 : 0; + } } ret.nonZeros = nnz; } @@ -1104,20 +1133,18 @@ public class LibMatrixBincell appendRightForSparseBinary(op, b.values(r), b.indexes(r), b.pos(r), b.size(r), 0, r, m1ret); } } - } + } } else if(m1ret.sparseBlock==null) { m1ret.sparseBlock = SparseBlockFactory.createSparseBlock(rlen); - - for(int r=0; r<rlen; r++) - { + for(int r=0; r<rlen; r++) { if( !b.isEmpty(r) ) { SparseRow tmp = new SparseRowVector( b.size(r), clen ); appendRightForSparseBinary(op, b.values(r), b.indexes(r), b.pos(r), b.size(r), 0, r, m1ret); m1ret.sparseBlock.set(r, tmp, false); } - } + } } else //that.sparseRows==null { @@ -1143,13 +1170,12 @@ public class LibMatrixBincell else //one side dense { for(int r=0; r<rlen; r++) - for(int c=0; c<clen; c++) - { + for(int c=0; c<clen; c++) { double thisvalue = m1ret.quickGetValue(r, c); double thatvalue = m2.quickGetValue(r, c); double resultvalue = op.fn.execute(thisvalue, thatvalue); m1ret.quickSetValue(r, c, resultvalue); - } + } } } @@ -1161,14 +1187,11 @@ public class LibMatrixBincell if( atype == BinaryAccessType.MATRIX_COL_VECTOR ) //MATRIX - COL_VECTOR { - for(int r=0; r<rlen; r++) - { + for(int r=0; r<rlen; r++) { //replicated value double v2 = m2.quickGetValue(r, 0); - - for(int c=0; c<clen; c++) - { - double v1 = m1ret.quickGetValue(r, c); + for(int c=0; c<clen; c++) { + double v1 = m1ret.quickGetValue(r, c); double v = op.fn.execute( v1, v2 ); m1ret.quickSetValue(r, c, v); } @@ -1177,8 +1200,7 @@ public class LibMatrixBincell else if( atype == BinaryAccessType.MATRIX_ROW_VECTOR ) //MATRIX - ROW_VECTOR { for(int r=0; r<rlen; r++) - for(int c=0; c<clen; c++) - { + for(int c=0; c<clen; c++) { double v1 = m1ret.quickGetValue(r, c); double v2 = m2.quickGetValue(0, c); //replicated value double v = op.fn.execute( v1, v2 ); @@ -1188,8 +1210,7 @@ public class LibMatrixBincell else // MATRIX - MATRIX { for(int r=0; r<rlen; r++) - for(int c=0; c<clen; c++) - { + for(int c=0; c<clen; c++) { double v1 = m1ret.quickGetValue(r, c); double v2 = m2.quickGetValue(r, c); double v = op.fn.execute( v1, v2 ); http://git-wip-us.apache.org/repos/asf/systemml/blob/63ad279f/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 f307d78..7a334a4 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 @@ -1094,10 +1094,10 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab final int n = clen; //allocate target in memory-efficient CSR format - int nnz = (int) nonZeros; + int lnnz = (int) nonZeros; int[] rptr = new int[m+1]; - int[] indexes = new int[nnz]; - double[] values = new double[nnz]; + 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]; @@ -1110,10 +1110,9 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab rptr[i+1]=pos; } sparseBlock = new SparseBlockCSR( - rptr, indexes, values, nnz); + rptr, indexes, values, lnnz); //update nnz and cleanup dense block - nonZeros = nnz; denseBlock = null; } @@ -2626,7 +2625,7 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab //allocate output if( ret == null ) ret = new MatrixBlock(rlen, clen, sp, this.nonZeros); - else + else ret.reset(rlen, clen, sp); //core execute @@ -2663,7 +2662,6 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab return; final int m = rlen; - final int n = clen; if( sparse && ret.sparse ) //SPARSE <- SPARSE { @@ -2691,7 +2689,7 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab } else if( sparse ) //DENSE <- SPARSE { - SparseBlock a = sparseBlock; + SparseBlock a = sparseBlock; for(int i=0; i<m; i++) { if( a.isEmpty(i) ) continue; @@ -2712,15 +2710,19 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab { //allocate dense output block ret.allocateDenseBlock(); - double[] a = getDenseBlockValues(); - double[] c = ret.getDenseBlockValues(); - int len = m * n; + DenseBlock da = getDenseBlock(); + DenseBlock dc = ret.getDenseBlock(); //unary op, incl nnz maintenance - int nnz = 0; - for( int i=0; i<len; i++ ) { - c[i] = op.fn.execute(a[i]); - nnz += (c[i] != 0) ? 1 : 0; + long nnz = 0; + for( int bi=0; bi<da.numBlocks(); bi++ ) { + double[] a = da.values(bi); + double[] c = dc.values(bi); + int len = da.size(bi); + for( int i=0; i<len; i++ ) { + c[i] = op.fn.execute(a[i]); + nnz += (c[i] != 0) ? 1 : 0; + } } ret.nonZeros = nnz; } @@ -2750,113 +2752,6 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab } @Override - public void unaryOperationsInPlace(UnaryOperator op) - throws DMLRuntimeException - { - if(op.sparseSafe) - sparseUnaryOperationsInPlace(op); - else - denseUnaryOperationsInPlace(op); - } - - /** - * only apply to non zero cells - * - * @param op unary operator - * @throws DMLRuntimeException if DMLRuntimeException occurs - */ - private void sparseUnaryOperationsInPlace(UnaryOperator op) - throws DMLRuntimeException - { - //early abort possible since sparse-safe - if( isEmptyBlock(false) ) - return; - - if(sparse) - { - nonZeros=0; - for(int r=0; r<Math.min(rlen, sparseBlock.numRows()); r++) - { - if(sparseBlock.isEmpty(r)) - continue; - - int apos = sparseBlock.pos(r); - int alen = sparseBlock.size(r); - int[] aix = sparseBlock.indexes(r); - double[] avals = sparseBlock.values(r); - - int pos=0; - for(int i=apos; i<apos+alen; i++) - { - double v=op.fn.execute(avals[i]); - if(v!=0) { - avals[pos]=v; - aix[pos]=aix[i]; - pos++; - nonZeros++; - } - } - //TODO perf sparse block: truncate replaced by deleteIndexrange - sparseBlock.deleteIndexRange(r, pos, clen); - } - - } - else - { - double[] a = getDenseBlockValues(); - int limit = rlen*clen; - long nnz = 0; - for(int i=0; i<limit; i++) { - a[i] = op.fn.execute(a[i]); - if(a[i] != 0) - nnz++; - } - nonZeros = nnz; - } - } - - private void denseUnaryOperationsInPlace(UnaryOperator op) - throws DMLRuntimeException - { - if( sparse ) //SPARSE MATRIX - { - double v; - for(int r=0; r<rlen; r++) - for(int c=0; c<clen; c++) - { - v=op.fn.execute(quickGetValue(r, c)); - quickSetValue(r, c, v); - } - } - else//DENSE MATRIX - { - //early abort not possible because not sparsesafe - if(denseBlock==null) - allocateDenseBlock(); - - //compute values in-place and update nnz - double[] a = getDenseBlockValues(); - final int limit = rlen*clen; - int lnnz = 0; - for( int i=0; i<limit; i++ ) { - a[i] = op.fn.execute(a[i]); - if( a[i]!=0 ) - lnnz++; - } - nonZeros = lnnz; - - //IBM JVM bug (JDK6) causes crash for certain inputs (w/ infinities) - //nonZeros = 0; - //for(int i=0; i<limit; i++) - //{ - // denseBlock[i]=op.fn.execute(denseBlock[i]); - // if(denseBlock[i]!=0) - // nonZeros++; - //} - } - } - - @Override public MatrixValue binaryOperations(BinaryOperator op, MatrixValue thatValue, MatrixValue result) throws DMLRuntimeException { @@ -2869,7 +2764,7 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab //compute output dimensions boolean outer = (LibMatrixBincell.getBinaryAccessType(this, that) - == BinaryAccessType.OUTER_VECTOR_VECTOR); + == BinaryAccessType.OUTER_VECTOR_VECTOR); int rows = rlen; int cols = outer ? that.clen : clen; http://git-wip-us.apache.org/repos/asf/systemml/blob/63ad279f/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixCell.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixCell.java b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixCell.java index 7e82c43..b1190ad 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixCell.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixCell.java @@ -266,12 +266,6 @@ public class MatrixCell extends MatrixValue implements WritableComparable, Seria return c3; } - @Override - public void unaryOperationsInPlace(UnaryOperator op) - throws DMLRuntimeException { - value=op.fn.execute(value); - } - public int compareTo(MatrixCell o) { return Double.compare(this.value, o.value); } http://git-wip-us.apache.org/repos/asf/systemml/blob/63ad279f/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixValue.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixValue.java b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixValue.java index e0a9579..c6361bc 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixValue.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixValue.java @@ -41,7 +41,6 @@ import org.apache.sysml.runtime.util.UtilFunctions; @SuppressWarnings("rawtypes") public abstract class MatrixValue implements WritableComparable { - static public class CellIndex { public int row; public int column; @@ -152,8 +151,6 @@ public abstract class MatrixValue implements WritableComparable public abstract MatrixValue unaryOperations(UnaryOperator op, MatrixValue result) throws DMLRuntimeException; - - public abstract void unaryOperationsInPlace(UnaryOperator op) throws DMLRuntimeException; public abstract void incrementalAggregate(AggregateOperator aggOp, MatrixValue correction, MatrixValue newWithCorrection) throws DMLRuntimeException; http://git-wip-us.apache.org/repos/asf/systemml/blob/63ad279f/src/main/java/org/apache/sysml/runtime/matrix/data/WeightedCell.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/WeightedCell.java b/src/main/java/org/apache/sysml/runtime/matrix/data/WeightedCell.java index f111111..faad3d2 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/WeightedCell.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/WeightedCell.java @@ -174,10 +174,4 @@ public class WeightedCell extends MatrixCell c3.setWeight(weight); return c3; } - - @Override - public void unaryOperationsInPlace(UnaryOperator op) - throws DMLRuntimeException { - value=op.fn.execute(value); - } }
