Robust/src/Analysis/Scheduling/ScheduleAnalysis.java

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