1 package Analysis.Scheduling;
3 import Analysis.TaskStateAnalysis.*;
8 /** This class holds flag transition diagram(s) can be put on one core.
10 public class ScheduleAnalysis {
13 TaskAnalysis taskanalysis;
14 Vector<ScheduleNode> scheduleNodes;
15 Vector<ClassNode> classNodes;
16 Vector<ScheduleEdge> scheduleEdges;
17 Hashtable<ClassDescriptor, ClassNode> cd2ClassNode;
18 boolean sorted = false;
23 Vector<Vector<ScheduleNode>> scheduleGraphs;
24 Vector<Vector<Schedule>> schedulings;
26 public ScheduleAnalysis(State state, TaskAnalysis taskanalysis) {
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;
35 this.scheduleGraphs = null;
36 this.schedulings = null;
39 public void setTransThreshold(int tt) {
40 this.transThreshold = tt;
43 public int getCoreNum() {
47 public void setCoreNum(int coreNum) {
48 this.coreNum = coreNum;
51 public Iterator getScheduleGraphs() {
52 return this.scheduleGraphs.iterator();
55 public Iterator getSchedulingsIter() {
56 return this.schedulings.iterator();
59 public Vector<Vector<Schedule>> getSchedulings() {
60 return this.schedulings;
64 public Vector<ScheduleEdge> getSEdges4Test() {
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);
76 //Sort flagState nodes inside this ClassNode
77 Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
79 Vector rootnodes = taskanalysis.getRootNodes(cd);
80 if(((rootnodes != null) && (rootnodes.size() > 0)) || (cd.getSymbol().equals("StartupObject"))) {
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);
89 if(cd.getSymbol().equals("C")) {
90 cNode.setTransTime(45);
97 // For each ClassNode create a ScheduleNode containing it
99 for(i = 0; i < classNodes.size(); i++) {
100 ScheduleNode sn = new ScheduleNode(classNodes.elementAt(i), 0);
101 classNodes.elementAt(i).setScheduleNode(sn);
102 scheduleNodes.add(sn);
105 } catch (Exception e) {
110 // Create 'new' edges between the ScheduleNodes.
111 Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
112 for(i = 0; i < classNodes.size(); i++) {
113 ClassNode cNode = classNodes.elementAt(i);
114 ClassDescriptor cd = cNode.getClassDescriptor();
115 Vector rootnodes = taskanalysis.getRootNodes(cd);
116 if(rootnodes != null) {
117 for(int h = 0; h < rootnodes.size(); h++){
118 FlagState root=(FlagState)rootnodes.elementAt(h);
119 Vector allocatingTasks = root.getAllocatingTasks();
120 if(allocatingTasks != null) {
121 for(int k = 0; k < allocatingTasks.size(); k++) {
122 TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
123 Vector<FEdge> fev = (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
124 int numEdges = fev.size();
125 ScheduleNode sNode = cNode.getScheduleNode();
126 for(int j = 0; j < numEdges; j++) {
127 FEdge pfe = fev.elementAt(j);
128 FEdge.NewObjInfo noi = pfe.getNewObjInfo(cd);
129 if ((noi == null) || (noi.getNewRate() == 0) || (noi.getProbability() == 0)) {
130 // fake creating edge, do not need to create corresponding 'new' edge
133 if(noi.getRoot() == null) {
134 // set root FlagState
137 FlagState pfs = (FlagState)pfe.getTarget();
138 ClassDescriptor pcd = pfs.getClassDescriptor();
139 ClassNode pcNode = cdToCNodes.get(pcd);
141 ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", root, 0);//new ScheduleEdge(sNode, "new", cd, 0);
143 sEdge.setSourceCNode(pcNode);
144 sEdge.setTargetCNode(cNode);
145 sEdge.setTargetFState(root);
146 sEdge.setNewRate(noi.getNewRate());
147 sEdge.setProbability(noi.getProbability());
148 pcNode.getScheduleNode().addEdge(sEdge);
149 scheduleEdges.add(sEdge);
150 if((j !=0 ) || (k != 0) || (h != 0)) {
151 toBreakDown.add(sEdge);
156 allocatingTasks = null;
164 // Do topology sort of the ClassNodes and ScheduleEdges.
165 Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
166 Vector<ScheduleNode> tempSNodes = ClassNode.DFS.topology(scheduleNodes, ssev);
167 scheduleNodes.removeAllElements();
168 scheduleNodes = tempSNodes;
170 scheduleEdges.removeAllElements();
171 scheduleEdges = ssev;
175 // Break down the 'cycle's
176 for(i = 0; i < toBreakDown.size(); i++ ) {
177 cloneSNodeList(toBreakDown.elementAt(i), false);
181 // Remove fake 'new' edges
182 for(i = 0; i < scheduleEdges.size(); i++) {
183 ScheduleEdge se = scheduleEdges.elementAt(i);
184 if((0 == se.getNewRate()) || (0 == se.getProbability())) {
185 scheduleEdges.removeElement(se);
186 scheduleNodes.removeElement(se.getTarget());
190 SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes);
193 public void scheduleAnalysis() {
196 //Access the ScheduleEdges in reverse topology order
197 Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses = new Hashtable<FEdge, Vector<ScheduleEdge>>();
198 Hashtable<ScheduleNode, Vector<FEdge>> sn2fes = new Hashtable<ScheduleNode, Vector<FEdge>>();
199 ScheduleNode preSNode = null;
200 for(i = scheduleEdges.size(); i > 0; i--) {
201 ScheduleEdge se = scheduleEdges.elementAt(i-1);
202 if(preSNode == null) {
203 preSNode = (ScheduleNode)se.getSource();
206 boolean split = false;
207 FEdge fe = se.getFEdge();
208 if(fe.getSource() == fe.getTarget()) {
210 int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
213 for(int j = 1; j< repeat; j++ ) {
214 cloneSNodeList(se, true);
217 se.setProbability(100);
220 rate = (int)Math.ceil(se.getListExeTime()/ calInExeTime(se.getSourceFState()));
221 } catch (Exception e) {
224 for(int j = rate - 1; j > 0; j--) {
225 for(int k = repeat; k > 0; k--) {
226 cloneSNodeList(se, true);
230 // if preSNode is not the same as se's source ScheduleNode
231 // handle any ScheduleEdges previously put into fe2ses whose source ScheduleNode is preSNode
232 boolean same = (preSNode == se.getSource());
234 if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()) {
235 if(sn2fes.containsKey(preSNode)) {
236 Vector<FEdge> fes = sn2fes.remove(preSNode);
237 for(int j = 0; j < fes.size(); j++) {
238 FEdge tempfe = fes.elementAt(j);
239 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
240 ScheduleEdge tempse = ses.elementAt(0);
241 int temptime = tempse.getListExeTime();
242 // find out the ScheduleEdge with least exeTime
243 for(int k = 1; k < ses.size(); k++) {
244 int ttemp = ses.elementAt(k).getListExeTime();
245 if(ttemp < temptime) {
246 tempse = ses.elementAt(k);
251 handleScheduleEdge(tempse, true);
252 ses.removeElement(tempse);
253 // handle other ScheduleEdges
254 for(int k = 0; k < ses.size(); k++) {
255 handleScheduleEdge(ses.elementAt(k), false);
258 fe2ses.remove(tempfe);
263 preSNode = (ScheduleNode)se.getSource();
266 // if fe is the last task inside this ClassNode, delay the expanding and merging until we find all such 'nmew' edges
267 // associated with a last task inside this ClassNode
268 if(!fe.getTarget().edges().hasNext()) {
269 if(fe2ses.get(fe) == null) {
270 fe2ses.put(fe, new Vector<ScheduleEdge>());
272 if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
273 sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
275 fe2ses.get(fe).add(se);
276 sn2fes.get((ScheduleNode)se.getSource()).add(fe);
278 // As this is not a last task, first handle available ScheduleEdges previously put into fe2ses
279 if((same) && (sn2fes.containsKey(preSNode))) {
280 Vector<FEdge> fes = sn2fes.remove(preSNode);
281 for(int j = 0; j < fes.size(); j++) {
282 FEdge tempfe = fes.elementAt(j);
283 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
284 ScheduleEdge tempse = ses.elementAt(0);
285 int temptime = tempse.getListExeTime();
286 // find out the ScheduleEdge with least exeTime
287 for(int k = 1; k < ses.size(); k++) {
288 int ttemp = ses.elementAt(k).getListExeTime();
289 if(ttemp < temptime) {
290 tempse = ses.elementAt(k);
295 handleScheduleEdge(tempse, true);
296 ses.removeElement(tempse);
297 // handle other ScheduleEdges
298 for(int k = 0; k < ses.size(); k++) {
299 handleScheduleEdge(ses.elementAt(k), false);
302 fe2ses.remove(tempfe);
307 if((!(se.getTransTime() < this.transThreshold)) && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
309 splitSNode(se, true);
311 // handle this ScheduleEdge
312 handleScheduleEdge(se, true);
318 if(!fe2ses.isEmpty()) {
319 Set<FEdge> keys = fe2ses.keySet();
320 Iterator it_keys = keys.iterator();
321 while(it_keys.hasNext()) {
322 FEdge tempfe = (FEdge)it_keys.next();
323 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
324 ScheduleEdge tempse = ses.elementAt(0);
325 int temptime = tempse.getListExeTime();
326 // find out the ScheduleEdge with least exeTime
327 for(int k = 1; k < ses.size(); k++) {
328 int ttemp = ses.elementAt(k).getListExeTime();
329 if(ttemp < temptime) {
330 tempse = ses.elementAt(k);
335 handleScheduleEdge(tempse, true);
336 ses.removeElement(tempse);
337 // handle other ScheduleEdges
338 for(int k = 0; k < ses.size(); k++) {
339 handleScheduleEdge(ses.elementAt(k), false);
350 SchedulingUtil.printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
353 private void handleScheduleEdge(ScheduleEdge se, boolean merge) {
355 int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
358 rate = (int)Math.ceil((se.getTransTime() - calInExeTime(se.getSourceFState()))/ se.getListExeTime());
362 } catch (Exception e) {
366 // clone the whole ScheduleNode lists starting with se's target
367 for(int j = 1; j < repeat; j++ ) {
368 cloneSNodeList(se, true);
371 se.setProbability(100);
375 // clone the whole ScheduleNode lists starting with se's target
376 for(int j = 0; j < repeat; j++ ) {
377 cloneSNodeList(se, true);
380 se.setProbability(100);
383 // merge the original ScheduleNode to the source ScheduleNode
384 ((ScheduleNode)se.getSource()).mergeSEdge(se);
385 scheduleNodes.remove(se.getTarget());
386 scheduleEdges.remove(se);
387 // As se has been changed into an internal edge inside a ScheduleNode,
388 // change the source and target of se from original ScheduleNodes into ClassNodes.
389 se.setTarget(se.getTargetCNode());
390 se.setSource(se.getSourceCNode());
392 // clone the whole ScheduleNode lists starting with se's target
393 for(int j = 1; j < repeat; j++ ) {
394 cloneSNodeList(se, true);
397 se.setProbability(100);
401 private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) {
402 Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
403 ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
404 scheduleNodes.add(csNode);
406 // Clone all the external in ScheduleEdges
409 Vector inedges = sEdge.getTarget().getInedgeVector();
410 for(i = 0; i < inedges.size(); i++) {
411 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
414 se = new ScheduleEdge(csNode, "new", tse.getFstate(), tse.getIsNew(), 0); //new ScheduleEdge(csNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0);
415 se.setProbability(100);
418 se = new ScheduleEdge(csNode, "transmit", tse.getFstate(), false, 0);//new ScheduleEdge(csNode, "transmit", tse.getClassDescriptor(), false, 0);
420 se.setSourceCNode(tse.getSourceCNode());
421 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
422 se.setFEdge(tse.getFEdge());
423 se.setTargetFState(tse.getTargetFState());
425 tse.getSource().addEdge(se);
426 scheduleEdges.add(se);
430 sEdge.getTarget().removeInedge(sEdge);
431 sEdge.setTarget(csNode);
432 csNode.getInedgeVector().add(sEdge);
433 sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
434 //sEdge.setTargetFState(null);
435 sEdge.setIsclone(true);
438 Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>();
439 Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>();
440 Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>();
442 toClone.add((ScheduleNode)sEdge.getTarget());
444 while(!toClone.isEmpty()) {
445 Hashtable<ClassNode, ClassNode> tocn2cn = new Hashtable<ClassNode, ClassNode>();
446 csNode = clone.poll();
447 ScheduleNode osNode = toClone.poll();
448 cn2cn = qcn2cn.poll();
449 // Clone all the external ScheduleEdges and the following ScheduleNodes
450 Vector edges = osNode.getEdgeVector();
451 for(i = 0; i < edges.size(); i++) {
452 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
453 ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
454 scheduleNodes.add(tSNode);
456 toClone.add((ScheduleNode)tse.getTarget());
458 ScheduleEdge se = null;
460 se = new ScheduleEdge(tSNode, "new", tse.getFstate(), tse.getIsNew(), 0);//new ScheduleEdge(tSNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0);
461 se.setProbability(tse.getProbability());
462 se.setNewRate(tse.getNewRate());
464 se = new ScheduleEdge(tSNode, "transmit", tse.getFstate(), false, 0);//new ScheduleEdge(tSNode, "transmit", tse.getClassDescriptor(), false, 0);
466 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
467 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
468 se.setFEdge(tse.getFEdge());
469 se.setTargetFState(tse.getTargetFState());
472 scheduleEdges.add(se);
483 private int calInExeTime(FlagState fs) throws Exception {
485 ClassDescriptor cd = fs.getClassDescriptor();
486 ClassNode cNode = cd2ClassNode.get(cd);
487 exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
489 Vector inedges = cNode.getInedgeVector();
490 if(inedges.size() > 1) {
491 throw new Exception("Error: ClassNode's inedges more than one!");
493 if(inedges.size() > 0) {
494 ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
495 cNode = (ClassNode)sEdge.getSource();
496 exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
502 exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
506 private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) {
507 FEdge fe = se.getFEdge();
508 FlagState fs = (FlagState)fe.getTarget();
509 FlagState nfs = (FlagState)fs.clone();
510 fs.getEdgeVector().removeAllElements();
511 nfs.getInedgeVector().removeAllElements();
512 ClassNode sCNode = se.getSourceCNode();
514 // split the subtree whose root is nfs from the whole flag transition tree
515 Vector<FlagState> sfss = sCNode.getFlagStates();
516 Vector<FlagState> fStates = new Vector<FlagState>();
517 Queue<FlagState> toiterate = new LinkedList<FlagState>();
520 while(!toiterate.isEmpty()){
521 FlagState tfs = toiterate.poll();
522 Iterator it_edges = tfs.edges();
523 while(it_edges.hasNext()) {
524 FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
525 if(!fStates.contains(temp)) {
528 sfss.removeElement(temp);
533 Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
535 // create a ClassNode and ScheduleNode for this subtree
536 ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
537 ScheduleNode sNode = new ScheduleNode(cNode, 0);
538 cNode.setScheduleNode(sNode);
539 cNode.setSorted(true);
540 cNode.setTransTime(sCNode.getTransTime());
541 classNodes.add(cNode);
542 scheduleNodes.add(sNode);
545 } catch (Exception e) {
548 // flush the exeTime of fs and its ancestors
551 while(!toiterate.isEmpty()) {
552 FlagState tfs = toiterate.poll();
553 int ttime = tfs.getExeTime();
554 Iterator it_inedges = tfs.inedges();
555 while(it_inedges.hasNext()) {
556 FEdge fEdge = (FEdge)it_inedges.next();
557 FlagState temp = (FlagState)fEdge.getSource();
558 int time = fEdge.getExeTime() + ttime;
559 if(temp.getExeTime() > time) {
560 temp.setExeTime(time);
567 // create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode
568 ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", (FlagState)fe.getTarget(), false, 0);//new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
569 sEdge.setTargetFState(fs);
571 sEdge.setSourceCNode(sCNode);
572 sEdge.setTargetCNode(cNode);
573 sEdge.setTargetFState(nfs);
575 // Add calculation codes for calculating transmit time of an object
576 sEdge.setTransTime(cNode.getTransTime());
577 se.getSource().addEdge(sEdge);
578 scheduleEdges.add(sEdge);
579 // redirect ScheudleEdges out of this subtree to the new ScheduleNode
580 Iterator it_sEdges = se.getSource().edges();
581 Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
582 while(it_sEdges.hasNext()) {
583 ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
584 if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
585 if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
586 tse.setSource(sNode);
587 tse.setSourceCNode(cNode);
588 sNode.getEdgeVector().addElement(tse);
593 se.getSource().getEdgeVector().removeAll(toremove);
598 //merge se into its source ScheduleNode
599 ((ScheduleNode)se.getSource()).mergeSEdge(se);
600 scheduleNodes.remove(se.getTarget());
601 scheduleEdges.removeElement(se);
602 // As se has been changed into an internal edge inside a ScheduleNode,
603 // change the source and target of se from original ScheduleNodes into ClassNodes.
604 se.setTarget(se.getTargetCNode());
605 se.setSource(se.getSourceCNode());
607 handleScheduleEdge(se, true);
613 public void schedule() throws Exception {
614 if(this.coreNum == -1) {
615 throw new Exception("Error: un-initialized coreNum when doing scheduling.");
618 if(this.scheduleGraphs == null) {
619 this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
622 int reduceNum = this.scheduleNodes.size() - this.coreNum;
624 // Enough cores, no need to merge more ScheduleEdge
625 if(!(reduceNum > 0)) {
626 this.scheduleGraphs.addElement(this.scheduleNodes);
628 // sort the ScheduleEdges in dececending order of transmittime
629 Vector<ScheduleEdge> sEdges = new Vector<ScheduleEdge>();
630 sEdges.addElement(this.scheduleEdges.elementAt(0));
631 for(int i = 1; i < this.scheduleEdges.size(); i++) {
632 ScheduleEdge temp = this.scheduleEdges.elementAt(i);
633 int j = sEdges.size() - 1;
635 if(temp.getTransTime() > sEdges.elementAt(j--).getTransTime()) {
639 sEdges.add(j+1, temp);
642 int temp = sEdges.elementAt(reduceNum - 1).getTransTime();
643 for(int i = sEdges.size() - 1; i > reduceNum - 1; i--) {
644 if(sEdges.elementAt(i).getTransTime() != temp) {
645 sEdges.removeElementAt(i);
650 int start = reduceNum - 2;
651 for(; start >= 0; start--) {
652 if(sEdges.elementAt(start).getTransTime() != temp) {
662 // generate scheduling
663 Vector candidates = new Vector();
664 for(int i = start; i < sEdges.size(); i++) {
665 candidates.addElement(Integer.valueOf(i));
667 Combination combGen = new Combination(candidates, reduceNum);
670 Vector toreduce = combGen.next();
671 if(toreduce != null) {
672 Vector<ScheduleEdge> reduceEdges = new Vector<ScheduleEdge>();
673 for(int i = 0; i < start; i++) {
674 reduceEdges.add(sEdges.elementAt(i));
676 for(int i = 0; i < toreduce.size(); i++) {
677 reduceEdges.add(sEdges.elementAt(((Integer)toreduce.elementAt(i)).intValue()));
679 Vector<ScheduleNode> sNodes = generateScheduling(reduceEdges, gid++);
680 this.scheduleGraphs.add(sNodes);
693 if(this.schedulings == null) {
694 this.schedulings = new Vector<Vector<Schedule>>();
697 for(int i = 0; i < this.scheduleGraphs.size(); i++) {
698 Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
699 Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
700 // for each ScheduleNode create a schedule node representing a core
701 Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
703 for(j = 0; j < scheduleGraph.size(); j++) {
704 sn2coreNum.put(scheduleGraph.elementAt(j), j);
706 for(j = 0; j < scheduleGraph.size(); j++) {
707 Schedule tmpSchedule = new Schedule(j);
708 ScheduleNode sn = scheduleGraph.elementAt(j);
710 Vector<ClassNode> cNodes = sn.getClassNodes();
711 for(int k = 0; k < cNodes.size(); k++) {
712 Iterator it_flags = cNodes.elementAt(k).getFlags();
713 while(it_flags.hasNext()) {
714 FlagState fs = (FlagState)it_flags.next();
715 Iterator it_edges = fs.edges();
716 while(it_edges.hasNext()) {
717 TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
718 tmpSchedule.addTask(td);
723 // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
724 Iterator it_edges = sn.edges();
725 while(it_edges.hasNext()) {
726 ScheduleEdge se = (ScheduleEdge)it_edges.next();
727 ScheduleNode target = (ScheduleNode)se.getTarget();
729 for(int k = 0; k < se.getNewRate(); k++) {
730 tmpSchedule.addTargetCore(se.getFstate(), sn2coreNum.get(target));
734 tmpSchedule.addTargetCore(se.getFstate(), sn2coreNum.get(target), se.getTargetFState());
737 it_edges = sn.getScheduleEdgesIterator();
738 while(it_edges.hasNext()) {
739 ScheduleEdge se = (ScheduleEdge)it_edges.next();
741 for(int k = 0; k < se.getNewRate(); k++) {
742 tmpSchedule.addTargetCore(se.getFstate(), j);
746 tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState());
749 scheduling.add(tmpSchedule);
751 this.schedulings.add(scheduling);
756 public Vector<ScheduleNode> generateScheduling(Vector<ScheduleEdge> reduceEdges, int gid) {
757 Vector<ScheduleNode> result = new Vector<ScheduleNode>();
759 // clone the ScheduleNodes
760 Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
761 Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
762 for(int i = 0; i < this.scheduleNodes.size(); i++) {
763 Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
764 ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
765 ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
767 sn2hash.put(temp, cn2cn);
768 sn2sn.put(tocopy, temp);
771 // clone the ScheduleEdges and merge those in reduceEdges at the same time
772 Vector<ScheduleEdge> toMerge = new Vector<ScheduleEdge>();
773 for(int i = 0; i < this.scheduleEdges.size(); i++) {
774 ScheduleEdge sse = this.scheduleEdges.elementAt(i);
775 ScheduleNode csource = sn2sn.get(sse.getSource());
776 ScheduleNode ctarget = sn2sn.get(sse.getTarget());
777 Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
778 Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
781 se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getIsNew(), gid);//new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
782 se.setProbability(sse.getProbability());
783 se.setNewRate(sse.getNewRate());
785 se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), false, gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
787 se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
788 se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
789 se.setFEdge(sse.getFEdge());
790 se.setTargetFState(sse.getTargetFState());
793 if(reduceEdges.contains(sse)) {
802 for(int i = 0; i < toMerge.size(); i++) {
803 ScheduleEdge sEdge = toMerge.elementAt(i);
805 ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
806 result.removeElement(sEdge.getTarget());
807 // As se has been changed into an internal edge inside a ScheduleNode,
808 // change the source and target of se from original ScheduleNodes into ClassNodes.
809 sEdge.setTarget(sEdge.getTargetCNode());
810 sEdge.setSource(sEdge.getSourceCNode());
814 String path = "scheduling_" + gid + ".dot";
815 SchedulingUtil.printScheduleGraph(path, result);
827 public Combination(Vector factors, int selectNum) throws Exception{
828 this.factors = factors;
829 if(factors.size() < selectNum) {
830 throw new Exception("Error: selectNum > candidates' number in combination.");
832 if(factors.size() == selectNum) {
838 this.head = this.factors.remove(0);
840 this.resultNum = this.factors.size() + 1;
844 this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
845 this.selectNum = selectNum;
847 for(int i = factors.size(); i > selectNum; i--) {
850 for(int i = factors.size() - selectNum; i > 0; i--) {
855 public Vector next() {
861 Vector result = this.factors;
864 if(this.tail == null) {
866 Vector result = new Vector();
867 result.add(this.head);
869 this.head = this.factors.remove(0);
873 Vector result = this.tail.next();
875 if(this.factors.size() == this.selectNum) {
878 result = this.factors;
882 this.head = this.factors.remove(0);
884 this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
885 result = this.tail.next();
886 } catch(Exception e) {