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