Repository: systemml Updated Branches: refs/heads/master 3f3e927b8 -> 1cbfdef3f
[SYSTEMML-1886] Extended codegen outer template (sparse-safe driver ops) This patch extends the codegen outer template by the ability to fuse additional sparse-safe operations on the driver. In detail, this is realized by generalizing the OFMC-merge condition of the outer template as well as the related cplan construction. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/30caf365 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/30caf365 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/30caf365 Branch: refs/heads/master Commit: 30caf3652125851979b3bca3312f98551853fbed Parents: 3f3e927 Author: Matthias Boehm <[email protected]> Authored: Mon Sep 4 19:08:27 2017 -0700 Committer: Matthias Boehm <[email protected]> Committed: Mon Sep 4 19:08:27 2017 -0700 ---------------------------------------------------------------------- .../org/apache/sysml/hops/OptimizerUtils.java | 10 ++++--- .../codegen/template/TemplateOuterProduct.java | 13 ++++---- .../hops/codegen/template/TemplateUtils.java | 18 ++++++++++++ .../sysml/hops/rewrite/HopRewriteUtils.java | 13 ++++++++ .../functions/codegen/OuterProdTmplTest.java | 27 ++++++++++++++--- src/test/scripts/functions/codegen/wdivmmNeq.R | 31 ++++++++++++++++++++ .../scripts/functions/codegen/wdivmmNeq.dml | 29 ++++++++++++++++++ 7 files changed, 128 insertions(+), 13 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/30caf365/src/main/java/org/apache/sysml/hops/OptimizerUtils.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/OptimizerUtils.java b/src/main/java/org/apache/sysml/hops/OptimizerUtils.java index a4143e3..82b1848 100644 --- a/src/main/java/org/apache/sysml/hops/OptimizerUtils.java +++ b/src/main/java/org/apache/sysml/hops/OptimizerUtils.java @@ -1015,15 +1015,17 @@ public class OptimizerUtils return ( op==OpOp2.NOTEQUAL && val==0); } - public static double getBinaryOpSparsityConditionalSparseSafe( double sp1, OpOp2 op, LiteralOp lit ) - { + public static boolean isBinaryOpSparsityConditionalSparseSafe( OpOp2 op, LiteralOp lit ) { double val = HopRewriteUtils.getDoubleValueSafe(lit); - return ( (op==OpOp2.GREATER && val==0) ||(op==OpOp2.LESS && val==0) ||(op==OpOp2.NOTEQUAL && val==0) ||(op==OpOp2.EQUAL && val!=0) - ||(op==OpOp2.MINUS && val==0)) ? sp1 : 1.0; + ||(op==OpOp2.MINUS && val==0)); + } + + public static double getBinaryOpSparsityConditionalSparseSafe( double sp1, OpOp2 op, LiteralOp lit ) { + return isBinaryOpSparsityConditionalSparseSafe(op, lit) ? sp1 : 1.0; } /** http://git-wip-us.apache.org/repos/asf/systemml/blob/30caf365/src/main/java/org/apache/sysml/hops/codegen/template/TemplateOuterProduct.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateOuterProduct.java b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateOuterProduct.java index f001a81..ec2ee3b 100644 --- a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateOuterProduct.java +++ b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateOuterProduct.java @@ -78,7 +78,10 @@ public class TemplateOuterProduct extends TemplateBase { public boolean merge(Hop hop, Hop input) { return !isClosed() && (TemplateUtils.isBinaryMatrixRowVector(hop) - || HopRewriteUtils.isBinaryMatrixScalarOperation(hop)); + || HopRewriteUtils.isBinaryMatrixScalarOperation(hop) + || (HopRewriteUtils.isBinary(hop, OpOp2.MULT) + && HopRewriteUtils.isBinarySparseSafe(input) + && !TemplateUtils.rContainsOuterProduct(input))); } @Override @@ -167,10 +170,10 @@ public class TemplateOuterProduct extends TemplateBase { CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID()); String primitiveOpName = ((BinaryOp)hop).getOp().toString(); - if( HopRewriteUtils.isEqualSize(hop.getInput().get(0), hop.getInput().get(1)) ) { - Hop main = hop.getInput().get((cdata1 instanceof CNodeData) ? 0 : 1); - inHops2.put("_X", main); - } + if( TemplateUtils.isMatrix(hop.getInput().get(0)) && cdata1 instanceof CNodeData ) + inHops2.put("_X", hop.getInput().get(0)); + if( TemplateUtils.isMatrix(hop.getInput().get(1)) && cdata2 instanceof CNodeData ) + inHops2.put("_X", hop.getInput().get(1)); //add lookups if required cdata1 = TemplateUtils.wrapLookupIfNecessary(cdata1, hop.getInput().get(0)); http://git-wip-us.apache.org/repos/asf/systemml/blob/30caf365/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 6c07e6e..ecfe7d5 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 @@ -430,4 +430,22 @@ public class TemplateUtils node.setVisited(); return ret; } + + public static boolean containsOuterProduct(Hop hop) { + hop.resetVisitStatus(); + boolean ret = rContainsOuterProduct(hop); + hop.resetVisitStatus(); + return ret; + } + + public static boolean rContainsOuterProduct(Hop current) { + if( current.isVisited() ) + return false; + boolean ret = false; + ret |= HopRewriteUtils.isOuterProductLikeMM(current); + for( int i=0; i<current.getInput().size() && !ret; i++ ) + ret |= rContainsOuterProduct(current.getInput().get(i)); + current.setVisited(); + return ret; + } } http://git-wip-us.apache.org/repos/asf/systemml/blob/30caf365/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 914e0cb..1bf381c 100644 --- a/src/main/java/org/apache/sysml/hops/rewrite/HopRewriteUtils.java +++ b/src/main/java/org/apache/sysml/hops/rewrite/HopRewriteUtils.java @@ -47,6 +47,7 @@ import org.apache.sysml.hops.IndexingOp; import org.apache.sysml.hops.LeftIndexingOp; import org.apache.sysml.hops.LiteralOp; import org.apache.sysml.hops.MemoTable; +import org.apache.sysml.hops.OptimizerUtils; import org.apache.sysml.hops.ParameterizedBuiltinOp; import org.apache.sysml.hops.ReorgOp; import org.apache.sysml.hops.TernaryOp; @@ -824,6 +825,18 @@ public class HopRewriteUtils return isBinary(hop, type) && hop.getParent().size() <= maxParents; } + public static boolean isBinarySparseSafe(Hop hop) { + if( !(hop instanceof BinaryOp) ) + return false; + if( isBinary(hop, OpOp2.MULT) ) + return true; + BinaryOp bop = (BinaryOp) hop; + Hop lit = bop.getInput().get(0) instanceof LiteralOp ? bop.getInput().get(0) : + bop.getInput().get(1) instanceof LiteralOp ? bop.getInput().get(1) : null; + return lit != null && OptimizerUtils + .isBinaryOpSparsityConditionalSparseSafe(bop.getOp(), (LiteralOp)lit); + } + public static boolean isBinaryMatrixScalarOperation(Hop hop) { return hop instanceof BinaryOp && ((hop.getInput().get(0).getDataType().isMatrix() && hop.getInput().get(1).getDataType().isScalar()) http://git-wip-us.apache.org/repos/asf/systemml/blob/30caf365/src/test/java/org/apache/sysml/test/integration/functions/codegen/OuterProdTmplTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/codegen/OuterProdTmplTest.java b/src/test/java/org/apache/sysml/test/integration/functions/codegen/OuterProdTmplTest.java index 358a87c..9a656b7 100644 --- a/src/test/java/org/apache/sysml/test/integration/functions/codegen/OuterProdTmplTest.java +++ b/src/test/java/org/apache/sysml/test/integration/functions/codegen/OuterProdTmplTest.java @@ -34,7 +34,7 @@ import org.apache.sysml.test.integration.TestConfiguration; import org.apache.sysml.test.utils.TestUtils; public class OuterProdTmplTest extends AutomatedTestBase -{ +{ private static final String TEST_NAME1 = "wdivmm"; private static final String TEST_NAME2 = "wdivmmRight"; private static final String TEST_NAME3 = "wsigmoid"; @@ -43,7 +43,8 @@ public class OuterProdTmplTest extends AutomatedTestBase private static final String TEST_NAME6 = "wdivmmbasic"; private static final String TEST_NAME7 = "wdivmmTransposeOut"; private static final String TEST_NAME8 = "wSparseUnsafeOuterProduct"; - + private static final String TEST_NAME9 = "wdivmmNeq"; + private static final String TEST_DIR = "functions/codegen/"; private static final String TEST_CLASS_DIR = TEST_DIR + OuterProdTmplTest.class.getSimpleName() + "/"; private final static String TEST_CONF = "SystemML-config-codegen.xml"; @@ -62,6 +63,7 @@ public class OuterProdTmplTest extends AutomatedTestBase addTestConfiguration( TEST_NAME6, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME6, new String[] { "6" }) ); addTestConfiguration( TEST_NAME7, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME7, new String[] { "7" }) ); addTestConfiguration( TEST_NAME8, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME8, new String[] { "8" }) ); + addTestConfiguration( TEST_NAME9, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME9, new String[] { "9" }) ); } @Test @@ -168,7 +170,21 @@ public class OuterProdTmplTest extends AutomatedTestBase public void testCodegenOuterProdRewrite8_sp() { testCodegenIntegrationWithInput( TEST_NAME8, true, ExecType.SPARK ); } - + + @Test + public void testCodegenOuterProdRewrite9() { + testCodegenIntegration( TEST_NAME9, true, ExecType.CP ); + } + + @Test + public void testCodegenOuterProd9() { + testCodegenIntegration( TEST_NAME9, false, ExecType.CP ); + } + + @Test + public void testCodegenOuterProdRewrite9_sp() { + testCodegenIntegrationWithInput( TEST_NAME9, true, ExecType.SPARK ); + } private void testCodegenIntegration( String testname, boolean rewrites, ExecType instType ) { @@ -209,9 +225,12 @@ public class OuterProdTmplTest extends AutomatedTestBase if( testname.equals(TEST_NAME8) ) Assert.assertTrue(!(heavyHittersContainsSubString("spoofOP") || heavyHittersContainsSubString("sp_spoofOP"))); - else if( !rewrites ) + else if( !rewrites ) { Assert.assertTrue(heavyHittersContainsSubString("spoofOP") || heavyHittersContainsSubString("sp_spoofOP")); + if( testname.equals(TEST_NAME9) ) + Assert.assertTrue(!heavyHittersContainsSubString("!=")); + } } finally { rtplatform = platformOld; http://git-wip-us.apache.org/repos/asf/systemml/blob/30caf365/src/test/scripts/functions/codegen/wdivmmNeq.R ---------------------------------------------------------------------- diff --git a/src/test/scripts/functions/codegen/wdivmmNeq.R b/src/test/scripts/functions/codegen/wdivmmNeq.R new file mode 100644 index 0000000..d21f32a --- /dev/null +++ b/src/test/scripts/functions/codegen/wdivmmNeq.R @@ -0,0 +1,31 @@ +#------------------------------------------------------------- +# +# Licensed to the Apache Software Foundation (ASF) under one +# or more contributor license agreements. See the NOTICE file +# distributed with this work for additional information +# regarding copyright ownership. The ASF licenses this file +# to you under the Apache License, Version 2.0 (the +# "License"); you may not use this file except in compliance +# with the License. You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, +# software distributed under the License is distributed on an +# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +# KIND, either express or implied. See the License for the +# specific language governing permissions and limitations +# under the License. +# +#------------------------------------------------------------- + +args<-commandArgs(TRUE) +options(digits=22) +library("Matrix") + +X = matrix( 3, 4000, 2000); +U = matrix( 4, 4000, 10); +V = matrix( 5, 2000, 10); +eps = 0.1; +S= ((X!=0)*(U%*%t(V)+eps)) %*% V; +writeMM(as(S, "CsparseMatrix"), paste(args[2], "S", sep="")); http://git-wip-us.apache.org/repos/asf/systemml/blob/30caf365/src/test/scripts/functions/codegen/wdivmmNeq.dml ---------------------------------------------------------------------- diff --git a/src/test/scripts/functions/codegen/wdivmmNeq.dml b/src/test/scripts/functions/codegen/wdivmmNeq.dml new file mode 100644 index 0000000..7293670 --- /dev/null +++ b/src/test/scripts/functions/codegen/wdivmmNeq.dml @@ -0,0 +1,29 @@ +#------------------------------------------------------------- +# +# Licensed to the Apache Software Foundation (ASF) under one +# or more contributor license agreements. See the NOTICE file +# distributed with this work for additional information +# regarding copyright ownership. The ASF licenses this file +# to you under the Apache License, Version 2.0 (the +# "License"); you may not use this file except in compliance +# with the License. You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, +# software distributed under the License is distributed on an +# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +# KIND, either express or implied. See the License for the +# specific language governing permissions and limitations +# under the License. +# +#------------------------------------------------------------- + +X = matrix( 3, rows=4000, cols=2000); +U = matrix( 4, rows=4000, cols=10); +V = matrix( 5, rows=2000, cols=10); +while(FALSE){} +eps = 0.1; +S= ((X!=0)*(U%*%t(V)+eps)) %*% V; + +write(S,$1)
