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 se.setTarget(se.getTargetCNode());
447 se.setSource(se.getSourceCNode());
448 se.getTargetCNode().addEdge(se);
450 // clone the whole ScheduleNode lists starting with se's target
451 for(int j = 1; j < repeat; j++ ) {
452 cloneSNodeList(se, true);
455 se.setProbability(100);
457 } catch (Exception e) {
463 private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) throws Exception {
464 Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>(); // hashtable from classnode in orignal se's targe to cloned one
465 ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
466 scheduleNodes.add(csNode);
468 // Clone all the external in ScheduleEdges
471 Vector inedges = sEdge.getTarget().getInedgeVector();
472 for(i = 0; i < inedges.size(); i++) {
473 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
475 switch(tse.getType()) {
476 case ScheduleEdge.NEWEDGE: {
477 se = new ScheduleEdge(csNode, "new", tse.getFstate(), tse.getType(), 0);
478 se.setProbability(100);
482 case ScheduleEdge.TRANSEDGE: {
483 se = new ScheduleEdge(csNode, "transmit", tse.getFstate(), tse.getType(), 0);
484 se.setProbability(tse.getProbability());
485 se.setNewRate(tse.getNewRate());
488 /*case ScheduleEdge.ASSOCEDGE: {
489 se = new ScheduleEdge(csNode, "associate", tse.getFstate(), tse.getType(), 0);
490 se.setProbability(tse.getProbability());
491 se.setNewRate(tse.getNewRate());
495 throw new Exception("Error: not valid ScheduleEdge here");
498 se.setSourceCNode(tse.getSourceCNode());
499 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
500 se.setFEdge(tse.getFEdge());
501 se.setTargetFState(tse.getTargetFState());
503 tse.getSource().addEdge(se);
504 scheduleEdges.add(se);
508 // in associate ScheduleEdgs
509 /*inedges = ((ScheduleNode)sEdge.getTarget()).getInAssociateSEdges();
510 for(i = 0; i < inedges.size(); i++) {
511 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
513 switch(tse.getType()) {
514 case ScheduleEdge.ASSOCEDGE: {
515 se = new ScheduleEdge(csNode, "associate", tse.getFstate(), tse.getType(), 0);
516 se.setProbability(tse.getProbability());
517 se.setNewRate(tse.getNewRate());
521 throw new Exception("Error: not valid ScheduleEdge here");
524 se.setSourceCNode(tse.getSourceCNode());
525 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
526 se.setFEdge(tse.getFEdge());
527 se.setTargetFState(tse.getTargetFState());
529 ((ScheduleNode)tse.getSource()).addAssociateSEdge(se);
533 sEdge.getTarget().removeInedge(sEdge);
534 sEdge.setTarget(csNode);
535 csNode.getInedgeVector().add(sEdge);
536 sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
537 //sEdge.setTargetFState(null);
538 sEdge.setIsclone(true);
541 Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>(); // all nodes to be cloned
542 Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>(); //clone nodes
543 Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>(); // queue of the mappings of classnodes inside cloned ScheduleNode
544 Vector<ScheduleNode> origins = new Vector<ScheduleNode>(); // queue of source ScheduleNode cloned
545 Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>(); // mapping from cloned ScheduleNode to clone ScheduleNode
547 toClone.add((ScheduleNode)sEdge.getTarget());
548 origins.addElement((ScheduleNode)sEdge.getTarget());
549 sn2sn.put((ScheduleNode)sEdge.getTarget(), csNode);
551 while(!toClone.isEmpty()) {
552 Hashtable<ClassNode, ClassNode> tocn2cn = new Hashtable<ClassNode, ClassNode>();
553 csNode = clone.poll();
554 ScheduleNode osNode = toClone.poll();
555 cn2cn = qcn2cn.poll();
556 // Clone all the external ScheduleEdges and the following ScheduleNodes
557 Vector edges = osNode.getEdgeVector();
558 for(i = 0; i < edges.size(); i++) {
559 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
560 ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
561 scheduleNodes.add(tSNode);
563 toClone.add((ScheduleNode)tse.getTarget());
564 origins.addElement((ScheduleNode)tse.getTarget());
565 sn2sn.put((ScheduleNode)tse.getTarget(), tSNode);
567 ScheduleEdge se = null;
568 switch(tse.getType()) {
569 case ScheduleEdge.NEWEDGE: {
570 se = new ScheduleEdge(tSNode, "new", tse.getFstate(), tse.getType(), 0);
573 case ScheduleEdge.TRANSEDGE: {
574 se = new ScheduleEdge(tSNode, "transmit", tse.getFstate(), tse.getType(), 0);
577 /*case ScheduleEdge.ASSOCEDGE: {
578 se = new ScheduleEdge(tSNode, "associate", tse.getFstate(), tse.getType(), 0);
582 throw new Exception("Error: not valid ScheduleEdge here");
585 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
586 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
587 se.setFEdge(tse.getFEdge());
588 se.setTargetFState(tse.getTargetFState());
589 se.setProbability(tse.getProbability());
590 se.setNewRate(tse.getNewRate());
593 scheduleEdges.add(se);
599 // associate ScheduleEdges
600 /*for(int j = 0; j < origins.size(); ++j) {
601 ScheduleNode osNode = origins.elementAt(i);
602 Vector<ScheduleEdge> edges = osNode.getAssociateSEdges();
603 ScheduleNode csNode = sn2sn.get(osNode);
604 for(i = 0; i < edges.size(); i++) {
605 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
606 assert(tse.getType() == ScheduleEdge.ASSOCEDGE);
607 ScheduleNode tSNode = (ScheduleNode)tse.getTarget();
608 if(origins.contains(tSNode)) {
609 tSNode = sn2sn.get(tSNode);
611 ScheduleEdge se = new ScheduleEdge(tSNode, "associate", tse.getFstate(), tse.getType(), 0);
612 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
613 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
614 se.setFEdge(tse.getFEdge());
615 se.setTargetFState(tse.getTargetFState());
616 se.setProbability(tse.getProbability());
617 se.setNewRate(tse.getNewRate());
619 csNode.addAssociateSEdge(se);
631 private int calInExeTime(FlagState fs) throws Exception {
633 ClassDescriptor cd = fs.getClassDescriptor();
634 ClassNode cNode = cd2ClassNode.get(cd);
635 exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
637 Vector inedges = cNode.getInedgeVector();
638 // Now that there are associate ScheduleEdges, there may be multiple inedges of a ClassNode
639 if(inedges.size() > 1) {
640 throw new Exception("Error: ClassNode's inedges more than one!");
642 if(inedges.size() > 0) {
643 /*ScheduleEdge sEdge = null;
644 for(int i = 0; i < inedges.size(); ++i) {
645 sEdge = (ScheduleEdge)inedges.elementAt(i);
646 if(sEdge.getType() == ScheduleEdge.NEWEDGE) {
650 ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
651 cNode = (ClassNode)sEdge.getSource();
652 exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
658 exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
662 private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) {
663 assert(ScheduleEdge.NEWEDGE == se.getType());
665 FEdge fe = se.getFEdge();
666 FlagState fs = (FlagState)fe.getTarget();
667 FlagState nfs = (FlagState)fs.clone();
668 fs.getEdgeVector().removeAllElements();
669 nfs.getInedgeVector().removeAllElements();
670 ClassNode sCNode = se.getSourceCNode();
672 // split the subtree whose root is nfs from the whole flag transition tree
673 Vector<FlagState> sfss = sCNode.getFlagStates();
674 Vector<FlagState> fStates = new Vector<FlagState>();
675 Queue<FlagState> toiterate = new LinkedList<FlagState>();
678 while(!toiterate.isEmpty()){
679 FlagState tfs = toiterate.poll();
680 Iterator it_edges = tfs.edges();
681 while(it_edges.hasNext()) {
682 FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
683 if(!fStates.contains(temp)) {
686 sfss.removeElement(temp);
691 Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
693 // create a ClassNode and ScheduleNode for this subtree
694 ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
695 ScheduleNode sNode = new ScheduleNode(cNode, 0);
696 cNode.setScheduleNode(sNode);
697 cNode.setSorted(true);
698 cNode.setTransTime(sCNode.getTransTime());
699 classNodes.add(cNode);
700 scheduleNodes.add(sNode);
703 } catch (Exception e) {
706 // flush the exeTime of fs and its ancestors
709 while(!toiterate.isEmpty()) {
710 FlagState tfs = toiterate.poll();
711 int ttime = tfs.getExeTime();
712 Iterator it_inedges = tfs.inedges();
713 while(it_inedges.hasNext()) {
714 FEdge fEdge = (FEdge)it_inedges.next();
715 FlagState temp = (FlagState)fEdge.getSource();
716 int time = fEdge.getExeTime() + ttime;
717 if(temp.getExeTime() > time) {
718 temp.setExeTime(time);
725 // create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode
726 ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", fs, ScheduleEdge.TRANSEDGE, 0);//new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
728 sEdge.setSourceCNode(sCNode);
729 sEdge.setTargetCNode(cNode);
730 sEdge.setTargetFState(nfs);
732 // Add calculation codes for calculating transmit time of an object
733 sEdge.setTransTime(cNode.getTransTime());
734 se.getSource().addEdge(sEdge);
735 scheduleEdges.add(sEdge);
736 // remove the ClassNodes and internal ScheduleEdges out of this subtree to the new ScheduleNode
737 ScheduleNode oldSNode = (ScheduleNode)se.getSource();
738 Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
739 Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
740 Vector<ClassNode> rCNodes = new Vector<ClassNode>();
741 rCNodes.addElement(sCNode);
742 if(it_isEdges != null){
743 while(it_isEdges.hasNext()) {
744 ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
745 if(rCNodes.contains(tse.getSourceCNode())) {
746 if(sCNode == tse.getSourceCNode()) {
747 if ((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
748 tse.setSource(cNode);
749 tse.setSourceCNode(cNode);
754 sNode.getScheduleEdges().addElement(tse);
755 sNode.getClassNodes().addElement(tse.getTargetCNode());
756 rCNodes.addElement(tse.getTargetCNode());
757 oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
758 toremove.addElement(tse);
762 oldSNode.getScheduleEdges().removeAll(toremove);
764 // redirect ScheudleEdges out of this subtree to the new ScheduleNode
765 Iterator it_sEdges = se.getSource().edges();
766 while(it_sEdges.hasNext()) {
767 ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
768 if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
769 if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
770 tse.setSource(sNode);
771 tse.setSourceCNode(cNode);
772 sNode.getEdgeVector().addElement(tse);
777 se.getSource().getEdgeVector().removeAll(toremove);
783 //merge se into its source ScheduleNode
784 ((ScheduleNode)se.getSource()).mergeSEdge(se);
785 scheduleNodes.remove(se.getTarget());
786 scheduleEdges.removeElement(se);
787 // As se has been changed into an internal edge inside a ScheduleNode,
788 // change the source and target of se from original ScheduleNodes into ClassNodes.
789 se.setTarget(se.getTargetCNode());
790 se.setSource(se.getSourceCNode());
791 se.getTargetCNode().addEdge(se);
793 handleScheduleEdge(se, true);
795 } catch (Exception e) {
803 public void schedule() throws Exception {
804 if(this.coreNum == -1) {
805 throw new Exception("Error: un-initialized coreNum when doing scheduling.");
808 if(this.scheduleGraphs == null) {
809 this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
812 int reduceNum = this.scheduleNodes.size() - this.coreNum;
814 // Enough cores, no need to merge more ScheduleEdge
815 if(!(reduceNum > 0)) {
816 this.scheduleGraphs.addElement(this.scheduleNodes);
818 String path = "scheduling_" + gid + ".dot";
819 SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
821 // sort the ScheduleEdges in dececending order of transmittime
822 Vector<ScheduleEdge> sEdges = new Vector<ScheduleEdge>();
823 sEdges.addElement(this.scheduleEdges.elementAt(0));
824 for(int i = 1; i < this.scheduleEdges.size(); i++) {
825 ScheduleEdge temp = this.scheduleEdges.elementAt(i);
826 int j = sEdges.size() - 1;
828 if(temp.getTransTime() > sEdges.elementAt(j--).getTransTime()) {
832 sEdges.add(j+1, temp);
835 int temp = sEdges.elementAt(reduceNum - 1).getTransTime();
836 for(int i = sEdges.size() - 1; i > reduceNum - 1; i--) {
837 if(sEdges.elementAt(i).getTransTime() != temp) {
838 sEdges.removeElementAt(i);
843 int start = reduceNum - 2;
844 for(; start >= 0; start--) {
845 if(sEdges.elementAt(start).getTransTime() != temp) {
855 // generate scheduling
856 Vector candidates = new Vector();
857 for(int i = start; i < sEdges.size(); i++) {
858 candidates.addElement(Integer.valueOf(i));
860 Combination combGen = new Combination(candidates, reduceNum);
863 Vector toreduce = combGen.next();
864 if(toreduce != null) {
865 Vector<ScheduleEdge> reduceEdges = new Vector<ScheduleEdge>();
866 for(int i = 0; i < start; i++) {
867 reduceEdges.add(sEdges.elementAt(i));
869 for(int i = 0; i < toreduce.size(); i++) {
870 reduceEdges.add(sEdges.elementAt(((Integer)toreduce.elementAt(i)).intValue()));
872 Vector<ScheduleNode> sNodes = generateScheduling(reduceEdges, gid++);
873 this.scheduleGraphs.add(sNodes);
886 if(this.schedulings == null) {
887 this.schedulings = new Vector<Vector<Schedule>>();
890 Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
891 Iterator it_tasks = state.getTaskSymbolTable().getDescriptorsIterator();
892 while(it_tasks.hasNext()) {
893 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
894 if(td.numParameters() > 1) {
895 multiparamtds.addElement(td);
899 for(int i = 0; i < this.scheduleGraphs.size(); i++) {
900 Hashtable<TaskDescriptor, Vector<Schedule>> td2cores = new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks reside on which cores
901 Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
902 Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
903 // for each ScheduleNode create a schedule node representing a core
904 Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
906 for(j = 0; j < scheduleGraph.size(); j++) {
907 sn2coreNum.put(scheduleGraph.elementAt(j), j);
910 boolean setstartupcore = false;
911 Schedule startup = null;
912 Vector<Integer> leafcores = new Vector<Integer>();
913 Vector[] ancestorCores = new Vector[this.coreNum];
914 for(j = 0; j < ancestorCores.length; ++j) {
915 ancestorCores[j] = new Vector();
917 for(j = 0; j < scheduleGraph.size(); j++) {
918 Schedule tmpSchedule = new Schedule(j);
919 ScheduleNode sn = scheduleGraph.elementAt(j);
921 Vector<ClassNode> cNodes = sn.getClassNodes();
922 for(int k = 0; k < cNodes.size(); k++) {
923 Iterator it_flags = cNodes.elementAt(k).getFlags();
924 while(it_flags.hasNext()) {
925 FlagState fs = (FlagState)it_flags.next();
926 Iterator it_edges = fs.edges();
927 while(it_edges.hasNext()) {
928 TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
929 tmpSchedule.addTask(td);
930 if(td.numParameters() > 1) {
931 if(!td2cores.containsKey(td)) {
932 td2cores.put(td, new Vector<Schedule>());
934 Vector<Schedule> tmpcores = td2cores.get(td);
935 if(!tmpcores.contains(tmpSchedule)) {
936 tmpcores.add(tmpSchedule);
938 tmpSchedule.addFState4TD(td, fs);
940 if(td.getParamType(0).getClassDesc().getSymbol().equals(TypeUtil.StartupClass)) {
941 assert(!setstartupcore);
943 startup = tmpSchedule;
944 setstartupcore = true;
950 // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
951 Iterator it_edges = sn.edges();
952 if(!it_edges.hasNext()) {
953 // leaf core, considered as ancestor of startup core
954 if(!leafcores.contains(Integer.valueOf(j))) {
955 leafcores.addElement(Integer.valueOf(j));
958 while(it_edges.hasNext()) {
959 ScheduleEdge se = (ScheduleEdge)it_edges.next();
960 ScheduleNode target = (ScheduleNode)se.getTarget();
961 Integer targetcore = sn2coreNum.get(target);
962 switch(se.getType()) {
963 case ScheduleEdge.NEWEDGE: {
964 for(int k = 0; k < se.getNewRate(); k++) {
965 tmpSchedule.addTargetCore(se.getFstate(), targetcore);
969 case ScheduleEdge.TRANSEDGE: {
971 tmpSchedule.addTargetCore(se.getFstate(), targetcore, se.getTargetFState());
972 // check if missed some FlagState associated with some multi-parameter
973 // task, which has been cloned when splitting a ClassNode
974 FlagState fs = se.getSourceFState();
975 FlagState tfs = se.getTargetFState();
976 Iterator it = tfs.edges();
977 while(it.hasNext()) {
978 TaskDescriptor td = ((FEdge)it.next()).getTask();
979 if(td.numParameters() > 1) {
980 if(tmpSchedule.getTasks().contains(td)) {
981 tmpSchedule.addFState4TD(td, fs);
987 /*case ScheduleEdge.ASSOCEDGE: {
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());
1012 /*case ScheduleEdge.ASSOCEDGE: {
1018 scheduling.add(tmpSchedule);
1021 leafcores.removeElement(Integer.valueOf(startupcore));
1022 ancestorCores[startupcore] = leafcores;
1023 int number = this.coreNum;
1024 if(scheduling.size() < number) {
1025 number = scheduling.size();
1027 for(j = 0; j < number; ++j) {
1028 scheduling.elementAt(j).setAncestorCores(ancestorCores[j]);
1031 // set up all the associate ally cores
1032 if(multiparamtds.size() > 0) {
1033 Object[] tds = (td2cores.keySet().toArray());
1034 for(j = 0; j < tds.length; ++j) {
1035 TaskDescriptor td = (TaskDescriptor)tds[j];
1036 Vector<Schedule> cores = td2cores.get(td);
1037 if(cores.size() == 1) {
1040 for(int k = 0; k < cores.size(); ++k) {
1041 Schedule tmpSchedule = cores.elementAt(k);
1042 Vector<FlagState> tmpfss = tmpSchedule.getFStates4TD(td);
1043 for(int h = 0; h < tmpfss.size(); ++h) {
1044 for(int l = 0; l < cores.size(); ++l) {
1046 tmpSchedule.addAllyCore(tmpfss.elementAt(h), cores.elementAt(l).getCoreNum());
1054 this.schedulings.add(scheduling);
1059 public Vector<ScheduleNode> generateScheduling(Vector<ScheduleEdge> reduceEdges, int gid) {
1060 Vector<ScheduleNode> result = new Vector<ScheduleNode>();
1062 // clone the ScheduleNodes
1063 Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
1064 Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
1065 for(int i = 0; i < this.scheduleNodes.size(); i++) {
1066 Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
1067 ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
1068 ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
1069 result.add(i, temp);
1070 sn2hash.put(temp, cn2cn);
1071 sn2sn.put(tocopy, temp);
1074 // clone the ScheduleEdges and merge those in reduceEdges at the same time
1075 Vector<ScheduleEdge> toMerge = new Vector<ScheduleEdge>();
1076 for(int i = 0; i < this.scheduleEdges.size(); i++) {
1077 ScheduleEdge sse = this.scheduleEdges.elementAt(i);
1078 ScheduleNode csource = sn2sn.get(sse.getSource());
1079 ScheduleNode ctarget = sn2sn.get(sse.getTarget());
1080 Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
1081 Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
1082 ScheduleEdge se = null;
1083 switch(sse.getType()) {
1084 case ScheduleEdge.NEWEDGE: {
1085 se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
1086 se.setProbability(sse.getProbability());
1087 se.setNewRate(sse.getNewRate());
1090 case ScheduleEdge.TRANSEDGE: {
1091 se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
1094 /*case ScheduleEdge.ASSOCEDGE: {
1096 se = new ScheduleEdge(ctarget, "associate", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
1100 se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
1101 se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
1102 se.setFEdge(sse.getFEdge());
1103 se.setTargetFState(sse.getTargetFState());
1104 se.setIsclone(true);
1105 csource.addEdge(se);
1106 if(reduceEdges.contains(sse)) {
1115 for(int i = 0; i < toMerge.size(); i++) {
1116 ScheduleEdge sEdge = toMerge.elementAt(i);
1118 switch(sEdge.getType()) {
1119 case ScheduleEdge.NEWEDGE: {
1121 ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
1122 } catch(Exception e) {
1123 e.printStackTrace();
1128 case ScheduleEdge.TRANSEDGE: {
1130 ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
1131 } catch(Exception e) {
1132 e.printStackTrace();
1137 /*case ScheduleEdge.ASSOCEDGE: {
1142 result.removeElement(sEdge.getTarget());
1143 if(ScheduleEdge.NEWEDGE == sEdge.getType()) {
1144 // As se has been changed into an internal edge inside a ScheduleNode,
1145 // change the source and target of se from original ScheduleNodes into ClassNodes.
1146 sEdge.setTarget(sEdge.getTargetCNode());
1147 sEdge.setSource(sEdge.getSourceCNode());
1148 sEdge.getTargetCNode().addEdge(sEdge);
1153 String path = "scheduling_" + gid + ".dot";
1154 SchedulingUtil.printScheduleGraph(path, result);
1166 public Combination(Vector factors, int selectNum) throws Exception{
1167 this.factors = factors;
1168 if(factors.size() < selectNum) {
1169 throw new Exception("Error: selectNum > candidates' number in combination.");
1171 if(factors.size() == selectNum) {
1177 this.head = this.factors.remove(0);
1178 if(selectNum == 1) {
1179 this.resultNum = this.factors.size() + 1;
1183 this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
1184 this.selectNum = selectNum;
1186 for(int i = factors.size(); i > selectNum; i--) {
1187 this.resultNum *= i;
1189 for(int i = factors.size() - selectNum; i > 0; i--) {
1190 this.resultNum /= i;
1194 public Vector next() {
1195 if(resultNum == 0) {
1200 Vector result = this.factors;
1203 if(this.tail == null) {
1205 Vector result = new Vector();
1206 result.add(this.head);
1207 if(resultNum != 0) {
1208 this.head = this.factors.remove(0);
1212 Vector result = this.tail.next();
1213 if(result == null) {
1214 if(this.factors.size() == this.selectNum) {
1217 result = this.factors;
1221 this.head = this.factors.remove(0);
1223 this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
1224 result = this.tail.next();
1225 } catch(Exception e) {
1226 e.printStackTrace();
1230 result.add(0, head);