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