1 package Analysis.Scheduling;
4 import java.io.FileOutputStream;
5 import java.io.PrintStream;
6 import java.io.PrintWriter;
7 import java.util.Hashtable;
8 import java.util.Iterator;
9 import java.util.LinkedList;
10 import java.util.Queue;
11 import java.util.Random;
12 import java.util.Vector;
14 import Analysis.OwnershipAnalysis.OwnershipAnalysis;
15 import Analysis.TaskStateAnalysis.FEdge;
16 import Analysis.TaskStateAnalysis.FlagState;
17 import Analysis.TaskStateAnalysis.TaskAnalysis;
18 import IR.ClassDescriptor;
20 import IR.TaskDescriptor;
23 public class MCImplSynthesis {
26 ScheduleAnalysis scheduleAnalysis;
27 TaskAnalysis taskAnalysis;
28 OwnershipAnalysis ownershipAnalysis;
29 ScheduleSimulator scheduleSimulator;
32 int scheduleThreshold; // # of starting points generated by schedule analysis
33 int probThreshold; // the probability to stop when no accelaration achieved
34 // in the directed simulated annealing
35 int generateThreshold; // how many optimized implementation generated in
36 // each iteration of the directed simulated annealing
37 int skipThreshold; // the probability to skip to producing more optimization
38 // with the same root sets(see ScheduleAnalysis.coremapping)
40 public MCImplSynthesis(State state,
42 OwnershipAnalysis oa) {
44 this.coreNum = state.CORENUM;
45 this.taskAnalysis = ta;
46 this.ownershipAnalysis = oa;
47 this.scheduleAnalysis = new ScheduleAnalysis(state,
49 this.scheduleAnalysis.setCoreNum(this.coreNum);
50 this.scheduleSimulator = new ScheduleSimulator(this.coreNum,
53 this.scheduleThreshold = 1000;
54 this.probThreshold = 0;
55 this.generateThreshold = 30;
56 this.skipThreshold = 100; // never skip // 30;
59 public int getCoreNum() {
60 return this.scheduleAnalysis.getCoreNum();
63 public int getScheduleThreshold() {
64 return scheduleThreshold;
67 public void setScheduleThreshold(int scheduleThreshold) {
68 this.scheduleThreshold = scheduleThreshold;
71 public int getProbThreshold() {
75 public void setProbThreshold(int probThreshold) {
76 this.probThreshold = probThreshold;
79 public int getGenerateThreshold() {
80 return generateThreshold;
83 public void setGenerateThreshold(int generateThreshold) {
84 this.generateThreshold = generateThreshold;
87 public Vector<Schedule> synthesis() {
88 // Print stuff to the original output and error streams.
89 // The stuff printed through the 'origOut' and 'origErr' references
90 // should go to the console on most systems while the messages
91 // printed through the 'System.out' and 'System.err' will end up in
92 // the files we created for them.
93 //origOut.println ("\nRedirect: Round #2");
94 //System.out.println ("Test output via 'SimulatorResult.out'.");
95 //origOut.println ("Test output via 'origOut' reference.");
97 // Save the current standard input, output, and error streams
98 // for later restoration.
99 PrintStream origOut = System.out;
101 // Create a new output stream for the stcriticalPathandard output.
102 PrintStream stdout = null;
104 if(!state.BAMBOOCOMPILETIME) {
105 stdout = new PrintStream(
106 new FileOutputStream(this.state.outputdir + "SimulatorResult_"
107 + this.coreNum + ".out"));
109 } catch (Exception e) {
110 // Sigh. Couldn't open the file.
111 System.out.println("Redirect: Unable to open output file!");
115 // Print stuff to the original output and error streams.
116 // On most systems all of this will end up on your console when you
117 // run this application.
118 //origOut.println ("\nRedirect: Round #1");
119 //System.out.println ("Test output via 'System.out'.");
120 //origOut.println ("Test output via 'origOut' reference.");
122 // Set the System out and err streams to use our replacements.
123 if(!state.BAMBOOCOMPILETIME) {
124 System.setOut(stdout);
127 Vector<Schedule> scheduling = null;
128 Vector<ScheduleNode> schedulinggraph = null;
131 // check all multi-parameter tasks
132 Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
134 this.state.getTaskSymbolTable().getDescriptorsIterator();
135 while(it_tasks.hasNext()) {
136 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
137 if(td.numParameters() > 1) {
138 multiparamtds.addElement(td);
143 // generate multiple schedulings
144 this.scheduleAnalysis.setScheduleThreshold(this.scheduleThreshold);
146 this.scheduleAnalysis.schedule(this.generateThreshold,
149 if(this.generateThreshold > 5) {
150 this.generateThreshold = 5;
152 this.scheduleSimulator.init();
154 Vector<Vector<ScheduleNode>> scheduleGraphs = null;
155 Vector<Vector<ScheduleNode>> newscheduleGraphs =
156 this.scheduleAnalysis.getScheduleGraphs();
157 Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
158 this.scheduleAnalysis.getTd2maincd();
159 Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
160 Vector<Integer> selectedSchedulings = new Vector<Integer>();
161 Vector<SimExecutionNode> selectedSimExeGraphs =
162 new Vector<SimExecutionNode>();
163 SimExecutionNode selectedSimExeGraph_bk = null;
166 long bestexetime = Long.MAX_VALUE;
167 Random rand = new Random();
168 int threshold = this.scheduleThreshold;
169 // simulate the generated schedulings and try to optimize it
171 if(!state.BAMBOOCOMPILETIME) {
172 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
173 System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
175 gid += newscheduleGraphs.size();
176 if(scheduleGraphs != null) {
177 for(int i = 0; i < scheduleGraphs.size(); i++) {
178 Vector<ScheduleNode> tmpgraph = scheduleGraphs.elementAt(i);
179 for(int j = 0; j < tmpgraph.size(); j++) {
180 ScheduleNode snode = tmpgraph.elementAt(j);
181 snode.getEdgeVector().clear();
182 snode.getInedgeVector().clear();
183 snode.getScheduleEdges().clear();
184 snode.getClassNodes().clear();
189 scheduleGraphs.clear();
191 scheduleGraphs = newscheduleGraphs;
193 // get scheduling layouts from schedule graphs
194 for(int i = 0; i < scheduleGraphs.size(); i++) {
195 Vector<ScheduleNode> scheduleGraph = scheduleGraphs.elementAt(i);
196 Vector<Schedule> tmpscheduling =
197 generateScheduling(scheduleGraph, td2maincd);
198 schedulings.add(tmpscheduling);
199 scheduleGraph = null;
200 tmpscheduling = null;
202 selectedSchedulings.clear();
203 selectedSimExeGraphs.clear();
204 long tmpexetime = this.scheduleSimulator.simulate(schedulings,
206 selectedSimExeGraphs);
207 boolean remove = false;
208 if(tmpexetime < bestexetime) {
210 bestexetime = tmpexetime;
211 if(scheduling != null) {
213 for(int j = 0; j < schedulinggraph.size(); j++) {
214 ScheduleNode snode = schedulinggraph.elementAt(j);
215 snode.getEdgeVector().clear();
216 snode.getInedgeVector().clear();
217 snode.getScheduleEdges().clear();
218 snode.getClassNodes().clear();
220 schedulinggraph.clear();
221 selectedSimExeGraph_bk = null;
223 scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0));
224 schedulinggraph = scheduleGraphs.elementAt(
225 selectedSchedulings.elementAt(0));
226 selectedSimExeGraph_bk = selectedSimExeGraphs.elementAt(0);
228 if(!state.BAMBOOCOMPILETIME) {
229 System.out.print("end of: #" + tryindex + " (bestexetime: "
230 + bestexetime + ")\n");
231 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
234 threshold = this.scheduleThreshold;
235 } else if(tmpexetime == bestexetime) {
236 if(!state.BAMBOOCOMPILETIME) {
237 System.out.print("end of: #" + tryindex + " (bestexetime: "
238 + bestexetime + ")\n");
239 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
243 if((threshold > 40) ||
244 ((Math.abs(rand.nextInt()) % 100) < this.probThreshold + 10)) {
248 if(!state.BAMBOOCOMPILETIME) {
249 System.out.print("end of: #" + tryindex + " (bestexetime: "
250 + bestexetime + ")\n");
251 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
254 if(threshold == this.scheduleThreshold) {
255 if(scheduleGraphs != null) {
256 scheduleGraphs.clear();
258 scheduleGraphs.addElement(schedulinggraph);
259 if(selectedSchedulings != null) {
260 selectedSchedulings.clear();
262 selectedSchedulings.addElement(Integer.valueOf(0));
263 if(selectedSimExeGraphs != null) {
264 selectedSimExeGraphs.clear();
266 selectedSimExeGraphs.addElement(selectedSimExeGraph_bk);
269 if( (threshold > 40) ||
270 ((Math.abs(rand.nextInt()) % 100) < this.probThreshold + 1)) {
277 // try to optimize the best one scheduling
279 newscheduleGraphs = optimizeScheduling(scheduleGraphs,
281 selectedSimExeGraphs,
284 /*if(newscheduleGraphs != null) {
285 if(this.generateThreshold < 30) {
286 this.generateThreshold = 30;
291 if(this.generateThreshold > 0) {
292 this.generateThreshold -= 3;
294 if((Math.abs(rand.nextInt()) % 10000) < this.probThreshold + 1) {
300 scheduleGraphs.removeElementAt(selectedSchedulings.elementAt(0));
301 selectedSimExeGraphs.removeElementAt(0);
306 }while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
308 if(scheduleGraphs != null) {
309 scheduleGraphs.clear();
311 scheduleGraphs = null;
312 newscheduleGraphs = null;
315 selectedSchedulings.clear();
316 selectedSchedulings = null;
317 selectedSimExeGraphs.clear();
318 selectedSimExeGraphs = null;
320 multiparamtds.clear();
321 multiparamtds = null;
325 if(!state.BAMBOOCOMPILETIME) {
326 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
328 System.out.print("selected bestexetime: " + bestexetime + "\n");
329 if(!state.BAMBOOCOMPILETIME) {
330 String path = this.state.outputdir + "scheduling_selected.dot";
331 SchedulingUtil.printScheduleGraph(path, schedulinggraph);
334 // Close the streams.
336 if(!state.BAMBOOCOMPILETIME) {
339 System.setOut(origOut);
341 } catch (Exception e) {
342 origOut.println("Redirect: Unable to close files!");
345 schedulinggraph.clear();
346 schedulinggraph = null;
352 // get the distribution info of new search algorithm
353 public void distribution(boolean isall, int startnum) {
354 // Print stuff to the original output and error streams.
355 // The stuff printed through the 'origOut' and 'origErr' references
356 // should go to the console on most systems while the messages
357 // printed through the 'System.out' and 'System.err' will end up in
358 // the files we created for them.
359 //origOut.println ("\nRedirect: Round #2");
360 //System.out.println ("Test output via 'SimulatorResult.out'.");
361 //origOut.println ("Test output via 'origOut' reference.");
363 // Save the current standard input, output, and error streams
364 // for later restoration.
365 PrintStream origOut = System.out;
367 // Create a new output stream for the standard output.
368 PrintStream stdout = null;
370 stdout = new PrintStream(
371 new FileOutputStream(this.state.outputdir + "SimulatorResult_"
372 + this.coreNum + ".out"));
373 } catch (Exception e) {
374 // Sigh. Couldn't open the file.
375 System.out.println("Redirect: Unable to open output file!");
379 // Print stuff to the original output and error streams.
380 // On most systems all of this will end up on your console when you
381 // run this application.
382 //origOut.println ("\nRedirect: Round #1");
383 //System.out.println ("Test output via 'System.out'.");
384 //origOut.println ("Test output via 'origOut' reference.");
386 // Set the System out and err streams to use our replacements.
387 System.setOut(stdout);
390 // check all multi-parameter tasks
391 Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
393 this.state.getTaskSymbolTable().getDescriptorsIterator();
394 while(it_tasks.hasNext()) {
395 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
396 if(td.numParameters() > 1) {
397 multiparamtds.addElement(td);
402 // Generate all possible schedulings
403 //this.scheduleAnalysis.setScheduleThreshold(Integer.MAX_VALUE);
404 //this.scheduleAnalysis.schedule(-1, multiparamtds);
405 this.scheduleAnalysis.setScheduleThreshold(10000);
406 this.scheduleAnalysis.schedule(80,
409 this.scheduleSimulator.init();
411 Vector<Vector<ScheduleNode>> totestscheduleGraphs =
412 this.scheduleAnalysis.getScheduleGraphs();
413 Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
414 this.scheduleAnalysis.getTd2maincd();
415 Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
416 Vector<Integer> selectedSchedulings = new Vector<Integer>();
417 Vector<SimExecutionNode> selectedSimExeGraphs =
418 new Vector<SimExecutionNode>();
420 File file=new File(this.state.outputdir+"distributeinfo_s_"+this.coreNum
422 FileOutputStream dotstream = null;
424 dotstream = new FileOutputStream(file,false);
425 } catch (Exception e) {
429 PrintWriter output = new java.io.PrintWriter(dotstream, true);
430 output.println("start time(1,000,000 cycles): "
431 + totestscheduleGraphs.size());
432 for(int ii = 0; ii < totestscheduleGraphs.size(); ii++) {
433 Vector<Vector<ScheduleNode>> newscheduleGraphs =
434 new Vector<Vector<ScheduleNode>>();
435 newscheduleGraphs.add(totestscheduleGraphs.elementAt(ii));
436 // simulate the generated schedulings and try to optimize it
438 // get scheduling layouts from schedule graphs
439 for(int i = 0; i < newscheduleGraphs.size(); i++) {
440 Vector<ScheduleNode> scheduleGraph = newscheduleGraphs.elementAt(i);
441 Vector<Schedule> tmpscheduling =
442 generateScheduling(scheduleGraph, td2maincd);
443 schedulings.add(tmpscheduling);
444 scheduleGraph = null;
445 tmpscheduling = null;
447 selectedSchedulings.clear();
448 selectedSimExeGraphs.clear();
449 long tmpexetime = this.scheduleSimulator.simulate(schedulings,
451 selectedSimExeGraphs);
452 output.println(((float)tmpexetime/100000000));
456 // check all multi-parameter tasks
457 Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
459 this.state.getTaskSymbolTable().getDescriptorsIterator();
460 while(it_tasks.hasNext()) {
461 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
462 if(td.numParameters() > 1) {
463 multiparamtds.addElement(td);
468 // generate multiple schedulings
469 this.scheduleThreshold = 20;
470 this.generateThreshold = 30;
471 this.probThreshold = 0;
472 this.scheduleAnalysis.setScheduleThreshold(1000);
474 this.scheduleAnalysis.schedule(this.generateThreshold,
477 this.scheduleSimulator.init();
479 Vector<Vector<ScheduleNode>> scheduleGraphs = null;
480 Vector<Vector<ScheduleNode>> totestscheduleGraphs =
481 this.scheduleAnalysis.getScheduleGraphs();
482 Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
483 this.scheduleAnalysis.getTd2maincd();
484 Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
485 Vector<Integer> selectedSchedulings = new Vector<Integer>();
486 Vector<SimExecutionNode> selectedSimExeGraphs =
487 new Vector<SimExecutionNode>();
488 SimExecutionNode selectedSimExeGraph_bk = null;
490 File file=new File(this.state.outputdir + "distributeinfo_s_"
491 + this.coreNum + ".out");
492 FileOutputStream dotstream = null;
493 File file2=new File(this.state.outputdir + "distributeinfo_o_"
494 + this.coreNum + ".out");
495 FileOutputStream dotstream2 = null;
497 dotstream = new FileOutputStream(file,false);
498 dotstream2 = new FileOutputStream(file2,false);
499 } catch (Exception e) {
503 PrintWriter output = new java.io.PrintWriter(dotstream, true);
504 PrintWriter output2 = new java.io.PrintWriter(dotstream2, true);
505 output.println("start time(100,000,000 cycles): "
506 + totestscheduleGraphs.size());
507 output2.println("optimized time(100,000,000 cycles): "
508 + totestscheduleGraphs.size());
509 for(int ii = startnum; ii < totestscheduleGraphs.size(); ii++) {
510 Vector<Vector<ScheduleNode>> newscheduleGraphs =
511 new Vector<Vector<ScheduleNode>>();
512 newscheduleGraphs.add(totestscheduleGraphs.elementAt(ii));
514 long bestexetime = Long.MAX_VALUE;
516 Vector<Schedule> scheduling = null;
517 Vector<ScheduleNode> schedulinggraph = null;
518 boolean isfirst = true;
519 Random rand = new Random();
520 int threshold = this.scheduleThreshold;
521 // simulate the generated schedulings and try to optimize it
522 System.out.print("=========================================================\n");
523 System.out.print("# " + ii + ": \n");
525 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
526 System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
527 gid += newscheduleGraphs.size();
528 if(scheduleGraphs != null) {
529 for(int i = 0; i < scheduleGraphs.size(); i++) {
530 Vector<ScheduleNode> tmpgraph = scheduleGraphs.elementAt(i);
531 for(int j = 0; j < tmpgraph.size(); j++) {
532 ScheduleNode snode = tmpgraph.elementAt(j);
533 snode.getEdgeVector().clear();
534 snode.getInedgeVector().clear();
535 snode.getScheduleEdges().clear();
536 snode.getClassNodes().clear();
541 scheduleGraphs.clear();
543 scheduleGraphs = newscheduleGraphs;
545 // get scheduling layouts from schedule graphs
546 for(int i = 0; i < scheduleGraphs.size(); i++) {
547 Vector<ScheduleNode> scheduleGraph = scheduleGraphs.elementAt(i);
548 Vector<Schedule> tmpscheduling =
549 generateScheduling(scheduleGraph, td2maincd);
550 schedulings.add(tmpscheduling);
551 scheduleGraph = null;
552 tmpscheduling = null;
554 selectedSchedulings.clear();
555 selectedSimExeGraphs.clear();
556 long tmpexetime = this.scheduleSimulator.simulate(schedulings,
558 selectedSimExeGraphs);
560 output.println(((float)tmpexetime/100000000));
563 if(tmpexetime < bestexetime) {
564 bestexetime = tmpexetime;
565 if(scheduling != null) {
567 for(int j = 0; j < schedulinggraph.size(); j++) {
568 ScheduleNode snode = schedulinggraph.elementAt(j);
569 snode.getEdgeVector().clear();
570 snode.getInedgeVector().clear();
571 snode.getScheduleEdges().clear();
572 snode.getClassNodes().clear();
574 schedulinggraph.clear();
575 selectedSimExeGraph_bk = null;
577 scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0));
578 schedulinggraph = scheduleGraphs.elementAt(
579 selectedSchedulings.elementAt(0));
580 selectedSimExeGraph_bk = selectedSimExeGraphs.elementAt(0);
582 threshold = this.scheduleThreshold;
583 System.out.print("end of: #" + tryindex + " (bestexetime: "
584 + bestexetime + ")\n");
585 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
586 } else if(tmpexetime == bestexetime) {
587 System.out.print("end of: #" + tryindex + " (bestexetime: "
588 + bestexetime + ")\n");
589 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
591 threshold = this.scheduleThreshold;
592 if((Math.abs(rand.nextInt()) % 100) < this.probThreshold) {
596 System.out.print("end of: #" + tryindex + " (bestexetime: "
597 + bestexetime + ")\n");
598 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
600 if(threshold == this.scheduleThreshold) {
601 if(scheduleGraphs != null) {
602 scheduleGraphs.clear();
604 scheduleGraphs.addElement(schedulinggraph);
605 if(selectedSchedulings != null) {
606 selectedSchedulings.clear();
608 selectedSchedulings.addElement(Integer.valueOf(0));
609 if(selectedSimExeGraphs != null) {
610 selectedSimExeGraphs.clear();
612 selectedSimExeGraphs.addElement(selectedSimExeGraph_bk);
615 if((Math.abs(rand.nextInt()) % 100) < this.probThreshold + 1) {
622 // try to optimize theschedulings best one scheduling
623 newscheduleGraphs = optimizeScheduling(scheduleGraphs,
625 selectedSimExeGraphs,
627 this.scheduleThreshold);
628 if(tmpexetime < bestexetime) {
629 scheduleGraphs.remove(selectedSchedulings.elementAt(0));
634 }while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
636 scheduleGraphs.clear();
637 scheduleGraphs = null;
639 schedulinggraph = null;
640 if(newscheduleGraphs != null) {
641 newscheduleGraphs.clear();
643 newscheduleGraphs = null;
644 totestscheduleGraphs.elementAt(ii).clear();
645 for(int i = 0; i < schedulings.size(); i++) {
646 schedulings.elementAt(i).clear();
649 selectedSchedulings.clear();
650 selectedSimExeGraphs.clear();
652 output2.println(((float)bestexetime/100000000));
653 System.out.print("=========================================================\n");
656 if(scheduleGraphs != null) {
657 scheduleGraphs.clear();
659 scheduleGraphs = null;
660 totestscheduleGraphs = null;
661 for(int i = 0; i < schedulings.size(); i++) {
662 schedulings.elementAt(i).clear();
666 selectedSchedulings.clear();
667 selectedSchedulings = null;
668 selectedSimExeGraphs.clear();
669 selectedSimExeGraphs = null;
670 multiparamtds.clear();
671 multiparamtds = null;
675 // Close the streams.
681 System.setOut(origOut);
682 } catch (Exception e) {
683 origOut.println("Redirect: Unable to close files!");
690 private Vector<Vector<ScheduleNode>>
691 optimizeScheduling(Vector<Vector<ScheduleNode>> scheduleGraphs,
692 Vector<Integer> selectedScheduleGraphs,
693 Vector<SimExecutionNode> selectedSimExeGraphs,
696 if(this.coreNum == 1) {
701 Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
705 for(int i = 0; i < selectedScheduleGraphs.size(); i++) {
706 Vector<ScheduleNode> schedulegraph = scheduleGraphs.elementAt(
707 selectedScheduleGraphs.elementAt(i));
708 SimExecutionNode startnode = selectedSimExeGraphs.elementAt(i);
709 Vector<SimExecutionEdge> criticalPath = analyzeCriticalPath(startnode);
711 if(this.state.PRINTCRITICALPATH) {
712 System.err.println("gid: " + lgid + " endpoint: " + startnode.getTimepoint());
714 Vector<Vector<ScheduleNode>> tmposchedulegraphs =
715 optimizeCriticalPath(schedulegraph,
719 if(tmposchedulegraphs != null) {
720 if(optimizeschedulegraphs == null) {
721 optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
723 optimizeschedulegraphs.addAll(tmposchedulegraphs);
724 lgid += tmposchedulegraphs.size();
725 left -= tmposchedulegraphs.size();
727 schedulegraph = null;
729 tmposchedulegraphs = null;
733 schedulegraph = null;
735 tmposchedulegraphs = null;
738 return optimizeschedulegraphs;
741 private Vector<SimExecutionEdge>
742 analyzeCriticalPath(SimExecutionNode startnode) {
743 // first figure out the critical path
744 Vector<SimExecutionEdge> criticalPath = new Vector<SimExecutionEdge>();
745 getCriticalPath(startnode, criticalPath);
746 computeBestStartPoint(criticalPath);
751 // TODO: currently only get one critical path. It's possible that there are
752 // multiple critical paths and some of them can not be optimized while others
753 // can. Need to fix up for this situation.
754 private long getCriticalPath(SimExecutionNode startnode,
755 Vector<SimExecutionEdge> criticalPath) {
757 SimExecutionNode snode = startnode;
758 // go reversely to find the critical path
759 while(snode != null) {
760 SimExecutionNode nsnode = null;
761 Iterator<SimExecutionEdge> it_iedges =
762 (Iterator<SimExecutionEdge>)snode.inedges();
763 while(it_iedges.hasNext()) {
764 SimExecutionEdge sedge = it_iedges.next();
765 //if(sedge.getWeight() != 0) {
766 SimExecutionNode tsnode = (SimExecutionNode)(sedge.getSource());
767 if(tsnode.getTimepoint() + sedge.getWeight() == snode.getTimepoint()) {
769 criticalPath.insertElementAt(sedge, 0);
770 sum += sedge.getWeight();
781 private void computeBestStartPoint(Vector<SimExecutionEdge> criticalPath) {
782 // calculate the earliest start time of each task on the critial path
783 for(int i = 0; i < criticalPath.size(); i++) {
784 SimExecutionEdge seedge = criticalPath.elementAt(i);
785 Vector<SimExecutionEdge> predicates = seedge.getPredicates();
786 if(predicates != null) {
789 // check the latest finish time of all the predicates
790 for(int j = 0; j < predicates.size(); j++) {
791 SimExecutionEdge predicate = predicates.elementAt(j);
792 long tmptime = predicate.getBestStartPoint() + predicate.getWeight();
793 if(tmptime > starttime) {
795 seedge.setLastpredicateEdge(predicate);
796 if(predicate.getTd() != null) {
797 seedge.setLastpredicateNode(
798 (SimExecutionNode)predicate.getTarget());
801 seedge.setLastpredicateNode(
802 (SimExecutionNode)predicate.getSource());
806 seedge.setBestStartPoint(starttime);
807 } else if(seedge.getSource().getInedgeVector().size() > 0) {
808 // should have only one in edge
809 long starttime = ((SimExecutionNode)seedge.getSource()).getTimepoint();
810 seedge.setBestStartPoint(starttime);
813 seedge.setBestStartPoint(0);
819 private Vector<Vector<ScheduleNode>>
820 optimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
821 Vector<SimExecutionEdge> criticalPath,
824 Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
828 // for test, print out the criticalPath
829 if(this.state.PRINTCRITICALPATH) {
830 SchedulingUtil.printCriticalPath(this.state.outputdir + "criticalpath_"
831 + lgid + ".dot", criticalPath);
834 // first check all seedges whose real start point is late than predicted
835 // earliest start time and group them
836 long opcheckpoint = Long.MAX_VALUE;
837 Vector<Integer> sparecores = null;
838 // group according to core index
839 Hashtable<Long, Hashtable<Integer, Vector<SimExecutionEdge>>> toselects =
840 new Hashtable<Long, Hashtable<Integer, Vector<SimExecutionEdge>>>();
841 Random rand = new Random();
842 for(int i = 0; i < criticalPath.size(); i++) {
843 SimExecutionEdge seedge = criticalPath.elementAt(i);
844 long starttime = seedge.getBestStartPoint();
845 if((starttime < ((SimExecutionNode)seedge.getSource()).getTimepoint())
846 && (seedge.getTd() != null)){
847 // Note: must be a task related edge, can not be an object transfer edge
848 // no restrictions due to data dependencies
849 // have potential to be parallelled and start execution earlier
850 seedge.setFixedTime(false);
851 // consider to optimize it only when its predicates can NOT
852 // be optimized, otherwise first considering optimize its predicates
853 //SimExecutionEdge lastpredicateedge = seedge.getLastpredicateEdge();
855 //if(lastpredicateedge.isFixedTime()) {
856 int corenum = seedge.getCoreNum();
857 if(!toselects.containsKey(starttime)) {
858 toselects.put(starttime,
859 new Hashtable<Integer, Vector<SimExecutionEdge>>());
861 if(!toselects.get(starttime).containsKey(corenum)) {
862 toselects.get(starttime).put(corenum,
863 new Vector<SimExecutionEdge>());
865 toselects.get(starttime).get(corenum).add(seedge);
870 // Randomly choose the tasks to optimize(previously only
871 // consider the tasks with smallest best start time)
872 Vector<Long> keys = new Vector<Long>(toselects.keySet());
874 int length = keys.size();
876 return optimizeschedulegraphs;
878 int tochoose = Math.abs(rand.nextInt()) % length;
879 opcheckpoint = (keys.elementAt(tochoose)).longValue();
880 keys.removeElementAt(tochoose);
881 Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize =
882 toselects.get(opcheckpoint);
883 SimExecutionEdge seedge =
884 tooptimize.values().iterator().next().elementAt(0);
885 SimExecutionNode lastpredicatenode = seedge.getLastpredicateNode();
886 SimExecutionEdge lastpredicateedge = seedge.getLastpredicateEdge();
887 long timepoint = lastpredicatenode.getTimepoint();
888 if(lastpredicateedge.getTd() == null) {
890 timepoint += lastpredicateedge.getWeight();
892 // mapping to critical path
893 for(int index = 0; index < criticalPath.size(); index++) {
894 SimExecutionEdge tmpseedge = criticalPath.elementAt(index);
895 SimExecutionNode tmpsenode =
896 (SimExecutionNode)tmpseedge.getTarget();
897 if(tmpsenode.getTimepoint() > timepoint) {
898 // get the spare core info
899 sparecores = tmpsenode.getSpareCores();
904 if(tooptimize.size() > 0) {
905 Iterator<Integer> it_cores = tooptimize.keySet().iterator();
906 // check if it is possible to optimize these tasks
907 if((sparecores == null) || (sparecores.size() == 0)) {
908 // lack of spare cores
909 while(it_cores.hasNext()) {
910 int corenum = it_cores.next();
911 Vector<SimExecutionEdge> tmptasks = tooptimize.get(corenum);
912 // group the task instantiations according to whether it
913 // has backward data dependences or not
914 Vector<SimExecutionEdge> candidatetasks = new Vector();
915 for(int ii= 0; ii < tmptasks.size(); ii++) {
916 SimExecutionEdge tmpseedge = tmptasks.elementAt(ii);
917 SimExecutionNode target = (SimExecutionNode)tmpseedge.getTarget();
918 Vector<SimExecutionEdge> children =
919 (Vector<SimExecutionEdge>)target.getEdgeVector();
921 for(; jj < children.size(); jj++) {
922 SimExecutionEdge tmpedge = children.elementAt(jj);
923 if(tmpedge.getTd() != null) {
924 Vector<SimExecutionEdge> predicates =
925 tmpedge.getPredicates();
926 if((predicates != null) &&
927 (predicates.contains(tmpseedge))) {
931 } else if(tmpedge.getWeight() != 0) {
933 if(((SimExecutionNode)tmpedge.getTarget()).getTimepoint()
934 == tmpedge.getWeight() + target.getTimepoint()) {
939 if(jj == children.size()) {
940 candidatetasks.add(tmpseedge);
943 if((candidatetasks.size() > 0) &&
944 (candidatetasks.size() < tmptasks.size())) {
945 // there are less important tasks which have no backward
946 // data dependences at this timepoint, try to change
947 // original execution order
948 Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize2 =
949 new Hashtable<Integer, Vector<SimExecutionEdge>>();
950 tooptimize2.put(corenum, candidatetasks);
951 Vector<Vector<ScheduleNode>> ops =
952 innerOptimizeCriticalPath(scheduleGraph,
958 if(optimizeschedulegraphs == null) {
959 optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
961 optimizeschedulegraphs.addAll(ops);
969 candidatetasks = null;
974 return optimizeschedulegraphs;
977 // flush the dependences and earliest start time
978 if(!state.BAMBOOCOMPILETIME) {
979 it_cores = tooptimize.keySet().iterator();
980 while(it_cores.hasNext()) {
981 int corenum = it_cores.next();
982 Vector<SimExecutionEdge> edgevec =
983 tooptimize.get(corenum);
984 for(int j = 0; j < edgevec.size(); j++) {
985 SimExecutionEdge edge = edgevec.elementAt(j);
986 lastpredicateedge = edge.getLastpredicateEdge();
987 lastpredicatenode = edge.getLastpredicateNode();
988 // if(edge.getCoreNum() != lastpredicate.getCoreNum()) // should never hit this
989 timepoint = lastpredicatenode.getTimepoint();
990 if(lastpredicateedge.getTd() == null) {
992 timepoint += lastpredicateedge.getWeight();
994 // mapping to critical path
995 for(int index = 0; index < criticalPath.size(); index++) {
996 SimExecutionEdge tmpseedge = criticalPath.elementAt(index);
997 SimExecutionNode tmpsenode =
998 (SimExecutionNode)tmpseedge.getTarget();
999 if(tmpsenode.getTimepoint() > timepoint) {
1000 // update the predicate info
1001 if(edge.getPredicates() != null) {
1002 edge.getPredicates().remove(lastpredicateedge);
1004 edge.addPredicate(criticalPath.elementAt(index));
1012 computeBestStartPoint(criticalPath);
1013 Vector<Vector<ScheduleNode>> ops = optimizeCriticalPath(scheduleGraph,
1018 if(optimizeschedulegraphs == null) {
1019 optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
1021 optimizeschedulegraphs.addAll(ops);
1028 // there are spare cores, try to reorganize the tasks to the spare
1030 Vector<Vector<ScheduleNode>> ops =
1031 innerOptimizeCriticalPath(scheduleGraph,
1037 if(optimizeschedulegraphs == null) {
1038 optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
1040 optimizeschedulegraphs.addAll(ops);
1054 return optimizeschedulegraphs;
1057 private Vector<Vector<ScheduleNode>>
1058 innerOptimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
1059 Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize,
1060 Vector<Integer> sparecores,
1065 Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
1067 // first clone the whole graph
1068 Vector<ScheduleNode> newscheduleGraph =
1069 cloneScheduleGraph(scheduleGraph, lgid);
1071 if(newscheduleGraph.size() == 0) {
1072 //System.err.println("empty schedule graph!");
1073 return optimizeschedulegraphs;
1076 // these nodes are root nodes
1077 Vector<ScheduleNode> roots = new Vector<ScheduleNode>();
1078 for(int i = 0; i < newscheduleGraph.size(); i++) {
1079 if((sparecores == null) || (sparecores.contains(i))) {
1080 roots.add(newscheduleGraph.elementAt(i));
1084 // map the tasks associated to SimExecutionedges to original
1085 // ClassNode in the ScheduleGraph and split them from previous
1087 Vector<ScheduleNode> tocombines = new Vector<ScheduleNode>();
1088 Iterator<Integer> it_cores = tooptimize.keySet().iterator();
1089 while(it_cores.hasNext()) {
1090 int corenum = it_cores.next();
1091 Vector<SimExecutionEdge> candidatetasks =
1092 tooptimize.get(corenum);
1093 for(int i = 0; i < candidatetasks.size(); i++) {
1094 TaskDescriptor td = candidatetasks.elementAt(i).getTd();
1095 // TODO: currently do not consider multi-param tasks
1096 if(td.numParameters() == 1) {
1097 ClassDescriptor cd = td.getParamType(0).getClassDesc();
1098 ScheduleNode snode = newscheduleGraph.elementAt(corenum); // corresponding ScheduleNode
1099 Iterator<ClassNode> it_cnodes = snode.getClassNodesIterator();
1100 ClassNode tosplit = null;
1101 while(it_cnodes.hasNext()) {
1102 ClassNode cnode = it_cnodes.next();
1103 if(cnode.getClassDescriptor().equals(cd)) {
1111 ScheduleNode splitnode = snode.spliteClassNode(tosplit);
1112 newscheduleGraph.add(splitnode);
1113 tocombines.add(splitnode);
1117 candidatetasks = null;
1121 if(tocombines.size() == 0) {
1122 return optimizeschedulegraphs;
1125 SchedulingUtil.assignCids(newscheduleGraph);
1127 // get all the ScheduleEdge
1128 Vector<ScheduleEdge> scheduleEdges = new Vector<ScheduleEdge>();
1129 for(int i= 0; i < newscheduleGraph.size(); i++) {
1130 scheduleEdges.addAll(
1131 (Vector<ScheduleEdge>)newscheduleGraph.elementAt(i).getEdgeVector());
1134 Vector<Vector<ScheduleNode>> rootNodes =
1135 SchedulingUtil.rangeScheduleNodes(roots);
1136 if(rootNodes == null) {
1137 return optimizeschedulegraphs;
1139 Vector<Vector<ScheduleNode>> nodes2combine =
1140 SchedulingUtil.rangeScheduleNodes(tocombines);
1141 if(nodes2combine == null) {
1142 return optimizeschedulegraphs;
1145 CombinationUtil.CombineGenerator cGen =
1146 CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine);
1147 Random rand = new Random();
1148 while ((left > 0) && (cGen.nextGen())) {
1149 //while ((left > 0) && (cGen.randomGenE())) {
1150 if(Math.abs(rand.nextInt()) % 100 > this.generateThreshold) {
1151 Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
1152 Vector<ScheduleNode> sNodes =
1153 SchedulingUtil.generateScheduleGraph(this.state,
1159 if(optimizeschedulegraphs == null) {
1160 optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
1162 optimizeschedulegraphs.add(sNodes);
1169 for(int i = 0; i < rootNodes.size(); i++) {
1170 if(rootNodes.elementAt(i) != null) {
1171 rootNodes.elementAt(i).clear();
1175 for(int i = 0; i < nodes2combine.size(); i++) {
1176 if(nodes2combine.elementAt(i) != null) {
1177 nodes2combine.elementAt(i).clear();
1180 nodes2combine = null;
1181 for(int j = 0; j < newscheduleGraph.size(); j++) {
1182 ScheduleNode snode = newscheduleGraph.elementAt(j);
1183 snode.getEdgeVector().clear();
1184 snode.getInedgeVector().clear();
1185 snode.getScheduleEdges().clear();
1186 snode.getClassNodes().clear();
1188 newscheduleGraph = null;
1189 scheduleEdges.clear();
1190 scheduleEdges = null;
1194 return optimizeschedulegraphs;
1197 private Vector<ScheduleNode>
1198 cloneScheduleGraph(Vector<ScheduleNode> scheduleGraph,
1200 Vector<ScheduleNode> result = new Vector<ScheduleNode>();
1202 // get all the ScheduleEdge
1203 Vector<ScheduleEdge> scheduleEdges = new Vector<ScheduleEdge>();
1204 for(int i= 0; i < scheduleGraph.size(); i++) {
1205 scheduleEdges.addAll(
1206 (Vector<ScheduleEdge>)scheduleGraph.elementAt(i).getEdgeVector());
1208 Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash =
1209 new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
1210 Hashtable<ScheduleNode, ScheduleNode> sn2sn =
1211 new Hashtable<ScheduleNode, ScheduleNode>();
1212 SchedulingUtil.cloneScheduleGraph(scheduleGraph,
1219 SchedulingUtil.assignCids(result);
1220 scheduleEdges.clear();
1221 scheduleEdges = null;
1230 private Vector<Schedule>
1231 generateScheduling(Vector<ScheduleNode> scheduleGraph,
1232 Hashtable<TaskDescriptor, ClassDescriptor> td2maincd) {
1233 Hashtable<TaskDescriptor, Vector<Schedule>> td2cores =
1234 new Hashtable<TaskDescriptor, Vector<Schedule>>(); // tasks reside on which cores
1235 Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
1236 // for each ScheduleNode create a schedule node representing a core
1237 Hashtable<ScheduleNode, Integer> sn2coreNum =
1238 new Hashtable<ScheduleNode, Integer>();
1239 Hashtable<TaskDescriptor, Integer> td2maincore =
1240 new Hashtable<TaskDescriptor, Integer>();
1241 Hashtable<TaskDescriptor, Vector<Schedule>> td2allycores =
1242 new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks --
1243 // ally cores which might have parameters
1247 for(j = 0; j < scheduleGraph.size(); j++) {
1248 sn2coreNum.put(scheduleGraph.elementAt(j), j);
1250 int startupcore = 0;
1251 boolean setstartupcore = false;
1252 Schedule startup = null;
1253 int gid = scheduleGraph.elementAt(0).getGid();
1254 for(j = 0; j < scheduleGraph.size(); j++) {
1255 Schedule tmpSchedule = new Schedule(j, gid);
1256 ScheduleNode sn = scheduleGraph.elementAt(j);
1258 Vector<ClassNode> cNodes = sn.getClassNodes();
1259 for(int k = 0; k < cNodes.size(); k++) {
1260 ClassNode cNode = cNodes.elementAt(k);
1261 ClassDescriptor cd = cNode.getClassDescriptor();
1262 Iterator it_flags = cNode.getFlags();
1263 while(it_flags.hasNext()) {
1264 FlagState fs = (FlagState)it_flags.next();
1265 Iterator it_edges = fs.edges();
1266 while(it_edges.hasNext()) {
1267 FEdge tmpfe = (FEdge)it_edges.next();
1268 TaskDescriptor td = (tmpfe).getTask();
1269 boolean contain = true;
1270 if(td.numParameters() > 1) {
1271 // td is a multi-param task, check if this core contains the
1273 ClassDescriptor cd1 = td2maincd.get(td);
1274 if(td2maincd.get(td).equals(cd)) {
1276 td2maincore.put(td, tmpSchedule.getCoreNum());
1279 if(!td2allycores.containsKey(td)) {
1280 td2allycores.put(td, new Vector<Schedule>());
1282 Vector<Schedule> allycores = td2allycores.get(td);
1283 if(!allycores.contains(tmpSchedule)) {
1284 allycores.addElement(tmpSchedule);
1288 // If the FlagState can be fed to some multi-param tasks,
1289 // need to record corresponding ally cores later.
1290 tmpSchedule.addFState4TD(td, fs);
1293 tmpSchedule.addTask(td);
1294 if(!td2cores.containsKey(td)) {
1295 td2cores.put(td, new Vector<Schedule>());
1297 Vector<Schedule> tmpcores = td2cores.get(td);
1298 if(!tmpcores.contains(tmpSchedule)) {
1299 tmpcores.add(tmpSchedule);
1303 if(td.getParamType(0).getClassDesc().getSymbol().equals(
1304 TypeUtil.StartupClass)) {
1305 assert(!setstartupcore);
1307 startup = tmpSchedule;
1308 setstartupcore = true;
1317 // For each of the ScheduleEdge out of this ScheduleNode, add the
1318 // target ScheduleNode into the queue inside sn
1319 Iterator it_edges = sn.edges();
1320 while(it_edges.hasNext()) {
1321 ScheduleEdge se = (ScheduleEdge)it_edges.next();
1322 ScheduleNode target = (ScheduleNode)se.getTarget();
1323 Integer targetcore = sn2coreNum.get(target);
1324 switch(se.getType()) {
1325 case ScheduleEdge.NEWEDGE: {
1326 FlagState fs = se.getFstate();
1327 // Check if the new obj could be fed to some
1328 // multi-parameter task, if so, add for ally cores
1330 Iterator it = fs.edges();
1331 boolean canTriggerSTask = false; // Flag indicates if fs can trigger
1332 // some single-param task
1333 while(it.hasNext()) {
1334 TaskDescriptor td = ((FEdge)it.next()).getTask();
1335 if(td.numParameters() > 1) {
1336 tmpSchedule.addFState4TD(td, fs); // TODO
1337 // add this core as a allycore of td
1338 if(!td2allycores.containsKey(td)) {
1339 td2allycores.put(td, new Vector<Schedule>());
1341 Vector<Schedule> allycores = td2allycores.get(td);
1342 if(!allycores.contains(tmpSchedule)) {
1343 allycores.addElement(tmpSchedule);
1346 canTriggerSTask = true;
1349 if(canTriggerSTask) {
1350 // Only transfer the obj when it can trigger some single-parm task
1351 // TODO: ensure that multi-param tasks have these objects
1352 for(int k = 0; k < se.getNewRate(); k++) {
1353 tmpSchedule.addTargetCore(fs, targetcore);
1359 case ScheduleEdge.TRANSEDGE: {
1361 tmpSchedule.addTargetCore(se.getFstate(),
1363 se.getTargetFState());
1364 // check if missed some FlagState associated with some
1365 // multi-parameter task, which has been cloned when
1366 // splitting a ClassNode
1367 FlagState fs = se.getSourceFState();
1368 FlagState tfs = se.getTargetFState();
1369 Iterator it = tfs.edges();
1370 while(it.hasNext()) {
1371 TaskDescriptor td = ((FEdge)it.next()).getTask();
1372 if(td.numParameters() > 1) {
1373 tmpSchedule.addFState4TD(td, fs);
1374 // add this core as a allycore of td
1375 if(!td2allycores.containsKey(td)) {
1376 td2allycores.put(td, new Vector<Schedule>());
1378 Vector<Schedule> allycores = td2allycores.get(td);
1379 if(!allycores.contains(tmpSchedule)) {
1380 allycores.addElement(tmpSchedule);
1388 it_edges = sn.getScheduleEdgesIterator();
1389 while(it_edges.hasNext()) {
1390 ScheduleEdge se = (ScheduleEdge)it_edges.next();
1391 switch(se.getType()) {
1392 case ScheduleEdge.NEWEDGE: {
1393 // TODO, added 09/07/06
1394 FlagState fs = se.getFstate();
1395 // Check if the new obj could be fed to some
1396 // multi-parameter task, if so, add for ally cores
1398 Iterator it = fs.edges();
1399 boolean canTriggerSTask = false; // Flag indicates if fs can trigger
1400 // some single-param task
1401 while(it.hasNext()) {
1402 TaskDescriptor td = ((FEdge)it.next()).getTask();
1403 if(td.numParameters() > 1) {
1404 tmpSchedule.addFState4TD(td, fs); // TODO
1405 // add this core as a allycore of td
1406 if(!td2allycores.containsKey(td)) {
1407 td2allycores.put(td, new Vector<Schedule>());
1409 Vector<Schedule> allycores = td2allycores.get(td);
1410 if(!allycores.contains(tmpSchedule)) {
1411 allycores.addElement(tmpSchedule);
1414 canTriggerSTask = true;
1417 if(canTriggerSTask) {
1418 for(int k = 0; k < se.getNewRate(); k++) {
1419 tmpSchedule.addTargetCore(se.getFstate(), j);
1425 case ScheduleEdge.TRANSEDGE: {
1427 tmpSchedule.addTargetCore(se.getFstate(),
1429 se.getTargetFState());
1430 // check if missed some FlagState associated with some
1431 // multi-parameter task, which has been cloned when
1432 // splitting a ClassNode
1433 FlagState fs = se.getSourceFState();
1434 FlagState tfs = se.getTargetFState();
1435 Iterator it = tfs.edges();
1436 while(it.hasNext()) {
1437 TaskDescriptor td = ((FEdge)it.next()).getTask();
1438 if(td.numParameters() > 1) {
1439 tmpSchedule.addFState4TD(td, fs);
1440 // add this core as a allycore of td
1441 if(!td2allycores.containsKey(td)) {
1442 td2allycores.put(td, new Vector<Schedule>());
1444 Vector<Schedule> allycores = td2allycores.get(td);
1445 if(!allycores.contains(tmpSchedule)) {
1446 allycores.addElement(tmpSchedule);
1455 scheduling.add(tmpSchedule);
1458 int number = this.coreNum;
1459 if(scheduling.size() < number) {
1460 number = scheduling.size();
1463 Iterator<TaskDescriptor> it_mptds = td2maincd.keySet().iterator();
1464 while(it_mptds.hasNext()) {
1465 TaskDescriptor td = it_mptds.next();
1466 Vector<FEdge> fes = (Vector<FEdge>) this.taskAnalysis.getFEdgesFromTD(td);
1467 Vector<Schedule> cores = td2cores.get(td);
1468 assert(cores.size() == 1); // should have only one core
1469 for(int k = 0; k < cores.size(); ++k) {
1470 Schedule tmpSchedule = cores.elementAt(k);
1472 // Make sure all the parameter objs of a multi-parameter
1473 // task would be send to right place after the task finished
1474 for(int h = 0; h < fes.size(); ++h) {
1475 FEdge tmpfe = fes.elementAt(h);
1476 FlagState tmpfs = (FlagState)tmpfe.getTarget();
1477 Vector<TaskDescriptor> tmptds = new Vector<TaskDescriptor>();
1478 if((tmpSchedule.getTargetCoreTable() == null)
1479 || (!tmpSchedule.getTargetCoreTable().containsKey(tmpfs))) {
1480 // add up all possible cores' info
1481 Iterator it_edges = tmpfs.edges();
1482 while(it_edges.hasNext()) {
1483 TaskDescriptor tmptd = ((FEdge)it_edges.next()).getTask();
1484 if(!tmptds.contains(tmptd)) {
1486 // only multiparam task will be processed here!!! TODO
1487 Vector<Schedule> tmpcores = td2cores.get(tmptd);
1488 for(int m = 0; m < tmpcores.size(); ++m) {
1489 Schedule target = tmpcores.elementAt(m);
1490 int targetcore = target.getCoreNum();
1491 int num = target.getTaskNum(tmptd);
1492 for(int n = 0; n < num; n++) {
1493 tmpSchedule.addTargetCore(tmpfs, targetcore);
1507 // Make sure all objs which could be feed to a multi-parameter
1508 // task would be send to all the possible task instances
1509 it_mptds = td2allycores.keySet().iterator();
1510 while(it_mptds.hasNext()) {
1511 TaskDescriptor td = it_mptds.next();
1512 Vector<Schedule> allycores = td2allycores.get(td);
1513 for(int i = 0; i < allycores.size(); i++) {
1514 Schedule tSchedule = allycores.elementAt(i);
1515 Vector<FlagState> tmpfss = tSchedule.getFStates4TD(td);
1516 int targetcore = td2maincore.get(td).intValue();
1517 for(int h = 0; h < tmpfss.size(); ++h) {
1518 tSchedule.addAllyCore(tmpfss.elementAt(h), targetcore);
1527 td2allycores = null;