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                             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() + "%) }";
 246                                 }
 247                             }
 248                             output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
 249                         }
 250                     }
 251                 }
 252         }
 253     }
 254
 255     private static Set nonmerge(GraphNode gn, Collection nodes) {
 256         HashSet newset=new HashSet();
 257         HashSet toprocess=new HashSet();
 258         toprocess.add(gn);
 259         while(!toprocess.isEmpty()) {
 260             GraphNode gn2=(GraphNode)toprocess.iterator().next();
 261             toprocess.remove(gn2);
 262             if (!gn2.merge)
 263                 newset.add(gn2);
 264             else {
 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))
 270                         toprocess.add(node);
 271                 }
 272             }
 273         }
 274         return newset;
 275     }
 276
 277     public static void printSimulationResult(String path, int time, int coreNum, Vector<CheckPoint> checkpoints) {
 278         try {
 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{");
 283             output.print("\t");
 284             output.println("node [shape=plaintext];");
 285             output.print("\t");
 286             output.println("edge [dir=none];");
 287             output.print("\t");
 288             output.println("ranksep=.05;");
 289             output.println();
 290             output.print("\t");
 291             int j = 0;
 292
 293             // the capital line
 294             output.print("{rank=source; \"Time\"; ");
 295             for(j = 0; j < coreNum; j++) {
 296                 output.print("\"core " + j + "\"; ");
 297             }
 298             output.println("}");
 299             // time coordinate nodes
 300             Vector<String> timeNodes = new Vector<String>();
 301             String[] lastTaskNodes = new String[coreNum];
 302             String[] lastTasks = new String[coreNum];
 303             boolean[] isTaskFinish = new boolean[coreNum];
 304             for(j = 0; j < coreNum; j++) {
 305                 lastTaskNodes[j] = "first";
 306                 isTaskFinish[j] = true;
 307                 lastTasks[j] = "";
 308             }
 309             timeNodes.add("0");
 310             for(j = 0; j < checkpoints.size(); j++) {
 311                 CheckPoint tcp = checkpoints.elementAt(j);
 312                 Hashtable<Integer, String> tmplastTasks = new Hashtable<Integer, String>();
 313                 Vector<Integer> tmpisTaskFinish = new Vector<Integer>();
 314                 Vector<Integer> tmpisset = new Vector<Integer>();
 315                 String tnode = String.valueOf(tcp.getTimepoint());
 316                 if(!timeNodes.contains(tnode)) {
 317                     timeNodes.add(tnode);
 318                 }
 319                 Vector<Action> actions = tcp.getActions();
 320                 Hashtable<String, StringBuffer> tmpTaskNodes = new Hashtable<String, StringBuffer>();
 321                 for(int i = 0; i < actions.size(); i++) {
 322                     Action taction = actions.elementAt(i);
 323                     int cNum = taction.getCoreNum();
 324                     if(!tmplastTasks.contains(cNum)) {
 325                         tmplastTasks.put(cNum, lastTasks[cNum]);
 326                     }
 327                     if(!(tmpisset.contains(cNum)) && (isTaskFinish[cNum]) && !(tmpisTaskFinish.contains(cNum))) {
 328                         tmpisTaskFinish.add(cNum); // records those with task finished the first time visit it
 329                     }
 330                     String tmpTaskNode = "\"" + tnode + "core" + cNum + "\"";
 331                     StringBuffer tmpLabel = null;
 332                     boolean isfirst = false;
 333                     if(!tmpTaskNodes.containsKey(tmpTaskNode)) {
 334                         tmpTaskNodes.put(tmpTaskNode, new StringBuffer(tnode + ":"));
 335                         isfirst = true;
 336                     }
 337                     tmpLabel = tmpTaskNodes.get(tmpTaskNode);
 338                     switch(taction.getType()){
 339                     case Action.ADDOBJ: {
 340                         if(!isfirst) {
 341                             tmpLabel.append("\\n");
 342                         }
 343                         tmpLabel.append("(" + taction.getTransObj().getSymbol() + ")arrives;");
 344                         if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 345                             output.print("\t");
 346                             if(lastTaskNodes[cNum].equals("first")) {
 347                                 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
 348                             } else {
 349                                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 350                             }
 351                             if(tmpisTaskFinish.contains(cNum)) {
 352                                 output.print(" [style=invis]");
 353                             }
 354                             output.println(";");
 355                             lastTaskNodes[cNum] = tmpTaskNode;
 356                         }
 357                         break;
 358                     }
 359                     case Action.TASKFINISH: {
 360                         if(!isfirst) {
 361                             tmpLabel.append("\\n");
 362                         }
 363                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes;");
 364                         if(!(lastTaskNodes[cNum].equals("first"))) {
 365                             if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 366                                 output.print("\t");
 367                                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 368                                 lastTaskNodes[cNum] = tmpTaskNode;
 369                             }
 370                             if(tmpisset.contains(cNum)) {
 371                                 isTaskFinish[cNum] &= true;
 372                             } else {
 373                                 isTaskFinish[cNum] = true;
 374                                 tmpisset.add(cNum);
 375                             }
 376                             lastTasks[cNum] = "";
 377                         } else {
 378                             throw new Exception("Error: unexpected task finish");
 379                         }
 380                         break;
 381                     }
 382                     case Action.TFWITHOBJ: {
 383                         if(!isfirst) {
 384                             tmpLabel.append("\\n");
 385                         }
 386                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes; ");
 387                         Iterator<Entry<ClassDescriptor, Integer>> it_entry = (Iterator<Entry<ClassDescriptor, Integer>>)taction.getNObjs().entrySet().iterator();
 388                         while(it_entry.hasNext()) {
 389                             Entry<ClassDescriptor, Integer> entry = it_entry.next();
 390                             tmpLabel.append(entry.getValue() + "(" + entry.getKey().getSymbol() + ")");
 391                             if(it_entry.hasNext()) {
 392                                 tmpLabel.append(",");
 393                             } else {
 394                                 tmpLabel.append(";");
 395                             }
 396                         }
 397                         if(!(lastTaskNodes[cNum].equals("first"))) {
 398                             if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 399                                 output.print("\t");
 400                                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 401                                 lastTaskNodes[cNum] = tmpTaskNode;
 402                             }
 403                             if(tmpisset.contains(cNum)) {
 404                                 isTaskFinish[cNum] &= true;
 405                             } else {
 406                                 isTaskFinish[cNum] = true;
 407                                 tmpisset.add(cNum);
 408                             }
 409                             lastTasks[cNum] = "";
 410                         } else {
 411                             throw new Exception("Error: unexpected task finish");
 412                         }
 413                         break;
 414                     }
 415                     case Action.TASKSTART: {
 416                         if(!isfirst) {
 417                             tmpLabel.append("\\n");
 418                         }
 419                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">starts;");
 420                         lastTasks[cNum] = taction.getTd().getSymbol();
 421
 422                         if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 423                             output.print("\t");
 424                             if(lastTaskNodes[cNum].equals("first")) {
 425                                 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
 426                             } else {
 427                                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 428                             }
 429                             if(tmpisTaskFinish.contains(cNum)) {
 430                                 output.print(" [style=invis]");
 431                             }
 432                             output.println(";");
 433                             lastTaskNodes[cNum] = tmpTaskNode;
 434                         }
 435                         isTaskFinish[cNum] &= false;
 436                         break;
 437                     }
 438                     case Action.TASKABORT: {
 439                         if(!isfirst) {
 440                             tmpLabel.append("\\n");
 441                         }
 442                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">aborts;");
 443                         if(!(lastTaskNodes[cNum].equals("first")) &&
 444                                 (tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) {
 445                             if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 446                                 output.print("\t");
 447                                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 448                                 lastTaskNodes[cNum] = tmpTaskNode;
 449                             }
 450                             if(tmpisset.contains(cNum)) {
 451                                 isTaskFinish[cNum] &= true;
 452                             } else {
 453                                 isTaskFinish[cNum] = true;
 454                                 tmpisset.add(cNum);
 455                             }
 456                             lastTasks[cNum] = "";
 457                         } else {
 458                             throw new Exception("Error: unexpected task aborts");
 459                         }
 460                         break;
 461                     }
 462                     case Action.TASKREMOVE: {
 463                         if(!isfirst) {
 464                             tmpLabel.append("\\n");
 465                         }
 466                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">removes;");
 467                         if(!(lastTaskNodes[cNum].equals("first")) &&
 468                                 (tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) {
 469                             if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 470                                 output.print("\t");
 471                                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 472                                 lastTaskNodes[cNum] = tmpTaskNode;
 473                             }
 474                             if(tmpisset.contains(cNum)) {
 475                                 isTaskFinish[cNum] &= true;
 476                             } else {
 477                                 isTaskFinish[cNum] = true;
 478                                 tmpisset.add(cNum);
 479                             }
 480                             lastTasks[cNum] = "";
 481                         } else {
 482                             throw new Exception("Error: unexpected task remove");
 483                         }
 484                         break;
 485                     }
 486                     }
 487                 }
 488                 Enumeration<String> keys = tmpTaskNodes.keys();
 489                 while(keys.hasMoreElements()) {
 490                     String tmpTaskNode = keys.nextElement();
 491                     output.print("\t");
 492                     output.println(tmpTaskNode + "[label=\"" + tmpTaskNodes.get(tmpTaskNode).toString() + "\"]");
 493                 }
 494                 output.print("\t");
 495                 output.print("{rank=same; rankdir=LR; " + tnode + "; ");
 496                 keys = tmpTaskNodes.keys();
 497                 while(keys.hasMoreElements()) {
 498                     String tmpTaskNode = keys.nextElement();
 499                     output.print(tmpTaskNode);
 500                     output.print("; ");
 501                 }
 502                 output.println("}");
 503                 output.print("\t");
 504             }
 505             output.print("\t");
 506             output.print("\t");
 507             output.println("\"Time\"->" + timeNodes.elementAt(0) + "[style=invis];");
 508             for(j = 0; j < time; j++) {
 509                 output.print(j + "->");
 510             }
 511             output.println(timeNodes.lastElement() + ";");
 512             output.println("}");
 513             output.close();
 514         } catch (Exception e) {
 515             e.printStackTrace();
 516             System.exit(-1);
 517         }
 518     }
 519 }