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             boolean[] isTaskFinish = new boolean[coreNum];
 303             for(j = 0; j < coreNum; j++) {
 304                 lastTaskNodes[j] = "first";
 305                 isTaskFinish[j] = true;
 306             }
 307             timeNodes.add("0");
 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);
 313                 }
 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 + ":"));
 324                         isfirst = true;
 325                     }
 326                     tmpLabel = tmpTaskNodes.get(tmpTaskNode);
 327                     switch(taction.getType()){
 328                     case Action.ADDOBJ: {
 329                         if(!isfirst) {
 330                             tmpLabel.append("\\n");
 331                         }
 332                         tmpLabel.append("(" + taction.getTransObj().getSymbol() + ")arrives;");
 333                         if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 334                             output.print("\t");
 335                             if(lastTaskNodes[cNum].equals("first")) {
 336                                 output.println("\"core " + cNum + "\"->" + tmpTaskNode);
 337                             } else {
 338                                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 339                             }
 340                             if(isTaskFinish[cNum]) {
 341                                 output.print(" [style=invis]");
 342                             }
 343                             output.println(";");
 344                             lastTaskNodes[cNum] = tmpTaskNode;
 345                         }
 346                         break;
 347                     }
 348                     case Action.TASKFINISH: {
 349                         if(!isfirst) {
 350                             tmpLabel.append("\\n");
 351                         }
 352                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes;");
 353                         if(!(lastTaskNodes[cNum].equals("first"))) {
 354                             if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 355                                 output.print("\t");
 356                                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 357                                 lastTaskNodes[cNum] = tmpTaskNode;
 358                             }
 359                             isTaskFinish[cNum] = true;
 360                         } else {
 361                             throw new Exception("Error: unexpected task finish");
 362                         }
 363                         break;
 364                     }
 365                     case Action.TFWITHOBJ: {
 366                         if(!isfirst) {
 367                             tmpLabel.append("\\n");
 368                         }
 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(",");
 376                             } else {
 377                                 tmpLabel.append(";");
 378                             }
 379                         }
 380                         if(!(lastTaskNodes[cNum].equals("first")) &&
 381                                 !(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 382                             output.print("\t");
 383                             output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 384                             lastTaskNodes[cNum] = tmpTaskNode;
 385                             isTaskFinish[cNum] = true;
 386                         } else {
 387                             throw new Exception("Error: unexpected task finish");
 388                         }
 389                         break;
 390                     }
 391                     case Action.TASKSTART: {
 392                         if(!isfirst) {
 393                             tmpLabel.append("\\n");
 394                         }
 395                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">starts;");
 396
 397                         if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 398                             output.print("\t");
 399                             if(lastTaskNodes[cNum].equals("first")) {
 400                                 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
 401                             } else {
 402                                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 403                             }
 404                             if(isTaskFinish[cNum]) {
 405                                 output.print(" [style=invis]");
 406                             }
 407                             output.println(";");
 408                             lastTaskNodes[cNum] = tmpTaskNode;
 409                         }
 410                         isTaskFinish[cNum] = false;
 411                         break;
 412                     }
 413                     case Action.TASKABORT: {
 414                         if(!isfirst) {
 415                             tmpLabel.append("\\n");
 416                         }
 417                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">aborts;");
 418                         if(!(lastTaskNodes[cNum].equals("first")) &&
 419                                 !(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 420                             output.print("\t");
 421                             output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 422                             lastTaskNodes[cNum] = tmpTaskNode;
 423                             isTaskFinish[cNum] = true;
 424                         } else {
 425                             throw new Exception("Error: unexpected task aborts");
 426                         }
 427                         break;
 428                     }
 429                     case Action.TASKREMOVE: {
 430                         if(!isfirst) {
 431                             tmpLabel.append("\\n");
 432                         }
 433                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">removes;");
 434                         if(!(lastTaskNodes[cNum].equals("first")) &&
 435                                 !(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 436                             output.print("\t");
 437                             output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 438                             lastTaskNodes[cNum] = tmpTaskNode;
 439                             isTaskFinish[cNum] = true;
 440                         } else {
 441                             throw new Exception("Error: unexpected task remove");
 442                         }
 443                         break;
 444                     }
 445                     }
 446                 }
 447                 Enumeration<String> keys = tmpTaskNodes.keys();
 448                 while(keys.hasMoreElements()) {
 449                     String tmpTaskNode = keys.nextElement();
 450                     output.print("\t");
 451                     output.println(tmpTaskNode + "[label=\"" + tmpTaskNodes.get(tmpTaskNode).toString() + "\"]");
 452                 }
 453                 output.print("\t");
 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);
 459                     output.print("; ");
 460                 }
 461                 output.println("}");
 462                 output.print("\t");
 463             }
 464             output.print("\t");
 465             output.print("\t");
 466             output.println("\"Time\"->" + timeNodes.elementAt(0) + "[style=invis];");
 467             for(j = 0; j < time; j++) {
 468                 output.print(j + "->");
 469             }
 470             output.println(timeNodes.lastElement() + ";");
 471             output.println("}");
 472             output.close();
 473         } catch (Exception e) {
 474             e.printStackTrace();
 475             System.exit(-1);
 476         }
 477     }
 478 }