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() {
75 /*Iterator<TaskDescriptor> key = td2maincd.keySet().iterator();
76 while(key.hasNext()) {
77 TaskDescriptor td = key.next();
78 System.err.println(td.getSymbol() + ", maincd: "
79 + this.td2maincd.get(td).getSymbol());
85 public boolean schedule(int generateThreshold,
87 Vector<TaskDescriptor> multiparamtds) {
88 boolean tooptimize = true;
90 Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
91 ScheduleNode startupNode = null;
93 if((multiparamtds != null) || (multiparamtds.size() > 0)) {
94 this.td2maincd = new Hashtable<TaskDescriptor, ClassDescriptor>();
97 // necessary preparation such as read profile info etc.
100 startupNode = buildCFSTG(toBreakDown, multiparamtds);
102 treeTransform(toBreakDown, startupNode);
103 // do CFSTG transform to explore the potential parallelism as much
106 // mappint to real multi-core processor
107 tooptimize = coreMapping(generateThreshold, skipThreshold);
109 } catch (Exception e) {
116 private void preSchedule() {
117 this.checkBackEdge();
119 // set up profiling data
120 if(state.USEPROFILE) {
121 java.util.Hashtable<String, TaskInfo> taskinfos =
122 new java.util.Hashtable<String, TaskInfo>();
123 this.readProfileInfo(taskinfos);
126 Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator();
127 while(it_classes.hasNext()) {
128 ClassDescriptor cd = (ClassDescriptor) it_classes.next();
130 Vector rootnodes = this.taskanalysis.getRootNodes(cd);
131 if(rootnodes!=null) {
132 Iterator it_rootnodes = rootnodes.iterator();
133 while(it_rootnodes.hasNext()) {
134 FlagState root = (FlagState)it_rootnodes.next();
135 Vector allocatingTasks = root.getAllocatingTasks();
136 if(allocatingTasks != null) {
137 for(int k = 0; k < allocatingTasks.size(); k++) {
139 (TaskDescriptor)allocatingTasks.elementAt(k);
140 Vector<FEdge> fev = this.taskanalysis.getFEdgesFromTD(td);
141 int numEdges = fev.size();
142 for(int j = 0; j < numEdges; j++) {
143 FEdge pfe = fev.elementAt(j);
144 TaskInfo taskinfo = taskinfos.get(td.getSymbol());
145 tint = taskinfo.m_exetime[pfe.getTaskExitIndex()];
146 pfe.setExeTime(tint);
148 taskinfo.m_probability[pfe.getTaskExitIndex()];
149 pfe.setProbability(idouble);
151 int tindex = pfe.getTaskExitIndex();
152 if((taskinfo.m_newobjinfo.elementAt(tindex) != null)
153 && (taskinfo.m_newobjinfo.elementAt(tindex).containsKey(
155 newRate = taskinfo.m_newobjinfo.elementAt(tindex).get(
158 pfe.addNewObjInfo(cd, newRate, idouble);
159 if(taskinfo.m_byObj != -1) {
160 ((FlagState)pfe.getSource()).setByObj(taskinfo.m_byObj);
163 /*System.err.println("task " + td.getSymbol() + " exit# " +
164 pfe.getTaskExitIndex() + " exetime: " + pfe.getExeTime()
165 + " prob: " + pfe.getProbability() + "% newobj: "
166 + pfe.getNewObjInfoHashtable().size());*/
174 Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator();
175 while(it_flags.hasNext()) {
176 FlagState fs = (FlagState)it_flags.next();
177 Iterator it_edges = fs.edges();
178 while(it_edges.hasNext()) {
179 FEdge edge = (FEdge)it_edges.next();
180 TaskInfo taskinfo = taskinfos.get(edge.getTask().getSymbol());
181 double idouble = 0.0;
182 if(edge.getTaskExitIndex() >= taskinfo.m_exetime.length) {
185 tint = taskinfo.m_exetime[edge.getTaskExitIndex()];
186 idouble = taskinfo.m_probability[edge.getTaskExitIndex()];
188 edge.setExeTime(tint);
189 edge.setProbability(idouble);
190 if(taskinfo.m_byObj != -1) {
191 ((FlagState)edge.getSource()).setByObj(taskinfo.m_byObj);
194 /*System.err.println("task " + edge.getTask().getSymbol() + " exit# " +
195 edge.getTaskExitIndex() + " exetime: " + edge.getExeTime()
196 + " prob: " + edge.getProbability());*/
206 randomProfileSetting();
210 private void checkBackEdge() {
211 // Indentify backedges
212 Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();
213 while(it_classes.hasNext()) {
214 ClassDescriptor cd=(ClassDescriptor) it_classes.next();
216 Set<FlagState> fss = this.taskanalysis.getFlagStates(cd);
217 SCC scc=GraphNode.DFS.computeSCC(fss);
218 if (scc.hasCycles()) {
219 for(int i=0; i<scc.numSCC(); i++) {
220 if (scc.hasCycle(i)) {
221 Set cycleset = scc.getSCC(i);
222 Iterator it_fs = cycleset.iterator();
223 while(it_fs.hasNext()) {
224 FlagState fs = (FlagState)it_fs.next();
225 Iterator it_edges = fs.edges();
226 while(it_edges.hasNext()) {
227 FEdge edge = (FEdge)it_edges.next();
228 if(cycleset.contains(edge.getTarget())) {
230 edge.setisbackedge(true);
245 private void readProfileInfo(java.util.Hashtable<String, TaskInfo> taskinfos){
247 // read in profile data and set
248 //FileInputStream inStream = new FileInputStream("/scratch/profile.rst");
249 FileInputStream inStream =
250 new FileInputStream(/*"/scratch/" + */this.state.profilename);
251 byte[] b = new byte[1024 * 100];
252 int length = inStream.read(b);
254 System.out.print("No content in input file: /scratch/"
255 + this.state.profilename + "\n");
258 String profiledata = new String(b, 0, length);
260 // profile data format:
261 // taskname, numoftaskexits(; exetime, probability, numofnewobjtypes(,
262 // newobj type, num of objs)+)+
263 int inindex = profiledata.indexOf('\n');
264 while((inindex != -1) ) {
265 String inline = profiledata.substring(0, inindex);
266 profiledata = profiledata.substring(inindex + 1);
267 //System.printString(inline + "\n");
268 int tmpinindex = inline.indexOf(',');
269 if(tmpinindex == -1) {
272 String inname = inline.substring(0, tmpinindex);
273 String inint = inline.substring(tmpinindex + 1);
274 while(inint.startsWith(" ")) {
275 inint = inint.substring(1);
277 tmpinindex = inint.indexOf(',');
278 if(tmpinindex == -1) {
281 int numofexits = Integer.parseInt(inint.substring(0, tmpinindex));
282 TaskInfo tinfo = new TaskInfo(numofexits);
283 inint = inint.substring(tmpinindex + 1);
284 while(inint.startsWith(" ")) {
285 inint = inint.substring(1);
287 tmpinindex = inint.indexOf(';');
288 int byObj = Integer.parseInt(inint.substring(0, tmpinindex));
290 tinfo.m_byObj = byObj;
292 inint = inint.substring(tmpinindex + 1);
293 while(inint.startsWith(" ")) {
294 inint = inint.substring(1);
296 for(int i = 0; i < numofexits; i++) {
297 String tmpinfo = null;
298 if(i < numofexits - 1) {
299 tmpinindex = inint.indexOf(';');
300 tmpinfo = inint.substring(0, tmpinindex);
301 inint = inint.substring(tmpinindex + 1);
302 while(inint.startsWith(" ")) {
303 inint = inint.substring(1);
309 tmpinindex = tmpinfo.indexOf(',');
310 tinfo.m_exetime[i] = Long.parseLong(tmpinfo.substring(0, tmpinindex));
311 tmpinfo = tmpinfo.substring(tmpinindex + 1);
312 while(tmpinfo.startsWith(" ")) {
313 tmpinfo = tmpinfo.substring(1);
315 tmpinindex = tmpinfo.indexOf(',');
316 tinfo.m_probability[i] = Double.parseDouble(
317 tmpinfo.substring(0,tmpinindex));
318 tmpinfo = tmpinfo.substring(tmpinindex + 1);
319 while(tmpinfo.startsWith(" ")) {
320 tmpinfo = tmpinfo.substring(1);
322 tmpinindex = tmpinfo.indexOf(',');
324 if(tmpinindex == -1) {
325 numofnobjs = Integer.parseInt(tmpinfo);
326 if(numofnobjs != 0) {
327 System.err.println("Error profile data format!");
331 tinfo.m_newobjinfo.setElementAt(new Hashtable<String,Integer>(), i);
332 numofnobjs = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
333 tmpinfo = tmpinfo.substring(tmpinindex + 1);
334 while(tmpinfo.startsWith(" ")) {
335 tmpinfo = tmpinfo.substring(1);
337 for(int j = 0; j < numofnobjs; j++) {
338 tmpinindex = tmpinfo.indexOf(',');
339 String nobjtype = tmpinfo.substring(0, tmpinindex);
340 tmpinfo = tmpinfo.substring(tmpinindex + 1);
341 while(tmpinfo.startsWith(" ")) {
342 tmpinfo = tmpinfo.substring(1);
345 if(j < numofnobjs - 1) {
346 tmpinindex = tmpinfo.indexOf(',');
347 objnum = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
348 tmpinfo = tmpinfo.substring(tmpinindex + 1);
349 while(tmpinfo.startsWith(" ")) {
350 tmpinfo = tmpinfo.substring(1);
353 objnum = Integer.parseInt(tmpinfo);
355 tinfo.m_newobjinfo.elementAt(i).put(nobjtype, objnum);
359 taskinfos.put(inname, tinfo);
360 inindex = profiledata.indexOf('\n');
365 } catch(Exception e) {
371 private void randomProfileSetting() {
372 // Randomly set the newRate and probability of FEdges
373 java.util.Random r=new java.util.Random();
375 Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();
376 for(; it_classes.hasNext();) {
377 ClassDescriptor cd=(ClassDescriptor) it_classes.next();
379 Vector rootnodes=this.taskanalysis.getRootNodes(cd);
380 if(rootnodes!=null) {
381 Iterator it_rootnodes=rootnodes.iterator();
382 for(; it_rootnodes.hasNext();) {
383 FlagState root=(FlagState)it_rootnodes.next();
384 Vector allocatingTasks = root.getAllocatingTasks();
385 if(allocatingTasks != null) {
386 for(int k = 0; k < allocatingTasks.size(); k++) {
387 TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
389 (Vector<FEdge>)this.taskanalysis.getFEdgesFromTD(td);
390 int numEdges = fev.size();
392 for(int j = 0; j < numEdges; j++) {
393 FEdge pfe = fev.elementAt(j);
394 if(numEdges - j == 1) {
395 pfe.setProbability(total);
397 if((total != 0) && (total != 1)) {
399 tint = r.nextInt()%total;
402 pfe.setProbability(tint);
406 // tint = r.nextInt()%10;
407 // } while(tint <= 0);
408 //int newRate = tint;
409 //int newRate = (j+1)%2+1;
411 String cdname = cd.getSymbol();
412 if((cdname.equals("SeriesRunner")) ||
413 (cdname.equals("MDRunner")) ||
414 (cdname.equals("Stage")) ||
415 (cdname.equals("AppDemoRunner")) ||
416 (cdname.equals("FilterBankAtom")) ||
417 (cdname.equals("Grid")) ||
418 (cdname.equals("Fractal")) ||
419 (cdname.equals("KMeans")) ||
420 (cdname.equals("ZTransform")) ||
421 (cdname.equals("TestRunner")) ||
422 (cdname.equals("TestRunner2")) ||
423 (cdname.equals("LinkList")) ||
424 (cdname.equals("BHRunner"))) {
425 newRate = this.coreNum;
426 } else if(cdname.equals("SentenceParser")) {
428 } else if(cdname.equals("BlurPiece")){
430 } else if(cdname.equals("ImageX")){
432 } else if(cdname.equals("ImageY")){
436 // tint = r.nextInt()%100;
437 // } while(tint <= 0);
438 // int probability = tint;
439 int probability = 100;
440 pfe.addNewObjInfo(cd, newRate, probability);
449 Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator();
450 while(it_flags.hasNext()) {
451 FlagState fs = (FlagState)it_flags.next();
452 Iterator it_edges = fs.edges();
454 while(it_edges.hasNext()) {
456 // tint = r.nextInt()%10;
457 // } while(tint <= 0);
459 FEdge edge = (FEdge)it_edges.next();
460 edge.setExeTime(tint);
461 if((fs.getClassDescriptor().getSymbol().equals("MD"))
462 && (edge.getTask().getSymbol().equals("t6"))) {
463 if(edge.isbackedge()) {
464 if(edge.getTarget().equals(edge.getSource())) {
465 edge.setProbability(93.75);
467 edge.setProbability(3.125);
470 edge.setProbability(3.125);
474 if(!it_edges.hasNext()) {
475 edge.setProbability(total);
477 if((total != 0) && (total != 1)) {
479 tint = r.nextInt()%total;
482 edge.setProbability(tint);
494 private ScheduleNode buildCFSTG(Vector<ScheduleEdge> toBreakDown,
495 Vector<TaskDescriptor> multiparamtds) {
496 Hashtable<ClassDescriptor, ClassNode> cdToCNodes =
497 new Hashtable<ClassDescriptor, ClassNode>();
498 // Build the combined flag transition diagram
499 // First, for each class create a ClassNode
500 Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator();
501 while(it_classes.hasNext()) {
502 ClassDescriptor cd = (ClassDescriptor) it_classes.next();
503 Set<FlagState> fStates = taskanalysis.getFlagStates(cd);
505 //Sort flagState nodes inside this ClassNode
506 Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
508 Vector rootnodes = taskanalysis.getRootNodes(cd);
509 if(((rootnodes != null) && (rootnodes.size() > 0))
510 || (cd.getSymbol().equals(TypeUtil.StartupClass))) {
511 ClassNode cNode = new ClassNode(cd, sFStates);
512 cNode.setSorted(true);
513 classNodes.add(cNode);
514 cd2ClassNode.put(cd, cNode);
515 cdToCNodes.put(cd, cNode);
524 ScheduleNode startupNode = null;
525 // For each ClassNode create a ScheduleNode containing it
527 for(i = 0; i < classNodes.size(); i++) {
528 ClassNode cn = classNodes.elementAt(i);
529 ScheduleNode sn = new ScheduleNode(cn, 0);
530 if(cn.getClassDescriptor().getSymbol().equals(TypeUtil.StartupClass)) {
533 cn.setScheduleNode(sn);
534 scheduleNodes.add(sn);
537 } catch (Exception e) {
542 // Create 'new' edges between the ScheduleNodes.
543 for(i = 0; i < classNodes.size(); i++) {
544 ClassNode cNode = classNodes.elementAt(i);
545 ClassDescriptor cd = cNode.getClassDescriptor();
546 Vector rootnodes = taskanalysis.getRootNodes(cd);
547 if(rootnodes != null) {
548 for(int h = 0; h < rootnodes.size(); h++) {
549 FlagState root=(FlagState)rootnodes.elementAt(h);
550 Vector allocatingTasks = root.getAllocatingTasks();
551 if(allocatingTasks != null) {
552 for(int k = 0; k < allocatingTasks.size(); k++) {
553 TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
555 (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
556 int numEdges = fev.size();
557 ScheduleNode sNode = cNode.getScheduleNode();
558 for(int j = 0; j < numEdges; j++) {
559 FEdge pfe = fev.elementAt(j);
560 FEdge.NewObjInfo noi = pfe.getNewObjInfo(cd);
561 if ((noi == null) || (noi.getNewRate() == 0)
562 || (noi.getProbability() == 0)) {
563 // fake creating edge, do not need to create corresponding
567 if(noi.getRoot() == null) {
568 // set root FlagState
571 FlagState pfs = (FlagState)pfe.getTarget();
572 ClassDescriptor pcd = pfs.getClassDescriptor();
573 ClassNode pcNode = cdToCNodes.get(pcd);
575 ScheduleEdge sEdge = new ScheduleEdge(sNode,
578 ScheduleEdge.NEWEDGE,
581 sEdge.setSourceCNode(pcNode);
582 sEdge.setTargetCNode(cNode);
583 sEdge.setTargetFState(root);
584 sEdge.setNewRate(noi.getNewRate());
585 sEdge.setProbability(noi.getProbability());
586 pcNode.getScheduleNode().addEdge(sEdge);
587 scheduleEdges.add(sEdge);
588 if((j !=0 ) || (k != 0) || (h != 0)) {
589 toBreakDown.add(sEdge);
594 allocatingTasks = null;
602 for(i = 0; i < multiparamtds.size(); i++) {
603 TaskDescriptor td = multiparamtds.elementAt(i);
604 ClassDescriptor cd = td.getParamType(0).getClassDesc();
605 // set the first parameter as main cd
606 // NOTE: programmer should write in such a style that
607 // for all multi-param tasks, the main class should be
608 // the first parameter
609 // TODO: may have bug when cd has multiple new flag states
610 this.td2maincd.put(td, cd);
616 private void treeTransform(Vector<ScheduleEdge> toBreakDown,
617 ScheduleNode startupNode) {
620 // Break down the 'cycle's
622 for(i = 0; i < toBreakDown.size(); i++ ) {
623 cloneSNodeList(toBreakDown.elementAt(i), false);
625 } catch (Exception e) {
630 // Remove fake 'new' edges
631 for(i = 0; i < scheduleEdges.size(); i++) {
632 ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i);
633 if((0 == se.getNewRate()) || (0 == se.getProbability())) {
634 scheduleEdges.removeElement(se);
635 scheduleNodes.removeElement(se.getTarget());
639 // Do topology sort of the ClassNodes and ScheduleEdges.
640 Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
641 Vector<ScheduleNode> tempSNodes =
642 ClassNode.DFS.topology(scheduleNodes, ssev);
643 scheduleNodes.removeAllElements();
644 scheduleNodes = tempSNodes;
646 scheduleEdges.removeAllElements();
647 scheduleEdges = ssev;
651 // Set the cid of these ScheduleNode
652 Queue<ScheduleNode> toVisit = new LinkedList<ScheduleNode>();
653 toVisit.add(startupNode);
654 while(!toVisit.isEmpty()) {
655 ScheduleNode sn = toVisit.poll();
656 if(sn.getCid() == -1) {
657 // not visited before
658 sn.setCid(ScheduleNode.colorID++);
659 Iterator it_edge = sn.edges();
660 while(it_edge.hasNext()) {
661 toVisit.add((ScheduleNode)((ScheduleEdge)it_edge.next()).getTarget());
668 if(this.state.PRINTSCHEDULING) {
669 SchedulingUtil.printScheduleGraph(
670 this.state.outputdir + "scheduling_ori.dot", this.scheduleNodes);
674 private void handleDescenSEs(Vector<ScheduleEdge> ses,
677 ScheduleEdge tempse = ses.elementAt(0);
678 long temptime = tempse.getListExeTime();
679 // find out the ScheduleEdge with least exeTime
680 for(int k = 1; k < ses.size(); k++) {
681 long ttemp = ses.elementAt(k).getListExeTime();
682 if(ttemp < temptime) {
683 tempse = ses.elementAt(k);
685 } // if(ttemp < temptime)
686 } // for(int k = 1; k < ses.size(); k++)
688 handleScheduleEdge(tempse, true);
689 ses.removeElement(tempse);
691 // handle other ScheduleEdges
692 for(int k = 0; k < ses.size(); k++) {
693 handleScheduleEdge(ses.elementAt(k), false);
694 } // for(int k = 0; k < ses.size(); k++)
697 private void CFSTGTransform() {
701 // table of all schedule edges associated to one fedge
702 Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses =
703 new Hashtable<FEdge, Vector<ScheduleEdge>>();
704 // table of all fedges associated to one schedule node
705 Hashtable<ScheduleNode, Vector<FEdge>> sn2fes =
706 new Hashtable<ScheduleNode, Vector<FEdge>>();
707 ScheduleNode preSNode = null;
708 // Access the ScheduleEdges in reverse topology order
709 for(i = scheduleEdges.size(); i > 0; i--) {
710 ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i-1);
711 if(ScheduleEdge.NEWEDGE == se.getType()) {
712 if(preSNode == null) {
713 preSNode = (ScheduleNode)se.getSource();
716 boolean split = false;
717 FEdge fe = se.getFEdge();
718 if(fe.getSource() == fe.getTarget()) {
719 // the associated start fe is a back edge
721 // check the number of newly created objs
722 int repeat = (int)Math.ceil(se.getNewRate()*se.getProbability()/100);
725 // more than one new objs, expand the new edge
726 for(int j = 1; j< repeat; j++ ) {
727 cloneSNodeList(se, true);
728 } // for(int j = 1; j< repeat; j++ )
730 se.setProbability(100);
731 } // if(repeat > 1)*/
733 // match the rates of obj creation and new obj consumption
734 rate = (int)Math.ceil(
735 se.getListExeTime()/calInExeTime(se.getSourceFState()));
736 } catch (Exception e) {
739 repeat = (rate > repeat)? rate : repeat;
740 // expand the new edge
741 for(int j = 1; j< repeat; j++ ) {
742 cloneSNodeList(se, true);
743 } // for(int j = 1; j< repeat; j++ )
745 se.setProbability(100);
746 /*for(int j = rate - 1; j > 0; j--) {
747 for(int k = repeat; k > 0; k--) {
748 cloneSNodeList(se, true);
749 } // for(int k = repeat; k > 0; k--)
750 } // for(int j = rate - 1; j > 0; j--)*/
751 } catch (Exception e) {
755 } else { // if(fe.getSource() == fe.getTarget())
756 // the associated start fe is not a back edge
757 // Note: if preSNode is not the same as se's source ScheduleNode
758 // handle any ScheduleEdges previously put into fe2ses whose source
759 // ScheduleNode is preSNode
760 boolean same = (preSNode == se.getSource());
762 // check the topology sort, only process those after se.getSource()
763 if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()){
764 if(sn2fes.containsKey(preSNode)) {
765 Vector<FEdge> fes = sn2fes.remove(preSNode);
766 for(int j = 0; j < fes.size(); j++) {
767 FEdge tempfe = fes.elementAt(j);
768 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
769 boolean isflag = !(preSNode.edges().hasNext());
770 this.handleDescenSEs(ses, isflag);
772 fe2ses.remove(tempfe);
773 } // for(int j = 0; j < fes.size(); j++)
777 preSNode = (ScheduleNode)se.getSource();
780 if(fe.getTarget().edges().hasNext()) {
781 // not associated with the last task, check if to split the snode
782 if((!(se.getTransTime() < this.transThreshold))
783 && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
784 // it's better to transfer the other obj with preSnode
786 splitSNode(se, true);
788 } // if(!fe.getTarget().edges().hasNext())
791 // delay the expanding and merging until we find all such 'new'
792 // edges associated with a last task inside this ClassNode
793 if(fe2ses.get(fe) == null) {
794 fe2ses.put(fe, new Vector<ScheduleEdge>());
796 if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
797 sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
799 if(!fe2ses.get(fe).contains(se)) {
800 fe2ses.get(fe).add(se);
802 if(!sn2fes.get((ScheduleNode)se.getSource()).contains(fe)) {
803 sn2fes.get((ScheduleNode)se.getSource()).add(fe);
806 } // if(fe.getSource() == fe.getTarget())
807 } // if(ScheduleEdge.NEWEDGE == se.getType())
808 } // for(i = scheduleEdges.size(); i > 0; i--)
809 if(!fe2ses.isEmpty()) {
810 Set<FEdge> keys = fe2ses.keySet();
811 Iterator it_keys = keys.iterator();
812 while(it_keys.hasNext()) {
813 FEdge tempfe = (FEdge)it_keys.next();
814 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
815 boolean isflag = !(tempfe.getTarget().edges().hasNext());
816 this.handleDescenSEs(ses, isflag);
827 if(this.state.PRINTSCHEDULING) {
828 SchedulingUtil.printScheduleGraph(
829 this.state.outputdir + "scheduling_extend.dot", this.scheduleNodes);
833 private void handleScheduleEdge(ScheduleEdge se,
837 int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
840 if(se.getListExeTime() == 0) {
843 rate = (int)Math.ceil(
844 (se.getTransTime()-calInExeTime(se.getSourceFState()))
845 /se.getListExeTime());
850 } catch (Exception e) {
854 // clone the whole ScheduleNode lists starting with se's target
855 for(int j = 1; j < repeat; j++ ) {
856 cloneSNodeList(se, true);
859 se.setProbability(100);
863 // clone the whole ScheduleNode lists starting with se's target
864 for(int j = 0; j < repeat; j++ ) {
865 cloneSNodeList(se, true);
868 se.setProbability(100);
871 // merge the original ScheduleNode to the source ScheduleNode
872 ((ScheduleNode)se.getSource()).mergeSEdge(se);
873 scheduleNodes.remove(se.getTarget());
874 scheduleEdges.remove(se);
875 // As se has been changed into an internal edge inside a ScheduleNode,
876 // change the source and target of se from original ScheduleNodes
878 if(se.getType() == ScheduleEdge.NEWEDGE) {
879 se.setTarget(se.getTargetCNode());
880 //se.setSource(se.getSourceCNode());
881 //se.getTargetCNode().addEdge(se);
882 se.getSourceCNode().addEdge(se);
885 // clone the whole ScheduleNode lists starting with se's target
886 for(int j = 1; j < repeat; j++ ) {
887 cloneSNodeList(se, true);
890 se.setProbability(100);
892 } catch (Exception e) {
898 private void cloneSNodeList(ScheduleEdge sEdge,
899 boolean copyIE) throws Exception {
900 Hashtable<ClassNode, ClassNode> cn2cn =
901 new Hashtable<ClassNode, ClassNode>(); // hashtable from classnode in
902 // orignal se's targe to cloned one
903 ScheduleNode csNode =
904 (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
905 scheduleNodes.add(csNode);
907 // Clone all the external in ScheduleEdges
910 Vector inedges = sEdge.getTarget().getInedgeVector();
911 for(i = 0; i < inedges.size(); i++) {
912 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
914 switch(tse.getType()) {
915 case ScheduleEdge.NEWEDGE: {
916 se = new ScheduleEdge(csNode,"new",tse.getFstate(),tse.getType(),0);
917 se.setProbability(100);
922 case ScheduleEdge.TRANSEDGE: {
923 se = new ScheduleEdge(csNode,"transmit",tse.getFstate(),tse.getType(),0);
924 se.setProbability(tse.getProbability());
925 se.setNewRate(tse.getNewRate());
930 throw new Exception("Error: not valid ScheduleEdge here");
933 se.setSourceCNode(tse.getSourceCNode());
934 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
935 se.setFEdge(tse.getFEdge());
936 se.setTargetFState(tse.getTargetFState());
938 tse.getSource().addEdge(se);
939 scheduleEdges.add(se);
943 sEdge.getTarget().removeInedge(sEdge);
944 sEdge.setTarget(csNode);
945 csNode.getInedgeVector().add(sEdge);
946 sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
947 sEdge.setIsclone(true);
950 Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>(); // all nodes to be cloned
951 Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>(); //clone nodes
952 Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>(); // queue of the mappings of classnodes inside cloned ScheduleNode
953 Vector<ScheduleNode> origins = new Vector<ScheduleNode>(); // queue of source ScheduleNode cloned
954 Hashtable<ScheduleNode, ScheduleNode> sn2sn =
955 new Hashtable<ScheduleNode, ScheduleNode>(); // mapping from cloned ScheduleNode to clone ScheduleNode
957 toClone.add((ScheduleNode)sEdge.getTarget());
958 origins.addElement((ScheduleNode)sEdge.getTarget());
959 sn2sn.put((ScheduleNode)sEdge.getTarget(), csNode);
961 while(!toClone.isEmpty()) {
962 Hashtable<ClassNode, ClassNode> tocn2cn =
963 new Hashtable<ClassNode, ClassNode>();
964 csNode = clone.poll();
965 ScheduleNode osNode = toClone.poll();
966 cn2cn = qcn2cn.poll();
967 // Clone all the external ScheduleEdges and the following ScheduleNodes
968 Vector edges = osNode.getEdgeVector();
969 for(i = 0; i < edges.size(); i++) {
970 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
971 ScheduleNode tSNode =
972 (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
973 scheduleNodes.add(tSNode);
975 toClone.add((ScheduleNode)tse.getTarget());
976 origins.addElement((ScheduleNode)tse.getTarget());
977 sn2sn.put((ScheduleNode)tse.getTarget(), tSNode);
979 ScheduleEdge se = null;
980 switch(tse.getType()) {
981 case ScheduleEdge.NEWEDGE: {
982 se = new ScheduleEdge(tSNode,"new",tse.getFstate(),tse.getType(),0);
986 case ScheduleEdge.TRANSEDGE: {
987 se = new ScheduleEdge(tSNode,"transmit",tse.getFstate(),tse.getType(),0);
992 throw new Exception("Error: not valid ScheduleEdge here");
995 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
996 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
997 se.setFEdge(tse.getFEdge());
998 se.setTargetFState(tse.getTargetFState());
999 se.setProbability(tse.getProbability());
1000 se.setNewRate(tse.getNewRate());
1001 se.setIsclone(true);
1003 scheduleEdges.add(se);
1018 private long calInExeTime(FlagState fs) throws Exception {
1020 ClassDescriptor cd = fs.getClassDescriptor();
1021 ClassNode cNode = cd2ClassNode.get(cd);
1022 exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
1024 Vector inedges = cNode.getInedgeVector();
1025 // Now that there are associate ScheduleEdges, there may be
1026 // multiple inedges of a ClassNode
1027 if(inedges.size() > 1) {
1028 throw new Exception("Error: ClassNode's inedges more than one!");
1030 if(inedges.size() > 0) {
1031 ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
1032 cNode = (ClassNode)sEdge.getSource();
1033 exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
1039 exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
1043 private ScheduleNode splitSNode(ScheduleEdge se,
1045 assert(ScheduleEdge.NEWEDGE == se.getType());
1047 FEdge fe = se.getFEdge();
1048 FlagState fs = (FlagState)fe.getTarget();
1049 FlagState nfs = (FlagState)fs.clone();
1050 fs.getEdgeVector().removeAllElements();
1051 nfs.getInedgeVector().removeAllElements();
1052 ClassNode sCNode = se.getSourceCNode();
1054 // split the subtree whose root is nfs from the whole flag transition tree
1055 Vector<FlagState> sfss = sCNode.getFlagStates();
1056 Vector<FlagState> fStates = new Vector<FlagState>();
1057 Queue<FlagState> toiterate = new LinkedList<FlagState>();
1060 while(!toiterate.isEmpty()) {
1061 FlagState tfs = toiterate.poll();
1062 Iterator it_edges = tfs.edges();
1063 while(it_edges.hasNext()) {
1064 FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
1065 if(!fStates.contains(temp)) {
1067 toiterate.add(temp);
1068 sfss.removeElement(temp);
1074 Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
1076 // create a ClassNode and ScheduleNode for this subtree
1077 ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
1078 ScheduleNode sNode = new ScheduleNode(cNode, 0);
1079 cNode.setScheduleNode(sNode);
1080 cNode.setSorted(true);
1081 cNode.setTransTime(sCNode.getTransTime());
1082 classNodes.add(cNode);
1083 scheduleNodes.add(sNode);
1086 } catch (Exception e) {
1087 e.printStackTrace();
1089 // flush the exeTime of fs and its ancestors
1092 while(!toiterate.isEmpty()) {
1093 FlagState tfs = toiterate.poll();
1094 long ttime = tfs.getExeTime();
1095 Iterator it_inedges = tfs.inedges();
1096 while(it_inedges.hasNext()) {
1097 FEdge fEdge = (FEdge)it_inedges.next();
1098 FlagState temp = (FlagState)fEdge.getSource();
1099 long time = fEdge.getExeTime() + ttime;
1100 if(temp.getExeTime() > time) {
1101 temp.setExeTime(time);
1102 toiterate.add(temp);
1109 // create a 'trans' ScheudleEdge between this new ScheduleNode and se's
1110 // source ScheduleNode
1111 ScheduleEdge sEdge =
1112 new ScheduleEdge(sNode, "transmit", fs, ScheduleEdge.TRANSEDGE, 0);
1114 sEdge.setSourceCNode(sCNode);
1115 sEdge.setTargetCNode(cNode);
1116 sEdge.setTargetFState(nfs);
1118 // Add calculation codes for calculating transmit time of an object
1119 sEdge.setTransTime(cNode.getTransTime());
1120 se.getSource().addEdge(sEdge);
1121 scheduleEdges.add(sEdge);
1122 // remove the ClassNodes and internal ScheduleEdges out of this subtree
1123 // to the new ScheduleNode
1124 ScheduleNode oldSNode = (ScheduleNode)se.getSource();
1125 Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
1126 Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
1127 Vector<ClassNode> rCNodes = new Vector<ClassNode>();
1128 rCNodes.addElement(sCNode);
1129 if(it_isEdges != null) {
1130 while(it_isEdges.hasNext()) {
1131 ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
1132 if(rCNodes.contains(tse.getSourceCNode())) {
1133 if(sCNode.equals(tse.getSourceCNode())) {
1134 if (!(tse.getSourceFState().equals(fs))
1135 && (sFStates.contains(tse.getSourceFState()))) {
1136 tse.setSource(cNode);
1137 tse.setSourceCNode(cNode);
1142 sNode.getScheduleEdges().addElement(tse);
1143 sNode.getClassNodes().addElement(tse.getTargetCNode());
1144 rCNodes.addElement(tse.getTargetCNode());
1145 oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
1146 toremove.addElement(tse);
1151 oldSNode.getScheduleEdges().removeAll(toremove);
1153 // redirect ScheudleEdges out of this subtree to the new ScheduleNode
1154 Iterator it_sEdges = se.getSource().edges();
1155 while(it_sEdges.hasNext()) {
1156 ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
1157 if(!(tse.equals(se)) && !(tse.equals(sEdge))
1158 && (tse.getSourceCNode().equals(sCNode))) {
1159 if(!(tse.getSourceFState().equals(fs))
1160 && (sFStates.contains(tse.getSourceFState()))) {
1161 tse.setSource(sNode);
1162 tse.setSourceCNode(cNode);
1163 sNode.getEdgeVector().addElement(tse);
1169 se.getSource().getEdgeVector().removeAll(toremove);
1176 //merge se into its source ScheduleNode
1177 sNode.setCid(((ScheduleNode)se.getSource()).getCid());
1178 ((ScheduleNode)se.getSource()).mergeSEdge(se);
1179 scheduleNodes.remove(se.getTarget());
1180 scheduleEdges.removeElement(se);
1181 // As se has been changed into an internal edge inside a ScheduleNode,
1182 // change the source and target of se from original ScheduleNodes
1184 if(se.getType() == ScheduleEdge.NEWEDGE) {
1185 se.setTarget(se.getTargetCNode());
1186 //se.setSource(se.getSourceCNode());
1187 //se.getTargetCNode().addEdge(se);
1188 se.getSourceCNode().addEdge(se);
1191 sNode.setCid(ScheduleNode.colorID++);
1192 handleScheduleEdge(se, true);
1194 } catch (Exception e) {
1195 e.printStackTrace();
1202 // TODO: restrict the number of generated scheduling according to the setted
1203 // scheduleThreshold
1204 private boolean coreMapping(int generateThreshold,
1205 int skipThreshold) throws Exception {
1206 if(this.coreNum == -1) {
1207 throw new Exception("Error: un-initialized coreNum when doing scheduling.");
1210 if(this.scheduleGraphs == null) {
1211 this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
1214 int reduceNum = this.scheduleNodes.size() - this.coreNum;
1216 // Combine some ScheduleNode if necessary
1217 // May generate multiple graphs suggesting candidate schedulings
1218 if(!(reduceNum > 0)) {
1219 // Enough cores, no need to combine any ScheduleNode
1220 this.scheduleGraphs.addElement(this.scheduleNodes);
1222 if(this.state.PRINTSCHEDULING) {
1223 String path = this.state.outputdir + "scheduling_" + gid + ".dot";
1224 SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
1228 SchedulingUtil.assignCids(this.scheduleNodes);
1230 // Go through all the Schedule Nodes, organize them in order of their cid
1231 Vector<Vector<ScheduleNode>> sNodeVecs =
1232 SchedulingUtil.rangeScheduleNodes(this.scheduleNodes);
1235 boolean isBig = Math.pow(this.coreNum, reduceNum) > 1000;
1236 Random rand = new Random();
1237 if(isBig && state.BAMBOOCOMPILETIME) {
1238 CombinationUtil.RootsGenerator rGen =
1239 CombinationUtil.allocateRootsGenerator(sNodeVecs,
1241 while((gid <= this.scheduleThreshold) && (rGen.nextGen())) {
1242 // first get the chosen rootNodes
1243 Vector<Vector<ScheduleNode>> rootNodes = rGen.getRootNodes();
1244 Vector<Vector<ScheduleNode>> nodes2combine = rGen.getNode2Combine();
1246 CombinationUtil.CombineGenerator cGen =
1247 CombinationUtil.allocateCombineGenerator(rootNodes,
1249 while((gid <= this.scheduleThreshold) && (cGen.randomGenE())) {
1250 boolean implement = true;
1252 implement = Math.abs(rand.nextInt()) % 100 > generateThreshold;
1255 Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
1256 Vector<ScheduleNode> sNodes =
1257 SchedulingUtil.generateScheduleGraph(this.state,
1263 this.scheduleGraphs.add(sNodes);
1266 } else if(Math.abs(rand.nextInt()) % 100 > skipThreshold){
1272 nodes2combine = null;
1277 CombinationUtil.RandomGenerator rGen =
1278 CombinationUtil.allocateRandomGenerator(sNodeVecs,
1280 // random genenration
1281 while((gid <= this.scheduleThreshold) && (rGen.nextGen())) {
1282 Vector<Vector<ScheduleNode>> mapping = rGen.getMapping();
1283 boolean implement = true;
1285 implement = Math.abs(rand.nextInt()) % 100 > generateThreshold;
1288 Vector<ScheduleNode> sNodes =
1289 SchedulingUtil.generateScheduleGraph(this.state,
1294 this.scheduleGraphs.add(sNodes);
1302 CombinationUtil.RootsGenerator rGen =
1303 CombinationUtil.allocateRootsGenerator(sNodeVecs,
1305 while((!isBig || (gid <= this.scheduleThreshold)) && (rGen.nextGen())) {
1306 // first get the chosen rootNodes
1307 Vector<Vector<ScheduleNode>> rootNodes = rGen.getRootNodes();
1308 Vector<Vector<ScheduleNode>> nodes2combine = rGen.getNode2Combine();
1310 CombinationUtil.CombineGenerator cGen =
1311 CombinationUtil.allocateCombineGenerator(rootNodes,
1313 while((!isBig || (gid <= this.scheduleThreshold)) && (cGen.nextGen())) {
1314 boolean implement = true;
1316 implement = Math.abs(rand.nextInt()) % 100 > generateThreshold;
1319 Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
1320 Vector<ScheduleNode> sNodes =
1321 SchedulingUtil.generateScheduleGraph(this.state,
1327 this.scheduleGraphs.add(sNodes);
1330 } else if(Math.abs(rand.nextInt()) % 100 > skipThreshold){
1336 nodes2combine = null;
1345 static class TaskInfo {
1346 public int m_numofexits;
1347 public long[] m_exetime;
1348 public double[] m_probability;
1349 public Vector<Hashtable<String, Integer>> m_newobjinfo;
1352 public TaskInfo(int numofexits) {
1353 this.m_numofexits = numofexits;
1354 this.m_exetime = new long[this.m_numofexits];
1355 this.m_probability = new double[this.m_numofexits];
1356 this.m_newobjinfo = new Vector<Hashtable<String, Integer>>();
1357 for(int i = 0; i < this.m_numofexits; i++) {
1358 this.m_newobjinfo.add(null);