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             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));
  77             default:
  78                 return false;
  79             }
  80     }
  81
  82     public static void printScheduleGraph(String path, Vector<ScheduleNode> sNodes) {
  83         try {
  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");
  91             output.close();
  92         } catch (Exception e) {
  93             e.printStackTrace();
  94             System.exit(-1);
  95         }
  96     }
  97
  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();
 112                 output.print("\t");
 113                 if(se.getSourceCNode().isclone()) {
 114                     output.print(se.getSourceCNode().getLabel());
 115                 } else {
 116                     if(se.getSourceFState() == null) {
 117                         output.print(se.getSourceCNode().getClusterLabel());
 118                     } else {
 119                         output.print(se.getSourceFState().getLabel());
 120                     }
 121                 }
 122
 123                 output.print(" -> ");
 124                 if(se.isclone()) {
 125                     if(se.getTargetCNode().isclone()) {
 126                         output.print(se.getTargetCNode().getLabel());
 127                     } else {
 128                         output.print(se.getTargetCNode().getClusterLabel());
 129                     }
 130                     output.println(" [label=\"" + se.getLabel() + "\", color=red];");
 131                 } else {
 132                     output.print(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail=");
 133                     if(se.getSourceCNode().isclone()) {
 134                         output.println(se.getSourceCNode().getLabel() + "];");
 135                     } else {
 136                         output.println(se.getSourceCNode().getClusterLabel() + "];");
 137                     }
 138                 }
 139             }
 140             output.println("\t}\n");
 141             //Draw 'new' edges of this ScheduleNode
 142             while(edges.hasNext()) {
 143                 ScheduleEdge se = (ScheduleEdge)edges.next();
 144                 output.print("\t");
 145                 if(se.getSourceCNode().isclone()) {
 146                     output.print(se.getSourceCNode().getLabel());
 147                 } else {
 148                     if(se.getSourceFState() == null) {
 149                         output.print(se.getSourceCNode().getClusterLabel());
 150                     } else {
 151                         output.print(se.getSourceFState().getLabel());
 152                     }
 153                 }
 154
 155                 output.print(" -> ");
 156                 if(se.isclone()) {
 157                     if(se.getTargetCNode().isclone()) {
 158                         output.print(se.getTargetCNode().getLabel());
 159                     } else {
 160                         output.print(se.getTargetCNode().getClusterLabel());
 161                     }
 162                     output.println(" [label=\"" + se.getLabel() + "\", color=red, style=dashed];");
 163                 } else {
 164                     output.println(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed];");
 165                 }
 166             }
 167         }
 168     }
 169
 170     private static void traverseCNodes(PrintWriter output, Iterator it){
 171         //Draw clusters representing ClassNodes
 172         while (it.hasNext()) {
 173             ClassNode gn = (ClassNode) it.next();
 174             if(gn.isclone()) {
 175                 output.println("\t\t" + gn.getLabel() + " [style=dashed, label=\"" + gn.getTextLabel() + "\", shape=box];");
 176             } else {
 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");
 182             }
 183         }
 184     }
 185
 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());
 191
 192         Iterator it = nodes.iterator();
 193         while (it.hasNext()) {
 194             GraphNode gn = (GraphNode) it.next();
 195             Iterator edges = gn.edges();
 196             String label = "";
 197             String dotnodeparams="";
 198
 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);
 203
 204                 if (!newlabel.equals("") && !label.equals("")) {
 205                     label+=", ";
 206                 }
 207                 if (!newparams.equals("")) {
 208                     dotnodeparams+=", " + name.nodeOption(gn);
 209                 }
 210                 label+=name.nodeLabel(gn);
 211             }
 212             label += ":[" + ((FlagState)gn).getExeTime() + "]";
 213
 214             if (!gn.merge)
 215                 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
 216
 217             if (!gn.merge)
 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="";
 226
 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(""))
 232                                     edgelabel+=", ";
 233                                 edgelabel+=newlabel;
 234                                 if (!newoption.equals(""))
 235                                     edgedotnodeparams+=", "+newoption;
 236                             }
 237                             edgelabel+=":[" + ((FEdge)edge).getExeTime() + "]";
 238                             edgelabel+=":(" + ((FEdge)edge).getProbability() + "%)";
 239                             Hashtable<ClassDescriptor, NewObjInfo> hashtable = ((FEdge)edge).getNewObjInfoHashtable();
 240                             if(hashtable != null) {
 241                                 Set<ClassDescriptor> keys = hashtable.keySet();
 242                                 Iterator it_keys = keys.iterator();
 243                                 while(it_keys.hasNext()) {
 244                                     ClassDescriptor cd = (ClassDescriptor)it_keys.next();
 245                                     NewObjInfo noi = hashtable.get(cd);
 246                                     edgelabel += ":{ class " + cd.getSymbol() + " | " + noi.getNewRate() + " | (" + noi.getProbability() + "%) }";
 247                                 }
 248                             }
 249                             output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
 250                         }
 251                     }
 252                 }
 253         }
 254     }
 255
 256     private static Set nonmerge(GraphNode gn, Collection nodes) {
 257         HashSet newset=new HashSet();
 258         HashSet toprocess=new HashSet();
 259         toprocess.add(gn);
 260         while(!toprocess.isEmpty()) {
 261             GraphNode gn2=(GraphNode)toprocess.iterator().next();
 262             toprocess.remove(gn2);
 263             if (!gn2.merge)
 264                 newset.add(gn2);
 265             else {
 266                 Iterator edges = gn2.edges();
 267                 while (edges.hasNext()) {
 268                     Edge edge = (Edge) edges.next();
 269                     GraphNode node = edge.getTarget();
 270                     if (!newset.contains(node)&&nodes.contains(node))
 271                         toprocess.add(node);
 272                 }
 273             }
 274         }
 275         return newset;
 276     }
 277
 278     public static void printSimulationResult(String path, int time, int coreNum, Vector<CheckPoint> checkpoints) {
 279         try {
 280             File file=new File(path);
 281             FileOutputStream dotstream=new FileOutputStream(file,false);
 282             PrintWriter output = new java.io.PrintWriter(dotstream, true);
 283             output.println("digraph simulation{");
 284             output.print("\t");
 285             output.println("node [shape=plaintext];");
 286             output.print("\t");
 287             output.println("edge [dir=none];");
 288             output.print("\t");
 289             output.println("ranksep=.05;");
 290             output.println();
 291             output.print("\t");
 292             int j = 0;
 293
 294             // the capital line
 295             output.print("{rank=source; \"Time\"; ");
 296             for(j = 0; j < coreNum; j++) {
 297                 output.print("\"core " + j + "\"; ");
 298             }
 299             output.println("}");
 300             // time coordinate nodes
 301             Vector<String> timeNodes = new Vector<String>();
 302             String[] lastTaskNodes = new String[coreNum];
 303             String[] lastTasks = new String[coreNum];
 304             boolean[] isTaskFinish = new boolean[coreNum];
 305             for(j = 0; j < coreNum; j++) {
 306                 lastTaskNodes[j] = "first";
 307                 isTaskFinish[j] = true;
 308                 lastTasks[j] = "";
 309             }
 310             timeNodes.add("0");
 311             for(j = 0; j < checkpoints.size(); j++) {
 312                 CheckPoint tcp = checkpoints.elementAt(j);
 313                 Hashtable<Integer, String> tmplastTasks = new Hashtable<Integer, String>();
 314                 Vector<Integer> tmpisTaskFinish = new Vector<Integer>();
 315                 Vector<Integer> tmpisset = new Vector<Integer>();
 316                 String tnode = String.valueOf(tcp.getTimepoint());
 317                 if(!timeNodes.contains(tnode)) {
 318                     timeNodes.add(tnode);
 319                 }
 320                 Vector<Action> actions = tcp.getActions();
 321                 Hashtable<String, StringBuffer> tmpTaskNodes = new Hashtable<String, StringBuffer>();
 322                 for(int i = 0; i < actions.size(); i++) {
 323                     Action taction = actions.elementAt(i);
 324                     int cNum = taction.getCoreNum();
 325                     if(!tmplastTasks.contains(cNum)) {
 326                         tmplastTasks.put(cNum, lastTasks[cNum]);
 327                     }
 328                     if(!(tmpisset.contains(cNum)) && (isTaskFinish[cNum]) && !(tmpisTaskFinish.contains(cNum))) {
 329                         tmpisTaskFinish.add(cNum); // records those with task finished the first time visit it
 330                     }
 331                     String tmpTaskNode = "\"" + tnode + "core" + cNum + "\"";
 332                     StringBuffer tmpLabel = null;
 333                     boolean isfirst = false;
 334                     if(!tmpTaskNodes.containsKey(tmpTaskNode)) {
 335                         tmpTaskNodes.put(tmpTaskNode, new StringBuffer(tnode + ":"));
 336                         isfirst = true;
 337                     }
 338                     tmpLabel = tmpTaskNodes.get(tmpTaskNode);
 339                     switch(taction.getType()){
 340                     case Action.ADDOBJ: {
 341                         if(!isfirst) {
 342                             tmpLabel.append("\\n");
 343                         }
 344                         tmpLabel.append("(" + taction.getTransObj().getSymbol() + ")arrives;");
 345                         if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 346                             output.print("\t");
 347                             if(lastTaskNodes[cNum].equals("first")) {
 348                                 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
 349                             } else {
 350                                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 351                             }
 352                             if(tmpisTaskFinish.contains(cNum)) {
 353                                 output.print(" [style=invis]");
 354                             }
 355                             output.println(";");
 356                             lastTaskNodes[cNum] = tmpTaskNode;
 357                         }
 358                         break;
 359                     }
 360                     case Action.TASKFINISH: {
 361                         if(!isfirst) {
 362                             tmpLabel.append("\\n");
 363                         }
 364                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes;");
 365                         if(!(lastTaskNodes[cNum].equals("first"))) {
 366                             if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 367                                 output.print("\t");
 368                                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 369                                 lastTaskNodes[cNum] = tmpTaskNode;
 370                             }
 371                             if(tmpisset.contains(cNum)) {
 372                                 isTaskFinish[cNum] &= true;
 373                             } else {
 374                                 isTaskFinish[cNum] = true;
 375                                 tmpisset.add(cNum);
 376                             }
 377                             lastTasks[cNum] = "";
 378                         } else {
 379                             throw new Exception("Error: unexpected task finish");
 380                         }
 381                         break;
 382                     }
 383                     case Action.TFWITHOBJ: {
 384                         if(!isfirst) {
 385                             tmpLabel.append("\\n");
 386                         }
 387                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes; ");
 388                         Iterator<Entry<ClassDescriptor, Integer>> it_entry = (Iterator<Entry<ClassDescriptor, Integer>>)taction.getNObjs().entrySet().iterator();
 389                         while(it_entry.hasNext()) {
 390                             Entry<ClassDescriptor, Integer> entry = it_entry.next();
 391                             tmpLabel.append(entry.getValue() + "(" + entry.getKey().getSymbol() + ")");
 392                             if(it_entry.hasNext()) {
 393                                 tmpLabel.append(",");
 394                             } else {
 395                                 tmpLabel.append(";");
 396                             }
 397                         }
 398                         if(!(lastTaskNodes[cNum].equals("first"))) {
 399                             if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 400                                 output.print("\t");
 401                                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 402                                 lastTaskNodes[cNum] = tmpTaskNode;
 403                             }
 404                             if(tmpisset.contains(cNum)) {
 405                                 isTaskFinish[cNum] &= true;
 406                             } else {
 407                                 isTaskFinish[cNum] = true;
 408                                 tmpisset.add(cNum);
 409                             }
 410                             lastTasks[cNum] = "";
 411                         } else {
 412                             throw new Exception("Error: unexpected task finish");
 413                         }
 414                         break;
 415                     }
 416                     case Action.TASKSTART: {
 417                         if(!isfirst) {
 418                             tmpLabel.append("\\n");
 419                         }
 420                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">starts;");
 421                         lastTasks[cNum] = taction.getTd().getSymbol();
 422
 423                         if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 424                             output.print("\t");
 425                             if(lastTaskNodes[cNum].equals("first")) {
 426                                 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
 427                             } else {
 428                                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 429                             }
 430                             if(tmpisTaskFinish.contains(cNum)) {
 431                                 output.print(" [style=invis]");
 432                             }
 433                             output.println(";");
 434                             lastTaskNodes[cNum] = tmpTaskNode;
 435                         }
 436                         isTaskFinish[cNum] &= false;
 437                         break;
 438                     }
 439                     case Action.TASKABORT: {
 440                         if(!isfirst) {
 441                             tmpLabel.append("\\n");
 442                         }
 443                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">aborts;");
 444                         if(!(lastTaskNodes[cNum].equals("first")) &&
 445                                 (tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) {
 446                             if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 447                                 output.print("\t");
 448                                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 449                                 lastTaskNodes[cNum] = tmpTaskNode;
 450                             }
 451                             if(tmpisset.contains(cNum)) {
 452                                 isTaskFinish[cNum] &= true;
 453                             } else {
 454                                 isTaskFinish[cNum] = true;
 455                                 tmpisset.add(cNum);
 456                             }
 457                             lastTasks[cNum] = "";
 458                         } else {
 459                             throw new Exception("Error: unexpected task aborts");
 460                         }
 461                         break;
 462                     }
 463                     case Action.TASKREMOVE: {
 464                         if(!isfirst) {
 465                             tmpLabel.append("\\n");
 466                         }
 467                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">removes;");
 468                         if(!(lastTaskNodes[cNum].equals("first")) &&
 469                                 (tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) {
 470                             if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 471                                 output.print("\t");
 472                                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 473                                 lastTaskNodes[cNum] = tmpTaskNode;
 474                             }
 475                             if(tmpisset.contains(cNum)) {
 476                                 isTaskFinish[cNum] &= true;
 477                             } else {
 478                                 isTaskFinish[cNum] = true;
 479                                 tmpisset.add(cNum);
 480                             }
 481                             lastTasks[cNum] = "";
 482                         } else {
 483                             throw new Exception("Error: unexpected task remove");
 484                         }
 485                         break;
 486                     }
 487                     }
 488                 }
 489                 Enumeration<String> keys = tmpTaskNodes.keys();
 490                 while(keys.hasMoreElements()) {
 491                     String tmpTaskNode = keys.nextElement();
 492                     output.print("\t");
 493                     output.println(tmpTaskNode + "[label=\"" + tmpTaskNodes.get(tmpTaskNode).toString() + "\"]");
 494                 }
 495                 output.print("\t");
 496                 output.print("{rank=same; rankdir=LR; " + tnode + "; ");
 497                 keys = tmpTaskNodes.keys();
 498                 while(keys.hasMoreElements()) {
 499                     String tmpTaskNode = keys.nextElement();
 500                     output.print(tmpTaskNode);
 501                     output.print("; ");
 502                 }
 503                 output.println("}");
 504                 output.print("\t");
 505             }
 506             output.print("\t");
 507             output.print("\t");
 508             output.println("\"Time\"->" + timeNodes.elementAt(0) + "[style=invis];");
 509             for(j = 0; j < time; j++) {
 510                 output.print(j + "->");
 511             }
 512             output.println(timeNodes.lastElement() + ";");
 513             output.println("}");
 514             output.close();
 515         } catch (Exception e) {
 516             e.printStackTrace();
 517             System.exit(-1);
 518         }
 519     }
 520 }