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, 0);//new ScheduleEdge(sNode, "new", cd, 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         // Do topology sort of the ClassNodes and ScheduleEdges.
 165         Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
 166         Vector<ScheduleNode> tempSNodes = ClassNode.DFS.topology(scheduleNodes, ssev);
 167         scheduleNodes.removeAllElements();
 168         scheduleNodes = tempSNodes;
 169         tempSNodes = null;
 170         scheduleEdges.removeAllElements();
 171         scheduleEdges = ssev;
 172         ssev = null;
 173         sorted = true;
 174
 175         // Break down the 'cycle's
 176         for(i = 0; i < toBreakDown.size(); i++ ) {
 177             cloneSNodeList(toBreakDown.elementAt(i), false);
 178         }
 179         toBreakDown = null;
 180
 181         // Remove fake 'new' edges
 182         for(i = 0; i < scheduleEdges.size(); i++) {
 183             ScheduleEdge se = scheduleEdges.elementAt(i);
 184             if((0 == se.getNewRate()) || (0 == se.getProbability())) {
 185                 scheduleEdges.removeElement(se);
 186                 scheduleNodes.removeElement(se.getTarget());
 187             }
 188         }
 189
 190         SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes);
 191     }
 192
 193     public void scheduleAnalysis() {
 194         // First iteration
 195         int i = 0;
 196         //Access the ScheduleEdges in reverse topology order
 197         Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses = new Hashtable<FEdge, Vector<ScheduleEdge>>();
 198         Hashtable<ScheduleNode, Vector<FEdge>> sn2fes = new Hashtable<ScheduleNode, Vector<FEdge>>();
 199         ScheduleNode preSNode = null;
 200         for(i = scheduleEdges.size(); i > 0; i--) {
 201             ScheduleEdge se = scheduleEdges.elementAt(i-1);
 202             if(preSNode == null) {
 203                 preSNode = (ScheduleNode)se.getSource();
 204             }
 205             if(se.getIsNew()) {
 206                 boolean split = false;
 207                 FEdge fe = se.getFEdge();
 208                 if(fe.getSource() == fe.getTarget()) {
 209                     // back edge
 210                     int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
 211                     int rate = 0;
 212                     if(repeat > 1){
 213                         for(int j = 1; j< repeat; j++ ) {
 214                             cloneSNodeList(se, true);
 215                         }
 216                         se.setNewRate(1);
 217                         se.setProbability(100);
 218                     }
 219                     try {
 220                         rate = (int)Math.ceil(se.getListExeTime()/ calInExeTime(se.getSourceFState()));
 221                     } catch (Exception e) {
 222                         e.printStackTrace();
 223                     }
 224                     for(int j = rate - 1; j > 0; j--) {
 225                         for(int k = repeat; k > 0; k--) {
 226                             cloneSNodeList(se, true);
 227                         }
 228                     }
 229                 } else {
 230                     // if preSNode is not the same as se's source ScheduleNode
 231                     // handle any ScheduleEdges previously put into fe2ses whose source ScheduleNode is preSNode
 232                     boolean same = (preSNode == se.getSource());
 233                     if(!same) {
 234                         if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()) {
 235                             if(sn2fes.containsKey(preSNode)) {
 236                                 Vector<FEdge> fes = sn2fes.remove(preSNode);
 237                                 for(int j = 0; j < fes.size(); j++) {
 238                                     FEdge tempfe = fes.elementAt(j);
 239                                     Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 240                                     ScheduleEdge tempse = ses.elementAt(0);
 241                                     int temptime = tempse.getListExeTime();
 242                                     // find out the ScheduleEdge with least exeTime
 243                                     for(int k = 1; k < ses.size(); k++) {
 244                                         int ttemp = ses.elementAt(k).getListExeTime();
 245                                         if(ttemp < temptime) {
 246                                             tempse = ses.elementAt(k);
 247                                             temptime = ttemp;
 248                                         }
 249                                     }
 250                                     // handle the tempse
 251                                     handleScheduleEdge(tempse, true);
 252                                     ses.removeElement(tempse);
 253                                     // handle other ScheduleEdges
 254                                     for(int k = 0; k < ses.size(); k++) {
 255                                         handleScheduleEdge(ses.elementAt(k), false);
 256                                     }
 257                                     ses = null;
 258                                     fe2ses.remove(tempfe);
 259                                 }
 260                                 fes = null;
 261                             }
 262                         }
 263                         preSNode = (ScheduleNode)se.getSource();
 264                     }
 265
 266                     // if fe is the last task inside this ClassNode, delay the expanding and merging until we find all such 'nmew' edges
 267                     // associated with a last task inside this ClassNode
 268                     if(!fe.getTarget().edges().hasNext()) {
 269                         if(fe2ses.get(fe) == null) {
 270                             fe2ses.put(fe, new Vector<ScheduleEdge>());
 271                         }
 272                         if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
 273                             sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
 274                         }
 275                         fe2ses.get(fe).add(se);
 276                         sn2fes.get((ScheduleNode)se.getSource()).add(fe);
 277                     } else {
 278                         // As this is not a last task, first handle available ScheduleEdges previously put into fe2ses
 279                         if((same) && (sn2fes.containsKey(preSNode))) {
 280                             Vector<FEdge> fes = sn2fes.remove(preSNode);
 281                             for(int j = 0; j < fes.size(); j++) {
 282                                 FEdge tempfe = fes.elementAt(j);
 283                                 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 284                                 ScheduleEdge tempse = ses.elementAt(0);
 285                                 int temptime = tempse.getListExeTime();
 286                                 // find out the ScheduleEdge with least exeTime
 287                                 for(int k = 1; k < ses.size(); k++) {
 288                                     int ttemp = ses.elementAt(k).getListExeTime();
 289                                     if(ttemp < temptime) {
 290                                         tempse = ses.elementAt(k);
 291                                         temptime = ttemp;
 292                                     }
 293                                 }
 294                                 // handle the tempse
 295                                 handleScheduleEdge(tempse, true);
 296                                 ses.removeElement(tempse);
 297                                 // handle other ScheduleEdges
 298                                 for(int k = 0; k < ses.size(); k++) {
 299                                     handleScheduleEdge(ses.elementAt(k), false);
 300                                 }
 301                                 ses = null;
 302                                 fe2ses.remove(tempfe);
 303                             }
 304                             fes = null;
 305                         }
 306
 307                         if((!(se.getTransTime() < this.transThreshold)) && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
 308                             split = true;
 309                             splitSNode(se, true);
 310                         } else {
 311                             // handle this ScheduleEdge
 312                             handleScheduleEdge(se, true);
 313                         }
 314                     }
 315                 }
 316             }
 317         }
 318         if(!fe2ses.isEmpty()) {
 319             Set<FEdge> keys = fe2ses.keySet();
 320             Iterator it_keys = keys.iterator();
 321             while(it_keys.hasNext()) {
 322                 FEdge tempfe = (FEdge)it_keys.next();
 323                 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 324                 ScheduleEdge tempse = ses.elementAt(0);
 325                 int temptime = tempse.getListExeTime();
 326                 // find out the ScheduleEdge with least exeTime
 327                 for(int k = 1; k < ses.size(); k++) {
 328                     int ttemp = ses.elementAt(k).getListExeTime();
 329                     if(ttemp < temptime) {
 330                         tempse = ses.elementAt(k);
 331                         temptime = ttemp;
 332                     }
 333                 }
 334                 // handle the tempse
 335                 handleScheduleEdge(tempse, true);
 336                 ses.removeElement(tempse);
 337                 // handle other ScheduleEdges
 338                 for(int k = 0; k < ses.size(); k++) {
 339                     handleScheduleEdge(ses.elementAt(k), false);
 340                 }
 341                 ses = null;
 342             }
 343             keys = null;
 344             fe2ses.clear();
 345             sn2fes.clear();
 346         }
 347         fe2ses = null;
 348         sn2fes = null;
 349
 350         SchedulingUtil.printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
 351     }
 352
 353     private void handleScheduleEdge(ScheduleEdge se, boolean merge) {
 354         int rate = 0;
 355         int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
 356         if(merge) {
 357             try {
 358                 rate = (int)Math.ceil((se.getTransTime() - calInExeTime(se.getSourceFState()))/ se.getListExeTime());
 359                 if(rate < 0 ) {
 360                     rate = 0;
 361                 }
 362             } catch (Exception e) {
 363                 e.printStackTrace();
 364             }
 365             if(0 == rate) {
 366                 // clone the whole ScheduleNode lists starting with se's target
 367                 for(int j = 1; j < repeat; j++ ) {
 368                     cloneSNodeList(se, true);
 369                 }
 370                 se.setNewRate(1);
 371                 se.setProbability(100);
 372             } else {
 373                 repeat -= rate;
 374                 if(repeat > 0){
 375                     // clone the whole ScheduleNode lists starting with se's target
 376                     for(int j = 0; j < repeat; j++ ) {
 377                         cloneSNodeList(se, true);
 378                     }
 379                     se.setNewRate(rate);
 380                     se.setProbability(100);
 381                 }
 382             }
 383             // merge the original ScheduleNode to the source ScheduleNode
 384             ((ScheduleNode)se.getSource()).mergeSEdge(se);
 385             scheduleNodes.remove(se.getTarget());
 386             scheduleEdges.remove(se);
 387             // As se has been changed into an internal edge inside a ScheduleNode,
 388             // change the source and target of se from original ScheduleNodes into ClassNodes.
 389             se.setTarget(se.getTargetCNode());
 390             se.setSource(se.getSourceCNode());
 391         } else {
 392             // clone the whole ScheduleNode lists starting with se's target
 393             for(int j = 1; j < repeat; j++ ) {
 394                 cloneSNodeList(se, true);
 395             }
 396             se.setNewRate(1);
 397             se.setProbability(100);
 398         }
 399     }
 400
 401     private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) {
 402         Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
 403         ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
 404         scheduleNodes.add(csNode);
 405
 406         // Clone all the external in ScheduleEdges
 407         int i;
 408         if(copyIE) {
 409             Vector inedges = sEdge.getTarget().getInedgeVector();
 410             for(i = 0; i < inedges.size(); i++) {
 411                 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
 412                 ScheduleEdge se;
 413                 if(tse.getIsNew()) {
 414                     se = new ScheduleEdge(csNode, "new", tse.getFstate(), tse.getIsNew(), 0); //new ScheduleEdge(csNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0);
 415                     se.setProbability(100);
 416                     se.setNewRate(1);
 417                 } else {
 418                     se = new ScheduleEdge(csNode, "transmit", tse.getFstate(), false, 0);//new ScheduleEdge(csNode, "transmit", tse.getClassDescriptor(), false, 0);
 419                 }
 420                 se.setSourceCNode(tse.getSourceCNode());
 421                 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
 422                 se.setFEdge(tse.getFEdge());
 423                 se.setTargetFState(tse.getTargetFState());
 424                 se.setIsclone(true);
 425                 tse.getSource().addEdge(se);
 426                 scheduleEdges.add(se);
 427             }
 428             inedges = null;
 429         } else {
 430             sEdge.getTarget().removeInedge(sEdge);
 431             sEdge.setTarget(csNode);
 432             csNode.getInedgeVector().add(sEdge);
 433             sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
 434             //sEdge.setTargetFState(null);
 435             sEdge.setIsclone(true);
 436         }
 437
 438         Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>();
 439         Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>();
 440         Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>();
 441         clone.add(csNode);
 442         toClone.add((ScheduleNode)sEdge.getTarget());
 443         qcn2cn.add(cn2cn);
 444         while(!toClone.isEmpty()) {
 445             Hashtable<ClassNode, ClassNode> tocn2cn = new Hashtable<ClassNode, ClassNode>();
 446             csNode = clone.poll();
 447             ScheduleNode osNode = toClone.poll();
 448             cn2cn = qcn2cn.poll();
 449             // Clone all the external ScheduleEdges and the following ScheduleNodes
 450             Vector edges = osNode.getEdgeVector();
 451             for(i = 0; i < edges.size(); i++) {
 452                 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
 453                 ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
 454                 scheduleNodes.add(tSNode);
 455                 clone.add(tSNode);
 456                 toClone.add((ScheduleNode)tse.getTarget());
 457                 qcn2cn.add(tocn2cn);
 458                 ScheduleEdge se = null;
 459                 if(tse.getIsNew()) {
 460                     se = new ScheduleEdge(tSNode, "new", tse.getFstate(), tse.getIsNew(), 0);//new ScheduleEdge(tSNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0);
 461                     se.setProbability(tse.getProbability());
 462                     se.setNewRate(tse.getNewRate());
 463                 } else {
 464                     se = new ScheduleEdge(tSNode, "transmit", tse.getFstate(), false, 0);//new ScheduleEdge(tSNode, "transmit", tse.getClassDescriptor(), false, 0);
 465                 }
 466                 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
 467                 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
 468                 se.setFEdge(tse.getFEdge());
 469                 se.setTargetFState(tse.getTargetFState());
 470                 se.setIsclone(true);
 471                 csNode.addEdge(se);
 472                 scheduleEdges.add(se);
 473             }
 474             tocn2cn = null;
 475             edges = null;
 476         }
 477         toClone = null;
 478         clone = null;
 479         qcn2cn = null;
 480         cn2cn = null;
 481     }
 482
 483     private int calInExeTime(FlagState fs) throws Exception {
 484         int exeTime = 0;
 485         ClassDescriptor cd = fs.getClassDescriptor();
 486         ClassNode cNode = cd2ClassNode.get(cd);
 487         exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
 488         while(true) {
 489             Vector inedges = cNode.getInedgeVector();
 490             if(inedges.size() > 1) {
 491                 throw new Exception("Error: ClassNode's inedges more than one!");
 492             }
 493             if(inedges.size() > 0) {
 494                 ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
 495                 cNode = (ClassNode)sEdge.getSource();
 496                 exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
 497             }else {
 498                 break;
 499             }
 500             inedges = null;
 501         }
 502         exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
 503         return exeTime;
 504     }
 505
 506     private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) {
 507         FEdge fe = se.getFEdge();
 508         FlagState fs = (FlagState)fe.getTarget();
 509         FlagState nfs = (FlagState)fs.clone();
 510         fs.getEdgeVector().removeAllElements();
 511         nfs.getInedgeVector().removeAllElements();
 512         ClassNode sCNode = se.getSourceCNode();
 513
 514         // split the subtree whose root is nfs from the whole flag transition tree
 515         Vector<FlagState> sfss = sCNode.getFlagStates();
 516         Vector<FlagState> fStates = new Vector<FlagState>();
 517         Queue<FlagState> toiterate = new LinkedList<FlagState>();
 518         toiterate.add(nfs);
 519         fStates.add(nfs);
 520         while(!toiterate.isEmpty()){
 521             FlagState tfs = toiterate.poll();
 522             Iterator it_edges = tfs.edges();
 523             while(it_edges.hasNext()) {
 524                 FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
 525                 if(!fStates.contains(temp)) {
 526                     fStates.add(temp);
 527                     toiterate.add(temp);
 528                     sfss.removeElement(temp);
 529                 }
 530             }
 531         }
 532         sfss = null;
 533         Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
 534         fStates = null;
 535         // create a ClassNode and ScheduleNode for this subtree
 536         ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
 537         ScheduleNode sNode = new ScheduleNode(cNode, 0);
 538         cNode.setScheduleNode(sNode);
 539         cNode.setSorted(true);
 540         cNode.setTransTime(sCNode.getTransTime());
 541         classNodes.add(cNode);
 542         scheduleNodes.add(sNode);
 543         try {
 544             sNode.calExeTime();
 545         } catch (Exception e) {
 546             e.printStackTrace();
 547         }
 548         // flush the exeTime of fs and its ancestors
 549         fs.setExeTime(0);
 550         toiterate.add(fs);
 551         while(!toiterate.isEmpty()) {
 552             FlagState tfs = toiterate.poll();
 553             int ttime = tfs.getExeTime();
 554             Iterator it_inedges = tfs.inedges();
 555             while(it_inedges.hasNext()) {
 556                 FEdge fEdge = (FEdge)it_inedges.next();
 557                 FlagState temp = (FlagState)fEdge.getSource();
 558                 int time = fEdge.getExeTime() + ttime;
 559                 if(temp.getExeTime() > time) {
 560                     temp.setExeTime(time);
 561                     toiterate.add(temp);
 562                 }
 563             }
 564         }
 565         toiterate = null;
 566
 567         // create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode
 568         ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", fs, false, 0);//new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
 569         sEdge.setFEdge(fe);
 570         sEdge.setSourceCNode(sCNode);
 571         sEdge.setTargetCNode(cNode);
 572         sEdge.setTargetFState(nfs);
 573         // todo
 574         // Add calculation codes for calculating transmit time of an object
 575         sEdge.setTransTime(cNode.getTransTime());
 576         se.getSource().addEdge(sEdge);
 577         scheduleEdges.add(sEdge);
 578         // remove the ClassNodes and internal ScheduleEdges out of this subtree to the new ScheduleNode
 579         ScheduleNode oldSNode = (ScheduleNode)se.getSource();
 580         Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
 581         Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
 582         Vector<ClassNode> rCNodes = new Vector<ClassNode>();
 583         rCNodes.addElement(sCNode);
 584         if(it_isEdges != null){
 585             while(it_isEdges.hasNext()) {
 586                 ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
 587                 if(rCNodes.contains(tse.getSourceCNode())) {
 588                     if(sCNode == tse.getSourceCNode()) {
 589                         if ((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
 590                             tse.setSource(cNode);
 591                             tse.setSourceCNode(cNode);
 592                         } else {
 593                             continue;
 594                         }
 595                     }
 596                     sNode.getScheduleEdges().addElement(tse);
 597                     sNode.getClassNodes().addElement(tse.getTargetCNode());
 598                     rCNodes.addElement(tse.getTargetCNode());
 599                     oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
 600                     toremove.addElement(tse);
 601                 }
 602             }
 603         }
 604         oldSNode.getScheduleEdges().removeAll(toremove);
 605         toremove.clear();
 606         // redirect ScheudleEdges out of this subtree to the new ScheduleNode
 607         Iterator it_sEdges = se.getSource().edges();
 608         //Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
 609         while(it_sEdges.hasNext()) {
 610             ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
 611             if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
 612                 if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
 613                     tse.setSource(sNode);
 614                     tse.setSourceCNode(cNode);
 615                     sNode.getEdgeVector().addElement(tse);
 616                     toremove.add(tse);
 617                 }
 618             }
 619         }
 620         se.getSource().getEdgeVector().removeAll(toremove);
 621         toremove = null;
 622         sFStates = null;
 623
 624         if(!copy) {
 625             //merge se into its source ScheduleNode
 626             ((ScheduleNode)se.getSource()).mergeSEdge(se);
 627             scheduleNodes.remove(se.getTarget());
 628             scheduleEdges.removeElement(se);
 629             // As se has been changed into an internal edge inside a ScheduleNode,
 630             // change the source and target of se from original ScheduleNodes into ClassNodes.
 631             se.setTarget(se.getTargetCNode());
 632             se.setSource(se.getSourceCNode());
 633         } else {
 634             handleScheduleEdge(se, true);
 635         }
 636
 637         return sNode;
 638     }
 639
 640     public void schedule() throws Exception {
 641         if(this.coreNum == -1) {
 642             throw new Exception("Error: un-initialized coreNum when doing scheduling.");
 643         }
 644
 645         if(this.scheduleGraphs == null) {
 646             this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
 647         }
 648
 649         int reduceNum = this.scheduleNodes.size() - this.coreNum;
 650
 651         // Enough cores, no need to merge more ScheduleEdge
 652         if(!(reduceNum > 0)) {
 653             this.scheduleGraphs.addElement(this.scheduleNodes);
 654         } else {
 655             // sort the ScheduleEdges in dececending order of transmittime
 656             Vector<ScheduleEdge> sEdges = new Vector<ScheduleEdge>();
 657             sEdges.addElement(this.scheduleEdges.elementAt(0));
 658             for(int i = 1; i < this.scheduleEdges.size(); i++) {
 659                 ScheduleEdge temp = this.scheduleEdges.elementAt(i);
 660                 int j = sEdges.size() - 1;
 661                 do {
 662                     if(temp.getTransTime() > sEdges.elementAt(j--).getTransTime()) {
 663                         break;
 664                     }
 665                 } while(j >= 0);
 666                 sEdges.add(j+1, temp);
 667             }
 668
 669             int temp = sEdges.elementAt(reduceNum - 1).getTransTime();
 670             for(int i = sEdges.size() - 1; i > reduceNum - 1; i--) {
 671                 if(sEdges.elementAt(i).getTransTime() != temp) {
 672                     sEdges.removeElementAt(i);
 673                 } else {
 674                     break;
 675                 }
 676             }
 677             int start = reduceNum - 2;
 678             for(; start >= 0; start--) {
 679                 if(sEdges.elementAt(start).getTransTime() != temp) {
 680                     start++;
 681                     reduceNum -= start;
 682                     break;
 683                 }
 684             }
 685             if(start < 0) {
 686                 start = 0;
 687             }
 688
 689             // generate scheduling
 690             Vector candidates = new Vector();
 691             for(int i = start; i < sEdges.size(); i++) {
 692                 candidates.addElement(Integer.valueOf(i));
 693             }
 694             Combination combGen = new Combination(candidates, reduceNum);
 695             int gid = 1;
 696             do {
 697                 Vector toreduce = combGen.next();
 698                 if(toreduce != null) {
 699                     Vector<ScheduleEdge> reduceEdges = new Vector<ScheduleEdge>();
 700                     for(int i = 0; i < start; i++) {
 701                         reduceEdges.add(sEdges.elementAt(i));
 702                     }
 703                     for(int i = 0; i < toreduce.size(); i++) {
 704                         reduceEdges.add(sEdges.elementAt(((Integer)toreduce.elementAt(i)).intValue()));
 705                     }
 706                     Vector<ScheduleNode> sNodes = generateScheduling(reduceEdges, gid++);
 707                     this.scheduleGraphs.add(sNodes);
 708                     reduceEdges = null;
 709                     sNodes = null;
 710                 } else {
 711                     break;
 712                 }
 713                 toreduce = null;
 714             }while(true);
 715             sEdges = null;
 716             candidates = null;
 717
 718         }
 719
 720         if(this.schedulings == null) {
 721             this.schedulings = new Vector<Vector<Schedule>>();
 722         }
 723
 724         for(int i = 0; i < this.scheduleGraphs.size(); i++) {
 725             Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
 726             Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
 727             // for each ScheduleNode create a schedule node representing a core
 728             Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
 729             int j = 0;
 730             for(j = 0; j < scheduleGraph.size(); j++) {
 731                 sn2coreNum.put(scheduleGraph.elementAt(j), j);
 732             }
 733             int startupcore = 0;
 734             boolean setstartupcore = false;
 735             Schedule startup = null;
 736             Vector<Integer> leafcores = new Vector<Integer>();
 737             Vector[] ancestorCores = new Vector[this.coreNum];
 738             for(j = 0; j < ancestorCores.length; ++j) {
 739                 ancestorCores[j] = new Vector();
 740             }
 741             for(j = 0; j < scheduleGraph.size(); j++) {
 742                 Schedule tmpSchedule = new Schedule(j);
 743                 ScheduleNode sn = scheduleGraph.elementAt(j);
 744
 745                 Vector<ClassNode> cNodes = sn.getClassNodes();
 746                 for(int k = 0; k < cNodes.size(); k++) {
 747                     Iterator it_flags = cNodes.elementAt(k).getFlags();
 748                     while(it_flags.hasNext()) {
 749                         FlagState fs = (FlagState)it_flags.next();
 750                         Iterator it_edges = fs.edges();
 751                         while(it_edges.hasNext()) {
 752                             TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
 753                             tmpSchedule.addTask(td);
 754                             if(td.getParamType(0).getClassDesc().getSymbol().equals(TypeUtil.StartupClass)) {
 755                                 assert(!setstartupcore);
 756                                 startupcore = j;
 757                                 startup = tmpSchedule;
 758                                 setstartupcore = true;
 759                             }
 760                         }
 761                     }
 762                 }
 763
 764                 // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
 765                 Iterator it_edges = sn.edges();
 766                 if(!it_edges.hasNext()) {
 767                     // leaf core, considered as ancestor of startup core
 768                     if(!leafcores.contains(Integer.valueOf(j))) {
 769                         leafcores.addElement(Integer.valueOf(j));
 770                     }
 771                 }
 772                 while(it_edges.hasNext()) {
 773                     ScheduleEdge se = (ScheduleEdge)it_edges.next();
 774                     ScheduleNode target = (ScheduleNode)se.getTarget();
 775                     Integer targetcore = sn2coreNum.get(target);
 776                     if(se.getIsNew()) {
 777                         for(int k = 0; k < se.getNewRate(); k++) {
 778                             tmpSchedule.addTargetCore(se.getFstate(), targetcore);
 779                         }
 780                     } else {
 781                         // 'transmit' edge
 782                         tmpSchedule.addTargetCore(se.getFstate(), targetcore, se.getTargetFState());
 783                     }
 784                     tmpSchedule.addChildCores(targetcore);
 785                     if((targetcore.intValue() != j) && (!ancestorCores[targetcore.intValue()].contains((Integer.valueOf(j))))) {
 786                         ancestorCores[targetcore.intValue()].addElement(Integer.valueOf(j));
 787                     }
 788                 }
 789                 it_edges = sn.getScheduleEdgesIterator();
 790                 while(it_edges.hasNext()) {
 791                     ScheduleEdge se = (ScheduleEdge)it_edges.next();
 792                     if(se.getIsNew()) {
 793                         for(int k = 0; k < se.getNewRate(); k++) {
 794                             tmpSchedule.addTargetCore(se.getFstate(), j);
 795                         }
 796                     } else {
 797                         // 'transmit' edge
 798                         tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState());
 799                     }
 800                 }
 801                 scheduling.add(tmpSchedule);
 802             }
 803             leafcores.removeElement(Integer.valueOf(startupcore));
 804             ancestorCores[startupcore] = leafcores;
 805             for(j = 0; j < this.coreNum; ++j) {
 806                 scheduling.elementAt(j).setAncestorCores(ancestorCores[j]);
 807             }
 808             this.schedulings.add(scheduling);
 809         }
 810
 811     }
 812
 813     public Vector<ScheduleNode> generateScheduling(Vector<ScheduleEdge> reduceEdges, int gid) {
 814         Vector<ScheduleNode> result = new Vector<ScheduleNode>();
 815
 816         // clone the ScheduleNodes
 817         Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
 818         Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
 819         for(int i = 0; i < this.scheduleNodes.size(); i++) {
 820             Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
 821             ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
 822             ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
 823             result.add(i, temp);
 824             sn2hash.put(temp, cn2cn);
 825             sn2sn.put(tocopy, temp);
 826             cn2cn = null;
 827         }
 828         // clone the ScheduleEdges and merge those in reduceEdges at the same time
 829         Vector<ScheduleEdge> toMerge = new Vector<ScheduleEdge>();
 830         for(int i = 0; i < this.scheduleEdges.size(); i++) {
 831             ScheduleEdge sse = this.scheduleEdges.elementAt(i);
 832             ScheduleNode csource = sn2sn.get(sse.getSource());
 833             ScheduleNode ctarget = sn2sn.get(sse.getTarget());
 834             Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
 835             Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
 836             ScheduleEdge se;
 837             if(sse.getIsNew()) {
 838                 se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getIsNew(), gid);//new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
 839                 se.setProbability(sse.getProbability());
 840                 se.setNewRate(sse.getNewRate());
 841             } else {
 842                 se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), false, gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
 843             }
 844             se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
 845             se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
 846             se.setFEdge(sse.getFEdge());
 847             se.setTargetFState(sse.getTargetFState());
 848             se.setIsclone(true);
 849             csource.addEdge(se);
 850             if(reduceEdges.contains(sse)) {
 851                 toMerge.add(se);
 852             }
 853             sourcecn2cn = null;
 854             targetcn2cn = null;
 855         }
 856         sn2hash = null;
 857         sn2sn = null;
 858
 859         for(int i = 0; i < toMerge.size(); i++) {
 860             ScheduleEdge sEdge = toMerge.elementAt(i);
 861             // merge this edge
 862             if(sEdge.getIsNew()) {
 863                 ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
 864             } else {
 865                 try {
 866                     ((ScheduleNode)sEdge.getSource()).mergeTransEdge(sEdge);
 867                 } catch(Exception e) {
 868                     e.printStackTrace();
 869                     System.exit(-1);
 870                 }
 871             }
 872             result.removeElement(sEdge.getTarget());
 873             if(sEdge.getIsNew()) {
 874                 // As se has been changed into an internal edge inside a ScheduleNode,
 875                 // change the source and target of se from original ScheduleNodes into ClassNodes.
 876                 sEdge.setTarget(sEdge.getTargetCNode());
 877                 sEdge.setSource(sEdge.getSourceCNode());
 878             }
 879         }
 880         toMerge = null;
 881
 882         String path = "scheduling_" + gid + ".dot";
 883         SchedulingUtil.printScheduleGraph(path, result);
 884
 885         return result;
 886     }
 887
 888     class Combination{
 889         Combination tail;
 890         Object head;
 891         Vector factors;
 892         int selectNum;
 893         int resultNum;
 894
 895         public Combination(Vector factors, int selectNum) throws Exception{
 896             this.factors = factors;
 897             if(factors.size() < selectNum) {
 898                 throw new Exception("Error: selectNum > candidates' number in combination.");
 899             }
 900             if(factors.size() == selectNum) {
 901                 this.resultNum = 1;
 902                 head = null;
 903                 tail = null;
 904                 return;
 905             }
 906             this.head = this.factors.remove(0);
 907             if(selectNum == 1) {
 908                 this.resultNum = this.factors.size() + 1;
 909                 this.tail = null;
 910                 return;
 911             }
 912             this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
 913             this.selectNum = selectNum;
 914             this.resultNum = 1;
 915             for(int i = factors.size(); i > selectNum; i--) {
 916                 this.resultNum *= i;
 917             }
 918             for(int i = factors.size() - selectNum; i > 0; i--) {
 919                 this.resultNum /= i;
 920             }
 921         }
 922
 923         public Vector next() {
 924             if(resultNum == 0) {
 925                 return null;
 926             }
 927             if(head == null) {
 928                 resultNum--;
 929                 Vector result = this.factors;
 930                 return result;
 931             }
 932             if(this.tail == null) {
 933                 resultNum--;
 934                 Vector result = new Vector();
 935                 result.add(this.head);
 936                 if(resultNum != 0) {
 937                     this.head = this.factors.remove(0);
 938                 }
 939                 return result;
 940             }
 941             Vector result = this.tail.next();
 942             if(result == null) {
 943                 if(this.factors.size() == this.selectNum) {
 944                     this.head = null;
 945                     this.tail = null;
 946                     result = this.factors;
 947                     this.resultNum--;
 948                     return result;
 949                 }
 950                 this.head = this.factors.remove(0);
 951                 try {
 952                     this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
 953                     result = this.tail.next();
 954                 } catch(Exception e) {
 955                     e.printStackTrace();
 956                 }
 957
 958             }
 959             result.add(0, head);
 960             resultNum--;
 961             return result;
 962         }
 963     }
 964 }