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                 case ScheduleEdge.TRANSEDGE: {
 469                     se = new ScheduleEdge(csNode, "transmit", tse.getFstate(), tse.getType(), 0);
 470                     se.setProbability(tse.getProbability());
 471                     se.setNewRate(tse.getNewRate());
 472                     break;
 473                 }
 474                 default: {
 475                     throw new Exception("Error: not valid ScheduleEdge here");
 476                 }
 477                 }
 478                 se.setSourceCNode(tse.getSourceCNode());
 479                 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
 480                 se.setFEdge(tse.getFEdge());
 481                 se.setTargetFState(tse.getTargetFState());
 482                 se.setIsclone(true);
 483                 tse.getSource().addEdge(se);
 484                 scheduleEdges.add(se);
 485             }
 486             inedges = null;
 487         } else {
 488             sEdge.getTarget().removeInedge(sEdge);
 489             sEdge.setTarget(csNode);
 490             csNode.getInedgeVector().add(sEdge);
 491             sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
 492             sEdge.setIsclone(true);
 493         }
 494
 495         Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>(); // all nodes to be cloned
 496         Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>(); //clone nodes
 497         Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>(); // queue of the mappings of classnodes inside cloned ScheduleNode
 498         Vector<ScheduleNode> origins = new Vector<ScheduleNode>(); // queue of source ScheduleNode cloned
 499         Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>(); // mapping from cloned ScheduleNode to clone ScheduleNode
 500         clone.add(csNode);
 501         toClone.add((ScheduleNode)sEdge.getTarget());
 502         origins.addElement((ScheduleNode)sEdge.getTarget());
 503         sn2sn.put((ScheduleNode)sEdge.getTarget(), csNode);
 504         qcn2cn.add(cn2cn);
 505         while(!toClone.isEmpty()) {
 506             Hashtable<ClassNode, ClassNode> tocn2cn = new Hashtable<ClassNode, ClassNode>();
 507             csNode = clone.poll();
 508             ScheduleNode osNode = toClone.poll();
 509             cn2cn = qcn2cn.poll();
 510             // Clone all the external ScheduleEdges and the following ScheduleNodes
 511             Vector edges = osNode.getEdgeVector();
 512             for(i = 0; i < edges.size(); i++) {
 513                 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
 514                 ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
 515                 scheduleNodes.add(tSNode);
 516                 clone.add(tSNode);
 517                 toClone.add((ScheduleNode)tse.getTarget());
 518                 origins.addElement((ScheduleNode)tse.getTarget());
 519                 sn2sn.put((ScheduleNode)tse.getTarget(), tSNode);
 520                 qcn2cn.add(tocn2cn);
 521                 ScheduleEdge se = null;
 522                 switch(tse.getType()) {
 523                 case ScheduleEdge.NEWEDGE: {
 524                     se = new ScheduleEdge(tSNode, "new", tse.getFstate(), tse.getType(), 0);
 525                     break;
 526                 }
 527                 case ScheduleEdge.TRANSEDGE: {
 528                     se = new ScheduleEdge(tSNode, "transmit", tse.getFstate(), tse.getType(), 0);
 529                     break;
 530                 }
 531                 default: {
 532                     throw new Exception("Error: not valid ScheduleEdge here");
 533                 }
 534                 }
 535                 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
 536                 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
 537                 se.setFEdge(tse.getFEdge());
 538                 se.setTargetFState(tse.getTargetFState());
 539                 se.setProbability(tse.getProbability());
 540                 se.setNewRate(tse.getNewRate());
 541                 se.setIsclone(true);
 542                 csNode.addEdge(se);
 543                 scheduleEdges.add(se);
 544             }
 545             tocn2cn = null;
 546             edges = null;
 547         }
 548
 549         toClone = null;
 550         clone = null;
 551         qcn2cn = null;
 552         cn2cn = null;
 553     }
 554
 555     private int calInExeTime(FlagState fs) throws Exception {
 556         int exeTime = 0;
 557         ClassDescriptor cd = fs.getClassDescriptor();
 558         ClassNode cNode = cd2ClassNode.get(cd);
 559         exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
 560         while(true) {
 561             Vector inedges = cNode.getInedgeVector();
 562             // Now that there are associate ScheduleEdges, there may be multiple inedges of a ClassNode
 563             if(inedges.size() > 1) {
 564                 throw new Exception("Error: ClassNode's inedges more than one!");
 565             }
 566             if(inedges.size() > 0) {
 567                 ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
 568                 cNode = (ClassNode)sEdge.getSource();
 569                 exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
 570             }else {
 571                 break;
 572             }
 573             inedges = null;
 574         }
 575         exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
 576         return exeTime;
 577     }
 578
 579     private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) {
 580         assert(ScheduleEdge.NEWEDGE == se.getType());
 581
 582         FEdge fe = se.getFEdge();
 583         FlagState fs = (FlagState)fe.getTarget();
 584         FlagState nfs = (FlagState)fs.clone();
 585         fs.getEdgeVector().removeAllElements();
 586         nfs.getInedgeVector().removeAllElements();
 587         ClassNode sCNode = se.getSourceCNode();
 588
 589         // split the subtree whose root is nfs from the whole flag transition tree
 590         Vector<FlagState> sfss = sCNode.getFlagStates();
 591         Vector<FlagState> fStates = new Vector<FlagState>();
 592         Queue<FlagState> toiterate = new LinkedList<FlagState>();
 593         toiterate.add(nfs);
 594         fStates.add(nfs);
 595         while(!toiterate.isEmpty()){
 596             FlagState tfs = toiterate.poll();
 597             Iterator it_edges = tfs.edges();
 598             while(it_edges.hasNext()) {
 599                 FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
 600                 if(!fStates.contains(temp)) {
 601                     fStates.add(temp);
 602                     toiterate.add(temp);
 603                     sfss.removeElement(temp);
 604                 }
 605             }
 606         }
 607         sfss = null;
 608         Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
 609         fStates = null;
 610         // create a ClassNode and ScheduleNode for this subtree
 611         ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
 612         ScheduleNode sNode = new ScheduleNode(cNode, 0);
 613         cNode.setScheduleNode(sNode);
 614         cNode.setSorted(true);
 615         cNode.setTransTime(sCNode.getTransTime());
 616         classNodes.add(cNode);
 617         scheduleNodes.add(sNode);
 618         try {
 619             sNode.calExeTime();
 620         } catch (Exception e) {
 621             e.printStackTrace();
 622         }
 623         // flush the exeTime of fs and its ancestors
 624         fs.setExeTime(0);
 625         toiterate.add(fs);
 626         while(!toiterate.isEmpty()) {
 627             FlagState tfs = toiterate.poll();
 628             int ttime = tfs.getExeTime();
 629             Iterator it_inedges = tfs.inedges();
 630             while(it_inedges.hasNext()) {
 631                 FEdge fEdge = (FEdge)it_inedges.next();
 632                 FlagState temp = (FlagState)fEdge.getSource();
 633                 int time = fEdge.getExeTime() + ttime;
 634                 if(temp.getExeTime() > time) {
 635                     temp.setExeTime(time);
 636                     toiterate.add(temp);
 637                 }
 638             }
 639         }
 640         toiterate = null;
 641
 642         // create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode
 643         ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", fs, ScheduleEdge.TRANSEDGE, 0);//new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
 644         sEdge.setFEdge(fe);
 645         sEdge.setSourceCNode(sCNode);
 646         sEdge.setTargetCNode(cNode);
 647         sEdge.setTargetFState(nfs);
 648         // TODO
 649         // Add calculation codes for calculating transmit time of an object
 650         sEdge.setTransTime(cNode.getTransTime());
 651         se.getSource().addEdge(sEdge);
 652         scheduleEdges.add(sEdge);
 653         // remove the ClassNodes and internal ScheduleEdges out of this subtree to the new ScheduleNode
 654         ScheduleNode oldSNode = (ScheduleNode)se.getSource();
 655         Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
 656         Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
 657         Vector<ClassNode> rCNodes = new Vector<ClassNode>();
 658         rCNodes.addElement(sCNode);
 659         if(it_isEdges != null){
 660             while(it_isEdges.hasNext()) {
 661                 ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
 662                 if(rCNodes.contains(tse.getSourceCNode())) {
 663                     if(sCNode == tse.getSourceCNode()) {
 664                         if ((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
 665                             tse.setSource(cNode);
 666                             tse.setSourceCNode(cNode);
 667                         } else {
 668                             continue;
 669                         }
 670                     }
 671                     sNode.getScheduleEdges().addElement(tse);
 672                     sNode.getClassNodes().addElement(tse.getTargetCNode());
 673                     rCNodes.addElement(tse.getTargetCNode());
 674                     oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
 675                     toremove.addElement(tse);
 676                 }
 677             }
 678         }
 679         oldSNode.getScheduleEdges().removeAll(toremove);
 680         toremove.clear();
 681         // redirect ScheudleEdges out of this subtree to the new ScheduleNode
 682         Iterator it_sEdges = se.getSource().edges();
 683         while(it_sEdges.hasNext()) {
 684             ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
 685             if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
 686                 if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
 687                     tse.setSource(sNode);
 688                     tse.setSourceCNode(cNode);
 689                     sNode.getEdgeVector().addElement(tse);
 690                     toremove.add(tse);
 691                 }
 692             }
 693         }
 694         se.getSource().getEdgeVector().removeAll(toremove);
 695         toremove = null;
 696         sFStates = null;
 697
 698         try {
 699             if(!copy) {
 700                 //merge se into its source ScheduleNode
 701                 ((ScheduleNode)se.getSource()).mergeSEdge(se);
 702                 scheduleNodes.remove(se.getTarget());
 703                 scheduleEdges.removeElement(se);
 704                 // As se has been changed into an internal edge inside a ScheduleNode,
 705                 // change the source and target of se from original ScheduleNodes into ClassNodes.
 706                 if(se.getType() == ScheduleEdge.NEWEDGE) {
 707                     se.setTarget(se.getTargetCNode());
 708                     se.setSource(se.getSourceCNode());
 709                     se.getTargetCNode().addEdge(se);
 710                 }
 711             } else {
 712                 handleScheduleEdge(se, true);
 713             }
 714         } catch (Exception e) {
 715             e.printStackTrace();
 716             System.exit(-1);
 717         }
 718
 719         return sNode;
 720     }
 721
 722     public void schedule() throws Exception {
 723         if(this.coreNum == -1) {
 724             throw new Exception("Error: un-initialized coreNum when doing scheduling.");
 725         }
 726
 727         if(this.scheduleGraphs == null) {
 728             this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
 729         }
 730
 731         int reduceNum = this.scheduleNodes.size() - this.coreNum;
 732
 733         // Combine some ScheduleNode if necessary
 734         // May generate multiple graphs suggesting candidate schedulings
 735         if(!(reduceNum > 0)) {
 736             // Enough cores, no need to combine any ScheduleNode
 737             this.scheduleGraphs.addElement(this.scheduleNodes);
 738             int gid = 1;
 739             String path = "scheduling_" + gid + ".dot";
 740             SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
 741         } else {
 742             // Go through all the Scheudle Nodes, organize them in order of their cid
 743             Vector<Vector<ScheduleNode>> sNodeVecs = new Vector<Vector<ScheduleNode>>();
 744             for(int i = 0; i < this.scheduleNodes.size(); i++) {
 745                 ScheduleNode tmpn = this.scheduleNodes.elementAt(i);
 746                 int index = tmpn.getCid();
 747                 while(sNodeVecs.size() <= index) {
 748                     sNodeVecs.add(null);
 749                 }
 750                 if(sNodeVecs.elementAt(index) == null) {
 751                     sNodeVecs.setElementAt(new Vector<ScheduleNode>(), index);
 752                 }
 753                 sNodeVecs.elementAt(index).add(tmpn);
 754             }
 755
 756             CombinationUtil.RootsGenerator rGen = CombinationUtil.allocateRootsGenerator(sNodeVecs, this.coreNum);
 757
 758             int gid = 1;
 759             while(rGen.nextGen()) {
 760                 // first get the chosen rootNodes
 761                 Vector<Vector<ScheduleNode>> rootNodes = rGen.getRootNodes();
 762                 Vector<Vector<ScheduleNode>> nodes2combine = rGen.getNode2Combine();
 763
 764                 CombinationUtil.CombineGenerator cGen = CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine);
 765                 while (cGen.nextGen()) {
 766                     Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
 767                     Vector<ScheduleNode> sNodes = generateScheduling(rootNodes, combine, gid++);
 768                     this.scheduleGraphs.add(sNodes);
 769                     combine = null;
 770                     sNodes = null;
 771                 }
 772                 rootNodes = null;
 773                 nodes2combine = null;
 774             }
 775             sNodeVecs = null;
 776         }
 777
 778         // Generate schedulings according to result schedule graph
 779         if(this.schedulings == null) {
 780             this.schedulings = new Vector<Vector<Schedule>>();
 781         }
 782
 783         Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
 784         Iterator it_tasks = state.getTaskSymbolTable().getDescriptorsIterator();
 785         while(it_tasks.hasNext()) {
 786             TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 787             if(td.numParameters() > 1) {
 788                 multiparamtds.addElement(td);
 789             }
 790         }
 791
 792         for(int i = 0; i < this.scheduleGraphs.size(); i++) {
 793             Hashtable<TaskDescriptor, Vector<Schedule>> td2cores = new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks reside on which cores
 794             Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
 795             Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
 796             // for each ScheduleNode create a schedule node representing a core
 797             Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
 798             int j = 0;
 799             for(j = 0; j < scheduleGraph.size(); j++) {
 800                 sn2coreNum.put(scheduleGraph.elementAt(j), j);
 801             }
 802             int startupcore = 0;
 803             boolean setstartupcore = false;
 804             Schedule startup = null;
 805             for(j = 0; j < scheduleGraph.size(); j++) {
 806                 Schedule tmpSchedule = new Schedule(j);
 807                 ScheduleNode sn = scheduleGraph.elementAt(j);
 808
 809                 Vector<ClassNode> cNodes = sn.getClassNodes();
 810                 for(int k = 0; k < cNodes.size(); k++) {
 811                     Iterator it_flags = cNodes.elementAt(k).getFlags();
 812                     while(it_flags.hasNext()) {
 813                         FlagState fs = (FlagState)it_flags.next();
 814                         Iterator it_edges = fs.edges();
 815                         while(it_edges.hasNext()) {
 816                             TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
 817                             tmpSchedule.addTask(td);
 818                             if(!td2cores.containsKey(td)) {
 819                                 td2cores.put(td, new Vector<Schedule>());
 820                             }
 821                             Vector<Schedule> tmpcores = td2cores.get(td);
 822                             if(!tmpcores.contains(tmpSchedule)) {
 823                                 tmpcores.add(tmpSchedule);
 824                             }
 825                             // if the FlagState can be fed to some multi-param tasks,
 826                             // need to record corresponding ally cores later
 827                             if(td.numParameters() > 1) {
 828                                 tmpSchedule.addFState4TD(td, fs);
 829                             }
 830                             if(td.getParamType(0).getClassDesc().getSymbol().equals(TypeUtil.StartupClass)) {
 831                                 assert(!setstartupcore);
 832                                 startupcore = j;
 833                                 startup = tmpSchedule;
 834                                 setstartupcore = true;
 835                             }
 836                         }
 837                     }
 838                 }
 839
 840                 // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
 841                 Iterator it_edges = sn.edges();
 842                 while(it_edges.hasNext()) {
 843                     ScheduleEdge se = (ScheduleEdge)it_edges.next();
 844                     ScheduleNode target = (ScheduleNode)se.getTarget();
 845                     Integer targetcore = sn2coreNum.get(target);
 846                     switch(se.getType()) {
 847                     case ScheduleEdge.NEWEDGE: {
 848                         for(int k = 0; k < se.getNewRate(); k++) {
 849                             tmpSchedule.addTargetCore(se.getFstate(), targetcore);
 850                         }
 851                         break;
 852                     }
 853                     case ScheduleEdge.TRANSEDGE: {
 854                         // 'transmit' edge
 855                         tmpSchedule.addTargetCore(se.getFstate(), targetcore, se.getTargetFState());
 856                         // check if missed some FlagState associated with some multi-parameter
 857                         // task, which has been cloned when splitting a ClassNode
 858                         FlagState fs = se.getSourceFState();
 859                         FlagState tfs = se.getTargetFState();
 860                         Iterator it = tfs.edges();
 861                         while(it.hasNext()) {
 862                             TaskDescriptor td = ((FEdge)it.next()).getTask();
 863                             if(td.numParameters() > 1) {
 864                                 if(tmpSchedule.getTasks().contains(td)) {
 865                                     tmpSchedule.addFState4TD(td, fs);
 866                                 }
 867                             }
 868                         }
 869                         break;
 870                     }
 871                     }
 872                 }
 873                 it_edges = sn.getScheduleEdgesIterator();
 874                 while(it_edges.hasNext()) {
 875                     ScheduleEdge se = (ScheduleEdge)it_edges.next();
 876                     switch(se.getType()) {
 877                     case ScheduleEdge.NEWEDGE: {
 878                         for(int k = 0; k < se.getNewRate(); k++) {
 879                             tmpSchedule.addTargetCore(se.getFstate(), j);
 880                         }
 881                         break;
 882                     }
 883                     case ScheduleEdge.TRANSEDGE: {
 884                         // 'transmit' edge
 885                         tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState());
 886                         break;
 887                     }
 888                     }
 889                 }
 890                 scheduling.add(tmpSchedule);
 891             }
 892
 893             int number = this.coreNum;
 894             if(scheduling.size() < number) {
 895                 number = scheduling.size();
 896             }
 897
 898             // set up all the associate ally cores
 899             if(multiparamtds.size() > 0) {
 900                 for(j = 0; j < multiparamtds.size(); ++j) {
 901                     TaskDescriptor td = multiparamtds.elementAt(j);
 902                     Vector<FEdge> fes = (Vector<FEdge>)this.taskanalysis.getFEdgesFromTD(td);
 903                     Vector<Schedule> cores = td2cores.get(td);
 904                     for(int k = 0; k < cores.size(); ++k) {
 905                         Schedule tmpSchedule = cores.elementAt(k);
 906
 907                         for(int h = 0; h < fes.size(); ++h) {
 908                             FEdge tmpfe = fes.elementAt(h);
 909                             FlagState tmpfs = (FlagState)tmpfe.getTarget();
 910                             Vector<TaskDescriptor> tmptds = new Vector<TaskDescriptor>();
 911                             if((tmpSchedule.getTargetCoreTable() == null) || (!tmpSchedule.getTargetCoreTable().contains(tmpfs))) {
 912                                 // add up all possible cores' info
 913                                 Iterator it_edges = tmpfs.edges();
 914                                 while(it_edges.hasNext()) {
 915                                     TaskDescriptor tmptd = ((FEdge)it_edges.next()).getTask();
 916                                     if(!tmptds.contains(tmptd)) {
 917                                         tmptds.add(tmptd);
 918                                         Vector<Schedule> tmpcores = td2cores.get(tmptd);
 919                                         for(int m = 0; m < tmpcores.size(); ++m) {
 920                                             if(m != tmpSchedule.getCoreNum()) {
 921                                                 // if the FlagState can be fed to some multi-param tasks,
 922                                                 // need to record corresponding ally cores later
 923                                                 if(tmptd.numParameters() > 1) {
 924                                                     tmpSchedule.addAllyCore(tmpfs, tmpcores.elementAt(m).getCoreNum());
 925                                                 } else {
 926                                                     tmpSchedule.addTargetCore(tmpfs, tmpcores.elementAt(m).getCoreNum());
 927                                                 }
 928                                             }
 929                                         }
 930                                     }
 931                                 }
 932                             }
 933                         }
 934
 935                         if(cores.size() > 1) {
 936                             Vector<FlagState> tmpfss = tmpSchedule.getFStates4TD(td);
 937                             for(int h = 0; h < tmpfss.size(); ++h) {
 938                                 for(int l = 0; l < cores.size(); ++l) {
 939                                     if(l != k) {
 940                                         tmpSchedule.addAllyCore(tmpfss.elementAt(h), cores.elementAt(l).getCoreNum());
 941                                     }
 942                                 }
 943                             }
 944                         }
 945                     }
 946                 }
 947             }
 948
 949             this.schedulings.add(scheduling);
 950         }
 951     }
 952
 953     public Vector<ScheduleNode> generateScheduling(Vector<Vector<ScheduleNode>> rootnodes, Vector<Vector<CombinationUtil.Combine>> combine, int gid) {
 954         Vector<ScheduleNode> result = new Vector<ScheduleNode>();
 955
 956         // clone the ScheduleNodes
 957         Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
 958         Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
 959         for(int i = 0; i < this.scheduleNodes.size(); i++) {
 960             Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
 961             ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
 962             ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
 963             result.add(i, temp);
 964             sn2hash.put(temp, cn2cn);
 965             sn2sn.put(tocopy, temp);
 966             cn2cn = null;
 967         }
 968         // clone the ScheduleEdges
 969         for(int i = 0; i < this.scheduleEdges.size(); i++) {
 970             ScheduleEdge sse = this.scheduleEdges.elementAt(i);
 971             ScheduleNode csource = sn2sn.get(sse.getSource());
 972             ScheduleNode ctarget = sn2sn.get(sse.getTarget());
 973             Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
 974             Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
 975             ScheduleEdge se =  null;
 976             switch(sse.getType()) {
 977             case ScheduleEdge.NEWEDGE: {
 978                 se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
 979                 se.setProbability(sse.getProbability());
 980                 se.setNewRate(sse.getNewRate());
 981                 break;
 982             }
 983             case ScheduleEdge.TRANSEDGE: {
 984                 se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
 985                 break;
 986             }
 987             }
 988             se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
 989             se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
 990             se.setFEdge(sse.getFEdge());
 991             se.setTargetFState(sse.getTargetFState());
 992             se.setIsclone(true);
 993             csource.addEdge(se);
 994             sourcecn2cn = null;
 995             targetcn2cn = null;
 996         }
 997
 998         // combine those nodes in combine with corresponding rootnodes
 999         for(int i = 0; i < combine.size(); i++) {
1000             if(combine.elementAt(i) != null) {
1001                 for(int j = 0; j < combine.elementAt(i).size(); j++) {
1002                     CombinationUtil.Combine tmpcombine = combine.elementAt(i).elementAt(j);
1003                     ScheduleNode tocombine = sn2sn.get(tmpcombine.node);
1004                     ScheduleNode root = sn2sn.get(rootnodes.elementAt(tmpcombine.root).elementAt(tmpcombine.index));
1005                     ScheduleEdge se = (ScheduleEdge)tocombine.inedges().next();
1006                     try{
1007                         if(root.equals(((ScheduleNode)se.getSource()))) {
1008                             root.mergeSEdge(se);
1009                             if(ScheduleEdge.NEWEDGE == se.getType()) {
1010                                 // As se has been changed into an internal edge inside a ScheduleNode,
1011                                 // change the source and target of se from original ScheduleNodes into ClassNodes.
1012                                 se.setTarget(se.getTargetCNode());
1013                                 se.setSource(se.getSourceCNode());
1014                                 se.getTargetCNode().addEdge(se);
1015                             }
1016                         } else {
1017                             root.mergeSNode(tocombine);
1018                         }
1019                     } catch(Exception e) {
1020                         e.printStackTrace();
1021                         System.exit(-1);
1022                     }
1023                     result.removeElement(tocombine);
1024                 }
1025             }
1026         }
1027
1028         sn2hash = null;
1029         sn2sn = null;
1030
1031         String path = "scheduling_" + gid + ".dot";
1032         SchedulingUtil.printScheduleGraph(path, result);
1033
1034         return result;
1035     }
1036 }