You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemml.apache.org by mb...@apache.org on 2016/08/11 19:00:20 UTC
[1/2] incubator-systemml git commit: [SYSTEMML-821] Various cleanups
OLE/RLE compressed column groups
Repository: incubator-systemml
Updated Branches:
refs/heads/master d0cae2318 -> 2137a7e4a
[SYSTEMML-821] Various cleanups OLE/RLE compressed column groups
Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/b1dc0d5b
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/b1dc0d5b
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/b1dc0d5b
Branch: refs/heads/master
Commit: b1dc0d5bf17c61b949404bc7ea1a9e9f497ad627
Parents: d0cae23
Author: Matthias Boehm <mb...@us.ibm.com>
Authored: Tue Aug 9 23:00:03 2016 -0700
Committer: Matthias Boehm <mb...@us.ibm.com>
Committed: Thu Aug 11 11:52:09 2016 -0700
----------------------------------------------------------------------
.../sysml/runtime/compress/ColGroupBitmap.java | 21 +-
.../sysml/runtime/compress/ColGroupOLE.java | 254 ++++++++++---------
.../sysml/runtime/compress/ColGroupRLE.java | 211 ++++++++-------
3 files changed, 262 insertions(+), 224 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b1dc0d5b/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java b/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java
index 0ab65f1..005673c 100644
--- a/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java
+++ b/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java
@@ -295,7 +295,7 @@ public abstract class ColGroupBitmap extends ColGroup
* @param bitmapIx
* @return
*/
- protected double sumValues(int bitmapIx)
+ protected final double sumValues(int bitmapIx)
{
final int numCols = getNumCols();
final int valOff = bitmapIx * numCols;
@@ -308,7 +308,7 @@ public abstract class ColGroupBitmap extends ColGroup
return val;
}
- protected double sumValues(int bitmapIx, double[] b)
+ protected final double sumValues(int bitmapIx, double[] b)
{
final int numCols = getNumCols();
final int valOff = bitmapIx * numCols;
@@ -326,7 +326,7 @@ public abstract class ColGroupBitmap extends ColGroup
* @param b
* @param c
*/
- protected void sumAllValues(double[] b, double[] c)
+ protected final void sumAllValues(double[] b, double[] c)
{
final int numVals = getNumValues();
final int numCols = getNumCols();
@@ -337,6 +337,21 @@ public abstract class ColGroupBitmap extends ColGroup
LinearAlgebraUtils.vectMultiplyAdd(b[i], _values, c, off, 0, numVals);
}
+
+ /**
+ *
+ * @param numVals
+ * @param sb
+ * @return
+ */
+ protected final double[] preaggValues(int numVals, double[] b) {
+ double[] ret = new double[numVals];
+ for( int k = 0; k < numVals; k++ )
+ ret[k] = sumValues(k, b);
+
+ return ret;
+ }
+
/**
* Method for use by subclasses. Applies a scalar operation to the value
* metadata stored in the superclass.
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b1dc0d5b/src/main/java/org/apache/sysml/runtime/compress/ColGroupOLE.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/compress/ColGroupOLE.java b/src/main/java/org/apache/sysml/runtime/compress/ColGroupOLE.java
index 8a0285e..81d57dc 100644
--- a/src/main/java/org/apache/sysml/runtime/compress/ColGroupOLE.java
+++ b/src/main/java/org/apache/sysml/runtime/compress/ColGroupOLE.java
@@ -84,13 +84,13 @@ public class ColGroupOLE extends ColGroupBitmap
_skiplist = new int[numVals];
int rl = (getNumRows()/2/blksz)*blksz;
for (int k = 0; k < numVals; k++) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
- int bufIx = 0;
- for( int i=0; i<rl && bufIx<bitmapLen; i+=blksz ) {
- bufIx += _data[bitmapOff+bufIx] + 1;
+ int boff = _ptr[k];
+ int blen = len(k);
+ int bix = 0;
+ for( int i=0; i<rl && bix<blen; i+=blksz ) {
+ bix += _data[boff+bix] + 1;
}
- _skiplist[k] = bufIx;
+ _skiplist[k] = bix;
}
}
}
@@ -125,13 +125,13 @@ public class ColGroupOLE extends ColGroupBitmap
//cache conscious append via horizontal scans
for( int bi=0; bi<n; bi+=blksz ) {
for (int k = 0, off=0; k < numVals; k++, off+=numCols) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
- int bufIx = apos[k];
- if( bufIx >= bitmapLen )
+ int boff = _ptr[k];
+ int blen = len(k);
+ int bix = apos[k];
+ if( bix >= blen )
continue;
- int len = _data[bitmapOff+bufIx];
- int pos = bitmapOff+bufIx+1;
+ int len = _data[boff+bix];
+ int pos = boff+bix+1;
for( int i=pos; i<pos+len; i++ )
for( int j=0, rix = bi+_data[i]; j<numCols; j++ )
if( _values[off+j]!=0 )
@@ -168,13 +168,13 @@ public class ColGroupOLE extends ColGroupBitmap
//cache conscious append via horizontal scans
for( int bi=0; bi<n; bi+=blksz ) {
for (int k = 0, off=0; k < numVals; k++, off+=numCols) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
- int bufIx = apos[k];
- if( bufIx >= bitmapLen )
+ int boff = _ptr[k];
+ int blen = len(k);
+ int bix = apos[k];
+ if( bix >= blen )
continue;
- int len = _data[bitmapOff+bufIx];
- int pos = bitmapOff+bufIx+1;
+ int len = _data[boff+bix];
+ int pos = boff+bix+1;
for( int i=pos; i<pos+len; i++ )
for( int j=0, rix = bi+_data[i]; j<numCols; j++ )
if( _values[off+j]!=0 )
@@ -207,13 +207,13 @@ public class ColGroupOLE extends ColGroupBitmap
//cache conscious append via horizontal scans
for( int bi=0; bi<n; bi+=blksz ) {
for (int k = 0, off=0; k < numVals; k++, off+=numCols) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
- int bufIx = apos[k];
- if( bufIx >= bitmapLen )
+ int boff = _ptr[k];
+ int blen = len(k);
+ int bix = apos[k];
+ if( bix >= blen )
continue;
- int len = _data[bitmapOff+bufIx];
- int pos = bitmapOff+bufIx+1;
+ int len = _data[boff+bix];
+ int pos = boff+bix+1;
for( int i=pos; i<pos+len; i++ ) {
c[bi+_data[i]] = _values[off+colpos];
}
@@ -289,30 +289,8 @@ public class ColGroupOLE extends ColGroupBitmap
final int blksz2 = ColGroupBitmap.WRITE_CACHE_BLKSZ;
//step 1: prepare position and value arrays
-
- //current pos / values per OLs
- int[] apos = new int[numVals];
- double[] aval = new double[numVals];
-
- //skip-scan to beginning for all OLs
- if( rl > 0 ) { //rl aligned with blksz
- int rskip = (getNumRows()/2/blksz)*blksz;
-
- for (int k = 0; k < numVals; k++) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
- int start = (rl>=rskip)?rskip:0;
- int bufIx = (rl>=rskip)?_skiplist[k]:0;
- for( int i=start; i<rl && bufIx<bitmapLen; i+=blksz ) {
- bufIx += _data[bitmapOff+bufIx] + 1;
- }
- apos[k] = bufIx;
- }
- }
-
- //pre-aggregate values per OLs
- for( int k = 0; k < numVals; k++ )
- aval[k] = sumValues(k, sb);
+ int[] apos = skipScan(numVals, rl);
+ double[] aval = preaggValues(numVals, sb);
//step 2: cache conscious matrix-vector via horizontal scans
for( int bi=rl; bi<ru; bi+=blksz2 )
@@ -321,24 +299,22 @@ public class ColGroupOLE extends ColGroupBitmap
//horizontal segment scan, incl pos maintenance
for (int k = 0; k < numVals; k++) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
+ int boff = _ptr[k];
+ int blen = len(k);
double val = aval[k];
- int bufIx = apos[k];
+ int bix = apos[k];
- for( int ii=bi; ii<bimax && bufIx<bitmapLen; ii+=blksz ) {
+ for( int ii=bi; ii<bimax && bix<blen; ii+=blksz ) {
//prepare length, start, and end pos
- int len = _data[bitmapOff+bufIx];
- int pos = bitmapOff+bufIx+1;
+ int len = _data[boff+bix];
+ int pos = boff+bix+1;
//compute partial results
- //LinearAlgebraUtils.vectAdd(val, c, bitmaps, pos, ii, len);
- for( int i=pos; i<pos+len; i++ )
- c[ii + _data[i]] += val;
- bufIx += len + 1;
+ LinearAlgebraUtils.vectAdd(val, c, _data, pos, ii, len);
+ bix += len + 1;
}
- apos[k] = bufIx;
+ apos[k] = bix;
}
}
}
@@ -348,28 +324,28 @@ public class ColGroupOLE extends ColGroupBitmap
for (int k = 0; k < numVals; k++)
{
//prepare value-to-add for entire value bitmap
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
+ int boff = _ptr[k];
+ int blen = len(k);
double val = sumValues(k, sb);
//iterate over bitmap blocks and add values
if (val != 0) {
- int offsetBase = 0;
- int bufIx = 0;
- int curBlckLen;
+ int bix = 0;
+ int off = 0;
+ int slen = -1;
//scan to beginning offset if necessary
if( rl > 0 ){
- for (; bufIx<bitmapLen & offsetBase<rl; bufIx += curBlckLen + 1, offsetBase += blksz) {
- curBlckLen = _data[bitmapOff+bufIx];
+ for (; bix<blen & off<rl; bix += slen+1, off += blksz) {
+ slen = _data[boff+bix];
}
}
//compute partial results
- for (; bufIx<bitmapLen & offsetBase<ru; bufIx += curBlckLen + 1, offsetBase += blksz) {
- curBlckLen = _data[bitmapOff+bufIx];
- for (int blckIx = 1; blckIx <= curBlckLen; blckIx++) {
- c[offsetBase + _data[bitmapOff+bufIx + blckIx]] += val;
+ for (; bix<blen & off<ru; bix += slen + 1, off += blksz) {
+ slen = _data[boff+bix];
+ for (int blckIx = 1; blckIx <= slen; blckIx++) {
+ c[off + _data[boff+bix + blckIx]] += val;
}
}
}
@@ -406,22 +382,22 @@ public class ColGroupOLE extends ColGroupBitmap
//horizontal segment scan, incl pos maintenance
for (int k = 0; k < numVals; k++) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
- int bufIx = apos[k];
+ int boff = _ptr[k];
+ int blen = len(k);
+ int bix = apos[k];
double vsum = 0;
- for( int ii=ai; ii<aimax && bufIx<bitmapLen; ii+=blksz ) {
+ for( int ii=ai; ii<aimax && bix<blen; ii+=blksz ) {
//prepare length, start, and end pos
- int len = _data[bitmapOff+bufIx];
- int pos = bitmapOff+bufIx+1;
+ int len = _data[boff+bix];
+ int pos = boff+bix+1;
//iterate over bitmap blocks and compute partial results (a[i]*1)
vsum += LinearAlgebraUtils.vectSum(a, _data, ii, pos, len);
- bufIx += len + 1;
+ bix += len + 1;
}
- apos[k] = bufIx;
+ apos[k] = bix;
cvals[k] += vsum;
}
}
@@ -436,13 +412,13 @@ public class ColGroupOLE extends ColGroupBitmap
//iterate over all values and their bitmaps
for (int k=0, valOff=0; k<numVals; k++, valOff+=numCols)
{
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
+ int boff = _ptr[k];
+ int blen = len(k);
//iterate over bitmap blocks and add partial results
double vsum = 0;
- for (int bix=0, off=0; bix < bitmapLen; bix+=_data[bitmapOff+bix]+1, off+=blksz)
- vsum += LinearAlgebraUtils.vectSum(a, _data, off, bitmapOff+bix+1, _data[bitmapOff+bix]);
+ for (int bix=0, off=0; bix < blen; bix+=_data[boff+bix]+1, off+=blksz)
+ vsum += LinearAlgebraUtils.vectSum(a, _data, off, boff+bix+1, _data[boff+bix]);
//scale partial results by values and write results
for( int j = 0; j < numCols; j++ )
@@ -478,16 +454,16 @@ public class ColGroupOLE extends ColGroupBitmap
final int numVals = getNumValues();
final int numCols = getNumCols();
- for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++)
+ for (int k = 0; k < numVals; k++)
{
- int bitmapOff = _ptr[bitmapIx];
- int bitmapLen = len(bitmapIx);
- int valOff = bitmapIx * numCols;
+ int boff = _ptr[k];
+ int blen = len(k);
+ int valOff = k * numCols;
//iterate over bitmap blocks and count partial lengths
int count = 0;
- for (int bix=0; bix < bitmapLen; bix+=_data[bitmapOff+bix]+1)
- count += _data[bitmapOff+bix];
+ for (int bix=0; bix < blen; bix+=_data[boff+bix]+1)
+ count += _data[boff+bix];
//scale counts by all values
for( int j = 0; j < numCols; j++ )
@@ -510,22 +486,21 @@ public class ColGroupOLE extends ColGroupBitmap
final int numVals = getNumValues();
//iterate over all values and their bitmaps
- for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++)
+ for (int k = 0; k < numVals; k++)
{
//prepare value-to-add for entire value bitmap
- int bitmapOff = _ptr[bitmapIx];
- int bitmapLen = len(bitmapIx);
- double val = sumValues(bitmapIx);
+ int boff = _ptr[k];
+ int blen = len(k);
+ double val = sumValues(k);
//iterate over bitmap blocks and add values
if (val != 0) {
- int offsetBase = 0;
- int bufIx = 0;
- int curBlckLen;
- for (; bufIx < bitmapLen; bufIx += curBlckLen + 1, offsetBase += blksz) {
- curBlckLen = _data[bitmapOff+bufIx];
- for (int blckIx = 1; blckIx <= curBlckLen; blckIx++) {
- int rix = offsetBase + _data[bitmapOff+bufIx + blckIx];
+ int off = 0;
+ int slen;
+ for( int bix = 0; bix < blen; bix += slen + 1, off += blksz ) {
+ slen = _data[boff+bix];
+ for (int i = 1; i <= slen; i++) {
+ int rix = off + _data[boff+bix + i];
kbuff.set(result.quickGetValue(rix, 0), result.quickGetValue(rix, 1));
kplus.execute2(kbuff, val);
result.quickSetValue(rix, 0, kbuff._sum);
@@ -547,16 +522,16 @@ public class ColGroupOLE extends ColGroupBitmap
//iterate over all values and their bitmaps
final int numVals = getNumValues();
final int numCols = getNumCols();
- for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++)
+ for (int k = 0; k < numVals; k++)
{
- int bitmapOff = _ptr[bitmapIx];
- int bitmapLen = len(bitmapIx);
- int valOff = bitmapIx * numCols;
+ int boff = _ptr[k];
+ int blen = len(k);
+ int valOff = k * numCols;
//iterate over bitmap blocks and count partial lengths
int count = 0;
- for (int bix=0; bix < bitmapLen; bix+=_data[bitmapOff+bix]+1)
- count += _data[bitmapOff+bix];
+ for (int bix=0; bix < blen; bix+=_data[boff+bix]+1)
+ count += _data[boff+bix];
//scale counts by all values
for( int j = 0; j < numCols; j++ ) {
@@ -585,20 +560,19 @@ public class ColGroupOLE extends ColGroupBitmap
Arrays.fill(ret, true);
//iterate over all values and their bitmaps
- for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++)
+ for (int k = 0; k < numVals; k++)
{
//prepare value-to-add for entire value bitmap
- int bitmapOff = _ptr[bitmapIx];
- int bitmapLen = len(bitmapIx);
+ int boff = _ptr[k];
+ int blen = len(k);
//iterate over bitmap blocks and add values
- int offsetBase = 0;
- int bufIx = 0;
- int curBlckLen;
- for (; bufIx < bitmapLen; bufIx += curBlckLen + 1, offsetBase += blksz) {
- curBlckLen = _data[bitmapOff+bufIx];
- for (int blckIx = 1; blckIx <= curBlckLen; blckIx++) {
- ret[offsetBase + _data[bitmapOff+bufIx + blckIx]] &= false;
+ int off = 0;
+ int slen;
+ for( int bix=0; bix < blen; bix+=slen+1, off+=blksz) {
+ slen = _data[boff+bix];
+ for (int i = 1; i <= slen; i++) {
+ ret[off + _data[boff+bix + i]] &= false;
}
}
}
@@ -617,18 +591,52 @@ public class ColGroupOLE extends ColGroupBitmap
for (int k = 0; k < numVals; k++)
{
//prepare value-to-add for entire value bitmap
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
+ int boff = _ptr[k];
+ int blen = len(k);
//iterate over bitmap blocks and add values
- int offsetBase = 0;
- int curBlckLen;
- for (int bufIx=0; bufIx<bitmapLen; bufIx+=curBlckLen+1, offsetBase+=blksz) {
- curBlckLen = _data[bitmapOff+bufIx];
- for (int blckIx = 1; blckIx <= curBlckLen; blckIx++) {
- rnnz[offsetBase + _data[bitmapOff+bufIx + blckIx]] += numCols;
+ int off = 0;
+ int slen;
+ for (int bix=0; bix<blen; bix+=slen+1, off+=blksz) {
+ slen = _data[boff+bix];
+ for (int blckIx = 1; blckIx <= slen; blckIx++) {
+ rnnz[off + _data[boff+bix + blckIx]] += numCols;
+ }
+ }
+ }
+ }
+
+ /////////////////////////////////
+ // internal helper functions
+
+ /**
+ * Scans to given row_lower position by exploiting any existing
+ * skip list and scanning segment length fields. Returns array
+ * of positions for all values;
+ *
+ * @param numVals
+ * @param rl
+ * @return
+ */
+ private int[] skipScan(int numVals, int rl) {
+ int[] ret = new int[numVals];
+ final int blksz = BitmapEncoder.BITMAP_BLOCK_SZ;
+
+ if( rl > 0 ) { //rl aligned with blksz
+ int rskip = (getNumRows()/2/blksz)*blksz;
+
+ for( int k = 0; k < numVals; k++ ) {
+ int boff = _ptr[k];
+ int blen = len(k);
+ int start = (rl>=rskip)?rskip:0;
+ int bix = (rl>=rskip)?_skiplist[k]:0;
+ for( int i=start; i<rl && bix<blen; i+=blksz ) {
+ bix += _data[boff+bix] + 1;
}
+ ret[k] = bix;
}
}
+
+ return ret;
}
}
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b1dc0d5b/src/main/java/org/apache/sysml/runtime/compress/ColGroupRLE.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/compress/ColGroupRLE.java b/src/main/java/org/apache/sysml/runtime/compress/ColGroupRLE.java
index 05d77f8..017a7d3 100644
--- a/src/main/java/org/apache/sysml/runtime/compress/ColGroupRLE.java
+++ b/src/main/java/org/apache/sysml/runtime/compress/ColGroupRLE.java
@@ -65,9 +65,9 @@ public class ColGroupRLE extends ColGroupBitmap
final int numVals = ubm.getNumValues();
char[][] lbitmaps = new char[numVals][];
int totalLen = 0;
- for( int i=0; i<numVals; i++ ) {
- lbitmaps[i] = BitmapEncoder.genRLEBitmap(ubm.getOffsetsList(i));
- totalLen += lbitmaps[i].length;
+ for( int k=0; k<numVals; k++ ) {
+ lbitmaps[k] = BitmapEncoder.genRLEBitmap(ubm.getOffsetsList(k));
+ totalLen += lbitmaps[k].length;
}
// compact bitmaps to linearized representation
@@ -106,20 +106,20 @@ public class ColGroupRLE extends ColGroupBitmap
for( int bi=0; bi<n; bi+=blksz ) {
int bimax = Math.min(bi+blksz, n);
for (int k=0, off=0; k < numVals; k++, off+=numCols) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
- int bufIx = apos[k];
+ int boff = _ptr[k];
+ int blen = len(k);
+ int bix = apos[k];
int start = astart[k];
- for( ; bufIx<bitmapLen & start<bimax; bufIx+=2) {
- start += _data[bitmapOff + bufIx];
- int len = _data[bitmapOff + bufIx+1];
+ for( ; bix<blen & start<bimax; bix+=2) {
+ start += _data[boff + bix];
+ int len = _data[boff + bix+1];
for( int i=start; i<start+len; i++ )
for( int j=0; j<numCols; j++ )
if( _values[off+j]!=0 )
target.appendValue(i, _colIndexes[j], _values[off+j]);
start += len;
}
- apos[k] = bufIx;
+ apos[k] = bix;
astart[k] = start;
}
}
@@ -154,22 +154,22 @@ public class ColGroupRLE extends ColGroupBitmap
for( int bi=0; bi<n; bi+=blksz ) {
int bimax = Math.min(bi+blksz, n);
for (int k=0, off=0; k < numVals; k++, off+=numCols) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
- int bufIx = apos[k];
- if( bufIx >= bitmapLen )
+ int boff = _ptr[k];
+ int blen = len(k);
+ int bix = apos[k];
+ if( bix >= blen )
continue;
int start = astart[k];
- for( ; bufIx<bitmapLen & start<bimax; bufIx+=2) {
- start += _data[bitmapOff + bufIx];
- int len = _data[bitmapOff + bufIx+1];
+ for( ; bix<blen & start<bimax; bix+=2) {
+ start += _data[boff + bix];
+ int len = _data[boff + bix+1];
for( int i=start; i<start+len; i++ )
for( int j=0; j<numCols; j++ )
if( _values[off+j]!=0 )
target.appendValue(i, cix[j], _values[off+j]);
start += len;
}
- apos[k] = bufIx;
+ apos[k] = bix;
astart[k] = start;
}
}
@@ -200,20 +200,20 @@ public class ColGroupRLE extends ColGroupBitmap
for( int bi=0; bi<n; bi+=blksz ) {
int bimax = Math.min(bi+blksz, n);
for (int k=0, off=0; k < numVals; k++, off+=numCols) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
- int bufIx = apos[k];
- if( bufIx >= bitmapLen )
+ int boff = _ptr[k];
+ int blen = len(k);
+ int bix = apos[k];
+ if( bix >= blen )
continue;
int start = astart[k];
- for( ; bufIx<bitmapLen & start<bimax; bufIx+=2) {
- start += _data[bitmapOff + bufIx];
- int len = _data[bitmapOff + bufIx+1];
+ for( ; bix<blen & start<bimax; bix+=2) {
+ start += _data[boff + bix];
+ int len = _data[boff + bix+1];
for( int i=start; i<start+len; i++ )
c[i] = _values[off+colpos];
start += len;
}
- apos[k] = bufIx;
+ apos[k] = bix;
astart[k] = start;
}
}
@@ -253,34 +253,10 @@ public class ColGroupRLE extends ColGroupBitmap
//step 1: prepare position and value arrays
//current pos / values per RLE list
- int[] apos = new int[numVals];
int[] astart = new int[numVals];
- double[] aval = new double[numVals];
-
- //skip-scan to beginning for all OLs
- if( rl > 0 ) { //rl aligned with blksz
- for (int k = 0; k < numVals; k++) {
- int boff = _ptr[k];
- int blen = len(k);
- int bix = 0;
- int start = 0;
- while( bix<blen ) {
- int lstart = _data[boff + bix]; //start
- int llen = _data[boff + bix + 1]; //len
- if( start+lstart+llen >= rl )
- break;
- start += lstart + llen;
- bix += 2;
- }
- apos[k] = bix;
- astart[k] = start;
- }
- }
+ int[] apos = skipScan(numVals, rl, astart);
+ double[] aval = preaggValues(numVals, sb);
- //pre-aggregate values per OLs
- for( int k = 0; k < numVals; k++ )
- aval[k] = sumValues(k, sb);
-
//step 2: cache conscious matrix-vector via horizontal scans
for( int bi=rl; bi<ru; bi+=blksz )
{
@@ -376,21 +352,21 @@ public class ColGroupRLE extends ColGroupBitmap
//horizontal scan, incl pos maintenance
for (int k = 0; k < numVals; k++) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
- int bufIx = apos[k];
+ int boff = _ptr[k];
+ int blen = len(k);
+ int bix = apos[k];
int start = astart[k];
//compute partial results, not aligned
- while( bufIx<bitmapLen & start<aimax ) {
- start += _data[bitmapOff + bufIx];
- int len = _data[bitmapOff + bufIx+1];
+ while( bix<blen & start<aimax ) {
+ start += _data[boff + bix];
+ int len = _data[boff + bix+1];
cvals[k] += LinearAlgebraUtils.vectSum(a, start, len);
start += len;
- bufIx += 2;
+ bix += 2;
}
- apos[k] = bufIx;
+ apos[k] = bix;
astart[k] = start;
}
}
@@ -404,16 +380,16 @@ public class ColGroupRLE extends ColGroupBitmap
else
{
//iterate over all values and their bitmaps
- for (int bitmapIx=0, valOff=0; bitmapIx<numVals; bitmapIx++, valOff+=numCols)
+ for (int k=0, valOff=0; k<numVals; k++, valOff+=numCols)
{
- int bitmapOff = _ptr[bitmapIx];
- int bitmapLen = len(bitmapIx);
+ int boff = _ptr[k];
+ int blen = len(k);
double vsum = 0;
int curRunEnd = 0;
- for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) {
- int curRunStartOff = curRunEnd + _data[bitmapOff+bufIx];
- int curRunLen = _data[bitmapOff+bufIx + 1];
+ for ( int bix = 0; bix < blen; bix+=2 ) {
+ int curRunStartOff = curRunEnd + _data[boff+bix];
+ int curRunLen = _data[boff+bix+1];
vsum += LinearAlgebraUtils.vectSum(a, curRunStartOff, curRunLen);
curRunEnd = curRunStartOff + curRunLen;
}
@@ -484,15 +460,15 @@ public class ColGroupRLE extends ColGroupBitmap
final int numCols = getNumCols();
final int numVals = getNumValues();
- for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) {
- int bitmapOff = _ptr[bitmapIx];
- int bitmapLen = len(bitmapIx);
- int valOff = bitmapIx * numCols;
+ for (int k = 0; k < numVals; k++) {
+ int boff = _ptr[k];
+ int blen = len(k);
+ int valOff = k * numCols;
int curRunEnd = 0;
int count = 0;
- for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) {
- int curRunStartOff = curRunEnd + _data[bitmapOff+bufIx];
- curRunEnd = curRunStartOff + _data[bitmapOff+bufIx + 1];
+ for (int bix = 0; bix < blen; bix+=2) {
+ int curRunStartOff = curRunEnd + _data[boff+bix];
+ curRunEnd = curRunStartOff + _data[boff+bix+1];
count += curRunEnd-curRunStartOff;
}
@@ -514,17 +490,17 @@ public class ColGroupRLE extends ColGroupBitmap
KahanObject kbuff = new KahanObject(0, 0);
final int numVals = getNumValues();
- for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) {
- int bitmapOff = _ptr[bitmapIx];
- int bitmapLen = len(bitmapIx);
- double val = sumValues(bitmapIx);
+ for (int k = 0; k < numVals; k++) {
+ int boff = _ptr[k];
+ int blen = len(k);
+ double val = sumValues(k);
if (val != 0.0) {
int curRunStartOff = 0;
int curRunEnd = 0;
- for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) {
- curRunStartOff = curRunEnd + _data[bitmapOff+bufIx];
- curRunEnd = curRunStartOff + _data[bitmapOff+bufIx + 1];
+ for (int bix = 0; bix < blen; bix+=2) {
+ curRunStartOff = curRunEnd + _data[boff+bix];
+ curRunEnd = curRunStartOff + _data[boff+bix+1];
for (int rix = curRunStartOff; rix < curRunEnd; rix++) {
kbuff.set(result.quickGetValue(rix, 0), result.quickGetValue(rix, 1));
kplus.execute2(kbuff, val);
@@ -547,15 +523,15 @@ public class ColGroupRLE extends ColGroupBitmap
final int numCols = getNumCols();
final int numVals = getNumValues();
- for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) {
- int bitmapOff = _ptr[bitmapIx];
- int bitmapLen = len(bitmapIx);
- int valOff = bitmapIx * numCols;
+ for (int k = 0; k < numVals; k++) {
+ int boff = _ptr[k];
+ int blen = len(k);
+ int valOff = k * numCols;
int curRunEnd = 0;
int count = 0;
- for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) {
- int curRunStartOff = curRunEnd + _data[bitmapOff+bufIx];
- curRunEnd = curRunStartOff + _data[bitmapOff+bufIx + 1];
+ for (int bix=0; bix < blen; bix+=2) {
+ int curRunStartOff = curRunEnd + _data[boff+bix];
+ curRunEnd = curRunStartOff + _data[boff+bix+1];
count += curRunEnd-curRunStartOff;
}
@@ -578,15 +554,15 @@ public class ColGroupRLE extends ColGroupBitmap
//initialize everything with zero
Arrays.fill(ret, true);
- for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) {
- int bitmapOff = _ptr[bitmapIx];
- int bitmapLen = len(bitmapIx);
+ for (int k = 0; k < numVals; k++) {
+ int boff = _ptr[k];
+ int blen = len(k);
int curRunStartOff = 0;
int curRunEnd = 0;
- for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) {
- curRunStartOff = curRunEnd + _data[bitmapOff+bufIx];
- curRunEnd = curRunStartOff + _data[bitmapOff+bufIx + 1];
+ for (int bix = 0; bix < blen; bix+=2) {
+ curRunStartOff = curRunEnd + _data[boff+bix];
+ curRunEnd = curRunStartOff + _data[boff+bix + 1];
Arrays.fill(ret, curRunStartOff, curRunEnd, false);
}
}
@@ -601,17 +577,56 @@ public class ColGroupRLE extends ColGroupBitmap
final int numCols = getNumCols();
for (int k = 0; k < numVals; k++) {
- int bitmapOff = _ptr[k];
- int bitmapLen = len(k);
+ int boff = _ptr[k];
+ int blen = len(k);
int curRunStartOff = 0;
int curRunEnd = 0;
- for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) {
- curRunStartOff = curRunEnd + _data[bitmapOff+bufIx];
- curRunEnd = curRunStartOff + _data[bitmapOff+bufIx + 1];
+ for (int bix = 0; bix < blen; bix+=2) {
+ curRunStartOff = curRunEnd + _data[boff+bix];
+ curRunEnd = curRunStartOff + _data[boff+bix + 1];
for( int i=curRunStartOff; i<curRunEnd; i++ )
rnnz[i] += numCols;
}
}
}
+
+ /////////////////////////////////
+ // internal helper functions
+
+
+ /**
+ * Scans to given row_lower position by scanning run length
+ * fields. Returns array of positions for all values and modifies
+ * given array of start positions for all values too.
+ *
+ * @param numVals
+ * @param rl
+ * @param astart
+ * @return
+ */
+ private int[] skipScan(int numVals, int rl, int[] astart) {
+ int[] apos = new int[numVals];
+
+ if( rl > 0 ) { //rl aligned with blksz
+ for (int k = 0; k < numVals; k++) {
+ int boff = _ptr[k];
+ int blen = len(k);
+ int bix = 0;
+ int start = 0;
+ while( bix<blen ) {
+ int lstart = _data[boff + bix]; //start
+ int llen = _data[boff + bix + 1]; //len
+ if( start+lstart+llen >= rl )
+ break;
+ start += lstart + llen;
+ bix += 2;
+ }
+ apos[k] = bix;
+ astart[k] = start;
+ }
+ }
+
+ return apos;
+ }
}
[2/2] incubator-systemml git commit: [SYSTEMML-824] Performance
scalar/agg/binary ops (sparse, par, overlap)
Posted by mb...@apache.org.
[SYSTEMML-824] Performance scalar/agg/binary ops (sparse, par, overlap)
This patch makes various performance improvements some of which change
the asymptotic behavior with huge improvements on large data.
(1) Scalar operations: Right scalar divide with non-zero scalar (e.g.,
X/7) are now marked as sparse-safe.
(2) Unary aggregate operations: The min size threshold for parallel
operations is now checked on the number of non-zeros instead of number
of cells in order to avoid unnecessary thread pool creation overhead on
small data.
(3) Ternary aggregate operations: The rewrites of sum(v1*v2*v3) to
tak+(v1,v2,v3) is now only applied if sum is the only consumer of the
intermediate in order to avoid unnecessary redundancy.
(4) Binary operations: There is now an additional special case for "skip
empty" operations like * and / (with dense rhs) that were handled so far
with the generic case (e.g., * sparse-dense with sparse output) leading
to an asymptotic improvement from O(n log n) to O(n).
Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/2137a7e4
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/2137a7e4
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/2137a7e4
Branch: refs/heads/master
Commit: 2137a7e4a0af7a48326294fa6bb56084ade9d2b5
Parents: b1dc0d5
Author: Matthias Boehm <mb...@us.ibm.com>
Authored: Wed Aug 10 23:04:28 2016 -0700
Committer: Matthias Boehm <mb...@us.ibm.com>
Committed: Thu Aug 11 11:52:13 2016 -0700
----------------------------------------------------------------------
.../java/org/apache/sysml/hops/AggUnaryOp.java | 16 ++-
.../sysml/runtime/matrix/data/LibMatrixAgg.java | 2 +-
.../runtime/matrix/data/LibMatrixBincell.java | 101 +++++++++++--------
.../matrix/operators/RightScalarOperator.java | 9 +-
4 files changed, 70 insertions(+), 58 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/2137a7e4/src/main/java/org/apache/sysml/hops/AggUnaryOp.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/AggUnaryOp.java b/src/main/java/org/apache/sysml/hops/AggUnaryOp.java
index 0152d54..8b44e4b 100644
--- a/src/main/java/org/apache/sysml/hops/AggUnaryOp.java
+++ b/src/main/java/org/apache/sysml/hops/AggUnaryOp.java
@@ -495,31 +495,29 @@ public class AggUnaryOp extends Hop implements MultiThreadedHop
//currently we support only sum over binary multiply but potentially
//it can be generalized to any RC aggregate over two common binary operations
- if( _direction == Direction.RowCol
- && _op == AggOp.SUM )
+ if( OptimizerUtils.ALLOW_SUM_PRODUCT_REWRITES &&
+ _direction == Direction.RowCol && _op == AggOp.SUM )
{
Hop input1 = getInput().get(0);
- if( input1 instanceof BinaryOp && ((BinaryOp)input1).getOp()==OpOp2.MULT )
+ if( input1.getParent().size() == 1 && //sum single consumer
+ input1 instanceof BinaryOp && ((BinaryOp)input1).getOp()==OpOp2.MULT )
{
Hop input11 = input1.getInput().get(0);
Hop input12 = input1.getInput().get(1);
- if( input11 instanceof BinaryOp && ((BinaryOp)input11).getOp()==OpOp2.MULT )
- {
+ if( input11 instanceof BinaryOp && ((BinaryOp)input11).getOp()==OpOp2.MULT ) {
//ternary, arbitrary matrices but no mv/outer operations.
ret = HopRewriteUtils.isEqualSize(input11.getInput().get(0), input1)
&& HopRewriteUtils.isEqualSize(input11.getInput().get(1), input1)
&& HopRewriteUtils.isEqualSize(input12, input1);
}
- else if( input12 instanceof BinaryOp && ((BinaryOp)input12).getOp()==OpOp2.MULT )
- {
+ else if( input12 instanceof BinaryOp && ((BinaryOp)input12).getOp()==OpOp2.MULT ) {
//ternary, arbitrary matrices but no mv/outer operations.
ret = HopRewriteUtils.isEqualSize(input12.getInput().get(0), input1)
&& HopRewriteUtils.isEqualSize(input12.getInput().get(1), input1)
&& HopRewriteUtils.isEqualSize(input11, input1);
}
- else
- {
+ else {
//binary, arbitrary matrices but no mv/outer operations.
ret = HopRewriteUtils.isEqualSize(input11, input12);
}
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/2137a7e4/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 cf689b8..3357dee 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
@@ -229,7 +229,7 @@ public class LibMatrixAgg
throws DMLRuntimeException
{
//fall back to sequential version if necessary
- if( k <= 1 || (long)in.rlen*in.clen < PAR_NUMCELL_THRESHOLD || in.rlen <= k
+ if( k <= 1 || (long)in.nonZeros < PAR_NUMCELL_THRESHOLD || in.rlen <= k/2
|| (!(uaop.indexFn instanceof ReduceCol) && out.clen*8*k > PAR_INTERMEDIATE_SIZE_THRESHOLD ) ||
!out.isThreadSafe()) {
aggregateUnaryMatrix(in, out, uaop);
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/2137a7e4/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 f9269e8..8e7d330 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
@@ -228,8 +228,8 @@ public class LibMatrixBincell
private static void safeBinary(MatrixBlock m1, MatrixBlock m2, MatrixBlock ret, BinaryOperator op)
throws DMLRuntimeException
{
- boolean isMultiply = (op.fn instanceof Multiply);
- boolean skipEmpty = (isMultiply);
+ boolean skipEmpty = (op.fn instanceof Multiply
+ || isSparseSafeDivide(op, m2) );
//skip empty blocks (since sparse-safe)
if( m1.isEmptyBlock(false) && m2.isEmptyBlock(false)
@@ -425,18 +425,35 @@ public class LibMatrixBincell
}
ret.nonZeros = nnz;
}
+ else if( skipEmpty && (m1.sparse || m2.sparse) )
+ {
+ SparseBlock a = m1.sparse ? m1.sparseBlock : m2.sparseBlock;
+ if( a != null ) {
+ MatrixBlock b = m1.sparse ? m2 : m1;
+ for( int i=0; i<a.numRows(); 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);
+ for(int k = apos; k < apos+alen; k++) {
+ double in2 = b.quickGetValue(i, aix[k]);
+ if( in2==0 ) continue;
+ double val = op.fn.execute(avals[k], in2);
+ ret.appendValue(i, aix[k], val);
+ }
+ }
+ }
+ }
else //generic case
{
- double thisvalue, thatvalue, resultvalue;
for(int r=0; r<rlen; r++)
- for(int c=0; c<clen; c++)
- {
- thisvalue=m1.quickGetValue(r, c);
- thatvalue=m2.quickGetValue(r, c);
- if(thisvalue==0 && thatvalue==0)
- continue;
- resultvalue=op.fn.execute(thisvalue, thatvalue);
- ret.appendValue(r, c, resultvalue);
+ for(int c=0; c<clen; c++) {
+ double in1 = m1.quickGetValue(r, c);
+ double in2 = m2.quickGetValue(r, c);
+ if( in1==0 && in2==0) continue;
+ double val = op.fn.execute(in1, in2);
+ ret.appendValue(r, c, val);
}
}
}
@@ -995,23 +1012,9 @@ public class LibMatrixBincell
}
ret.nonZeros = nnz;
}
- else //DENSE <- DENSE
- {
- //allocate dense block
- ret.allocateDenseBlock(true);
-
- double[] a = m1.denseBlock;
- double[] c = ret.denseBlock;
-
- 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;
- }
- ret.nonZeros = nnz;
+ else { //DENSE <- DENSE
+ denseBinaryScalar(m1, ret, op);
}
-
}
/**
@@ -1068,27 +1071,39 @@ public class LibMatrixBincell
}
ret.nonZeros = nnz;
}
- else //DENSE MATRIX
- {
- //allocate dense block (if necessary), incl clear nnz
- ret.allocateDenseBlock(true);
-
- double[] a = m1.denseBlock;
- double[] c = ret.denseBlock;
-
- //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;
- }
- ret.nonZeros = nnz;
+ else { //DENSE MATRIX
+ denseBinaryScalar(m1, ret, op);
}
}
/**
*
+ * @param m1
+ * @param ret
+ * @param op
+ * @throws DMLRuntimeException
+ */
+ private static void denseBinaryScalar(MatrixBlock m1, MatrixBlock ret, ScalarOperator op)
+ throws DMLRuntimeException
+ {
+ //allocate dense block (if necessary), incl clear nnz
+ ret.allocateDenseBlock(true);
+
+ double[] a = m1.denseBlock;
+ double[] c = ret.denseBlock;
+
+ //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;
+ }
+ ret.nonZeros = nnz;
+ }
+
+ /**
+ *
* @param m1ret
* @param m2
* @param op
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/2137a7e4/src/main/java/org/apache/sysml/runtime/matrix/operators/RightScalarOperator.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/operators/RightScalarOperator.java b/src/main/java/org/apache/sysml/runtime/matrix/operators/RightScalarOperator.java
index 3a4c481..cea41f1 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/operators/RightScalarOperator.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/operators/RightScalarOperator.java
@@ -21,6 +21,7 @@
package org.apache.sysml.runtime.matrix.operators;
import org.apache.sysml.runtime.DMLRuntimeException;
+import org.apache.sysml.runtime.functionobjects.Divide;
import org.apache.sysml.runtime.functionobjects.GreaterThan;
import org.apache.sysml.runtime.functionobjects.GreaterThanEquals;
import org.apache.sysml.runtime.functionobjects.LessThan;
@@ -49,12 +50,10 @@ public class RightScalarOperator extends ScalarOperator
super.setConstant(cst);
//enable conditionally sparse safe operations
- if( (fn instanceof GreaterThan && _constant>=0)
+ sparseSafe = (fn instanceof GreaterThan && _constant>=0)
|| (fn instanceof GreaterThanEquals && _constant>0)
|| (fn instanceof LessThan && _constant<=0)
- || (fn instanceof LessThanEquals && _constant<0))
- {
- sparseSafe = true;
- }
+ || (fn instanceof LessThanEquals && _constant<0)
+ || (fn instanceof Divide && _constant!=0);
}
}