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(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);
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, ScheduleEdge.NEWEDGE, 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 // Create 'associate' edges between the ScheduleNodes.
165 /*Iterator<TaskDescriptor> it_tasks = (Iterator<TaskDescriptor>)state.getTaskSymbolTable().getDescriptorsIterator();
166 while(it_tasks.hasNext()) {
167 TaskDescriptor td = it_tasks.next();
168 int numParams = td.numParameters();
169 if(!(numParams > 1)) {
170 // single parameter task
173 ClassNode[] cNodes = new ClassNode[numParams];
174 for(i = 0; i < numParams; ++i) {
175 cNodes[i] = this.cd2ClassNode.get(td.getParamType(i).getClassDesc());
177 Vector<FEdge> fev = (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
178 // for each fedge associated to this td, create an associate ScheduleEdge
179 // from the ClassNode containg this FEdge to every other ClassNode representing
181 for(i = 0; i < fev.size(); ++i) {
182 FEdge tmpfe = fev.elementAt(i);
183 for(int j = 0; j < numParams; ++j) {
184 if(j == tmpfe.getIndex()) {
187 FlagState fs = (FlagState)tmpfe.getSource();
188 ScheduleEdge se = new ScheduleEdge(cNodes[j].getScheduleNode(), "associate", fs, ScheduleEdge.ASSOCEDGE, 0);
190 se.setSourceCNode(cNodes[i]);
191 se.setTargetCNode(cNodes[j]);
192 // targetFState is always null
193 cNodes[i].getScheduleNode().addAssociateSEdge(se);
194 // scheduleEdges only holds new/transmit edges
195 //scheduleEdges.add(se);
201 // Break down the 'cycle's
203 for(i = 0; i < toBreakDown.size(); i++ ) {
204 cloneSNodeList(toBreakDown.elementAt(i), false);
207 } catch (Exception e) {
212 // Remove fake 'new' edges
213 for(i = 0; i < scheduleEdges.size(); i++) {
214 /*if(ScheduleEdge.NEWEDGE != scheduleEdges.elementAt(i).getType()) {
217 ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i);
218 if((0 == se.getNewRate()) || (0 == se.getProbability())) {
219 scheduleEdges.removeElement(se);
220 scheduleNodes.removeElement(se.getTarget());
224 // Do topology sort of the ClassNodes and ScheduleEdges.
225 Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
226 Vector<ScheduleNode> tempSNodes = ClassNode.DFS.topology(scheduleNodes, ssev);
227 scheduleNodes.removeAllElements();
228 scheduleNodes = tempSNodes;
230 scheduleEdges.removeAllElements();
231 scheduleEdges = ssev;
235 SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes);
238 public void scheduleAnalysis() {
241 //Access the ScheduleEdges in reverse topology order
242 Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses = new Hashtable<FEdge, Vector<ScheduleEdge>>();
243 Hashtable<ScheduleNode, Vector<FEdge>> sn2fes = new Hashtable<ScheduleNode, Vector<FEdge>>();
244 ScheduleNode preSNode = null;
245 for(i = scheduleEdges.size(); i > 0; i--) {
246 ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i-1);
247 if(ScheduleEdge.NEWEDGE == se.getType()) {
248 if(preSNode == null) {
249 preSNode = (ScheduleNode)se.getSource();
252 boolean split = false;
253 FEdge fe = se.getFEdge();
254 if(fe.getSource() == fe.getTarget()) {
257 int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
260 for(int j = 1; j< repeat; j++ ) {
261 cloneSNodeList(se, true);
264 se.setProbability(100);
267 rate = (int)Math.ceil(se.getListExeTime()/ calInExeTime(se.getSourceFState()));
268 } catch (Exception e) {
271 for(int j = rate - 1; j > 0; j--) {
272 for(int k = repeat; k > 0; k--) {
273 cloneSNodeList(se, true);
276 } catch (Exception e) {
281 // if preSNode is not the same as se's source ScheduleNode
282 // handle any ScheduleEdges previously put into fe2ses whose source ScheduleNode is preSNode
283 boolean same = (preSNode == se.getSource());
285 // check the topology sort, only process those after se.getSource()
286 if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()) {
287 if(sn2fes.containsKey(preSNode)) {
288 Vector<FEdge> fes = sn2fes.remove(preSNode);
289 for(int j = 0; j < fes.size(); j++) {
290 FEdge tempfe = fes.elementAt(j);
291 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
292 ScheduleEdge tempse = ses.elementAt(0);
293 int temptime = tempse.getListExeTime();
294 // find out the ScheduleEdge with least exeTime
295 for(int k = 1; k < ses.size(); k++) {
296 int ttemp = ses.elementAt(k).getListExeTime();
297 if(ttemp < temptime) {
298 tempse = ses.elementAt(k);
303 handleScheduleEdge(tempse, true);
304 ses.removeElement(tempse);
305 // handle other ScheduleEdges
306 for(int k = 0; k < ses.size(); k++) {
307 handleScheduleEdge(ses.elementAt(k), false);
310 fe2ses.remove(tempfe);
315 preSNode = (ScheduleNode)se.getSource();
318 // if fe is the last task inside this ClassNode, delay the expanding and merging until we find all such 'new' edges
319 // associated with a last task inside this ClassNode
320 if(!fe.getTarget().edges().hasNext()) {
321 if(fe2ses.get(fe) == null) {
322 fe2ses.put(fe, new Vector<ScheduleEdge>());
324 if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
325 sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
327 if(!fe2ses.get(fe).contains(se)) {
328 fe2ses.get(fe).add(se);
330 if(!sn2fes.get((ScheduleNode)se.getSource()).contains(fe)) {
331 sn2fes.get((ScheduleNode)se.getSource()).add(fe);
334 // As this is not a last task, first handle available ScheduleEdges previously put into fe2ses
335 if((same) && (sn2fes.containsKey(preSNode))) {
336 Vector<FEdge> fes = sn2fes.remove(preSNode);
337 for(int j = 0; j < fes.size(); j++) {
338 FEdge tempfe = fes.elementAt(j);
339 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
340 ScheduleEdge tempse = ses.elementAt(0);
341 int temptime = tempse.getListExeTime();
342 // find out the ScheduleEdge with least exeTime
343 for(int k = 1; k < ses.size(); k++) {
344 int ttemp = ses.elementAt(k).getListExeTime();
345 if(ttemp < temptime) {
346 tempse = ses.elementAt(k);
351 handleScheduleEdge(tempse, true);
352 ses.removeElement(tempse);
353 // handle other ScheduleEdges
354 for(int k = 0; k < ses.size(); k++) {
355 handleScheduleEdge(ses.elementAt(k), false);
358 fe2ses.remove(tempfe);
363 if((!(se.getTransTime() < this.transThreshold)) && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
365 splitSNode(se, true);
367 // handle this ScheduleEdge
368 handleScheduleEdge(se, true);
374 if(!fe2ses.isEmpty()) {
375 Set<FEdge> keys = fe2ses.keySet();
376 Iterator it_keys = keys.iterator();
377 while(it_keys.hasNext()) {
378 FEdge tempfe = (FEdge)it_keys.next();
379 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
380 ScheduleEdge tempse = ses.elementAt(0);
381 int temptime = tempse.getListExeTime();
382 // find out the ScheduleEdge with least exeTime
383 for(int k = 1; k < ses.size(); k++) {
384 int ttemp = ses.elementAt(k).getListExeTime();
385 if(ttemp < temptime) {
386 tempse = ses.elementAt(k);
391 handleScheduleEdge(tempse, true);
392 ses.removeElement(tempse);
393 // handle other ScheduleEdges
394 for(int k = 0; k < ses.size(); k++) {
395 handleScheduleEdge(ses.elementAt(k), false);
406 SchedulingUtil.printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
409 private void handleScheduleEdge(ScheduleEdge se, boolean merge) {
412 int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
415 rate = (int)Math.ceil((se.getTransTime() - calInExeTime(se.getSourceFState()))/ se.getListExeTime());
419 } catch (Exception e) {
423 // clone the whole ScheduleNode lists starting with se's target
424 for(int j = 1; j < repeat; j++ ) {
425 cloneSNodeList(se, true);
428 se.setProbability(100);
432 // clone the whole ScheduleNode lists starting with se's target
433 for(int j = 0; j < repeat; j++ ) {
434 cloneSNodeList(se, true);
437 se.setProbability(100);
440 // merge the original ScheduleNode to the source ScheduleNode
441 ((ScheduleNode)se.getSource()).mergeSEdge(se);
442 scheduleNodes.remove(se.getTarget());
443 scheduleEdges.remove(se);
444 // As se has been changed into an internal edge inside a ScheduleNode,
445 // change the source and target of se from original ScheduleNodes into ClassNodes.
446 if(se.getType() == ScheduleEdge.NEWEDGE) {
447 se.setTarget(se.getTargetCNode());
448 se.setSource(se.getSourceCNode());
449 se.getTargetCNode().addEdge(se);
452 // clone the whole ScheduleNode lists starting with se's target
453 for(int j = 1; j < repeat; j++ ) {
454 cloneSNodeList(se, true);
457 se.setProbability(100);
459 } catch (Exception e) {
465 private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) throws Exception {
466 Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>(); // hashtable from classnode in orignal se's targe to cloned one
467 ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
468 scheduleNodes.add(csNode);
470 // Clone all the external in ScheduleEdges
473 Vector inedges = sEdge.getTarget().getInedgeVector();
474 for(i = 0; i < inedges.size(); i++) {
475 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
477 switch(tse.getType()) {
478 case ScheduleEdge.NEWEDGE: {
479 se = new ScheduleEdge(csNode, "new", tse.getFstate(), tse.getType(), 0);
480 se.setProbability(100);
484 case ScheduleEdge.TRANSEDGE: {
485 se = new ScheduleEdge(csNode, "transmit", tse.getFstate(), tse.getType(), 0);
486 se.setProbability(tse.getProbability());
487 se.setNewRate(tse.getNewRate());
490 /*case ScheduleEdge.ASSOCEDGE: {
491 se = new ScheduleEdge(csNode, "associate", tse.getFstate(), tse.getType(), 0);
492 se.setProbability(tse.getProbability());
493 se.setNewRate(tse.getNewRate());
497 throw new Exception("Error: not valid ScheduleEdge here");
500 se.setSourceCNode(tse.getSourceCNode());
501 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
502 se.setFEdge(tse.getFEdge());
503 se.setTargetFState(tse.getTargetFState());
505 tse.getSource().addEdge(se);
506 scheduleEdges.add(se);
510 // in associate ScheduleEdgs
511 /*inedges = ((ScheduleNode)sEdge.getTarget()).getInAssociateSEdges();
512 for(i = 0; i < inedges.size(); i++) {
513 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
515 switch(tse.getType()) {
516 case ScheduleEdge.ASSOCEDGE: {
517 se = new ScheduleEdge(csNode, "associate", tse.getFstate(), tse.getType(), 0);
518 se.setProbability(tse.getProbability());
519 se.setNewRate(tse.getNewRate());
523 throw new Exception("Error: not valid ScheduleEdge here");
526 se.setSourceCNode(tse.getSourceCNode());
527 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
528 se.setFEdge(tse.getFEdge());
529 se.setTargetFState(tse.getTargetFState());
531 ((ScheduleNode)tse.getSource()).addAssociateSEdge(se);
535 sEdge.getTarget().removeInedge(sEdge);
536 sEdge.setTarget(csNode);
537 csNode.getInedgeVector().add(sEdge);
538 sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
539 //sEdge.setTargetFState(null);
540 sEdge.setIsclone(true);
543 Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>(); // all nodes to be cloned
544 Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>(); //clone nodes
545 Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>(); // queue of the mappings of classnodes inside cloned ScheduleNode
546 Vector<ScheduleNode> origins = new Vector<ScheduleNode>(); // queue of source ScheduleNode cloned
547 Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>(); // mapping from cloned ScheduleNode to clone ScheduleNode
549 toClone.add((ScheduleNode)sEdge.getTarget());
550 origins.addElement((ScheduleNode)sEdge.getTarget());
551 sn2sn.put((ScheduleNode)sEdge.getTarget(), csNode);
553 while(!toClone.isEmpty()) {
554 Hashtable<ClassNode, ClassNode> tocn2cn = new Hashtable<ClassNode, ClassNode>();
555 csNode = clone.poll();
556 ScheduleNode osNode = toClone.poll();
557 cn2cn = qcn2cn.poll();
558 // Clone all the external ScheduleEdges and the following ScheduleNodes
559 Vector edges = osNode.getEdgeVector();
560 for(i = 0; i < edges.size(); i++) {
561 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
562 ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
563 scheduleNodes.add(tSNode);
565 toClone.add((ScheduleNode)tse.getTarget());
566 origins.addElement((ScheduleNode)tse.getTarget());
567 sn2sn.put((ScheduleNode)tse.getTarget(), tSNode);
569 ScheduleEdge se = null;
570 switch(tse.getType()) {
571 case ScheduleEdge.NEWEDGE: {
572 se = new ScheduleEdge(tSNode, "new", tse.getFstate(), tse.getType(), 0);
575 case ScheduleEdge.TRANSEDGE: {
576 se = new ScheduleEdge(tSNode, "transmit", tse.getFstate(), tse.getType(), 0);
579 /*case ScheduleEdge.ASSOCEDGE: {
580 se = new ScheduleEdge(tSNode, "associate", tse.getFstate(), tse.getType(), 0);
584 throw new Exception("Error: not valid ScheduleEdge here");
587 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
588 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
589 se.setFEdge(tse.getFEdge());
590 se.setTargetFState(tse.getTargetFState());
591 se.setProbability(tse.getProbability());
592 se.setNewRate(tse.getNewRate());
595 scheduleEdges.add(se);
601 // associate ScheduleEdges
602 /*for(int j = 0; j < origins.size(); ++j) {
603 ScheduleNode osNode = origins.elementAt(i);
604 Vector<ScheduleEdge> edges = osNode.getAssociateSEdges();
605 ScheduleNode csNode = sn2sn.get(osNode);
606 for(i = 0; i < edges.size(); i++) {
607 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
608 assert(tse.getType() == ScheduleEdge.ASSOCEDGE);
609 ScheduleNode tSNode = (ScheduleNode)tse.getTarget();
610 if(origins.contains(tSNode)) {
611 tSNode = sn2sn.get(tSNode);
613 ScheduleEdge se = new ScheduleEdge(tSNode, "associate", tse.getFstate(), tse.getType(), 0);
614 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
615 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
616 se.setFEdge(tse.getFEdge());
617 se.setTargetFState(tse.getTargetFState());
618 se.setProbability(tse.getProbability());
619 se.setNewRate(tse.getNewRate());
621 csNode.addAssociateSEdge(se);
633 private int calInExeTime(FlagState fs) throws Exception {
635 ClassDescriptor cd = fs.getClassDescriptor();
636 ClassNode cNode = cd2ClassNode.get(cd);
637 exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
639 Vector inedges = cNode.getInedgeVector();
640 // Now that there are associate ScheduleEdges, there may be multiple inedges of a ClassNode
641 if(inedges.size() > 1) {
642 throw new Exception("Error: ClassNode's inedges more than one!");
644 if(inedges.size() > 0) {
645 /*ScheduleEdge sEdge = null;
646 for(int i = 0; i < inedges.size(); ++i) {
647 sEdge = (ScheduleEdge)inedges.elementAt(i);
648 if(sEdge.getType() == ScheduleEdge.NEWEDGE) {
652 ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
653 cNode = (ClassNode)sEdge.getSource();
654 exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
660 exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
664 private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) {
665 assert(ScheduleEdge.NEWEDGE == se.getType());
667 FEdge fe = se.getFEdge();
668 FlagState fs = (FlagState)fe.getTarget();
669 FlagState nfs = (FlagState)fs.clone();
670 fs.getEdgeVector().removeAllElements();
671 nfs.getInedgeVector().removeAllElements();
672 ClassNode sCNode = se.getSourceCNode();
674 // split the subtree whose root is nfs from the whole flag transition tree
675 Vector<FlagState> sfss = sCNode.getFlagStates();
676 Vector<FlagState> fStates = new Vector<FlagState>();
677 Queue<FlagState> toiterate = new LinkedList<FlagState>();
680 while(!toiterate.isEmpty()){
681 FlagState tfs = toiterate.poll();
682 Iterator it_edges = tfs.edges();
683 while(it_edges.hasNext()) {
684 FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
685 if(!fStates.contains(temp)) {
688 sfss.removeElement(temp);
693 Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
695 // create a ClassNode and ScheduleNode for this subtree
696 ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
697 ScheduleNode sNode = new ScheduleNode(cNode, 0);
698 cNode.setScheduleNode(sNode);
699 cNode.setSorted(true);
700 cNode.setTransTime(sCNode.getTransTime());
701 classNodes.add(cNode);
702 scheduleNodes.add(sNode);
705 } catch (Exception e) {
708 // flush the exeTime of fs and its ancestors
711 while(!toiterate.isEmpty()) {
712 FlagState tfs = toiterate.poll();
713 int ttime = tfs.getExeTime();
714 Iterator it_inedges = tfs.inedges();
715 while(it_inedges.hasNext()) {
716 FEdge fEdge = (FEdge)it_inedges.next();
717 FlagState temp = (FlagState)fEdge.getSource();
718 int time = fEdge.getExeTime() + ttime;
719 if(temp.getExeTime() > time) {
720 temp.setExeTime(time);
727 // create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode
728 ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", fs, ScheduleEdge.TRANSEDGE, 0);//new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
730 sEdge.setSourceCNode(sCNode);
731 sEdge.setTargetCNode(cNode);
732 sEdge.setTargetFState(nfs);
734 // Add calculation codes for calculating transmit time of an object
735 sEdge.setTransTime(cNode.getTransTime());
736 se.getSource().addEdge(sEdge);
737 scheduleEdges.add(sEdge);
738 // remove the ClassNodes and internal ScheduleEdges out of this subtree to the new ScheduleNode
739 ScheduleNode oldSNode = (ScheduleNode)se.getSource();
740 Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
741 Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
742 Vector<ClassNode> rCNodes = new Vector<ClassNode>();
743 rCNodes.addElement(sCNode);
744 if(it_isEdges != null){
745 while(it_isEdges.hasNext()) {
746 ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
747 if(rCNodes.contains(tse.getSourceCNode())) {
748 if(sCNode == tse.getSourceCNode()) {
749 if ((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
750 tse.setSource(cNode);
751 tse.setSourceCNode(cNode);
756 sNode.getScheduleEdges().addElement(tse);
757 sNode.getClassNodes().addElement(tse.getTargetCNode());
758 rCNodes.addElement(tse.getTargetCNode());
759 oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
760 toremove.addElement(tse);
764 oldSNode.getScheduleEdges().removeAll(toremove);
766 // redirect ScheudleEdges out of this subtree to the new ScheduleNode
767 Iterator it_sEdges = se.getSource().edges();
768 while(it_sEdges.hasNext()) {
769 ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
770 if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
771 if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
772 tse.setSource(sNode);
773 tse.setSourceCNode(cNode);
774 sNode.getEdgeVector().addElement(tse);
779 se.getSource().getEdgeVector().removeAll(toremove);
785 //merge se into its source ScheduleNode
786 ((ScheduleNode)se.getSource()).mergeSEdge(se);
787 scheduleNodes.remove(se.getTarget());
788 scheduleEdges.removeElement(se);
789 // As se has been changed into an internal edge inside a ScheduleNode,
790 // change the source and target of se from original ScheduleNodes into ClassNodes.
791 if(se.getType() == ScheduleEdge.NEWEDGE) {
792 se.setTarget(se.getTargetCNode());
793 se.setSource(se.getSourceCNode());
794 se.getTargetCNode().addEdge(se);
797 handleScheduleEdge(se, true);
799 } catch (Exception e) {
807 public void schedule() throws Exception {
808 if(this.coreNum == -1) {
809 throw new Exception("Error: un-initialized coreNum when doing scheduling.");
812 if(this.scheduleGraphs == null) {
813 this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
816 int reduceNum = this.scheduleNodes.size() - this.coreNum;
818 // Enough cores, no need to merge more ScheduleEdge
819 if(!(reduceNum > 0)) {
820 this.scheduleGraphs.addElement(this.scheduleNodes);
822 String path = "scheduling_" + gid + ".dot";
823 SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
825 // sort the ScheduleEdges in dececending order of transmittime
826 Vector<ScheduleEdge> sEdges = new Vector<ScheduleEdge>();
827 sEdges.addElement(this.scheduleEdges.elementAt(0));
828 for(int i = 1; i < this.scheduleEdges.size(); i++) {
829 ScheduleEdge temp = this.scheduleEdges.elementAt(i);
830 int j = sEdges.size() - 1;
832 if(temp.getTransTime() > sEdges.elementAt(j--).getTransTime()) {
836 sEdges.add(j+1, temp);
839 int temp = sEdges.elementAt(reduceNum - 1).getTransTime();
840 for(int i = sEdges.size() - 1; i > reduceNum - 1; i--) {
841 if(sEdges.elementAt(i).getTransTime() != temp) {
842 sEdges.removeElementAt(i);
847 int start = reduceNum - 2;
848 for(; start >= 0; start--) {
849 if(sEdges.elementAt(start).getTransTime() != temp) {
859 // generate scheduling
860 Vector candidates = new Vector();
861 for(int i = start; i < sEdges.size(); i++) {
862 candidates.addElement(Integer.valueOf(i));
864 Combination combGen = new Combination(candidates, reduceNum);
867 Vector toreduce = combGen.next();
868 if(toreduce != null) {
869 Vector<ScheduleEdge> reduceEdges = new Vector<ScheduleEdge>();
870 for(int i = 0; i < start; i++) {
871 reduceEdges.add(sEdges.elementAt(i));
873 for(int i = 0; i < toreduce.size(); i++) {
874 reduceEdges.add(sEdges.elementAt(((Integer)toreduce.elementAt(i)).intValue()));
876 Vector<ScheduleNode> sNodes = generateScheduling(reduceEdges, gid++);
877 this.scheduleGraphs.add(sNodes);
890 if(this.schedulings == null) {
891 this.schedulings = new Vector<Vector<Schedule>>();
894 Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
895 Iterator it_tasks = state.getTaskSymbolTable().getDescriptorsIterator();
896 while(it_tasks.hasNext()) {
897 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
898 if(td.numParameters() > 1) {
899 multiparamtds.addElement(td);
903 for(int i = 0; i < this.scheduleGraphs.size(); i++) {
904 Hashtable<TaskDescriptor, Vector<Schedule>> td2cores = new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks reside on which cores
905 Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
906 Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
907 // for each ScheduleNode create a schedule node representing a core
908 Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
910 for(j = 0; j < scheduleGraph.size(); j++) {
911 sn2coreNum.put(scheduleGraph.elementAt(j), j);
914 boolean setstartupcore = false;
915 Schedule startup = null;
916 Vector<Integer> leafcores = new Vector<Integer>();
917 Vector[] ancestorCores = new Vector[this.coreNum];
918 for(j = 0; j < ancestorCores.length; ++j) {
919 ancestorCores[j] = new Vector();
921 for(j = 0; j < scheduleGraph.size(); j++) {
922 Schedule tmpSchedule = new Schedule(j);
923 ScheduleNode sn = scheduleGraph.elementAt(j);
925 Vector<ClassNode> cNodes = sn.getClassNodes();
926 for(int k = 0; k < cNodes.size(); k++) {
927 Iterator it_flags = cNodes.elementAt(k).getFlags();
928 while(it_flags.hasNext()) {
929 FlagState fs = (FlagState)it_flags.next();
930 Iterator it_edges = fs.edges();
931 while(it_edges.hasNext()) {
932 TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
933 tmpSchedule.addTask(td);
934 if(td.numParameters() > 1) {
935 if(!td2cores.containsKey(td)) {
936 td2cores.put(td, new Vector<Schedule>());
938 Vector<Schedule> tmpcores = td2cores.get(td);
939 if(!tmpcores.contains(tmpSchedule)) {
940 tmpcores.add(tmpSchedule);
942 tmpSchedule.addFState4TD(td, fs);
944 if(td.getParamType(0).getClassDesc().getSymbol().equals(TypeUtil.StartupClass)) {
945 assert(!setstartupcore);
947 startup = tmpSchedule;
948 setstartupcore = true;
954 // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
955 Iterator it_edges = sn.edges();
956 if(!it_edges.hasNext()) {
957 // leaf core, considered as ancestor of startup core
958 if(!leafcores.contains(Integer.valueOf(j))) {
959 leafcores.addElement(Integer.valueOf(j));
962 while(it_edges.hasNext()) {
963 ScheduleEdge se = (ScheduleEdge)it_edges.next();
964 ScheduleNode target = (ScheduleNode)se.getTarget();
965 Integer targetcore = sn2coreNum.get(target);
966 switch(se.getType()) {
967 case ScheduleEdge.NEWEDGE: {
968 for(int k = 0; k < se.getNewRate(); k++) {
969 tmpSchedule.addTargetCore(se.getFstate(), targetcore);
973 case ScheduleEdge.TRANSEDGE: {
975 tmpSchedule.addTargetCore(se.getFstate(), targetcore, se.getTargetFState());
976 // check if missed some FlagState associated with some multi-parameter
977 // task, which has been cloned when splitting a ClassNode
978 FlagState fs = se.getSourceFState();
979 FlagState tfs = se.getTargetFState();
980 Iterator it = tfs.edges();
981 while(it.hasNext()) {
982 TaskDescriptor td = ((FEdge)it.next()).getTask();
983 if(td.numParameters() > 1) {
984 if(tmpSchedule.getTasks().contains(td)) {
985 tmpSchedule.addFState4TD(td, fs);
992 tmpSchedule.addChildCores(targetcore);
993 if((targetcore.intValue() != j) && (!ancestorCores[targetcore.intValue()].contains((Integer.valueOf(j))))) {
994 ancestorCores[targetcore.intValue()].addElement(Integer.valueOf(j));
997 it_edges = sn.getScheduleEdgesIterator();
998 while(it_edges.hasNext()) {
999 ScheduleEdge se = (ScheduleEdge)it_edges.next();
1000 switch(se.getType()) {
1001 case ScheduleEdge.NEWEDGE: {
1002 for(int k = 0; k < se.getNewRate(); k++) {
1003 tmpSchedule.addTargetCore(se.getFstate(), j);
1007 case ScheduleEdge.TRANSEDGE: {
1009 tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState());
1014 scheduling.add(tmpSchedule);
1017 leafcores.removeElement(Integer.valueOf(startupcore));
1018 ancestorCores[startupcore] = leafcores;
1019 int number = this.coreNum;
1020 if(scheduling.size() < number) {
1021 number = scheduling.size();
1023 for(j = 0; j < number; ++j) {
1024 scheduling.elementAt(j).setAncestorCores(ancestorCores[j]);
1027 // set up all the associate ally cores
1028 if(multiparamtds.size() > 0) {
1029 Object[] tds = (td2cores.keySet().toArray());
1030 for(j = 0; j < tds.length; ++j) {
1031 TaskDescriptor td = (TaskDescriptor)tds[j];
1032 Vector<Schedule> cores = td2cores.get(td);
1033 if(cores.size() == 1) {
1036 for(int k = 0; k < cores.size(); ++k) {
1037 Schedule tmpSchedule = cores.elementAt(k);
1038 Vector<FlagState> tmpfss = tmpSchedule.getFStates4TD(td);
1039 for(int h = 0; h < tmpfss.size(); ++h) {
1040 for(int l = 0; l < cores.size(); ++l) {
1042 tmpSchedule.addAllyCore(tmpfss.elementAt(h), cores.elementAt(l).getCoreNum());
1050 this.schedulings.add(scheduling);
1055 public Vector<ScheduleNode> generateScheduling(Vector<ScheduleEdge> reduceEdges, int gid) {
1056 Vector<ScheduleNode> result = new Vector<ScheduleNode>();
1058 // clone the ScheduleNodes
1059 Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
1060 Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
1061 for(int i = 0; i < this.scheduleNodes.size(); i++) {
1062 Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
1063 ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
1064 ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
1065 result.add(i, temp);
1066 sn2hash.put(temp, cn2cn);
1067 sn2sn.put(tocopy, temp);
1070 // clone the ScheduleEdges and merge those in reduceEdges at the same time
1071 Vector<ScheduleEdge> toMerge = new Vector<ScheduleEdge>();
1072 for(int i = 0; i < this.scheduleEdges.size(); i++) {
1073 ScheduleEdge sse = this.scheduleEdges.elementAt(i);
1074 ScheduleNode csource = sn2sn.get(sse.getSource());
1075 ScheduleNode ctarget = sn2sn.get(sse.getTarget());
1076 Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
1077 Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
1078 ScheduleEdge se = null;
1079 switch(sse.getType()) {
1080 case ScheduleEdge.NEWEDGE: {
1081 se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
1082 se.setProbability(sse.getProbability());
1083 se.setNewRate(sse.getNewRate());
1086 case ScheduleEdge.TRANSEDGE: {
1087 se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
1091 se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
1092 se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
1093 se.setFEdge(sse.getFEdge());
1094 se.setTargetFState(sse.getTargetFState());
1095 se.setIsclone(true);
1096 csource.addEdge(se);
1097 if(reduceEdges.contains(sse)) {
1106 for(int i = 0; i < toMerge.size(); i++) {
1107 ScheduleEdge sEdge = toMerge.elementAt(i);
1109 switch(sEdge.getType()) {
1110 case ScheduleEdge.NEWEDGE: {
1112 ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
1113 } catch(Exception e) {
1114 e.printStackTrace();
1119 case ScheduleEdge.TRANSEDGE: {
1121 ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
1122 } catch(Exception e) {
1123 e.printStackTrace();
1129 result.removeElement(sEdge.getTarget());
1130 if(ScheduleEdge.NEWEDGE == sEdge.getType()) {
1131 // As se has been changed into an internal edge inside a ScheduleNode,
1132 // change the source and target of se from original ScheduleNodes into ClassNodes.
1133 sEdge.setTarget(sEdge.getTargetCNode());
1134 sEdge.setSource(sEdge.getSourceCNode());
1135 sEdge.getTargetCNode().addEdge(sEdge);
1140 String path = "scheduling_" + gid + ".dot";
1141 SchedulingUtil.printScheduleGraph(path, result);
1153 public Combination(Vector factors, int selectNum) throws Exception{
1154 this.factors = factors;
1155 if(factors.size() < selectNum) {
1156 throw new Exception("Error: selectNum > candidates' number in combination.");
1158 if(factors.size() == selectNum) {
1164 this.head = this.factors.remove(0);
1165 if(selectNum == 1) {
1166 this.resultNum = this.factors.size() + 1;
1170 this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
1171 this.selectNum = selectNum;
1173 for(int i = factors.size(); i > selectNum; i--) {
1174 this.resultNum *= i;
1176 for(int i = factors.size() - selectNum; i > 0; i--) {
1177 this.resultNum /= i;
1181 public Vector next() {
1182 if(resultNum == 0) {
1187 Vector result = this.factors;
1190 if(this.tail == null) {
1192 Vector result = new Vector();
1193 result.add(this.head);
1194 if(resultNum != 0) {
1195 this.head = this.factors.remove(0);
1199 Vector result = this.tail.next();
1200 if(result == null) {
1201 if(this.factors.size() == this.selectNum) {
1204 result = this.factors;
1208 this.head = this.factors.remove(0);
1210 this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
1211 result = this.tail.next();
1212 } catch(Exception e) {
1213 e.printStackTrace();
1217 result.add(0, head);