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.State;
  24 import IR.Tree.FlagExpressionNode;
  25 import IR.Tree.FlagNode;
  26 import IR.Tree.FlagOpNode;
  27 import Util.Edge;
  28 import Util.GraphNode;
  29 import Util.Namer;
  30
  31 public class SchedulingUtil {
  32
  33   public static Vector<ScheduleNode> generateScheduleGraph(State state,
  34                                                            Vector<ScheduleNode> scheduleNodes,
  35                                                            Vector<ScheduleEdge> scheduleEdges,
  36                                                            Vector<Vector<ScheduleNode>> mapping,
  37                                                            int gid) {
  38     Vector<ScheduleNode> result = new Vector<ScheduleNode>();
  39
  40     // clone the ScheduleNodes
  41     Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash =
  42       new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
  43     Hashtable<ScheduleNode, ScheduleNode> sn2sn =
  44       new Hashtable<ScheduleNode, ScheduleNode>();
  45     cloneScheduleGraph(scheduleNodes,
  46                        scheduleEdges,
  47                        sn2hash,
  48                        sn2sn,
  49                        result,
  50                        gid);
  51
  52     // combine those nodes in combine with corresponding rootnodes
  53     for(int i = 0; i < mapping.size(); i++) {
  54       Vector<ScheduleNode> sNodes = mapping.elementAt(i);
  55       if(sNodes != null) {
  56         ScheduleNode rootnode = sNodes.elementAt(0);
  57         for(int j = 1; j < sNodes.size(); j++) {
  58           ScheduleNode tocombine = sn2sn.get(sNodes.elementAt(j));
  59           ScheduleNode root = sn2sn.get(rootnode);
  60           ScheduleEdge se = (ScheduleEdge)tocombine.inedges().next();
  61           try {
  62             if(root.equals(((ScheduleNode)se.getSource()))) {
  63               root.mergeSEdge(se);
  64               if(ScheduleEdge.NEWEDGE == se.getType()) {
  65                 // As se has been changed into an internal edge inside a ScheduleNode,
  66                 // change the source and target of se from original ScheduleNodes into ClassNodes.
  67                 se.setTarget(se.getTargetCNode());
  68                 //se.setSource(se.getSourceCNode());
  69                 //se.getTargetCNode().addEdge(se);
  70                 se.getSourceCNode().addEdge(se);
  71               }
  72             } else {
  73               root.mergeSNode(tocombine);
  74             }
  75           } catch(Exception e) {
  76             e.printStackTrace();
  77             System.exit(-1);
  78           }
  79           result.removeElement(tocombine);
  80         }
  81       }
  82     }
  83
  84     assignCids(result);
  85
  86     sn2hash.clear();
  87     sn2hash = null;
  88     sn2sn.clear();
  89     sn2sn = null;
  90
  91     if(state.PRINTSCHEDULING) {
  92       String path = state.outputdir + "scheduling_" + gid + ".dot";
  93       SchedulingUtil.printScheduleGraph(path, result);
  94     }
  95
  96     return result;
  97   }
  98
  99   public static Vector<ScheduleNode> generateScheduleGraph(State state,
 100                                                            Vector<ScheduleNode> scheduleNodes,
 101                                                            Vector<ScheduleEdge> scheduleEdges,
 102                                                            Vector<Vector<ScheduleNode>> rootnodes,
 103                                                            Vector<Vector<CombinationUtil.Combine>> combine,
 104                                                            int gid) {
 105     Vector<ScheduleNode> result = new Vector<ScheduleNode>();
 106
 107     // clone the ScheduleNodes
 108     Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash =
 109       new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
 110     Hashtable<ScheduleNode, ScheduleNode> sn2sn =
 111       new Hashtable<ScheduleNode, ScheduleNode>();
 112     cloneScheduleGraph(scheduleNodes,
 113                        scheduleEdges,
 114                        sn2hash,
 115                        sn2sn,
 116                        result,
 117                        gid);
 118
 119     // combine those nodes in combine with corresponding rootnodes
 120     for(int i = 0; i < combine.size(); i++) {
 121       if(combine.elementAt(i) != null) {
 122         for(int j = 0; j < combine.elementAt(i).size(); j++) {
 123           CombinationUtil.Combine tmpcombine = combine.elementAt(i).elementAt(j);
 124           ScheduleNode tocombine = sn2sn.get(tmpcombine.node);
 125           ScheduleNode root = sn2sn.get(rootnodes.elementAt(tmpcombine.root).elementAt(tmpcombine.index));
 126           ScheduleEdge se = (ScheduleEdge)tocombine.inedges().next();
 127           try {
 128             if(root.equals(((ScheduleNode)se.getSource()))) {
 129               root.mergeSEdge(se);
 130               if(ScheduleEdge.NEWEDGE == se.getType()) {
 131                 // As se has been changed into an internal edge inside a ScheduleNode,
 132                 // change the source and target of se from original ScheduleNodes into ClassNodes.
 133                 se.setTarget(se.getTargetCNode());
 134                 //se.setSource(se.getSourceCNode());
 135                 //se.getTargetCNode().addEdge(se);
 136                 se.getSourceCNode().addEdge(se);
 137               }
 138             } else {
 139               root.mergeSNode(tocombine);
 140             }
 141           } catch(Exception e) {
 142             e.printStackTrace();
 143             System.exit(-1);
 144           }
 145           result.removeElement(tocombine);
 146         }
 147       }
 148     }
 149
 150     assignCids(result);
 151
 152     sn2hash.clear();
 153     sn2hash = null;
 154     sn2sn.clear();
 155     sn2sn = null;
 156
 157     if(state.PRINTSCHEDULING) {
 158       String path = state.outputdir + "scheduling_" + gid + ".dot";
 159       SchedulingUtil.printScheduleGraph(path, result);
 160     }
 161
 162     return result;
 163   }
 164
 165   public static void cloneScheduleGraph(Vector<ScheduleNode> scheduleNodes,
 166                                         Vector<ScheduleEdge> scheduleEdges,
 167                                         Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash,
 168                                         Hashtable<ScheduleNode, ScheduleNode> sn2sn,
 169                                         Vector<ScheduleNode> result,
 170                                         int gid) {
 171     for(int i = 0; i < scheduleNodes.size(); i++) {
 172       Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
 173       ScheduleNode tocopy = scheduleNodes.elementAt(i);
 174       ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
 175       result.add(i, temp);
 176       sn2hash.put(temp, cn2cn);
 177       sn2sn.put(tocopy, temp);
 178       cn2cn = null;
 179     }
 180     // clone the ScheduleEdges
 181     for(int i = 0; i < scheduleEdges.size(); i++) {
 182       ScheduleEdge sse = scheduleEdges.elementAt(i);
 183       ScheduleNode csource = sn2sn.get(sse.getSource());
 184       ScheduleNode ctarget = sn2sn.get(sse.getTarget());
 185       Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
 186       Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
 187       ScheduleEdge se =  null;
 188       switch(sse.getType()) {
 189       case ScheduleEdge.NEWEDGE: {
 190         se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid);               //new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
 191         se.setProbability(sse.getProbability());
 192         se.setNewRate(sse.getNewRate());
 193         break;
 194       }
 195
 196       case ScheduleEdge.TRANSEDGE: {
 197         se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid);               //new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
 198         break;
 199       }
 200       }
 201       se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
 202       se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
 203       se.setFEdge(sse.getFEdge());
 204       se.setTargetFState(sse.getTargetFState());
 205       se.setIsclone(true);
 206       csource.addEdge(se);
 207       sourcecn2cn = null;
 208       targetcn2cn = null;
 209     }
 210   }
 211
 212   public static void assignCids(Vector<ScheduleNode> result) {
 213     Hashtable<Integer, Integer> hcid2cid = new Hashtable<Integer, Integer>();
 214     int ncid = 0;
 215     for(int i = 0; i < result.size(); i++) {
 216       ScheduleNode tmpnode = result.elementAt(i);
 217       tmpnode.computeHashcid();
 218       int hcid = tmpnode.getHashcid();
 219       if(hcid2cid.containsKey(hcid)) {
 220         // already have a cid for this node
 221         tmpnode.setCid(hcid2cid.get(hcid));
 222       } else {
 223         // generate a new cid for such node
 224         tmpnode.setCid(ncid);
 225         hcid2cid.put(hcid, ncid);
 226         ncid++;
 227       }
 228     }
 229     hcid2cid.clear();
 230     hcid2cid = null;
 231   }
 232
 233   //  Organize the scheduleNodes in order of their cid
 234   public static Vector<Vector<ScheduleNode>>
 235   rangeScheduleNodes(Vector<ScheduleNode> scheduleNodes) {
 236     try {
 237       Vector<Vector<ScheduleNode>> sNodeVecs = new Vector<Vector<ScheduleNode>>();
 238
 239       for(int i = 0; i < scheduleNodes.size(); i++) {
 240         ScheduleNode tmpn = scheduleNodes.elementAt(i);
 241         int tmpcid = tmpn.getCid();
 242         int index = 0;
 243         for(index = 0; index < sNodeVecs.size(); index++) {
 244           if(sNodeVecs.elementAt(index).elementAt(0).getCid() > tmpcid) {
 245             // find the place to insert
 246             sNodeVecs.insertElementAt(new Vector<ScheduleNode>(), index);
 247             /*sNodeVecs.add(sNodeVecs.lastElement());
 248                for(int j = sNodeVecs.size() - 2; j > index; j--) {
 249                sNodeVecs.setElementAt(sNodeVecs.elementAt(j - 1), j);
 250                }
 251                sNodeVecs.setElementAt(new Vector<ScheduleNode>(), index);*/
 252             break;
 253           } else if(sNodeVecs.elementAt(index).elementAt(0).getCid() == tmpcid) {
 254             break;
 255           }
 256         }
 257         if(index == sNodeVecs.size()) {
 258           sNodeVecs.add(new Vector<ScheduleNode>());
 259         }
 260
 261         /*int index = tmpcid;
 262            while(sNodeVecs.size() <= index) {
 263            sNodeVecs.add(null);
 264            }
 265            if(sNodeVecs.elementAt(index) == null) {
 266            sNodeVecs.setElementAt(new Vector<ScheduleNode>(), index);
 267            }*/
 268         if(!sNodeVecs.elementAt(index).contains(tmpn)) {
 269           sNodeVecs.elementAt(index).addElement(tmpn);
 270         }
 271       }
 272
 273       return sNodeVecs;
 274     } catch(Error e) {
 275       System.err.println("Error in rangeScheduleNodes: " + scheduleNodes.size());
 276       e.printStackTrace();
 277       //System.exit(-1);
 278       return null;
 279     }
 280   }
 281
 282   /*public static int maxDivisor(int l, int r) {
 283      int a = l;
 284      int b = r;
 285      int c = 0;
 286
 287      while(true) {
 288         if(a == 0) {
 289             return b << c;
 290         } else if(b == 0) {
 291             return a << c;
 292         }
 293
 294         if(((a&1)==0) && ((b&1)==0)) {
 295             // a and b are both even
 296             a >>= 1;
 297             b >>= 1;
 298    ++c;
 299         } else if(((a&1)==0) && ((b&1)!=0)) {
 300             // a is even, b is odd
 301             a >>= 1;
 302         } else if (((a&1)!=0) && ((b&1)==0)) {
 303             // a is odd, b is even
 304             b >>= 1;
 305         } else if (((a&1)!=0) && ((b&1)!=0)) {
 306             // a and b are both odd
 307             int tmp = a>b? b:a;
 308             a = a>b ? (a-b):(b-a);
 309             b = tmp;
 310         }
 311      }
 312      }*/
 313
 314   public static boolean isTaskTrigger_flag(FlagExpressionNode fen,
 315                                            FlagState fs) {
 316     if (fen==null)
 317       return true;
 318     else if (fen instanceof FlagNode)
 319       return fs.get(((FlagNode)fen).getFlag());
 320     else
 321       switch (((FlagOpNode)fen).getOp().getOp()) {
 322       case Operation.LOGIC_AND:
 323         return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 324
 325       case Operation.LOGIC_OR:
 326         return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 327
 328       case Operation.LOGIC_NOT:
 329         return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
 330
 331       default:
 332         return false;
 333       }
 334   }
 335
 336   public static void printScheduleGraph(String path,
 337                                         Vector<ScheduleNode> sNodes) {
 338     try {
 339       File file=new File(path);
 340       FileOutputStream dotstream=new FileOutputStream(file,false);
 341       PrintWriter output = new java.io.PrintWriter(dotstream, true);
 342       output.println("digraph G {");
 343       output.println("\tcompound=true;\n");
 344       traverseSNodes(output, sNodes);
 345       output.println("}\n");
 346       output.close();
 347     } catch (Exception e) {
 348       e.printStackTrace();
 349       System.exit(-1);
 350     }
 351   }
 352
 353   private static void traverseSNodes(PrintWriter output,
 354                                      Vector<ScheduleNode> sNodes) {
 355     //Draw clusters representing ScheduleNodes
 356     Iterator it = sNodes.iterator();
 357     while (it.hasNext()) {
 358       ScheduleNode gn = (ScheduleNode) it.next();
 359       Iterator edges = gn.edges();
 360       output.println("\tsubgraph " + gn.getLabel() + "{");
 361       output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
 362       Iterator it_cnodes = gn.getClassNodesIterator();
 363       traverseCNodes(output, it_cnodes);
 364       it_cnodes = null;
 365       //Draw the internal 'new' edges
 366       Iterator it_edges =gn.getScheduleEdgesIterator();
 367       while(it_edges.hasNext()) {
 368         ScheduleEdge se = (ScheduleEdge)it_edges.next();
 369         output.print("\t");
 370         if(se.getSourceCNode().isclone()) {
 371           output.print(se.getSourceCNode().getLabel());
 372         } else {
 373           if(se.getSourceFState() == null) {
 374             output.print(se.getSourceCNode().getClusterLabel());
 375           } else {
 376             output.print(se.getSourceFState().getLabel());
 377           }
 378         }
 379
 380         output.print(" -> ");
 381         if(se.isclone()) {
 382           if(se.getTargetCNode().isclone()) {
 383             output.print(se.getTargetCNode().getLabel());
 384           } else {
 385             output.print(se.getTargetCNode().getClusterLabel());
 386           }
 387           output.println(" [label=\"" + se.getLabel() + "\", color=red];");
 388         } else {
 389           output.print(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail=");
 390           if(se.getSourceCNode().isclone()) {
 391             output.println(se.getSourceCNode().getLabel() + "];");
 392           } else {
 393             output.println(se.getSourceCNode().getClusterLabel() + "];");
 394           }
 395         }
 396       }
 397       output.println("\t}\n");
 398       it_edges = null;
 399       //Draw 'new' edges of this ScheduleNode
 400       while(edges.hasNext()) {
 401         ScheduleEdge se = (ScheduleEdge)edges.next();
 402         output.print("\t");
 403         if(se.getSourceCNode().isclone()) {
 404           output.print(se.getSourceCNode().getLabel());
 405         } else {
 406           if(se.getSourceFState() == null) {
 407             output.print(se.getSourceCNode().getClusterLabel());
 408           } else {
 409             output.print(se.getSourceFState().getLabel());
 410           }
 411         }
 412
 413         output.print(" -> ");
 414         if(se.isclone()) {
 415           if(se.getTargetCNode().isclone()) {
 416             output.print(se.getTargetCNode().getLabel());
 417           } else {
 418             output.print(se.getTargetCNode().getClusterLabel());
 419           }
 420           output.println(" [label=\"" + se.getLabel() + "\", color=red, style=dashed];");
 421         } else {
 422           output.println(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed];");
 423         }
 424       }
 425       edges = null;
 426     }
 427     it = null;
 428   }
 429
 430   private static void traverseCNodes(PrintWriter output,
 431                                      Iterator it) {
 432     //Draw clusters representing ClassNodes
 433     while (it.hasNext()) {
 434       ClassNode gn = (ClassNode) it.next();
 435       if(gn.isclone()) {
 436         output.println("\t\t" + gn.getLabel() + " [style=dashed, label=\"" + gn.getTextLabel() + "\", shape=box];");
 437       } else {
 438         output.println("\tsubgraph " + gn.getClusterLabel() + "{");
 439         output.println("\t\tstyle=dashed;");
 440         output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
 441         traverseFlagStates(output, gn.getFlagStates());
 442         output.println("\t}\n");
 443       }
 444     }
 445   }
 446
 447   private static void traverseFlagStates(PrintWriter output,
 448                                          Collection nodes) {
 449     Set cycleset=GraphNode.findcycles(nodes);
 450     Vector namers=new Vector();
 451     namers.add(new Namer());
 452     namers.add(new Allocations());
 453
 454     Iterator it = nodes.iterator();
 455     while (it.hasNext()) {
 456       GraphNode gn = (GraphNode) it.next();
 457       Iterator edges = gn.edges();
 458       String label = "";
 459       String dotnodeparams="";
 460
 461       for(int i=0; i<namers.size(); i++) {
 462         Namer name=(Namer) namers.get(i);
 463         String newlabel=name.nodeLabel(gn);
 464         String newparams=name.nodeOption(gn);
 465
 466         if (!newlabel.equals("") && !label.equals("")) {
 467           label+=", ";
 468         }
 469         if (!newparams.equals("")) {
 470           dotnodeparams+=", " + name.nodeOption(gn);
 471         }
 472         label+=name.nodeLabel(gn);
 473       }
 474       label += ":[" + ((FlagState)gn).getExeTime() + "]";
 475
 476       if (!gn.merge)
 477         output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
 478
 479       if (!gn.merge)
 480         while (edges.hasNext()) {
 481           Edge edge = (Edge) edges.next();
 482           GraphNode node = edge.getTarget();
 483           if (nodes.contains(node)) {
 484             Iterator nodeit=nonmerge(node, nodes).iterator();
 485             for(; nodeit.hasNext(); ) {
 486               GraphNode node2=(GraphNode)nodeit.next();
 487               String edgelabel = "";
 488               String edgedotnodeparams="";
 489
 490               for(int i=0; i<namers.size(); i++) {
 491                 Namer name=(Namer) namers.get(i);
 492                 String newlabel=name.edgeLabel(edge);
 493                 String newoption=name.edgeOption(edge);
 494                 if (!newlabel.equals("")&& !edgelabel.equals(""))
 495                   edgelabel+=", ";
 496                 edgelabel+=newlabel;
 497                 if (!newoption.equals(""))
 498                   edgedotnodeparams+=", "+newoption;
 499               }
 500               edgelabel+=":[" + ((FEdge)edge).getExeTime() + "]";
 501               edgelabel+=":(" + ((FEdge)edge).getProbability() + "%)";
 502               Hashtable<ClassDescriptor, NewObjInfo> hashtable = ((FEdge)edge).getNewObjInfoHashtable();
 503               if(hashtable != null) {
 504                 Set<ClassDescriptor> keys = hashtable.keySet();
 505                 Iterator it_keys = keys.iterator();
 506                 while(it_keys.hasNext()) {
 507                   ClassDescriptor cd = (ClassDescriptor)it_keys.next();
 508                   NewObjInfo noi = hashtable.get(cd);
 509                   edgelabel += ":{ class " + cd.getSymbol() + " | " + noi.getNewRate() + " | (" + noi.getProbability() + "%) }";
 510                 }
 511                 keys = null;
 512                 it_keys = null;
 513               }
 514               output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
 515             }
 516             nodeit = null;
 517           }
 518         }
 519       edges = null;
 520     }
 521     cycleset = null;
 522     namers = null;
 523     it = null;
 524   }
 525
 526   private static Set nonmerge(GraphNode gn,
 527                               Collection nodes) {
 528     HashSet newset=new HashSet();
 529     HashSet toprocess=new HashSet();
 530     toprocess.add(gn);
 531     while(!toprocess.isEmpty()) {
 532       GraphNode gn2=(GraphNode)toprocess.iterator().next();
 533       toprocess.remove(gn2);
 534       if (!gn2.merge)
 535         newset.add(gn2);
 536       else {
 537         Iterator edges = gn2.edges();
 538         while (edges.hasNext()) {
 539           Edge edge = (Edge) edges.next();
 540           GraphNode node = edge.getTarget();
 541           if (!newset.contains(node)&&nodes.contains(node))
 542             toprocess.add(node);
 543         }
 544         edges = null;
 545       }
 546     }
 547     toprocess = null;
 548     return newset;
 549   }
 550
 551   public static void printSimulationResult(String path,
 552                                            long time,
 553                                            int coreNum,
 554                                            Vector<CheckPoint> checkpoints) {
 555     try {
 556       File file=new File(path);
 557       FileOutputStream dotstream=new FileOutputStream(file,false);
 558       PrintWriter output = new java.io.PrintWriter(dotstream, true);
 559       output.println("digraph simulation{");
 560       output.print("\t");
 561       output.println("node [shape=plaintext];");
 562       output.print("\t");
 563       output.println("edge [dir=none];");
 564       output.print("\t");
 565       output.println("ranksep=.05;");
 566       output.println();
 567       output.print("\t");
 568       int j = 0;
 569
 570       // the capital line
 571       output.print("{rank=source; \"Time\"; ");
 572       for(j = 0; j < coreNum; j++) {
 573         output.print("\"core " + j + "\"; ");
 574       }
 575       output.println("}");
 576       // time coordinate nodes
 577       Vector<String> timeNodes = new Vector<String>();
 578       String[] lastTaskNodes = new String[coreNum];
 579       String[] lastTasks = new String[coreNum];
 580       boolean[] isTaskFinish = new boolean[coreNum];
 581       for(j = 0; j < coreNum; j++) {
 582         lastTaskNodes[j] = "first";
 583         isTaskFinish[j] = true;
 584         lastTasks[j] = "";
 585       }
 586       timeNodes.add("0");
 587       for(j = 0; j < checkpoints.size(); j++) {
 588         CheckPoint tcp = checkpoints.elementAt(j);
 589         Hashtable<Integer, String> tmplastTasks = new Hashtable<Integer, String>();
 590         Vector<Integer> tmpisTaskFinish = new Vector<Integer>();
 591         Vector<Integer> tmpisset = new Vector<Integer>();
 592         String tnode = String.valueOf(tcp.getTimepoint());
 593         if(!timeNodes.contains(tnode)) {
 594           timeNodes.add(tnode);
 595         }
 596         Vector<Action> actions = tcp.getActions();
 597         Hashtable<String, StringBuffer> tmpTaskNodes = new Hashtable<String, StringBuffer>();
 598         for(int i = 0; i < actions.size(); i++) {
 599           Action taction = actions.elementAt(i);
 600           int cNum = taction.getCoreNum();
 601           if(!tmplastTasks.containsKey(cNum)) {
 602             tmplastTasks.put(cNum, lastTasks[cNum]);
 603           }
 604           if(!(tmpisset.contains(cNum))
 605              && (isTaskFinish[cNum])
 606              && !(tmpisTaskFinish.contains(cNum))) {
 607             tmpisTaskFinish.add(cNum);              // records those with task finished the first time visit it
 608           }
 609           String tmpTaskNode = "\"" + tnode + "core" + cNum + "\"";
 610           StringBuffer tmpLabel = null;
 611           boolean isfirst = false;
 612           if(!tmpTaskNodes.containsKey(tmpTaskNode)) {
 613             tmpTaskNodes.put(tmpTaskNode, new StringBuffer(tnode + ":"));
 614             isfirst = true;
 615           }
 616           tmpLabel = tmpTaskNodes.get(tmpTaskNode);
 617           switch(taction.getType()) {
 618           case Action.ADDOBJ: {
 619             if(!isfirst) {
 620               tmpLabel.append("\\n");
 621             }
 622             tmpLabel.append("(" + taction.getTransObj().getSymbol() + ")arrives;");
 623             if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 624               output.print("\t");
 625               if(lastTaskNodes[cNum].equals("first")) {
 626                 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
 627               } else {
 628                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 629               }
 630               if(tmpisTaskFinish.contains(cNum)) {
 631                 output.print(" [style=invis]");
 632               }
 633               output.println(";");
 634               lastTaskNodes[cNum] = tmpTaskNode;
 635             }
 636             break;
 637           }
 638
 639           case Action.TASKFINISH: {
 640             if(!isfirst) {
 641               tmpLabel.append("\\n");
 642             }
 643             tmpLabel.append("<" + taction.getTd().getSymbol() + "(");
 644             /*Vector<Integer> taskparams = taction.getTaskParams();
 645                for(int ii = 0; ii < taskparams.size(); ii++) {
 646                tmpLabel.append(taskparams.elementAt(ii));
 647                if(ii < taskparams.size() - 1) {
 648                tmpLabel.append(",");
 649                }
 650                }*/
 651             tmpLabel.append(")>finishes;");
 652             if(!(lastTaskNodes[cNum].equals("first"))) {
 653               if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 654                 output.print("\t");
 655                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 656                 lastTaskNodes[cNum] = tmpTaskNode;
 657               }
 658               if(tmpisset.contains(cNum)) {
 659                 isTaskFinish[cNum] &= true;
 660               } else {
 661                 isTaskFinish[cNum] = true;
 662                 tmpisset.add(cNum);
 663               }
 664               lastTasks[cNum] = "";
 665             } else {
 666               throw new Exception("Error: unexpected task finish");
 667             }
 668             break;
 669           }
 670
 671           case Action.TFWITHOBJ: {
 672             if(!isfirst) {
 673               tmpLabel.append("\\n");
 674             }
 675             tmpLabel.append("<" + taction.getTd().getSymbol() + "(");
 676             /*Vector<Integer> taskparams = taction.getTaskParams();
 677                for(int ii = 0; ii < taskparams.size(); ii++) {
 678                tmpLabel.append(taskparams.elementAt(ii));
 679                if(ii < taskparams.size() - 1) {
 680                tmpLabel.append(",");
 681                }
 682                }*/
 683             tmpLabel.append(")>finishes;");
 684             Iterator<Entry<ClassDescriptor, Integer>> it_entry = (Iterator<Entry<ClassDescriptor, Integer>>)taction.getNObjs().entrySet().iterator();
 685             while(it_entry.hasNext()) {
 686               Entry<ClassDescriptor, Integer> entry = it_entry.next();
 687               tmpLabel.append(entry.getValue() + "(" + entry.getKey().getSymbol() + ")");
 688               if(it_entry.hasNext()) {
 689                 tmpLabel.append(",");
 690               } else {
 691                 tmpLabel.append(";");
 692               }
 693               entry = null;
 694             }
 695             it_entry = null;
 696             if(!(lastTaskNodes[cNum].equals("first"))) {
 697               if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 698                 output.print("\t");
 699                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 700                 lastTaskNodes[cNum] = tmpTaskNode;
 701               }
 702               if(tmpisset.contains(cNum)) {
 703                 isTaskFinish[cNum] &= true;
 704               } else {
 705                 isTaskFinish[cNum] = true;
 706                 tmpisset.add(cNum);
 707               }
 708               lastTasks[cNum] = "";
 709             } else {
 710               throw new Exception("Error: unexpected task finish");
 711             }
 712             break;
 713           }
 714
 715           case Action.TASKSTART: {
 716             if(!isfirst) {
 717               tmpLabel.append("\\n");
 718             }
 719             tmpLabel.append("<" + taction.getTd().getSymbol() + "(");
 720             /*Vector<Integer> taskparams = taction.getTaskParams();
 721                for(int ii = 0; ii < taskparams.size(); ii++) {
 722                tmpLabel.append(taskparams.elementAt(ii));
 723                if(ii < taskparams.size() - 1) {
 724                tmpLabel.append(",");
 725                }
 726                }*/
 727             tmpLabel.append(")>starts;");
 728             lastTasks[cNum] = taction.getTd().getSymbol();
 729
 730             if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 731               output.print("\t");
 732               if(lastTaskNodes[cNum].equals("first")) {
 733                 output.print("\"core " + cNum + "\"->" + tmpTaskNode);
 734               } else {
 735                 output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
 736               }
 737               if(tmpisTaskFinish.contains(cNum)) {
 738                 output.print(" [style=invis]");
 739               }
 740               output.println(";");
 741               lastTaskNodes[cNum] = tmpTaskNode;
 742             }
 743             isTaskFinish[cNum] &= false;
 744             break;
 745           }
 746
 747           case Action.TASKABORT: {
 748             if(!isfirst) {
 749               tmpLabel.append("\\n");
 750             }
 751             tmpLabel.append("<" + taction.getTd().getSymbol() + "(");
 752             /*Vector<Integer> taskparams = taction.getTaskParams();
 753                for(int ii = 0; ii < taskparams.size(); ii++) {
 754                tmpLabel.append(taskparams.elementAt(ii));
 755                if(ii < taskparams.size() - 1) {
 756                tmpLabel.append(",");
 757                }
 758                }*/
 759             tmpLabel.append(")>aborts;");
 760             if(!(lastTaskNodes[cNum].equals("first")) &&
 761                (tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) {
 762               if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 763                 output.print("\t");
 764                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 765                 lastTaskNodes[cNum] = tmpTaskNode;
 766               }
 767               if(tmpisset.contains(cNum)) {
 768                 isTaskFinish[cNum] &= true;
 769               } else {
 770                 isTaskFinish[cNum] = true;
 771                 tmpisset.add(cNum);
 772               }
 773               lastTasks[cNum] = "";
 774             } else {
 775               throw new Exception("Error: unexpected task aborts");
 776             }
 777             break;
 778           }
 779
 780           case Action.TASKREMOVE: {
 781             if(!isfirst) {
 782               tmpLabel.append("\\n");
 783             }
 784             tmpLabel.append("<" + taction.getTd().getSymbol() + "(");
 785             /*Vector<Integer> taskparams = taction.getTaskParams();
 786                for(int ii = 0; ii < taskparams.size(); ii++) {
 787                tmpLabel.append(taskparams.elementAt(ii));
 788                if(ii < taskparams.size() - 1) {
 789                tmpLabel.append(",");
 790                }
 791                }*/
 792             tmpLabel.append(")>removes;");
 793             if(!(lastTaskNodes[cNum].equals("first")) &&
 794                (tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) {
 795               if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
 796                 output.print("\t");
 797                 output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode + ";");
 798                 lastTaskNodes[cNum] = tmpTaskNode;
 799               }
 800               if(tmpisset.contains(cNum)) {
 801                 isTaskFinish[cNum] &= true;
 802               } else {
 803                 isTaskFinish[cNum] = true;
 804                 tmpisset.add(cNum);
 805               }
 806               lastTasks[cNum] = "";
 807             } else {
 808               throw new Exception("Error: unexpected task remove");
 809             }
 810             break;
 811           }
 812           }
 813         }
 814         Enumeration<String> keys = tmpTaskNodes.keys();
 815         while(keys.hasMoreElements()) {
 816           String tmpTaskNode = keys.nextElement();
 817           output.print("\t");
 818           output.println(tmpTaskNode + "[label=\"" + tmpTaskNodes.get(tmpTaskNode).toString() + "\"]");
 819         }
 820         output.print("\t");
 821         output.print("{rank=same; rankdir=LR; " + tnode + "; ");
 822         keys = tmpTaskNodes.keys();
 823         while(keys.hasMoreElements()) {
 824           String tmpTaskNode = keys.nextElement();
 825           output.print(tmpTaskNode);
 826           output.print("; ");
 827         }
 828         keys = null;
 829         output.println("}");
 830         output.print("\t");
 831         tmplastTasks = null;
 832         tmpisTaskFinish = null;
 833         tmpisset = null;
 834         actions = null;
 835         tmpTaskNodes = null;
 836       }
 837       output.print("\t");
 838       output.print("\t");
 839       long prev = Long.parseLong(timeNodes.elementAt(0));
 840       long next = 0;
 841       long max = 0;
 842       long max2 = 0;
 843       for(j = 1; j < timeNodes.size(); j++) {
 844         next = Long.parseLong(timeNodes.elementAt(j));
 845         long delta = next - prev;
 846         if(max < delta) {
 847           max2 = max;
 848           max = delta;
 849         } else if((max != delta) && (max2 < delta)) {
 850           max2 = delta;
 851         }
 852         prev = next;
 853       }
 854       if(max2 == 0) {
 855         max2 = 1;
 856       } else if(max/max2 > 100) {
 857         max2 = max/100;
 858       }
 859       output.println("\"Time\"->" + timeNodes.elementAt(0) + "[style=invis];");
 860       prev = Long.parseLong(timeNodes.elementAt(0));
 861       next = 0;
 862       for(j = 1; j < timeNodes.size(); j++) {
 863         next = Long.parseLong(timeNodes.elementAt(j));
 864         if(next - prev > max2) {
 865           do {
 866             output.print(prev + "->");
 867             prev += max2;
 868           } while(next - prev > max2);
 869           output.println(next + ";");
 870         } else {
 871           output.println("{rank=same; rankdir=LR; " + prev + "; " + next + "}");
 872           output.println(prev + "->" + next + "[style=invis];");
 873         }
 874         prev = next;
 875       }
 876
 877       /*for(j = 0; j < time; j++) {
 878          output.print(j + "->");
 879          }
 880          output.println(timeNodes.lastElement() + ";");*/
 881       output.println("}");
 882       output.close();
 883       timeNodes = null;
 884       lastTaskNodes = null;
 885       lastTasks = null;
 886       isTaskFinish = null;
 887     } catch (Exception e) {
 888       e.printStackTrace();
 889       System.exit(-1);
 890     }
 891   }
 892
 893   public static void printCriticalPath(String path,
 894                                        Vector<SimExecutionEdge> criticalPath) {
 895     try {
 896       File file=new File(path);
 897       FileOutputStream dotstream=new FileOutputStream(file,false);
 898       PrintWriter output = new java.io.PrintWriter(dotstream, true);
 899       output.println("digraph simulation{");
 900       output.print("\t");
 901       output.println("node [shape=plaintext];");
 902       output.print("\t");
 903       output.println("edge [dir=none];");
 904       output.print("\t");
 905       output.println("ranksep=.05;");
 906       output.println();
 907       output.print("\t");
 908       Vector<SimExecutionNode> nodes = new Vector<SimExecutionNode>();
 909       String label = "";
 910       String dotnodeparams="";
 911
 912       for(int i = 0; i < criticalPath.size(); i++) {
 913         SimExecutionEdge seedge = criticalPath.elementAt(i);
 914         SimExecutionNode startnode = (SimExecutionNode)seedge.getSource();
 915         SimExecutionNode endnode = (SimExecutionNode)seedge.getTarget();
 916         if(!nodes.contains(startnode)) {
 917           label = startnode.getCoreNum() + ":" + startnode.getTimepoint();
 918           output.println("\t" + startnode.getLabel() + " [label=\""
 919                          + label + "\" ];");
 920           nodes.addElement(startnode);
 921         }
 922         if(!nodes.contains(endnode)) {
 923           label = endnode.getCoreNum() + ":" + endnode.getTimepoint();
 924           output.println("\t" + endnode.getLabel() + " [label=\""
 925                          + label + "\" ];");
 926           nodes.addElement(endnode);
 927         }
 928         output.println("\t" + startnode.getLabel() + " -> " + endnode.getLabel()
 929                        + " [" + "label=\"" + seedge.getLabel() + "\"];");
 930       }
 931       output.println("}");
 932       output.close();
 933       nodes.clear();
 934       nodes = null;
 935     } catch (Exception e) {
 936       e.printStackTrace();
 937       System.exit(-1);
 938     }
 939   }
 940 }