This is an automated email from the ASF dual-hosted git repository.
mboehm7 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/systemds.git
The following commit(s) were added to refs/heads/master by this push:
new 0bf27ea [SYSTEMDS-2802] Fix parfor handling of negative loop
increments
0bf27ea is described below
commit 0bf27eaad3ffb40da8e6bf87d42721f0a333ba19
Author: Matthias Boehm <[email protected]>
AuthorDate: Sat Jan 23 18:13:32 2021 +0100
[SYSTEMDS-2802] Fix parfor handling of negative loop increments
* Fix parfor dependency analysis for negative increments (via
normalization)
* Fix parfor runtime program block (determine number of iterations
correctly, to prevent invalid early-abort)
* Fix removed local debug flag for parfor dependency analysis
* Tests for parfor dependency analysis and runtime predicates
---
.../apache/sysds/parser/ParForStatementBlock.java | 26 ++++++-
.../runtime/controlprogram/ParForProgramBlock.java | 7 +-
.../parfor/ParForDependencyAnalysisTest.java | 9 ++-
.../parfor/misc/ForLoopPredicateTest.java | 90 +++++++++++-----------
src/test/scripts/component/parfor/parfor55a.dml | 29 +++++++
src/test/scripts/component/parfor/parfor55b.dml | 29 +++++++
.../scripts/functions/parfor/parfor_pred1_neg.dml | 25 ++++++
.../scripts/functions/parfor/parfor_pred2_neg.dml | 27 +++++++
8 files changed, 189 insertions(+), 53 deletions(-)
diff --git a/src/main/java/org/apache/sysds/parser/ParForStatementBlock.java
b/src/main/java/org/apache/sysds/parser/ParForStatementBlock.java
index b88d8c3..af88d60 100644
--- a/src/main/java/org/apache/sysds/parser/ParForStatementBlock.java
+++ b/src/main/java/org/apache/sysds/parser/ParForStatementBlock.java
@@ -33,6 +33,10 @@ import org.apache.sysds.hops.IndexingOp;
import org.apache.sysds.hops.LiteralOp;
import org.apache.sysds.hops.OptimizerUtils;
import org.apache.sysds.hops.rewrite.HopRewriteUtils;
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.log4j.Level;
+import org.apache.log4j.Logger;
import org.apache.sysds.common.Builtins;
import org.apache.sysds.common.Types.DataType;
import org.apache.sysds.common.Types.OpOp1;
@@ -60,6 +64,9 @@ import org.apache.sysds.runtime.util.UtilFunctions;
*/
public class ParForStatementBlock extends ForStatementBlock
{
+ private static final boolean LDEBUG = false; //internal local debug
level
+ protected static final Log LOG =
LogFactory.getLog(ParForStatementBlock.class.getName());
+
//external parameter names
private static HashSet<String> _paramNames;
public static final String CHECK = "check"; //run loop
dependency analysis
@@ -140,6 +147,13 @@ public class ParForStatementBlock extends ForStatementBlock
if( USE_FN_CACHE ) {
_fncache = new HashMap<>();
}
+
+ // for internal debugging only
+ if( LDEBUG ) {
+
Logger.getLogger("org.apache.sysds.parser.ParForStatementBlock")
+ .setLevel(Level.TRACE);
+ System.out.println();
+ }
}
public ParForStatementBlock() {
@@ -908,7 +922,15 @@ public class ParForStatementBlock extends ForStatementBlock
incr =
((IntIdentifier)ip.getIncrementExpr()).getValue();
else
incr = ( low <= up ) ? 1 : -1;
-
+
+ //normalize bounds to positive
increment (for dependency analysis only)
+ if( incr < 0 ) {
+ long tmp = low;
+ low = up;
+ up = tmp;
+ incr *= -1; //positive increment
+ }
+
_bounds._lower.put(ip.getIterVar()._name, low);
_bounds._upper.put(ip.getIterVar()._name, up);
_bounds._increment.put(ip.getIterVar()._name, incr);
@@ -1093,7 +1115,7 @@ public class ParForStatementBlock extends
ForStatementBlock
//min/max bound
int len = Math.max(f1._b.length, f2._b.length);
boolean invalid = false;
- for( int i=0; i<len; i++ )
+ for( int i=0; i<len; i++ )
{
String var=(f1._b.length>i) ? f1._vars[i] :
f2._vars[i];
if( !_bounds._lower.containsKey(var) ||
!_bounds._upper.containsKey(var) ) {
diff --git
a/src/main/java/org/apache/sysds/runtime/controlprogram/ParForProgramBlock.java
b/src/main/java/org/apache/sysds/runtime/controlprogram/ParForProgramBlock.java
index 1e4281c..d95512f 100644
---
a/src/main/java/org/apache/sysds/runtime/controlprogram/ParForProgramBlock.java
+++
b/src/main/java/org/apache/sysds/runtime/controlprogram/ParForProgramBlock.java
@@ -569,7 +569,8 @@ public class ParForProgramBlock extends ForProgramBlock
+ "of variable '" + _iterPredVar + "' must
evaluate to a non-zero value.");
//early exit on num iterations = zero
- _numIterations = computeNumIterations(from, to, incr);
+ _numIterations = UtilFunctions.getSeqLength(
+ from.getDoubleValue(), to.getDoubleValue(),
incr.getDoubleValue());
if( _numIterations <= 0 )
return; //avoid unnecessary optimization/initialization
@@ -1519,10 +1520,6 @@ public class ParForProgramBlock extends ForProgramBlock
StatisticMonitor.putPfPwMapping(_ID, _pwIDs[i]);
}
}
-
- private static long computeNumIterations( IntObject from, IntObject to,
IntObject incr ) {
- return (long)Math.ceil(((double)(to.getLongValue() -
from.getLongValue() + 1)) / incr.getLongValue());
- }
/**
* NOTE: Only required for remote parfor. Hence, there is no need to
transfer DMLConfig to
diff --git
a/src/test/java/org/apache/sysds/test/component/parfor/ParForDependencyAnalysisTest.java
b/src/test/java/org/apache/sysds/test/component/parfor/ParForDependencyAnalysisTest.java
index e8dac4e..04f575a 100644
---
a/src/test/java/org/apache/sysds/test/component/parfor/ParForDependencyAnalysisTest.java
+++
b/src/test/java/org/apache/sysds/test/component/parfor/ParForDependencyAnalysisTest.java
@@ -68,6 +68,8 @@ import org.apache.sysds.test.TestConfiguration;
* 53a: no, 53b dep, 53c dep, 53d dep, 53e dep
* * lists
* 54a: no, 54b: no, 54c: dep, 54d: dep
+ * * negative loop increment
+ * 55a: no, 55b: yes
*/
public class ParForDependencyAnalysisTest extends AutomatedTestBase
{
@@ -325,6 +327,12 @@ public class ParForDependencyAnalysisTest extends
AutomatedTestBase
@Test
public void testDependencyAnalysis54d() { runTest("parfor54d.dml",
true); }
+ @Test
+ public void testDependencyAnalysis55a() { runTest("parfor55a.dml",
false); }
+
+ @Test
+ public void testDependencyAnalysis55b() { runTest("parfor55b.dml",
true); }
+
private void runTest( String scriptFilename, boolean expectedException
) {
boolean raisedException = false;
try
@@ -371,5 +379,4 @@ public class ParForDependencyAnalysisTest extends
AutomatedTestBase
//check correctness
Assert.assertEquals(expectedException, raisedException);
}
-
}
diff --git
a/src/test/java/org/apache/sysds/test/functions/parfor/misc/ForLoopPredicateTest.java
b/src/test/java/org/apache/sysds/test/functions/parfor/misc/ForLoopPredicateTest.java
index aea2a15..c2ecb9e 100644
---
a/src/test/java/org/apache/sysds/test/functions/parfor/misc/ForLoopPredicateTest.java
+++
b/src/test/java/org/apache/sysds/test/functions/parfor/misc/ForLoopPredicateTest.java
@@ -29,7 +29,6 @@ import org.apache.sysds.test.TestConfiguration;
public class ForLoopPredicateTest extends AutomatedTestBase
{
-
private final static String TEST_NAME1 = "for_pred1a"; //const
private final static String TEST_NAME2 = "for_pred1b"; //const seq
private final static String TEST_NAME3 = "for_pred2a"; //var
@@ -37,6 +36,8 @@ public class ForLoopPredicateTest extends AutomatedTestBase
private final static String TEST_NAME5 = "for_pred3a"; //expression
private final static String TEST_NAME6 = "for_pred3b"; //expression seq
private final static String TEST_NAME7 = "for_pred1a_seq"; //const seq
two parameters (this tests is only for parser)
+ private final static String TEST_NAME8 = "parfor_pred1_neg"; //to:from
(negative increment)
+ private final static String TEST_NAME9 = "parfor_pred2_neg"; //2:1
(negative increment, two steps)
private final static String TEST_DIR = "functions/parfor/";
private final static String TEST_CLASS_DIR = TEST_DIR +
ForLoopPredicateTest.class.getSimpleName() + "/";
@@ -45,8 +46,7 @@ public class ForLoopPredicateTest extends AutomatedTestBase
private final static int increment = 1;
@Override
- public void setUp()
- {
+ public void setUp() {
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"}));
addTestConfiguration(TEST_NAME3, new
TestConfiguration(TEST_CLASS_DIR, TEST_NAME3, new String[]{"R"}));
@@ -54,102 +54,103 @@ public class ForLoopPredicateTest extends
AutomatedTestBase
addTestConfiguration(TEST_NAME5, new
TestConfiguration(TEST_CLASS_DIR, TEST_NAME5, new String[]{"R"}));
addTestConfiguration(TEST_NAME6, new
TestConfiguration(TEST_CLASS_DIR, TEST_NAME6, new String[]{"R"}));
addTestConfiguration(TEST_NAME7, new
TestConfiguration(TEST_CLASS_DIR, TEST_NAME7, new String[]{"R"}));
+ addTestConfiguration(TEST_NAME8, new
TestConfiguration(TEST_CLASS_DIR, TEST_NAME8, new String[]{"R"}));
+ addTestConfiguration(TEST_NAME9, new
TestConfiguration(TEST_CLASS_DIR, TEST_NAME9, new String[]{"R"}));
}
@Test
- public void testForConstIntegerPredicate()
- {
+ public void testForConstIntegerPredicate() {
runForPredicateTest(1, true);
}
@Test
- public void testForConstIntegerSeq2ParametersPredicate()
- {
+ public void testForConstIntegerSeq2ParametersPredicate() {
runForPredicateTest(7, true);
}
@Test
- public void testForConstIntegerSeqPredicate()
- {
+ public void testForConstIntegerSeqPredicate() {
runForPredicateTest(2, true);
}
@Test
- public void testForVariableIntegerPredicate()
- {
+ public void testForVariableIntegerPredicate() {
runForPredicateTest(3, true);
}
@Test
- public void testForVariableIntegerSeqPredicate()
- {
+ public void testForVariableIntegerSeqPredicate() {
runForPredicateTest(4, true);
}
@Test
- public void testForExpressionIntegerPredicate()
- {
+ public void testForExpressionIntegerPredicate() {
runForPredicateTest(5, true);
}
@Test
- public void testForExpressionIntegerSeqPredicate()
- {
+ public void testForExpressionIntegerSeqPredicate() {
runForPredicateTest(6, true);
}
@Test
- public void testForConstDoublePredicate()
- {
+ public void testForConstDoublePredicate() {
runForPredicateTest(1, false);
}
@Test
- public void testForConstDoubleSeq2ParametersPredicate()
- {
+ public void testForConstDoubleSeq2ParametersPredicate() {
runForPredicateTest(7, false);
}
@Test
- public void testForConstDoubleSeqPredicate()
- {
+ public void testForConstDoubleSeqPredicate() {
runForPredicateTest(2, false);
}
@Test
- public void testForVariableDoublePredicate()
- {
+ public void testForVariableDoublePredicate() {
runForPredicateTest(3, false);
}
@Test
- public void testForVariableDoubleSeqPredicate()
- {
+ public void testForVariableDoubleSeqPredicate() {
runForPredicateTest(4, false);
}
@Test
- public void testForExpressionDoublePredicate()
- {
+ public void testForExpressionDoublePredicate() {
runForPredicateTest(5, false);
}
@Test
- public void testForExpressionDoubleSeqPredicate()
- {
+ public void testForExpressionDoubleSeqPredicate() {
runForPredicateTest(6, false);
}
- /**
- *
- * @param testNum
- * @param intScalar
- */
- private void runForPredicateTest( int testNum, boolean intScalar )
+ @Test
+ public void testParFor1IntNegativeIncrement() {
+ runForPredicateTest(8, true, true);
+ }
+
+ @Test
+ public void testParFor1DoubleNegativeIncrement() {
+ runForPredicateTest(8, false, true);
+ }
+
+ @Test
+ public void testParFor2IntNegativeIncrement() {
+ runForPredicateTest(9, true, true);
+ }
+
+ private void runForPredicateTest( int testNum, boolean intScalar ) {
+ runForPredicateTest(testNum, intScalar, false);
+ }
+
+ private void runForPredicateTest( int testNum, boolean intScalar,
boolean negative )
{
String TEST_NAME = null;
- switch( testNum )
- {
+ switch( testNum ) {
case 1: TEST_NAME = TEST_NAME1; break;
case 2: TEST_NAME = TEST_NAME2; break;
case 3: TEST_NAME = TEST_NAME3; break;
@@ -157,6 +158,8 @@ public class ForLoopPredicateTest extends AutomatedTestBase
case 5: TEST_NAME = TEST_NAME5; break;
case 6: TEST_NAME = TEST_NAME6; break;
case 7: TEST_NAME = TEST_NAME7; break;
+ case 8: TEST_NAME = TEST_NAME8; break;
+ case 9: TEST_NAME = TEST_NAME9; break;
}
getAndLoadTestConfiguration(TEST_NAME);
@@ -164,14 +167,12 @@ public class ForLoopPredicateTest extends
AutomatedTestBase
Object valFrom = null;
Object valTo = null;
Object valIncrement = null;
- if( intScalar )
- {
+ if( intScalar ) {
valFrom = Integer.valueOf((int)Math.round(from));
valTo = Integer.valueOf((int)Math.round(to));
valIncrement = Integer.valueOf(increment);
}
- else
- {
+ else {
valFrom = new Double(from);
valTo = new Double(to);
valIncrement = new Double(increment);
@@ -196,5 +197,4 @@ public class ForLoopPredicateTest extends AutomatedTestBase
Assert.assertEquals(
Double.valueOf(Math.ceil((Math.round(to)-Math.round(from)+1)/increment)),
dmlfile.get(new CellIndex(1,1)));
}
-
-}
\ No newline at end of file
+}
diff --git a/src/test/scripts/component/parfor/parfor55a.dml
b/src/test/scripts/component/parfor/parfor55a.dml
new file mode 100644
index 0000000..21a8c48
--- /dev/null
+++ b/src/test/scripts/component/parfor/parfor55a.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.
+#
+#-------------------------------------------------------------
+
+
+A = matrix(0, rows=10,cols=1);
+B = Rand(rows=10,cols=1);
+
+parfor( i in 10:1 )
+ A[i,1] = B[i,1];
+
+#print(A);
diff --git a/src/test/scripts/component/parfor/parfor55b.dml
b/src/test/scripts/component/parfor/parfor55b.dml
new file mode 100644
index 0000000..fbc8fff4
--- /dev/null
+++ b/src/test/scripts/component/parfor/parfor55b.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.
+#
+#-------------------------------------------------------------
+
+
+A = matrix(0,rows=10,cols=1);
+B = Rand(rows=10,cols=1);
+
+parfor( i in 10:2 )
+ A[i,1] = B[i,1] + A[i-1,1];
+
+#print(A);
diff --git a/src/test/scripts/functions/parfor/parfor_pred1_neg.dml
b/src/test/scripts/functions/parfor/parfor_pred1_neg.dml
new file mode 100644
index 0000000..bb1d8db
--- /dev/null
+++ b/src/test/scripts/functions/parfor/parfor_pred1_neg.dml
@@ -0,0 +1,25 @@
+#-------------------------------------------------------------
+#
+# 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.
+#
+#-------------------------------------------------------------
+
+R = matrix(0, rows=1, cols=1);
+parfor( i in $2:$1 )
+ R += matrix(1,1,1);
+write(R, $4);
diff --git a/src/test/scripts/functions/parfor/parfor_pred2_neg.dml
b/src/test/scripts/functions/parfor/parfor_pred2_neg.dml
new file mode 100644
index 0000000..fb6c022
--- /dev/null
+++ b/src/test/scripts/functions/parfor/parfor_pred2_neg.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.
+#
+#-------------------------------------------------------------
+
+R = matrix(0, rows=1, cols=1);
+parfor( i in 2:1 )
+ R += matrix(1,1,1);
+off = ceil(round($2)-round($1)+1)-2;
+R += matrix(off,1,1);
+write(R, $4);
