[SYSTEMML-2050] New rewrites for removing unnecessary ifelse operations Since the new ifelse operation is not lazily evaluated, all inputs have to be computed eagerly which incurs unnecessary overhead if the predicate could be evaluated during compilation (or recompilation). This patch introduces three classes of related rewrites, which all ensure robustness for arbitrary combinations of scalars and matrices:
a) ifelse(TRUE/FALSE, A, B) -> A/B (constant scalar predicate) b) ifelse(E, A, B) -> A/B if nnz(E)==length(E) or nnz(E)==0 (constant matrix predicate) c) ifelse(E, A, A) -> A (same input) Furthermore, this also includes a minor fix for the explain output of ternary ifelse operations (explain hops / recompile_hops). Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/e0006a27 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/e0006a27 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/e0006a27 Branch: refs/heads/master Commit: e0006a272b3e7036702c53dabad4ccf563793a26 Parents: 280d9c9 Author: Matthias Boehm <[email protected]> Authored: Thu Jan 18 19:30:14 2018 -0800 Committer: Matthias Boehm <[email protected]> Committed: Thu Jan 18 21:17:28 2018 -0800 ---------------------------------------------------------------------- src/main/java/org/apache/sysml/hops/Hop.java | 1 + .../RewriteAlgebraicSimplificationDynamic.java | 43 +++++ .../functions/misc/RewriteIfElseTest.java | 192 +++++++++++++++++++ .../functions/ternary/FullIfElseTest.java | 4 + .../functions/misc/RewriteIfElseMatrix.R | 34 ++++ .../functions/misc/RewriteIfElseMatrix.dml | 29 +++ .../functions/misc/RewriteIfElseScalar.R | 33 ++++ .../functions/misc/RewriteIfElseScalar.dml | 27 +++ 8 files changed, 363 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/e0006a27/src/main/java/org/apache/sysml/hops/Hop.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/Hop.java b/src/main/java/org/apache/sysml/hops/Hop.java index 3ed837e..a966425 100644 --- a/src/main/java/org/apache/sysml/hops/Hop.java +++ b/src/main/java/org/apache/sysml/hops/Hop.java @@ -1477,6 +1477,7 @@ public abstract class Hop implements ParseInfo HopsOpOp3String.put(OpOp3.COVARIANCE, "cov"); HopsOpOp3String.put(OpOp3.PLUS_MULT, "+*"); HopsOpOp3String.put(OpOp3.MINUS_MULT, "-*"); + HopsOpOp3String.put(OpOp3.IFELSE, "ifelse"); } protected static final HashMap<Hop.OpOp4, String> HopsOpOp4String; http://git-wip-us.apache.org/repos/asf/systemml/blob/e0006a27/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java b/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java index d60b60f..8453450 100644 --- a/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java +++ b/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java @@ -160,6 +160,7 @@ public class RewriteAlgebraicSimplificationDynamic extends HopRewriteRule hi = removeUnnecessaryCumulativeOp(hop, hi, i); //e.g., cumsum(X) -> X, if nrow(X)==1; hi = removeUnnecessaryReorgOperation(hop, hi, i); //e.g., matrix(X) -> X, if dims(in)==dims(out); r(X)->X, if 1x1 dims hi = removeUnnecessaryOuterProduct(hop, hi, i); //e.g., X*(Y%*%matrix(1,...) -> X*Y, if Y col vector + hi = removeUnnecessaryIfElseOperation(hop, hi, i);//e.g., ifelse(E, A, B) -> A, if E==TRUE or nnz(E)==length(E) if(OptimizerUtils.ALLOW_OPERATOR_FUSION) hi = fuseDatagenAndReorgOperation(hop, hi, i); //e.g., t(rand(rows=10,cols=1)) -> rand(rows=1,cols=10), if one dim=1 hi = simplifyColwiseAggregate(hop, hi, i); //e.g., colsums(X) -> sum(X) or X, if col/row vector @@ -448,6 +449,48 @@ public class RewriteAlgebraicSimplificationDynamic extends HopRewriteRule return hi; } + private static Hop removeUnnecessaryIfElseOperation(Hop parent, Hop hi, int pos) throws HopsException + { + if( !HopRewriteUtils.isTernary(hi, OpOp3.IFELSE) ) + return hi; + + Hop expr = hi.getInput().get(0); + Hop first = hi.getInput().get(1); + Hop second = hi.getInput().get(2); + boolean applied = false; + + //pattern 1: ifelse(TRUE/FALSE, A, B) -> A/B (constant scalar predicate) + if( expr instanceof LiteralOp ) { + Hop hnew = ((LiteralOp)expr).getBooleanValue() ? first : second; + if( HopRewriteUtils.isEqualSize(hnew, hi) ) { + HopRewriteUtils.replaceChildReference(parent, hi, hnew, pos ); + HopRewriteUtils.cleanupUnreferenced(hi); + LOG.debug("Applied removeUnnecessaryIfElse1 (line "+hi.getBeginLine()+")"); + hi = hnew; applied = true; + } + } + //pattern 2: ifelse(E, A, B) -> A/B if nnz(E)==length(E) or nnz(E)==0 (constant matrix predicate) + if( !applied && expr.getNnz()==expr.getLength() || expr.getNnz()==0 ) { + Hop hnew = expr.getNnz()==0 ? second : first; + if( HopRewriteUtils.isEqualSize(hnew, hi) ) { + HopRewriteUtils.replaceChildReference(parent, hi, hnew, pos ); + HopRewriteUtils.cleanupUnreferenced(hi); + LOG.debug("Applied removeUnnecessaryIfElse2 (line "+hi.getBeginLine()+")"); + hi = hnew; applied = true; + } + } + //pattern 3: ifelse(E, A, A) -> A (same input) + if( !applied && first == second //dep CSE + && HopRewriteUtils.isEqualSize(first, hi) ){ + HopRewriteUtils.replaceChildReference(parent, hi, first, pos ); + HopRewriteUtils.cleanupUnreferenced(hi); + LOG.debug("Applied removeUnnecessaryIfElse3 (line "+hi.getBeginLine()+")"); + hi = first; + } + + return hi; + } + @SuppressWarnings("unchecked") private static Hop fuseDatagenAndReorgOperation(Hop parent, Hop hi, int pos) { http://git-wip-us.apache.org/repos/asf/systemml/blob/e0006a27/src/test/java/org/apache/sysml/test/integration/functions/misc/RewriteIfElseTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/misc/RewriteIfElseTest.java b/src/test/java/org/apache/sysml/test/integration/functions/misc/RewriteIfElseTest.java new file mode 100644 index 0000000..53ee5c7 --- /dev/null +++ b/src/test/java/org/apache/sysml/test/integration/functions/misc/RewriteIfElseTest.java @@ -0,0 +1,192 @@ +/* + * 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. + */ + +package org.apache.sysml.test.integration.functions.misc; + +import java.util.HashMap; + +import org.apache.sysml.api.DMLScript; +import org.apache.sysml.api.DMLScript.RUNTIME_PLATFORM; +import org.apache.sysml.hops.OptimizerUtils; +import org.apache.sysml.lops.LopProperties.ExecType; +import org.apache.sysml.runtime.instructions.Instruction; +import org.apache.sysml.runtime.matrix.MatrixCharacteristics; +import org.apache.sysml.runtime.matrix.data.MatrixValue.CellIndex; +import org.apache.sysml.test.integration.AutomatedTestBase; +import org.apache.sysml.test.integration.TestConfiguration; +import org.apache.sysml.test.utils.TestUtils; +import org.apache.sysml.utils.Statistics; +import org.junit.Assert; +import org.junit.Test; + +public class RewriteIfElseTest extends AutomatedTestBase +{ + private static final String TEST_NAME1 = "RewriteIfElseScalar"; + private static final String TEST_NAME2 = "RewriteIfElseMatrix"; + + private static final String TEST_DIR = "functions/misc/"; + private static final String TEST_CLASS_DIR = TEST_DIR + RewriteIfElseTest.class.getSimpleName() + "/"; + + private static final int rows = 10; + private static final int cols = 10; + + @Override + public void setUp() { + TestUtils.clearAssertionInformation(); + addTestConfiguration( TEST_NAME1, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME1, new String[] { "R" }) ); + addTestConfiguration( TEST_NAME2, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME2, new String[] { "R" }) ); + } + + @Test + public void testIfElseScalarTrueNoRewritesCP() { + testRewriteIfElse(TEST_NAME1, true, false, ExecType.CP); + } + + @Test + public void testIfElseScalarFalseNoRewritesCP() { + testRewriteIfElse(TEST_NAME1, false, false, ExecType.CP); + } + + @Test + public void testIfElseScalarTrueRewritesCP() { + testRewriteIfElse(TEST_NAME1, true, true, ExecType.CP); + } + + @Test + public void testIfElseScalarFalseRewritesCP() { + testRewriteIfElse(TEST_NAME1, false, true, ExecType.CP); + } + + @Test + public void testIfElseMatrixTrueNoRewritesCP() { + testRewriteIfElse(TEST_NAME2, true, false, ExecType.CP); + } + + @Test + public void testIfElseMatrixFalseNoRewritesCP() { + testRewriteIfElse(TEST_NAME2, false, false, ExecType.CP); + } + + @Test + public void testIfElseMatrixTrueRewritesCP() { + testRewriteIfElse(TEST_NAME2, true, true, ExecType.CP); + } + + @Test + public void testIfElseMatrixFalseRewritesCP() { + testRewriteIfElse(TEST_NAME2, false, true, ExecType.CP); + } + + @Test + public void testIfElseScalarTrueNoRewritesSP() { + testRewriteIfElse(TEST_NAME1, true, false, ExecType.SPARK); + } + + @Test + public void testIfElseScalarFalseNoRewritesSP() { + testRewriteIfElse(TEST_NAME1, false, false, ExecType.SPARK); + } + + @Test + public void testIfElseScalarTrueRewritesSP() { + testRewriteIfElse(TEST_NAME1, true, true, ExecType.SPARK); + } + + @Test + public void testIfElseScalarFalseRewritesSP() { + testRewriteIfElse(TEST_NAME1, false, true, ExecType.SPARK); + } + + @Test + public void testIfElseMatrixTrueNoRewritesSP() { + testRewriteIfElse(TEST_NAME2, true, false, ExecType.SPARK); + } + + @Test + public void testIfElseMatrixFalseNoRewritesSP() { + testRewriteIfElse(TEST_NAME2, false, false, ExecType.SPARK); + } + + @Test + public void testIfElseMatrixTrueRewritesSP() { + testRewriteIfElse(TEST_NAME2, true, true, ExecType.SPARK); + } + + @Test + public void testIfElseMatrixFalseRewritesSP() { + testRewriteIfElse(TEST_NAME2, false, true, ExecType.SPARK); + } + + private void testRewriteIfElse(String testname, boolean pred, boolean rewrites, ExecType et) + { + RUNTIME_PLATFORM platformOld = rtplatform; + switch( et ){ + case MR: rtplatform = RUNTIME_PLATFORM.HADOOP; break; + case SPARK: rtplatform = RUNTIME_PLATFORM.SPARK; break; + default: rtplatform = RUNTIME_PLATFORM.HYBRID_SPARK; break; + } + + boolean sparkConfigOld = DMLScript.USE_LOCAL_SPARK_CONFIG; + if( rtplatform == RUNTIME_PLATFORM.SPARK || rtplatform == RUNTIME_PLATFORM.HYBRID_SPARK ) + DMLScript.USE_LOCAL_SPARK_CONFIG = true; + + boolean rewritesOld = OptimizerUtils.ALLOW_ALGEBRAIC_SIMPLIFICATION; + OptimizerUtils.ALLOW_ALGEBRAIC_SIMPLIFICATION = rewrites; + + try + { + TestConfiguration config = getTestConfiguration(testname); + loadTestConfiguration(config); + + String HOME = SCRIPT_DIR + TEST_DIR; + fullDMLScriptName = HOME + testname + ".dml"; + programArgs = new String[] { "-explain", "hops", "-stats", "-args", + testname.equals(TEST_NAME1) ? String.valueOf(pred).toUpperCase() : input("X"), output("R") }; + fullRScriptName = HOME + testname + ".R"; + rCmd = getRCmd(testname.equals(TEST_NAME1) ? String.valueOf(pred).toUpperCase() : inputDir(), expectedDir()); + + if( testname.equals(TEST_NAME2) ) { + double val = pred ? 1 : 0; + double[][] X = getRandomMatrix(rows, cols, val, val, 1.0, 7); + writeInputMatrixWithMTD("X", X, true, + new MatrixCharacteristics(10,10,1000,1000,pred?100:0)); + } + + //execute tests + runTest(true, false, null, -1); + runRScript(true); + + //compare matrices + HashMap<CellIndex, Double> dmlfile = readDMLMatrixFromHDFS("R"); + HashMap<CellIndex, Double> rfile = readRMatrixFromFS("R"); + Assert.assertTrue(TestUtils.compareMatrices(dmlfile, rfile, Math.pow(10,-10), "Stat-DML", "Stat-R")); + + //check for presence of power operator, if we did a rewrite + if( rewrites ) { + String opcode = et==ExecType.SPARK ? Instruction.SP_INST_PREFIX + "rand" : "rand"; + Assert.assertTrue(heavyHittersContainsString(opcode) && Statistics.getCPHeavyHitterCount(opcode)==1); + } + } + finally { + OptimizerUtils.ALLOW_ALGEBRAIC_SIMPLIFICATION = rewritesOld; + rtplatform = platformOld; + DMLScript.USE_LOCAL_SPARK_CONFIG = sparkConfigOld; + } + } +} http://git-wip-us.apache.org/repos/asf/systemml/blob/e0006a27/src/test/java/org/apache/sysml/test/integration/functions/ternary/FullIfElseTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/ternary/FullIfElseTest.java b/src/test/java/org/apache/sysml/test/integration/functions/ternary/FullIfElseTest.java index 581a6cd..95f43ac 100644 --- a/src/test/java/org/apache/sysml/test/integration/functions/ternary/FullIfElseTest.java +++ b/src/test/java/org/apache/sysml/test/integration/functions/ternary/FullIfElseTest.java @@ -25,6 +25,7 @@ import org.junit.Test; import org.apache.sysml.api.DMLScript; import org.apache.sysml.api.DMLScript.RUNTIME_PLATFORM; +import org.apache.sysml.hops.OptimizerUtils; import org.apache.sysml.lops.LopProperties.ExecType; import org.apache.sysml.runtime.matrix.data.MatrixValue.CellIndex; import org.apache.sysml.test.integration.AutomatedTestBase; @@ -305,8 +306,10 @@ public class FullIfElseTest extends AutomatedTestBase } boolean sparkConfigOld = DMLScript.USE_LOCAL_SPARK_CONFIG; + boolean rewritesOld = OptimizerUtils.ALLOW_ALGEBRAIC_SIMPLIFICATION; if( rtplatform == RUNTIME_PLATFORM.SPARK || rtplatform == RUNTIME_PLATFORM.HYBRID_SPARK ) DMLScript.USE_LOCAL_SPARK_CONFIG = true; + OptimizerUtils.ALLOW_ALGEBRAIC_SIMPLIFICATION = false; //test runtime ops try { @@ -340,6 +343,7 @@ public class FullIfElseTest extends AutomatedTestBase finally { rtplatform = platformOld; DMLScript.USE_LOCAL_SPARK_CONFIG = sparkConfigOld; + OptimizerUtils.ALLOW_ALGEBRAIC_SIMPLIFICATION = rewritesOld; } } http://git-wip-us.apache.org/repos/asf/systemml/blob/e0006a27/src/test/scripts/functions/misc/RewriteIfElseMatrix.R ---------------------------------------------------------------------- diff --git a/src/test/scripts/functions/misc/RewriteIfElseMatrix.R b/src/test/scripts/functions/misc/RewriteIfElseMatrix.R new file mode 100644 index 0000000..894e5a8 --- /dev/null +++ b/src/test/scripts/functions/misc/RewriteIfElseMatrix.R @@ -0,0 +1,34 @@ +#------------------------------------------------------------- +# +# 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") + +E = as.matrix(readMM(paste(args[1], "X.mtx", sep=""))) + +A = matrix(3, 10, 10); +B = matrix(7, 10, 10); +R = matrix(ifelse(E, A, B), 10, 10); +R[2,1] = 1; + +writeMM(as(R, "CsparseMatrix"), paste(args[2], "R", sep="")); + http://git-wip-us.apache.org/repos/asf/systemml/blob/e0006a27/src/test/scripts/functions/misc/RewriteIfElseMatrix.dml ---------------------------------------------------------------------- diff --git a/src/test/scripts/functions/misc/RewriteIfElseMatrix.dml b/src/test/scripts/functions/misc/RewriteIfElseMatrix.dml new file mode 100644 index 0000000..87c2732 --- /dev/null +++ b/src/test/scripts/functions/misc/RewriteIfElseMatrix.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. +# +#------------------------------------------------------------- + +E = read($1); + +A = matrix(3, 10, 10); +B = matrix(7, 10, 10); +R = ifelse(E, A, B); +R[2,1] = 1; + +write(R, $2); http://git-wip-us.apache.org/repos/asf/systemml/blob/e0006a27/src/test/scripts/functions/misc/RewriteIfElseScalar.R ---------------------------------------------------------------------- diff --git a/src/test/scripts/functions/misc/RewriteIfElseScalar.R b/src/test/scripts/functions/misc/RewriteIfElseScalar.R new file mode 100644 index 0000000..26fc756 --- /dev/null +++ b/src/test/scripts/functions/misc/RewriteIfElseScalar.R @@ -0,0 +1,33 @@ +#------------------------------------------------------------- +# +# 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") + +A = matrix(3, 10, 10); +B = matrix(7, 10, 10); +E = matrix(as.logical(args[1]), 10, 10); +R = matrix(ifelse(E, A, B), 10, 10); +R[2,1] = 1; + +writeMM(as(R, "CsparseMatrix"), paste(args[2], "R", sep="")); + http://git-wip-us.apache.org/repos/asf/systemml/blob/e0006a27/src/test/scripts/functions/misc/RewriteIfElseScalar.dml ---------------------------------------------------------------------- diff --git a/src/test/scripts/functions/misc/RewriteIfElseScalar.dml b/src/test/scripts/functions/misc/RewriteIfElseScalar.dml new file mode 100644 index 0000000..d5423e6 --- /dev/null +++ b/src/test/scripts/functions/misc/RewriteIfElseScalar.dml @@ -0,0 +1,27 @@ +#------------------------------------------------------------- +# +# 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. +# +#------------------------------------------------------------- + +A = matrix(3, 10, 10); +B = matrix(7, 10, 10); +R = ifelse($1, A, B); +R[2,1] = 1; + +write(R, $2);
