You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@nemo.apache.org by wo...@apache.org on 2019/01/14 05:35:06 UTC
[incubator-nemo] branch master updated: [NEMO-11] Generalize
Equality of Int Predicates for Loops (#103)
This is an automated email from the ASF dual-hosted git repository.
wonook pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-nemo.git
The following commit(s) were added to refs/heads/master by this push:
new d66ec54 [NEMO-11] Generalize Equality of Int Predicates for Loops (#103)
d66ec54 is described below
commit d66ec54d686d8291eae0362367fad356987d35cc
Author: Arun Lakshman R <26...@users.noreply.github.com>
AuthorDate: Mon Jan 14 11:05:01 2019 +0530
[NEMO-11] Generalize Equality of Int Predicates for Loops (#103)
JIRA: [NEMO-11: Generalize Equality of Int Predicates for Loops](https://issues.apache.org/jira/projects/NEMO/issues/NEMO-11)
**Major changes:**
- None
**Minor changes to note:**
- `LoopFusionPass.checkEqualityOfIntPredicates` the recursive logic has been changed to iterative logic
**Tests for the changes:**
- Test cases have been added to the file `Util` class
**Other comments:**
- As this seems to be a utility method, this has been moved to a util class in the same module
- The access modifier of the method has been changed from `private` to `public` for testing
Closes #103
---
.../src/main/java/org/apache/nemo/common/Util.java | 54 ++++++++++++++++++++++
.../apache/nemo/common/ir/vertex/LoopVertex.java | 10 ++++
.../java/org/apache/nemo/common/util/UtilTest.java | 41 ++++++++++++++++
.../compiletime/reshaping/LoopOptimizations.java | 23 +--------
4 files changed, 106 insertions(+), 22 deletions(-)
diff --git a/common/src/main/java/org/apache/nemo/common/Util.java b/common/src/main/java/org/apache/nemo/common/Util.java
new file mode 100644
index 0000000..288c5c2
--- /dev/null
+++ b/common/src/main/java/org/apache/nemo/common/Util.java
@@ -0,0 +1,54 @@
+/*
+ * 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.nemo.common.util;
+
+import java.util.function.IntPredicate;
+
+/**
+ * Class to hold the utility methods.
+ */
+public final class Util {
+
+ /**
+ * Private constructor for utility class.
+ */
+ private Util() {
+ }
+
+ /**
+ * Check the equality of two intPredicates.
+ * Check if the both the predicates either passes together or fails together for each
+ * integer in the range [0,noOfTimes]
+ *
+ * @param firstPredicate the first IntPredicate.
+ * @param secondPredicate the second IntPredicate.
+ * @param noOfTimes Number to check the IntPredicates from.
+ * @return whether or not we can say that they are equal.
+ */
+ public static boolean checkEqualityOfIntPredicates(final IntPredicate firstPredicate,
+ final IntPredicate secondPredicate, final int noOfTimes) {
+ for (int value = 0; value <= noOfTimes; value++) {
+ if (firstPredicate.test(value) != secondPredicate.test(value)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+}
diff --git a/common/src/main/java/org/apache/nemo/common/ir/vertex/LoopVertex.java b/common/src/main/java/org/apache/nemo/common/ir/vertex/LoopVertex.java
index 53139a9..dd12406 100644
--- a/common/src/main/java/org/apache/nemo/common/ir/vertex/LoopVertex.java
+++ b/common/src/main/java/org/apache/nemo/common/ir/vertex/LoopVertex.java
@@ -27,6 +27,7 @@ import org.apache.nemo.common.ir.edge.IREdge;
import org.apache.nemo.common.ir.edge.executionproperty.CommunicationPatternProperty;
import org.apache.nemo.common.ir.edge.executionproperty.DuplicateEdgeGroupProperty;
import org.apache.nemo.common.ir.edge.executionproperty.DuplicateEdgeGroupPropertyValue;
+import org.apache.nemo.common.util.Util;
import java.io.Serializable;
import java.util.*;
@@ -309,6 +310,15 @@ public final class LoopVertex extends IRVertex {
this.maxNumberOfIterations--;
}
+ public boolean terminationConditionEquals(final LoopVertex that) {
+ if (this.maxNumberOfIterations.equals(that.getMaxNumberOfIterations()) && Util
+ .checkEqualityOfIntPredicates(this.terminationCondition, that.getTerminationCondition(),
+ this.maxNumberOfIterations)) {
+ return true;
+ }
+ return false;
+ }
+
/**
* Set the intPredicate termination condition for the LoopVertex.
* @param terminationCondition the termination condition to set.
diff --git a/common/src/test/java/org/apache/nemo/common/util/UtilTest.java b/common/src/test/java/org/apache/nemo/common/util/UtilTest.java
new file mode 100644
index 0000000..4e6869f
--- /dev/null
+++ b/common/src/test/java/org/apache/nemo/common/util/UtilTest.java
@@ -0,0 +1,41 @@
+/*
+ * 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.nemo.common.util;
+
+import static org.junit.Assert.assertEquals;
+
+import java.util.function.IntPredicate;
+
+import org.junit.Test;
+
+public class UtilTest {
+
+ @Test
+ public void testCheckEqualityOfIntPredicates() {
+
+ IntPredicate firstPredicate = number -> number < 5;
+ IntPredicate secondPredicate = number -> number < 10;
+ assertEquals(true,
+ Util.checkEqualityOfIntPredicates(firstPredicate, secondPredicate, 4));
+ assertEquals(false,
+ Util.checkEqualityOfIntPredicates(firstPredicate, secondPredicate, 5));
+ assertEquals(false,
+ Util.checkEqualityOfIntPredicates(firstPredicate, secondPredicate, 7));
+ }
+}
diff --git a/compiler/optimizer/src/main/java/org/apache/nemo/compiler/optimizer/pass/compiletime/reshaping/LoopOptimizations.java b/compiler/optimizer/src/main/java/org/apache/nemo/compiler/optimizer/pass/compiletime/reshaping/LoopOptimizations.java
index fd93487..f3d09ad 100644
--- a/compiler/optimizer/src/main/java/org/apache/nemo/compiler/optimizer/pass/compiletime/reshaping/LoopOptimizations.java
+++ b/compiler/optimizer/src/main/java/org/apache/nemo/compiler/optimizer/pass/compiletime/reshaping/LoopOptimizations.java
@@ -139,9 +139,7 @@ public final class LoopOptimizations {
loopsToBeFused.add(loopVertex);
independentLoops.forEach(independentLoop -> {
// add them to the list if those independent loops have equal termination conditions.
- if (independentLoop.getMaxNumberOfIterations().equals(numberOfIterations)
- && checkEqualityOfIntPredicates(independentLoop.getTerminationCondition(), terminationCondition,
- numberOfIterations)) {
+ if (loopVertex.terminationConditionEquals(independentLoop)) {
loopsToBeFused.add(independentLoop);
}
});
@@ -227,25 +225,6 @@ public final class LoopOptimizations {
});
return mergedLoopVertex;
}
-
- /**
- * Check the equality of two intPredicates.
- * @param predicate1 the first IntPredicate.
- * @param predicate2 the second IntPredicate.
- * @param numberToTestUntil Number to check the IntPredicates from.
- * @return whether or not we can say that they are equal.
- */
- private Boolean checkEqualityOfIntPredicates(final IntPredicate predicate1, final IntPredicate predicate2,
- final Integer numberToTestUntil) {
- // TODO #11: Generalize Equality of Int Predicates for Loops.
- if (numberToTestUntil.equals(0)) {
- return predicate1.test(numberToTestUntil) == predicate2.test(numberToTestUntil);
- } else if (predicate1.test(numberToTestUntil) != predicate2.test(numberToTestUntil)) {
- return false;
- } else {
- return checkEqualityOfIntPredicates(predicate1, predicate2, numberToTestUntil - 1);
- }
- }
}
/**