Robust/src/Analysis/Scheduling/SchedulingUtil.java

   1 package Analysis.Scheduling;
   2
   3 import java.io.File;
   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;
  11 import java.util.Set;
  12 import java.util.Vector;
  13 import java.util.Map.Entry;
  14
  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;
  22 import IR.Operation;
  23 import IR.Tree.FlagExpressionNode;
  24 import IR.Tree.FlagNode;
  25 import IR.Tree.FlagOpNode;
  26 import Util.Edge;
  27 import Util.GraphNode;
  28 import Util.Namer;
  29
  30 public class SchedulingUtil {
  31
  32   /*public static int maxDivisor(int l, int r) {
  33       int a = l;
  34       int b = r;
  35       int c = 0;
  36
  37       while(true) {
  38           if(a == 0) {
  39               return b << c;
  40           } else if(b == 0) {
  41               return a << c;
  42           }
  43
  44           if(((a&1)==0) && ((b&1)==0)) {
  45               // a and b are both even
  46               a >>= 1;
  47               b >>= 1;
  48    ++c;
  49           } else if(((a&1)==0) && ((b&1)!=0)) {
  50               // a is even, b is odd
  51               a >>= 1;
  52           } else if (((a&1)!=0) && ((b&1)==0)) {
  53               // a is odd, b is even
  54               b >>= 1;
  55           } else if (((a&1)!=0) && ((b&1)!=0)) {
  56               // a and b are both odd
  57               int tmp = a>b? b:a;
  58               a = a>b ? (a-b):(b-a);
  59               b = tmp;
  60           }
  61       }
  62      }*/
  63
  64   public static boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
  65     if (fen==null)
  66       return true;
  67     else if (fen instanceof FlagNode)
  68       return fs.get(((FlagNode)fen).getFlag());
  69     else
  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
  74       case Operation.LOGIC_OR:
  75         return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
  76
  77       case Operation.LOGIC_NOT:
  78         return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
  79
  80       default:
  81         return false;
  82       }
  83   }
  84
  85   public static void printScheduleGraph(String path, Vector<ScheduleNode> sNodes) {
  86     try {
  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");
  94       output.close();
  95     } catch (Exception e) {
  96       e.printStackTrace();
  97       System.exit(-1);
  98     }
  99   }
 100
 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();
 115         output.print("\t");
 116         if(se.getSourceCNode().isclone()) {
 117           output.print(se.getSourceCNode().getLabel());
 118         } else {
 119           if(se.getSourceFState() == null) {
 120             output.print(se.getSourceCNode().getClusterLabel());
 121           } else {
 122             output.print(se.getSourceFState().getLabel());
 123           }
 124         }
 125
 126         output.print(" -> ");
 127         if(se.isclone()) {
 128           if(se.getTargetCNode().isclone()) {
 129             output.print(se.getTargetCNode().getLabel());
 130           } else {
 131             output.print(se.getTargetCNode().getClusterLabel());
 132           }
 133           output.println(" [label=\"" + se.getLabel() + "\", color=red];");
 134         } else {
 135           output.print(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail=");
 136           if(se.getSourceCNode().isclone()) {
 137             output.println(se.getSourceCNode().getLabel() + "];");
 138           } else {
 139             output.println(se.getSourceCNode().getClusterLabel() + "];");
 140           }
 141         }
 142       }
 143       output.println("\t}\n");
 144       //Draw 'new' edges of this ScheduleNode
 145       while(edges.hasNext()) {
 146         ScheduleEdge se = (ScheduleEdge)edges.next();
 147         output.print("\t");
 148         if(se.getSourceCNode().isclone()) {
 149           output.print(se.getSourceCNode().getLabel());
 150         } else {
 151           if(se.getSourceFState() == null) {
 152             output.print(se.getSourceCNode().getClusterLabel());
 153           } else {
 154             output.print(se.getSourceFState().getLabel());
 155           }
 156         }
 157
 158         output.print(" -> ");
 159         if(se.isclone()) {
 160           if(se.getTargetCNode().isclone()) {
 161             output.print(se.getTargetCNode().getLabel());
 162           } else {
 163             output.print(se.getTargetCNode().getClusterLabel());
 164           }
 165           output.println(" [label=\"" + se.getLabel() + "\", color=red, style=dashed];");
 166         } else {
 167           output.println(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed];");
 168         }
 169       }
 170     }
 171   }
 172
 173   private static void traverseCNodes(PrintWriter output, Iterator it) {
 174     //Draw clusters representing ClassNodes
 175     while (it.hasNext()) {
 176       ClassNode gn = (ClassNode) it.next();
 177       if(gn.isclone()) {
 178         output.println("\t\t" + gn.getLabel() + " [style=dashed, label=\"" + gn.getTextLabel() + "\", shape=box];");
 179       } else {
 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");
 185       }
 186     }
 187   }
 188
 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());
 194
 195     Iterator it = nodes.iterator();
 196     while (it.hasNext()) {
 197       GraphNode gn = (GraphNode) it.next();
 198       Iterator edges = gn.edges();
 199       String label = "";
 200       String dotnodeparams="";
 201
 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);
 206
 207         if (!newlabel.equals("") && !label.equals("")) {
 208           label+=", ";
 209         }
 210         if (!newparams.equals("")) {
 211           dotnodeparams+=", " + name.nodeOption(gn);
 212         }
 213         label+=name.nodeLabel(gn);
 214       }
 215       label += ":[" + ((FlagState)gn).getExeTime() + "]";
 216
 217       if (!gn.merge)
 218         output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
 219
 220       if (!gn.merge)
 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="";
 229
 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(""))
 235                   edgelabel+=", ";
 236                 edgelabel+=newlabel;
 237                 if (!newoption.equals(""))
 238                   edgedotnodeparams+=", "+newoption;
 239               }
 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() + "%) }";
 250                 }
 251               }
 252               output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
 253             }
 254           }
 255         }
 256     }
 257   }
 258
 259   private static Set nonmerge(GraphNode gn, Collection nodes) {
 260     HashSet newset=new HashSet();
 261     HashSet toprocess=new HashSet();
 262     toprocess.add(gn);
 263     while(!toprocess.isEmpty()) {
 264       GraphNode gn2=(GraphNode)toprocess.iterator().next();
 265       toprocess.remove(gn2);
 266       if (!gn2.merge)
 267         newset.add(gn2);
 268       else {
 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))
 274             toprocess.add(node);
 275         }
 276       }
 277     }
 278     return newset;
 279   }
 280
 281   public static void printSimulationResult(String path, int time, int coreNum, Vector<CheckPoint> checkpoints) {
 282     try {
 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{");
 287       output.print("\t");
 288       output.println("node [shape=plaintext];");
 289       output.print("\t");
 290       output.println("edge [dir=none];");
 291       output.print("\t");
 292       output.println("ranksep=.05;");
 293       output.println();
 294       output.print("\t");
 295       int j = 0;
 296
 297       // the capital line
 298       output.print("{rank=source; \"Time\"; ");
 299       for(j = 0; j < coreNum; j++) {
 300         output.print("\"core " + j + "\"; ");
 301       }
 302       output.println("}");
 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;
 311         lastTasks[j] = "";
 312       }
 313       timeNodes.add("0");
 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);
 322         }
 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]);
 330           }
 331           if(!(tmpisset.contains(cNum)) && (isTaskFinish[cNum]) && !(tmpisTaskFinish.contains(cNum))) {
 332             tmpisTaskFinish.add(cNum);             // records those with task finished the first time visit it
 333           }
 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 + ":"));
 339             isfirst = true;
 340           }
 341           tmpLabel = tmpTaskNodes.get(tmpTaskNode);
 342           switch(taction.getType()){
 343           case Action.ADDOBJ: {
 344             if(!isfirst) {
 345               tmpLabel.append("\\n");
 346             }
 347             tmpLabel.append("(" + taction.getTransObj().getSymbol() + ")arrives;");
 348             if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 349               output.print("\t");
 350               if(lastTaskNodes[cNum].equals("first")) {
 351                 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
 352               } else {
 353                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 354               }
 355               if(tmpisTaskFinish.contains(cNum)) {
 356                 output.print(" [style=invis]");
 357               }
 358               output.println(";");
 359               lastTaskNodes[cNum] = tmpTaskNode;
 360             }
 361             break;
 362           }
 363
 364           case Action.TASKFINISH: {
 365             if(!isfirst) {
 366               tmpLabel.append("\\n");
 367             }
 368             tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes;");
 369             if(!(lastTaskNodes[cNum].equals("first"))) {
 370               if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 371                 output.print("\t");
 372                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 373                 lastTaskNodes[cNum] = tmpTaskNode;
 374               }
 375               if(tmpisset.contains(cNum)) {
 376                 isTaskFinish[cNum] &= true;
 377               } else {
 378                 isTaskFinish[cNum] = true;
 379                 tmpisset.add(cNum);
 380               }
 381               lastTasks[cNum] = "";
 382             } else {
 383               throw new Exception("Error: unexpected task finish");
 384             }
 385             break;
 386           }
 387
 388           case Action.TFWITHOBJ: {
 389             if(!isfirst) {
 390               tmpLabel.append("\\n");
 391             }
 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(",");
 399               } else {
 400                 tmpLabel.append(";");
 401               }
 402             }
 403             if(!(lastTaskNodes[cNum].equals("first"))) {
 404               if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 405                 output.print("\t");
 406                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 407                 lastTaskNodes[cNum] = tmpTaskNode;
 408               }
 409               if(tmpisset.contains(cNum)) {
 410                 isTaskFinish[cNum] &= true;
 411               } else {
 412                 isTaskFinish[cNum] = true;
 413                 tmpisset.add(cNum);
 414               }
 415               lastTasks[cNum] = "";
 416             } else {
 417               throw new Exception("Error: unexpected task finish");
 418             }
 419             break;
 420           }
 421
 422           case Action.TASKSTART: {
 423             if(!isfirst) {
 424               tmpLabel.append("\\n");
 425             }
 426             tmpLabel.append("<" + taction.getTd().getSymbol() + ">starts;");
 427             lastTasks[cNum] = taction.getTd().getSymbol();
 428
 429             if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 430               output.print("\t");
 431               if(lastTaskNodes[cNum].equals("first")) {
 432                 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
 433               } else {
 434                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 435               }
 436               if(tmpisTaskFinish.contains(cNum)) {
 437                 output.print(" [style=invis]");
 438               }
 439               output.println(";");
 440               lastTaskNodes[cNum] = tmpTaskNode;
 441             }
 442             isTaskFinish[cNum] &= false;
 443             break;
 444           }
 445
 446           case Action.TASKABORT: {
 447             if(!isfirst) {
 448               tmpLabel.append("\\n");
 449             }
 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))) {
 454                 output.print("\t");
 455                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 456                 lastTaskNodes[cNum] = tmpTaskNode;
 457               }
 458               if(tmpisset.contains(cNum)) {
 459                 isTaskFinish[cNum] &= true;
 460               } else {
 461                 isTaskFinish[cNum] = true;
 462                 tmpisset.add(cNum);
 463               }
 464               lastTasks[cNum] = "";
 465             } else {
 466               throw new Exception("Error: unexpected task aborts");
 467             }
 468             break;
 469           }
 470
 471           case Action.TASKREMOVE: {
 472             if(!isfirst) {
 473               tmpLabel.append("\\n");
 474             }
 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))) {
 479                 output.print("\t");
 480                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 481                 lastTaskNodes[cNum] = tmpTaskNode;
 482               }
 483               if(tmpisset.contains(cNum)) {
 484                 isTaskFinish[cNum] &= true;
 485               } else {
 486                 isTaskFinish[cNum] = true;
 487                 tmpisset.add(cNum);
 488               }
 489               lastTasks[cNum] = "";
 490             } else {
 491               throw new Exception("Error: unexpected task remove");
 492             }
 493             break;
 494           }
 495           }
 496         }
 497         Enumeration<String> keys = tmpTaskNodes.keys();
 498         while(keys.hasMoreElements()) {
 499           String tmpTaskNode = keys.nextElement();
 500           output.print("\t");
 501           output.println(tmpTaskNode + "[label=\"" + tmpTaskNodes.get(tmpTaskNode).toString() + "\"]");
 502         }
 503         output.print("\t");
 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);
 509           output.print("; ");
 510         }
 511         output.println("}");
 512         output.print("\t");
 513       }
 514       output.print("\t");
 515       output.print("\t");
 516       output.println("\"Time\"->" + timeNodes.elementAt(0) + "[style=invis];");
 517       for(j = 0; j < time; j++) {
 518         output.print(j + "->");
 519       }
 520       output.println(timeNodes.lastElement() + ";");
 521       output.println("}");
 522       output.close();
 523     } catch (Exception e) {
 524       e.printStackTrace();
 525       System.exit(-1);
 526     }
 527   }
 528 }