1 package Analysis.Scheduling;
3 import Analysis.TaskStateAnalysis.*;
6 import Util.GraphNode.SCC;
8 import java.io.FileInputStream;
11 /** This class holds flag transition diagram(s) can be put on one core.
13 public class ScheduleAnalysis {
16 TaskAnalysis taskanalysis;
18 Vector<ScheduleNode> scheduleNodes;
19 Vector<ClassNode> classNodes;
20 Vector<ScheduleEdge> scheduleEdges;
21 Hashtable<ClassDescriptor, ClassNode> cd2ClassNode;
22 boolean sorted = false;
26 int scheduleThreshold;
28 Vector<Vector<ScheduleNode>> scheduleGraphs;
30 // Main CD table for multi-param tasks
31 Hashtable<TaskDescriptor, ClassDescriptor> td2maincd;
33 public ScheduleAnalysis(State state,
34 TaskAnalysis taskanalysis) {
36 this.taskanalysis = taskanalysis;
37 this.scheduleNodes = new Vector<ScheduleNode>();
38 this.classNodes = new Vector<ClassNode>();
39 this.scheduleEdges = new Vector<ScheduleEdge>();
40 this.cd2ClassNode = new Hashtable<ClassDescriptor, ClassNode>();
41 this.transThreshold = 45; // defaultly 45
42 this.scheduleThreshold = 1000; // defaultly 1000
44 this.scheduleGraphs = null;
45 this.td2maincd = null;
48 public void setTransThreshold(int tt) {
49 this.transThreshold = tt;
52 public void setScheduleThreshold(int stt) {
53 this.scheduleThreshold = stt;
56 public int getCoreNum() {
60 public void setCoreNum(int coreNum) {
61 this.coreNum = coreNum;
64 public Vector<Vector<ScheduleNode>> getScheduleGraphs() {
65 return this.scheduleGraphs;
69 public Vector<ScheduleEdge> getSEdges4Test() {
73 public Hashtable<TaskDescriptor, ClassDescriptor> getTd2maincd() {
77 public boolean schedule(int generateThreshold,
78 Vector<TaskDescriptor> multiparamtds) {
79 boolean tooptimize = true;
81 Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
82 ScheduleNode startupNode = null;
84 if((multiparamtds != null) || (multiparamtds.size() > 0)) {
85 this.td2maincd = new Hashtable<TaskDescriptor, ClassDescriptor>();
88 // necessary preparation such as read profile info etc.
91 startupNode = buildCFSTG(toBreakDown, multiparamtds);
93 treeTransform(toBreakDown, startupNode);
94 // do CFSTG transform to explore the potential parallelism as much
97 // mappint to real multi-core processor
98 tooptimize = coreMapping(generateThreshold);
100 } catch (Exception e) {
107 private void preSchedule() {
108 this.checkBackEdge();
110 // set up profiling data
111 if(state.USEPROFILE) {
112 java.util.Hashtable<String, TaskInfo> taskinfos =
113 new java.util.Hashtable<String, TaskInfo>();
114 this.readProfileInfo(taskinfos);
117 Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator();
118 while(it_classes.hasNext()) {
119 ClassDescriptor cd = (ClassDescriptor) it_classes.next();
121 Vector rootnodes = this.taskanalysis.getRootNodes(cd);
122 if(rootnodes!=null) {
123 Iterator it_rootnodes = rootnodes.iterator();
124 while(it_rootnodes.hasNext()) {
125 FlagState root = (FlagState)it_rootnodes.next();
126 Vector allocatingTasks = root.getAllocatingTasks();
127 if(allocatingTasks != null) {
128 for(int k = 0; k < allocatingTasks.size(); k++) {
130 (TaskDescriptor)allocatingTasks.elementAt(k);
131 Vector<FEdge> fev = this.taskanalysis.getFEdgesFromTD(td);
132 int numEdges = fev.size();
133 for(int j = 0; j < numEdges; j++) {
134 FEdge pfe = fev.elementAt(j);
135 TaskInfo taskinfo = taskinfos.get(td.getSymbol());
136 tint = taskinfo.m_exetime[pfe.getTaskExitIndex()];
137 pfe.setExeTime(tint);
139 taskinfo.m_probability[pfe.getTaskExitIndex()];
140 pfe.setProbability(idouble);
142 int tindex = pfe.getTaskExitIndex();
143 if((taskinfo.m_newobjinfo.elementAt(tindex) != null)
144 && (taskinfo.m_newobjinfo.elementAt(tindex).containsKey(
146 newRate = taskinfo.m_newobjinfo.elementAt(tindex).get(
149 pfe.addNewObjInfo(cd, newRate, idouble);
150 if(taskinfo.m_byObj != -1) {
151 ((FlagState)pfe.getSource()).setByObj(taskinfo.m_byObj);
160 Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator();
161 while(it_flags.hasNext()) {
162 FlagState fs = (FlagState)it_flags.next();
163 Iterator it_edges = fs.edges();
164 while(it_edges.hasNext()) {
165 FEdge edge = (FEdge)it_edges.next();
166 TaskInfo taskinfo = taskinfos.get(edge.getTask().getSymbol());
167 tint = taskinfo.m_exetime[edge.getTaskExitIndex()];
168 edge.setExeTime(tint);
169 double idouble = taskinfo.m_probability[edge.getTaskExitIndex()];
170 edge.setProbability(idouble);
171 if(taskinfo.m_byObj != -1) {
172 ((FlagState)edge.getSource()).setByObj(taskinfo.m_byObj);
183 randomProfileSetting();
187 private void checkBackEdge() {
188 // Indentify backedges
189 Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();
190 while(it_classes.hasNext()) {
191 ClassDescriptor cd=(ClassDescriptor) it_classes.next();
193 Set<FlagState> fss = this.taskanalysis.getFlagStates(cd);
194 SCC scc=GraphNode.DFS.computeSCC(fss);
195 if (scc.hasCycles()) {
196 for(int i=0; i<scc.numSCC(); i++) {
197 if (scc.hasCycle(i)) {
198 Set cycleset = scc.getSCC(i);
199 Iterator it_fs = cycleset.iterator();
200 while(it_fs.hasNext()) {
201 FlagState fs = (FlagState)it_fs.next();
202 Iterator it_edges = fs.edges();
203 while(it_edges.hasNext()) {
204 FEdge edge = (FEdge)it_edges.next();
205 if(cycleset.contains(edge.getTarget())) {
207 edge.setisbackedge(true);
222 private void readProfileInfo(java.util.Hashtable<String, TaskInfo> taskinfos){
224 // read in profile data and set
225 //FileInputStream inStream = new FileInputStream("/scratch/profile.rst");
226 FileInputStream inStream =
227 new FileInputStream("/scratch/" + this.state.profilename);
228 byte[] b = new byte[1024 * 100];
229 int length = inStream.read(b);
231 System.out.print("No content in input file: /scratch/"
232 + this.state.profilename + "\n");
235 String profiledata = new String(b, 0, length);
237 // profile data format:
238 // taskname, numoftaskexits(; exetime, probability, numofnewobjtypes(,
239 // newobj type, num of objs)+)+
240 int inindex = profiledata.indexOf('\n');
241 while((inindex != -1) ) {
242 String inline = profiledata.substring(0, inindex);
243 profiledata = profiledata.substring(inindex + 1);
244 //System.printString(inline + "\n");
245 int tmpinindex = inline.indexOf(',');
246 if(tmpinindex == -1) {
249 String inname = inline.substring(0, tmpinindex);
250 String inint = inline.substring(tmpinindex + 1);
251 while(inint.startsWith(" ")) {
252 inint = inint.substring(1);
254 tmpinindex = inint.indexOf(',');
255 if(tmpinindex == -1) {
258 int numofexits = Integer.parseInt(inint.substring(0, tmpinindex));
259 TaskInfo tinfo = new TaskInfo(numofexits);
260 inint = inint.substring(tmpinindex + 1);
261 while(inint.startsWith(" ")) {
262 inint = inint.substring(1);
264 tmpinindex = inint.indexOf(';');
265 int byObj = Integer.parseInt(inint.substring(0, tmpinindex));
267 tinfo.m_byObj = byObj;
269 inint = inint.substring(tmpinindex + 1);
270 while(inint.startsWith(" ")) {
271 inint = inint.substring(1);
273 for(int i = 0; i < numofexits; i++) {
274 String tmpinfo = null;
275 if(i < numofexits - 1) {
276 tmpinindex = inint.indexOf(';');
277 tmpinfo = inint.substring(0, tmpinindex);
278 inint = inint.substring(tmpinindex + 1);
279 while(inint.startsWith(" ")) {
280 inint = inint.substring(1);
286 tmpinindex = tmpinfo.indexOf(',');
287 tinfo.m_exetime[i] = Long.parseLong(tmpinfo.substring(0, tmpinindex));
288 tmpinfo = tmpinfo.substring(tmpinindex + 1);
289 while(tmpinfo.startsWith(" ")) {
290 tmpinfo = tmpinfo.substring(1);
292 tmpinindex = tmpinfo.indexOf(',');
293 tinfo.m_probability[i] = Double.parseDouble(
294 tmpinfo.substring(0,tmpinindex));
295 tmpinfo = tmpinfo.substring(tmpinindex + 1);
296 while(tmpinfo.startsWith(" ")) {
297 tmpinfo = tmpinfo.substring(1);
299 tmpinindex = tmpinfo.indexOf(',');
301 if(tmpinindex == -1) {
302 numofnobjs = Integer.parseInt(tmpinfo);
303 if(numofnobjs != 0) {
304 System.err.println("Error profile data format!");
308 tinfo.m_newobjinfo.setElementAt(new Hashtable<String,Integer>(), i);
309 numofnobjs = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
310 tmpinfo = tmpinfo.substring(tmpinindex + 1);
311 while(tmpinfo.startsWith(" ")) {
312 tmpinfo = tmpinfo.substring(1);
314 for(int j = 0; j < numofnobjs; j++) {
315 tmpinindex = tmpinfo.indexOf(',');
316 String nobjtype = tmpinfo.substring(0, tmpinindex);
317 tmpinfo = tmpinfo.substring(tmpinindex + 1);
318 while(tmpinfo.startsWith(" ")) {
319 tmpinfo = tmpinfo.substring(1);
322 if(j < numofnobjs - 1) {
323 tmpinindex = tmpinfo.indexOf(',');
324 objnum = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
325 tmpinfo = tmpinfo.substring(tmpinindex + 1);
326 while(tmpinfo.startsWith(" ")) {
327 tmpinfo = tmpinfo.substring(1);
330 objnum = Integer.parseInt(tmpinfo);
332 tinfo.m_newobjinfo.elementAt(i).put(nobjtype, objnum);
336 taskinfos.put(inname, tinfo);
337 inindex = profiledata.indexOf('\n');
342 } catch(Exception e) {
348 private void randomProfileSetting() {
349 // Randomly set the newRate and probability of FEdges
350 java.util.Random r=new java.util.Random();
352 Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();
353 for(; it_classes.hasNext();) {
354 ClassDescriptor cd=(ClassDescriptor) it_classes.next();
356 Vector rootnodes=this.taskanalysis.getRootNodes(cd);
357 if(rootnodes!=null) {
358 Iterator it_rootnodes=rootnodes.iterator();
359 for(; it_rootnodes.hasNext();) {
360 FlagState root=(FlagState)it_rootnodes.next();
361 Vector allocatingTasks = root.getAllocatingTasks();
362 if(allocatingTasks != null) {
363 for(int k = 0; k < allocatingTasks.size(); k++) {
364 TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
366 (Vector<FEdge>)this.taskanalysis.getFEdgesFromTD(td);
367 int numEdges = fev.size();
369 for(int j = 0; j < numEdges; j++) {
370 FEdge pfe = fev.elementAt(j);
371 if(numEdges - j == 1) {
372 pfe.setProbability(total);
374 if((total != 0) && (total != 1)) {
376 tint = r.nextInt()%total;
379 pfe.setProbability(tint);
383 // tint = r.nextInt()%10;
384 // } while(tint <= 0);
385 //int newRate = tint;
386 //int newRate = (j+1)%2+1;
388 String cdname = cd.getSymbol();
389 if((cdname.equals("SeriesRunner")) ||
390 (cdname.equals("MDRunner")) ||
391 (cdname.equals("Stage")) ||
392 (cdname.equals("AppDemoRunner")) ||
393 (cdname.equals("FilterBankAtom")) ||
394 (cdname.equals("Grid")) ||
395 (cdname.equals("Fractal")) ||
396 (cdname.equals("KMeans")) ||
397 (cdname.equals("ZTransform")) ||
398 (cdname.equals("TestRunner")) ||
399 (cdname.equals("LinkList"))) {
400 newRate = this.coreNum;
401 } else if(cdname.equals("SentenceParser")) {
405 // tint = r.nextInt()%100;
406 // } while(tint <= 0);
407 // int probability = tint;
408 int probability = 100;
409 pfe.addNewObjInfo(cd, newRate, probability);
418 Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator();
419 while(it_flags.hasNext()) {
420 FlagState fs = (FlagState)it_flags.next();
421 Iterator it_edges = fs.edges();
423 while(it_edges.hasNext()) {
425 // tint = r.nextInt()%10;
426 // } while(tint <= 0);
428 FEdge edge = (FEdge)it_edges.next();
429 edge.setExeTime(tint);
430 if((fs.getClassDescriptor().getSymbol().equals("MD"))
431 && (edge.getTask().getSymbol().equals("t6"))) {
432 if(edge.isbackedge()) {
433 if(edge.getTarget().equals(edge.getSource())) {
434 edge.setProbability(93.75);
436 edge.setProbability(3.125);
439 edge.setProbability(3.125);
443 if(!it_edges.hasNext()) {
444 edge.setProbability(total);
446 if((total != 0) && (total != 1)) {
448 tint = r.nextInt()%total;
451 edge.setProbability(tint);
463 private ScheduleNode buildCFSTG(Vector<ScheduleEdge> toBreakDown,
464 Vector<TaskDescriptor> multiparamtds) {
465 Hashtable<ClassDescriptor, ClassNode> cdToCNodes =
466 new Hashtable<ClassDescriptor, ClassNode>();
467 // Build the combined flag transition diagram
468 // First, for each class create a ClassNode
469 Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator();
470 while(it_classes.hasNext()) {
471 ClassDescriptor cd = (ClassDescriptor) it_classes.next();
472 Set<FlagState> fStates = taskanalysis.getFlagStates(cd);
474 //Sort flagState nodes inside this ClassNode
475 Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
477 Vector rootnodes = taskanalysis.getRootNodes(cd);
478 if(((rootnodes != null) && (rootnodes.size() > 0))
479 || (cd.getSymbol().equals(TypeUtil.StartupClass))) {
480 ClassNode cNode = new ClassNode(cd, sFStates);
481 cNode.setSorted(true);
482 classNodes.add(cNode);
483 cd2ClassNode.put(cd, cNode);
484 cdToCNodes.put(cd, cNode);
493 ScheduleNode startupNode = null;
494 // For each ClassNode create a ScheduleNode containing it
496 for(i = 0; i < classNodes.size(); i++) {
497 ClassNode cn = classNodes.elementAt(i);
498 ScheduleNode sn = new ScheduleNode(cn, 0);
499 if(cn.getClassDescriptor().getSymbol().equals(TypeUtil.StartupClass)) {
502 cn.setScheduleNode(sn);
503 scheduleNodes.add(sn);
506 } catch (Exception e) {
511 // Create 'new' edges between the ScheduleNodes.
512 Vector<ClassDescriptor> singleCDs = new Vector<ClassDescriptor>();
513 for(i = 0; i < classNodes.size(); i++) {
514 ClassNode cNode = classNodes.elementAt(i);
515 ClassDescriptor cd = cNode.getClassDescriptor();
516 Vector rootnodes = taskanalysis.getRootNodes(cd);
517 boolean isSingle = false;
518 if(rootnodes != null) {
519 for(int h = 0; h < rootnodes.size(); h++) {
520 FlagState root=(FlagState)rootnodes.elementAt(h);
521 Vector allocatingTasks = root.getAllocatingTasks();
522 if(allocatingTasks != null) {
523 for(int k = 0; k < allocatingTasks.size(); k++) {
524 TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
526 (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
527 int numEdges = fev.size();
528 ScheduleNode sNode = cNode.getScheduleNode();
529 for(int j = 0; j < numEdges; j++) {
530 FEdge pfe = fev.elementAt(j);
531 FEdge.NewObjInfo noi = pfe.getNewObjInfo(cd);
532 if ((noi == null) || (noi.getNewRate() == 0)
533 || (noi.getProbability() == 0)) {
534 // fake creating edge, do not need to create corresponding
538 if(noi.getNewRate() == 1) {
541 if(noi.getRoot() == null) {
542 // set root FlagState
545 FlagState pfs = (FlagState)pfe.getTarget();
546 ClassDescriptor pcd = pfs.getClassDescriptor();
547 ClassNode pcNode = cdToCNodes.get(pcd);
549 ScheduleEdge sEdge = new ScheduleEdge(sNode,
552 ScheduleEdge.NEWEDGE,
555 sEdge.setSourceCNode(pcNode);
556 sEdge.setTargetCNode(cNode);
557 sEdge.setTargetFState(root);
558 sEdge.setNewRate(noi.getNewRate());
559 sEdge.setProbability(noi.getProbability());
560 pcNode.getScheduleNode().addEdge(sEdge);
561 scheduleEdges.add(sEdge);
562 if((j !=0 ) || (k != 0) || (h != 0)) {
563 toBreakDown.add(sEdge);
568 allocatingTasks = null;
579 for(i = 0; i < multiparamtds.size(); i++) {
580 TaskDescriptor td = multiparamtds.elementAt(i);
581 for(int j = 0; j < td.numParameters(); j++) {
582 ClassDescriptor cd = td.getParamType(j).getClassDesc();
583 if(singleCDs.contains(cd)) {
584 // set the first parameter which has single creation rate as main cd
585 // TODO: may have bug when cd has multiple new flag states
586 this.td2maincd.put(td, cd);
595 private void treeTransform(Vector<ScheduleEdge> toBreakDown,
596 ScheduleNode startupNode) {
599 // Break down the 'cycle's
601 for(i = 0; i < toBreakDown.size(); i++ ) {
602 cloneSNodeList(toBreakDown.elementAt(i), false);
604 } catch (Exception e) {
609 // Remove fake 'new' edges
610 for(i = 0; i < scheduleEdges.size(); i++) {
611 ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i);
612 if((0 == se.getNewRate()) || (0 == se.getProbability())) {
613 scheduleEdges.removeElement(se);
614 scheduleNodes.removeElement(se.getTarget());
618 // Do topology sort of the ClassNodes and ScheduleEdges.
619 Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
620 Vector<ScheduleNode> tempSNodes =
621 ClassNode.DFS.topology(scheduleNodes, ssev);
622 scheduleNodes.removeAllElements();
623 scheduleNodes = tempSNodes;
625 scheduleEdges.removeAllElements();
626 scheduleEdges = ssev;
630 // Set the cid of these ScheduleNode
631 Queue<ScheduleNode> toVisit = new LinkedList<ScheduleNode>();
632 toVisit.add(startupNode);
633 while(!toVisit.isEmpty()) {
634 ScheduleNode sn = toVisit.poll();
635 if(sn.getCid() == -1) {
636 // not visited before
637 sn.setCid(ScheduleNode.colorID++);
638 Iterator it_edge = sn.edges();
639 while(it_edge.hasNext()) {
640 toVisit.add((ScheduleNode)((ScheduleEdge)it_edge.next()).getTarget());
647 if(this.state.PRINTSCHEDULING) {
648 SchedulingUtil.printScheduleGraph(
649 this.state.outputdir + "scheduling_ori.dot", this.scheduleNodes);
653 private void CFSTGTransform() {
656 //Access the ScheduleEdges in reverse topology order
657 Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses =
658 new Hashtable<FEdge, Vector<ScheduleEdge>>();
659 Hashtable<ScheduleNode, Vector<FEdge>> sn2fes =
660 new Hashtable<ScheduleNode, Vector<FEdge>>();
661 ScheduleNode preSNode = null;
662 for(i = scheduleEdges.size(); i > 0; i--) {
663 ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i-1);
664 if(ScheduleEdge.NEWEDGE == se.getType()) {
665 if(preSNode == null) {
666 preSNode = (ScheduleNode)se.getSource();
669 boolean split = false;
670 FEdge fe = se.getFEdge();
671 if(fe.getSource() == fe.getTarget()) {
674 int repeat = (int)Math.ceil(se.getNewRate()*se.getProbability()/100);
677 for(int j = 1; j< repeat; j++ ) {
678 cloneSNodeList(se, true);
681 se.setProbability(100);
684 rate = (int)Math.ceil(
685 se.getListExeTime()/calInExeTime(se.getSourceFState()));
686 } catch (Exception e) {
689 for(int j = rate - 1; j > 0; j--) {
690 for(int k = repeat; k > 0; k--) {
691 cloneSNodeList(se, true);
694 } catch (Exception e) {
699 // if preSNode is not the same as se's source ScheduleNode
700 // handle any ScheduleEdges previously put into fe2ses whose source
701 // ScheduleNode is preSNode
702 boolean same = (preSNode == se.getSource());
704 // check the topology sort, only process those after se.getSource()
705 if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()){
706 if(sn2fes.containsKey(preSNode)) {
707 Vector<FEdge> fes = sn2fes.remove(preSNode);
708 for(int j = 0; j < fes.size(); j++) {
709 FEdge tempfe = fes.elementAt(j);
710 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
711 ScheduleEdge tempse = ses.elementAt(0);
712 long temptime = tempse.getListExeTime();
713 // find out the ScheduleEdge with least exeTime
714 for(int k = 1; k < ses.size(); k++) {
715 long ttemp = ses.elementAt(k).getListExeTime();
716 if(ttemp < temptime) {
717 tempse = ses.elementAt(k);
722 handleScheduleEdge(tempse, true);
723 ses.removeElement(tempse);
724 // handle other ScheduleEdges
725 for(int k = 0; k < ses.size(); k++) {
726 handleScheduleEdge(ses.elementAt(k), false);
729 fe2ses.remove(tempfe);
734 preSNode = (ScheduleNode)se.getSource();
737 // if fe is the last task inside this ClassNode, delay the expanding
738 // and merging until we find all such 'new' edges
739 // associated with a last task inside this ClassNode
740 if(!fe.getTarget().edges().hasNext()) {
741 if(fe2ses.get(fe) == null) {
742 fe2ses.put(fe, new Vector<ScheduleEdge>());
744 if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
745 sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
747 if(!fe2ses.get(fe).contains(se)) {
748 fe2ses.get(fe).add(se);
750 if(!sn2fes.get((ScheduleNode)se.getSource()).contains(fe)) {
751 sn2fes.get((ScheduleNode)se.getSource()).add(fe);
754 // As this is not a last task, first handle available ScheduleEdges
755 // previously put into fe2ses
756 if((same) && (sn2fes.containsKey(preSNode))) {
757 Vector<FEdge> fes = sn2fes.remove(preSNode);
758 for(int j = 0; j < fes.size(); j++) {
759 FEdge tempfe = fes.elementAt(j);
760 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
761 ScheduleEdge tempse = ses.elementAt(0);
762 long temptime = tempse.getListExeTime();
763 // find out the ScheduleEdge with least exeTime
764 for(int k = 1; k < ses.size(); k++) {
765 long ttemp = ses.elementAt(k).getListExeTime();
766 if(ttemp < temptime) {
767 tempse = ses.elementAt(k);
772 handleScheduleEdge(tempse, true);
773 ses.removeElement(tempse);
774 // handle other ScheduleEdges
775 for(int k = 0; k < ses.size(); k++) {
776 handleScheduleEdge(ses.elementAt(k), false);
779 fe2ses.remove(tempfe);
784 if((!(se.getTransTime() < this.transThreshold))
785 && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
787 splitSNode(se, true);
789 // handle this ScheduleEdge
790 handleScheduleEdge(se, true);
796 if(!fe2ses.isEmpty()) {
797 Set<FEdge> keys = fe2ses.keySet();
798 Iterator it_keys = keys.iterator();
799 while(it_keys.hasNext()) {
800 FEdge tempfe = (FEdge)it_keys.next();
801 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
802 ScheduleEdge tempse = ses.elementAt(0);
803 long temptime = tempse.getListExeTime();
804 // find out the ScheduleEdge with least exeTime
805 for(int k = 1; k < ses.size(); k++) {
806 long ttemp = ses.elementAt(k).getListExeTime();
807 if(ttemp < temptime) {
808 tempse = ses.elementAt(k);
813 handleScheduleEdge(tempse, true);
814 ses.removeElement(tempse);
815 // handle other ScheduleEdges
816 for(int k = 0; k < ses.size(); k++) {
817 handleScheduleEdge(ses.elementAt(k), false);
829 if(this.state.PRINTSCHEDULING) {
830 SchedulingUtil.printScheduleGraph(
831 this.state.outputdir + "scheduling_extend.dot", this.scheduleNodes);
835 private void handleScheduleEdge(ScheduleEdge se,
839 int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
842 if(se.getListExeTime() == 0) {
845 rate = (int)Math.ceil(
846 (se.getTransTime()-calInExeTime(se.getSourceFState()))
847 /se.getListExeTime());
852 } catch (Exception e) {
856 // clone the whole ScheduleNode lists starting with se's target
857 for(int j = 1; j < repeat; j++ ) {
858 cloneSNodeList(se, true);
861 se.setProbability(100);
865 // clone the whole ScheduleNode lists starting with se's target
866 for(int j = 0; j < repeat; j++ ) {
867 cloneSNodeList(se, true);
870 se.setProbability(100);
873 // merge the original ScheduleNode to the source ScheduleNode
874 ((ScheduleNode)se.getSource()).mergeSEdge(se);
875 scheduleNodes.remove(se.getTarget());
876 scheduleEdges.remove(se);
877 // As se has been changed into an internal edge inside a ScheduleNode,
878 // change the source and target of se from original ScheduleNodes
880 if(se.getType() == ScheduleEdge.NEWEDGE) {
881 se.setTarget(se.getTargetCNode());
882 //se.setSource(se.getSourceCNode());
883 //se.getTargetCNode().addEdge(se);
884 se.getSourceCNode().addEdge(se);
887 // clone the whole ScheduleNode lists starting with se's target
888 for(int j = 1; j < repeat; j++ ) {
889 cloneSNodeList(se, true);
892 se.setProbability(100);
894 } catch (Exception e) {
900 private void cloneSNodeList(ScheduleEdge sEdge,
901 boolean copyIE) throws Exception {
902 Hashtable<ClassNode, ClassNode> cn2cn =
903 new Hashtable<ClassNode, ClassNode>(); // hashtable from classnode in
904 // orignal se's targe to cloned one
905 ScheduleNode csNode =
906 (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
907 scheduleNodes.add(csNode);
909 // Clone all the external in ScheduleEdges
912 Vector inedges = sEdge.getTarget().getInedgeVector();
913 for(i = 0; i < inedges.size(); i++) {
914 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
916 switch(tse.getType()) {
917 case ScheduleEdge.NEWEDGE: {
918 se = new ScheduleEdge(csNode,"new",tse.getFstate(),tse.getType(),0);
919 se.setProbability(100);
924 case ScheduleEdge.TRANSEDGE: {
925 se = new ScheduleEdge(csNode,"transmit",tse.getFstate(),tse.getType(),0);
926 se.setProbability(tse.getProbability());
927 se.setNewRate(tse.getNewRate());
932 throw new Exception("Error: not valid ScheduleEdge here");
935 se.setSourceCNode(tse.getSourceCNode());
936 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
937 se.setFEdge(tse.getFEdge());
938 se.setTargetFState(tse.getTargetFState());
940 tse.getSource().addEdge(se);
941 scheduleEdges.add(se);
945 sEdge.getTarget().removeInedge(sEdge);
946 sEdge.setTarget(csNode);
947 csNode.getInedgeVector().add(sEdge);
948 sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
949 sEdge.setIsclone(true);
952 Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>(); // all nodes to be cloned
953 Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>(); //clone nodes
954 Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>(); // queue of the mappings of classnodes inside cloned ScheduleNode
955 Vector<ScheduleNode> origins = new Vector<ScheduleNode>(); // queue of source ScheduleNode cloned
956 Hashtable<ScheduleNode, ScheduleNode> sn2sn =
957 new Hashtable<ScheduleNode, ScheduleNode>(); // mapping from cloned ScheduleNode to clone ScheduleNode
959 toClone.add((ScheduleNode)sEdge.getTarget());
960 origins.addElement((ScheduleNode)sEdge.getTarget());
961 sn2sn.put((ScheduleNode)sEdge.getTarget(), csNode);
963 while(!toClone.isEmpty()) {
964 Hashtable<ClassNode, ClassNode> tocn2cn =
965 new Hashtable<ClassNode, ClassNode>();
966 csNode = clone.poll();
967 ScheduleNode osNode = toClone.poll();
968 cn2cn = qcn2cn.poll();
969 // Clone all the external ScheduleEdges and the following ScheduleNodes
970 Vector edges = osNode.getEdgeVector();
971 for(i = 0; i < edges.size(); i++) {
972 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
973 ScheduleNode tSNode =
974 (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
975 scheduleNodes.add(tSNode);
977 toClone.add((ScheduleNode)tse.getTarget());
978 origins.addElement((ScheduleNode)tse.getTarget());
979 sn2sn.put((ScheduleNode)tse.getTarget(), tSNode);
981 ScheduleEdge se = null;
982 switch(tse.getType()) {
983 case ScheduleEdge.NEWEDGE: {
984 se = new ScheduleEdge(tSNode,"new",tse.getFstate(),tse.getType(),0);
988 case ScheduleEdge.TRANSEDGE: {
989 se = new ScheduleEdge(tSNode,"transmit",tse.getFstate(),tse.getType(),0);
994 throw new Exception("Error: not valid ScheduleEdge here");
997 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
998 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
999 se.setFEdge(tse.getFEdge());
1000 se.setTargetFState(tse.getTargetFState());
1001 se.setProbability(tse.getProbability());
1002 se.setNewRate(tse.getNewRate());
1003 se.setIsclone(true);
1005 scheduleEdges.add(se);
1020 private long calInExeTime(FlagState fs) throws Exception {
1022 ClassDescriptor cd = fs.getClassDescriptor();
1023 ClassNode cNode = cd2ClassNode.get(cd);
1024 exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
1026 Vector inedges = cNode.getInedgeVector();
1027 // Now that there are associate ScheduleEdges, there may be
1028 // multiple inedges of a ClassNode
1029 if(inedges.size() > 1) {
1030 throw new Exception("Error: ClassNode's inedges more than one!");
1032 if(inedges.size() > 0) {
1033 ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
1034 cNode = (ClassNode)sEdge.getSource();
1035 exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
1041 exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
1045 private ScheduleNode splitSNode(ScheduleEdge se,
1047 assert(ScheduleEdge.NEWEDGE == se.getType());
1049 FEdge fe = se.getFEdge();
1050 FlagState fs = (FlagState)fe.getTarget();
1051 FlagState nfs = (FlagState)fs.clone();
1052 fs.getEdgeVector().removeAllElements();
1053 nfs.getInedgeVector().removeAllElements();
1054 ClassNode sCNode = se.getSourceCNode();
1056 // split the subtree whose root is nfs from the whole flag transition tree
1057 Vector<FlagState> sfss = sCNode.getFlagStates();
1058 Vector<FlagState> fStates = new Vector<FlagState>();
1059 Queue<FlagState> toiterate = new LinkedList<FlagState>();
1062 while(!toiterate.isEmpty()) {
1063 FlagState tfs = toiterate.poll();
1064 Iterator it_edges = tfs.edges();
1065 while(it_edges.hasNext()) {
1066 FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
1067 if(!fStates.contains(temp)) {
1069 toiterate.add(temp);
1070 sfss.removeElement(temp);
1076 Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
1078 // create a ClassNode and ScheduleNode for this subtree
1079 ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
1080 ScheduleNode sNode = new ScheduleNode(cNode, 0);
1081 cNode.setScheduleNode(sNode);
1082 cNode.setSorted(true);
1083 cNode.setTransTime(sCNode.getTransTime());
1084 classNodes.add(cNode);
1085 scheduleNodes.add(sNode);
1088 } catch (Exception e) {
1089 e.printStackTrace();
1091 // flush the exeTime of fs and its ancestors
1094 while(!toiterate.isEmpty()) {
1095 FlagState tfs = toiterate.poll();
1096 long ttime = tfs.getExeTime();
1097 Iterator it_inedges = tfs.inedges();
1098 while(it_inedges.hasNext()) {
1099 FEdge fEdge = (FEdge)it_inedges.next();
1100 FlagState temp = (FlagState)fEdge.getSource();
1101 long time = fEdge.getExeTime() + ttime;
1102 if(temp.getExeTime() > time) {
1103 temp.setExeTime(time);
1104 toiterate.add(temp);
1111 // create a 'trans' ScheudleEdge between this new ScheduleNode and se's
1112 // source ScheduleNode
1113 ScheduleEdge sEdge =
1114 new ScheduleEdge(sNode, "transmit", fs, ScheduleEdge.TRANSEDGE, 0);
1116 sEdge.setSourceCNode(sCNode);
1117 sEdge.setTargetCNode(cNode);
1118 sEdge.setTargetFState(nfs);
1120 // Add calculation codes for calculating transmit time of an object
1121 sEdge.setTransTime(cNode.getTransTime());
1122 se.getSource().addEdge(sEdge);
1123 scheduleEdges.add(sEdge);
1124 // remove the ClassNodes and internal ScheduleEdges out of this subtree
1125 // to the new ScheduleNode
1126 ScheduleNode oldSNode = (ScheduleNode)se.getSource();
1127 Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
1128 Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
1129 Vector<ClassNode> rCNodes = new Vector<ClassNode>();
1130 rCNodes.addElement(sCNode);
1131 if(it_isEdges != null) {
1132 while(it_isEdges.hasNext()) {
1133 ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
1134 if(rCNodes.contains(tse.getSourceCNode())) {
1135 if(sCNode.equals(tse.getSourceCNode())) {
1136 if (!(tse.getSourceFState().equals(fs))
1137 && (sFStates.contains(tse.getSourceFState()))) {
1138 tse.setSource(cNode);
1139 tse.setSourceCNode(cNode);
1144 sNode.getScheduleEdges().addElement(tse);
1145 sNode.getClassNodes().addElement(tse.getTargetCNode());
1146 rCNodes.addElement(tse.getTargetCNode());
1147 oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
1148 toremove.addElement(tse);
1153 oldSNode.getScheduleEdges().removeAll(toremove);
1155 // redirect ScheudleEdges out of this subtree to the new ScheduleNode
1156 Iterator it_sEdges = se.getSource().edges();
1157 while(it_sEdges.hasNext()) {
1158 ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
1159 if(!(tse.equals(se)) && !(tse.equals(sEdge))
1160 && (tse.getSourceCNode().equals(sCNode))) {
1161 if(!(tse.getSourceFState().equals(fs))
1162 && (sFStates.contains(tse.getSourceFState()))) {
1163 tse.setSource(sNode);
1164 tse.setSourceCNode(cNode);
1165 sNode.getEdgeVector().addElement(tse);
1171 se.getSource().getEdgeVector().removeAll(toremove);
1178 //merge se into its source ScheduleNode
1179 sNode.setCid(((ScheduleNode)se.getSource()).getCid());
1180 ((ScheduleNode)se.getSource()).mergeSEdge(se);
1181 scheduleNodes.remove(se.getTarget());
1182 scheduleEdges.removeElement(se);
1183 // As se has been changed into an internal edge inside a ScheduleNode,
1184 // change the source and target of se from original ScheduleNodes
1186 if(se.getType() == ScheduleEdge.NEWEDGE) {
1187 se.setTarget(se.getTargetCNode());
1188 //se.setSource(se.getSourceCNode());
1189 //se.getTargetCNode().addEdge(se);
1190 se.getSourceCNode().addEdge(se);
1193 sNode.setCid(ScheduleNode.colorID++);
1194 handleScheduleEdge(se, true);
1196 } catch (Exception e) {
1197 e.printStackTrace();
1204 // TODO: restrict the number of generated scheduling according to the setted
1205 // scheduleThreshold
1206 private boolean coreMapping(int generateThreshold) throws Exception {
1207 if(this.coreNum == -1) {
1208 throw new Exception("Error: un-initialized coreNum when doing scheduling.");
1211 if(this.scheduleGraphs == null) {
1212 this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
1215 int reduceNum = this.scheduleNodes.size() - this.coreNum;
1217 // Combine some ScheduleNode if necessary
1218 // May generate multiple graphs suggesting candidate schedulings
1219 if(!(reduceNum > 0)) {
1220 // Enough cores, no need to combine any ScheduleNode
1221 this.scheduleGraphs.addElement(this.scheduleNodes);
1223 if(this.state.PRINTSCHEDULING) {
1224 String path = this.state.outputdir + "scheduling_" + gid + ".dot";
1225 SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
1229 SchedulingUtil.assignCids(this.scheduleNodes);
1231 // Go through all the Schedule Nodes, organize them in order of their cid
1232 Vector<Vector<ScheduleNode>> sNodeVecs =
1233 SchedulingUtil.rangeScheduleNodes(this.scheduleNodes);
1235 CombinationUtil.RootsGenerator rGen =
1236 CombinationUtil.allocateRootsGenerator(sNodeVecs,
1240 Random rand = new Random();
1241 boolean isBig = Math.pow(this.coreNum, reduceNum) > 1000;
1242 while((!isBig || (gid <= this.scheduleThreshold)) && (rGen.nextGen())) {
1243 // first get the chosen rootNodes
1244 Vector<Vector<ScheduleNode>> rootNodes = rGen.getRootNodes();
1245 Vector<Vector<ScheduleNode>> nodes2combine = rGen.getNode2Combine();
1247 CombinationUtil.CombineGenerator cGen =
1248 CombinationUtil.allocateCombineGenerator(rootNodes,
1250 while((!isBig || (gid <= this.scheduleThreshold)) && (cGen.nextGen())) {
1251 boolean implement = true;
1253 implement = Math.abs(rand.nextInt()) % 100 > generateThreshold;
1256 Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
1257 Vector<ScheduleNode> sNodes =
1258 SchedulingUtil.generateScheduleGraph(this.state,
1264 this.scheduleGraphs.add(sNodes);
1271 nodes2combine = null;
1279 static class TaskInfo {
1280 public int m_numofexits;
1281 public long[] m_exetime;
1282 public double[] m_probability;
1283 public Vector<Hashtable<String, Integer>> m_newobjinfo;
1286 public TaskInfo(int numofexits) {
1287 this.m_numofexits = numofexits;
1288 this.m_exetime = new long[this.m_numofexits];
1289 this.m_probability = new double[this.m_numofexits];
1290 this.m_newobjinfo = new Vector<Hashtable<String, Integer>>();
1291 for(int i = 0; i < this.m_numofexits; i++) {
1292 this.m_newobjinfo.add(null);