From fd6b6ca9fb5907d4f897333b1247b1d4f3b19d2f Mon Sep 17 00:00:00 2001 From: jzhou Date: Thu, 3 Jan 2008 19:35:17 +0000 Subject: [PATCH] Make the Scheduling codes can handle back edges in combined flag transition diagram. Improve the output diagram also to make it more readable. --- Robust/src/Analysis/Scheduling/ClassNode.java | 45 +++---- .../Analysis/Scheduling/ScheduleAnalysis.java | 117 ++++++++++++------ .../src/Analysis/Scheduling/ScheduleEdge.java | 3 + .../src/Analysis/Scheduling/ScheduleNode.java | 24 ++-- Robust/src/Makefile | 2 +- 5 files changed, 123 insertions(+), 68 deletions(-) diff --git a/Robust/src/Analysis/Scheduling/ClassNode.java b/Robust/src/Analysis/Scheduling/ClassNode.java index 9667fa25..027d8dd6 100644 --- a/Robust/src/Analysis/Scheduling/ClassNode.java +++ b/Robust/src/Analysis/Scheduling/ClassNode.java @@ -23,10 +23,10 @@ public class ClassNode extends GraphNode implements Cloneable{ * @param fStates */ public ClassNode(ClassDescriptor cd, Vector fStates) { - this.cd=cd; - this.flagStates = fStates; - this.sn = null; - this.uid=ClassNode.nodeID++; + this.cd=cd; + this.flagStates = fStates; + this.sn = null; + this.uid=ClassNode.nodeID++; } public int getuid() { @@ -68,9 +68,9 @@ public class ClassNode extends GraphNode implements Cloneable{ return flagStates.size(); } - /** Accessor method - * @return returns the classdescriptor of the flagstate. - */ + /** Accessor method + * @return returns the classdescriptor of the flagstate. + */ public ClassDescriptor getClassDescriptor(){ return cd; @@ -81,10 +81,10 @@ public class ClassNode extends GraphNode implements Cloneable{ public boolean equals(Object o) { if (o instanceof ClassNode) { - ClassNode fs=(ClassNode)o; + ClassNode fs=(ClassNode)o; if ((fs.getClassDescriptor()!= cd) || - (fs.getScheduleNode() != sn) || - (fs.isSorted() != sorted)) { + (fs.getScheduleNode() != sn) || + (fs.isSorted() != sorted)) { return false; } return (fs.getFlagStates().equals(flagStates)); @@ -97,25 +97,28 @@ public class ClassNode extends GraphNode implements Cloneable{ } public String getLabel() { - //return "cluster_"+uid; - return "N"+uid; - } + return "N_"+uid; + } + + public String getClusterLabel() { + return "cluster_"+uid; + } public String getTextLabel() { - String label=null; - label = "Class " + this.cd.getSymbol(); - - if (label==null) - return " "; - return label; + String label=null; + label = "Class " + this.cd.getSymbol(); + + if (label==null) + return " "; + return label; } public Object clone() { ClassNode o = null; try { - o = (ClassNode)super.clone(); + o = (ClassNode)super.clone(); } catch(CloneNotSupportedException e){ - e.printStackTrace(); + e.printStackTrace(); } o.uid = ClassNode.nodeID++; return o; diff --git a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java index 222d3244..e3423ebe 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java +++ b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java @@ -74,17 +74,18 @@ public class ScheduleAnalysis { } // Create 'new' edges between the ScheduleNodes. + Vector toBreakDown = new Vector(); for(i = 0; i < classNodes.size(); i++) { ClassNode cNode = classNodes.elementAt(i); ClassDescriptor cd = cNode.getClassDescriptor(); Vector rootnodes = taskanalysis.getRootNodes(cd); if(rootnodes != null) { - for(Iterator it_rootnodes=rootnodes.iterator();it_rootnodes.hasNext();){ - FlagState root=(FlagState)it_rootnodes.next(); + for(int h = 0; h < rootnodes.size(); h++){ + FlagState root=(FlagState)rootnodes.elementAt(h); Vector allocatingTasks = root.getAllocatingTasks(); if(allocatingTasks != null) { - for(Iterator it_atnodes=allocatingTasks.iterator();it_atnodes.hasNext();){ - TaskDescriptor td = (TaskDescriptor)it_atnodes.next(); + for(int k = 0; k < allocatingTasks.size(); k++) { + TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k); Vector fev = (Vector)taskanalysis.getFEdgesFromTD(td); int numEdges = fev.size(); ScheduleNode sNode = cNode.getScheduleNode(); @@ -97,17 +98,20 @@ public class ScheduleAnalysis { ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", td, cd); sEdge.setFEdge(pfe); sEdge.setSourceCNode(pcNode); - sEdge.setTargetCNode(cNode); + sEdge.setTargetCNode(cNode); sEdge.setTargetFState(root); pcNode.getScheduleNode().addEdge(sEdge); scheduleEdges.add(sEdge); if(taskToSEdges.get(td) == null) { - taskToSEdges.put(td, new Hashtable>()); + taskToSEdges.put(td, new Hashtable>()); } if(taskToSEdges.get(td).get(cd) == null) { - taskToSEdges.get(td).put(cd, new Vector()); + taskToSEdges.get(td).put(cd, new Vector()); } taskToSEdges.get(td).get(cd).add(sEdge); + if((j !=0 ) || (k != 0) || (h != 0)) { + toBreakDown.add(sEdge); + } } fev = null; } @@ -128,6 +132,11 @@ public class ScheduleAnalysis { scheduleEdges = ssev; ssev = null; sorted = true; + + // Break down the 'cycle's + for(i = 0; i < toBreakDown.size(); i++ ) { + cloneSNodeList(toBreakDown.elementAt(i), false); + } } public void scheduleAnalysis() { @@ -156,7 +165,7 @@ public class ScheduleAnalysis { // back edge if(se.getNewRate() > 1){ for(int j = 1; j< se.getNewRate(); j++ ) { - cloneSNodeList(se); + cloneSNodeList(se, true); } se.setNewRate(1); } @@ -164,7 +173,7 @@ public class ScheduleAnalysis { if(se.getNewRate() > 1){ // clone the whole ScheduleNode lists starting with se's target for(int j = 1; j < se.getNewRate(); j++ ) { - cloneSNodeList(se); + cloneSNodeList(se, true); } se.setNewRate(1); } else if (se.getNewRate() == 1) { @@ -178,24 +187,32 @@ public class ScheduleAnalysis { } } - private void cloneSNodeList(ScheduleEdge sEdge) { + private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) { Hashtable cn2cn = new Hashtable(); ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn); scheduleNodes.add(csNode); // Clone all the external in ScheduleEdges - int i; - Vector inedges = sEdge.getTarget().getInedgeVector(); - for(i = 0; i < inedges.size(); i++) { - ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i); - ScheduleEdge se = new ScheduleEdge(csNode, "new", tse.getTask(), tse.getClassDescriptor()); - se.setProbability(tse.getProbability()); - se.setNewRate(1); - se.setSourceCNode(tse.getSourceCNode()); - se.setTargetCNode(cn2cn.get(tse.getTargetCNode())); - tse.getSource().addEdge(se); - scheduleEdges.add(se); - } + int i; + if(copyIE) { + Vector inedges = sEdge.getTarget().getInedgeVector(); + for(i = 0; i < inedges.size(); i++) { + ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i); + ScheduleEdge se = new ScheduleEdge(csNode, "new", tse.getTask(), tse.getClassDescriptor()); + se.setProbability(tse.getProbability()); + se.setNewRate(1); + se.setFEdge(tse.getFEdge()); + se.setSourceCNode(tse.getSourceCNode()); + se.setTargetCNode(cn2cn.get(tse.getTargetCNode())); + tse.getSource().addEdge(se); + scheduleEdges.add(se); + } + } else { + sEdge.getTarget().removeInedge(sEdge); + sEdge.setTarget(csNode); + csNode.getInedgeVector().add(sEdge); + sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode())); + } Queue toClone = new LinkedList(); Queue clone = new LinkedList(); @@ -251,14 +268,10 @@ public class ScheduleAnalysis { File file=new File(path); FileOutputStream dotstream=new FileOutputStream(file,false); PrintWriter output = new java.io.PrintWriter(dotstream, true); - //ScheduleNode.DOTVisitor.visit(dotstream, scheduleNodes); output.println("digraph G {"); - //output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];"); - //output.println("\tedge [fontsize=6];"); output.println("\tcompound=true;\n"); traverseSNodes(output); - output.println("}\n"); - + output.println("}\n"); } catch (Exception e) { e.printStackTrace(); System.exit(-1); @@ -272,23 +285,54 @@ public class ScheduleAnalysis { ScheduleNode gn = (ScheduleNode) it.next(); Iterator edges = gn.edges(); output.println("\tsubgraph " + gn.getLabel() + "{"); - //output.println("\t\tstyle=dashed;"); - //output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";"); + output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";"); Iterator it_cnodes = gn.getClassNodesIterator(); - traverseCNodes(output, it_cnodes); + if(gn.isclone()) { + while (it_cnodes.hasNext()) { + ClassNode cn = (ClassNode) it_cnodes.next(); + output.println("\t\t" + cn.getLabel() + " [style=dashed, label=\"" + cn.getTextLabel() + "\", shape=box];"); + } + } else { + traverseCNodes(output, it_cnodes); + } //Draw the internal 'new' edges Iterator it_edges =gn.getScheduleEdgesIterator(); while(it_edges.hasNext()) { ScheduleEdge se = (ScheduleEdge)it_edges.next(); - //output.println("\t" + se.getSourceFState().getLabel() + " -> " + se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail=" + se.getSourceCNode().getLabel() + "];"); - output.println("\t" + se.getSourceCNode().getLabel() + " -> " + se.getTargetCNode().getLabel() + " [label=\"" + se.getLabel() + "\", color=red];"); + output.print("\t"); + if(se.getSourceFState() == null) { + output.print(se.getSourceCNode().getLabel()); + } else { + output.print(se.getSourceFState().getLabel()); + } + output.print(" -> "); + if(se.getTargetFState() == null) { + output.println(se.getTargetCNode().getLabel() + " [label=\"" + se.getLabel() + "\", color=red];"); + } else { + output.print(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail="); + if(se.getSourceFState() == null) { + output.println(se.getSourceCNode().getLabel() + "];"); + } else { + output.println(se.getSourceCNode().getClusterLabel() + "];"); + } + } } output.println("\t}\n"); //Draw 'new' edges of this ScheduleNode while(edges.hasNext()) { ScheduleEdge se = (ScheduleEdge)edges.next(); - //output.println("\t" + se.getSourceFState().getLabel() + " -> " + se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed, ltail=" + gn.getLabel() + "];"); - output.println("\t" + se.getSourceCNode().getLabel() + " -> " + se.getTargetCNode().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed];"); + output.print("\t"); + if(((ScheduleNode)se.getSource()).isclone()) { + output.print(se.getSourceCNode().getLabel()); + } else { + output.print(se.getSourceFState().getLabel()); + } + output.print(" -> "); + if(((ScheduleNode)se.getTarget()).isclone()) { + output.println(se.getTargetCNode().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed];"); + } else { + output.println(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed, ltail=" + gn.getLabel() + "];"); + } } } } @@ -297,12 +341,11 @@ public class ScheduleAnalysis { //Draw clusters representing ClassNodes while (it.hasNext()) { ClassNode gn = (ClassNode) it.next(); - /*output.println("\tsubgraph " + gn.getLabel() + "{"); + output.println("\tsubgraph " + gn.getClusterLabel() + "{"); output.println("\t\tstyle=dashed;"); output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";"); traverseFlagStates(output, gn.getFlagStates()); - output.println("\t}\n");*/ - output.println("\t\t" + gn.getLabel() + " [style=dashed, label=\"" + gn.getTextLabel() + "\", shape=box];"); + output.println("\t}\n"); } } diff --git a/Robust/src/Analysis/Scheduling/ScheduleEdge.java b/Robust/src/Analysis/Scheduling/ScheduleEdge.java index d90fbbb7..9d0a21e0 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleEdge.java +++ b/Robust/src/Analysis/Scheduling/ScheduleEdge.java @@ -65,6 +65,9 @@ public class ScheduleEdge extends Edge { } public FlagState getSourceFState() { + if(this.fedge == null) { + return null; + } return (FlagState)this.fedge.getTarget(); } diff --git a/Robust/src/Analysis/Scheduling/ScheduleNode.java b/Robust/src/Analysis/Scheduling/ScheduleNode.java index e0d6a89e..5ea3b61d 100644 --- a/Robust/src/Analysis/Scheduling/ScheduleNode.java +++ b/Robust/src/Analysis/Scheduling/ScheduleNode.java @@ -29,12 +29,12 @@ public class ScheduleNode extends GraphNode implements Cloneable{ */ public ScheduleNode() { this.uid=ScheduleNode.nodeID++; - this.coreNum = 0; + this.coreNum = -1; } public ScheduleNode(ClassNode cn) { this.uid=ScheduleNode.nodeID++; - this.coreNum = 0; + this.coreNum = -1; this.classNodes = new Vector(); this.scheduleEdges = new Vector(); this.classNodes.add(cn); @@ -169,13 +169,13 @@ public class ScheduleNode extends GraphNode implements Cloneable{ } else if(this.targetSNodes != null) { return false; } - if(fs.classNodes != null) { - if(!fs.classNodes.equals(classNodes)) { - return false; - } - } else if(classNodes != null) { + if(fs.classNodes != null) { + if(!fs.classNodes.equals(classNodes)) { return false; - } + } + } else if(classNodes != null) { + return false; + } return (fs.scheduleEdges.equals(scheduleEdges)); } return false; @@ -191,7 +191,9 @@ public class ScheduleNode extends GraphNode implements Cloneable{ public String getTextLabel() { String label=null; - label = "[Cluster of classes]" + uid; + if(this.coreNum != -1) { + label = "Core " + this.coreNum; + } if (label==null) return " "; @@ -239,6 +241,10 @@ public class ScheduleNode extends GraphNode implements Cloneable{ Vector targetCNodes = (Vector)((ScheduleNode)se.getTarget()).getClassNodes(); Vector targetSEdges = (Vector)((ScheduleNode)se.getTarget()).getScheduleEdges(); + for(int i = 0; i < targetCNodes.size(); i++) { + targetCNodes.elementAt(i).setScheduleNode(this); + } + if(classNodes == null) { classNodes = targetCNodes; scheduleEdges = targetSEdges; diff --git a/Robust/src/Makefile b/Robust/src/Makefile index 748ee17f..31abafe9 100644 --- a/Robust/src/Makefile +++ b/Robust/src/Makefile @@ -114,7 +114,7 @@ javadoc: javadoc -classpath ../cup:.:$(CLASSPATH) -sourcepath . -private -d javadoc Lex Util IR IR.Tree IR.Flat Analysis Analysis.CallGraph Analysis.Flag Analysis.TaskStateAnalysis Analysis.Locality Analysis.Prefetch Main Analysis.OwnershipAnalysis clean: - rm -f IR/*.class IR/Tree/*.class Main/*.class Lex/*.class Parse/*.class Parse/Sym.java Parse/Parser.java IR/Flat/*.class classdefs.h methodheaders.h methods.c structdefs.h virtualtable.h task.h taskdefs.c taskdefs.h Analysis/*.class Analysis/Flag/*.class Analysis/CallGraph/*.class Analysis/TaskStateAnalysis/*.class Interface/*.class Util/*.class Analysis/Locality/*.class Analysis/Prefetch/*.class Analysis/FlatIRGraph/*.class Analysis/OwnershipAnalysis/*.class + rm -f IR/*.class IR/Tree/*.class Main/*.class Lex/*.class Parse/*.class Parse/Sym.java Parse/Parser.java IR/Flat/*.class classdefs.h methodheaders.h methods.c structdefs.h virtualtable.h task.h taskdefs.c taskdefs.h Analysis/*.class Analysis/Flag/*.class Analysis/CallGraph/*.class Analysis/TaskStateAnalysis/*.class Interface/*.class Util/*.class Analysis/Locality/*.class Analysis/Prefetch/*.class Analysis/FlatIRGraph/*.class Analysis/OwnershipAnalysis/*.class Analysis/Scheduling/*.class cleandoc: rm -rf javadoc -- 2.34.1