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