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.getTargetFState() == null) {
 125                 if(se.isclone()) {
 126                     if(se.getTargetCNode().isclone()) {
 127                         output.print(se.getTargetCNode().getLabel());
 128                     } else {
 129                         output.print(se.getTargetCNode().getClusterLabel());
 130                     }
 131                     output.println(" [label=\"" + se.getLabel() + "\", color=red];");
 132                 } else {
 133                     output.print(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail=");
 134                     if(se.getSourceCNode().isclone()) {
 135                         output.println(se.getSourceCNode().getLabel() + "];");
 136                     } else {
 137                         output.println(se.getSourceCNode().getClusterLabel() + "];");
 138                     }
 139                 }
 140             }
 141             output.println("\t}\n");
 142             //Draw 'new' edges of this ScheduleNode
 143             while(edges.hasNext()) {
 144                 ScheduleEdge se = (ScheduleEdge)edges.next();
 145                 output.print("\t");
 146                 if(se.getSourceCNode().isclone()) {
 147                     output.print(se.getSourceCNode().getLabel());
 148                 } else {
 149                     if(se.getSourceFState() == null) {
 150                         output.print(se.getSourceCNode().getClusterLabel());
 151                     } else {
 152                         output.print(se.getSourceFState().getLabel());
 153                     }
 154                 }
 155
 156                 output.print(" -> ");
 157                 //if(se.getTargetFState() == null) {
 158                 if(se.isclone()) {
 159                     if(se.getTargetCNode().isclone()) {
 160                         output.print(se.getTargetCNode().getLabel());
 161                     } else {
 162                         output.print(se.getTargetCNode().getClusterLabel());
 163                     }
 164                     output.println(" [label=\"" + se.getLabel() + "\", color=red, style=dashed]");
 165                 } else {
 166                     output.println(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed]");
 167                 }
 168             }
 169         }
 170     }
 171
 172     private static void traverseCNodes(PrintWriter output, Iterator it){
 173         //Draw clusters representing ClassNodes
 174         while (it.hasNext()) {
 175             ClassNode gn = (ClassNode) it.next();
 176             if(gn.isclone()) {
 177                 output.println("\t\t" + gn.getLabel() + " [style=dashed, label=\"" + gn.getTextLabel() + "\", shape=box];");
 178             } else {
 179                 output.println("\tsubgraph " + gn.getClusterLabel() + "{");
 180                 output.println("\t\tstyle=dashed;");
 181                 output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
 182                 traverseFlagStates(output, gn.getFlagStates());
 183                 output.println("\t}\n");
 184             }
 185         }
 186     }
 187
 188     private static void traverseFlagStates(PrintWriter output, Collection nodes) {
 189         Set cycleset=GraphNode.findcycles(nodes);
 190         Vector namers=new Vector();
 191         namers.add(new Namer());
 192         namers.add(new Allocations());
 193         //namers.add(new TaskEdges());
 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                             Hashtable<ClassDescriptor, NewObjInfo> hashtable = ((FEdge)edge).getNewObjInfoHashtable();
 242                             if(hashtable != null) {
 243                                 Set<ClassDescriptor> keys = hashtable.keySet();
 244                                 Iterator it_keys = keys.iterator();
 245                                 while(it_keys.hasNext()) {
 246                                     ClassDescriptor cd = (ClassDescriptor)it_keys.next();
 247                                     NewObjInfo noi = hashtable.get(cd);
 248                                     edgelabel += ":{ class " + cd.getSymbol() + " | " + noi.getNewRate() + " | (" + noi.getProbability() + "%) }";
 249                                 }
 250                             }
 251                             output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
 252                         }
 253                     }
 254                 }
 255         }
 256     }
 257
 258     private static Set nonmerge(GraphNode gn, Collection nodes) {
 259         HashSet newset=new HashSet();
 260         HashSet toprocess=new HashSet();
 261         toprocess.add(gn);
 262         while(!toprocess.isEmpty()) {
 263             GraphNode gn2=(GraphNode)toprocess.iterator().next();
 264             toprocess.remove(gn2);
 265             if (!gn2.merge)
 266                 newset.add(gn2);
 267             else {
 268                 Iterator edges = gn2.edges();
 269                 while (edges.hasNext()) {
 270                     Edge edge = (Edge) edges.next();
 271                     GraphNode node = edge.getTarget();
 272                     if (!newset.contains(node)&&nodes.contains(node))
 273                         toprocess.add(node);
 274                 }
 275             }
 276         }
 277         return newset;
 278     }
 279
 280     public static void printSimulationResult(String path, int time, int coreNum, Vector<CheckPoint> checkpoints) {
 281         try {
 282             File file=new File(path);
 283             FileOutputStream dotstream=new FileOutputStream(file,false);
 284             PrintWriter output = new java.io.PrintWriter(dotstream, true);
 285             output.println("digraph simulation{");
 286             output.print("\t");
 287             output.println("node [shape=plaintext];");
 288             output.print("\t");
 289             output.println("edge [dir=none];");
 290             output.print("\t");
 291             output.println("ranksep=.05;");
 292             output.println();
 293             output.print("\t");
 294             int j = 0;
 295
 296             // the capital line
 297             output.print("{rank=source; \"Time\"; ");
 298             for(j = 0; j < coreNum; j++) {
 299                 output.print("\"core " + j + "\"; ");
 300             }
 301             output.println("}");
 302             // time coordinate nodes
 303             Vector<String> timeNodes = new Vector<String>();
 304             String[] lastTaskNodes = new String[coreNum];
 305             boolean[] isTaskFinish = new boolean[coreNum];
 306             for(j = 0; j < coreNum; j++) {
 307                 lastTaskNodes[j] = "first";
 308                 isTaskFinish[j] = true;
 309             }
 310             timeNodes.add("0");
 311             for(j = 0; j < checkpoints.size(); j++) {
 312                 CheckPoint tcp = checkpoints.elementAt(j);
 313                 String tnode = String.valueOf(tcp.getTimepoint());
 314                 if(!timeNodes.contains(tnode)) {
 315                     timeNodes.add(tnode);
 316                 }
 317                 Vector<Action> actions = tcp.getActions();
 318                 Hashtable<String, StringBuffer> tmpTaskNodes = new Hashtable<String, StringBuffer>();
 319                 //Vector<String> sortedttnodes = new Vector<String>();
 320                 for(int i = 0; i < actions.size(); i++) {
 321                     Action taction = actions.elementAt(i);
 322                     int cNum = taction.getCoreNum();
 323                     String tmpTaskNode = "\"" + tnode + "core" + cNum + "\"";
 324                     StringBuffer tmpLabel = null;
 325                     boolean isfirst = false;
 326                     if(!tmpTaskNodes.containsKey(tmpTaskNode)) {
 327                         tmpTaskNodes.put(tmpTaskNode, new StringBuffer(tnode + ":"));
 328                         isfirst = true;
 329                         /*int length = sortedttnodes.size();
 330                         int k = length;
 331                         for(; k > 0; k--) {
 332                             String tmptnode = sortedttnodes.elementAt(k-1);
 333                             int tcorenum = Integer.parseInt(tmptnode.substring(tmptnode.indexOf("core") + 4, tmptnode.length() - 1));
 334                             if(tcorenum < cNum) {
 335                                 break;
 336                             }
 337                         }
 338                         sortedttnodes.add(k, tmpTaskNode);*/
 339                     }
 340                     tmpLabel = tmpTaskNodes.get(tmpTaskNode);
 341                     switch(taction.getType()){
 342                     case Action.ADDOBJ: {
 343                         if(!isfirst) {
 344                             tmpLabel.append("\\n");
 345                         }
 346                         tmpLabel.append("(" + taction.getTransObj().getSymbol() + ")arrives;");
 347                         if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 348                             output.print("\t");
 349                             if(lastTaskNodes[cNum].equals("first")) {
 350                                 output.println("\"core " + cNum + "\"->" + tmpTaskNode);
 351                             } else {
 352                                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 353                             }
 354                             if(isTaskFinish[cNum]) {
 355                                 output.print(" [style=invis]");
 356                             }
 357                             output.println(";");
 358                             lastTaskNodes[cNum] = tmpTaskNode;
 359                         }
 360                         break;
 361                     }
 362                     case Action.TASKFINISH: {
 363                         if(!isfirst) {
 364                             tmpLabel.append("\\n");
 365                         }
 366                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes;");
 367                         if(!(lastTaskNodes[cNum].equals("first")) &&
 368                                 !(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 369                             output.print("\t");
 370                             output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 371                             lastTaskNodes[cNum] = tmpTaskNode;
 372                             isTaskFinish[cNum] = true;
 373                         } else {
 374                             throw new Exception("Error: unexpected task finish");
 375                         }
 376                         break;
 377                     }
 378                     case Action.TFWITHOBJ: {
 379                         if(!isfirst) {
 380                             tmpLabel.append("\\n");
 381                         }
 382                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes; ");
 383                         Iterator<Entry<ClassDescriptor, Integer>> it_entry = (Iterator<Entry<ClassDescriptor, Integer>>)taction.getNObjs().entrySet().iterator();
 384                         while(it_entry.hasNext()) {
 385                             Entry<ClassDescriptor, Integer> entry = it_entry.next();
 386                             tmpLabel.append(entry.getValue() + "(" + entry.getKey().getSymbol() + ")");
 387                             if(it_entry.hasNext()) {
 388                                 tmpLabel.append(",");
 389                             } else {
 390                                 tmpLabel.append(";");
 391                             }
 392                         }
 393                         if(!(lastTaskNodes[cNum].equals("first")) &&
 394                                 !(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 395                             output.print("\t");
 396                             output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 397                             lastTaskNodes[cNum] = tmpTaskNode;
 398                             isTaskFinish[cNum] = true;
 399                         } else {
 400                             throw new Exception("Error: unexpected task finish");
 401                         }
 402                         break;
 403                     }
 404                     case Action.TASKSTART: {
 405                         if(!isfirst) {
 406                             tmpLabel.append("\\n");
 407                         }
 408                         tmpLabel.append("<" + taction.getTd().getSymbol() + ">starts;");
 409
 410                         if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 411                             output.print("\t");
 412                             if(lastTaskNodes[cNum].equals("first")) {
 413                                 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
 414                             } else {
 415                                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 416                             }
 417                             if(isTaskFinish[cNum]) {
 418                                 output.print(" [style=invis]");
 419                             }
 420                             output.println(";");
 421                             lastTaskNodes[cNum] = tmpTaskNode;
 422                         }
 423                         isTaskFinish[cNum] = false;
 424                         break;
 425                     }
 426                     }
 427                 }
 428                 Enumeration<String> keys = tmpTaskNodes.keys();
 429                 while(keys.hasMoreElements()) {
 430                     String tmpTaskNode = keys.nextElement();
 431                     output.print("\t");
 432                     output.println(tmpTaskNode + "[label=\"" + tmpTaskNodes.get(tmpTaskNode).toString() + "\"]");
 433                 }
 434                 output.print("\t");
 435                 output.print("{rank=same; rankdir=LR; " + tnode + "; ");
 436                 /*for(int k = 0; k < sortedttnodes.size(); k++) {
 437                     output.print(sortedttnodes.elementAt(k));
 438                     output.print("; ");
 439                 }*/
 440                 keys = tmpTaskNodes.keys();
 441                 while(keys.hasMoreElements()) {
 442                     String tmpTaskNode = keys.nextElement();
 443                     output.print(tmpTaskNode);
 444                     output.print("; ");
 445                 }
 446                 output.println("}");
 447                 output.print("\t");
 448                 /*output.print(tnode + "->");
 449                 for(int k = 0; k < sortedttnodes.size() - 1; k++) {
 450                     output.print(sortedttnodes.elementAt(k) + "->");
 451                 }
 452                 output.println(sortedttnodes.lastElement() + " [style=dashed];");*/
 453             }
 454             output.print("\t");
 455             //output.println("node [shape=point, color=blue];");
 456             output.print("\t");
 457             output.println("\"Time\"->" + timeNodes.elementAt(0) + "[style=invis];");
 458             //for(j = 0; j < timeNodes.size() - 1; j++) {
 459             for(j = 0; j < time; j++) {
 460                 output.print(j + "->");
 461             }
 462             output.println(timeNodes.lastElement() + ";");
 463             output.println("}");
 464             output.close();
 465         } catch (Exception e) {
 466             e.printStackTrace();
 467             System.exit(-1);
 468         }
 469     }
 470 }