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)));
73 case Operation.LOGIC_OR:
74 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
75 case Operation.LOGIC_NOT:
76 return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
82 public static void printScheduleGraph(String path, Vector<ScheduleNode> sNodes) {
84 File file=new File(path);
85 FileOutputStream dotstream=new FileOutputStream(file,false);
86 PrintWriter output = new java.io.PrintWriter(dotstream, true);
87 output.println("digraph G {");
88 output.println("\tcompound=true;\n");
89 traverseSNodes(output, sNodes);
90 output.println("}\n");
92 } catch (Exception e) {
98 private static void traverseSNodes(PrintWriter output, Vector<ScheduleNode> sNodes){
99 //Draw clusters representing ScheduleNodes
100 Iterator it = sNodes.iterator();
101 while (it.hasNext()) {
102 ScheduleNode gn = (ScheduleNode) it.next();
103 Iterator edges = gn.edges();
104 output.println("\tsubgraph " + gn.getLabel() + "{");
105 output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
106 Iterator it_cnodes = gn.getClassNodesIterator();
107 traverseCNodes(output, it_cnodes);
108 //Draw the internal 'new' edges
109 Iterator it_edges =gn.getScheduleEdgesIterator();
110 while(it_edges.hasNext()) {
111 ScheduleEdge se = (ScheduleEdge)it_edges.next();
113 if(se.getSourceCNode().isclone()) {
114 output.print(se.getSourceCNode().getLabel());
116 if(se.getSourceFState() == null) {
117 output.print(se.getSourceCNode().getClusterLabel());
119 output.print(se.getSourceFState().getLabel());
123 output.print(" -> ");
125 if(se.getTargetCNode().isclone()) {
126 output.print(se.getTargetCNode().getLabel());
128 output.print(se.getTargetCNode().getClusterLabel());
130 output.println(" [label=\"" + se.getLabel() + "\", color=red];");
132 output.print(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail=");
133 if(se.getSourceCNode().isclone()) {
134 output.println(se.getSourceCNode().getLabel() + "];");
136 output.println(se.getSourceCNode().getClusterLabel() + "];");
140 output.println("\t}\n");
141 //Draw 'new' edges of this ScheduleNode
142 while(edges.hasNext()) {
143 ScheduleEdge se = (ScheduleEdge)edges.next();
145 if(se.getSourceCNode().isclone()) {
146 output.print(se.getSourceCNode().getLabel());
148 if(se.getSourceFState() == null) {
149 output.print(se.getSourceCNode().getClusterLabel());
151 output.print(se.getSourceFState().getLabel());
155 output.print(" -> ");
157 if(se.getTargetCNode().isclone()) {
158 output.print(se.getTargetCNode().getLabel());
160 output.print(se.getTargetCNode().getClusterLabel());
162 output.println(" [label=\"" + se.getLabel() + "\", color=red, style=dashed]");
164 output.println(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed]");
170 private static void traverseCNodes(PrintWriter output, Iterator it){
171 //Draw clusters representing ClassNodes
172 while (it.hasNext()) {
173 ClassNode gn = (ClassNode) it.next();
175 output.println("\t\t" + gn.getLabel() + " [style=dashed, label=\"" + gn.getTextLabel() + "\", shape=box];");
177 output.println("\tsubgraph " + gn.getClusterLabel() + "{");
178 output.println("\t\tstyle=dashed;");
179 output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
180 traverseFlagStates(output, gn.getFlagStates());
181 output.println("\t}\n");
186 private static void traverseFlagStates(PrintWriter output, Collection nodes) {
187 Set cycleset=GraphNode.findcycles(nodes);
188 Vector namers=new Vector();
189 namers.add(new Namer());
190 namers.add(new Allocations());
192 Iterator it = nodes.iterator();
193 while (it.hasNext()) {
194 GraphNode gn = (GraphNode) it.next();
195 Iterator edges = gn.edges();
197 String dotnodeparams="";
199 for(int i=0;i<namers.size();i++) {
200 Namer name=(Namer) namers.get(i);
201 String newlabel=name.nodeLabel(gn);
202 String newparams=name.nodeOption(gn);
204 if (!newlabel.equals("") && !label.equals("")) {
207 if (!newparams.equals("")) {
208 dotnodeparams+=", " + name.nodeOption(gn);
210 label+=name.nodeLabel(gn);
212 label += ":[" + ((FlagState)gn).getExeTime() + "]";
215 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
218 while (edges.hasNext()) {
219 Edge edge = (Edge) edges.next();
220 GraphNode node = edge.getTarget();
221 if (nodes.contains(node)) {
222 for(Iterator nodeit=nonmerge(node, nodes).iterator();nodeit.hasNext();) {
223 GraphNode node2=(GraphNode)nodeit.next();
224 String edgelabel = "";
225 String edgedotnodeparams="";
227 for(int i=0;i<namers.size();i++) {
228 Namer name=(Namer) namers.get(i);
229 String newlabel=name.edgeLabel(edge);
230 String newoption=name.edgeOption(edge);
231 if (!newlabel.equals("")&& ! edgelabel.equals(""))
234 if (!newoption.equals(""))
235 edgedotnodeparams+=", "+newoption;
237 edgelabel+=":[" + ((FEdge)edge).getExeTime() + "]";
238 Hashtable<ClassDescriptor, NewObjInfo> hashtable = ((FEdge)edge).getNewObjInfoHashtable();
239 if(hashtable != null) {
240 Set<ClassDescriptor> keys = hashtable.keySet();
241 Iterator it_keys = keys.iterator();
242 while(it_keys.hasNext()) {
243 ClassDescriptor cd = (ClassDescriptor)it_keys.next();
244 NewObjInfo noi = hashtable.get(cd);
245 edgelabel += ":{ class " + cd.getSymbol() + " | " + noi.getNewRate() + " | (" + noi.getProbability() + "%) }";
248 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
255 private static Set nonmerge(GraphNode gn, Collection nodes) {
256 HashSet newset=new HashSet();
257 HashSet toprocess=new HashSet();
259 while(!toprocess.isEmpty()) {
260 GraphNode gn2=(GraphNode)toprocess.iterator().next();
261 toprocess.remove(gn2);
265 Iterator edges = gn2.edges();
266 while (edges.hasNext()) {
267 Edge edge = (Edge) edges.next();
268 GraphNode node = edge.getTarget();
269 if (!newset.contains(node)&&nodes.contains(node))
277 public static void printSimulationResult(String path, int time, int coreNum, Vector<CheckPoint> checkpoints) {
279 File file=new File(path);
280 FileOutputStream dotstream=new FileOutputStream(file,false);
281 PrintWriter output = new java.io.PrintWriter(dotstream, true);
282 output.println("digraph simulation{");
284 output.println("node [shape=plaintext];");
286 output.println("edge [dir=none];");
288 output.println("ranksep=.05;");
294 output.print("{rank=source; \"Time\"; ");
295 for(j = 0; j < coreNum; j++) {
296 output.print("\"core " + j + "\"; ");
299 // time coordinate nodes
300 Vector<String> timeNodes = new Vector<String>();
301 String[] lastTaskNodes = new String[coreNum];
302 boolean[] isTaskFinish = new boolean[coreNum];
303 for(j = 0; j < coreNum; j++) {
304 lastTaskNodes[j] = "first";
305 isTaskFinish[j] = true;
308 for(j = 0; j < checkpoints.size(); j++) {
309 CheckPoint tcp = checkpoints.elementAt(j);
310 String tnode = String.valueOf(tcp.getTimepoint());
311 if(!timeNodes.contains(tnode)) {
312 timeNodes.add(tnode);
314 Vector<Action> actions = tcp.getActions();
315 Hashtable<String, StringBuffer> tmpTaskNodes = new Hashtable<String, StringBuffer>();
316 for(int i = 0; i < actions.size(); i++) {
317 Action taction = actions.elementAt(i);
318 int cNum = taction.getCoreNum();
319 String tmpTaskNode = "\"" + tnode + "core" + cNum + "\"";
320 StringBuffer tmpLabel = null;
321 boolean isfirst = false;
322 if(!tmpTaskNodes.containsKey(tmpTaskNode)) {
323 tmpTaskNodes.put(tmpTaskNode, new StringBuffer(tnode + ":"));
326 tmpLabel = tmpTaskNodes.get(tmpTaskNode);
327 switch(taction.getType()){
328 case Action.ADDOBJ: {
330 tmpLabel.append("\\n");
332 tmpLabel.append("(" + taction.getTransObj().getSymbol() + ")arrives;");
333 if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
335 if(lastTaskNodes[cNum].equals("first")) {
336 output.println("\"core " + cNum + "\"->" + tmpTaskNode);
338 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
340 if(isTaskFinish[cNum]) {
341 output.print(" [style=invis]");
344 lastTaskNodes[cNum] = tmpTaskNode;
348 case Action.TASKFINISH: {
350 tmpLabel.append("\\n");
352 tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes;");
353 if(!(lastTaskNodes[cNum].equals("first"))) {
354 if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
356 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
357 lastTaskNodes[cNum] = tmpTaskNode;
359 isTaskFinish[cNum] = true;
361 throw new Exception("Error: unexpected task finish");
365 case Action.TFWITHOBJ: {
367 tmpLabel.append("\\n");
369 tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes; ");
370 Iterator<Entry<ClassDescriptor, Integer>> it_entry = (Iterator<Entry<ClassDescriptor, Integer>>)taction.getNObjs().entrySet().iterator();
371 while(it_entry.hasNext()) {
372 Entry<ClassDescriptor, Integer> entry = it_entry.next();
373 tmpLabel.append(entry.getValue() + "(" + entry.getKey().getSymbol() + ")");
374 if(it_entry.hasNext()) {
375 tmpLabel.append(",");
377 tmpLabel.append(";");
380 if(!(lastTaskNodes[cNum].equals("first")) &&
381 !(lastTaskNodes[cNum].equals(tmpTaskNode))) {
383 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
384 lastTaskNodes[cNum] = tmpTaskNode;
385 isTaskFinish[cNum] = true;
387 throw new Exception("Error: unexpected task finish");
391 case Action.TASKSTART: {
393 tmpLabel.append("\\n");
395 tmpLabel.append("<" + taction.getTd().getSymbol() + ">starts;");
397 if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
399 if(lastTaskNodes[cNum].equals("first")) {
400 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
402 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
404 if(isTaskFinish[cNum]) {
405 output.print(" [style=invis]");
408 lastTaskNodes[cNum] = tmpTaskNode;
410 isTaskFinish[cNum] = false;
413 case Action.TASKABORT: {
415 tmpLabel.append("\\n");
417 tmpLabel.append("<" + taction.getTd().getSymbol() + ">aborts;");
418 if(!(lastTaskNodes[cNum].equals("first")) &&
419 !(lastTaskNodes[cNum].equals(tmpTaskNode))) {
421 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
422 lastTaskNodes[cNum] = tmpTaskNode;
423 isTaskFinish[cNum] = true;
425 throw new Exception("Error: unexpected task aborts");
429 case Action.TASKREMOVE: {
431 tmpLabel.append("\\n");
433 tmpLabel.append("<" + taction.getTd().getSymbol() + ">removes;");
434 if(!(lastTaskNodes[cNum].equals("first")) &&
435 !(lastTaskNodes[cNum].equals(tmpTaskNode))) {
437 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
438 lastTaskNodes[cNum] = tmpTaskNode;
439 isTaskFinish[cNum] = true;
441 throw new Exception("Error: unexpected task remove");
447 Enumeration<String> keys = tmpTaskNodes.keys();
448 while(keys.hasMoreElements()) {
449 String tmpTaskNode = keys.nextElement();
451 output.println(tmpTaskNode + "[label=\"" + tmpTaskNodes.get(tmpTaskNode).toString() + "\"]");
454 output.print("{rank=same; rankdir=LR; " + tnode + "; ");
455 keys = tmpTaskNodes.keys();
456 while(keys.hasMoreElements()) {
457 String tmpTaskNode = keys.nextElement();
458 output.print(tmpTaskNode);
466 output.println("\"Time\"->" + timeNodes.elementAt(0) + "[style=invis];");
467 for(j = 0; j < time; j++) {
468 output.print(j + "->");
470 output.println(timeNodes.lastElement() + ";");
473 } catch (Exception e) {