1 package Analysis.Scheduling;
5 import Analysis.TaskStateAnalysis.FEdge;
6 import Analysis.TaskStateAnalysis.FlagState;
9 /** This class holds flag transition diagram(s) can be put on one core.
11 public class ScheduleNode extends GraphNode implements Cloneable {
16 private static int nodeID=0;
17 public static int colorID = 0;
19 private Vector<ClassNode> classNodes;
20 private Vector<ScheduleEdge> scheduleEdges;
22 private long executionTime;
27 * @param cd ClassDescriptor
30 public ScheduleNode(int gid) {
31 this.uid = ScheduleNode.nodeID++;
34 this.executionTime = -1;
35 this.classNodes = null;
36 this.scheduleEdges = null;
40 public ScheduleNode(ClassNode cn, int gid) {
41 this.uid = ScheduleNode.nodeID++;
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;
64 public void setCid(int cid) {
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() + ", ";
73 temp += getTextLabel();
77 public Vector getClassNodes() {
81 public Iterator getClassNodesIterator() {
82 if(classNodes == null) {
85 return classNodes.iterator();
88 public void resetClassNodes() {
92 public Vector getScheduleEdges() {
96 public Iterator getScheduleEdgesIterator() {
97 if(scheduleEdges == null) {
100 return scheduleEdges.iterator();
103 public void resetScheduleEdges() {
104 scheduleEdges = null;
107 public int getHashcid() {
111 public void computeHashcid() {
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);
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;
125 int tmp = mergedcids.elementAt(j-1);
127 mergedcids.setElementAt(tmp, j);
132 mergedcids.setElementAt(tomerge, j);
134 for(int i = 0; i < mergedcids.size(); i++) {
135 this.hashcid = this.hashcid * 31 + mergedcids.elementAt(i);
140 public long getExeTime() {
141 if(this.executionTime == -1) {
144 } catch (Exception e) {
148 return this.executionTime;
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");
155 ClassNode cn = this.classNodes.elementAt(0);
157 throw new Error("Error: Non-sorted ClassNode!");
159 this.executionTime = cn.getFlagStates().elementAt(0).getExeTime();
162 /** Tests for equality of two flagstate objects.
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) {
172 if(fs.cid != this.cid) {
176 if ((fs.executionTime != this.executionTime)) {
179 if(fs.classNodes != null) {
180 if(!fs.classNodes.equals(classNodes)) {
183 } else if(classNodes != null) {
191 public int hashCode() {
192 int hashcode = gid^uid^cid^(int)executionTime;
193 if(this.classNodes != null) {
194 hashcode ^= classNodes.hashCode();
199 public String getLabel() {
200 return "cluster" + uid;
203 public String getTextLabel() {
211 public Object clone(Hashtable<ClassNode, ClassNode> cn2cn,
213 ScheduleNode o = null;
215 o = (ScheduleNode) super.clone();
216 } catch(CloneNotSupportedException e) {
219 o.uid = ScheduleNode.nodeID++;
222 // Clone all the internal ClassNodes and ScheduleEdges
223 Vector<ClassNode> tcns = new Vector<ClassNode>();
224 Vector<ScheduleEdge> tses = new Vector<ScheduleEdge>();
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);
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,
241 ScheduleEdge.NEWEDGE,
243 se.setProbability(temp.getProbability());
244 se.setNewRate(temp.getNewRate());
248 case ScheduleEdge.TRANSEDGE: {
249 se = new ScheduleEdge(o,
252 ScheduleEdge.TRANSEDGE,
254 se.setProbability(temp.getProbability());
255 se.setNewRate(temp.getNewRate());
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());
266 // internal edge, it's source and target have been redirected to ClassNodes
267 se.setTarget(se.getTargetCNode());
268 se.getSourceCNode().addEdge(se);
271 o.scheduleEdges = tses;
275 o.inedges = new Vector();
276 o.edges = new Vector();
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();
285 for(int i = 0; i < targetCNodes.size(); i++) {
286 targetCNodes.elementAt(i).setScheduleNode(this);
289 if(classNodes == null) {
290 classNodes = targetCNodes;
291 scheduleEdges = targetSEdges;
293 if(targetCNodes.size() != 0) {
294 classNodes.addAll(targetCNodes);
296 if(targetSEdges.size() != 0) {
297 scheduleEdges.addAll(targetSEdges);
302 if(ScheduleEdge.TRANSEDGE == se.getType()) {
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);
317 classNodes.removeElement(tcn);
319 // flush the exeTime of fs and its ancestors
321 Queue<FlagState> toiterate = new LinkedList<FlagState>();
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);
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);
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();
354 if(tse.getSourceCNode().equals(tcn)) {
355 tse.setSourceCNode(scn);
357 this.edges.addElement(tse);
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.");
368 if(this.executionTime < sn.getExeTime()) {
369 this.executionTime = sn.getExeTime();
371 } else if(ScheduleEdge.NEWEDGE == se.getType()) {
374 scheduleEdges.add(se);
375 se.resetListExeTime();
378 Iterator it_edges = sn.edges();
379 while(it_edges.hasNext()) {
380 ScheduleEdge tse = (ScheduleEdge)it_edges.next();
382 this.edges.addElement(tse);
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;
391 this.executionTime += ((ScheduleNode)se.getTarget()).getExeTime();
395 public void mergeSNode(ScheduleNode sn) {
396 Vector<ClassNode> targetCNodes = (Vector<ClassNode>)sn.getClassNodes();
397 Vector<ScheduleEdge> targetSEdges = (Vector<ScheduleEdge>)sn.getScheduleEdges();
399 for(int i = 0; i < targetCNodes.size(); i++) {
400 targetCNodes.elementAt(i).setScheduleNode(this);
403 if(classNodes == null) {
404 classNodes = targetCNodes;
405 scheduleEdges = targetSEdges;
407 if(targetCNodes.size() != 0) {
408 classNodes.addAll(targetCNodes);
410 if(targetSEdges.size() != 0) {
411 scheduleEdges.addAll(targetSEdges);
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();
422 this.edges.addElement(tse);
425 it_edges = sn.inedges();
426 while(it_edges.hasNext()) {
427 ScheduleEdge tse = (ScheduleEdge)it_edges.next();
429 this.inedges.addElement(tse);
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;
438 this.executionTime += sn.getExeTime();
441 public ScheduleNode spliteClassNode(ClassNode cd) {
442 ScheduleNode sNode = new ScheduleNode(cd, this.gid);
443 // clean all inedges and edges
445 sNode.inedges.clear();
447 this.classNodes.remove(cd);
448 cd.setScheduleNode(sNode);
451 } catch (Exception e) {
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()))) {
463 toremove.addElement(tse);
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())) {
475 } else if(cd.equals(tse.getTargetCNode())){
477 tse.setTarget(sNode);
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)) {
489 //this.removeEdge(tse);
490 //sNode.addEdge(tse);
491 tse.setSource(sNode);
492 sNode.edges.addElement(tse);
495 this.edges.removeAll(toremove);
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)) {
505 tse.setTarget(sNode);
506 sNode.inedges.addElement(tse);
510 this.inedges.removeAll(toremove);
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();