Robust/src/Analysis/Scheduling/ScheduleAnalysis.java

   1 package Analysis.Scheduling;
   2
   3 import Analysis.TaskStateAnalysis.*;
   4 import Analysis.TaskStateAnalysis.FEdge.NewObjInfo;
   5 import IR.*;
   6
   7 import java.util.*;
   8 import java.io.*;
   9
  10 import Util.Edge;
  11 import Util.GraphNode;
  12 import Util.Namer;
  13
  14 /** This class holds flag transition diagram(s) can be put on one core.
  15  */
  16 public class ScheduleAnalysis {
  17
  18     TaskAnalysis taskanalysis;
  19     State state;
  20     Vector<ScheduleNode> scheduleNodes;
  21     Vector<ClassNode> classNodes;
  22     Hashtable<ClassDescriptor, ClassNode> cd2ClassNode;
  23     boolean sorted = false;
  24     Vector<ScheduleEdge> scheduleEdges;
  25
  26     int transThreshold;
  27
  28     int coreNum;
  29     Vector<Vector<ScheduleNode>> schedules;
  30
  31     public ScheduleAnalysis(State state, TaskAnalysis taskanalysis) {
  32         this.state = state;
  33         this.taskanalysis = taskanalysis;
  34         this.scheduleNodes = new Vector<ScheduleNode>();
  35         this.classNodes = new Vector<ClassNode>();
  36         this.scheduleEdges = new Vector<ScheduleEdge>();
  37         this.cd2ClassNode = new Hashtable<ClassDescriptor, ClassNode>();
  38         this.transThreshold = 45;
  39         this.coreNum = -1;
  40     }
  41
  42     public void setTransThreshold(int tt) {
  43         this.transThreshold = tt;
  44     }
  45
  46     public void setCoreNum(int coreNum) {
  47         this.coreNum = coreNum;
  48     }
  49
  50     public Iterator getSchedules() {
  51         return this.schedules.iterator();
  52     }
  53
  54     // for test
  55     public Vector<ScheduleEdge> getSEdges4Test() {
  56         return scheduleEdges;
  57     }
  58
  59     public void preSchedule() {
  60         Hashtable<ClassDescriptor, ClassNode> cdToCNodes = new Hashtable<ClassDescriptor, ClassNode>();
  61         // Build the combined flag transition diagram
  62         // First, for each class create a ClassNode
  63         for(Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext(); ) {
  64             ClassDescriptor cd = (ClassDescriptor) it_classes.next();
  65             Set<FlagState> fStates = taskanalysis.getFlagStates(cd);
  66
  67             //Sort flagState nodes inside this ClassNode
  68             Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
  69
  70             Vector rootnodes  = taskanalysis.getRootNodes(cd);
  71             if(((rootnodes != null) && (rootnodes.size() > 0)) || (cd.getSymbol().equals("StartupObject"))) {
  72                 ClassNode cNode = new ClassNode(cd, sFStates);
  73                 cNode.setSorted(true);
  74                 classNodes.add(cNode);
  75                 cd2ClassNode.put(cd, cNode);
  76                 cdToCNodes.put(cd, cNode);
  77                 cNode.calExeTime();
  78
  79                 // for test
  80                 if(cd.getSymbol().equals("C")) {
  81                     cNode.setTransTime(45);
  82                 }
  83             }
  84             fStates = null;
  85             sFStates = null;
  86         }
  87
  88         // For each ClassNode create a ScheduleNode containing it
  89         int i = 0;
  90         for(i = 0; i < classNodes.size(); i++) {
  91             ScheduleNode sn = new ScheduleNode(classNodes.elementAt(i), 0);
  92             classNodes.elementAt(i).setScheduleNode(sn);
  93             scheduleNodes.add(sn);
  94             try {
  95                 sn.calExeTime();
  96             } catch (Exception e) {
  97                 e.printStackTrace();
  98             }
  99         }
 100
 101         // Create 'new' edges between the ScheduleNodes.
 102         Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
 103         for(i = 0; i < classNodes.size(); i++) {
 104             ClassNode cNode = classNodes.elementAt(i);
 105             ClassDescriptor cd = cNode.getClassDescriptor();
 106             Vector rootnodes  = taskanalysis.getRootNodes(cd);
 107             if(rootnodes != null) {
 108                 for(int h = 0; h < rootnodes.size(); h++){
 109                     FlagState root=(FlagState)rootnodes.elementAt(h);
 110                     Vector allocatingTasks = root.getAllocatingTasks();
 111                     if(allocatingTasks != null) {
 112                         for(int k = 0; k < allocatingTasks.size(); k++) {
 113                             TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
 114                             Vector<FEdge> fev = (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
 115                             int numEdges = fev.size();
 116                             ScheduleNode sNode = cNode.getScheduleNode();
 117                             for(int j = 0; j < numEdges; j++) {
 118                                 FEdge pfe = fev.elementAt(j);
 119                                 FEdge.NewObjInfo noi = pfe.getNewObjInfo(cd);
 120                                 if ((noi == null) || (noi.getNewRate() == 0) || (noi.getProbability() == 0)) {
 121                                     // fake creating edge, do not need to create corresponding 'new' edge
 122                                     continue;
 123                                 }
 124                                 FlagState pfs = (FlagState)pfe.getTarget();
 125                                 ClassDescriptor pcd = pfs.getClassDescriptor();
 126                                 ClassNode pcNode = cdToCNodes.get(pcd);
 127
 128                                 ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", cd, 0);
 129                                 sEdge.setFEdge(pfe);
 130                                 sEdge.setSourceCNode(pcNode);
 131                                 sEdge.setTargetCNode(cNode);
 132                                 sEdge.setTargetFState(root);
 133                                 sEdge.setNewRate(noi.getNewRate());
 134                                 sEdge.setProbability(noi.getProbability());
 135                                 pcNode.getScheduleNode().addEdge(sEdge);
 136                                 scheduleEdges.add(sEdge);
 137                                 if((j !=0 ) || (k != 0) || (h != 0)) {
 138                                     toBreakDown.add(sEdge);
 139                                 }
 140                             }
 141                             fev = null;
 142                         }
 143                         allocatingTasks = null;
 144                     }
 145                 }
 146                 rootnodes = null;
 147             }
 148         }
 149         cdToCNodes = null;
 150
 151         // Do topology sort of the ClassNodes and ScheduleEdges.
 152         Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
 153         Vector<ScheduleNode> tempSNodes = ClassNode.DFS.topology(scheduleNodes, ssev);
 154         scheduleNodes.removeAllElements();
 155         scheduleNodes = tempSNodes;
 156         tempSNodes = null;
 157         scheduleEdges.removeAllElements();
 158         scheduleEdges = ssev;
 159         ssev = null;
 160         sorted = true;
 161
 162         // Break down the 'cycle's
 163         for(i = 0; i < toBreakDown.size(); i++ ) {
 164             cloneSNodeList(toBreakDown.elementAt(i), false);
 165         }
 166         toBreakDown = null;
 167
 168         // Remove fake 'new' edges
 169         for(i = 0; i < scheduleEdges.size(); i++) {
 170             ScheduleEdge se = scheduleEdges.elementAt(i);
 171             if((0 == se.getNewRate()) || (0 == se.getProbability())) {
 172                 scheduleEdges.removeElement(se);
 173                 scheduleNodes.removeElement(se.getTarget());
 174             }
 175         }
 176
 177         printScheduleGraph("scheduling_ori.dot", this.scheduleNodes);
 178     }
 179
 180     public void scheduleAnalysis() {
 181         // First iteration
 182         int i = 0;
 183         //Access the ScheduleEdges in reverse topology order
 184         Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses = new Hashtable<FEdge, Vector<ScheduleEdge>>();
 185         Hashtable<ScheduleNode, Vector<FEdge>> sn2fes = new Hashtable<ScheduleNode, Vector<FEdge>>();
 186         ScheduleNode preSNode = null;
 187         for(i = scheduleEdges.size(); i > 0; i--) {
 188             ScheduleEdge se = scheduleEdges.elementAt(i-1);
 189             if(preSNode == null) {
 190                 preSNode = (ScheduleNode)se.getSource();
 191             }
 192             if(se.getIsNew()) {
 193                 boolean split = false;
 194                 FEdge fe = se.getFEdge();
 195                 if(fe.getSource() == fe.getTarget()) {
 196                     // back edge
 197                     int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
 198                     int rate = 0;
 199                     if(repeat > 1){
 200                         for(int j = 1; j< repeat; j++ ) {
 201                             cloneSNodeList(se, true);
 202                         }
 203                         se.setNewRate(1);
 204                         se.setProbability(100);
 205                     }
 206                     try {
 207                         rate = (int)Math.ceil(se.getListExeTime()/ calInExeTime(se.getSourceFState()));
 208                     } catch (Exception e) {
 209                         e.printStackTrace();
 210                     }
 211                     for(int j = rate - 1; j > 0; j--) {
 212                         for(int k = repeat; k > 0; k--) {
 213                             cloneSNodeList(se, true);
 214                         }
 215                     }
 216                 } else {
 217                     // if preSNode is not the same as se's source ScheduleNode
 218                     // handle any ScheduleEdges previously put into fe2ses whose source ScheduleNode is preSNode
 219                     boolean same = (preSNode == se.getSource());
 220                     if(!same) {
 221                         if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()) {
 222                             if(sn2fes.containsKey(preSNode)) {
 223                                 Vector<FEdge> fes = sn2fes.remove(preSNode);
 224                                 for(int j = 0; j < fes.size(); j++) {
 225                                     FEdge tempfe = fes.elementAt(j);
 226                                     Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 227                                     ScheduleEdge tempse = ses.elementAt(0);
 228                                     int temptime = tempse.getListExeTime();
 229                                     // find out the ScheduleEdge with least exeTime
 230                                     for(int k = 1; k < ses.size(); k++) {
 231                                         int ttemp = ses.elementAt(k).getListExeTime();
 232                                         if(ttemp < temptime) {
 233                                             tempse = ses.elementAt(k);
 234                                             temptime = ttemp;
 235                                         }
 236                                     }
 237                                     // handle the tempse
 238                                     handleScheduleEdge(tempse, true);
 239                                     ses.removeElement(tempse);
 240                                     // handle other ScheduleEdges
 241                                     for(int k = 0; k < ses.size(); k++) {
 242                                         handleScheduleEdge(ses.elementAt(k), false);
 243                                     }
 244                                     ses = null;
 245                                     fe2ses.remove(tempfe);
 246                                 }
 247                                 fes = null;
 248                             }
 249                         }
 250                         preSNode = (ScheduleNode)se.getSource();
 251                     }
 252
 253                     // if fe is the last task inside this ClassNode, delay the expanding and merging until we find all such 'nmew' edges
 254                     // associated with a last task inside this ClassNode
 255                     if(!fe.getTarget().edges().hasNext()) {
 256                         if(fe2ses.get(fe) == null) {
 257                             fe2ses.put(fe, new Vector<ScheduleEdge>());
 258                         }
 259                         if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
 260                             sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
 261                         }
 262                         fe2ses.get(fe).add(se);
 263                         sn2fes.get((ScheduleNode)se.getSource()).add(fe);
 264                     } else {
 265                         // As this is not a last task, first handle available ScheduleEdges previously put into fe2ses
 266                         if((same) && (sn2fes.containsKey(preSNode))) {
 267                             Vector<FEdge> fes = sn2fes.remove(preSNode);
 268                             for(int j = 0; j < fes.size(); j++) {
 269                                 FEdge tempfe = fes.elementAt(j);
 270                                 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 271                                 ScheduleEdge tempse = ses.elementAt(0);
 272                                 int temptime = tempse.getListExeTime();
 273                                 // find out the ScheduleEdge with least exeTime
 274                                 for(int k = 1; k < ses.size(); k++) {
 275                                     int ttemp = ses.elementAt(k).getListExeTime();
 276                                     if(ttemp < temptime) {
 277                                         tempse = ses.elementAt(k);
 278                                         temptime = ttemp;
 279                                     }
 280                                 }
 281                                 // handle the tempse
 282                                 handleScheduleEdge(tempse, true);
 283                                 ses.removeElement(tempse);
 284                                 // handle other ScheduleEdges
 285                                 for(int k = 0; k < ses.size(); k++) {
 286                                     handleScheduleEdge(ses.elementAt(k), false);
 287                                 }
 288                                 ses = null;
 289                                 fe2ses.remove(tempfe);
 290                             }
 291                             fes = null;
 292                         }
 293
 294                         if((!(se.getTransTime() < this.transThreshold)) && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
 295                             split = true;
 296                             splitSNode(se, true);
 297                         } else {
 298                             // handle this ScheduleEdge
 299                             handleScheduleEdge(se, true);
 300                         }
 301                     }
 302                 }
 303             }
 304         }
 305         if(!fe2ses.isEmpty()) {
 306             Set<FEdge> keys = fe2ses.keySet();
 307             Iterator it_keys = keys.iterator();
 308             while(it_keys.hasNext()) {
 309                 FEdge tempfe = (FEdge)it_keys.next();
 310                 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 311                 ScheduleEdge tempse = ses.elementAt(0);
 312                 int temptime = tempse.getListExeTime();
 313                 // find out the ScheduleEdge with least exeTime
 314                 for(int k = 1; k < ses.size(); k++) {
 315                     int ttemp = ses.elementAt(k).getListExeTime();
 316                     if(ttemp < temptime) {
 317                         tempse = ses.elementAt(k);
 318                         temptime = ttemp;
 319                     }
 320                 }
 321                 // handle the tempse
 322                 handleScheduleEdge(tempse, true);
 323                 ses.removeElement(tempse);
 324                 // handle other ScheduleEdges
 325                 for(int k = 0; k < ses.size(); k++) {
 326                     handleScheduleEdge(ses.elementAt(k), false);
 327                 }
 328                 ses = null;
 329             }
 330             keys = null;
 331             fe2ses.clear();
 332             sn2fes.clear();
 333         }
 334         fe2ses = null;
 335         sn2fes = null;
 336
 337         printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
 338     }
 339
 340     private void handleScheduleEdge(ScheduleEdge se, boolean merge) {
 341         int rate = 0;
 342         int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
 343         if(merge) {
 344             try {
 345                 rate = (int)Math.ceil((se.getTransTime() - calInExeTime(se.getSourceFState()))/ se.getListExeTime());
 346                 if(rate < 0 ) {
 347                     rate = 0;
 348                 }
 349             } catch (Exception e) {
 350                 e.printStackTrace();
 351             }
 352             if(0 == rate) {
 353                 // clone the whole ScheduleNode lists starting with se's target
 354                 for(int j = 1; j < repeat; j++ ) {
 355                     cloneSNodeList(se, true);
 356                 }
 357                 se.setNewRate(1);
 358                 se.setProbability(100);
 359             } else {
 360                 repeat -= rate;
 361                 if(repeat > 0){
 362                     // clone the whole ScheduleNode lists starting with se's target
 363                     for(int j = 0; j < repeat; j++ ) {
 364                         cloneSNodeList(se, true);
 365                     }
 366                     se.setNewRate(rate);
 367                     se.setProbability(100);
 368                 }
 369             }
 370             // merge the original ScheduleNode to the source ScheduleNode
 371             ((ScheduleNode)se.getSource()).mergeSEdge(se);
 372             scheduleNodes.remove(se.getTarget());
 373             scheduleEdges.remove(se);
 374             // As se has been changed into an internal edge inside a ScheduleNode,
 375             // change the source and target of se from original ScheduleNodes into ClassNodes.
 376             se.setTarget(se.getTargetCNode());
 377             se.setSource(se.getSourceCNode());
 378         } else {
 379             // clone the whole ScheduleNode lists starting with se's target
 380             for(int j = 1; j < repeat; j++ ) {
 381                 cloneSNodeList(se, true);
 382             }
 383             se.setNewRate(1);
 384             se.setProbability(100);
 385         }
 386     }
 387
 388     private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) {
 389         Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
 390         ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
 391         scheduleNodes.add(csNode);
 392
 393         // Clone all the external in ScheduleEdges
 394         int i;
 395         if(copyIE) {
 396             Vector inedges = sEdge.getTarget().getInedgeVector();
 397             for(i = 0; i < inedges.size(); i++) {
 398                 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
 399                 ScheduleEdge se;
 400                 if(tse.getIsNew()) {
 401                     se = new ScheduleEdge(csNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0);
 402                     se.setProbability(100);
 403                     se.setNewRate(1);
 404                     se.setFEdge(tse.getFEdge());
 405                 } else {
 406                     se = new ScheduleEdge(csNode, "transmit", tse.getClassDescriptor(), false, 0);
 407                 }
 408                 se.setSourceCNode(tse.getSourceCNode());
 409                 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
 410                 tse.getSource().addEdge(se);
 411                 scheduleEdges.add(se);
 412             }
 413             inedges = null;
 414         } else {
 415             sEdge.getTarget().removeInedge(sEdge);
 416             sEdge.setTarget(csNode);
 417             csNode.getInedgeVector().add(sEdge);
 418             sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
 419             sEdge.setTargetFState(null);
 420         }
 421
 422         Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>();
 423         Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>();
 424         Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>();
 425         clone.add(csNode);
 426         toClone.add((ScheduleNode)sEdge.getTarget());
 427         qcn2cn.add(cn2cn);
 428         while(!toClone.isEmpty()) {
 429             Hashtable<ClassNode, ClassNode> tocn2cn = new Hashtable<ClassNode, ClassNode>();
 430             csNode = clone.poll();
 431             ScheduleNode osNode = toClone.poll();
 432             cn2cn = qcn2cn.poll();
 433             // Clone all the external ScheduleEdges and the following ScheduleNodes
 434             Vector edges = osNode.getEdgeVector();
 435             for(i = 0; i < edges.size(); i++) {
 436                 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
 437                 ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
 438                 scheduleNodes.add(tSNode);
 439                 clone.add(tSNode);
 440                 toClone.add((ScheduleNode)tse.getTarget());
 441                 qcn2cn.add(tocn2cn);
 442                 ScheduleEdge se = null;
 443                 if(tse.getIsNew()) {
 444                     se = new ScheduleEdge(tSNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0);
 445                     se.setProbability(tse.getProbability());
 446                     se.setNewRate(tse.getNewRate());
 447                 } else {
 448                     se = new ScheduleEdge(tSNode, "transmit", tse.getClassDescriptor(), false, 0);
 449                 }
 450                 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
 451                 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
 452                 csNode.addEdge(se);
 453                 scheduleEdges.add(se);
 454             }
 455             tocn2cn = null;
 456             edges = null;
 457         }
 458         toClone = null;
 459         clone = null;
 460         qcn2cn = null;
 461         cn2cn = null;
 462     }
 463
 464     private int calInExeTime(FlagState fs) throws Exception {
 465         int exeTime = 0;
 466         ClassDescriptor cd = fs.getClassDescriptor();
 467         ClassNode cNode = cd2ClassNode.get(cd);
 468         exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
 469         while(true) {
 470             Vector inedges = cNode.getInedgeVector();
 471             if(inedges.size() > 1) {
 472                 throw new Exception("Error: ClassNode's inedges more than one!");
 473             }
 474             if(inedges.size() > 0) {
 475                 ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
 476                 cNode = (ClassNode)sEdge.getSource();
 477                 exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
 478             }else {
 479                 break;
 480             }
 481             inedges = null;
 482         }
 483         exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
 484         return exeTime;
 485     }
 486
 487     private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) {
 488         FEdge fe = se.getFEdge();
 489         FlagState fs = (FlagState)fe.getTarget();
 490         FlagState nfs = (FlagState)fs.clone();
 491         fs.getEdgeVector().removeAllElements();
 492         nfs.getInedgeVector().removeAllElements();
 493         ClassNode sCNode = se.getSourceCNode();
 494
 495         // split the subtree whose root is nfs from the whole flag transition tree
 496         Vector<FlagState> sfss = sCNode.getFlagStates();
 497         Vector<FlagState> fStates = new Vector<FlagState>();
 498         Queue<FlagState> toiterate = new LinkedList<FlagState>();
 499         toiterate.add(nfs);
 500         fStates.add(nfs);
 501         while(!toiterate.isEmpty()){
 502             FlagState tfs = toiterate.poll();
 503             Iterator it_edges = tfs.edges();
 504             while(it_edges.hasNext()) {
 505                 FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
 506                 if(!fStates.contains(temp)) {
 507                     fStates.add(temp);
 508                     toiterate.add(temp);
 509                     sfss.removeElement(temp);
 510                 }
 511             }
 512         }
 513         sfss = null;
 514         Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
 515         fStates = null;
 516         // create a ClassNode and ScheduleNode for this subtree
 517         ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
 518         ScheduleNode sNode = new ScheduleNode(cNode, 0);
 519         cNode.setScheduleNode(sNode);
 520         cNode.setSorted(true);
 521         cNode.setTransTime(sCNode.getTransTime());
 522         classNodes.add(cNode);
 523         scheduleNodes.add(sNode);
 524         try {
 525             sNode.calExeTime();
 526         } catch (Exception e) {
 527             e.printStackTrace();
 528         }
 529         // flush the exeTime of fs and its ancestors
 530         fs.setExeTime(0);
 531         toiterate.add(fs);
 532         while(!toiterate.isEmpty()) {
 533             FlagState tfs = toiterate.poll();
 534             int ttime = tfs.getExeTime();
 535             Iterator it_inedges = tfs.inedges();
 536             while(it_inedges.hasNext()) {
 537                 FEdge fEdge = (FEdge)it_inedges.next();
 538                 FlagState temp = (FlagState)fEdge.getSource();
 539                 int time = fEdge.getExeTime() + ttime;
 540                 if(temp.getExeTime() > time) {
 541                     temp.setExeTime(time);
 542                     toiterate.add(temp);
 543                 }
 544             }
 545         }
 546         toiterate = null;
 547
 548         // create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode
 549         ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
 550         sEdge.setTargetFState(fs);
 551         sEdge.setFEdge(fe);
 552         sEdge.setSourceCNode(sCNode);
 553         sEdge.setTargetCNode(cNode);
 554         sEdge.setTargetFState(nfs);
 555         // todo
 556         // Add calculation codes for calculating transmit time of an object
 557         sEdge.setTransTime(cNode.getTransTime());
 558         se.getSource().addEdge(sEdge);
 559         scheduleEdges.add(sEdge);
 560         // redirect ScheudleEdges out of this subtree to the new ScheduleNode
 561         Iterator it_sEdges = se.getSource().edges();
 562         Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
 563         while(it_sEdges.hasNext()) {
 564             ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
 565             if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
 566                 if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
 567                     tse.setSource(sNode);
 568                     tse.setSourceCNode(cNode);
 569                     sNode.getEdgeVector().addElement(tse);
 570                     toremove.add(tse);
 571                 }
 572             }
 573         }
 574         se.getSource().getEdgeVector().removeAll(toremove);
 575         toremove = null;
 576         sFStates = null;
 577
 578         if(!copy) {
 579             //merge se into its source ScheduleNode
 580             ((ScheduleNode)se.getSource()).mergeSEdge(se);
 581             scheduleNodes.remove(se.getTarget());
 582             scheduleEdges.removeElement(se);
 583             // As se has been changed into an internal edge inside a ScheduleNode,
 584             // change the source and target of se from original ScheduleNodes into ClassNodes.
 585             se.setTarget(se.getTargetCNode());
 586             se.setSource(se.getSourceCNode());
 587         } else {
 588             handleScheduleEdge(se, true);
 589         }
 590
 591         return sNode;
 592     }
 593
 594     public void schedule() throws Exception {
 595         if(this.coreNum == -1) {
 596             throw new Exception("Error: un-initialized coreNum when doing scheduling.");
 597         }
 598
 599         if(this.schedules == null) {
 600             this.schedules = new Vector<Vector<ScheduleNode>>();
 601         }
 602
 603         int reduceNum = this.scheduleNodes.size() - this.coreNum;
 604
 605         // Enough cores, no need to merge more ScheduleEdge
 606         if(!(reduceNum > 0)) {
 607             this.schedules.addElement(this.scheduleNodes);
 608         } else {
 609             // sort the ScheduleEdges in dececending order of transmittime
 610             Vector<ScheduleEdge> sEdges = new Vector<ScheduleEdge>();
 611             sEdges.addElement(this.scheduleEdges.elementAt(0));
 612             for(int i = 1; i < this.scheduleEdges.size(); i++) {
 613                 ScheduleEdge temp = this.scheduleEdges.elementAt(i);
 614                 int j = sEdges.size() - 1;
 615                 do {
 616                     if(temp.getTransTime() > sEdges.elementAt(j--).getTransTime()) {
 617                         break;
 618                     }
 619                 } while(j >= 0);
 620                 sEdges.add(j+1, temp);
 621             }
 622
 623             int temp = sEdges.elementAt(reduceNum - 1).getTransTime();
 624             for(int i = sEdges.size() - 1; i > reduceNum - 1; i--) {
 625                 if(sEdges.elementAt(i).getTransTime() != temp) {
 626                     sEdges.removeElementAt(i);
 627                 } else {
 628                     break;
 629                 }
 630             }
 631             int start = reduceNum - 2;
 632             for(; start >= 0; start--) {
 633                 if(sEdges.elementAt(start).getTransTime() != temp) {
 634                     start++;
 635                     reduceNum -= start;
 636                     break;
 637                 }
 638             }
 639             if(start < 0) {
 640                 start = 0;
 641             }
 642
 643             // generate scheduling
 644             Vector candidates = new Vector();
 645             for(int i = start; i < sEdges.size(); i++) {
 646                 candidates.addElement(Integer.valueOf(i));
 647             }
 648             Combination combGen = new Combination(candidates, reduceNum);
 649             int gid = 1;
 650             do {
 651                 Vector toreduce = combGen.next();
 652                 if(toreduce != null) {
 653                     Vector<ScheduleEdge> reduceEdges = new Vector<ScheduleEdge>();
 654                     for(int i = 0; i < start; i++) {
 655                         reduceEdges.add(sEdges.elementAt(i));
 656                     }
 657                     for(int i = 0; i < toreduce.size(); i++) {
 658                         reduceEdges.add(sEdges.elementAt(((Integer)toreduce.elementAt(i)).intValue()));
 659                     }
 660                     Vector<ScheduleNode> sNodes = generateScheduling(reduceEdges, gid++);
 661                     this.schedules.add(sNodes);
 662                     reduceEdges = null;
 663                     sNodes = null;
 664                 } else {
 665                     break;
 666                 }
 667                 toreduce = null;
 668             }while(true);
 669             sEdges = null;
 670             candidates = null;
 671
 672         /*
 673             // Assign a core to each ScheduleNode
 674             int i = 0;
 675             int coreNum = 1;
 676             for(i = 0; i < scheduleNodes.size(); i++) {
 677                 ScheduleNode sn = scheduleNodes.elementAt(i);
 678                 sn.setCoreNum(coreNum++);
 679                 sn.listTasks();
 680                 // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
 681                 Iterator it_edges = sn.edges();
 682                 while(it_edges.hasNext()) {
 683                     ScheduleEdge se = (ScheduleEdge)it_edges.next();
 684                     ScheduleNode target = (ScheduleNode)se.getTarget();
 685                     sn.addTargetSNode(se.getTargetFState().getClassDescriptor(), target);
 686                 }
 687             }*/
 688         }
 689
 690     }
 691
 692     public Vector<ScheduleNode> generateScheduling(Vector<ScheduleEdge> reduceEdges, int gid) {
 693         Vector<ScheduleNode> result = new Vector<ScheduleNode>();
 694
 695         // clone the ScheduleNodes
 696         Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
 697         Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
 698         for(int i = 0; i < this.scheduleNodes.size(); i++) {
 699             Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
 700             ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
 701             ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
 702             result.add(i, temp);
 703             sn2hash.put(temp, cn2cn);
 704             sn2sn.put(tocopy, temp);
 705             cn2cn = null;
 706         }
 707         // clone the ScheduleEdges and merge those in reduceEdges at the same time
 708         Vector<ScheduleEdge> toMerge = new Vector<ScheduleEdge>();
 709         for(int i = 0; i < this.scheduleEdges.size(); i++) {
 710             ScheduleEdge sse = this.scheduleEdges.elementAt(i);
 711             ScheduleNode csource = sn2sn.get(sse.getSource());
 712             ScheduleNode ctarget = sn2sn.get(sse.getTarget());
 713             Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
 714             Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
 715             ScheduleEdge se;
 716             if(sse.getIsNew()) {
 717                 se = new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
 718                 se.setProbability(sse.getProbability());
 719                 se.setNewRate(sse.getNewRate());
 720                 se.setFEdge(sse.getFEdge());
 721             } else {
 722                 se = new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
 723             }
 724             se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
 725             se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
 726             csource.addEdge(se);
 727             if(reduceEdges.contains(sse)) {
 728                 toMerge.add(se);
 729             }
 730             sourcecn2cn = null;
 731             targetcn2cn = null;
 732         }
 733         sn2hash = null;
 734         sn2sn = null;
 735
 736         for(int i = 0; i < toMerge.size(); i++) {
 737             ScheduleEdge sEdge = toMerge.elementAt(i);
 738             // merge this edge
 739             ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
 740             result.removeElement(sEdge.getTarget());
 741             // As se has been changed into an internal edge inside a ScheduleNode,
 742             // change the source and target of se from original ScheduleNodes into ClassNodes.
 743             sEdge.setTarget(sEdge.getTargetCNode());
 744             sEdge.setSource(sEdge.getSourceCNode());
 745         }
 746         toMerge = null;
 747
 748         String path = "scheduling_" + gid + ".dot";
 749         printScheduleGraph(path, result);
 750
 751         return result;
 752     }
 753
 754     public void printScheduleGraph(String path, Vector<ScheduleNode> sNodes) {
 755         try {
 756             File file=new File(path);
 757             FileOutputStream dotstream=new FileOutputStream(file,false);
 758             PrintWriter output = new java.io.PrintWriter(dotstream, true);
 759             output.println("digraph G {");
 760             output.println("\tcompound=true;\n");
 761             traverseSNodes(output, sNodes);
 762             output.println("}\n");
 763         } catch (Exception e) {
 764             e.printStackTrace();
 765             System.exit(-1);
 766         }
 767     }
 768
 769     private void traverseSNodes(PrintWriter output, Vector<ScheduleNode> sNodes){
 770         //Draw clusters representing ScheduleNodes
 771         Iterator it = sNodes.iterator();
 772         while (it.hasNext()) {
 773             ScheduleNode gn = (ScheduleNode) it.next();
 774             Iterator edges = gn.edges();
 775             output.println("\tsubgraph " + gn.getLabel() + "{");
 776             output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
 777             Iterator it_cnodes = gn.getClassNodesIterator();
 778             traverseCNodes(output, it_cnodes);
 779             //Draw the internal 'new' edges
 780             Iterator it_edges =gn.getScheduleEdgesIterator();
 781             while(it_edges.hasNext()) {
 782                 ScheduleEdge se = (ScheduleEdge)it_edges.next();
 783                 output.print("\t");
 784                 if(se.getSourceCNode().isclone()) {
 785                     output.print(se.getSourceCNode().getLabel());
 786                 } else {
 787                     if(se.getSourceFState() == null) {
 788                         output.print(se.getSourceCNode().getClusterLabel());
 789                     } else {
 790                         output.print(se.getSourceFState().getLabel());
 791                     }
 792                 }
 793
 794                 output.print(" -> ");
 795                 if(se.getTargetFState() == null) {
 796                     if(se.getTargetCNode().isclone()) {
 797                         output.print(se.getTargetCNode().getLabel());
 798                     } else {
 799                         output.print(se.getTargetCNode().getClusterLabel());
 800                     }
 801                     output.println(" [label=\"" + se.getLabel() + "\", color=red];");
 802                 } else {
 803                     output.print(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail=");
 804                     if(se.getSourceCNode().isclone()) {
 805                         output.println(se.getSourceCNode().getLabel() + "];");
 806                     } else {
 807                         output.println(se.getSourceCNode().getClusterLabel() + "];");
 808                     }
 809                 }
 810             }
 811             output.println("\t}\n");
 812             //Draw 'new' edges of this ScheduleNode
 813             while(edges.hasNext()) {
 814                 ScheduleEdge se = (ScheduleEdge)edges.next();
 815                 output.print("\t");
 816                 if(se.getSourceCNode().isclone()) {
 817                     output.print(se.getSourceCNode().getLabel());
 818                 } else {
 819                     if(se.getSourceFState() == null) {
 820                         output.print(se.getSourceCNode().getClusterLabel());
 821                     } else {
 822                         output.print(se.getSourceFState().getLabel());
 823                     }
 824                 }
 825
 826                 output.print(" -> ");
 827                 if(se.getTargetFState() == null) {
 828                     if(se.getTargetCNode().isclone()) {
 829                         output.print(se.getTargetCNode().getLabel());
 830                     } else {
 831                         output.print(se.getTargetCNode().getClusterLabel());
 832                     }
 833                     output.println(" [label=\"" + se.getLabel() + "\", color=red, style=dashed]");
 834                 } else {
 835                     output.println(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed]");
 836                 }
 837             }
 838         }
 839     }
 840
 841     private void traverseCNodes(PrintWriter output, Iterator it){
 842         //Draw clusters representing ClassNodes
 843         while (it.hasNext()) {
 844             ClassNode gn = (ClassNode) it.next();
 845             if(gn.isclone()) {
 846                 output.println("\t\t" + gn.getLabel() + " [style=dashed, label=\"" + gn.getTextLabel() + "\", shape=box];");
 847             } else {
 848                 output.println("\tsubgraph " + gn.getClusterLabel() + "{");
 849                 output.println("\t\tstyle=dashed;");
 850                 output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
 851                 traverseFlagStates(output, gn.getFlagStates());
 852                 output.println("\t}\n");
 853             }
 854         }
 855     }
 856
 857     private void traverseFlagStates(PrintWriter output, Collection nodes) {
 858         Set cycleset=GraphNode.findcycles(nodes);
 859         Vector namers=new Vector();
 860         namers.add(new Namer());
 861         namers.add(new Allocations());
 862         //namers.add(new TaskEdges());
 863
 864         Iterator it = nodes.iterator();
 865         while (it.hasNext()) {
 866             GraphNode gn = (GraphNode) it.next();
 867             Iterator edges = gn.edges();
 868             String label = "";
 869             String dotnodeparams="";
 870
 871             for(int i=0;i<namers.size();i++) {
 872                 Namer name=(Namer) namers.get(i);
 873                 String newlabel=name.nodeLabel(gn);
 874                 String newparams=name.nodeOption(gn);
 875
 876                 if (!newlabel.equals("") && !label.equals("")) {
 877                     label+=", ";
 878                 }
 879                 if (!newparams.equals("")) {
 880                     dotnodeparams+=", " + name.nodeOption(gn);
 881                 }
 882                 label+=name.nodeLabel(gn);
 883             }
 884             label += ":[" + ((FlagState)gn).getExeTime() + "]";
 885
 886             if (!gn.merge)
 887                 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
 888
 889             if (!gn.merge)
 890                 while (edges.hasNext()) {
 891                     Edge edge = (Edge) edges.next();
 892                     GraphNode node = edge.getTarget();
 893                     if (nodes.contains(node)) {
 894                         for(Iterator nodeit=nonmerge(node, nodes).iterator();nodeit.hasNext();) {
 895                             GraphNode node2=(GraphNode)nodeit.next();
 896                             String edgelabel = "";
 897                             String edgedotnodeparams="";
 898
 899                             for(int i=0;i<namers.size();i++) {
 900                                 Namer name=(Namer) namers.get(i);
 901                                 String newlabel=name.edgeLabel(edge);
 902                                 String newoption=name.edgeOption(edge);
 903                                 if (!newlabel.equals("")&& ! edgelabel.equals(""))
 904                                     edgelabel+=", ";
 905                                 edgelabel+=newlabel;
 906                                 if (!newoption.equals(""))
 907                                     edgedotnodeparams+=", "+newoption;
 908                             }
 909                             edgelabel+=":[" + ((FEdge)edge).getExeTime() + "]";
 910                             Hashtable<ClassDescriptor, NewObjInfo> hashtable = ((FEdge)edge).getNewObjInfoHashtable();
 911                             if(hashtable != null) {
 912                                 Set<ClassDescriptor> keys = hashtable.keySet();
 913                                 Iterator it_keys = keys.iterator();
 914                                 while(it_keys.hasNext()) {
 915                                     ClassDescriptor cd = (ClassDescriptor)it_keys.next();
 916                                     NewObjInfo noi = hashtable.get(cd);
 917                                     edgelabel += ":{ class " + cd.getSymbol() + " | " + noi.getNewRate() + " | (" + noi.getProbability() + "%) }";
 918                                 }
 919                             }
 920                             output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
 921                         }
 922                     }
 923                 }
 924         }
 925     }
 926
 927     private Set nonmerge(GraphNode gn, Collection nodes) {
 928         HashSet newset=new HashSet();
 929         HashSet toprocess=new HashSet();
 930         toprocess.add(gn);
 931         while(!toprocess.isEmpty()) {
 932             GraphNode gn2=(GraphNode)toprocess.iterator().next();
 933             toprocess.remove(gn2);
 934             if (!gn2.merge)
 935                 newset.add(gn2);
 936             else {
 937                 Iterator edges = gn2.edges();
 938                 while (edges.hasNext()) {
 939                     Edge edge = (Edge) edges.next();
 940                     GraphNode node = edge.getTarget();
 941                     if (!newset.contains(node)&&nodes.contains(node))
 942                         toprocess.add(node);
 943                 }
 944             }
 945         }
 946         return newset;
 947     }
 948
 949     class Combination{
 950         Combination tail;
 951         Object head;
 952         Vector factors;
 953         int selectNum;
 954         int resultNum;
 955
 956         public Combination(Vector factors, int selectNum) throws Exception{
 957             this.factors = factors;
 958             if(factors.size() < selectNum) {
 959                 throw new Exception("Error: selectNum > candidates' number in combination.");
 960             }
 961             if(factors.size() == selectNum) {
 962                 this.resultNum = 1;
 963                 head = null;
 964                 tail = null;
 965                 return;
 966             }
 967             this.head = this.factors.remove(0);
 968             if(selectNum == 1) {
 969                 this.resultNum = this.factors.size() + 1;
 970                 this.tail = null;
 971                 return;
 972             }
 973             this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
 974             this.selectNum = selectNum;
 975             this.resultNum = 1;
 976             for(int i = factors.size(); i > selectNum; i--) {
 977                 this.resultNum *= i;
 978             }
 979             for(int i = factors.size() - selectNum; i > 0; i--) {
 980                 this.resultNum /= i;
 981             }
 982         }
 983
 984         public Vector next() {
 985             if(resultNum == 0) {
 986                 return null;
 987             }
 988             if(head == null) {
 989                 resultNum--;
 990                 Vector result = this.factors;
 991                 return result;
 992             }
 993             if(this.tail == null) {
 994                 resultNum--;
 995                 Vector result = new Vector();
 996                 result.add(this.head);
 997                 if(resultNum != 0) {
 998                     this.head = this.factors.remove(0);
 999                 }
1000                 return result;
1001             }
1002             Vector result = this.tail.next();
1003             if(result == null) {
1004                 if(this.factors.size() == this.selectNum) {
1005                     this.head = null;
1006                     this.tail = null;
1007                     result = this.factors;
1008                     this.resultNum--;
1009                     return result;
1010                 }
1011                 this.head = this.factors.remove(0);
1012                 try {
1013                     this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
1014                     result = this.tail.next();
1015                 } catch(Exception e) {
1016                     e.printStackTrace();
1017                 }
1018
1019             }
1020             result.add(0, head);
1021             resultNum--;
1022             return result;
1023         }
1024     }
1025 }