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", fs, false, 0);//new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
570 sEdge.setSourceCNode(sCNode);
571 sEdge.setTargetCNode(cNode);
572 sEdge.setTargetFState(nfs);
574 // Add calculation codes for calculating transmit time of an object
575 sEdge.setTransTime(cNode.getTransTime());
576 se.getSource().addEdge(sEdge);
577 scheduleEdges.add(sEdge);
578 // remove the ClassNodes and internal ScheduleEdges out of this subtree to the new ScheduleNode
579 ScheduleNode oldSNode = (ScheduleNode)se.getSource();
580 Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
581 Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
582 Vector<ClassNode> rCNodes = new Vector<ClassNode>();
583 rCNodes.addElement(sCNode);
584 if(it_isEdges != null){
585 while(it_isEdges.hasNext()) {
586 ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
587 if(rCNodes.contains(tse.getSourceCNode())) {
588 if(sCNode == tse.getSourceCNode()) {
589 if ((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
590 tse.setSource(cNode);
591 tse.setSourceCNode(cNode);
596 sNode.getScheduleEdges().addElement(tse);
597 sNode.getClassNodes().addElement(tse.getTargetCNode());
598 rCNodes.addElement(tse.getTargetCNode());
599 oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
600 toremove.addElement(tse);
604 oldSNode.getScheduleEdges().removeAll(toremove);
606 // redirect ScheudleEdges out of this subtree to the new ScheduleNode
607 Iterator it_sEdges = se.getSource().edges();
608 //Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
609 while(it_sEdges.hasNext()) {
610 ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
611 if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
612 if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
613 tse.setSource(sNode);
614 tse.setSourceCNode(cNode);
615 sNode.getEdgeVector().addElement(tse);
620 se.getSource().getEdgeVector().removeAll(toremove);
625 //merge se into its source ScheduleNode
626 ((ScheduleNode)se.getSource()).mergeSEdge(se);
627 scheduleNodes.remove(se.getTarget());
628 scheduleEdges.removeElement(se);
629 // As se has been changed into an internal edge inside a ScheduleNode,
630 // change the source and target of se from original ScheduleNodes into ClassNodes.
631 se.setTarget(se.getTargetCNode());
632 se.setSource(se.getSourceCNode());
634 handleScheduleEdge(se, true);
640 public void schedule() throws Exception {
641 if(this.coreNum == -1) {
642 throw new Exception("Error: un-initialized coreNum when doing scheduling.");
645 if(this.scheduleGraphs == null) {
646 this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
649 int reduceNum = this.scheduleNodes.size() - this.coreNum;
651 // Enough cores, no need to merge more ScheduleEdge
652 if(!(reduceNum > 0)) {
653 this.scheduleGraphs.addElement(this.scheduleNodes);
655 // sort the ScheduleEdges in dececending order of transmittime
656 Vector<ScheduleEdge> sEdges = new Vector<ScheduleEdge>();
657 sEdges.addElement(this.scheduleEdges.elementAt(0));
658 for(int i = 1; i < this.scheduleEdges.size(); i++) {
659 ScheduleEdge temp = this.scheduleEdges.elementAt(i);
660 int j = sEdges.size() - 1;
662 if(temp.getTransTime() > sEdges.elementAt(j--).getTransTime()) {
666 sEdges.add(j+1, temp);
669 int temp = sEdges.elementAt(reduceNum - 1).getTransTime();
670 for(int i = sEdges.size() - 1; i > reduceNum - 1; i--) {
671 if(sEdges.elementAt(i).getTransTime() != temp) {
672 sEdges.removeElementAt(i);
677 int start = reduceNum - 2;
678 for(; start >= 0; start--) {
679 if(sEdges.elementAt(start).getTransTime() != temp) {
689 // generate scheduling
690 Vector candidates = new Vector();
691 for(int i = start; i < sEdges.size(); i++) {
692 candidates.addElement(Integer.valueOf(i));
694 Combination combGen = new Combination(candidates, reduceNum);
697 Vector toreduce = combGen.next();
698 if(toreduce != null) {
699 Vector<ScheduleEdge> reduceEdges = new Vector<ScheduleEdge>();
700 for(int i = 0; i < start; i++) {
701 reduceEdges.add(sEdges.elementAt(i));
703 for(int i = 0; i < toreduce.size(); i++) {
704 reduceEdges.add(sEdges.elementAt(((Integer)toreduce.elementAt(i)).intValue()));
706 Vector<ScheduleNode> sNodes = generateScheduling(reduceEdges, gid++);
707 this.scheduleGraphs.add(sNodes);
720 if(this.schedulings == null) {
721 this.schedulings = new Vector<Vector<Schedule>>();
724 for(int i = 0; i < this.scheduleGraphs.size(); i++) {
725 Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
726 Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
727 // for each ScheduleNode create a schedule node representing a core
728 Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
730 for(j = 0; j < scheduleGraph.size(); j++) {
731 sn2coreNum.put(scheduleGraph.elementAt(j), j);
733 for(j = 0; j < scheduleGraph.size(); j++) {
734 Schedule tmpSchedule = new Schedule(j);
735 ScheduleNode sn = scheduleGraph.elementAt(j);
737 Vector<ClassNode> cNodes = sn.getClassNodes();
738 for(int k = 0; k < cNodes.size(); k++) {
739 Iterator it_flags = cNodes.elementAt(k).getFlags();
740 while(it_flags.hasNext()) {
741 FlagState fs = (FlagState)it_flags.next();
742 Iterator it_edges = fs.edges();
743 while(it_edges.hasNext()) {
744 TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
745 tmpSchedule.addTask(td);
750 // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
751 Iterator it_edges = sn.edges();
752 while(it_edges.hasNext()) {
753 ScheduleEdge se = (ScheduleEdge)it_edges.next();
754 ScheduleNode target = (ScheduleNode)se.getTarget();
756 for(int k = 0; k < se.getNewRate(); k++) {
757 tmpSchedule.addTargetCore(se.getFstate(), sn2coreNum.get(target));
761 tmpSchedule.addTargetCore(se.getFstate(), sn2coreNum.get(target), se.getTargetFState());
764 it_edges = sn.getScheduleEdgesIterator();
765 while(it_edges.hasNext()) {
766 ScheduleEdge se = (ScheduleEdge)it_edges.next();
768 for(int k = 0; k < se.getNewRate(); k++) {
769 tmpSchedule.addTargetCore(se.getFstate(), j);
773 tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState());
776 scheduling.add(tmpSchedule);
778 this.schedulings.add(scheduling);
783 public Vector<ScheduleNode> generateScheduling(Vector<ScheduleEdge> reduceEdges, int gid) {
784 Vector<ScheduleNode> result = new Vector<ScheduleNode>();
786 // clone the ScheduleNodes
787 Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
788 Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
789 for(int i = 0; i < this.scheduleNodes.size(); i++) {
790 Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
791 ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
792 ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
794 sn2hash.put(temp, cn2cn);
795 sn2sn.put(tocopy, temp);
798 // clone the ScheduleEdges and merge those in reduceEdges at the same time
799 Vector<ScheduleEdge> toMerge = new Vector<ScheduleEdge>();
800 for(int i = 0; i < this.scheduleEdges.size(); i++) {
801 ScheduleEdge sse = this.scheduleEdges.elementAt(i);
802 ScheduleNode csource = sn2sn.get(sse.getSource());
803 ScheduleNode ctarget = sn2sn.get(sse.getTarget());
804 Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
805 Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
808 se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getIsNew(), gid);//new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
809 se.setProbability(sse.getProbability());
810 se.setNewRate(sse.getNewRate());
812 se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), false, gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
814 se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
815 se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
816 se.setFEdge(sse.getFEdge());
817 se.setTargetFState(sse.getTargetFState());
820 if(reduceEdges.contains(sse)) {
829 for(int i = 0; i < toMerge.size(); i++) {
830 ScheduleEdge sEdge = toMerge.elementAt(i);
832 if(sEdge.getIsNew()) {
833 ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
836 ((ScheduleNode)sEdge.getSource()).mergeTransEdge(sEdge);
837 } catch(Exception e) {
842 result.removeElement(sEdge.getTarget());
843 if(sEdge.getIsNew()) {
844 // As se has been changed into an internal edge inside a ScheduleNode,
845 // change the source and target of se from original ScheduleNodes into ClassNodes.
846 sEdge.setTarget(sEdge.getTargetCNode());
847 sEdge.setSource(sEdge.getSourceCNode());
852 String path = "scheduling_" + gid + ".dot";
853 SchedulingUtil.printScheduleGraph(path, result);
865 public Combination(Vector factors, int selectNum) throws Exception{
866 this.factors = factors;
867 if(factors.size() < selectNum) {
868 throw new Exception("Error: selectNum > candidates' number in combination.");
870 if(factors.size() == selectNum) {
876 this.head = this.factors.remove(0);
878 this.resultNum = this.factors.size() + 1;
882 this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
883 this.selectNum = selectNum;
885 for(int i = factors.size(); i > selectNum; i--) {
888 for(int i = factors.size() - selectNum; i > 0; i--) {
893 public Vector next() {
899 Vector result = this.factors;
902 if(this.tail == null) {
904 Vector result = new Vector();
905 result.add(this.head);
907 this.head = this.factors.remove(0);
911 Vector result = this.tail.next();
913 if(this.factors.size() == this.selectNum) {
916 result = this.factors;
920 this.head = this.factors.remove(0);
922 this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
923 result = this.tail.next();
924 } catch(Exception e) {