1 package Analysis.Scheduling;
4 import java.io.FileOutputStream;
5 import java.io.PrintWriter;
6 import java.util.Collection;
7 import java.util.Enumeration;
8 import java.util.HashSet;
9 import java.util.Hashtable;
10 import java.util.Iterator;
12 import java.util.Vector;
13 import java.util.Map.Entry;
15 import Analysis.Scheduling.ScheduleSimulator.Action;
16 import Analysis.Scheduling.ScheduleSimulator.CheckPoint;
17 import Analysis.TaskStateAnalysis.Allocations;
18 import Analysis.TaskStateAnalysis.FEdge;
19 import Analysis.TaskStateAnalysis.FlagState;
20 import Analysis.TaskStateAnalysis.FEdge.NewObjInfo;
21 import IR.ClassDescriptor;
23 import IR.Tree.FlagExpressionNode;
24 import IR.Tree.FlagNode;
25 import IR.Tree.FlagOpNode;
27 import Util.GraphNode;
30 public class SchedulingUtil {
32 /*public static int maxDivisor(int l, int r) {
44 if(((a&1)==0) && ((b&1)==0)) {
45 // a and b are both even
49 } else if(((a&1)==0) && ((b&1)!=0)) {
50 // a is even, b is odd
52 } else if (((a&1)!=0) && ((b&1)==0)) {
53 // a is odd, b is even
55 } else if (((a&1)!=0) && ((b&1)!=0)) {
56 // a and b are both odd
58 a = a>b ? (a-b):(b-a);
64 public static boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
67 else if (fen instanceof FlagNode)
68 return fs.get(((FlagNode)fen).getFlag());
70 switch (((FlagOpNode)fen).getOp().getOp()) {
71 case Operation.LOGIC_AND:
72 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
74 case Operation.LOGIC_OR:
75 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
77 case Operation.LOGIC_NOT:
78 return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
85 public static void printScheduleGraph(String path, Vector<ScheduleNode> sNodes) {
87 File file=new File(path);
88 FileOutputStream dotstream=new FileOutputStream(file,false);
89 PrintWriter output = new java.io.PrintWriter(dotstream, true);
90 output.println("digraph G {");
91 output.println("\tcompound=true;\n");
92 traverseSNodes(output, sNodes);
93 output.println("}\n");
95 } catch (Exception e) {
101 private static void traverseSNodes(PrintWriter output, Vector<ScheduleNode> sNodes) {
102 //Draw clusters representing ScheduleNodes
103 Iterator it = sNodes.iterator();
104 while (it.hasNext()) {
105 ScheduleNode gn = (ScheduleNode) it.next();
106 Iterator edges = gn.edges();
107 output.println("\tsubgraph " + gn.getLabel() + "{");
108 output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
109 Iterator it_cnodes = gn.getClassNodesIterator();
110 traverseCNodes(output, it_cnodes);
111 //Draw the internal 'new' edges
112 Iterator it_edges =gn.getScheduleEdgesIterator();
113 while(it_edges.hasNext()) {
114 ScheduleEdge se = (ScheduleEdge)it_edges.next();
116 if(se.getSourceCNode().isclone()) {
117 output.print(se.getSourceCNode().getLabel());
119 if(se.getSourceFState() == null) {
120 output.print(se.getSourceCNode().getClusterLabel());
122 output.print(se.getSourceFState().getLabel());
126 output.print(" -> ");
128 if(se.getTargetCNode().isclone()) {
129 output.print(se.getTargetCNode().getLabel());
131 output.print(se.getTargetCNode().getClusterLabel());
133 output.println(" [label=\"" + se.getLabel() + "\", color=red];");
135 output.print(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail=");
136 if(se.getSourceCNode().isclone()) {
137 output.println(se.getSourceCNode().getLabel() + "];");
139 output.println(se.getSourceCNode().getClusterLabel() + "];");
143 output.println("\t}\n");
144 //Draw 'new' edges of this ScheduleNode
145 while(edges.hasNext()) {
146 ScheduleEdge se = (ScheduleEdge)edges.next();
148 if(se.getSourceCNode().isclone()) {
149 output.print(se.getSourceCNode().getLabel());
151 if(se.getSourceFState() == null) {
152 output.print(se.getSourceCNode().getClusterLabel());
154 output.print(se.getSourceFState().getLabel());
158 output.print(" -> ");
160 if(se.getTargetCNode().isclone()) {
161 output.print(se.getTargetCNode().getLabel());
163 output.print(se.getTargetCNode().getClusterLabel());
165 output.println(" [label=\"" + se.getLabel() + "\", color=red, style=dashed];");
167 output.println(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed];");
173 private static void traverseCNodes(PrintWriter output, Iterator it) {
174 //Draw clusters representing ClassNodes
175 while (it.hasNext()) {
176 ClassNode gn = (ClassNode) it.next();
178 output.println("\t\t" + gn.getLabel() + " [style=dashed, label=\"" + gn.getTextLabel() + "\", shape=box];");
180 output.println("\tsubgraph " + gn.getClusterLabel() + "{");
181 output.println("\t\tstyle=dashed;");
182 output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
183 traverseFlagStates(output, gn.getFlagStates());
184 output.println("\t}\n");
189 private static void traverseFlagStates(PrintWriter output, Collection nodes) {
190 Set cycleset=GraphNode.findcycles(nodes);
191 Vector namers=new Vector();
192 namers.add(new Namer());
193 namers.add(new Allocations());
195 Iterator it = nodes.iterator();
196 while (it.hasNext()) {
197 GraphNode gn = (GraphNode) it.next();
198 Iterator edges = gn.edges();
200 String dotnodeparams="";
202 for(int i=0; i<namers.size(); i++) {
203 Namer name=(Namer) namers.get(i);
204 String newlabel=name.nodeLabel(gn);
205 String newparams=name.nodeOption(gn);
207 if (!newlabel.equals("") && !label.equals("")) {
210 if (!newparams.equals("")) {
211 dotnodeparams+=", " + name.nodeOption(gn);
213 label+=name.nodeLabel(gn);
215 label += ":[" + ((FlagState)gn).getExeTime() + "]";
218 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
221 while (edges.hasNext()) {
222 Edge edge = (Edge) edges.next();
223 GraphNode node = edge.getTarget();
224 if (nodes.contains(node)) {
225 for(Iterator nodeit=nonmerge(node, nodes).iterator(); nodeit.hasNext();) {
226 GraphNode node2=(GraphNode)nodeit.next();
227 String edgelabel = "";
228 String edgedotnodeparams="";
230 for(int i=0; i<namers.size(); i++) {
231 Namer name=(Namer) namers.get(i);
232 String newlabel=name.edgeLabel(edge);
233 String newoption=name.edgeOption(edge);
234 if (!newlabel.equals("")&& !edgelabel.equals(""))
237 if (!newoption.equals(""))
238 edgedotnodeparams+=", "+newoption;
240 edgelabel+=":[" + ((FEdge)edge).getExeTime() + "]";
241 edgelabel+=":(" + ((FEdge)edge).getProbability() + "%)";
242 Hashtable<ClassDescriptor, NewObjInfo> hashtable = ((FEdge)edge).getNewObjInfoHashtable();
243 if(hashtable != null) {
244 Set<ClassDescriptor> keys = hashtable.keySet();
245 Iterator it_keys = keys.iterator();
246 while(it_keys.hasNext()) {
247 ClassDescriptor cd = (ClassDescriptor)it_keys.next();
248 NewObjInfo noi = hashtable.get(cd);
249 edgelabel += ":{ class " + cd.getSymbol() + " | " + noi.getNewRate() + " | (" + noi.getProbability() + "%) }";
252 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
259 private static Set nonmerge(GraphNode gn, Collection nodes) {
260 HashSet newset=new HashSet();
261 HashSet toprocess=new HashSet();
263 while(!toprocess.isEmpty()) {
264 GraphNode gn2=(GraphNode)toprocess.iterator().next();
265 toprocess.remove(gn2);
269 Iterator edges = gn2.edges();
270 while (edges.hasNext()) {
271 Edge edge = (Edge) edges.next();
272 GraphNode node = edge.getTarget();
273 if (!newset.contains(node)&&nodes.contains(node))
281 public static void printSimulationResult(String path, int time, int coreNum, Vector<CheckPoint> checkpoints) {
283 File file=new File(path);
284 FileOutputStream dotstream=new FileOutputStream(file,false);
285 PrintWriter output = new java.io.PrintWriter(dotstream, true);
286 output.println("digraph simulation{");
288 output.println("node [shape=plaintext];");
290 output.println("edge [dir=none];");
292 output.println("ranksep=.05;");
298 output.print("{rank=source; \"Time\"; ");
299 for(j = 0; j < coreNum; j++) {
300 output.print("\"core " + j + "\"; ");
303 // time coordinate nodes
304 Vector<String> timeNodes = new Vector<String>();
305 String[] lastTaskNodes = new String[coreNum];
306 String[] lastTasks = new String[coreNum];
307 boolean[] isTaskFinish = new boolean[coreNum];
308 for(j = 0; j < coreNum; j++) {
309 lastTaskNodes[j] = "first";
310 isTaskFinish[j] = true;
314 for(j = 0; j < checkpoints.size(); j++) {
315 CheckPoint tcp = checkpoints.elementAt(j);
316 Hashtable<Integer, String> tmplastTasks = new Hashtable<Integer, String>();
317 Vector<Integer> tmpisTaskFinish = new Vector<Integer>();
318 Vector<Integer> tmpisset = new Vector<Integer>();
319 String tnode = String.valueOf(tcp.getTimepoint());
320 if(!timeNodes.contains(tnode)) {
321 timeNodes.add(tnode);
323 Vector<Action> actions = tcp.getActions();
324 Hashtable<String, StringBuffer> tmpTaskNodes = new Hashtable<String, StringBuffer>();
325 for(int i = 0; i < actions.size(); i++) {
326 Action taction = actions.elementAt(i);
327 int cNum = taction.getCoreNum();
328 if(!tmplastTasks.contains(cNum)) {
329 tmplastTasks.put(cNum, lastTasks[cNum]);
331 if(!(tmpisset.contains(cNum)) && (isTaskFinish[cNum]) && !(tmpisTaskFinish.contains(cNum))) {
332 tmpisTaskFinish.add(cNum); // records those with task finished the first time visit it
334 String tmpTaskNode = "\"" + tnode + "core" + cNum + "\"";
335 StringBuffer tmpLabel = null;
336 boolean isfirst = false;
337 if(!tmpTaskNodes.containsKey(tmpTaskNode)) {
338 tmpTaskNodes.put(tmpTaskNode, new StringBuffer(tnode + ":"));
341 tmpLabel = tmpTaskNodes.get(tmpTaskNode);
342 switch(taction.getType()) {
343 case Action.ADDOBJ: {
345 tmpLabel.append("\\n");
347 tmpLabel.append("(" + taction.getTransObj().getSymbol() + ")arrives;");
348 if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
350 if(lastTaskNodes[cNum].equals("first")) {
351 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
353 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
355 if(tmpisTaskFinish.contains(cNum)) {
356 output.print(" [style=invis]");
359 lastTaskNodes[cNum] = tmpTaskNode;
364 case Action.TASKFINISH: {
366 tmpLabel.append("\\n");
368 tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes;");
369 if(!(lastTaskNodes[cNum].equals("first"))) {
370 if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
372 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
373 lastTaskNodes[cNum] = tmpTaskNode;
375 if(tmpisset.contains(cNum)) {
376 isTaskFinish[cNum] &= true;
378 isTaskFinish[cNum] = true;
381 lastTasks[cNum] = "";
383 throw new Exception("Error: unexpected task finish");
388 case Action.TFWITHOBJ: {
390 tmpLabel.append("\\n");
392 tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes; ");
393 Iterator<Entry<ClassDescriptor, Integer>> it_entry = (Iterator<Entry<ClassDescriptor, Integer>>)taction.getNObjs().entrySet().iterator();
394 while(it_entry.hasNext()) {
395 Entry<ClassDescriptor, Integer> entry = it_entry.next();
396 tmpLabel.append(entry.getValue() + "(" + entry.getKey().getSymbol() + ")");
397 if(it_entry.hasNext()) {
398 tmpLabel.append(",");
400 tmpLabel.append(";");
403 if(!(lastTaskNodes[cNum].equals("first"))) {
404 if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
406 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
407 lastTaskNodes[cNum] = tmpTaskNode;
409 if(tmpisset.contains(cNum)) {
410 isTaskFinish[cNum] &= true;
412 isTaskFinish[cNum] = true;
415 lastTasks[cNum] = "";
417 throw new Exception("Error: unexpected task finish");
422 case Action.TASKSTART: {
424 tmpLabel.append("\\n");
426 tmpLabel.append("<" + taction.getTd().getSymbol() + ">starts;");
427 lastTasks[cNum] = taction.getTd().getSymbol();
429 if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
431 if(lastTaskNodes[cNum].equals("first")) {
432 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
434 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
436 if(tmpisTaskFinish.contains(cNum)) {
437 output.print(" [style=invis]");
440 lastTaskNodes[cNum] = tmpTaskNode;
442 isTaskFinish[cNum] &= false;
446 case Action.TASKABORT: {
448 tmpLabel.append("\\n");
450 tmpLabel.append("<" + taction.getTd().getSymbol() + ">aborts;");
451 if(!(lastTaskNodes[cNum].equals("first")) &&
452 (tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) {
453 if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
455 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
456 lastTaskNodes[cNum] = tmpTaskNode;
458 if(tmpisset.contains(cNum)) {
459 isTaskFinish[cNum] &= true;
461 isTaskFinish[cNum] = true;
464 lastTasks[cNum] = "";
466 throw new Exception("Error: unexpected task aborts");
471 case Action.TASKREMOVE: {
473 tmpLabel.append("\\n");
475 tmpLabel.append("<" + taction.getTd().getSymbol() + ">removes;");
476 if(!(lastTaskNodes[cNum].equals("first")) &&
477 (tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) {
478 if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
480 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
481 lastTaskNodes[cNum] = tmpTaskNode;
483 if(tmpisset.contains(cNum)) {
484 isTaskFinish[cNum] &= true;
486 isTaskFinish[cNum] = true;
489 lastTasks[cNum] = "";
491 throw new Exception("Error: unexpected task remove");
497 Enumeration<String> keys = tmpTaskNodes.keys();
498 while(keys.hasMoreElements()) {
499 String tmpTaskNode = keys.nextElement();
501 output.println(tmpTaskNode + "[label=\"" + tmpTaskNodes.get(tmpTaskNode).toString() + "\"]");
504 output.print("{rank=same; rankdir=LR; " + tnode + "; ");
505 keys = tmpTaskNodes.keys();
506 while(keys.hasMoreElements()) {
507 String tmpTaskNode = keys.nextElement();
508 output.print(tmpTaskNode);
516 output.println("\"Time\"->" + timeNodes.elementAt(0) + "[style=invis];");
517 for(j = 0; j < time; j++) {
518 output.print(j + "->");
520 output.println(timeNodes.lastElement() + ";");
523 } catch (Exception e) {