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/05/14 20:22:37 UTC
[4/5] incubator-systemml git commit: [SYSTEMML-427][SYSTEMML-512]
Extended IPA (propagate scalar variables)
[SYSTEMML-427][SYSTEMML-512] Extended IPA (propagate scalar variables)
So far, our inter-procedural analysis propagated only scalar literals
into functions, which requires that literals are already replaced as
constants at parser level which is often not the case. This patch
extends IPA to also propagate scalar variables into functions that are
called once (in order to guarantee correctness). Furthermore, this
change also includes additional test cases created in SYSTEMML-512.
Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/bc97f384
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/bc97f384
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/bc97f384
Branch: refs/heads/master
Commit: bc97f384a51b3a255e7b8da25d37334d96ca4df7
Parents: 0ef2223
Author: Matthias Boehm <mb...@us.ibm.com>
Authored: Fri May 13 23:51:35 2016 -0700
Committer: Matthias Boehm <mb...@us.ibm.com>
Committed: Sat May 14 00:16:59 2016 -0700
----------------------------------------------------------------------
.../sysml/hops/ipa/InterProceduralAnalysis.java | 67 +++++++++------
.../misc/IPAScalarVariablePropagationTest.java | 89 ++++++++++++++++++++
.../misc/IPAScalarVariablePropagation.dml | 55 ++++++++++++
.../functions/misc/ZPackageSuite.java | 1 +
4 files changed, 185 insertions(+), 27 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/bc97f384/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java b/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java
index 3cef75b..00fd643 100644
--- a/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java
+++ b/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java
@@ -117,7 +117,6 @@ import org.apache.sysml.udf.lib.OrderWrapper;
@SuppressWarnings("deprecation")
public class InterProceduralAnalysis
{
-
private static final boolean LDEBUG = false; //internal local debug level
private static final Log LOG = LogFactory.getLog(InterProceduralAnalysis.class.getName());
@@ -129,6 +128,7 @@ public class InterProceduralAnalysis
private static final boolean FLAG_FUNCTION_RECOMPILE_ONCE = true; //flag functions which require recompilation inside a loop for full function recompile
private static final boolean REMOVE_UNNECESSARY_CHECKPOINTS = true; //remove unnecessary checkpoints (unconditionally overwritten intermediates)
private static final boolean REMOVE_CONSTANT_BINARY_OPS = true; //remove constant binary operations (e.g., X*ones, where ones=matrix(1,...))
+ private static final boolean PROPAGATE_SCALAR_VARS_INTO_FUN = true; //propagate scalar variables into functions that are called once
static {
// for internal debugging only
@@ -138,8 +138,7 @@ public class InterProceduralAnalysis
}
}
- public InterProceduralAnalysis()
- {
+ public InterProceduralAnalysis() {
//do nothing
}
@@ -170,12 +169,12 @@ public class InterProceduralAnalysis
DMLTranslator.resetHopsDAGVisitStatus( dmlp );
}
+ //step 2: propagate statistics and scalars into functions and across DAGs
if( !fcandCounts.isEmpty() || INTRA_PROCEDURAL_ANALYSIS ) {
- //step 2: propagate statistics into functions and across DAGs
//(callVars used to chain outputs/inputs of multiple functions calls)
LocalVariableMap callVars = new LocalVariableMap();
for ( StatementBlock sb : dmlp.getStatementBlocks() ) //propagate stats into candidates
- propagateStatisticsAcrossBlock( sb, fcandCounts.keySet(), callVars, fcandSafeNNZ, new HashSet<String>() );
+ propagateStatisticsAcrossBlock( sb, fcandCounts, callVars, fcandSafeNNZ, new HashSet<String>() );
}
//step 3: remove unused functions (e.g., inlined or never called)
@@ -228,7 +227,7 @@ public class InterProceduralAnalysis
//step 2: propagate statistics into functions and across DAGs
//(callVars used to chain outputs/inputs of multiple functions calls)
LocalVariableMap callVars = new LocalVariableMap();
- propagateStatisticsAcrossBlock( sb, fcandCounts.keySet(), callVars, fcandSafeNNZ, new HashSet<String>() );
+ propagateStatisticsAcrossBlock( sb, fcandCounts, callVars, fcandSafeNNZ, new HashSet<String>() );
}
return fcandCounts.keySet();
@@ -437,7 +436,7 @@ public class InterProceduralAnalysis
* @throws ParseException
* @throws CloneNotSupportedException
*/
- private void propagateStatisticsAcrossBlock( StatementBlock sb, Set<String> fcand, LocalVariableMap callVars, Map<String, Set<Long>> fcandSafeNNZ, Set<String> fnStack )
+ private void propagateStatisticsAcrossBlock( StatementBlock sb, Map<String, Integer> fcand, LocalVariableMap callVars, Map<String, Set<Long>> fcandSafeNNZ, Set<String> fnStack )
throws HopsException, ParseException
{
if (sb instanceof FunctionStatementBlock)
@@ -592,7 +591,7 @@ public class InterProceduralAnalysis
* @throws HopsException
* @throws ParseException
*/
- private void propagateStatisticsIntoFunctions(DMLProgram prog, ArrayList<Hop> roots, Set<String> fcand, LocalVariableMap callVars, Map<String, Set<Long>> fcandSafeNNZ, Set<String> fnStack )
+ private void propagateStatisticsIntoFunctions(DMLProgram prog, ArrayList<Hop> roots, Map<String, Integer> fcand, LocalVariableMap callVars, Map<String, Set<Long>> fcandSafeNNZ, Set<String> fnStack )
throws HopsException, ParseException
{
for( Hop root : roots )
@@ -608,7 +607,7 @@ public class InterProceduralAnalysis
* @throws HopsException
* @throws ParseException
*/
- private void propagateStatisticsIntoFunctions(DMLProgram prog, Hop hop, Set<String> fcand, LocalVariableMap callVars, Map<String, Set<Long>> fcandSafeNNZ, Set<String> fnStack )
+ private void propagateStatisticsIntoFunctions(DMLProgram prog, Hop hop, Map<String, Integer> fcand, LocalVariableMap callVars, Map<String, Set<Long>> fcandSafeNNZ, Set<String> fnStack )
throws HopsException, ParseException
{
if( hop.getVisited() == VisitStatus.DONE )
@@ -628,7 +627,7 @@ public class InterProceduralAnalysis
FunctionStatementBlock fsb = prog.getFunctionStatementBlock(fop.getFunctionNamespace(), fop.getFunctionName());
FunctionStatement fstmt = (FunctionStatement)fsb.getStatement(0);
- if( fcand.contains(fkey) &&
+ if( fcand.containsKey(fkey) &&
!fnStack.contains(fkey) ) //prevent recursion
{
//maintain function call stack
@@ -636,7 +635,8 @@ public class InterProceduralAnalysis
//create mapping and populate symbol table for refresh
LocalVariableMap tmpVars = new LocalVariableMap();
- populateLocalVariableMapForFunctionCall( fstmt, fop, tmpVars, fcandSafeNNZ.get(fkey) );
+ populateLocalVariableMapForFunctionCall( fstmt, fop,
+ callVars, tmpVars, fcandSafeNNZ.get(fkey), fcand.get(fkey) );
//recursively propagate statistics
propagateStatisticsAcrossBlock(fsb, fcand, tmpVars, fcandSafeNNZ, fnStack);
@@ -673,10 +673,13 @@ public class InterProceduralAnalysis
*
* @param fstmt
* @param fop
+ * @param callvars
* @param vars
- * @throws HopsException
+ * @param inputSafeNNZ
+ * @param singleton
+ * @throws HopsException
*/
- private void populateLocalVariableMapForFunctionCall( FunctionStatement fstmt, FunctionOp fop, LocalVariableMap vars, Set<Long> inputSafeNNZ )
+ private void populateLocalVariableMapForFunctionCall( FunctionStatement fstmt, FunctionOp fop, LocalVariableMap callvars, LocalVariableMap vars, Set<Long> inputSafeNNZ, Integer numCalls )
throws HopsException
{
ArrayList<DataIdentifier> inputVars = fstmt.getInputParams();
@@ -700,24 +703,34 @@ public class InterProceduralAnalysis
mo.setMetaData(meta);
vars.put(dat.getName(), mo);
}
- else if( input.getDataType()==DataType.SCALAR
- && input instanceof LiteralOp )
+ else if( input.getDataType()==DataType.SCALAR )
{
- //propagate literal scalars into functions
- LiteralOp lit = (LiteralOp)input;
- ScalarObject scalar = null;
- switch(input.getValueType())
+ //always propagate scalar literals into functions
+ //(for multiple calls, literal equivalence already checked)
+ if( input instanceof LiteralOp ) {
+ LiteralOp lit = (LiteralOp)input;
+ ScalarObject scalar = null;
+ switch(input.getValueType()) {
+ case DOUBLE: scalar = new DoubleObject(lit.getDoubleValue()); break;
+ case INT: scalar = new IntObject(lit.getLongValue()); break;
+ case BOOLEAN: scalar = new BooleanObject(lit.getBooleanValue()); break;
+ case STRING: scalar = new StringObject(lit.getStringValue()); break;
+ default: //do nothing
+ }
+ vars.put(dat.getName(), scalar);
+ }
+ //propagate scalar variables into functions if called once
+ //and input scalar is existing variable in symbol table
+ else if( PROPAGATE_SCALAR_VARS_INTO_FUN
+ && numCalls != null && numCalls == 1
+ && input instanceof DataOp )
{
- case DOUBLE: scalar = new DoubleObject(lit.getDoubleValue()); break;
- case INT: scalar = new IntObject(lit.getLongValue()); break;
- case BOOLEAN: scalar = new BooleanObject(lit.getBooleanValue()); break;
- case STRING: scalar = new StringObject(lit.getStringValue()); break;
- default:
- //do nothing
+ Data scalar = callvars.get(input.getName());
+ if( scalar != null && scalar instanceof ScalarObject ) {
+ vars.put(dat.getName(), scalar);
+ }
}
- vars.put(dat.getName(), scalar);
}
-
}
}
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/bc97f384/src/test/java/org/apache/sysml/test/integration/functions/misc/IPAScalarVariablePropagationTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/sysml/test/integration/functions/misc/IPAScalarVariablePropagationTest.java b/src/test/java/org/apache/sysml/test/integration/functions/misc/IPAScalarVariablePropagationTest.java
new file mode 100644
index 0000000..1ad1f8b
--- /dev/null
+++ b/src/test/java/org/apache/sysml/test/integration/functions/misc/IPAScalarVariablePropagationTest.java
@@ -0,0 +1,89 @@
+/*
+ * 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 org.junit.Assert;
+import org.junit.Test;
+import org.apache.sysml.hops.OptimizerUtils;
+import org.apache.sysml.lops.WeightedCrossEntropy;
+import org.apache.sysml.lops.WeightedDivMM;
+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;
+
+/**
+ *
+ */
+public class IPAScalarVariablePropagationTest extends AutomatedTestBase
+{
+ private final static String TEST_NAME1 = "IPAScalarVariablePropagation";
+ private final static String TEST_DIR = "functions/misc/";
+ private final static String TEST_CLASS_DIR = TEST_DIR + IPAScalarVariablePropagationTest.class.getSimpleName() + "/";
+
+ @Override
+ public void setUp() {
+ TestUtils.clearAssertionInformation();
+ addTestConfiguration( TEST_NAME1, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME1, new String[]{}) );
+ }
+
+ @Test
+ public void testScalarPropagationNoIPA() {
+ runIPAScalarVariablePropagationTest( TEST_NAME1, false );
+ }
+
+ @Test
+ public void testScalarPropagationIPA() {
+ runIPAScalarVariablePropagationTest( TEST_NAME1, true );
+ }
+
+ /**
+ *
+ * @param testname
+ * @param IPA
+ */
+ private void runIPAScalarVariablePropagationTest( String testname, boolean IPA )
+ {
+ boolean oldFlagIPA = OptimizerUtils.ALLOW_INTER_PROCEDURAL_ANALYSIS;
+
+ try
+ {
+ TestConfiguration config = getTestConfiguration(testname);
+ loadTestConfiguration(config);
+
+ String HOME = SCRIPT_DIR + TEST_DIR;
+ fullDMLScriptName = HOME + testname + ".dml";
+ programArgs = new String[]{"-stats","-args", String.valueOf(10) };
+ OptimizerUtils.ALLOW_INTER_PROCEDURAL_ANALYSIS = IPA;
+
+ //run test, incl expected MR jobs (in case if IPA 0 due to scalar propagation)
+ runTest(true, false, null, IPA ? 0 : 28);
+
+ //check for applied rewrites (in both cases, we expect the rewrites to happen:
+ // - without IPA it should be marked for recompilation and recompiled per iteration
+ // - with IPA the scalar rank should be directly propagated into the function
+ Assert.assertTrue("Missing opcode wdivmm", Statistics.getCPHeavyHitterOpCodes().contains(WeightedDivMM.OPCODE_CP));
+ Assert.assertTrue("Missing opcode wcemm", Statistics.getCPHeavyHitterOpCodes().contains(WeightedCrossEntropy.OPCODE_CP));
+ }
+ finally {
+ OptimizerUtils.ALLOW_INTER_PROCEDURAL_ANALYSIS = oldFlagIPA;
+ }
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/bc97f384/src/test/scripts/functions/misc/IPAScalarVariablePropagation.dml
----------------------------------------------------------------------
diff --git a/src/test/scripts/functions/misc/IPAScalarVariablePropagation.dml b/src/test/scripts/functions/misc/IPAScalarVariablePropagation.dml
new file mode 100644
index 0000000..9abc19d
--- /dev/null
+++ b/src/test/scripts/functions/misc/IPAScalarVariablePropagation.dml
@@ -0,0 +1,55 @@
+#-------------------------------------------------------------
+#
+# 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.
+#
+#-------------------------------------------------------------
+
+
+pnmf = function(matrix[double] V, integer max_iteration, integer rank) return (matrix[double] W, matrix[double] H) {
+ n = nrow(V)
+ m = ncol(V)
+
+ range = 0.1
+ W = Rand(rows=n, cols=rank, min=0, max=range, pdf="uniform")
+ H = Rand(rows=rank, cols=m, min=0, max=range, pdf="uniform")
+
+ i=0
+ while(i < max_iteration) {
+ H = (H * (t(W) %*% (V/(W%*%H))))/t(colSums(W))
+ W = (W * ((V/(W%*%H)) %*% t(H)))/t(rowSums(H))
+ i = i + 1;
+ print("at iteration: "+i)
+ }
+}
+
+negloglikfunc = function(matrix[double] V, matrix[double] W, matrix[double] H) return (double negloglik) {
+ negloglik = -1 * (sum(V*log(W%*%H)) - as.scalar(colSums(W)%*%rowSums(H)))
+}
+
+# data & args
+X = rand(rows=2000,cols=2000, sparsity=0.001)
+max_iteration = 5
+rank = as.integer($1)
+
+# run PNMF and evaluate
+[W, H] = pnmf(X, max_iteration, rank)
+negloglik_temp = negloglikfunc(X, W, H)
+
+# write outputs
+negloglik = matrix(negloglik_temp, rows=1, cols=1)
+print(sum(negloglik)+" "+sum(W)+" "+sum(H));
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/bc97f384/src/test_suites/java/org/apache/sysml/test/integration/functions/misc/ZPackageSuite.java
----------------------------------------------------------------------
diff --git a/src/test_suites/java/org/apache/sysml/test/integration/functions/misc/ZPackageSuite.java b/src/test_suites/java/org/apache/sysml/test/integration/functions/misc/ZPackageSuite.java
index 0e01913..dce345b 100644
--- a/src/test_suites/java/org/apache/sysml/test/integration/functions/misc/ZPackageSuite.java
+++ b/src/test_suites/java/org/apache/sysml/test/integration/functions/misc/ZPackageSuite.java
@@ -35,6 +35,7 @@ import org.junit.runners.Suite;
InvalidFunctionSignatureTest.class,
IPALiteralReplacementTest.class,
IPAScalarRecursionTest.class,
+ IPAScalarVariablePropagationTest.class,
IPAUnknownRecursionTest.class,
LongOverflowTest.class,
NegativeLoopIncrementsTest.class,