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     ScheduleNode startupNode = null;
  98     // For each ClassNode create a ScheduleNode containing it
  99     int i = 0;
 100     for(i = 0; i < classNodes.size(); i++) {
 101       ClassNode cn = classNodes.elementAt(i);
 102       ScheduleNode sn = new ScheduleNode(cn, 0);
 103       if(cn.getClassDescriptor().getSymbol().equals(TypeUtil.StartupClass)) {
 104         startupNode = sn;
 105       }
 106       cn.setScheduleNode(sn);
 107       scheduleNodes.add(sn);
 108       try {
 109         sn.calExeTime();
 110       } catch (Exception e) {
 111         e.printStackTrace();
 112       }
 113     }
 114
 115     // Create 'new' edges between the ScheduleNodes.
 116     Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
 117     for(i = 0; i < classNodes.size(); i++) {
 118       ClassNode cNode = classNodes.elementAt(i);
 119       ClassDescriptor cd = cNode.getClassDescriptor();
 120       Vector rootnodes  = taskanalysis.getRootNodes(cd);
 121       if(rootnodes != null) {
 122         for(int h = 0; h < rootnodes.size(); h++) {
 123           FlagState root=(FlagState)rootnodes.elementAt(h);
 124           Vector allocatingTasks = root.getAllocatingTasks();
 125           if(allocatingTasks != null) {
 126             for(int k = 0; k < allocatingTasks.size(); k++) {
 127               TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
 128               Vector<FEdge> fev = (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
 129               int numEdges = fev.size();
 130               ScheduleNode sNode = cNode.getScheduleNode();
 131               for(int j = 0; j < numEdges; j++) {
 132                 FEdge pfe = fev.elementAt(j);
 133                 FEdge.NewObjInfo noi = pfe.getNewObjInfo(cd);
 134                 if ((noi == null) || (noi.getNewRate() == 0) || (noi.getProbability() == 0)) {
 135                   // fake creating edge, do not need to create corresponding 'new' edge
 136                   continue;
 137                 }
 138                 if(noi.getRoot() == null) {
 139                   // set root FlagState
 140                   noi.setRoot(root);
 141                 }
 142                 FlagState pfs = (FlagState)pfe.getTarget();
 143                 ClassDescriptor pcd = pfs.getClassDescriptor();
 144                 ClassNode pcNode = cdToCNodes.get(pcd);
 145
 146                 ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", root, ScheduleEdge.NEWEDGE, 0);
 147                 sEdge.setFEdge(pfe);
 148                 sEdge.setSourceCNode(pcNode);
 149                 sEdge.setTargetCNode(cNode);
 150                 sEdge.setTargetFState(root);
 151                 sEdge.setNewRate(noi.getNewRate());
 152                 sEdge.setProbability(noi.getProbability());
 153                 pcNode.getScheduleNode().addEdge(sEdge);
 154                 scheduleEdges.add(sEdge);
 155                 if((j !=0 ) || (k != 0) || (h != 0)) {
 156                   toBreakDown.add(sEdge);
 157                 }
 158               }
 159               fev = null;
 160             }
 161             allocatingTasks = null;
 162           }
 163         }
 164         rootnodes = null;
 165       }
 166     }
 167     cdToCNodes = null;
 168
 169     // Break down the 'cycle's
 170     try {
 171       for(i = 0; i < toBreakDown.size(); i++ ) {
 172         cloneSNodeList(toBreakDown.elementAt(i), false);
 173       }
 174       toBreakDown = null;
 175     } catch (Exception e) {
 176       e.printStackTrace();
 177       System.exit(-1);
 178     }
 179
 180     // Remove fake 'new' edges
 181     for(i = 0; i < scheduleEdges.size(); i++) {
 182       ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i);
 183       if((0 == se.getNewRate()) || (0 == se.getProbability())) {
 184         scheduleEdges.removeElement(se);
 185         scheduleNodes.removeElement(se.getTarget());
 186       }
 187     }
 188
 189     // Do topology sort of the ClassNodes and ScheduleEdges.
 190     Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
 191     Vector<ScheduleNode> tempSNodes = ClassNode.DFS.topology(scheduleNodes, ssev);
 192     scheduleNodes.removeAllElements();
 193     scheduleNodes = tempSNodes;
 194     tempSNodes = null;
 195     scheduleEdges.removeAllElements();
 196     scheduleEdges = ssev;
 197     ssev = null;
 198     sorted = true;
 199
 200     // Set the cid of these ScheduleNode
 201     Queue<ScheduleNode> toVisit = new LinkedList<ScheduleNode>();
 202     toVisit.add(startupNode);
 203     while(!toVisit.isEmpty()) {
 204       ScheduleNode sn = toVisit.poll();
 205       if(sn.getCid() == -1) {
 206         // not visited before
 207         sn.setCid(ScheduleNode.colorID++);
 208         Iterator it_edge = sn.edges();
 209         while(it_edge.hasNext()) {
 210           toVisit.add((ScheduleNode)((ScheduleEdge)it_edge.next()).getTarget());
 211         }
 212       }
 213     }
 214     toVisit = null;
 215
 216     if(this.state.PRINTSCHEDULING) {
 217         SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes);
 218     }
 219   }
 220
 221   public void scheduleAnalysis() {
 222     // First iteration
 223     int i = 0;
 224     //Access the ScheduleEdges in reverse topology order
 225     Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses = new Hashtable<FEdge, Vector<ScheduleEdge>>();
 226     Hashtable<ScheduleNode, Vector<FEdge>> sn2fes = new Hashtable<ScheduleNode, Vector<FEdge>>();
 227     ScheduleNode preSNode = null;
 228     for(i = scheduleEdges.size(); i > 0; i--) {
 229       ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i-1);
 230       if(ScheduleEdge.NEWEDGE == se.getType()) {
 231         if(preSNode == null) {
 232           preSNode = (ScheduleNode)se.getSource();
 233         }
 234
 235         boolean split = false;
 236         FEdge fe = se.getFEdge();
 237         if(fe.getSource() == fe.getTarget()) {
 238           // back edge
 239           try {
 240             int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
 241             int rate = 0;
 242             if(repeat > 1) {
 243               for(int j = 1; j< repeat; j++ ) {
 244                 cloneSNodeList(se, true);
 245               }
 246               se.setNewRate(1);
 247               se.setProbability(100);
 248             }
 249             try {
 250               rate = (int)Math.ceil(se.getListExeTime()/ calInExeTime(se.getSourceFState()));
 251             } catch (Exception e) {
 252               e.printStackTrace();
 253             }
 254             for(int j = rate - 1; j > 0; j--) {
 255               for(int k = repeat; k > 0; k--) {
 256                 cloneSNodeList(se, true);
 257               }
 258             }
 259           } catch (Exception e) {
 260             e.printStackTrace();
 261             System.exit(-1);
 262           }
 263         } else {
 264           // if preSNode is not the same as se's source ScheduleNode
 265           // handle any ScheduleEdges previously put into fe2ses whose source ScheduleNode is preSNode
 266           boolean same = (preSNode == se.getSource());
 267           if(!same) {
 268             // check the topology sort, only process those after se.getSource()
 269             if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()) {
 270               if(sn2fes.containsKey(preSNode)) {
 271                 Vector<FEdge> fes = sn2fes.remove(preSNode);
 272                 for(int j = 0; j < fes.size(); j++) {
 273                   FEdge tempfe = fes.elementAt(j);
 274                   Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 275                   ScheduleEdge tempse = ses.elementAt(0);
 276                   int temptime = tempse.getListExeTime();
 277                   // find out the ScheduleEdge with least exeTime
 278                   for(int k = 1; k < ses.size(); k++) {
 279                     int ttemp = ses.elementAt(k).getListExeTime();
 280                     if(ttemp < temptime) {
 281                       tempse = ses.elementAt(k);
 282                       temptime = ttemp;
 283                     }
 284                   }
 285                   // handle the tempse
 286                   handleScheduleEdge(tempse, true);
 287                   ses.removeElement(tempse);
 288                   // handle other ScheduleEdges
 289                   for(int k = 0; k < ses.size(); k++) {
 290                     handleScheduleEdge(ses.elementAt(k), false);
 291                   }
 292                   ses = null;
 293                   fe2ses.remove(tempfe);
 294                 }
 295                 fes = null;
 296               }
 297             }
 298             preSNode = (ScheduleNode)se.getSource();
 299           }
 300
 301           // if fe is the last task inside this ClassNode, delay the expanding and merging until we find all such 'new' edges
 302           // associated with a last task inside this ClassNode
 303           if(!fe.getTarget().edges().hasNext()) {
 304             if(fe2ses.get(fe) == null) {
 305               fe2ses.put(fe, new Vector<ScheduleEdge>());
 306             }
 307             if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
 308               sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
 309             }
 310             if(!fe2ses.get(fe).contains(se)) {
 311               fe2ses.get(fe).add(se);
 312             }
 313             if(!sn2fes.get((ScheduleNode)se.getSource()).contains(fe)) {
 314               sn2fes.get((ScheduleNode)se.getSource()).add(fe);
 315             }
 316           } else {
 317             // As this is not a last task, first handle available ScheduleEdges previously put into fe2ses
 318             if((same) && (sn2fes.containsKey(preSNode))) {
 319               Vector<FEdge> fes = sn2fes.remove(preSNode);
 320               for(int j = 0; j < fes.size(); j++) {
 321                 FEdge tempfe = fes.elementAt(j);
 322                 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 323                 ScheduleEdge tempse = ses.elementAt(0);
 324                 int temptime = tempse.getListExeTime();
 325                 // find out the ScheduleEdge with least exeTime
 326                 for(int k = 1; k < ses.size(); k++) {
 327                   int ttemp = ses.elementAt(k).getListExeTime();
 328                   if(ttemp < temptime) {
 329                     tempse = ses.elementAt(k);
 330                     temptime = ttemp;
 331                   }
 332                 }
 333                 // handle the tempse
 334                 handleScheduleEdge(tempse, true);
 335                 ses.removeElement(tempse);
 336                 // handle other ScheduleEdges
 337                 for(int k = 0; k < ses.size(); k++) {
 338                   handleScheduleEdge(ses.elementAt(k), false);
 339                 }
 340                 ses = null;
 341                 fe2ses.remove(tempfe);
 342               }
 343               fes = null;
 344             }
 345
 346             if((!(se.getTransTime() < this.transThreshold)) && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
 347               split = true;
 348               splitSNode(se, true);
 349             } else {
 350               // handle this ScheduleEdge
 351               handleScheduleEdge(se, true);
 352             }
 353           }
 354         }
 355       }
 356     }
 357     if(!fe2ses.isEmpty()) {
 358       Set<FEdge> keys = fe2ses.keySet();
 359       Iterator it_keys = keys.iterator();
 360       while(it_keys.hasNext()) {
 361         FEdge tempfe = (FEdge)it_keys.next();
 362         Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 363         ScheduleEdge tempse = ses.elementAt(0);
 364         int temptime = tempse.getListExeTime();
 365         // find out the ScheduleEdge with least exeTime
 366         for(int k = 1; k < ses.size(); k++) {
 367           int ttemp = ses.elementAt(k).getListExeTime();
 368           if(ttemp < temptime) {
 369             tempse = ses.elementAt(k);
 370             temptime = ttemp;
 371           }
 372         }
 373         // handle the tempse
 374         handleScheduleEdge(tempse, true);
 375         ses.removeElement(tempse);
 376         // handle other ScheduleEdges
 377         for(int k = 0; k < ses.size(); k++) {
 378           handleScheduleEdge(ses.elementAt(k), false);
 379         }
 380         ses = null;
 381       }
 382       keys = null;
 383       fe2ses.clear();
 384       sn2fes.clear();
 385     }
 386     fe2ses = null;
 387     sn2fes = null;
 388
 389     if(this.state.PRINTSCHEDULING) {
 390         SchedulingUtil.printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
 391     }
 392   }
 393
 394   private void handleScheduleEdge(ScheduleEdge se, boolean merge) {
 395     try {
 396       int rate = 0;
 397       int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
 398       if(merge) {
 399         try {
 400           if(se.getListExeTime() == 0) {
 401             rate = repeat;
 402           } else {
 403             rate = (int)Math.ceil((se.getTransTime() - calInExeTime(se.getSourceFState()))/ se.getListExeTime());
 404           }
 405           if(rate < 0 ) {
 406             rate = 0;
 407           }
 408         } catch (Exception e) {
 409           e.printStackTrace();
 410         }
 411         if(0 == rate) {
 412           // clone the whole ScheduleNode lists starting with se's target
 413           for(int j = 1; j < repeat; j++ ) {
 414             cloneSNodeList(se, true);
 415           }
 416           se.setNewRate(1);
 417           se.setProbability(100);
 418         } else {
 419           repeat -= rate;
 420           if(repeat > 0) {
 421             // clone the whole ScheduleNode lists starting with se's target
 422             for(int j = 0; j < repeat; j++ ) {
 423               cloneSNodeList(se, true);
 424             }
 425             se.setNewRate(rate);
 426             se.setProbability(100);
 427           }
 428         }
 429         // merge the original ScheduleNode to the source ScheduleNode
 430         ((ScheduleNode)se.getSource()).mergeSEdge(se);
 431         scheduleNodes.remove(se.getTarget());
 432         scheduleEdges.remove(se);
 433         // As se has been changed into an internal edge inside a ScheduleNode,
 434         // change the source and target of se from original ScheduleNodes into ClassNodes.
 435         if(se.getType() == ScheduleEdge.NEWEDGE) {
 436           se.setTarget(se.getTargetCNode());
 437           se.setSource(se.getSourceCNode());
 438           se.getTargetCNode().addEdge(se);
 439         }
 440       } else {
 441         // clone the whole ScheduleNode lists starting with se's target
 442         for(int j = 1; j < repeat; j++ ) {
 443           cloneSNodeList(se, true);
 444         }
 445         se.setNewRate(1);
 446         se.setProbability(100);
 447       }
 448     } catch (Exception e) {
 449       e.printStackTrace();
 450       System.exit(-1);
 451     }
 452   }
 453
 454   private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) throws Exception {
 455     Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();     // hashtable from classnode in orignal se's targe to cloned one
 456     ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
 457     scheduleNodes.add(csNode);
 458
 459     // Clone all the external in ScheduleEdges
 460     int i;
 461     if(copyIE) {
 462       Vector inedges = sEdge.getTarget().getInedgeVector();
 463       for(i = 0; i < inedges.size(); i++) {
 464         ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
 465         ScheduleEdge se;
 466         switch(tse.getType()) {
 467         case ScheduleEdge.NEWEDGE: {
 468           se = new ScheduleEdge(csNode, "new", tse.getFstate(), tse.getType(), 0);
 469           se.setProbability(100);
 470           se.setNewRate(1);
 471           break;
 472         }
 473
 474         case ScheduleEdge.TRANSEDGE: {
 475           se = new ScheduleEdge(csNode, "transmit", tse.getFstate(), tse.getType(), 0);
 476           se.setProbability(tse.getProbability());
 477           se.setNewRate(tse.getNewRate());
 478           break;
 479         }
 480
 481         default: {
 482           throw new Exception("Error: not valid ScheduleEdge here");
 483         }
 484         }
 485         se.setSourceCNode(tse.getSourceCNode());
 486         se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
 487         se.setFEdge(tse.getFEdge());
 488         se.setTargetFState(tse.getTargetFState());
 489         se.setIsclone(true);
 490         tse.getSource().addEdge(se);
 491         scheduleEdges.add(se);
 492       }
 493       inedges = null;
 494     } else {
 495       sEdge.getTarget().removeInedge(sEdge);
 496       sEdge.setTarget(csNode);
 497       csNode.getInedgeVector().add(sEdge);
 498       sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
 499       sEdge.setIsclone(true);
 500     }
 501
 502     Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>();     // all nodes to be cloned
 503     Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>();     //clone nodes
 504     Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>();     // queue of the mappings of classnodes inside cloned ScheduleNode
 505     Vector<ScheduleNode> origins = new Vector<ScheduleNode>();     // queue of source ScheduleNode cloned
 506     Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();     // mapping from cloned ScheduleNode to clone ScheduleNode
 507     clone.add(csNode);
 508     toClone.add((ScheduleNode)sEdge.getTarget());
 509     origins.addElement((ScheduleNode)sEdge.getTarget());
 510     sn2sn.put((ScheduleNode)sEdge.getTarget(), csNode);
 511     qcn2cn.add(cn2cn);
 512     while(!toClone.isEmpty()) {
 513       Hashtable<ClassNode, ClassNode> tocn2cn = new Hashtable<ClassNode, ClassNode>();
 514       csNode = clone.poll();
 515       ScheduleNode osNode = toClone.poll();
 516       cn2cn = qcn2cn.poll();
 517       // Clone all the external ScheduleEdges and the following ScheduleNodes
 518       Vector edges = osNode.getEdgeVector();
 519       for(i = 0; i < edges.size(); i++) {
 520         ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
 521         ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
 522         scheduleNodes.add(tSNode);
 523         clone.add(tSNode);
 524         toClone.add((ScheduleNode)tse.getTarget());
 525         origins.addElement((ScheduleNode)tse.getTarget());
 526         sn2sn.put((ScheduleNode)tse.getTarget(), tSNode);
 527         qcn2cn.add(tocn2cn);
 528         ScheduleEdge se = null;
 529         switch(tse.getType()) {
 530         case ScheduleEdge.NEWEDGE: {
 531           se = new ScheduleEdge(tSNode, "new", tse.getFstate(), tse.getType(), 0);
 532           break;
 533         }
 534
 535         case ScheduleEdge.TRANSEDGE: {
 536           se = new ScheduleEdge(tSNode, "transmit", tse.getFstate(), tse.getType(), 0);
 537           break;
 538         }
 539
 540         default: {
 541           throw new Exception("Error: not valid ScheduleEdge here");
 542         }
 543         }
 544         se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
 545         se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
 546         se.setFEdge(tse.getFEdge());
 547         se.setTargetFState(tse.getTargetFState());
 548         se.setProbability(tse.getProbability());
 549         se.setNewRate(tse.getNewRate());
 550         se.setIsclone(true);
 551         csNode.addEdge(se);
 552         scheduleEdges.add(se);
 553       }
 554       tocn2cn = null;
 555       edges = null;
 556     }
 557
 558     toClone = null;
 559     clone = null;
 560     qcn2cn = null;
 561     cn2cn = null;
 562     origins = null;
 563     sn2sn = null;
 564   }
 565
 566   private int calInExeTime(FlagState fs) throws Exception {
 567     int exeTime = 0;
 568     ClassDescriptor cd = fs.getClassDescriptor();
 569     ClassNode cNode = cd2ClassNode.get(cd);
 570     exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
 571     while(true) {
 572       Vector inedges = cNode.getInedgeVector();
 573       // Now that there are associate ScheduleEdges, there may be multiple inedges of a ClassNode
 574       if(inedges.size() > 1) {
 575         throw new Exception("Error: ClassNode's inedges more than one!");
 576       }
 577       if(inedges.size() > 0) {
 578         ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
 579         cNode = (ClassNode)sEdge.getSource();
 580         exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
 581       } else {
 582         break;
 583       }
 584       inedges = null;
 585     }
 586     exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
 587     return exeTime;
 588   }
 589
 590   private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) {
 591     assert(ScheduleEdge.NEWEDGE == se.getType());
 592
 593     FEdge fe = se.getFEdge();
 594     FlagState fs = (FlagState)fe.getTarget();
 595     FlagState nfs = (FlagState)fs.clone();
 596     fs.getEdgeVector().removeAllElements();
 597     nfs.getInedgeVector().removeAllElements();
 598     ClassNode sCNode = se.getSourceCNode();
 599
 600     // split the subtree whose root is nfs from the whole flag transition tree
 601     Vector<FlagState> sfss = sCNode.getFlagStates();
 602     Vector<FlagState> fStates = new Vector<FlagState>();
 603     Queue<FlagState> toiterate = new LinkedList<FlagState>();
 604     toiterate.add(nfs);
 605     fStates.add(nfs);
 606     while(!toiterate.isEmpty()) {
 607       FlagState tfs = toiterate.poll();
 608       Iterator it_edges = tfs.edges();
 609       while(it_edges.hasNext()) {
 610         FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
 611         if(!fStates.contains(temp)) {
 612           fStates.add(temp);
 613           toiterate.add(temp);
 614           sfss.removeElement(temp);
 615         }
 616       }
 617     }
 618     sfss = null;
 619     Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
 620     fStates = null;
 621     // create a ClassNode and ScheduleNode for this subtree
 622     ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
 623     ScheduleNode sNode = new ScheduleNode(cNode, 0);
 624     cNode.setScheduleNode(sNode);
 625     cNode.setSorted(true);
 626     cNode.setTransTime(sCNode.getTransTime());
 627     classNodes.add(cNode);
 628     scheduleNodes.add(sNode);
 629     try {
 630       sNode.calExeTime();
 631     } catch (Exception e) {
 632       e.printStackTrace();
 633     }
 634     // flush the exeTime of fs and its ancestors
 635     fs.setExeTime(0);
 636     toiterate.add(fs);
 637     while(!toiterate.isEmpty()) {
 638       FlagState tfs = toiterate.poll();
 639       int ttime = tfs.getExeTime();
 640       Iterator it_inedges = tfs.inedges();
 641       while(it_inedges.hasNext()) {
 642         FEdge fEdge = (FEdge)it_inedges.next();
 643         FlagState temp = (FlagState)fEdge.getSource();
 644         int time = fEdge.getExeTime() + ttime;
 645         if(temp.getExeTime() > time) {
 646           temp.setExeTime(time);
 647           toiterate.add(temp);
 648         }
 649       }
 650     }
 651     toiterate = null;
 652
 653     // create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode
 654     ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", fs, ScheduleEdge.TRANSEDGE, 0);   //new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
 655     sEdge.setFEdge(fe);
 656     sEdge.setSourceCNode(sCNode);
 657     sEdge.setTargetCNode(cNode);
 658     sEdge.setTargetFState(nfs);
 659     // TODO
 660     // Add calculation codes for calculating transmit time of an object
 661     sEdge.setTransTime(cNode.getTransTime());
 662     se.getSource().addEdge(sEdge);
 663     scheduleEdges.add(sEdge);
 664     // remove the ClassNodes and internal ScheduleEdges out of this subtree to the new ScheduleNode
 665     ScheduleNode oldSNode = (ScheduleNode)se.getSource();
 666     Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
 667     Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
 668     Vector<ClassNode> rCNodes = new Vector<ClassNode>();
 669     rCNodes.addElement(sCNode);
 670     if(it_isEdges != null) {
 671       while(it_isEdges.hasNext()) {
 672         ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
 673         if(rCNodes.contains(tse.getSourceCNode())) {
 674           if(sCNode == tse.getSourceCNode()) {
 675             if ((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
 676               tse.setSource(cNode);
 677               tse.setSourceCNode(cNode);
 678             } else {
 679               continue;
 680             }
 681           }
 682           sNode.getScheduleEdges().addElement(tse);
 683           sNode.getClassNodes().addElement(tse.getTargetCNode());
 684           rCNodes.addElement(tse.getTargetCNode());
 685           oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
 686           toremove.addElement(tse);
 687         }
 688       }
 689     }
 690     oldSNode.getScheduleEdges().removeAll(toremove);
 691     toremove.clear();
 692     // redirect ScheudleEdges out of this subtree to the new ScheduleNode
 693     Iterator it_sEdges = se.getSource().edges();
 694     while(it_sEdges.hasNext()) {
 695       ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
 696       if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
 697         if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
 698           tse.setSource(sNode);
 699           tse.setSourceCNode(cNode);
 700           sNode.getEdgeVector().addElement(tse);
 701           toremove.add(tse);
 702         }
 703       }
 704     }
 705     se.getSource().getEdgeVector().removeAll(toremove);
 706     toremove = null;
 707     rCNodes = null;
 708     sFStates = null;
 709
 710     try {
 711       if(!copy) {
 712         //merge se into its source ScheduleNode
 713         sNode.setCid(((ScheduleNode)se.getSource()).getCid());
 714         ((ScheduleNode)se.getSource()).mergeSEdge(se);
 715         scheduleNodes.remove(se.getTarget());
 716         scheduleEdges.removeElement(se);
 717         // As se has been changed into an internal edge inside a ScheduleNode,
 718         // change the source and target of se from original ScheduleNodes into ClassNodes.
 719         if(se.getType() == ScheduleEdge.NEWEDGE) {
 720           se.setTarget(se.getTargetCNode());
 721           se.setSource(se.getSourceCNode());
 722           se.getTargetCNode().addEdge(se);
 723         }
 724       } else {
 725         sNode.setCid(ScheduleNode.colorID++);
 726         handleScheduleEdge(se, true);
 727       }
 728     } catch (Exception e) {
 729       e.printStackTrace();
 730       System.exit(-1);
 731     }
 732
 733     return sNode;
 734   }
 735
 736   public void schedule() throws Exception {
 737     if(this.coreNum == -1) {
 738       throw new Exception("Error: un-initialized coreNum when doing scheduling.");
 739     }
 740
 741     if(this.scheduleGraphs == null) {
 742       this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
 743     }
 744
 745     int reduceNum = this.scheduleNodes.size() - this.coreNum;
 746
 747     // Combine some ScheduleNode if necessary
 748     // May generate multiple graphs suggesting candidate schedulings
 749     if(!(reduceNum > 0)) {
 750       // Enough cores, no need to combine any ScheduleNode
 751       this.scheduleGraphs.addElement(this.scheduleNodes);
 752       int gid = 1;
 753       if(this.state.PRINTSCHEDULING) {
 754           String path = "scheduling_" + gid + ".dot";
 755           SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
 756       }
 757     } else {
 758       // Go through all the Scheudle Nodes, organize them in order of their cid
 759       Vector<Vector<ScheduleNode>> sNodeVecs = new Vector<Vector<ScheduleNode>>();
 760       for(int i = 0; i < this.scheduleNodes.size(); i++) {
 761         ScheduleNode tmpn = this.scheduleNodes.elementAt(i);
 762         int index = tmpn.getCid();
 763         while(sNodeVecs.size() <= index) {
 764           sNodeVecs.add(null);
 765         }
 766         if(sNodeVecs.elementAt(index) == null) {
 767           sNodeVecs.setElementAt(new Vector<ScheduleNode>(), index);
 768         }
 769         sNodeVecs.elementAt(index).add(tmpn);
 770       }
 771
 772       CombinationUtil.RootsGenerator rGen = CombinationUtil.allocateRootsGenerator(sNodeVecs, this.coreNum);
 773
 774       int gid = 1;
 775       while(rGen.nextGen()) {
 776         // first get the chosen rootNodes
 777         Vector<Vector<ScheduleNode>> rootNodes = rGen.getRootNodes();
 778         Vector<Vector<ScheduleNode>> nodes2combine = rGen.getNode2Combine();
 779
 780         CombinationUtil.CombineGenerator cGen = CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine);
 781         while (cGen.nextGen()) {
 782           Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
 783           Vector<ScheduleNode> sNodes = generateScheduling(rootNodes, combine, gid++);
 784           this.scheduleGraphs.add(sNodes);
 785           combine = null;
 786           sNodes = null;
 787         }
 788         rootNodes = null;
 789         nodes2combine = null;
 790       }
 791       sNodeVecs = null;
 792     }
 793
 794     // Generate schedulings according to result schedule graph
 795     if(this.schedulings == null) {
 796       this.schedulings = new Vector<Vector<Schedule>>();
 797     }
 798
 799     Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
 800     Iterator it_tasks = state.getTaskSymbolTable().getDescriptorsIterator();
 801     while(it_tasks.hasNext()) {
 802       TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 803       if(td.numParameters() > 1) {
 804         multiparamtds.addElement(td);
 805       }
 806     }
 807
 808     for(int i = 0; i < this.scheduleGraphs.size(); i++) {
 809       Hashtable<TaskDescriptor, Vector<Schedule>> td2cores = new Hashtable<TaskDescriptor, Vector<Schedule>>();       // multiparam tasks reside on which cores
 810       Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
 811       Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
 812       // for each ScheduleNode create a schedule node representing a core
 813       Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
 814       int j = 0;
 815       for(j = 0; j < scheduleGraph.size(); j++) {
 816         sn2coreNum.put(scheduleGraph.elementAt(j), j);
 817       }
 818       int startupcore = 0;
 819       boolean setstartupcore = false;
 820       Schedule startup = null;
 821       for(j = 0; j < scheduleGraph.size(); j++) {
 822         Schedule tmpSchedule = new Schedule(j);
 823         ScheduleNode sn = scheduleGraph.elementAt(j);
 824
 825         Vector<ClassNode> cNodes = sn.getClassNodes();
 826         for(int k = 0; k < cNodes.size(); k++) {
 827           Iterator it_flags = cNodes.elementAt(k).getFlags();
 828           while(it_flags.hasNext()) {
 829             FlagState fs = (FlagState)it_flags.next();
 830             Iterator it_edges = fs.edges();
 831             while(it_edges.hasNext()) {
 832               TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
 833               tmpSchedule.addTask(td);
 834               if(!td2cores.containsKey(td)) {
 835                 td2cores.put(td, new Vector<Schedule>());
 836               }
 837               Vector<Schedule> tmpcores = td2cores.get(td);
 838               if(!tmpcores.contains(tmpSchedule)) {
 839                 tmpcores.add(tmpSchedule);
 840               }
 841               tmpcores = null;
 842               // if the FlagState can be fed to some multi-param tasks,
 843               // need to record corresponding ally cores later
 844               if(td.numParameters() > 1) {
 845                 tmpSchedule.addFState4TD(td, fs);
 846               }
 847               if(td.getParamType(0).getClassDesc().getSymbol().equals(TypeUtil.StartupClass)) {
 848                 assert(!setstartupcore);
 849                 startupcore = j;
 850                 startup = tmpSchedule;
 851                 setstartupcore = true;
 852               }
 853             }
 854           }
 855         }
 856         cNodes = null;
 857
 858         // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
 859         Iterator it_edges = sn.edges();
 860         while(it_edges.hasNext()) {
 861           ScheduleEdge se = (ScheduleEdge)it_edges.next();
 862           ScheduleNode target = (ScheduleNode)se.getTarget();
 863           Integer targetcore = sn2coreNum.get(target);
 864           switch(se.getType()) {
 865           case ScheduleEdge.NEWEDGE: {
 866             for(int k = 0; k < se.getNewRate(); k++) {
 867               tmpSchedule.addTargetCore(se.getFstate(), targetcore);
 868             }
 869             break;
 870           }
 871
 872           case ScheduleEdge.TRANSEDGE: {
 873             // 'transmit' edge
 874             tmpSchedule.addTargetCore(se.getFstate(), targetcore, se.getTargetFState());
 875             // check if missed some FlagState associated with some multi-parameter
 876             // task, which has been cloned when splitting a ClassNode
 877             FlagState fs = se.getSourceFState();
 878             FlagState tfs = se.getTargetFState();
 879             Iterator it = tfs.edges();
 880             while(it.hasNext()) {
 881               TaskDescriptor td = ((FEdge)it.next()).getTask();
 882               if(td.numParameters() > 1) {
 883                 if(tmpSchedule.getTasks().contains(td)) {
 884                   tmpSchedule.addFState4TD(td, fs);
 885                 }
 886               }
 887             }
 888             break;
 889           }
 890           }
 891         }
 892         it_edges = sn.getScheduleEdgesIterator();
 893         while(it_edges.hasNext()) {
 894           ScheduleEdge se = (ScheduleEdge)it_edges.next();
 895           switch(se.getType()) {
 896           case ScheduleEdge.NEWEDGE: {
 897             for(int k = 0; k < se.getNewRate(); k++) {
 898               tmpSchedule.addTargetCore(se.getFstate(), j);
 899             }
 900             break;
 901           }
 902
 903           case ScheduleEdge.TRANSEDGE: {
 904             // 'transmit' edge
 905             tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState());
 906             break;
 907           }
 908           }
 909         }
 910         scheduling.add(tmpSchedule);
 911       }
 912
 913       int number = this.coreNum;
 914       if(scheduling.size() < number) {
 915         number = scheduling.size();
 916       }
 917
 918       // set up all the associate ally cores
 919       if(multiparamtds.size() > 0) {
 920         for(j = 0; j < multiparamtds.size(); ++j) {
 921           TaskDescriptor td = multiparamtds.elementAt(j);
 922           Vector<FEdge> fes = (Vector<FEdge>) this.taskanalysis.getFEdgesFromTD(td);
 923           Vector<Schedule> cores = td2cores.get(td);
 924           for(int k = 0; k < cores.size(); ++k) {
 925             Schedule tmpSchedule = cores.elementAt(k);
 926
 927             for(int h = 0; h < fes.size(); ++h) {
 928               FEdge tmpfe = fes.elementAt(h);
 929               FlagState tmpfs = (FlagState)tmpfe.getTarget();
 930               Vector<TaskDescriptor> tmptds = new Vector<TaskDescriptor>();
 931               if((tmpSchedule.getTargetCoreTable() == null) || (!tmpSchedule.getTargetCoreTable().contains(tmpfs))) {
 932                 // add up all possible cores' info
 933                 Iterator it_edges = tmpfs.edges();
 934                 while(it_edges.hasNext()) {
 935                   TaskDescriptor tmptd = ((FEdge)it_edges.next()).getTask();
 936                   if(!tmptds.contains(tmptd)) {
 937                     tmptds.add(tmptd);
 938                     Vector<Schedule> tmpcores = td2cores.get(tmptd);
 939                     for(int m = 0; m < tmpcores.size(); ++m) {
 940                       if(m != tmpSchedule.getCoreNum()) {
 941                         // if the FlagState can be fed to some multi-param tasks,
 942                         // need to record corresponding ally cores later
 943                         if(tmptd.numParameters() > 1) {
 944                           tmpSchedule.addAllyCore(tmpfs, tmpcores.elementAt(m).getCoreNum());
 945                         } else {
 946                           tmpSchedule.addTargetCore(tmpfs, tmpcores.elementAt(m).getCoreNum());
 947                         }
 948                       }
 949                     }
 950                     tmpcores = null;
 951                   }
 952                 }
 953               }
 954               tmptds = null;
 955             }
 956
 957             if(cores.size() > 1) {
 958               Vector<FlagState> tmpfss = tmpSchedule.getFStates4TD(td);
 959               for(int h = 0; h < tmpfss.size(); ++h) {
 960                 for(int l = 0; l < cores.size(); ++l) {
 961                   if(l != k) {
 962                     tmpSchedule.addAllyCore(tmpfss.elementAt(h), cores.elementAt(l).getCoreNum());
 963                   }
 964                 }
 965               }
 966               tmpfss = null;
 967             }
 968           }
 969           fes = null;
 970           cores = null;
 971         }
 972       }
 973       this.schedulings.add(scheduling);
 974       td2cores = null;
 975       scheduleGraph = null;
 976       scheduling = null;
 977       sn2coreNum = null;
 978     }
 979     multiparamtds = null;
 980   }
 981
 982   public Vector<ScheduleNode> generateScheduling(Vector<Vector<ScheduleNode>> rootnodes, Vector<Vector<CombinationUtil.Combine>> combine, int gid) {
 983     Vector<ScheduleNode> result = new Vector<ScheduleNode>();
 984
 985     // clone the ScheduleNodes
 986     Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
 987     Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
 988     for(int i = 0; i < this.scheduleNodes.size(); i++) {
 989       Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
 990       ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
 991       ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
 992       result.add(i, temp);
 993       sn2hash.put(temp, cn2cn);
 994       sn2sn.put(tocopy, temp);
 995       cn2cn = null;
 996     }
 997     // clone the ScheduleEdges
 998     for(int i = 0; i < this.scheduleEdges.size(); i++) {
 999       ScheduleEdge sse = this.scheduleEdges.elementAt(i);
1000       ScheduleNode csource = sn2sn.get(sse.getSource());
1001       ScheduleNode ctarget = sn2sn.get(sse.getTarget());
1002       Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
1003       Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
1004       ScheduleEdge se =  null;
1005       switch(sse.getType()) {
1006       case ScheduleEdge.NEWEDGE: {
1007         se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid);       //new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
1008         se.setProbability(sse.getProbability());
1009         se.setNewRate(sse.getNewRate());
1010         break;
1011       }
1012
1013       case ScheduleEdge.TRANSEDGE: {
1014         se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid);       //new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
1015         break;
1016       }
1017       }
1018       se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
1019       se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
1020       se.setFEdge(sse.getFEdge());
1021       se.setTargetFState(sse.getTargetFState());
1022       se.setIsclone(true);
1023       csource.addEdge(se);
1024       sourcecn2cn = null;
1025       targetcn2cn = null;
1026     }
1027
1028     // combine those nodes in combine with corresponding rootnodes
1029     for(int i = 0; i < combine.size(); i++) {
1030       if(combine.elementAt(i) != null) {
1031         for(int j = 0; j < combine.elementAt(i).size(); j++) {
1032           CombinationUtil.Combine tmpcombine = combine.elementAt(i).elementAt(j);
1033           ScheduleNode tocombine = sn2sn.get(tmpcombine.node);
1034           ScheduleNode root = sn2sn.get(rootnodes.elementAt(tmpcombine.root).elementAt(tmpcombine.index));
1035           ScheduleEdge se = (ScheduleEdge)tocombine.inedges().next();
1036           try {
1037             if(root.equals(((ScheduleNode)se.getSource()))) {
1038               root.mergeSEdge(se);
1039               if(ScheduleEdge.NEWEDGE == se.getType()) {
1040                 // As se has been changed into an internal edge inside a ScheduleNode,
1041                 // change the source and target of se from original ScheduleNodes into ClassNodes.
1042                 se.setTarget(se.getTargetCNode());
1043                 se.setSource(se.getSourceCNode());
1044                 se.getTargetCNode().addEdge(se);
1045               }
1046             } else {
1047               root.mergeSNode(tocombine);
1048             }
1049           } catch(Exception e) {
1050             e.printStackTrace();
1051             System.exit(-1);
1052           }
1053           result.removeElement(tocombine);
1054         }
1055       }
1056     }
1057
1058     sn2hash = null;
1059     sn2sn = null;
1060
1061     if(this.state.PRINTSCHEDULING) {
1062         String path = "scheduling_" + gid + ".dot";
1063         SchedulingUtil.printScheduleGraph(path, result);
1064     }
1065
1066     return result;
1067   }
1068 }