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