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 ScheduleNode startupNode = null;
98 // For each ClassNode create a ScheduleNode containing it
100 for(i = 0; i < classNodes.size(); i++) {
101 ClassNode cn = classNodes.elementAt(i);
102 ScheduleNode sn = new ScheduleNode(cn, 0);
103 if(cn.getClassDescriptor().getSymbol().equals(TypeUtil.StartupClass)) {
106 cn.setScheduleNode(sn);
107 scheduleNodes.add(sn);
110 } catch (Exception e) {
115 // Create 'new' edges between the ScheduleNodes.
116 Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
117 for(i = 0; i < classNodes.size(); i++) {
118 ClassNode cNode = classNodes.elementAt(i);
119 ClassDescriptor cd = cNode.getClassDescriptor();
120 Vector rootnodes = taskanalysis.getRootNodes(cd);
121 if(rootnodes != null) {
122 for(int h = 0; h < rootnodes.size(); h++) {
123 FlagState root=(FlagState)rootnodes.elementAt(h);
124 Vector allocatingTasks = root.getAllocatingTasks();
125 if(allocatingTasks != null) {
126 for(int k = 0; k < allocatingTasks.size(); k++) {
127 TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
128 Vector<FEdge> fev = (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
129 int numEdges = fev.size();
130 ScheduleNode sNode = cNode.getScheduleNode();
131 for(int j = 0; j < numEdges; j++) {
132 FEdge pfe = fev.elementAt(j);
133 FEdge.NewObjInfo noi = pfe.getNewObjInfo(cd);
134 if ((noi == null) || (noi.getNewRate() == 0) || (noi.getProbability() == 0)) {
135 // fake creating edge, do not need to create corresponding 'new' edge
138 if(noi.getRoot() == null) {
139 // set root FlagState
142 FlagState pfs = (FlagState)pfe.getTarget();
143 ClassDescriptor pcd = pfs.getClassDescriptor();
144 ClassNode pcNode = cdToCNodes.get(pcd);
146 ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", root, ScheduleEdge.NEWEDGE, 0);
148 sEdge.setSourceCNode(pcNode);
149 sEdge.setTargetCNode(cNode);
150 sEdge.setTargetFState(root);
151 sEdge.setNewRate(noi.getNewRate());
152 sEdge.setProbability(noi.getProbability());
153 pcNode.getScheduleNode().addEdge(sEdge);
154 scheduleEdges.add(sEdge);
155 if((j !=0 ) || (k != 0) || (h != 0)) {
156 toBreakDown.add(sEdge);
161 allocatingTasks = null;
169 // Break down the 'cycle's
171 for(i = 0; i < toBreakDown.size(); i++ ) {
172 cloneSNodeList(toBreakDown.elementAt(i), false);
175 } catch (Exception e) {
180 // Remove fake 'new' edges
181 for(i = 0; i < scheduleEdges.size(); i++) {
182 ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i);
183 if((0 == se.getNewRate()) || (0 == se.getProbability())) {
184 scheduleEdges.removeElement(se);
185 scheduleNodes.removeElement(se.getTarget());
189 // Do topology sort of the ClassNodes and ScheduleEdges.
190 Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
191 Vector<ScheduleNode> tempSNodes = ClassNode.DFS.topology(scheduleNodes, ssev);
192 scheduleNodes.removeAllElements();
193 scheduleNodes = tempSNodes;
195 scheduleEdges.removeAllElements();
196 scheduleEdges = ssev;
200 // Set the cid of these ScheduleNode
201 Queue<ScheduleNode> toVisit = new LinkedList<ScheduleNode>();
202 toVisit.add(startupNode);
203 while(!toVisit.isEmpty()) {
204 ScheduleNode sn = toVisit.poll();
205 if(sn.getCid() == -1) {
206 // not visited before
207 sn.setCid(ScheduleNode.colorID++);
208 Iterator it_edge = sn.edges();
209 while(it_edge.hasNext()) {
210 toVisit.add((ScheduleNode)((ScheduleEdge)it_edge.next()).getTarget());
215 SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes);
218 public void scheduleAnalysis() {
221 //Access the ScheduleEdges in reverse topology order
222 Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses = new Hashtable<FEdge, Vector<ScheduleEdge>>();
223 Hashtable<ScheduleNode, Vector<FEdge>> sn2fes = new Hashtable<ScheduleNode, Vector<FEdge>>();
224 ScheduleNode preSNode = null;
225 for(i = scheduleEdges.size(); i > 0; i--) {
226 ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i-1);
227 if(ScheduleEdge.NEWEDGE == se.getType()) {
228 if(preSNode == null) {
229 preSNode = (ScheduleNode)se.getSource();
232 boolean split = false;
233 FEdge fe = se.getFEdge();
234 if(fe.getSource() == fe.getTarget()) {
237 int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
240 for(int j = 1; j< repeat; j++ ) {
241 cloneSNodeList(se, true);
244 se.setProbability(100);
247 rate = (int)Math.ceil(se.getListExeTime()/ calInExeTime(se.getSourceFState()));
248 } catch (Exception e) {
251 for(int j = rate - 1; j > 0; j--) {
252 for(int k = repeat; k > 0; k--) {
253 cloneSNodeList(se, true);
256 } catch (Exception e) {
261 // if preSNode is not the same as se's source ScheduleNode
262 // handle any ScheduleEdges previously put into fe2ses whose source ScheduleNode is preSNode
263 boolean same = (preSNode == se.getSource());
265 // check the topology sort, only process those after se.getSource()
266 if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()) {
267 if(sn2fes.containsKey(preSNode)) {
268 Vector<FEdge> fes = sn2fes.remove(preSNode);
269 for(int j = 0; j < fes.size(); j++) {
270 FEdge tempfe = fes.elementAt(j);
271 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
272 ScheduleEdge tempse = ses.elementAt(0);
273 int temptime = tempse.getListExeTime();
274 // find out the ScheduleEdge with least exeTime
275 for(int k = 1; k < ses.size(); k++) {
276 int ttemp = ses.elementAt(k).getListExeTime();
277 if(ttemp < temptime) {
278 tempse = ses.elementAt(k);
283 handleScheduleEdge(tempse, true);
284 ses.removeElement(tempse);
285 // handle other ScheduleEdges
286 for(int k = 0; k < ses.size(); k++) {
287 handleScheduleEdge(ses.elementAt(k), false);
290 fe2ses.remove(tempfe);
295 preSNode = (ScheduleNode)se.getSource();
298 // if fe is the last task inside this ClassNode, delay the expanding and merging until we find all such 'new' edges
299 // associated with a last task inside this ClassNode
300 if(!fe.getTarget().edges().hasNext()) {
301 if(fe2ses.get(fe) == null) {
302 fe2ses.put(fe, new Vector<ScheduleEdge>());
304 if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
305 sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
307 if(!fe2ses.get(fe).contains(se)) {
308 fe2ses.get(fe).add(se);
310 if(!sn2fes.get((ScheduleNode)se.getSource()).contains(fe)) {
311 sn2fes.get((ScheduleNode)se.getSource()).add(fe);
314 // As this is not a last task, first handle available ScheduleEdges previously put into fe2ses
315 if((same) && (sn2fes.containsKey(preSNode))) {
316 Vector<FEdge> fes = sn2fes.remove(preSNode);
317 for(int j = 0; j < fes.size(); j++) {
318 FEdge tempfe = fes.elementAt(j);
319 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
320 ScheduleEdge tempse = ses.elementAt(0);
321 int temptime = tempse.getListExeTime();
322 // find out the ScheduleEdge with least exeTime
323 for(int k = 1; k < ses.size(); k++) {
324 int ttemp = ses.elementAt(k).getListExeTime();
325 if(ttemp < temptime) {
326 tempse = ses.elementAt(k);
331 handleScheduleEdge(tempse, true);
332 ses.removeElement(tempse);
333 // handle other ScheduleEdges
334 for(int k = 0; k < ses.size(); k++) {
335 handleScheduleEdge(ses.elementAt(k), false);
338 fe2ses.remove(tempfe);
343 if((!(se.getTransTime() < this.transThreshold)) && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
345 splitSNode(se, true);
347 // handle this ScheduleEdge
348 handleScheduleEdge(se, true);
354 if(!fe2ses.isEmpty()) {
355 Set<FEdge> keys = fe2ses.keySet();
356 Iterator it_keys = keys.iterator();
357 while(it_keys.hasNext()) {
358 FEdge tempfe = (FEdge)it_keys.next();
359 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
360 ScheduleEdge tempse = ses.elementAt(0);
361 int temptime = tempse.getListExeTime();
362 // find out the ScheduleEdge with least exeTime
363 for(int k = 1; k < ses.size(); k++) {
364 int ttemp = ses.elementAt(k).getListExeTime();
365 if(ttemp < temptime) {
366 tempse = ses.elementAt(k);
371 handleScheduleEdge(tempse, true);
372 ses.removeElement(tempse);
373 // handle other ScheduleEdges
374 for(int k = 0; k < ses.size(); k++) {
375 handleScheduleEdge(ses.elementAt(k), false);
386 SchedulingUtil.printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
389 private void handleScheduleEdge(ScheduleEdge se, boolean merge) {
392 int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
395 if(se.getListExeTime() == 0) {
398 rate = (int)Math.ceil((se.getTransTime() - calInExeTime(se.getSourceFState()))/ se.getListExeTime());
403 } catch (Exception e) {
407 // clone the whole ScheduleNode lists starting with se's target
408 for(int j = 1; j < repeat; j++ ) {
409 cloneSNodeList(se, true);
412 se.setProbability(100);
416 // clone the whole ScheduleNode lists starting with se's target
417 for(int j = 0; j < repeat; j++ ) {
418 cloneSNodeList(se, true);
421 se.setProbability(100);
424 // merge the original ScheduleNode to the source ScheduleNode
425 ((ScheduleNode)se.getSource()).mergeSEdge(se);
426 scheduleNodes.remove(se.getTarget());
427 scheduleEdges.remove(se);
428 // As se has been changed into an internal edge inside a ScheduleNode,
429 // change the source and target of se from original ScheduleNodes into ClassNodes.
430 if(se.getType() == ScheduleEdge.NEWEDGE) {
431 se.setTarget(se.getTargetCNode());
432 se.setSource(se.getSourceCNode());
433 se.getTargetCNode().addEdge(se);
436 // clone the whole ScheduleNode lists starting with se's target
437 for(int j = 1; j < repeat; j++ ) {
438 cloneSNodeList(se, true);
441 se.setProbability(100);
443 } catch (Exception e) {
449 private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) throws Exception {
450 Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>(); // hashtable from classnode in orignal se's targe to cloned one
451 ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
452 scheduleNodes.add(csNode);
454 // Clone all the external in ScheduleEdges
457 Vector inedges = sEdge.getTarget().getInedgeVector();
458 for(i = 0; i < inedges.size(); i++) {
459 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
461 switch(tse.getType()) {
462 case ScheduleEdge.NEWEDGE: {
463 se = new ScheduleEdge(csNode, "new", tse.getFstate(), tse.getType(), 0);
464 se.setProbability(100);
469 case ScheduleEdge.TRANSEDGE: {
470 se = new ScheduleEdge(csNode, "transmit", tse.getFstate(), tse.getType(), 0);
471 se.setProbability(tse.getProbability());
472 se.setNewRate(tse.getNewRate());
477 throw new Exception("Error: not valid ScheduleEdge here");
480 se.setSourceCNode(tse.getSourceCNode());
481 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
482 se.setFEdge(tse.getFEdge());
483 se.setTargetFState(tse.getTargetFState());
485 tse.getSource().addEdge(se);
486 scheduleEdges.add(se);
490 sEdge.getTarget().removeInedge(sEdge);
491 sEdge.setTarget(csNode);
492 csNode.getInedgeVector().add(sEdge);
493 sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
494 sEdge.setIsclone(true);
497 Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>(); // all nodes to be cloned
498 Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>(); //clone nodes
499 Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>(); // queue of the mappings of classnodes inside cloned ScheduleNode
500 Vector<ScheduleNode> origins = new Vector<ScheduleNode>(); // queue of source ScheduleNode cloned
501 Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>(); // mapping from cloned ScheduleNode to clone ScheduleNode
503 toClone.add((ScheduleNode)sEdge.getTarget());
504 origins.addElement((ScheduleNode)sEdge.getTarget());
505 sn2sn.put((ScheduleNode)sEdge.getTarget(), csNode);
507 while(!toClone.isEmpty()) {
508 Hashtable<ClassNode, ClassNode> tocn2cn = new Hashtable<ClassNode, ClassNode>();
509 csNode = clone.poll();
510 ScheduleNode osNode = toClone.poll();
511 cn2cn = qcn2cn.poll();
512 // Clone all the external ScheduleEdges and the following ScheduleNodes
513 Vector edges = osNode.getEdgeVector();
514 for(i = 0; i < edges.size(); i++) {
515 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
516 ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
517 scheduleNodes.add(tSNode);
519 toClone.add((ScheduleNode)tse.getTarget());
520 origins.addElement((ScheduleNode)tse.getTarget());
521 sn2sn.put((ScheduleNode)tse.getTarget(), tSNode);
523 ScheduleEdge se = null;
524 switch(tse.getType()) {
525 case ScheduleEdge.NEWEDGE: {
526 se = new ScheduleEdge(tSNode, "new", tse.getFstate(), tse.getType(), 0);
530 case ScheduleEdge.TRANSEDGE: {
531 se = new ScheduleEdge(tSNode, "transmit", tse.getFstate(), tse.getType(), 0);
536 throw new Exception("Error: not valid ScheduleEdge here");
539 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
540 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
541 se.setFEdge(tse.getFEdge());
542 se.setTargetFState(tse.getTargetFState());
543 se.setProbability(tse.getProbability());
544 se.setNewRate(tse.getNewRate());
547 scheduleEdges.add(se);
559 private int calInExeTime(FlagState fs) throws Exception {
561 ClassDescriptor cd = fs.getClassDescriptor();
562 ClassNode cNode = cd2ClassNode.get(cd);
563 exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
565 Vector inedges = cNode.getInedgeVector();
566 // Now that there are associate ScheduleEdges, there may be multiple inedges of a ClassNode
567 if(inedges.size() > 1) {
568 throw new Exception("Error: ClassNode's inedges more than one!");
570 if(inedges.size() > 0) {
571 ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
572 cNode = (ClassNode)sEdge.getSource();
573 exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
579 exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
583 private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) {
584 assert(ScheduleEdge.NEWEDGE == se.getType());
586 FEdge fe = se.getFEdge();
587 FlagState fs = (FlagState)fe.getTarget();
588 FlagState nfs = (FlagState)fs.clone();
589 fs.getEdgeVector().removeAllElements();
590 nfs.getInedgeVector().removeAllElements();
591 ClassNode sCNode = se.getSourceCNode();
593 // split the subtree whose root is nfs from the whole flag transition tree
594 Vector<FlagState> sfss = sCNode.getFlagStates();
595 Vector<FlagState> fStates = new Vector<FlagState>();
596 Queue<FlagState> toiterate = new LinkedList<FlagState>();
599 while(!toiterate.isEmpty()) {
600 FlagState tfs = toiterate.poll();
601 Iterator it_edges = tfs.edges();
602 while(it_edges.hasNext()) {
603 FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
604 if(!fStates.contains(temp)) {
607 sfss.removeElement(temp);
612 Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
614 // create a ClassNode and ScheduleNode for this subtree
615 ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
616 ScheduleNode sNode = new ScheduleNode(cNode, 0);
617 cNode.setScheduleNode(sNode);
618 cNode.setSorted(true);
619 cNode.setTransTime(sCNode.getTransTime());
620 classNodes.add(cNode);
621 scheduleNodes.add(sNode);
624 } catch (Exception e) {
627 // flush the exeTime of fs and its ancestors
630 while(!toiterate.isEmpty()) {
631 FlagState tfs = toiterate.poll();
632 int ttime = tfs.getExeTime();
633 Iterator it_inedges = tfs.inedges();
634 while(it_inedges.hasNext()) {
635 FEdge fEdge = (FEdge)it_inedges.next();
636 FlagState temp = (FlagState)fEdge.getSource();
637 int time = fEdge.getExeTime() + ttime;
638 if(temp.getExeTime() > time) {
639 temp.setExeTime(time);
646 // create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode
647 ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", fs, ScheduleEdge.TRANSEDGE, 0); //new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
649 sEdge.setSourceCNode(sCNode);
650 sEdge.setTargetCNode(cNode);
651 sEdge.setTargetFState(nfs);
653 // Add calculation codes for calculating transmit time of an object
654 sEdge.setTransTime(cNode.getTransTime());
655 se.getSource().addEdge(sEdge);
656 scheduleEdges.add(sEdge);
657 // remove the ClassNodes and internal ScheduleEdges out of this subtree to the new ScheduleNode
658 ScheduleNode oldSNode = (ScheduleNode)se.getSource();
659 Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
660 Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
661 Vector<ClassNode> rCNodes = new Vector<ClassNode>();
662 rCNodes.addElement(sCNode);
663 if(it_isEdges != null) {
664 while(it_isEdges.hasNext()) {
665 ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
666 if(rCNodes.contains(tse.getSourceCNode())) {
667 if(sCNode == tse.getSourceCNode()) {
668 if ((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
669 tse.setSource(cNode);
670 tse.setSourceCNode(cNode);
675 sNode.getScheduleEdges().addElement(tse);
676 sNode.getClassNodes().addElement(tse.getTargetCNode());
677 rCNodes.addElement(tse.getTargetCNode());
678 oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
679 toremove.addElement(tse);
683 oldSNode.getScheduleEdges().removeAll(toremove);
685 // redirect ScheudleEdges out of this subtree to the new ScheduleNode
686 Iterator it_sEdges = se.getSource().edges();
687 while(it_sEdges.hasNext()) {
688 ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
689 if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
690 if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
691 tse.setSource(sNode);
692 tse.setSourceCNode(cNode);
693 sNode.getEdgeVector().addElement(tse);
698 se.getSource().getEdgeVector().removeAll(toremove);
704 //merge se into its source ScheduleNode
705 ((ScheduleNode)se.getSource()).mergeSEdge(se);
706 scheduleNodes.remove(se.getTarget());
707 scheduleEdges.removeElement(se);
708 // As se has been changed into an internal edge inside a ScheduleNode,
709 // change the source and target of se from original ScheduleNodes into ClassNodes.
710 if(se.getType() == ScheduleEdge.NEWEDGE) {
711 se.setTarget(se.getTargetCNode());
712 se.setSource(se.getSourceCNode());
713 se.getTargetCNode().addEdge(se);
716 handleScheduleEdge(se, true);
718 } catch (Exception e) {
726 public void schedule() throws Exception {
727 if(this.coreNum == -1) {
728 throw new Exception("Error: un-initialized coreNum when doing scheduling.");
731 if(this.scheduleGraphs == null) {
732 this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
735 int reduceNum = this.scheduleNodes.size() - this.coreNum;
737 // Combine some ScheduleNode if necessary
738 // May generate multiple graphs suggesting candidate schedulings
739 if(!(reduceNum > 0)) {
740 // Enough cores, no need to combine any ScheduleNode
741 this.scheduleGraphs.addElement(this.scheduleNodes);
743 String path = "scheduling_" + gid + ".dot";
744 SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
746 // Go through all the Scheudle Nodes, organize them in order of their cid
747 Vector<Vector<ScheduleNode>> sNodeVecs = new Vector<Vector<ScheduleNode>>();
748 for(int i = 0; i < this.scheduleNodes.size(); i++) {
749 ScheduleNode tmpn = this.scheduleNodes.elementAt(i);
750 int index = tmpn.getCid();
751 while(sNodeVecs.size() <= index) {
754 if(sNodeVecs.elementAt(index) == null) {
755 sNodeVecs.setElementAt(new Vector<ScheduleNode>(), index);
757 sNodeVecs.elementAt(index).add(tmpn);
760 CombinationUtil.RootsGenerator rGen = CombinationUtil.allocateRootsGenerator(sNodeVecs, this.coreNum);
763 while(rGen.nextGen()) {
764 // first get the chosen rootNodes
765 Vector<Vector<ScheduleNode>> rootNodes = rGen.getRootNodes();
766 Vector<Vector<ScheduleNode>> nodes2combine = rGen.getNode2Combine();
768 CombinationUtil.CombineGenerator cGen = CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine);
769 while (cGen.nextGen()) {
770 Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
771 Vector<ScheduleNode> sNodes = generateScheduling(rootNodes, combine, gid++);
772 this.scheduleGraphs.add(sNodes);
777 nodes2combine = null;
782 // Generate schedulings according to result schedule graph
783 if(this.schedulings == null) {
784 this.schedulings = new Vector<Vector<Schedule>>();
787 Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
788 Iterator it_tasks = state.getTaskSymbolTable().getDescriptorsIterator();
789 while(it_tasks.hasNext()) {
790 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
791 if(td.numParameters() > 1) {
792 multiparamtds.addElement(td);
796 for(int i = 0; i < this.scheduleGraphs.size(); i++) {
797 Hashtable<TaskDescriptor, Vector<Schedule>> td2cores = new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks reside on which cores
798 Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
799 Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
800 // for each ScheduleNode create a schedule node representing a core
801 Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
803 for(j = 0; j < scheduleGraph.size(); j++) {
804 sn2coreNum.put(scheduleGraph.elementAt(j), j);
807 boolean setstartupcore = false;
808 Schedule startup = null;
809 for(j = 0; j < scheduleGraph.size(); j++) {
810 Schedule tmpSchedule = new Schedule(j);
811 ScheduleNode sn = scheduleGraph.elementAt(j);
813 Vector<ClassNode> cNodes = sn.getClassNodes();
814 for(int k = 0; k < cNodes.size(); k++) {
815 Iterator it_flags = cNodes.elementAt(k).getFlags();
816 while(it_flags.hasNext()) {
817 FlagState fs = (FlagState)it_flags.next();
818 Iterator it_edges = fs.edges();
819 while(it_edges.hasNext()) {
820 TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
821 tmpSchedule.addTask(td);
822 if(!td2cores.containsKey(td)) {
823 td2cores.put(td, new Vector<Schedule>());
825 Vector<Schedule> tmpcores = td2cores.get(td);
826 if(!tmpcores.contains(tmpSchedule)) {
827 tmpcores.add(tmpSchedule);
829 // if the FlagState can be fed to some multi-param tasks,
830 // need to record corresponding ally cores later
831 if(td.numParameters() > 1) {
832 tmpSchedule.addFState4TD(td, fs);
834 if(td.getParamType(0).getClassDesc().getSymbol().equals(TypeUtil.StartupClass)) {
835 assert(!setstartupcore);
837 startup = tmpSchedule;
838 setstartupcore = true;
844 // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
845 Iterator it_edges = sn.edges();
846 while(it_edges.hasNext()) {
847 ScheduleEdge se = (ScheduleEdge)it_edges.next();
848 ScheduleNode target = (ScheduleNode)se.getTarget();
849 Integer targetcore = sn2coreNum.get(target);
850 switch(se.getType()) {
851 case ScheduleEdge.NEWEDGE: {
852 for(int k = 0; k < se.getNewRate(); k++) {
853 tmpSchedule.addTargetCore(se.getFstate(), targetcore);
858 case ScheduleEdge.TRANSEDGE: {
860 tmpSchedule.addTargetCore(se.getFstate(), targetcore, se.getTargetFState());
861 // check if missed some FlagState associated with some multi-parameter
862 // task, which has been cloned when splitting a ClassNode
863 FlagState fs = se.getSourceFState();
864 FlagState tfs = se.getTargetFState();
865 Iterator it = tfs.edges();
866 while(it.hasNext()) {
867 TaskDescriptor td = ((FEdge)it.next()).getTask();
868 if(td.numParameters() > 1) {
869 if(tmpSchedule.getTasks().contains(td)) {
870 tmpSchedule.addFState4TD(td, fs);
878 it_edges = sn.getScheduleEdgesIterator();
879 while(it_edges.hasNext()) {
880 ScheduleEdge se = (ScheduleEdge)it_edges.next();
881 switch(se.getType()) {
882 case ScheduleEdge.NEWEDGE: {
883 for(int k = 0; k < se.getNewRate(); k++) {
884 tmpSchedule.addTargetCore(se.getFstate(), j);
889 case ScheduleEdge.TRANSEDGE: {
891 tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState());
896 scheduling.add(tmpSchedule);
899 int number = this.coreNum;
900 if(scheduling.size() < number) {
901 number = scheduling.size();
904 // set up all the associate ally cores
905 if(multiparamtds.size() > 0) {
906 for(j = 0; j < multiparamtds.size(); ++j) {
907 TaskDescriptor td = multiparamtds.elementAt(j);
908 Vector<FEdge> fes = (Vector<FEdge>) this.taskanalysis.getFEdgesFromTD(td);
909 Vector<Schedule> cores = td2cores.get(td);
910 for(int k = 0; k < cores.size(); ++k) {
911 Schedule tmpSchedule = cores.elementAt(k);
913 for(int h = 0; h < fes.size(); ++h) {
914 FEdge tmpfe = fes.elementAt(h);
915 FlagState tmpfs = (FlagState)tmpfe.getTarget();
916 Vector<TaskDescriptor> tmptds = new Vector<TaskDescriptor>();
917 if((tmpSchedule.getTargetCoreTable() == null) || (!tmpSchedule.getTargetCoreTable().contains(tmpfs))) {
918 // add up all possible cores' info
919 Iterator it_edges = tmpfs.edges();
920 while(it_edges.hasNext()) {
921 TaskDescriptor tmptd = ((FEdge)it_edges.next()).getTask();
922 if(!tmptds.contains(tmptd)) {
924 Vector<Schedule> tmpcores = td2cores.get(tmptd);
925 for(int m = 0; m < tmpcores.size(); ++m) {
926 if(m != tmpSchedule.getCoreNum()) {
927 // if the FlagState can be fed to some multi-param tasks,
928 // need to record corresponding ally cores later
929 if(tmptd.numParameters() > 1) {
930 tmpSchedule.addAllyCore(tmpfs, tmpcores.elementAt(m).getCoreNum());
932 tmpSchedule.addTargetCore(tmpfs, tmpcores.elementAt(m).getCoreNum());
941 if(cores.size() > 1) {
942 Vector<FlagState> tmpfss = tmpSchedule.getFStates4TD(td);
943 for(int h = 0; h < tmpfss.size(); ++h) {
944 for(int l = 0; l < cores.size(); ++l) {
946 tmpSchedule.addAllyCore(tmpfss.elementAt(h), cores.elementAt(l).getCoreNum());
955 this.schedulings.add(scheduling);
959 public Vector<ScheduleNode> generateScheduling(Vector<Vector<ScheduleNode>> rootnodes, Vector<Vector<CombinationUtil.Combine>> combine, int gid) {
960 Vector<ScheduleNode> result = new Vector<ScheduleNode>();
962 // clone the ScheduleNodes
963 Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
964 Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
965 for(int i = 0; i < this.scheduleNodes.size(); i++) {
966 Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
967 ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
968 ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
970 sn2hash.put(temp, cn2cn);
971 sn2sn.put(tocopy, temp);
974 // clone the ScheduleEdges
975 for(int i = 0; i < this.scheduleEdges.size(); i++) {
976 ScheduleEdge sse = this.scheduleEdges.elementAt(i);
977 ScheduleNode csource = sn2sn.get(sse.getSource());
978 ScheduleNode ctarget = sn2sn.get(sse.getTarget());
979 Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
980 Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
981 ScheduleEdge se = null;
982 switch(sse.getType()) {
983 case ScheduleEdge.NEWEDGE: {
984 se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid); //new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
985 se.setProbability(sse.getProbability());
986 se.setNewRate(sse.getNewRate());
990 case ScheduleEdge.TRANSEDGE: {
991 se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid); //new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
995 se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
996 se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
997 se.setFEdge(sse.getFEdge());
998 se.setTargetFState(sse.getTargetFState());
1000 csource.addEdge(se);
1005 // combine those nodes in combine with corresponding rootnodes
1006 for(int i = 0; i < combine.size(); i++) {
1007 if(combine.elementAt(i) != null) {
1008 for(int j = 0; j < combine.elementAt(i).size(); j++) {
1009 CombinationUtil.Combine tmpcombine = combine.elementAt(i).elementAt(j);
1010 ScheduleNode tocombine = sn2sn.get(tmpcombine.node);
1011 ScheduleNode root = sn2sn.get(rootnodes.elementAt(tmpcombine.root).elementAt(tmpcombine.index));
1012 ScheduleEdge se = (ScheduleEdge)tocombine.inedges().next();
1014 if(root.equals(((ScheduleNode)se.getSource()))) {
1015 root.mergeSEdge(se);
1016 if(ScheduleEdge.NEWEDGE == se.getType()) {
1017 // As se has been changed into an internal edge inside a ScheduleNode,
1018 // change the source and target of se from original ScheduleNodes into ClassNodes.
1019 se.setTarget(se.getTargetCNode());
1020 se.setSource(se.getSourceCNode());
1021 se.getTargetCNode().addEdge(se);
1024 root.mergeSNode(tocombine);
1026 } catch(Exception e) {
1027 e.printStackTrace();
1030 result.removeElement(tocombine);
1038 String path = "scheduling_" + gid + ".dot";
1039 SchedulingUtil.printScheduleGraph(path, result);