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 newRate = this.coreNum;
399 } else if(cdname.equals("SentenceParser")) {
403 // tint = r.nextInt()%100;
404 // } while(tint <= 0);
405 // int probability = tint;
406 int probability = 100;
407 pfe.addNewObjInfo(cd, newRate, probability);
416 Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator();
417 while(it_flags.hasNext()) {
418 FlagState fs = (FlagState)it_flags.next();
419 Iterator it_edges = fs.edges();
421 while(it_edges.hasNext()) {
423 // tint = r.nextInt()%10;
424 // } while(tint <= 0);
426 FEdge edge = (FEdge)it_edges.next();
427 edge.setExeTime(tint);
428 if((fs.getClassDescriptor().getSymbol().equals("MD"))
429 && (edge.getTask().getSymbol().equals("t6"))) {
430 if(edge.isbackedge()) {
431 if(edge.getTarget().equals(edge.getSource())) {
432 edge.setProbability(93.75);
434 edge.setProbability(3.125);
437 edge.setProbability(3.125);
441 if(!it_edges.hasNext()) {
442 edge.setProbability(total);
444 if((total != 0) && (total != 1)) {
446 tint = r.nextInt()%total;
449 edge.setProbability(tint);
461 private ScheduleNode buildCFSTG(Vector<ScheduleEdge> toBreakDown,
462 Vector<TaskDescriptor> multiparamtds) {
463 Hashtable<ClassDescriptor, ClassNode> cdToCNodes =
464 new Hashtable<ClassDescriptor, ClassNode>();
465 // Build the combined flag transition diagram
466 // First, for each class create a ClassNode
467 Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator();
468 while(it_classes.hasNext()) {
469 ClassDescriptor cd = (ClassDescriptor) it_classes.next();
470 Set<FlagState> fStates = taskanalysis.getFlagStates(cd);
472 //Sort flagState nodes inside this ClassNode
473 Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
475 Vector rootnodes = taskanalysis.getRootNodes(cd);
476 if(((rootnodes != null) && (rootnodes.size() > 0))
477 || (cd.getSymbol().equals(TypeUtil.StartupClass))) {
478 ClassNode cNode = new ClassNode(cd, sFStates);
479 cNode.setSorted(true);
480 classNodes.add(cNode);
481 cd2ClassNode.put(cd, cNode);
482 cdToCNodes.put(cd, cNode);
491 ScheduleNode startupNode = null;
492 // For each ClassNode create a ScheduleNode containing it
494 for(i = 0; i < classNodes.size(); i++) {
495 ClassNode cn = classNodes.elementAt(i);
496 ScheduleNode sn = new ScheduleNode(cn, 0);
497 if(cn.getClassDescriptor().getSymbol().equals(TypeUtil.StartupClass)) {
500 cn.setScheduleNode(sn);
501 scheduleNodes.add(sn);
504 } catch (Exception e) {
509 // Create 'new' edges between the ScheduleNodes.
510 Vector<ClassDescriptor> singleCDs = new Vector<ClassDescriptor>();
511 for(i = 0; i < classNodes.size(); i++) {
512 ClassNode cNode = classNodes.elementAt(i);
513 ClassDescriptor cd = cNode.getClassDescriptor();
514 Vector rootnodes = taskanalysis.getRootNodes(cd);
515 boolean isSingle = false;
516 if(rootnodes != null) {
517 for(int h = 0; h < rootnodes.size(); h++) {
518 FlagState root=(FlagState)rootnodes.elementAt(h);
519 Vector allocatingTasks = root.getAllocatingTasks();
520 if(allocatingTasks != null) {
521 for(int k = 0; k < allocatingTasks.size(); k++) {
522 TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
524 (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
525 int numEdges = fev.size();
526 ScheduleNode sNode = cNode.getScheduleNode();
527 for(int j = 0; j < numEdges; j++) {
528 FEdge pfe = fev.elementAt(j);
529 FEdge.NewObjInfo noi = pfe.getNewObjInfo(cd);
530 if ((noi == null) || (noi.getNewRate() == 0)
531 || (noi.getProbability() == 0)) {
532 // fake creating edge, do not need to create corresponding
536 if(noi.getNewRate() == 1) {
539 if(noi.getRoot() == null) {
540 // set root FlagState
543 FlagState pfs = (FlagState)pfe.getTarget();
544 ClassDescriptor pcd = pfs.getClassDescriptor();
545 ClassNode pcNode = cdToCNodes.get(pcd);
547 ScheduleEdge sEdge = new ScheduleEdge(sNode,
550 ScheduleEdge.NEWEDGE,
553 sEdge.setSourceCNode(pcNode);
554 sEdge.setTargetCNode(cNode);
555 sEdge.setTargetFState(root);
556 sEdge.setNewRate(noi.getNewRate());
557 sEdge.setProbability(noi.getProbability());
558 pcNode.getScheduleNode().addEdge(sEdge);
559 scheduleEdges.add(sEdge);
560 if((j !=0 ) || (k != 0) || (h != 0)) {
561 toBreakDown.add(sEdge);
566 allocatingTasks = null;
577 for(i = 0; i < multiparamtds.size(); i++) {
578 TaskDescriptor td = multiparamtds.elementAt(i);
579 for(int j = 0; j < td.numParameters(); j++) {
580 ClassDescriptor cd = td.getParamType(j).getClassDesc();
581 if(singleCDs.contains(cd)) {
582 // set the first parameter which has single creation rate as main cd
583 // TODO: may have bug when cd has multiple new flag states
584 this.td2maincd.put(td, cd);
593 private void treeTransform(Vector<ScheduleEdge> toBreakDown,
594 ScheduleNode startupNode) {
597 // Break down the 'cycle's
599 for(i = 0; i < toBreakDown.size(); i++ ) {
600 cloneSNodeList(toBreakDown.elementAt(i), false);
602 } catch (Exception e) {
607 // Remove fake 'new' edges
608 for(i = 0; i < scheduleEdges.size(); i++) {
609 ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i);
610 if((0 == se.getNewRate()) || (0 == se.getProbability())) {
611 scheduleEdges.removeElement(se);
612 scheduleNodes.removeElement(se.getTarget());
616 // Do topology sort of the ClassNodes and ScheduleEdges.
617 Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
618 Vector<ScheduleNode> tempSNodes =
619 ClassNode.DFS.topology(scheduleNodes, ssev);
620 scheduleNodes.removeAllElements();
621 scheduleNodes = tempSNodes;
623 scheduleEdges.removeAllElements();
624 scheduleEdges = ssev;
628 // Set the cid of these ScheduleNode
629 Queue<ScheduleNode> toVisit = new LinkedList<ScheduleNode>();
630 toVisit.add(startupNode);
631 while(!toVisit.isEmpty()) {
632 ScheduleNode sn = toVisit.poll();
633 if(sn.getCid() == -1) {
634 // not visited before
635 sn.setCid(ScheduleNode.colorID++);
636 Iterator it_edge = sn.edges();
637 while(it_edge.hasNext()) {
638 toVisit.add((ScheduleNode)((ScheduleEdge)it_edge.next()).getTarget());
645 if(this.state.PRINTSCHEDULING) {
646 SchedulingUtil.printScheduleGraph(
647 this.state.outputdir + "scheduling_ori.dot", this.scheduleNodes);
651 private void CFSTGTransform() {
654 //Access the ScheduleEdges in reverse topology order
655 Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses =
656 new Hashtable<FEdge, Vector<ScheduleEdge>>();
657 Hashtable<ScheduleNode, Vector<FEdge>> sn2fes =
658 new Hashtable<ScheduleNode, Vector<FEdge>>();
659 ScheduleNode preSNode = null;
660 for(i = scheduleEdges.size(); i > 0; i--) {
661 ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i-1);
662 if(ScheduleEdge.NEWEDGE == se.getType()) {
663 if(preSNode == null) {
664 preSNode = (ScheduleNode)se.getSource();
667 boolean split = false;
668 FEdge fe = se.getFEdge();
669 if(fe.getSource() == fe.getTarget()) {
672 int repeat = (int)Math.ceil(se.getNewRate()*se.getProbability()/100);
675 for(int j = 1; j< repeat; j++ ) {
676 cloneSNodeList(se, true);
679 se.setProbability(100);
682 rate = (int)Math.ceil(
683 se.getListExeTime()/calInExeTime(se.getSourceFState()));
684 } catch (Exception e) {
687 for(int j = rate - 1; j > 0; j--) {
688 for(int k = repeat; k > 0; k--) {
689 cloneSNodeList(se, true);
692 } catch (Exception e) {
697 // if preSNode is not the same as se's source ScheduleNode
698 // handle any ScheduleEdges previously put into fe2ses whose source
699 // ScheduleNode is preSNode
700 boolean same = (preSNode == se.getSource());
702 // check the topology sort, only process those after se.getSource()
703 if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()){
704 if(sn2fes.containsKey(preSNode)) {
705 Vector<FEdge> fes = sn2fes.remove(preSNode);
706 for(int j = 0; j < fes.size(); j++) {
707 FEdge tempfe = fes.elementAt(j);
708 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
709 ScheduleEdge tempse = ses.elementAt(0);
710 long temptime = tempse.getListExeTime();
711 // find out the ScheduleEdge with least exeTime
712 for(int k = 1; k < ses.size(); k++) {
713 long ttemp = ses.elementAt(k).getListExeTime();
714 if(ttemp < temptime) {
715 tempse = ses.elementAt(k);
720 handleScheduleEdge(tempse, true);
721 ses.removeElement(tempse);
722 // handle other ScheduleEdges
723 for(int k = 0; k < ses.size(); k++) {
724 handleScheduleEdge(ses.elementAt(k), false);
727 fe2ses.remove(tempfe);
732 preSNode = (ScheduleNode)se.getSource();
735 // if fe is the last task inside this ClassNode, delay the expanding
736 // and merging until we find all such 'new' edges
737 // associated with a last task inside this ClassNode
738 if(!fe.getTarget().edges().hasNext()) {
739 if(fe2ses.get(fe) == null) {
740 fe2ses.put(fe, new Vector<ScheduleEdge>());
742 if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
743 sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
745 if(!fe2ses.get(fe).contains(se)) {
746 fe2ses.get(fe).add(se);
748 if(!sn2fes.get((ScheduleNode)se.getSource()).contains(fe)) {
749 sn2fes.get((ScheduleNode)se.getSource()).add(fe);
752 // As this is not a last task, first handle available ScheduleEdges
753 // previously put into fe2ses
754 if((same) && (sn2fes.containsKey(preSNode))) {
755 Vector<FEdge> fes = sn2fes.remove(preSNode);
756 for(int j = 0; j < fes.size(); j++) {
757 FEdge tempfe = fes.elementAt(j);
758 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
759 ScheduleEdge tempse = ses.elementAt(0);
760 long temptime = tempse.getListExeTime();
761 // find out the ScheduleEdge with least exeTime
762 for(int k = 1; k < ses.size(); k++) {
763 long ttemp = ses.elementAt(k).getListExeTime();
764 if(ttemp < temptime) {
765 tempse = ses.elementAt(k);
770 handleScheduleEdge(tempse, true);
771 ses.removeElement(tempse);
772 // handle other ScheduleEdges
773 for(int k = 0; k < ses.size(); k++) {
774 handleScheduleEdge(ses.elementAt(k), false);
777 fe2ses.remove(tempfe);
782 if((!(se.getTransTime() < this.transThreshold))
783 && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
785 splitSNode(se, true);
787 // handle this ScheduleEdge
788 handleScheduleEdge(se, true);
794 if(!fe2ses.isEmpty()) {
795 Set<FEdge> keys = fe2ses.keySet();
796 Iterator it_keys = keys.iterator();
797 while(it_keys.hasNext()) {
798 FEdge tempfe = (FEdge)it_keys.next();
799 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
800 ScheduleEdge tempse = ses.elementAt(0);
801 long temptime = tempse.getListExeTime();
802 // find out the ScheduleEdge with least exeTime
803 for(int k = 1; k < ses.size(); k++) {
804 long ttemp = ses.elementAt(k).getListExeTime();
805 if(ttemp < temptime) {
806 tempse = ses.elementAt(k);
811 handleScheduleEdge(tempse, true);
812 ses.removeElement(tempse);
813 // handle other ScheduleEdges
814 for(int k = 0; k < ses.size(); k++) {
815 handleScheduleEdge(ses.elementAt(k), false);
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) throws Exception {
1205 if(this.coreNum == -1) {
1206 throw new Exception("Error: un-initialized coreNum when doing scheduling.");
1209 if(this.scheduleGraphs == null) {
1210 this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
1213 int reduceNum = this.scheduleNodes.size() - this.coreNum;
1215 // Combine some ScheduleNode if necessary
1216 // May generate multiple graphs suggesting candidate schedulings
1217 if(!(reduceNum > 0)) {
1218 // Enough cores, no need to combine any ScheduleNode
1219 this.scheduleGraphs.addElement(this.scheduleNodes);
1221 if(this.state.PRINTSCHEDULING) {
1222 String path = this.state.outputdir + "scheduling_" + gid + ".dot";
1223 SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
1227 SchedulingUtil.assignCids(this.scheduleNodes);
1229 // Go through all the Schedule Nodes, organize them in order of their cid
1230 Vector<Vector<ScheduleNode>> sNodeVecs =
1231 SchedulingUtil.rangeScheduleNodes(this.scheduleNodes);
1233 CombinationUtil.RootsGenerator rGen =
1234 CombinationUtil.allocateRootsGenerator(sNodeVecs,
1238 Random rand = new Random();
1239 boolean isBig = Math.pow(this.coreNum, reduceNum) > 1000;
1240 while((!isBig || (gid <= this.scheduleThreshold)) && (rGen.nextGen())) {
1241 // first get the chosen rootNodes
1242 Vector<Vector<ScheduleNode>> rootNodes = rGen.getRootNodes();
1243 Vector<Vector<ScheduleNode>> nodes2combine = rGen.getNode2Combine();
1245 CombinationUtil.CombineGenerator cGen =
1246 CombinationUtil.allocateCombineGenerator(rootNodes,
1248 while((!isBig || (gid <= this.scheduleThreshold)) && (cGen.nextGen())) {
1249 boolean implement = true;
1251 implement = Math.abs(rand.nextInt()) % 100 > generateThreshold;
1254 Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
1255 Vector<ScheduleNode> sNodes =
1256 SchedulingUtil.generateScheduleGraph(this.state,
1262 this.scheduleGraphs.add(sNodes);
1269 nodes2combine = null;
1277 static class TaskInfo {
1278 public int m_numofexits;
1279 public long[] m_exetime;
1280 public double[] m_probability;
1281 public Vector<Hashtable<String, Integer>> m_newobjinfo;
1284 public TaskInfo(int numofexits) {
1285 this.m_numofexits = numofexits;
1286 this.m_exetime = new long[this.m_numofexits];
1287 this.m_probability = new double[this.m_numofexits];
1288 this.m_newobjinfo = new Vector<Hashtable<String, Integer>>();
1289 for(int i = 0; i < this.m_numofexits; i++) {
1290 this.m_newobjinfo.add(null);