Robust/src/Analysis/Scheduling/ScheduleNode.java

   1 package Analysis.Scheduling;
   2
   3 import java.util.*;
   4
   5 import Analysis.TaskStateAnalysis.FEdge;
   6 import Analysis.TaskStateAnalysis.FlagState;
   7 import Util.GraphNode;
   8
   9 /** This class holds flag transition diagram(s) can be put on one core.
  10  */
  11 public class ScheduleNode extends GraphNode implements Cloneable {
  12
  13   private int uid;
  14   private int gid;
  15   private int cid;
  16   private static int nodeID=0;
  17   public static int colorID = 0;
  18
  19   private Vector<ClassNode> classNodes;
  20   private Vector<ScheduleEdge> scheduleEdges;
  21
  22   private long executionTime;
  23
  24   private int hashcid;
  25
  26   /** Class constructor
  27    *    @param cd ClassDescriptor
  28    *  @param fStates
  29    */
  30   public ScheduleNode(int gid) {
  31     this.uid = ScheduleNode.nodeID++;
  32     this.gid = gid;
  33     this.cid = -1;
  34     this.executionTime = -1;
  35     this.classNodes = null;
  36     this.scheduleEdges = null;
  37     this.hashcid = 0;
  38   }
  39
  40   public ScheduleNode(ClassNode cn, int gid) {
  41     this.uid = ScheduleNode.nodeID++;
  42     this.gid = gid;
  43     this.cid = -1;
  44     this.classNodes = new Vector<ClassNode>();
  45     this.scheduleEdges = new Vector<ScheduleEdge>();
  46     this.classNodes.add(cn);
  47     this.addEdge(cn.getEdgeVector());
  48     this.executionTime = -1;
  49     this.hashcid = 0;
  50   }
  51
  52   public int getGid() {
  53     return gid;
  54   }
  55
  56   public int getuid() {
  57     return uid;
  58   }
  59
  60   public int getCid() {
  61     return cid;
  62   }
  63
  64   public void setCid(int cid) {
  65     this.cid = cid;
  66   }
  67
  68   public String toString() {
  69     String temp = new String("");
  70     for(int i = 0; i < classNodes.size(); i++) {
  71       temp += classNodes.elementAt(i).getClassDescriptor().toString() + ", ";
  72     }
  73     temp += getTextLabel();
  74     return temp;
  75   }
  76
  77   public Vector getClassNodes() {
  78     return classNodes;
  79   }
  80
  81   public Iterator getClassNodesIterator() {
  82     if(classNodes == null) {
  83       return null;
  84     }
  85     return classNodes.iterator();
  86   }
  87
  88   public void resetClassNodes() {
  89     classNodes = null;
  90   }
  91
  92   public Vector getScheduleEdges() {
  93     return scheduleEdges;
  94   }
  95
  96   public Iterator getScheduleEdgesIterator() {
  97     if(scheduleEdges == null) {
  98       return null;
  99     }
 100     return scheduleEdges.iterator();
 101   }
 102
 103   public void resetScheduleEdges() {
 104     scheduleEdges = null;
 105   }
 106
 107   public int getHashcid() {
 108     return hashcid;
 109   }
 110
 111   public void computeHashcid() {
 112     this.hashcid = 0;
 113     /*if(this.mergedcids != null) {
 114         for(int i = 0; i < this.mergedcids.size(); i++) {
 115             this.hashcid = this.hashcid * 31 + this.mergedcids.elementAt(i);
 116         }
 117        }*/
 118     Vector<Integer> mergedcids = new Vector<Integer>();
 119     for(int i = 0; i < this.classNodes.size(); i++) {
 120       int tomerge = this.classNodes.elementAt(i).getCid();
 121       mergedcids.add(tomerge);
 122       // insert tomerge in accent order
 123       int j = mergedcids.size() - 1;
 124       for(; j > 0; j--) {
 125         int tmp = mergedcids.elementAt(j-1);
 126         if(tmp > tomerge) {
 127           mergedcids.setElementAt(tmp, j);
 128         } else {
 129           break;
 130         }
 131       }
 132       mergedcids.setElementAt(tomerge, j);
 133     }
 134     for(int i = 0; i < mergedcids.size(); i++) {
 135       this.hashcid = this.hashcid * 31 + mergedcids.elementAt(i);
 136     }
 137     mergedcids = null;
 138   }
 139
 140   public long getExeTime() {
 141     if(this.executionTime == -1) {
 142       try {
 143         calExeTime();
 144       } catch (Exception e) {
 145         e.printStackTrace();
 146       }
 147     }
 148     return this.executionTime;
 149   }
 150
 151   public void calExeTime() throws Exception {
 152     if(this.classNodes.size() != 1) {
 153       throw new Exception("Error: there are multiple ClassNodes inside the ScheduleNode when calculating executionTime");
 154     }
 155     ClassNode cn = this.classNodes.elementAt(0);
 156     if(!cn.isSorted()) {
 157       throw new Error("Error: Non-sorted ClassNode!");
 158     }
 159     this.executionTime = cn.getFlagStates().elementAt(0).getExeTime();
 160   }
 161
 162   /** Tests for equality of two flagstate objects.
 163    */
 164
 165   public boolean equals(Object o) {
 166     if (o instanceof ScheduleNode) {
 167       ScheduleNode fs=(ScheduleNode)o;
 168       if(fs.gid == this.gid) {
 169         if(fs.uid != this.uid) {
 170           return false;
 171         }
 172         if(fs.cid != this.cid) {
 173           return false;
 174         }
 175       }
 176       if ((fs.executionTime != this.executionTime)) {
 177         return false;
 178       }
 179       if(fs.classNodes != null) {
 180         if(!fs.classNodes.equals(classNodes)) {
 181           return false;
 182         }
 183       } else if(classNodes != null) {
 184         return false;
 185       }
 186       return true;
 187     }
 188     return false;
 189   }
 190
 191   public int hashCode() {
 192     int hashcode = gid^uid^cid^(int)executionTime;
 193     if(this.classNodes != null) {
 194       hashcode ^= classNodes.hashCode();
 195     }
 196     return hashcode;
 197   }
 198
 199   public String getLabel() {
 200     return "cluster" + uid;
 201   }
 202
 203   public String getTextLabel() {
 204     String label=null;
 205
 206     if (label==null)
 207       return " ";
 208     return label;
 209   }
 210
 211   public Object clone(Hashtable<ClassNode, ClassNode> cn2cn,
 212                       int gid) {
 213     ScheduleNode o = null;
 214     try {
 215       o = (ScheduleNode) super.clone();
 216     } catch(CloneNotSupportedException e) {
 217       e.printStackTrace();
 218     }
 219     o.uid = ScheduleNode.nodeID++;
 220     o.gid = gid;
 221     o.cid = this.cid;
 222     // Clone all the internal ClassNodes and ScheduleEdges
 223     Vector<ClassNode> tcns = new Vector<ClassNode>();
 224     Vector<ScheduleEdge> tses = new Vector<ScheduleEdge>();
 225     int i = 0;
 226     for(i = 0; i < this.classNodes.size(); i++) {
 227       ClassNode tcn = this.classNodes.elementAt(i);
 228       ClassNode cn = (ClassNode)tcn.clone();
 229       cn.setScheduleNode(o);
 230       tcns.add(cn);
 231       cn2cn.put(tcn, cn);
 232     }
 233     for(i = 0; i < this.scheduleEdges.size(); i++) {
 234       ScheduleEdge temp = this.scheduleEdges.elementAt(i);
 235       ScheduleEdge se = null;
 236       switch(temp.getType()) {
 237       case ScheduleEdge.NEWEDGE: {
 238         se = new ScheduleEdge(o,
 239                               "new",
 240                               temp.getFstate(),
 241                               ScheduleEdge.NEWEDGE,
 242                               gid);
 243         se.setProbability(temp.getProbability());
 244         se.setNewRate(temp.getNewRate());
 245         break;
 246       }
 247
 248       case ScheduleEdge.TRANSEDGE: {
 249         se = new ScheduleEdge(o,
 250                               "transmit",
 251                               temp.getFstate(),
 252                               ScheduleEdge.TRANSEDGE,
 253                               gid);
 254         se.setProbability(temp.getProbability());
 255         se.setNewRate(temp.getNewRate());
 256         break;
 257       }
 258       }
 259       se.setSourceCNode(cn2cn.get(temp.getSourceCNode()));
 260       se.setTargetCNode(cn2cn.get(temp.getTargetCNode()));
 261       se.setTransTime(temp.getTransTime());
 262       se.setFEdge(temp.getFEdge());
 263       se.setTargetFState(temp.getTargetFState());
 264       se.setIsclone(true);
 265       tses.add(se);
 266       // internal edge, it's source and target have been redirected to ClassNodes
 267       se.setTarget(se.getTargetCNode());
 268       se.getSourceCNode().addEdge(se);
 269     }
 270     o.classNodes = tcns;
 271     o.scheduleEdges = tses;
 272     tcns = null;
 273     tses = null;
 274
 275     o.inedges = new Vector();
 276     o.edges = new Vector();
 277     return o;
 278   }
 279
 280   public void mergeSEdge(ScheduleEdge se) throws Exception {
 281     ScheduleNode sn = (ScheduleNode)se.getTarget();
 282     Vector<ClassNode> targetCNodes = (Vector<ClassNode>)sn.getClassNodes();
 283     Vector<ScheduleEdge> targetSEdges = (Vector<ScheduleEdge>)sn.getScheduleEdges();
 284
 285     for(int i = 0; i <  targetCNodes.size(); i++) {
 286       targetCNodes.elementAt(i).setScheduleNode(this);
 287     }
 288
 289     if(classNodes == null) {
 290       classNodes = targetCNodes;
 291       scheduleEdges = targetSEdges;
 292     } else {
 293       if(targetCNodes.size() != 0) {
 294         classNodes.addAll(targetCNodes);
 295       }
 296       if(targetSEdges.size() != 0) {
 297         scheduleEdges.addAll(targetSEdges);
 298       }
 299     }
 300     targetCNodes = null;
 301
 302     if(ScheduleEdge.TRANSEDGE == se.getType()) {
 303       sn.removeInedge(se);
 304       this.removeEdge(se);
 305
 306       // merge the split ClassNode of same class
 307       FlagState sfs = se.getFstate();
 308       FlagState tfs = se.getTargetFState();
 309       ClassNode scn = se.getSourceCNode();
 310       ClassNode tcn = se.getTargetCNode();
 311       sfs.getEdgeVector().addAll(tfs.getEdgeVector());
 312       // merge the subtree whose root is nfs from the whole flag transition tree
 313       Vector<FlagState> sfss = scn.getFlagStates();
 314       sfss.addAll(tcn.getFlagStates());
 315       sfss.removeElement(tfs);
 316       sfss = null;
 317       classNodes.removeElement(tcn);
 318
 319       // flush the exeTime of fs and its ancestors
 320       sfs.setExeTime(0);
 321       Queue<FlagState> toiterate = new LinkedList<FlagState>();
 322       toiterate.add(sfs);
 323       while(!toiterate.isEmpty()) {
 324         FlagState tmpfs = toiterate.poll();
 325         long ttime = tmpfs.getExeTime();
 326         Iterator it_inedges = tmpfs.inedges();
 327         while(it_inedges.hasNext()) {
 328           FEdge fEdge = (FEdge)it_inedges.next();
 329           FlagState temp = (FlagState)fEdge.getSource();
 330           long time = fEdge.getExeTime() + ttime;
 331           if(temp.getExeTime() > time) {
 332             temp.setExeTime(time);
 333             toiterate.add(temp);
 334           }
 335         }
 336         it_inedges = null;
 337       }
 338       toiterate = null;
 339
 340       // redirct internal ScheduleEdge from tcn to scn
 341       for(int i = 0; i < targetSEdges.size(); ++i) {
 342         ScheduleEdge tmpse = targetSEdges.elementAt(i);
 343         if(tmpse.getSourceCNode().equals(tcn)) {
 344           tmpse.setSourceCNode(scn);
 345         }
 346       }
 347
 348       // redirect external ScheduleEdges to this ScheduleNode
 349       // and scn if it is originally from tcn
 350       Iterator it_edges = sn.edges();
 351       while(it_edges.hasNext()) {
 352         ScheduleEdge tse = (ScheduleEdge)it_edges.next();
 353         tse.setSource(this);
 354         if(tse.getSourceCNode().equals(tcn)) {
 355           tse.setSourceCNode(scn);
 356         }
 357         this.edges.addElement(tse);
 358       }
 359       it_edges = null;
 360
 361       targetSEdges = null;
 362
 363       // As all tasks inside one ScheduleNode are executed sequentially,
 364       // simply add the execution time of all the ClassNodes inside one ScheduleNode.
 365       if(this.executionTime == -1) {
 366         throw new Exception("Error: ScheduleNode without initiate execution time when analysising.");
 367       }
 368       if(this.executionTime < sn.getExeTime()) {
 369         this.executionTime = sn.getExeTime();
 370       }
 371     } else if(ScheduleEdge.NEWEDGE == se.getType()) {
 372       targetSEdges = null;
 373
 374       scheduleEdges.add(se);
 375       se.resetListExeTime();
 376       sn.removeInedge(se);
 377       this.removeEdge(se);
 378       Iterator it_edges = sn.edges();
 379       while(it_edges.hasNext()) {
 380         ScheduleEdge tse = (ScheduleEdge)it_edges.next();
 381         tse.setSource(this);
 382         this.edges.addElement(tse);
 383       }
 384       it_edges = null;
 385
 386       // As all tasks inside one ScheduleNode are executed sequentially,
 387       // simply add the execution time of all the ClassNodes inside one ScheduleNode.
 388       if(this.executionTime == -1) {
 389         this.executionTime = 0;
 390       }
 391       this.executionTime += ((ScheduleNode)se.getTarget()).getExeTime();
 392     }
 393   }
 394
 395   public void mergeSNode(ScheduleNode sn) {
 396     Vector<ClassNode> targetCNodes = (Vector<ClassNode>)sn.getClassNodes();
 397     Vector<ScheduleEdge> targetSEdges = (Vector<ScheduleEdge>)sn.getScheduleEdges();
 398
 399     for(int i = 0; i <  targetCNodes.size(); i++) {
 400       targetCNodes.elementAt(i).setScheduleNode(this);
 401     }
 402
 403     if(classNodes == null) {
 404       classNodes = targetCNodes;
 405       scheduleEdges = targetSEdges;
 406     } else {
 407       if(targetCNodes.size() != 0) {
 408         classNodes.addAll(targetCNodes);
 409       }
 410       if(targetSEdges.size() != 0) {
 411         scheduleEdges.addAll(targetSEdges);
 412       }
 413     }
 414     targetCNodes = null;
 415     targetSEdges = null;
 416
 417     // redirect external ScheduleEdges to this ScheduleNode
 418     Iterator it_edges = sn.edges();
 419     while(it_edges.hasNext()) {
 420       ScheduleEdge tse = (ScheduleEdge)it_edges.next();
 421       tse.setSource(this);
 422       this.edges.addElement(tse);
 423     }
 424
 425     it_edges = sn.inedges();
 426     while(it_edges.hasNext()) {
 427       ScheduleEdge tse = (ScheduleEdge)it_edges.next();
 428       tse.setTarget(this);
 429       this.inedges.addElement(tse);
 430     }
 431     it_edges = null;
 432
 433     // As all tasks inside one ScheduleNode are executed sequentially,
 434     // simply add the execution time of all the ClassNodes inside one ScheduleNode.
 435     if(this.executionTime == -1) {
 436       this.executionTime = 0;
 437     }
 438     this.executionTime += sn.getExeTime();
 439   }
 440
 441   public ScheduleNode spliteClassNode(ClassNode cd) {
 442     ScheduleNode sNode = new ScheduleNode(cd, this.gid);
 443     // clean all inedges and edges
 444     sNode.edges.clear();
 445     sNode.inedges.clear();
 446
 447     this.classNodes.remove(cd);
 448     cd.setScheduleNode(sNode);
 449     try {
 450       sNode.calExeTime();
 451     } catch (Exception e) {
 452       e.printStackTrace();
 453     }
 454
 455     // redirect all corresponding internal ScheduleEdge to the new snode
 456     Iterator it_innersEdges = this.scheduleEdges.iterator();
 457     Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
 458     if(it_innersEdges != null) {
 459       while(it_innersEdges.hasNext()) {
 460         ScheduleEdge tse = (ScheduleEdge)it_innersEdges.next();
 461         if((cd.equals(tse.getSourceCNode())) || (cd.equals(tse.getTargetCNode()))) {
 462           // related edge
 463           toremove.addElement(tse);
 464         }
 465       }
 466     }
 467     it_innersEdges = null;
 468     this.scheduleEdges.removeAll(toremove);
 469     for(int i = 0; i < toremove.size(); i++) {
 470       ScheduleEdge tse = toremove.elementAt(i);
 471       if(cd.equals(tse.getSourceCNode())) {
 472         // outedge
 473         tse.setTarget(this);
 474         sNode.addEdge(tse);
 475       } else if(cd.equals(tse.getTargetCNode())) {
 476         // inedge
 477         tse.setTarget(sNode);
 478         this.addEdge(tse);
 479       }
 480     }
 481     toremove.clear();
 482
 483     // redirect external ScheudleEdges out of this cd to the new ScheduleNode
 484     Iterator it_exsEdges = this.edges();
 485     while(it_exsEdges.hasNext()) {
 486       ScheduleEdge tse = (ScheduleEdge)it_exsEdges.next();
 487       if(tse.getSourceCNode().equals(cd)) {
 488         toremove.add(tse);
 489         //this.removeEdge(tse);
 490         //sNode.addEdge(tse);
 491         tse.setSource(sNode);
 492         sNode.edges.addElement(tse);
 493       }
 494     }
 495     this.edges.removeAll(toremove);
 496     toremove.clear();
 497
 498     it_exsEdges = null;
 499     // redirect inedges whose target is this Classnode to new ScheduleNode
 500     Iterator it_insEdges = this.inedges();
 501     while(it_insEdges.hasNext()) {
 502       ScheduleEdge tse = (ScheduleEdge)it_insEdges.next();
 503       if(tse.getTargetCNode().equals(cd)) {
 504         toremove.add(tse);
 505         tse.setTarget(sNode);
 506         sNode.inedges.addElement(tse);
 507       }
 508     }
 509     it_insEdges = null;
 510     this.inedges.removeAll(toremove);
 511     toremove.clear();
 512     toremove = null;
 513
 514     // As all tasks inside one ScheduleNode are executed sequentially,
 515     // simply subtract the execution time of the ClassNode .
 516     assert(this.executionTime != -1);
 517     this.executionTime -= sNode.getExeTime();
 518
 519     return sNode;
 520   }
 521 }