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