This is an automated email from the ASF dual-hosted git repository.
arnabp20 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 0febfb1 [SYSTEMDS-2581] Improve serialization of dedup DAGs
0febfb1 is described below
commit 0febfb1f5060b2043e4ff1d48b70c94bd7e07ec4
Author: arnabp <[email protected]>
AuthorDate: Wed Jan 13 14:38:49 2021 +0100
[SYSTEMDS-2581] Improve serialization of dedup DAGs
This patch cuts the dedup patch DAGs at placeholders just
after each loop iteration, instead of at the time of
serialization. This will help comparing compressed DAGs.
---
.../sysds/runtime/lineage/LineageDedupUtils.java | 46 +++++++++++++++++++---
.../apache/sysds/runtime/lineage/LineageItem.java | 7 +++-
.../sysds/runtime/lineage/LineageItemUtils.java | 6 ++-
.../sysds/runtime/lineage/LineageParser.java | 9 ++++-
.../runtime/lineage/LineageRecomputeUtils.java | 4 ++
5 files changed, 63 insertions(+), 9 deletions(-)
diff --git
a/src/main/java/org/apache/sysds/runtime/lineage/LineageDedupUtils.java
b/src/main/java/org/apache/sysds/runtime/lineage/LineageDedupUtils.java
index 230e5e1..496de6e 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageDedupUtils.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageDedupUtils.java
@@ -21,6 +21,7 @@ package org.apache.sysds.runtime.lineage;
import java.util.ArrayList;
import java.util.Map;
+import java.util.Stack;
import org.apache.sysds.runtime.controlprogram.BasicProgramBlock;
import org.apache.sysds.runtime.controlprogram.ForProgramBlock;
@@ -106,9 +107,6 @@ public class LineageDedupUtils {
String ph = LineageItemUtils.LPLACEHOLDER;
for (int i=0; i<liinputs.length; i++) {
// Wrap the inputs with order-preserving placeholders.
- // An alternative way would be to replace the
non-literal leaves with
- // placeholders after each iteration, but that requires
a full DAG
- // traversal after each iteration.
LineageItem phInput = new
LineageItem(ph+String.valueOf(i), new LineageItem[] {liinputs[i]});
_tmpLineage.set(inputnames.get(i), phInput);
}
@@ -125,11 +123,16 @@ public class LineageDedupUtils {
public static void setDedupMap(LineageDedupBlock ldb, long takenPath) {
// if this iteration took a new path, store the corresponding
map
- if (ldb.getMap(takenPath) == null)
- ldb.setMap(takenPath, _tmpLineage.getLineageMap());
+ if (ldb.getMap(takenPath) == null) {
+ LineageMap patchMap = _tmpLineage.getLineageMap();
+ // Cut the DAGs at placeholders
+ cutAtPlaceholder(patchMap);
+ ldb.setMap(takenPath, patchMap);
+ }
}
private static void initLocalLineage(ExecutionContext ec) {
+ _mainLineage = ec.getLineage();
_tmpLineage = _tmpLineage == null ? new Lineage() : _tmpLineage;
_tmpLineage.clearLineageMap();
_tmpLineage.clearDedupBlock();
@@ -165,6 +168,39 @@ public class LineageDedupUtils {
return sb.toString();
}
+ public static void cutAtPlaceholder(LineageMap lmap) {
+ // Gather all the DAG roots and cut each at placeholder
+ for (Map.Entry<String, LineageItem> litem :
lmap.getTraces().entrySet()) {
+ LineageItem root = litem.getValue();
+ root.resetVisitStatusNR();
+ cutAtPlaceholder(root);
+ }
+ }
+
+ public static void cutAtPlaceholder(LineageItem root) {
+ Stack<LineageItem> q = new Stack<>();
+ q.push(root);
+ while (!q.empty()) {
+ LineageItem tmp = q.pop();
+ if (tmp.isVisited())
+ continue;
+
+ if
(tmp.getOpcode().startsWith(LineageItemUtils.LPLACEHOLDER)) {
+ // set inputs to null
+ tmp.resetInputs();
+ tmp.setVisited();
+ continue;
+ }
+
+ if (tmp.getInputs() != null)
+ for (int i=0; i<tmp.getInputs().length; i++) {
+ LineageItem li = tmp.getInputs()[i];
+ q.push(li);
+ }
+ tmp.setVisited();
+ }
+ }
+
//------------------------------------------------------------------------------
/* The below static functions help to compute the number of distinct
paths
* in any program block, and are used for diagnostic purposes. These
will
diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageItem.java
b/src/main/java/org/apache/sysds/runtime/lineage/LineageItem.java
index 2fa3a22..3903bf0 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageItem.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageItem.java
@@ -31,7 +31,7 @@ public class LineageItem {
private final long _id;
private final String _opcode;
private final String _data;
- private final LineageItem[] _inputs;
+ private LineageItem[] _inputs;
private int _hash = 0;
private long _distLeaf2Node;
// init visited to true to ensure visited items are
@@ -93,6 +93,11 @@ public class LineageItem {
return _inputs;
}
+ public void resetInputs() {
+ _inputs = null;
+ _hash = 0;
+ }
+
public void setInput(int i, LineageItem item) {
_inputs[i] = item;
_hash = 0; //reset hash
diff --git
a/src/main/java/org/apache/sysds/runtime/lineage/LineageItemUtils.java
b/src/main/java/org/apache/sysds/runtime/lineage/LineageItemUtils.java
index 268fd12..977b12c 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageItemUtils.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageItemUtils.java
@@ -114,7 +114,11 @@ public class LineageItemUtils {
sb.append("(").append(getString(li)).append(") ");
if (li.isLeaf()) {
- sb.append(li.getData()).append(" ");
+ if (li.getOpcode().startsWith(LPLACEHOLDER))
+ //This is a special node. Serialize opcode
instead of data
+ sb.append(li.getOpcode()).append(" ");
+ else
+ sb.append(li.getData()).append(" ");
} else {
if (li.getType() == LineageItemType.Dedup)
sb.append(li.getOpcode()).append(li.getData()).append(" ");
diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageParser.java
b/src/main/java/org/apache/sysds/runtime/lineage/LineageParser.java
index dac78c5..46dff8e 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageParser.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageParser.java
@@ -63,6 +63,11 @@ public class LineageParser
switch (type) {
case Creation:
+ if
(representation.startsWith(LineageItemUtils.LPLACEHOLDER)) {
+ // Handle the placeholder nodes
+ li = new LineageItem(id,
representation, "Create"+representation);
+ break;
+ }
Instruction inst =
InstructionParser.parseSingleInstruction(representation);
if (!(inst instanceof LineageTraceable))
throw new
ParseException("Invalid Instruction (" + inst.getOpcode() + ") traced");
@@ -96,11 +101,11 @@ public class LineageParser
throw new ParseException("Invalid length ot lineage
item "+tokens.length+".");
String opcode = tokens[0];
- if (opcode.startsWith(LineageItemUtils.LPLACEHOLDER)) {
+ /*if (opcode.startsWith(LineageItemUtils.LPLACEHOLDER)) {
// Convert this to a leaf node (creation type)
String data = opcode;
return new LineageItem(id, data, "Create"+opcode);
- }
+ }*/
ArrayList<LineageItem> inputs = new ArrayList<>();
for( int i=1; i<tokens.length; i++ ) {
diff --git
a/src/main/java/org/apache/sysds/runtime/lineage/LineageRecomputeUtils.java
b/src/main/java/org/apache/sysds/runtime/lineage/LineageRecomputeUtils.java
index 0df1651..66e1932 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageRecomputeUtils.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageRecomputeUtils.java
@@ -82,6 +82,10 @@ public class LineageRecomputeUtils {
public static Map<String, DedupLoopItem> loopPatchMap = new HashMap<>();
public static Data parseNComputeLineageTrace(String mainTrace, String
dedupPatches) {
+ if (DEBUG) {
+ System.out.println(mainTrace);
+ System.out.println(dedupPatches);
+ }
LineageItem root = LineageParser.parseLineageTrace(mainTrace);
if (dedupPatches != null)
LineageParser.parseLineageTraceDedup(dedupPatches);
