From 888698c50499fab303d1ac0c41663523aff5a076 Mon Sep 17 00:00:00 2001 From: jzhou Date: Thu, 3 Jan 2008 00:53:49 +0000 Subject: [PATCH] Add directory and codes for task scheduling --- Robust/src/Analysis/Scheduling/ClassNode.java | 123 ++++++ .../Analysis/Scheduling/ScheduleAnalysis.java | 390 ++++++++++++++++++ .../src/Analysis/Scheduling/ScheduleEdge.java | 133 ++++++ .../src/Analysis/Scheduling/ScheduleNode.java | 267 ++++++++++++ .../TaskStateAnalysis/TaskAnalysis.java | 12 + Robust/src/IR/State.java | 1 + Robust/src/Main/Main.java | 31 ++ Robust/src/Makefile | 6 +- Robust/src/Util/Edge.java | 31 ++ Robust/src/Util/GraphNode.java | 54 ++- Robust/src/buildscript | 4 + 11 files changed, 1041 insertions(+), 11 deletions(-) create mode 100644 Robust/src/Analysis/Scheduling/ClassNode.java create mode 100644 Robust/src/Analysis/Scheduling/ScheduleAnalysis.java create mode 100644 Robust/src/Analysis/Scheduling/ScheduleEdge.java create mode 100644 Robust/src/Analysis/Scheduling/ScheduleNode.java diff --git a/Robust/src/Analysis/Scheduling/ClassNode.java b/Robust/src/Analysis/Scheduling/ClassNode.java new file mode 100644 index 00000000..9667fa25 --- /dev/null +++ b/Robust/src/Analysis/Scheduling/ClassNode.java @@ -0,0 +1,123 @@ +package Analysis.Scheduling; + +import Analysis.TaskStateAnalysis.*; +import IR.*; +import java.util.*; + +import Util.GraphNode; + +/** This class holds a flag diagram for one class. + */ +public class ClassNode extends GraphNode implements Cloneable{ + + private int uid; + private static int nodeID=0; + + private final ClassDescriptor cd; + private ScheduleNode sn; + private Vector flagStates; + private boolean sorted = false; + + /** Class constructor + * @param cd ClassDescriptor + * @param fStates + */ + public ClassNode(ClassDescriptor cd, Vector fStates) { + this.cd=cd; + this.flagStates = fStates; + this.sn = null; + this.uid=ClassNode.nodeID++; + } + + public int getuid() { + return uid; + } + + public ScheduleNode getScheduleNode() { + return this.sn; + } + + public void setScheduleNode(ScheduleNode sn) { + this.sn = sn; + } + + public boolean isSorted() { + return sorted; + } + + public void setSorted(boolean sorted) { + this.sorted = sorted; + } + + public Vector getFlagStates() { + return flagStates; + } + + public String toString() { + return cd.toString()+getTextLabel(); + } + + /** @return Iterator over the flags in the flagstate. + */ + + public Iterator getFlags() { + return flagStates.iterator(); + } + + public int numFlags(){ + return flagStates.size(); + } + + /** Accessor method + * @return returns the classdescriptor of the flagstate. + */ + + public ClassDescriptor getClassDescriptor(){ + return cd; + } + + /** Tests for equality of two flagstate objects. + */ + + public boolean equals(Object o) { + if (o instanceof ClassNode) { + ClassNode fs=(ClassNode)o; + if ((fs.getClassDescriptor()!= cd) || + (fs.getScheduleNode() != sn) || + (fs.isSorted() != sorted)) { + return false; + } + return (fs.getFlagStates().equals(flagStates)); + } + return false; + } + + public int hashCode() { + return cd.hashCode()^flagStates.hashCode(); + } + + public String getLabel() { + //return "cluster_"+uid; + return "N"+uid; + } + + public String getTextLabel() { + 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(); + } catch(CloneNotSupportedException e){ + e.printStackTrace(); + } + o.uid = ClassNode.nodeID++; + return o; + } +} diff --git a/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java new file mode 100644 index 00000000..222d3244 --- /dev/null +++ b/Robust/src/Analysis/Scheduling/ScheduleAnalysis.java @@ -0,0 +1,390 @@ +package Analysis.Scheduling; + +import Analysis.TaskStateAnalysis.*; +import IR.*; +import java.util.*; +import java.io.*; + +import Util.Edge; +import Util.GraphNode; +import Util.Namer; + +/** This class holds flag transition diagram(s) can be put on one core. + */ +public class ScheduleAnalysis { + + TaskAnalysis taskanalysis; + State state; + Vector scheduleNodes; + Vector classNodes; + boolean sorted = false; + Vector scheduleEdges; + Hashtable>> taskToSEdges; + + int probabilityThreshold; + + public ScheduleAnalysis(State state, TaskAnalysis taskanalysis) { + this.state = state; + this.taskanalysis = taskanalysis; + this.scheduleNodes = new Vector(); + this.classNodes = new Vector(); + this.scheduleEdges = new Vector(); + this.taskToSEdges = new Hashtable>>(); + this.probabilityThreshold = 45; + } + + public void setProbabilityThreshold(int pt) { + this.probabilityThreshold = pt; + } + + public Vector getSEdges(TaskDescriptor td, ClassDescriptor cd) { + return taskToSEdges.get(td).get(cd); + } + + public Vector getSEdges4Test() { + return scheduleEdges; + } + + public void preSchedule() { + Hashtable cdToCNodes = new Hashtable(); + // Build the combined flag transition diagram + // First, for each class create a ClassNode + for(Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext(); ) { + ClassDescriptor cd = (ClassDescriptor) it_classes.next(); + Set fStates = taskanalysis.getFlagStates(cd); + + //Sort flagState nodes inside this ClassNode + Vector sFStates = FlagState.DFS.topology(fStates, null); + + Vector rootnodes = taskanalysis.getRootNodes(cd); + if(((rootnodes != null) && (rootnodes.size() > 0)) || (cd.getSymbol().equals("StartupObject"))) { + ClassNode cNode = new ClassNode(cd, sFStates); + cNode.setSorted(true); + classNodes.add(cNode); + cdToCNodes.put(cd, cNode); + } + } + + // For each ClassNode create a ScheduleNode containing it + int i = 0; + for(i = 0; i < classNodes.size(); i++) { + ScheduleNode sn = new ScheduleNode(classNodes.elementAt(i)); + classNodes.elementAt(i).setScheduleNode(sn); + scheduleNodes.add(sn); + } + + // Create 'new' edges between the ScheduleNodes. + 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(); + Vector allocatingTasks = root.getAllocatingTasks(); + if(allocatingTasks != null) { + for(Iterator it_atnodes=allocatingTasks.iterator();it_atnodes.hasNext();){ + TaskDescriptor td = (TaskDescriptor)it_atnodes.next(); + Vector fev = (Vector)taskanalysis.getFEdgesFromTD(td); + int numEdges = fev.size(); + ScheduleNode sNode = cNode.getScheduleNode(); + for(int j = 0; j < numEdges; j++) { + FEdge pfe = fev.elementAt(j); + FlagState pfs = (FlagState)pfe.getTarget(); + ClassDescriptor pcd = pfs.getClassDescriptor(); + ClassNode pcNode = cdToCNodes.get(pcd); + + ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", td, cd); + sEdge.setFEdge(pfe); + sEdge.setSourceCNode(pcNode); + sEdge.setTargetCNode(cNode); + sEdge.setTargetFState(root); + pcNode.getScheduleNode().addEdge(sEdge); + scheduleEdges.add(sEdge); + if(taskToSEdges.get(td) == null) { + taskToSEdges.put(td, new Hashtable>()); + } + if(taskToSEdges.get(td).get(cd) == null) { + taskToSEdges.get(td).put(cd, new Vector()); + } + taskToSEdges.get(td).get(cd).add(sEdge); + } + fev = null; + } + allocatingTasks = null; + } + } + rootnodes = null; + } + } + + // Do topology sort of the ClassNodes and ScheduleEdges. + Vector ssev = new Vector(); + Vector tempSNodes = ClassNode.DFS.topology(scheduleNodes, ssev); + scheduleNodes.removeAllElements(); + scheduleNodes = tempSNodes; + tempSNodes = null; + scheduleEdges.removeAllElements(); + scheduleEdges = ssev; + ssev = null; + sorted = true; + } + + public void scheduleAnalysis() { + // First iteration + int i = 0; + Vector rsev = new Vector(); + for(i = scheduleEdges.size(); i > 0; i--) { + ScheduleEdge se = scheduleEdges.elementAt(i-1); + if(!(se.getProbability() > this.probabilityThreshold)){ + // Merge the target ScheduleNode into the source ScheduleNode + ((ScheduleNode)se.getSource()).merge(se); + scheduleNodes.remove(se.getTarget()); + se.setTarget((ScheduleNode)se.getSource()); + rsev.add(se); + } + } + scheduleEdges.removeAll(rsev); + rsev = null; + + //Second iteration + //Access the ScheduleEdges in reverse topology order + for(i = scheduleEdges.size(); i > 0; i--) { + ScheduleEdge se = scheduleEdges.elementAt(i-1); + FEdge fe = se.getFEdge(); + if(fe.getSource() == fe.getTarget()) { + // back edge + if(se.getNewRate() > 1){ + for(int j = 1; j< se.getNewRate(); j++ ) { + cloneSNodeList(se); + } + se.setNewRate(1); + } + } else { + if(se.getNewRate() > 1){ + // clone the whole ScheduleNode lists starting with se's target + for(int j = 1; j < se.getNewRate(); j++ ) { + cloneSNodeList(se); + } + se.setNewRate(1); + } else if (se.getNewRate() == 1) { + //merge the target ScheduleNode to the source ScheduleNode + ((ScheduleNode)se.getSource()).merge(se); + scheduleNodes.remove(se.getTarget()); + scheduleEdges.removeElement(se); + se.setTarget((ScheduleNode)se.getSource()); + } + } + } + } + + private void cloneSNodeList(ScheduleEdge sEdge) { + 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); + } + + Queue toClone = new LinkedList(); + Queue clone = new LinkedList(); + Queue qcn2cn = new LinkedList(); + clone.add(csNode); + toClone.add((ScheduleNode)sEdge.getTarget()); + qcn2cn.add(cn2cn); + while(!toClone.isEmpty()) { + Hashtable tocn2cn = new Hashtable(); + csNode = clone.poll(); + ScheduleNode osNode = toClone.poll(); + cn2cn = qcn2cn.poll(); + // Clone all the external ScheduleEdges and the following ScheduleNodes + Vector edges = osNode.getEdgeVector(); + for(i = 0; i < edges.size(); i++) { + ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i); + ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn); + scheduleNodes.add(tSNode); + clone.add(tSNode); + toClone.add((ScheduleNode)tse.getTarget()); + qcn2cn.add(tocn2cn); + ScheduleEdge se = new ScheduleEdge(tSNode, "new", tse.getTask(), tse.getClassDescriptor()); + se.setProbability(tse.getProbability()); + se.setNewRate(tse.getNewRate()); + se.setSourceCNode(cn2cn.get(tse.getSourceCNode())); + se.setTargetCNode(tocn2cn.get(tse.getTargetCNode())); + csNode.addEdge(se); + scheduleEdges.add(se); + } + } + } + + public void schedule() { + // Assign a core to each ScheduleNode + int i = 0; + int coreNum = 1; + for(i = 0; i < scheduleNodes.size(); i++) { + ScheduleNode sn = scheduleNodes.elementAt(i); + sn.setCoreNum(coreNum++); + sn.listTasks(); + // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn + Iterator it_edges = sn.edges(); + while(it_edges.hasNext()) { + ScheduleEdge se = (ScheduleEdge)it_edges.next(); + ScheduleNode target = (ScheduleNode)se.getTarget(); + sn.addTargetSNode(se.getTargetFState().getClassDescriptor(), target); + } + } + } + + public void printScheduleGraph(String path) { + try { + 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"); + + } catch (Exception e) { + e.printStackTrace(); + System.exit(-1); + } + } + + private void traverseSNodes(PrintWriter output){ + //Draw clusters representing ScheduleNodes + Iterator it = scheduleNodes.iterator(); + while (it.hasNext()) { + 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() + "\";"); + Iterator it_cnodes = gn.getClassNodesIterator(); + 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.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];"); + } + } + } + + private void traverseCNodes(PrintWriter output, Iterator it){ + //Draw clusters representing ClassNodes + while (it.hasNext()) { + ClassNode gn = (ClassNode) it.next(); + /*output.println("\tsubgraph " + gn.getLabel() + "{"); + 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];"); + } + } + + private void traverseFlagStates(PrintWriter output, Collection nodes) { + Set cycleset=GraphNode.findcycles(nodes); + Vector namers=new Vector(); + namers.add(new Namer()); + namers.add(new Allocations()); + //namers.add(new TaskEdges()); + + Iterator it = nodes.iterator(); + while (it.hasNext()) { + GraphNode gn = (GraphNode) it.next(); + Iterator edges = gn.edges(); + String label = ""; + String dotnodeparams=""; + + for(int i=0;i " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];"); + } + } + } + } + } + + private Set nonmerge(GraphNode gn, Collection nodes) { + HashSet newset=new HashSet(); + HashSet toprocess=new HashSet(); + toprocess.add(gn); + while(!toprocess.isEmpty()) { + GraphNode gn2=(GraphNode)toprocess.iterator().next(); + toprocess.remove(gn2); + if (!gn2.merge) + newset.add(gn2); + else { + Iterator edges = gn2.edges(); + while (edges.hasNext()) { + Edge edge = (Edge) edges.next(); + GraphNode node = edge.getTarget(); + if (!newset.contains(node)&&nodes.contains(node)) + toprocess.add(node); + } + } + } + return newset; + } + +} diff --git a/Robust/src/Analysis/Scheduling/ScheduleEdge.java b/Robust/src/Analysis/Scheduling/ScheduleEdge.java new file mode 100644 index 00000000..d90fbbb7 --- /dev/null +++ b/Robust/src/Analysis/Scheduling/ScheduleEdge.java @@ -0,0 +1,133 @@ +package Analysis.Scheduling; +import IR.*; +import Analysis.TaskStateAnalysis.*; +import Util.Edge; + +/* Edge *****************/ + +public class ScheduleEdge extends Edge { + + private String label; + private final TaskDescriptor td; + private final ClassDescriptor cd; + private FEdge fedge; + private FlagState targetFState; + private ClassNode sourceCNode; + private ClassNode targetCNode; + private int newRate; + private int probability; + //private int parameterindex; + + /** Class Constructor + * + */ + public ScheduleEdge(ScheduleNode target, String label, TaskDescriptor td, ClassDescriptor cd/*, int parameterindex*/) { + super(target); + this.fedge = null; + this.targetFState = null; + this.sourceCNode = null; + this.targetCNode = null; + this.label = label; + this.td = td; + this.cd = cd; + this.newRate = 1; + this.probability = 100; + //this.parameterindex = parameterindex; + } + + public void setTarget(ScheduleNode sn) { + this.target = sn; + } + + public String getLabel() { + String completeLabel = label + ":" + Integer.toString(this.newRate) + ":(" + Integer.toString(this.probability) + ")"; + return completeLabel; + } + + public int hashCode(){ + return target.hashCode()^label.hashCode(); + } + + public TaskDescriptor getTask() { + return td; + } + + public ClassDescriptor getClassDescriptor() { + return cd; + } + + public FEdge getFEdge() { + return this.fedge; + } + + public void setFEdge(FEdge fEdge) { + this.fedge = fEdge; + } + + public FlagState getSourceFState() { + return (FlagState)this.fedge.getTarget(); + } + + public void setTargetFState(FlagState targetFState) { + this.targetFState = targetFState; + } + + public FlagState getTargetFState() { + return this.targetFState; + } + + public int getProbability() { + return this.probability; + } + + public int getNewRate() { + return this.newRate; + } + + public ClassNode getSourceCNode() { + return this.sourceCNode; + } + + public void setSourceCNode(ClassNode sourceCNode) { + this.sourceCNode = sourceCNode; + } + + public ClassNode getTargetCNode() { + return this.targetCNode; + } + + public void setTargetCNode(ClassNode targetCNode) { + this.targetCNode = targetCNode; + } + + /* public int getIndex() { + return parameterindex; + }*/ + + public boolean equals(Object o) { + if (o instanceof ScheduleEdge) { + ScheduleEdge e=(ScheduleEdge)o; + if ((e.label.equals(label))&& + (e.target.equals(target))&& + (e.td.equals(td)) && + (e.cd.equals(cd)) && + (e.fedge.equals(fedge)) && + (e.targetFState.equals(targetFState)) && + (e.sourceCNode.equals(sourceCNode)) && + (e.targetCNode.equals(targetCNode)) && + (e.newRate == newRate) && + (e.probability == probability)/*&& + e.getIndex()==parameterindex*/) + return true; + } + return false; + } + + public void setProbability(int prob) { + this.probability = prob; + } + + public void setNewRate(int nr) { + this.newRate = nr; + } +} diff --git a/Robust/src/Analysis/Scheduling/ScheduleNode.java b/Robust/src/Analysis/Scheduling/ScheduleNode.java new file mode 100644 index 00000000..e0d6a89e --- /dev/null +++ b/Robust/src/Analysis/Scheduling/ScheduleNode.java @@ -0,0 +1,267 @@ +package Analysis.Scheduling; + +import Analysis.TaskStateAnalysis.*; +import IR.*; +import java.util.*; + +import Util.GraphNode; + +/** This class holds flag transition diagram(s) can be put on one core. + */ +public class ScheduleNode extends GraphNode implements Cloneable{ + + private int uid; + private static int nodeID=0; + + private int coreNum; + private Vector tasks; + private Hashtable> targetSNodes; + private boolean sorted = false; + + private boolean clone = false; + + private Vector classNodes; + Vector scheduleEdges; + + /** Class constructor + * @param cd ClassDescriptor + * @param fStates + */ + public ScheduleNode() { + this.uid=ScheduleNode.nodeID++; + this.coreNum = 0; + } + + public ScheduleNode(ClassNode cn) { + this.uid=ScheduleNode.nodeID++; + this.coreNum = 0; + this.classNodes = new Vector(); + this.scheduleEdges = new Vector(); + this.classNodes.add(cn); + this.addEdge(cn.getEdgeVector()); + } + + public int getuid() { + return uid; + } + + public int getCoreNum() { + return this.coreNum; + } + + public void setCoreNum(int coreNum) { + this.coreNum = coreNum; + } + + public void addTargetSNode(ClassDescriptor cd, ScheduleNode sn) { + if(this.targetSNodes == null) { + this.targetSNodes = new Hashtable>(); + } + + if(!this.targetSNodes.containsKey(cd)) { + this.targetSNodes.put(cd, new Vector()); + } + this.targetSNodes.get(cd).add(sn); + } + + public void listTasks() { + if(this.tasks == null) { + this.tasks = new Vector(); + } + + int i = 0; + for(i = 0; i < classNodes.size(); i++) { + Iterator it_flags = classNodes.elementAt(i).getFlags(); + while(it_flags.hasNext()) { + FlagState fs = (FlagState)it_flags.next(); + Iterator it_edges = fs.edges(); + while(it_edges.hasNext()) { + TaskDescriptor td = ((FEdge)it_edges.next()).getTask(); + if(!this.tasks.contains(td)) { + this.tasks.add(td); + } + } + } + } + } + + public void addTask(TaskDescriptor task){ + tasks.add(task); + } + + public Vector getTasks(){ + return tasks; + } + + public boolean isSorted() { + return sorted; + } + + public void setSorted(boolean sorted) { + this.sorted = sorted; + } + + public boolean isclone() { + return clone; + } + + public String toString() { + String temp = new String(""); + for(int i = 0; i < classNodes.size(); i++) { + temp += classNodes.elementAt(i).getClassDescriptor().toString() + ", "; + } + temp += getTextLabel(); + return temp; + } + + public Vector getClassNodes() { + if(classNodes == null) { + classNodes = new Vector(); + } + return classNodes; + } + + public Iterator getClassNodesIterator() { + return classNodes.iterator(); + } + + public void resetClassNodes() { + classNodes = null; + } + + public Vector getScheduleEdges() { + if(scheduleEdges == null) { + scheduleEdges = new Vector(); + } + return scheduleEdges; + } + + public Iterator getScheduleEdgesIterator() { + return scheduleEdges.iterator(); + } + + public void resetScheduleEdges() { + scheduleEdges = null; + } + + /** Tests for equality of two flagstate objects. + */ + + public boolean equals(Object o) { + if (o instanceof ScheduleNode) { + ScheduleNode fs=(ScheduleNode)o; + if ((fs.getCoreNum() != this.coreNum) || + (fs.sorted != this.sorted) || + (fs.clone != this.clone)){ + return false; + } + if(fs.tasks != null) { + if(!fs.tasks.equals(this.tasks)) { + return false; + } + } else if (tasks != null) { + return false; + } + if (fs.targetSNodes != null) { + if(!fs.targetSNodes.equals(this.targetSNodes)) { + return false; + } + } else if(this.targetSNodes != null) { + return false; + } + if(fs.classNodes != null) { + if(!fs.classNodes.equals(classNodes)) { + return false; + } + } else if(classNodes != null) { + return false; + } + return (fs.scheduleEdges.equals(scheduleEdges)); + } + return false; + } + + public int hashCode() { + return classNodes.hashCode()^scheduleEdges.hashCode(); + } + + public String getLabel() { + return "cluster" + uid; + } + + public String getTextLabel() { + String label=null; + label = "[Cluster of classes]" + uid; + + if (label==null) + return " "; + return label; + } + + public Object clone(Hashtable cn2cn) { + ScheduleNode o = null; + try { + o = (ScheduleNode)super.clone(); + } catch(CloneNotSupportedException e){ + e.printStackTrace(); + } + o.uid = ScheduleNode.nodeID++; + // Clone all the internal ClassNodes and ScheduleEdges + Vector tcns = new Vector(); + Vector tses = new Vector(); + int i = 0; + for(i = 0; i < this.classNodes.size(); i++) { + ClassNode tcn = this.classNodes.elementAt(i); + ClassNode cn = (ClassNode)tcn.clone(); + cn.setScheduleNode(o); + tcns.add(cn); + cn2cn.put(tcn, cn); + } + for(i = 0; i < this.scheduleEdges.size(); i++) { + ScheduleEdge temp = this.scheduleEdges.elementAt(i); + ScheduleEdge se = new ScheduleEdge(o, "new", temp.getTask(), temp.getClassDescriptor()); + se.setSourceCNode(cn2cn.get(temp.getSourceCNode())); + se.setTargetCNode(cn2cn.get(temp.getTargetCNode())); + tses.add(se); + } + o.classNodes = tcns; + o.scheduleEdges = tses; + tcns = null; + tses = null; + o.inedges = new Vector(); + o.edges = new Vector(); + + o.clone = true; + return o; + } + + public void merge(ScheduleEdge se) { + Vector targetCNodes = (Vector)((ScheduleNode)se.getTarget()).getClassNodes(); + Vector targetSEdges = (Vector)((ScheduleNode)se.getTarget()).getScheduleEdges(); + + if(classNodes == null) { + classNodes = targetCNodes; + scheduleEdges = targetSEdges; + } else { + if(targetCNodes.size() != 0) { + classNodes.addAll(targetCNodes); + } + if(targetSEdges.size() != 0) { + scheduleEdges.addAll(targetSEdges); + } + } + targetCNodes = null; + targetSEdges = null; + + scheduleEdges.add(se); + se.getTarget().removeInedge(se); + this.removeEdge(se); + //this.addEdge(se.getTarget().getEdgeVector()); + Iterator it_edges = se.getTarget().edges(); + while(it_edges.hasNext()) { + ScheduleEdge tse = (ScheduleEdge)it_edges.next(); + tse.setSource(this); + this.edges.addElement(tse); + } + } +} diff --git a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java index 68bdd683..dbc732ca 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java +++ b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java @@ -15,6 +15,7 @@ public class TaskAnalysis { Queue toprocess; TagAnalysis taganalysis; Hashtable cdtorootnodes; + Hashtable tdToFEdges; TypeUtil typeutil; @@ -89,6 +90,7 @@ public class TaskAnalysis { flagstates=new Hashtable(); Hashtable sourcenodes; cdtorootnodes=new Hashtable(); + tdToFEdges=new Hashtable(); getFlagsfromClasses(); @@ -152,6 +154,10 @@ private void analyseTasks(FlagState fs) { for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) { TaskDescriptor td = (TaskDescriptor)it_tasks.next(); String taskname=td.getSymbol(); + + if(!tdToFEdges.containsKey(td)) { + tdToFEdges.put(td, new Vector()); + } /** counter to keep track of the number of parameters (of the * task being analyzed) that are satisfied by the flagstate. @@ -214,6 +220,7 @@ private void analyseTasks(FlagState fs) { if (fn1.kind()==FKind.FlatReturnNode) { /* Self edge */ FEdge newedge=new FEdge(fs, taskname, td, parameterindex); + ((Vector)tdToFEdges.get(td)).add(newedge); fs.addEdge(newedge); continue; } else if (fn1.kind()==FKind.FlatFlagActionNode) { @@ -232,6 +239,7 @@ private void analyseTasks(FlagState fs) { //seen this node already fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit); FEdge newedge=new FEdge(fs_taskexit,taskname, td, parameterindex); + ((Vector)tdToFEdges.get(td)).add(newedge); fs.addEdge(newedge); } continue; @@ -417,5 +425,9 @@ private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){ public Vector getRootNodes(ClassDescriptor cd){ return (Vector)cdtorootnodes.get(cd); } + + public Vector getFEdgesFromTD(TaskDescriptor td) { + return (Vector)tdToFEdges.get(td); + } } diff --git a/Robust/src/IR/State.java b/Robust/src/IR/State.java index 9db4b173..070abf35 100644 --- a/Robust/src/IR/State.java +++ b/Robust/src/IR/State.java @@ -52,6 +52,7 @@ public class State { public boolean FLATIRGRAPHLIBMETHODS=false; public boolean OWNERSHIP=false; public boolean OPTIONAL=false; + public boolean SCHEDULING=false; public boolean THREAD=false; public boolean CONSCHECK=false; public boolean INSTRUCTIONFAILURE=false; diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index 784a95c4..86e1dfa3 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -3,6 +3,8 @@ package Main; import java.io.Reader; import java.io.BufferedReader; import java.io.FileReader; +import java.util.Vector; + import IR.Tree.ParseNode; import IR.Tree.BuildIR; import IR.Tree.SemanticCheck; @@ -10,6 +12,8 @@ import IR.Flat.BuildFlat; import IR.Flat.BuildCode; import IR.State; import IR.TypeUtil; +import Analysis.Scheduling.ScheduleAnalysis; +import Analysis.Scheduling.ScheduleEdge; import Analysis.TaskStateAnalysis.TaskAnalysis; import Analysis.TaskStateAnalysis.TaskGraph; import Analysis.CallGraph.CallGraph; @@ -70,6 +74,8 @@ public class Main { state.OWNERSHIP=true; else if (option.equals("-optional")) state.OPTIONAL=true; + else if (option.equals("-scheduling")) + state.SCHEDULING=true; else if (option.equals("-thread")) state.THREAD=true; else if (option.equals("-dsm")) @@ -185,6 +191,31 @@ public class Main { serve.run(); } + if (state.SCHEDULING) { + ScheduleAnalysis scheduleAnalysis = new ScheduleAnalysis(state, ta); + scheduleAnalysis.preSchedule(); + + // Randomly set the newRate and probability of ScheduleEdges + /*Vector sedges = scheduleAnalysis.getSEdges4Test(); + java.util.Random r=new java.util.Random(); + for(int i = 0; i < sedges.size(); i++) { + ScheduleEdge temp = sedges.elementAt(i); + int tint = 0; + do { + tint = r.nextInt()%100; + }while(tint <= 0); + temp.setProbability(tint); + do { + tint = r.nextInt()%10; + } while(tint <= 0); + temp.setNewRate(tint); + //temp.setNewRate((i+1)%2+1); + } + //sedges.elementAt(3).setNewRate(2);*/ + scheduleAnalysis.printScheduleGraph("scheduling_ori.dot"); + scheduleAnalysis.scheduleAnalysis(); + scheduleAnalysis.printScheduleGraph("scheduling.dot"); + } } diff --git a/Robust/src/Makefile b/Robust/src/Makefile index 1a95deaf..748ee17f 100644 --- a/Robust/src/Makefile +++ b/Robust/src/Makefile @@ -86,7 +86,11 @@ Interface/JhttpServer.class Interface/JhttpWorker.class \ Interface/LogFile.class Interface/Pair.class \ Interface/WebInterface.class Analysis/Prefetch/PrefetchAnalysis.class \ Analysis/Prefetch/PrefetchPair.class Analysis/Prefetch/PairMap.class \ -Analysis/Prefetch/IndexDescriptor.class +Analysis/Prefetch/IndexDescriptor.class \ +Analysis/Scheduling/ClassNode.class \ +Analysis/Scheduling/ScheduleAnalysis.class \ +Analysis/Scheduling/ScheduleEdge.class \ +Analysis/Scheduling/ScheduleNode.class diff --git a/Robust/src/Util/Edge.java b/Robust/src/Util/Edge.java index 72d55691..8b13b03d 100644 --- a/Robust/src/Util/Edge.java +++ b/Robust/src/Util/Edge.java @@ -38,4 +38,35 @@ public class Edge { dotnodeparams = param; } } + + public static final EdgeStatus UNVISITED = new EdgeStatus("UNVISITED"); + public static final EdgeStatus PROCESSING = new EdgeStatus("PROCESSING"); + public static final EdgeStatus FINISHED = new EdgeStatus("FINISHED"); + + public static class EdgeStatus { + private static String name; + private EdgeStatus(String name) { this.name = name; } + public String toString() { return name; } + } + + int discoverytime = -1; + int finishingtime = -1; /* used for searches */ + EdgeStatus status = UNVISITED; + + void reset() { + discoverytime = -1; + finishingtime = -1; + status = UNVISITED; + } + + void discover(int time) { + discoverytime = time; + status = PROCESSING; + } + + void finish(int time) { + assert status == PROCESSING; + finishingtime = time; + status = FINISHED; + } } diff --git a/Robust/src/Util/GraphNode.java b/Robust/src/Util/GraphNode.java index c352aaa4..424dfc65 100755 --- a/Robust/src/Util/GraphNode.java +++ b/Robust/src/Util/GraphNode.java @@ -397,6 +397,8 @@ public class GraphNode { int sccindex = 0; Collection nodes; Vector finishingorder=null; + Vector finishingorder_edge = null; + int edgetime = 0; HashMap sccmap; HashMap sccmaprev; @@ -456,6 +458,7 @@ public class GraphNode { private boolean go() { Iterator i; time = 0; + edgetime = 0; boolean acyclic=true; i = nodes.iterator(); while (i.hasNext()) { @@ -476,28 +479,59 @@ public class GraphNode { } private boolean dfs(GraphNode gn) { - boolean acyclic=true; + boolean acyclic=true; gn.discover(time++); Iterator edges = gn.edges(); while (edges.hasNext()) { Edge edge = (Edge) edges.next(); + edge.discover(edgetime++); GraphNode node = edge.getTarget(); - if (!nodes.contains(node)) /* Skip nodes which aren't in the set */ - continue; + if (!nodes.contains(node)) /* Skip nodes which aren't in the set */ { + if(finishingorder_edge != null) + finishingorder_edge.add(edge); + edge.finish(edgetime++); + continue; + } if (node.getStatus() == UNVISITED) { if (!dfs(node)) - acyclic=false; + acyclic=false; } else if (node.getStatus()==PROCESSING) { - acyclic=false; - } + acyclic=false; + } + if(finishingorder_edge != null) + finishingorder_edge.add(edge); + edge.finish(edgetime++); } - if (finishingorder!=null) - finishingorder.add(gn); - gn.finish(time++); - return acyclic; + if (finishingorder!=null) + finishingorder.add(gn); + gn.finish(time++); + return acyclic; } + public static Vector topology(Collection nodes, Vector finishingorder_edge) { + if (nodes==null) { + throw new NullPointerException(); + } + DFS dfs=new DFS(nodes); + dfs.finishingorder=new Vector(); + if(finishingorder_edge != null) { + dfs.finishingorder_edge = new Vector(); + } + boolean acyclic=dfs.go(); + Vector topology = new Vector(); + for(int i=dfs.finishingorder.size()-1;i>=0;i--) { + GraphNode gn=(GraphNode)dfs.finishingorder.get(i); + topology.add(gn); + } + if(finishingorder_edge != null) { + for(int i=dfs.finishingorder_edge.size()-1;i>=0;i--) { + Edge gn=(Edge)dfs.finishingorder_edge.get(i); + finishingorder_edge.add(gn); + } + } + return topology; + } } /* end DFS */ } diff --git a/Robust/src/buildscript b/Robust/src/buildscript index 38b04d67..5adc8f08 100755 --- a/Robust/src/buildscript +++ b/Robust/src/buildscript @@ -9,6 +9,7 @@ echo -recover compile task code echo -specdir directory echo -selfloop task - this task cannot self loop forever echo -taskstate do task state analysis +echo -scheduling do task scheduling echo -optional enable optional echo -debug generate debug symbols echo -prefetch prefetch analysis @@ -83,6 +84,9 @@ EXTRAOPTIONS="$EXTRAOPTIONS -pg" elif [[ $1 = '-taskstate' ]] then JAVAOPTS="$JAVAOPTS -taskstate" +elif [[ $1 = '-scheduling' ]] +then +JAVAOPTS="$JAVAOPTS -scheduling" elif [[ $1 = '-optional' ]] then JAVAOPTS="$JAVAOPTS -optional" -- 2.34.1