Robust/src/Analysis/Scheduling/ScheduleAnalysis.java

   1 package Analysis.Scheduling;
   2
   3 import Analysis.TaskStateAnalysis.*;
   4 import IR.*;
   5 import Util.GraphNode;
   6 import Util.GraphNode.SCC;
   7
   8 import java.io.FileInputStream;
   9 import java.util.*;
  10
  11 /** This class holds flag transition diagram(s) can be put on one core.
  12  */
  13 public class ScheduleAnalysis {
  14
  15   State state;
  16   TaskAnalysis taskanalysis;
  17
  18   Vector<ScheduleNode> scheduleNodes;
  19   Vector<ClassNode> classNodes;
  20   Vector<ScheduleEdge> scheduleEdges;
  21   Hashtable<ClassDescriptor, ClassNode> cd2ClassNode;
  22   boolean sorted = false;
  23
  24   int transThreshold;
  25
  26   int scheduleThreshold;
  27   int coreNum;
  28   Vector<Vector<ScheduleNode>> scheduleGraphs;
  29
  30   // Main CD table for multi-param tasks
  31   Hashtable<TaskDescriptor, ClassDescriptor> td2maincd;
  32
  33   public ScheduleAnalysis(State state,
  34                           TaskAnalysis taskanalysis) {
  35     this.state = state;
  36     this.taskanalysis = taskanalysis;
  37     this.scheduleNodes = new Vector<ScheduleNode>();
  38     this.classNodes = new Vector<ClassNode>();
  39     this.scheduleEdges = new Vector<ScheduleEdge>();
  40     this.cd2ClassNode = new Hashtable<ClassDescriptor, ClassNode>();
  41     this.transThreshold = 45; // defaultly 45
  42     this.scheduleThreshold = 1000; // defaultly 1000
  43     this.coreNum = -1;
  44     this.scheduleGraphs = null;
  45     this.td2maincd = null;
  46   }
  47
  48   public void setTransThreshold(int tt) {
  49     this.transThreshold = tt;
  50   }
  51
  52   public void setScheduleThreshold(int stt) {
  53     this.scheduleThreshold = stt;
  54   }
  55
  56   public int getCoreNum() {
  57     return coreNum;
  58   }
  59
  60   public void setCoreNum(int coreNum) {
  61     this.coreNum = coreNum;
  62   }
  63
  64   public Vector<Vector<ScheduleNode>> getScheduleGraphs() {
  65     return this.scheduleGraphs;
  66   }
  67
  68   // for test
  69   public Vector<ScheduleEdge> getSEdges4Test() {
  70     return scheduleEdges;
  71   }
  72
  73   public Hashtable<TaskDescriptor, ClassDescriptor> getTd2maincd() {
  74     return td2maincd;
  75   }
  76
  77   public boolean schedule(int generateThreshold,
  78                           Vector<TaskDescriptor> multiparamtds) {
  79     boolean tooptimize = true;
  80     try {
  81       Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
  82       ScheduleNode startupNode = null;
  83
  84       if((multiparamtds != null) || (multiparamtds.size() > 0)) {
  85         this.td2maincd = new Hashtable<TaskDescriptor, ClassDescriptor>();
  86       }
  87
  88       // necessary preparation such as read profile info etc.
  89       preSchedule();
  90       // build the CFSTG
  91       startupNode = buildCFSTG(toBreakDown, multiparamtds);
  92       // do Tree transform
  93       treeTransform(toBreakDown, startupNode);
  94       // do CFSTG transform to explore the potential parallelism as much
  95       // as possible
  96       CFSTGTransform();
  97       // mappint to real multi-core processor
  98       tooptimize = coreMapping(generateThreshold);
  99       toBreakDown = null;
 100     } catch (Exception e) {
 101       e.printStackTrace();
 102       System.exit(-1);
 103     }
 104     return tooptimize;
 105   }
 106
 107   private void preSchedule() {
 108     this.checkBackEdge();
 109
 110     // set up profiling data
 111     if(state.USEPROFILE) {
 112       java.util.Hashtable<String, TaskInfo> taskinfos =
 113         new java.util.Hashtable<String, TaskInfo>();
 114       this.readProfileInfo(taskinfos);
 115
 116       long tint = 0;
 117       Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator();
 118       while(it_classes.hasNext()) {
 119         ClassDescriptor cd = (ClassDescriptor) it_classes.next();
 120         if(cd.hasFlags()) {
 121           Vector rootnodes = this.taskanalysis.getRootNodes(cd);
 122           if(rootnodes!=null) {
 123             Iterator it_rootnodes = rootnodes.iterator();
 124             while(it_rootnodes.hasNext()) {
 125               FlagState root = (FlagState)it_rootnodes.next();
 126               Vector allocatingTasks = root.getAllocatingTasks();
 127               if(allocatingTasks != null) {
 128                 for(int k = 0; k < allocatingTasks.size(); k++) {
 129                   TaskDescriptor td =
 130                     (TaskDescriptor)allocatingTasks.elementAt(k);
 131                   Vector<FEdge> fev = this.taskanalysis.getFEdgesFromTD(td);
 132                   int numEdges = fev.size();
 133                   for(int j = 0; j < numEdges; j++) {
 134                     FEdge pfe = fev.elementAt(j);
 135                     TaskInfo taskinfo = taskinfos.get(td.getSymbol());
 136                     tint = taskinfo.m_exetime[pfe.getTaskExitIndex()];
 137                     pfe.setExeTime(tint);
 138                     double idouble =
 139                       taskinfo.m_probability[pfe.getTaskExitIndex()];
 140                     pfe.setProbability(idouble);
 141                     int newRate = 0;
 142                     int tindex = pfe.getTaskExitIndex();
 143                     if((taskinfo.m_newobjinfo.elementAt(tindex) != null)
 144                         && (taskinfo.m_newobjinfo.elementAt(tindex).containsKey(
 145                             cd.getSymbol()))) {
 146                       newRate = taskinfo.m_newobjinfo.elementAt(tindex).get(
 147                           cd.getSymbol());
 148                     }
 149                     pfe.addNewObjInfo(cd, newRate, idouble);
 150                     if(taskinfo.m_byObj != -1) {
 151                       ((FlagState)pfe.getSource()).setByObj(taskinfo.m_byObj);
 152                     }
 153                   }
 154                   fev = null;
 155                 }
 156               }
 157             }
 158             it_rootnodes = null;
 159           }
 160           Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator();
 161           while(it_flags.hasNext()) {
 162             FlagState fs = (FlagState)it_flags.next();
 163             Iterator it_edges = fs.edges();
 164             while(it_edges.hasNext()) {
 165               FEdge edge = (FEdge)it_edges.next();
 166               TaskInfo taskinfo = taskinfos.get(edge.getTask().getSymbol());
 167               tint = taskinfo.m_exetime[edge.getTaskExitIndex()];
 168               edge.setExeTime(tint);
 169               double idouble = taskinfo.m_probability[edge.getTaskExitIndex()];
 170               edge.setProbability(idouble);
 171               if(taskinfo.m_byObj != -1) {
 172                 ((FlagState)edge.getSource()).setByObj(taskinfo.m_byObj);
 173               }
 174             }
 175             it_edges = null;
 176           }
 177           it_flags = null;
 178         }
 179       }
 180       taskinfos = null;
 181       it_classes = null;
 182     } else {
 183       randomProfileSetting();
 184     }
 185   }
 186
 187   private void checkBackEdge() {
 188     // Indentify backedges
 189     Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();
 190     while(it_classes.hasNext()) {
 191       ClassDescriptor cd=(ClassDescriptor) it_classes.next();
 192       if(cd.hasFlags()) {
 193         Set<FlagState> fss = this.taskanalysis.getFlagStates(cd);
 194         SCC scc=GraphNode.DFS.computeSCC(fss);
 195         if (scc.hasCycles()) {
 196           for(int i=0; i<scc.numSCC(); i++) {
 197             if (scc.hasCycle(i)) {
 198               Set cycleset = scc.getSCC(i);
 199               Iterator it_fs = cycleset.iterator();
 200               while(it_fs.hasNext()) {
 201                 FlagState fs = (FlagState)it_fs.next();
 202                 Iterator it_edges = fs.edges();
 203                 while(it_edges.hasNext()) {
 204                   FEdge edge = (FEdge)it_edges.next();
 205                   if(cycleset.contains(edge.getTarget())) {
 206                     // a backedge
 207                     edge.setisbackedge(true);
 208                   }
 209                 }
 210                 it_edges = null;
 211               }
 212               it_fs = null;
 213             }
 214           }
 215         }
 216         fss = null;
 217       }
 218     }
 219     it_classes = null;
 220   }
 221
 222   private void readProfileInfo(java.util.Hashtable<String, TaskInfo> taskinfos){
 223     try {
 224       // read in profile data and set
 225       //FileInputStream inStream = new FileInputStream("/scratch/profile.rst");
 226       FileInputStream inStream =
 227         new FileInputStream("/scratch/" + this.state.profilename);
 228       byte[] b = new byte[1024 * 100];
 229       int length = inStream.read(b);
 230       if(length < 0) {
 231         System.out.print("No content in input file: /scratch/"
 232             + this.state.profilename + "\n");
 233         System.exit(-1);
 234       }
 235       String profiledata = new String(b, 0, length);
 236
 237       // profile data format:
 238       //   taskname, numoftaskexits(; exetime, probability, numofnewobjtypes(,
 239       //   newobj type, num of objs)+)+
 240       int inindex = profiledata.indexOf('\n');
 241       while((inindex != -1) ) {
 242         String inline = profiledata.substring(0, inindex);
 243         profiledata = profiledata.substring(inindex + 1);
 244         //System.printString(inline + "\n");
 245         int tmpinindex = inline.indexOf(',');
 246         if(tmpinindex == -1) {
 247           break;
 248         }
 249         String inname = inline.substring(0, tmpinindex);
 250         String inint = inline.substring(tmpinindex + 1);
 251         while(inint.startsWith(" ")) {
 252           inint = inint.substring(1);
 253         }
 254         tmpinindex = inint.indexOf(',');
 255         if(tmpinindex == -1) {
 256           break;
 257         }
 258         int numofexits = Integer.parseInt(inint.substring(0, tmpinindex));
 259         TaskInfo tinfo = new TaskInfo(numofexits);
 260         inint = inint.substring(tmpinindex + 1);
 261         while(inint.startsWith(" ")) {
 262           inint = inint.substring(1);
 263         }
 264         tmpinindex = inint.indexOf(';');
 265         int byObj = Integer.parseInt(inint.substring(0, tmpinindex));
 266         if(byObj != -1) {
 267           tinfo.m_byObj = byObj;
 268         }
 269         inint = inint.substring(tmpinindex + 1);
 270         while(inint.startsWith(" ")) {
 271           inint = inint.substring(1);
 272         }
 273         for(int i = 0; i < numofexits; i++) {
 274           String tmpinfo = null;
 275           if(i < numofexits - 1) {
 276             tmpinindex = inint.indexOf(';');
 277             tmpinfo = inint.substring(0, tmpinindex);
 278             inint = inint.substring(tmpinindex + 1);
 279             while(inint.startsWith(" ")) {
 280               inint = inint.substring(1);
 281             }
 282           } else {
 283             tmpinfo = inint;
 284           }
 285
 286           tmpinindex = tmpinfo.indexOf(',');
 287           tinfo.m_exetime[i] = Long.parseLong(tmpinfo.substring(0, tmpinindex));
 288           tmpinfo = tmpinfo.substring(tmpinindex + 1);
 289           while(tmpinfo.startsWith(" ")) {
 290             tmpinfo = tmpinfo.substring(1);
 291           }
 292           tmpinindex = tmpinfo.indexOf(',');
 293           tinfo.m_probability[i] = Double.parseDouble(
 294               tmpinfo.substring(0,tmpinindex));
 295           tmpinfo = tmpinfo.substring(tmpinindex + 1);
 296           while(tmpinfo.startsWith(" ")) {
 297             tmpinfo = tmpinfo.substring(1);
 298           }
 299           tmpinindex = tmpinfo.indexOf(',');
 300           int numofnobjs = 0;
 301           if(tmpinindex == -1) {
 302             numofnobjs = Integer.parseInt(tmpinfo);
 303             if(numofnobjs != 0) {
 304               System.err.println("Error profile data format!");
 305               System.exit(-1);
 306             }
 307           } else {
 308             tinfo.m_newobjinfo.setElementAt(new Hashtable<String,Integer>(), i);
 309             numofnobjs = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
 310             tmpinfo = tmpinfo.substring(tmpinindex + 1);
 311             while(tmpinfo.startsWith(" ")) {
 312               tmpinfo = tmpinfo.substring(1);
 313             }
 314             for(int j = 0; j < numofnobjs; j++) {
 315               tmpinindex = tmpinfo.indexOf(',');
 316               String nobjtype = tmpinfo.substring(0, tmpinindex);
 317               tmpinfo = tmpinfo.substring(tmpinindex + 1);
 318               while(tmpinfo.startsWith(" ")) {
 319                 tmpinfo = tmpinfo.substring(1);
 320               }
 321               int objnum = 0;
 322               if(j < numofnobjs - 1) {
 323                 tmpinindex = tmpinfo.indexOf(',');
 324                 objnum  = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
 325                 tmpinfo = tmpinfo.substring(tmpinindex + 1);
 326                 while(tmpinfo.startsWith(" ")) {
 327                   tmpinfo = tmpinfo.substring(1);
 328                 }
 329               } else {
 330                 objnum = Integer.parseInt(tmpinfo);
 331               }
 332               tinfo.m_newobjinfo.elementAt(i).put(nobjtype, objnum);
 333             }
 334           }
 335         }
 336         taskinfos.put(inname, tinfo);
 337         inindex = profiledata.indexOf('\n');
 338       }
 339       inStream.close();
 340       inStream = null;
 341       b = null;
 342     } catch(Exception e) {
 343       e.printStackTrace();
 344     }
 345   }
 346
 347   // for test
 348   private void randomProfileSetting() {
 349     // Randomly set the newRate and probability of FEdges
 350     java.util.Random r=new java.util.Random();
 351     int tint = 0;
 352     Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();
 353     for(; it_classes.hasNext();) {
 354       ClassDescriptor cd=(ClassDescriptor) it_classes.next();
 355       if(cd.hasFlags()) {
 356         Vector rootnodes=this.taskanalysis.getRootNodes(cd);
 357         if(rootnodes!=null) {
 358           Iterator it_rootnodes=rootnodes.iterator();
 359           for(; it_rootnodes.hasNext();) {
 360             FlagState root=(FlagState)it_rootnodes.next();
 361             Vector allocatingTasks = root.getAllocatingTasks();
 362             if(allocatingTasks != null) {
 363               for(int k = 0; k < allocatingTasks.size(); k++) {
 364                 TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
 365                 Vector<FEdge> fev =
 366                   (Vector<FEdge>)this.taskanalysis.getFEdgesFromTD(td);
 367                 int numEdges = fev.size();
 368                 int total = 100;
 369                 for(int j = 0; j < numEdges; j++) {
 370                   FEdge pfe = fev.elementAt(j);
 371                   if(numEdges - j == 1) {
 372                     pfe.setProbability(total);
 373                   } else {
 374                     if((total != 0) && (total != 1)) {
 375                       do {
 376                         tint = r.nextInt()%total;
 377                       } while(tint <= 0);
 378                     }
 379                     pfe.setProbability(tint);
 380                     total -= tint;
 381                   }
 382                   //do {
 383                   //   tint = r.nextInt()%10;
 384                   //  } while(tint <= 0);
 385                   //int newRate = tint;
 386                   //int newRate = (j+1)%2+1;
 387                   int newRate = 1;
 388                   String cdname = cd.getSymbol();
 389                   if((cdname.equals("SeriesRunner")) ||
 390                       (cdname.equals("MDRunner")) ||
 391                       (cdname.equals("Stage")) ||
 392                       (cdname.equals("AppDemoRunner")) ||
 393                       (cdname.equals("FilterBankAtom")) ||
 394                       (cdname.equals("Grid")) ||
 395                       (cdname.equals("Fractal")) ||
 396                       (cdname.equals("KMeans")) ||
 397                       (cdname.equals("ZTransform")) ||
 398                                                                                         (cdname.equals("TestRunner")) ||
 399                                                                                         (cdname.equals("LinkList"))) {
 400                     newRate = this.coreNum;
 401                   } else if(cdname.equals("SentenceParser")) {
 402                     newRate = 4;
 403                   }
 404                   //do {
 405                   //    tint = r.nextInt()%100;
 406                   //   } while(tint <= 0);
 407                   //   int probability = tint;
 408                   int probability = 100;
 409                   pfe.addNewObjInfo(cd, newRate, probability);
 410                 }
 411                 fev = null;
 412               }
 413             }
 414           }
 415           it_rootnodes = null;
 416         }
 417
 418         Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator();
 419         while(it_flags.hasNext()) {
 420           FlagState fs = (FlagState)it_flags.next();
 421           Iterator it_edges = fs.edges();
 422           int total = 100;
 423           while(it_edges.hasNext()) {
 424             //do {
 425             //    tint = r.nextInt()%10;
 426             //   } while(tint <= 0);
 427             tint = 3;
 428             FEdge edge = (FEdge)it_edges.next();
 429             edge.setExeTime(tint);
 430             if((fs.getClassDescriptor().getSymbol().equals("MD"))
 431                 && (edge.getTask().getSymbol().equals("t6"))) {
 432               if(edge.isbackedge()) {
 433                 if(edge.getTarget().equals(edge.getSource())) {
 434                   edge.setProbability(93.75);
 435                 } else {
 436                   edge.setProbability(3.125);
 437                 }
 438               } else {
 439                 edge.setProbability(3.125);
 440               }
 441               continue;
 442             }
 443             if(!it_edges.hasNext()) {
 444               edge.setProbability(total);
 445             } else {
 446               if((total != 0) && (total != 1)) {
 447                 do {
 448                   tint = r.nextInt()%total;
 449                 } while(tint <= 0);
 450               }
 451               edge.setProbability(tint);
 452               total -= tint;
 453             }
 454           }
 455           it_edges = null;
 456         }
 457         it_flags = null;
 458       }
 459     }
 460     it_classes = null;
 461   }
 462
 463   private ScheduleNode buildCFSTG(Vector<ScheduleEdge> toBreakDown,
 464                                   Vector<TaskDescriptor> multiparamtds) {
 465     Hashtable<ClassDescriptor, ClassNode> cdToCNodes =
 466       new Hashtable<ClassDescriptor, ClassNode>();
 467     // Build the combined flag transition diagram
 468     // First, for each class create a ClassNode
 469     Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator();
 470     while(it_classes.hasNext()) {
 471       ClassDescriptor cd = (ClassDescriptor) it_classes.next();
 472       Set<FlagState> fStates = taskanalysis.getFlagStates(cd);
 473
 474       //Sort flagState nodes inside this ClassNode
 475       Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
 476
 477       Vector rootnodes  = taskanalysis.getRootNodes(cd);
 478       if(((rootnodes != null) && (rootnodes.size() > 0))
 479           || (cd.getSymbol().equals(TypeUtil.StartupClass))) {
 480         ClassNode cNode = new ClassNode(cd, sFStates);
 481         cNode.setSorted(true);
 482         classNodes.add(cNode);
 483         cd2ClassNode.put(cd, cNode);
 484         cdToCNodes.put(cd, cNode);
 485         cNode.calExeTime();
 486       }
 487       rootnodes = null;
 488       fStates = null;
 489       sFStates = null;
 490     }
 491     it_classes = null;
 492
 493     ScheduleNode startupNode = null;
 494     // For each ClassNode create a ScheduleNode containing it
 495     int i = 0;
 496     for(i = 0; i < classNodes.size(); i++) {
 497       ClassNode cn = classNodes.elementAt(i);
 498       ScheduleNode sn = new ScheduleNode(cn, 0);
 499       if(cn.getClassDescriptor().getSymbol().equals(TypeUtil.StartupClass)) {
 500         startupNode = sn;
 501       }
 502       cn.setScheduleNode(sn);
 503       scheduleNodes.add(sn);
 504       try {
 505         sn.calExeTime();
 506       } catch (Exception e) {
 507         e.printStackTrace();
 508       }
 509     }
 510
 511     // Create 'new' edges between the ScheduleNodes.
 512     Vector<ClassDescriptor> singleCDs = new Vector<ClassDescriptor>();
 513     for(i = 0; i < classNodes.size(); i++) {
 514       ClassNode cNode = classNodes.elementAt(i);
 515       ClassDescriptor cd = cNode.getClassDescriptor();
 516       Vector rootnodes  = taskanalysis.getRootNodes(cd);
 517       boolean isSingle = false;
 518       if(rootnodes != null) {
 519         for(int h = 0; h < rootnodes.size(); h++) {
 520           FlagState root=(FlagState)rootnodes.elementAt(h);
 521           Vector allocatingTasks = root.getAllocatingTasks();
 522           if(allocatingTasks != null) {
 523             for(int k = 0; k < allocatingTasks.size(); k++) {
 524               TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
 525               Vector<FEdge> fev =
 526                 (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
 527               int numEdges = fev.size();
 528               ScheduleNode sNode = cNode.getScheduleNode();
 529               for(int j = 0; j < numEdges; j++) {
 530                 FEdge pfe = fev.elementAt(j);
 531                 FEdge.NewObjInfo noi = pfe.getNewObjInfo(cd);
 532                 if ((noi == null) || (noi.getNewRate() == 0)
 533                     || (noi.getProbability() == 0)) {
 534                   // fake creating edge, do not need to create corresponding
 535                   // 'new' edge
 536                   continue;
 537                 }
 538                 if(noi.getNewRate() == 1) {
 539                   isSingle = true;
 540                 }
 541                 if(noi.getRoot() == null) {
 542                   // set root FlagState
 543                   noi.setRoot(root);
 544                 }
 545                 FlagState pfs = (FlagState)pfe.getTarget();
 546                 ClassDescriptor pcd = pfs.getClassDescriptor();
 547                 ClassNode pcNode = cdToCNodes.get(pcd);
 548
 549                 ScheduleEdge sEdge = new ScheduleEdge(sNode,
 550                                                       "new",
 551                                                       root,
 552                                                       ScheduleEdge.NEWEDGE,
 553                                                       0);
 554                 sEdge.setFEdge(pfe);
 555                 sEdge.setSourceCNode(pcNode);
 556                 sEdge.setTargetCNode(cNode);
 557                 sEdge.setTargetFState(root);
 558                 sEdge.setNewRate(noi.getNewRate());
 559                 sEdge.setProbability(noi.getProbability());
 560                 pcNode.getScheduleNode().addEdge(sEdge);
 561                 scheduleEdges.add(sEdge);
 562                 if((j !=0 ) || (k != 0) || (h != 0)) {
 563                   toBreakDown.add(sEdge);
 564                 }
 565               }
 566               fev = null;
 567             }
 568             allocatingTasks = null;
 569           }
 570           if(isSingle) {
 571             singleCDs.add(cd);
 572           }
 573         }
 574         rootnodes = null;
 575       }
 576     }
 577     cdToCNodes = null;
 578
 579     for(i = 0; i < multiparamtds.size(); i++) {
 580       TaskDescriptor td = multiparamtds.elementAt(i);
 581       for(int j = 0; j < td.numParameters(); j++) {
 582         ClassDescriptor cd = td.getParamType(j).getClassDesc();
 583         if(singleCDs.contains(cd)) {
 584           // set the first parameter which has single creation rate as main cd
 585           // TODO: may have bug when cd has multiple new flag states
 586           this.td2maincd.put(td, cd);
 587           break;
 588         }
 589       }
 590     }
 591
 592     return startupNode;
 593   }
 594
 595   private void treeTransform(Vector<ScheduleEdge> toBreakDown,
 596                              ScheduleNode startupNode) {
 597     int i = 0;
 598
 599     // Break down the 'cycle's
 600     try {
 601       for(i = 0; i < toBreakDown.size(); i++ ) {
 602         cloneSNodeList(toBreakDown.elementAt(i), false);
 603       }
 604     } catch (Exception e) {
 605       e.printStackTrace();
 606       System.exit(-1);
 607     }
 608
 609     // Remove fake 'new' edges
 610     for(i = 0; i < scheduleEdges.size(); i++) {
 611       ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i);
 612       if((0 == se.getNewRate()) || (0 == se.getProbability())) {
 613         scheduleEdges.removeElement(se);
 614         scheduleNodes.removeElement(se.getTarget());
 615       }
 616     }
 617
 618     // Do topology sort of the ClassNodes and ScheduleEdges.
 619     Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
 620     Vector<ScheduleNode> tempSNodes =
 621       ClassNode.DFS.topology(scheduleNodes, ssev);
 622     scheduleNodes.removeAllElements();
 623     scheduleNodes = tempSNodes;
 624     tempSNodes = null;
 625     scheduleEdges.removeAllElements();
 626     scheduleEdges = ssev;
 627     ssev = null;
 628     sorted = true;
 629
 630     // Set the cid of these ScheduleNode
 631     Queue<ScheduleNode> toVisit = new LinkedList<ScheduleNode>();
 632     toVisit.add(startupNode);
 633     while(!toVisit.isEmpty()) {
 634       ScheduleNode sn = toVisit.poll();
 635       if(sn.getCid() == -1) {
 636         // not visited before
 637         sn.setCid(ScheduleNode.colorID++);
 638         Iterator it_edge = sn.edges();
 639         while(it_edge.hasNext()) {
 640           toVisit.add((ScheduleNode)((ScheduleEdge)it_edge.next()).getTarget());
 641         }
 642         it_edge = null;
 643       }
 644     }
 645     toVisit = null;
 646
 647     if(this.state.PRINTSCHEDULING) {
 648       SchedulingUtil.printScheduleGraph(
 649           this.state.outputdir + "scheduling_ori.dot", this.scheduleNodes);
 650     }
 651   }
 652
 653   private void CFSTGTransform() {
 654     // First iteration
 655     int i = 0;
 656     //Access the ScheduleEdges in reverse topology order
 657     Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses =
 658       new Hashtable<FEdge, Vector<ScheduleEdge>>();
 659     Hashtable<ScheduleNode, Vector<FEdge>> sn2fes =
 660       new Hashtable<ScheduleNode, Vector<FEdge>>();
 661     ScheduleNode preSNode = null;
 662     for(i = scheduleEdges.size(); i > 0; i--) {
 663       ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i-1);
 664       if(ScheduleEdge.NEWEDGE == se.getType()) {
 665         if(preSNode == null) {
 666           preSNode = (ScheduleNode)se.getSource();
 667         }
 668
 669         boolean split = false;
 670         FEdge fe = se.getFEdge();
 671         if(fe.getSource() == fe.getTarget()) {
 672           // back edge
 673           try {
 674             int repeat = (int)Math.ceil(se.getNewRate()*se.getProbability()/100);
 675             int rate = 0;
 676             if(repeat > 1) {
 677               for(int j = 1; j< repeat; j++ ) {
 678                 cloneSNodeList(se, true);
 679               }
 680               se.setNewRate(1);
 681               se.setProbability(100);
 682             }
 683             try {
 684               rate = (int)Math.ceil(
 685                   se.getListExeTime()/calInExeTime(se.getSourceFState()));
 686             } catch (Exception e) {
 687               e.printStackTrace();
 688             }
 689             for(int j = rate - 1; j > 0; j--) {
 690               for(int k = repeat; k > 0; k--) {
 691                 cloneSNodeList(se, true);
 692               }
 693             }
 694           } catch (Exception e) {
 695             e.printStackTrace();
 696             System.exit(-1);
 697           }
 698         } else {
 699           // if preSNode is not the same as se's source ScheduleNode
 700           // handle any ScheduleEdges previously put into fe2ses whose source
 701           // ScheduleNode is preSNode
 702           boolean same = (preSNode == se.getSource());
 703           if(!same) {
 704             // check the topology sort, only process those after se.getSource()
 705             if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()){
 706               if(sn2fes.containsKey(preSNode)) {
 707                 Vector<FEdge> fes = sn2fes.remove(preSNode);
 708                 for(int j = 0; j < fes.size(); j++) {
 709                   FEdge tempfe = fes.elementAt(j);
 710                   Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 711                   ScheduleEdge tempse = ses.elementAt(0);
 712                   long temptime = tempse.getListExeTime();
 713                   // find out the ScheduleEdge with least exeTime
 714                   for(int k = 1; k < ses.size(); k++) {
 715                     long ttemp = ses.elementAt(k).getListExeTime();
 716                     if(ttemp < temptime) {
 717                       tempse = ses.elementAt(k);
 718                       temptime = ttemp;
 719                     }
 720                   }
 721                   // handle the tempse
 722                   handleScheduleEdge(tempse, true);
 723                   ses.removeElement(tempse);
 724                   // handle other ScheduleEdges
 725                   for(int k = 0; k < ses.size(); k++) {
 726                     handleScheduleEdge(ses.elementAt(k), false);
 727                   }
 728                   ses = null;
 729                   fe2ses.remove(tempfe);
 730                 }
 731                 fes = null;
 732               }
 733             }
 734             preSNode = (ScheduleNode)se.getSource();
 735           }
 736
 737           // if fe is the last task inside this ClassNode, delay the expanding
 738           // and merging until we find all such 'new' edges
 739           // associated with a last task inside this ClassNode
 740           if(!fe.getTarget().edges().hasNext()) {
 741             if(fe2ses.get(fe) == null) {
 742               fe2ses.put(fe, new Vector<ScheduleEdge>());
 743             }
 744             if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
 745               sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
 746             }
 747             if(!fe2ses.get(fe).contains(se)) {
 748               fe2ses.get(fe).add(se);
 749             }
 750             if(!sn2fes.get((ScheduleNode)se.getSource()).contains(fe)) {
 751               sn2fes.get((ScheduleNode)se.getSource()).add(fe);
 752             }
 753           } else {
 754             // As this is not a last task, first handle available ScheduleEdges
 755             // previously put into fe2ses
 756             if((same) && (sn2fes.containsKey(preSNode))) {
 757               Vector<FEdge> fes = sn2fes.remove(preSNode);
 758               for(int j = 0; j < fes.size(); j++) {
 759                 FEdge tempfe = fes.elementAt(j);
 760                 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 761                 ScheduleEdge tempse = ses.elementAt(0);
 762                 long temptime = tempse.getListExeTime();
 763                 // find out the ScheduleEdge with least exeTime
 764                 for(int k = 1; k < ses.size(); k++) {
 765                   long ttemp = ses.elementAt(k).getListExeTime();
 766                   if(ttemp < temptime) {
 767                     tempse = ses.elementAt(k);
 768                     temptime = ttemp;
 769                   }
 770                 }
 771                 // handle the tempse
 772                 handleScheduleEdge(tempse, true);
 773                 ses.removeElement(tempse);
 774                 // handle other ScheduleEdges
 775                 for(int k = 0; k < ses.size(); k++) {
 776                   handleScheduleEdge(ses.elementAt(k), false);
 777                 }
 778                 ses = null;
 779                 fe2ses.remove(tempfe);
 780               }
 781               fes = null;
 782             }
 783
 784             if((!(se.getTransTime() < this.transThreshold))
 785                 && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
 786               split = true;
 787               splitSNode(se, true);
 788             } else {
 789               // handle this ScheduleEdge
 790               handleScheduleEdge(se, true);
 791             }
 792           }
 793         }
 794       }
 795     }
 796     if(!fe2ses.isEmpty()) {
 797       Set<FEdge> keys = fe2ses.keySet();
 798       Iterator it_keys = keys.iterator();
 799       while(it_keys.hasNext()) {
 800         FEdge tempfe = (FEdge)it_keys.next();
 801         Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 802         ScheduleEdge tempse = ses.elementAt(0);
 803         long temptime = tempse.getListExeTime();
 804         // find out the ScheduleEdge with least exeTime
 805         for(int k = 1; k < ses.size(); k++) {
 806           long ttemp = ses.elementAt(k).getListExeTime();
 807           if(ttemp < temptime) {
 808             tempse = ses.elementAt(k);
 809             temptime = ttemp;
 810           }
 811         }
 812         // handle the tempse
 813         handleScheduleEdge(tempse, true);
 814         ses.removeElement(tempse);
 815         // handle other ScheduleEdges
 816         for(int k = 0; k < ses.size(); k++) {
 817           handleScheduleEdge(ses.elementAt(k), false);
 818         }
 819         ses = null;
 820       }
 821       keys = null;
 822       it_keys = null;
 823     }
 824     fe2ses.clear();
 825     sn2fes.clear();
 826     fe2ses = null;
 827     sn2fes = null;
 828
 829     if(this.state.PRINTSCHEDULING) {
 830       SchedulingUtil.printScheduleGraph(
 831           this.state.outputdir + "scheduling_extend.dot", this.scheduleNodes);
 832     }
 833   }
 834
 835   private void handleScheduleEdge(ScheduleEdge se,
 836       boolean merge) {
 837     try {
 838       int rate = 0;
 839       int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
 840       if(merge) {
 841         try {
 842           if(se.getListExeTime() == 0) {
 843             rate = repeat;
 844           } else {
 845             rate = (int)Math.ceil(
 846                 (se.getTransTime()-calInExeTime(se.getSourceFState()))
 847                 /se.getListExeTime());
 848           }
 849           if(rate < 0 ) {
 850             rate = 0;
 851           }
 852         } catch (Exception e) {
 853           e.printStackTrace();
 854         }
 855         if(0 == rate) {
 856           // clone the whole ScheduleNode lists starting with se's target
 857           for(int j = 1; j < repeat; j++ ) {
 858             cloneSNodeList(se, true);
 859           }
 860           se.setNewRate(1);
 861           se.setProbability(100);
 862         } else {
 863           repeat -= rate;
 864           if(repeat > 0) {
 865             // clone the whole ScheduleNode lists starting with se's target
 866             for(int j = 0; j < repeat; j++ ) {
 867               cloneSNodeList(se, true);
 868             }
 869             se.setNewRate(rate);
 870             se.setProbability(100);
 871           }
 872         }
 873         // merge the original ScheduleNode to the source ScheduleNode
 874         ((ScheduleNode)se.getSource()).mergeSEdge(se);
 875         scheduleNodes.remove(se.getTarget());
 876         scheduleEdges.remove(se);
 877         // As se has been changed into an internal edge inside a ScheduleNode,
 878         // change the source and target of se from original ScheduleNodes
 879         // into ClassNodes.
 880         if(se.getType() == ScheduleEdge.NEWEDGE) {
 881           se.setTarget(se.getTargetCNode());
 882           //se.setSource(se.getSourceCNode());
 883           //se.getTargetCNode().addEdge(se);
 884           se.getSourceCNode().addEdge(se);
 885         }
 886       } else {
 887         // clone the whole ScheduleNode lists starting with se's target
 888         for(int j = 1; j < repeat; j++ ) {
 889           cloneSNodeList(se, true);
 890         }
 891         se.setNewRate(1);
 892         se.setProbability(100);
 893       }
 894     } catch (Exception e) {
 895       e.printStackTrace();
 896       System.exit(-1);
 897     }
 898   }
 899
 900   private void cloneSNodeList(ScheduleEdge sEdge,
 901       boolean copyIE) throws Exception {
 902     Hashtable<ClassNode, ClassNode> cn2cn =
 903       new Hashtable<ClassNode, ClassNode>(); // hashtable from classnode in
 904                                              // orignal se's targe to cloned one
 905     ScheduleNode csNode =
 906       (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
 907     scheduleNodes.add(csNode);
 908
 909     // Clone all the external in ScheduleEdges
 910     int i;
 911     if(copyIE) {
 912       Vector inedges = sEdge.getTarget().getInedgeVector();
 913       for(i = 0; i < inedges.size(); i++) {
 914         ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
 915         ScheduleEdge se;
 916         switch(tse.getType()) {
 917         case ScheduleEdge.NEWEDGE: {
 918           se = new ScheduleEdge(csNode,"new",tse.getFstate(),tse.getType(),0);
 919           se.setProbability(100);
 920           se.setNewRate(1);
 921           break;
 922         }
 923
 924         case ScheduleEdge.TRANSEDGE: {
 925           se = new ScheduleEdge(csNode,"transmit",tse.getFstate(),tse.getType(),0);
 926           se.setProbability(tse.getProbability());
 927           se.setNewRate(tse.getNewRate());
 928           break;
 929         }
 930
 931         default: {
 932           throw new Exception("Error: not valid ScheduleEdge here");
 933         }
 934         }
 935         se.setSourceCNode(tse.getSourceCNode());
 936         se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
 937         se.setFEdge(tse.getFEdge());
 938         se.setTargetFState(tse.getTargetFState());
 939         se.setIsclone(true);
 940         tse.getSource().addEdge(se);
 941         scheduleEdges.add(se);
 942       }
 943       inedges = null;
 944     } else {
 945       sEdge.getTarget().removeInedge(sEdge);
 946       sEdge.setTarget(csNode);
 947       csNode.getInedgeVector().add(sEdge);
 948       sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
 949       sEdge.setIsclone(true);
 950     }
 951
 952     Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>(); // all nodes to be cloned
 953     Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>();  //clone nodes
 954     Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>(); // queue of the mappings of classnodes inside cloned ScheduleNode
 955     Vector<ScheduleNode> origins = new Vector<ScheduleNode>();  // queue of source ScheduleNode cloned
 956     Hashtable<ScheduleNode, ScheduleNode> sn2sn =
 957       new Hashtable<ScheduleNode, ScheduleNode>(); // mapping from cloned ScheduleNode to clone ScheduleNode
 958     clone.add(csNode);
 959     toClone.add((ScheduleNode)sEdge.getTarget());
 960     origins.addElement((ScheduleNode)sEdge.getTarget());
 961     sn2sn.put((ScheduleNode)sEdge.getTarget(), csNode);
 962     qcn2cn.add(cn2cn);
 963     while(!toClone.isEmpty()) {
 964       Hashtable<ClassNode, ClassNode> tocn2cn =
 965         new Hashtable<ClassNode, ClassNode>();
 966       csNode = clone.poll();
 967       ScheduleNode osNode = toClone.poll();
 968       cn2cn = qcn2cn.poll();
 969       // Clone all the external ScheduleEdges and the following ScheduleNodes
 970       Vector edges = osNode.getEdgeVector();
 971       for(i = 0; i < edges.size(); i++) {
 972         ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
 973         ScheduleNode tSNode =
 974           (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
 975         scheduleNodes.add(tSNode);
 976         clone.add(tSNode);
 977         toClone.add((ScheduleNode)tse.getTarget());
 978         origins.addElement((ScheduleNode)tse.getTarget());
 979         sn2sn.put((ScheduleNode)tse.getTarget(), tSNode);
 980         qcn2cn.add(tocn2cn);
 981         ScheduleEdge se = null;
 982         switch(tse.getType()) {
 983         case ScheduleEdge.NEWEDGE: {
 984           se = new ScheduleEdge(tSNode,"new",tse.getFstate(),tse.getType(),0);
 985           break;
 986         }
 987
 988         case ScheduleEdge.TRANSEDGE: {
 989           se = new ScheduleEdge(tSNode,"transmit",tse.getFstate(),tse.getType(),0);
 990           break;
 991         }
 992
 993         default: {
 994           throw new Exception("Error: not valid ScheduleEdge here");
 995         }
 996         }
 997         se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
 998         se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
 999         se.setFEdge(tse.getFEdge());
1000         se.setTargetFState(tse.getTargetFState());
1001         se.setProbability(tse.getProbability());
1002         se.setNewRate(tse.getNewRate());
1003         se.setIsclone(true);
1004         csNode.addEdge(se);
1005         scheduleEdges.add(se);
1006       }
1007       tocn2cn = null;
1008       edges = null;
1009     }
1010
1011     toClone = null;
1012     clone = null;
1013     qcn2cn = null;
1014     cn2cn.clear();
1015     cn2cn = null;
1016     origins = null;
1017     sn2sn = null;
1018   }
1019
1020   private long calInExeTime(FlagState fs) throws Exception {
1021     long exeTime = 0;
1022     ClassDescriptor cd = fs.getClassDescriptor();
1023     ClassNode cNode = cd2ClassNode.get(cd);
1024     exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
1025     while(true) {
1026       Vector inedges = cNode.getInedgeVector();
1027       // Now that there are associate ScheduleEdges, there may be
1028       // multiple inedges of a ClassNode
1029       if(inedges.size() > 1) {
1030         throw new Exception("Error: ClassNode's inedges more than one!");
1031       }
1032       if(inedges.size() > 0) {
1033         ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
1034         cNode = (ClassNode)sEdge.getSource();
1035         exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
1036       } else {
1037         break;
1038       }
1039       inedges = null;
1040     }
1041     exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
1042     return exeTime;
1043   }
1044
1045   private ScheduleNode splitSNode(ScheduleEdge se,
1046       boolean copy) {
1047     assert(ScheduleEdge.NEWEDGE == se.getType());
1048
1049     FEdge fe = se.getFEdge();
1050     FlagState fs = (FlagState)fe.getTarget();
1051     FlagState nfs = (FlagState)fs.clone();
1052     fs.getEdgeVector().removeAllElements();
1053     nfs.getInedgeVector().removeAllElements();
1054     ClassNode sCNode = se.getSourceCNode();
1055
1056     // split the subtree whose root is nfs from the whole flag transition tree
1057     Vector<FlagState> sfss = sCNode.getFlagStates();
1058     Vector<FlagState> fStates = new Vector<FlagState>();
1059     Queue<FlagState> toiterate = new LinkedList<FlagState>();
1060     toiterate.add(nfs);
1061     fStates.add(nfs);
1062     while(!toiterate.isEmpty()) {
1063       FlagState tfs = toiterate.poll();
1064       Iterator it_edges = tfs.edges();
1065       while(it_edges.hasNext()) {
1066         FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
1067         if(!fStates.contains(temp)) {
1068           fStates.add(temp);
1069           toiterate.add(temp);
1070           sfss.removeElement(temp);
1071         }
1072       }
1073       it_edges = null;
1074     }
1075     sfss = null;
1076     Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
1077     fStates = null;
1078     // create a ClassNode and ScheduleNode for this subtree
1079     ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
1080     ScheduleNode sNode = new ScheduleNode(cNode, 0);
1081     cNode.setScheduleNode(sNode);
1082     cNode.setSorted(true);
1083     cNode.setTransTime(sCNode.getTransTime());
1084     classNodes.add(cNode);
1085     scheduleNodes.add(sNode);
1086     try {
1087       sNode.calExeTime();
1088     } catch (Exception e) {
1089       e.printStackTrace();
1090     }
1091     // flush the exeTime of fs and its ancestors
1092     fs.setExeTime(0);
1093     toiterate.add(fs);
1094     while(!toiterate.isEmpty()) {
1095       FlagState tfs = toiterate.poll();
1096       long ttime = tfs.getExeTime();
1097       Iterator it_inedges = tfs.inedges();
1098       while(it_inedges.hasNext()) {
1099         FEdge fEdge = (FEdge)it_inedges.next();
1100         FlagState temp = (FlagState)fEdge.getSource();
1101         long time = fEdge.getExeTime() + ttime;
1102         if(temp.getExeTime() > time) {
1103           temp.setExeTime(time);
1104           toiterate.add(temp);
1105         }
1106       }
1107       it_inedges = null;
1108     }
1109     toiterate = null;
1110
1111     // create a 'trans' ScheudleEdge between this new ScheduleNode and se's
1112     // source ScheduleNode
1113     ScheduleEdge sEdge =
1114       new ScheduleEdge(sNode, "transmit", fs, ScheduleEdge.TRANSEDGE, 0);
1115     sEdge.setFEdge(fe);
1116     sEdge.setSourceCNode(sCNode);
1117     sEdge.setTargetCNode(cNode);
1118     sEdge.setTargetFState(nfs);
1119     // TODO
1120     // Add calculation codes for calculating transmit time of an object
1121     sEdge.setTransTime(cNode.getTransTime());
1122     se.getSource().addEdge(sEdge);
1123     scheduleEdges.add(sEdge);
1124     // remove the ClassNodes and internal ScheduleEdges out of this subtree
1125     // to the new ScheduleNode
1126     ScheduleNode oldSNode = (ScheduleNode)se.getSource();
1127     Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
1128     Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
1129     Vector<ClassNode> rCNodes = new Vector<ClassNode>();
1130     rCNodes.addElement(sCNode);
1131     if(it_isEdges != null) {
1132       while(it_isEdges.hasNext()) {
1133         ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
1134         if(rCNodes.contains(tse.getSourceCNode())) {
1135           if(sCNode.equals(tse.getSourceCNode())) {
1136             if (!(tse.getSourceFState().equals(fs))
1137                 && (sFStates.contains(tse.getSourceFState()))) {
1138               tse.setSource(cNode);
1139               tse.setSourceCNode(cNode);
1140             } else {
1141               continue;
1142             }
1143           }
1144           sNode.getScheduleEdges().addElement(tse);
1145           sNode.getClassNodes().addElement(tse.getTargetCNode());
1146           rCNodes.addElement(tse.getTargetCNode());
1147           oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
1148           toremove.addElement(tse);
1149         }
1150       }
1151     }
1152     it_isEdges = null;
1153     oldSNode.getScheduleEdges().removeAll(toremove);
1154     toremove.clear();
1155     // redirect ScheudleEdges out of this subtree to the new ScheduleNode
1156     Iterator it_sEdges = se.getSource().edges();
1157     while(it_sEdges.hasNext()) {
1158       ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
1159       if(!(tse.equals(se)) && !(tse.equals(sEdge))
1160           && (tse.getSourceCNode().equals(sCNode))) {
1161         if(!(tse.getSourceFState().equals(fs))
1162             && (sFStates.contains(tse.getSourceFState()))) {
1163           tse.setSource(sNode);
1164           tse.setSourceCNode(cNode);
1165           sNode.getEdgeVector().addElement(tse);
1166           toremove.add(tse);
1167         }
1168       }
1169     }
1170     it_sEdges = null;
1171     se.getSource().getEdgeVector().removeAll(toremove);
1172     toremove = null;
1173     rCNodes = null;
1174     sFStates = null;
1175
1176     try {
1177       if(!copy) {
1178         //merge se into its source ScheduleNode
1179         sNode.setCid(((ScheduleNode)se.getSource()).getCid());
1180         ((ScheduleNode)se.getSource()).mergeSEdge(se);
1181         scheduleNodes.remove(se.getTarget());
1182         scheduleEdges.removeElement(se);
1183         // As se has been changed into an internal edge inside a ScheduleNode,
1184         // change the source and target of se from original ScheduleNodes
1185         // into ClassNodes.
1186         if(se.getType() == ScheduleEdge.NEWEDGE) {
1187           se.setTarget(se.getTargetCNode());
1188           //se.setSource(se.getSourceCNode());
1189           //se.getTargetCNode().addEdge(se);
1190           se.getSourceCNode().addEdge(se);
1191         }
1192       } else {
1193         sNode.setCid(ScheduleNode.colorID++);
1194         handleScheduleEdge(se, true);
1195       }
1196     } catch (Exception e) {
1197       e.printStackTrace();
1198       System.exit(-1);
1199     }
1200
1201     return sNode;
1202   }
1203
1204   // TODO: restrict the number of generated scheduling according to the setted
1205   // scheduleThreshold
1206   private boolean coreMapping(int generateThreshold) throws Exception {
1207     if(this.coreNum == -1) {
1208       throw new Exception("Error: un-initialized coreNum when doing scheduling.");
1209     }
1210
1211     if(this.scheduleGraphs == null) {
1212       this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
1213     }
1214
1215     int reduceNum = this.scheduleNodes.size() - this.coreNum;
1216
1217     // Combine some ScheduleNode if necessary
1218     // May generate multiple graphs suggesting candidate schedulings
1219     if(!(reduceNum > 0)) {
1220       // Enough cores, no need to combine any ScheduleNode
1221       this.scheduleGraphs.addElement(this.scheduleNodes);
1222       int gid = 1;
1223       if(this.state.PRINTSCHEDULING) {
1224         String path = this.state.outputdir + "scheduling_" + gid + ".dot";
1225         SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
1226       }
1227       return false;
1228     } else {
1229       SchedulingUtil.assignCids(this.scheduleNodes);
1230
1231       // Go through all the Schedule Nodes, organize them in order of their cid
1232       Vector<Vector<ScheduleNode>> sNodeVecs =
1233         SchedulingUtil.rangeScheduleNodes(this.scheduleNodes);
1234
1235       CombinationUtil.RootsGenerator rGen =
1236         CombinationUtil.allocateRootsGenerator(sNodeVecs,
1237             this.coreNum);
1238
1239       int gid = 1;
1240       Random rand = new Random();
1241       boolean isBig = Math.pow(this.coreNum, reduceNum) > 1000;
1242       while((!isBig || (gid <= this.scheduleThreshold)) && (rGen.nextGen())) {
1243         // first get the chosen rootNodes
1244         Vector<Vector<ScheduleNode>> rootNodes = rGen.getRootNodes();
1245         Vector<Vector<ScheduleNode>> nodes2combine = rGen.getNode2Combine();
1246
1247         CombinationUtil.CombineGenerator cGen =
1248           CombinationUtil.allocateCombineGenerator(rootNodes,
1249               nodes2combine);
1250         while((!isBig || (gid <= this.scheduleThreshold)) && (cGen.nextGen())) {
1251           boolean implement = true;
1252           if(isBig) {
1253             implement = Math.abs(rand.nextInt()) % 100 > generateThreshold;
1254           }
1255           if(implement) {
1256             Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
1257             Vector<ScheduleNode> sNodes =
1258               SchedulingUtil.generateScheduleGraph(this.state,
1259                   this.scheduleNodes,
1260                   this.scheduleEdges,
1261                   rootNodes,
1262                   combine,
1263                   gid++);
1264             this.scheduleGraphs.add(sNodes);
1265             combine = null;
1266             sNodes = null;
1267           }
1268         }
1269         cGen.clear();
1270         rootNodes = null;
1271         nodes2combine = null;
1272       }
1273       rGen.clear();
1274       sNodeVecs = null;
1275       return isBig;
1276     }
1277   }
1278
1279   static class TaskInfo {
1280     public int m_numofexits;
1281     public long[] m_exetime;
1282     public double[] m_probability;
1283     public Vector<Hashtable<String, Integer>> m_newobjinfo;
1284     public int m_byObj;
1285
1286     public TaskInfo(int numofexits) {
1287       this.m_numofexits = numofexits;
1288       this.m_exetime = new long[this.m_numofexits];
1289       this.m_probability = new double[this.m_numofexits];
1290       this.m_newobjinfo = new Vector<Hashtable<String, Integer>>();
1291       for(int i = 0; i < this.m_numofexits; i++) {
1292         this.m_newobjinfo.add(null);
1293       }
1294       this.m_byObj = -1;
1295     }
1296   }
1297 }