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 2017/10/23 04:04:24 UTC
[3/4] systemml git commit: [SYSTEMML-1971] New codegen vector
primitive for counting nnz
[SYSTEMML-1971] New codegen vector primitive for counting nnz
This patch adds a new codegen vector primitive for rowSums(X!=0), i.e.
for counting the number of non-zeros, which avoids unnecessary dense row
intermediates and is realized as a pure meta data operation for sparse
row inputs.
After recent optimizer changes, we compiled a row template in ALS-CG for
rowSums(X!=0), which showed severe performance issues on the amazon
books dataset. This was because amazon is a ultra-sparse dataset with
huge number of features (2330066), for which the dense row intermediates
are more than 7 orders of magnitude larger than the sparse row input.
This patch completely removed these performance issues.
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/1191dbfe
Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/1191dbfe
Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/1191dbfe
Branch: refs/heads/master
Commit: 1191dbfe2a20d85bf79f0106312f37df210053cf
Parents: c70cb11
Author: Matthias Boehm <mb...@gmail.com>
Authored: Sun Oct 22 19:53:52 2017 -0700
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Sun Oct 22 19:53:52 2017 -0700
----------------------------------------------------------------------
.../org/apache/sysml/hops/codegen/cplan/CNodeUnary.java | 9 ++++++---
.../apache/sysml/hops/codegen/template/TemplateRow.java | 5 +++++
.../sysml/hops/codegen/template/TemplateUtils.java | 3 ++-
.../org/apache/sysml/hops/rewrite/HopRewriteUtils.java | 6 ++++++
.../sysml/runtime/codegen/LibSpoofPrimitives.java | 12 ++++++++++++
5 files changed, 31 insertions(+), 4 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/systemml/blob/1191dbfe/src/main/java/org/apache/sysml/hops/codegen/cplan/CNodeUnary.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/cplan/CNodeUnary.java b/src/main/java/org/apache/sysml/hops/codegen/cplan/CNodeUnary.java
index b66423e..3a3dc79 100644
--- a/src/main/java/org/apache/sysml/hops/codegen/cplan/CNodeUnary.java
+++ b/src/main/java/org/apache/sysml/hops/codegen/cplan/CNodeUnary.java
@@ -30,7 +30,7 @@ public class CNodeUnary extends CNode
{
public enum UnaryType {
LOOKUP_R, LOOKUP_C, LOOKUP_RC, LOOKUP0, //codegen specific
- ROW_SUMS, ROW_MINS, ROW_MAXS, //codegen specific
+ ROW_SUMS, ROW_MINS, ROW_MAXS, ROW_COUNTNNZS, //codegen specific
VECT_EXP, VECT_POW2, VECT_MULT2, VECT_SQRT, VECT_LOG,
VECT_ABS, VECT_ROUND, VECT_CEIL, VECT_FLOOR, VECT_SIGN,
VECT_SIN, VECT_COS, VECT_TAN, VECT_ASIN, VECT_ACOS, VECT_ATAN,
@@ -52,8 +52,9 @@ public class CNodeUnary extends CNode
switch( this ) {
case ROW_SUMS:
case ROW_MINS:
- case ROW_MAXS: {
- String vectName = StringUtils.capitalize(this.toString().substring(4,7).toLowerCase());
+ case ROW_MAXS:
+ case ROW_COUNTNNZS: {
+ String vectName = StringUtils.capitalize(name().substring(4, name().length()-1).toLowerCase());
return sparse ? " double %TMP% = LibSpoofPrimitives.vect"+vectName+"(%IN1v%, %IN1i%, %POS1%, alen, len);\n":
" double %TMP% = LibSpoofPrimitives.vect"+vectName+"(%IN1%, %POS1%, %LEN%);\n";
}
@@ -244,6 +245,7 @@ public class CNodeUnary extends CNode
case ROW_SUMS: return "u(R+)";
case ROW_MINS: return "u(Rmin)";
case ROW_MAXS: return "u(Rmax)";
+ case ROW_COUNTNNZS: return "u(Rnnz)";
case VECT_EXP:
case VECT_POW2:
case VECT_MULT2:
@@ -308,6 +310,7 @@ public class CNodeUnary extends CNode
case ROW_SUMS:
case ROW_MINS:
case ROW_MAXS:
+ case ROW_COUNTNNZS:
case EXP:
case LOOKUP_R:
case LOOKUP_C:
http://git-wip-us.apache.org/repos/asf/systemml/blob/1191dbfe/src/main/java/org/apache/sysml/hops/codegen/template/TemplateRow.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateRow.java b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateRow.java
index e664b9f..9da04dc 100644
--- a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateRow.java
+++ b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateRow.java
@@ -240,6 +240,11 @@ public class TemplateRow extends TemplateBase
if( ((AggUnaryOp)hop).getDirection() == Direction.Row && HopRewriteUtils.isAggUnaryOp(hop, SUPPORTED_ROW_AGG) ) {
if(hop.getInput().get(0).getDim2()==1)
out = (cdata1.getDataType()==DataType.SCALAR) ? cdata1 : new CNodeUnary(cdata1,UnaryType.LOOKUP_R);
+ else if( HopRewriteUtils.isAggUnaryOp(hop, AggOp.SUM)
+ && HopRewriteUtils.isBinaryMatrixScalar(hop.getInput().get(0), OpOp2.NOTEQUAL, 0)
+ && cdata1 instanceof CNodeBinary ) {
+ out = new CNodeUnary(cdata1.getInput().get(0), UnaryType.ROW_COUNTNNZS);
+ }
else {
String opcode = "ROW_"+((AggUnaryOp)hop).getOp().name().toUpperCase()+"S";
out = new CNodeUnary(cdata1, UnaryType.valueOf(opcode));
http://git-wip-us.apache.org/repos/asf/systemml/blob/1191dbfe/src/main/java/org/apache/sysml/hops/codegen/template/TemplateUtils.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateUtils.java b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateUtils.java
index 96e15cb..e07c410 100644
--- a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateUtils.java
+++ b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateUtils.java
@@ -312,7 +312,8 @@ public class TemplateUtils
public static boolean hasSingleOperation(CNodeTpl tpl) {
CNode output = tpl.getOutput();
return ((output instanceof CNodeUnary
- && !TemplateUtils.isUnary(output, UnaryType.EXP, UnaryType.LOG))
+ && !TemplateUtils.isUnary(output,
+ UnaryType.EXP, UnaryType.LOG, UnaryType.ROW_COUNTNNZS))
|| (output instanceof CNodeBinary
&& !TemplateUtils.isBinary(output, BinType.VECT_OUTERMULT_ADD)))
&& hasOnlyDataNodeOrLookupInputs(output);
http://git-wip-us.apache.org/repos/asf/systemml/blob/1191dbfe/src/main/java/org/apache/sysml/hops/rewrite/HopRewriteUtils.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/rewrite/HopRewriteUtils.java b/src/main/java/org/apache/sysml/hops/rewrite/HopRewriteUtils.java
index 7bbfa52..68068eb 100644
--- a/src/main/java/org/apache/sysml/hops/rewrite/HopRewriteUtils.java
+++ b/src/main/java/org/apache/sysml/hops/rewrite/HopRewriteUtils.java
@@ -893,6 +893,12 @@ public class HopRewriteUtils
return ret;
}
+ public static boolean isBinaryMatrixScalar(Hop hop, OpOp2 type, double val) {
+ return isBinary(hop, type)
+ && (isLiteralOfValue(hop.getInput().get(0), val)
+ || isLiteralOfValue(hop.getInput().get(1), val));
+ }
+
public static boolean containsInput(Hop current, Hop probe) {
return rContainsInput(current, probe, new HashSet<Long>());
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/1191dbfe/src/main/java/org/apache/sysml/runtime/codegen/LibSpoofPrimitives.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/codegen/LibSpoofPrimitives.java b/src/main/java/org/apache/sysml/runtime/codegen/LibSpoofPrimitives.java
index 91fde5e..356c729 100644
--- a/src/main/java/org/apache/sysml/runtime/codegen/LibSpoofPrimitives.java
+++ b/src/main/java/org/apache/sysml/runtime/codegen/LibSpoofPrimitives.java
@@ -281,6 +281,18 @@ public class LibSpoofPrimitives
return (alen<len) ? Math.max(val, 0) : val;
}
+ public static double vectCountnnz(double[] a, int ai, int len) {
+ int count = 0;
+ for( int i = ai; i < ai+len; i++ )
+ count += (a[i] != 0) ? 1 : 0;
+ return count;
+ }
+
+ public static double vectCountnnz(double[] avals, int[] aix, int ai, int alen, int len) {
+ //pure meta data operation
+ return alen;
+ }
+
//custom vector div
public static void vectDivAdd(double[] a, double bval, double[] c, int ai, int ci, int len) {