ScheduleSimulator scheduleSimulator;
int coreNum;
- int scheduleThreshold;
- int probThreshold;
- int generateThreshold;
+ int scheduleThreshold; // how many starting points generated by schedule analysis
+ int probThreshold; // the probability to stop when no accelaration achieved in the
+ // directed simulated annealing
+ int generateThreshold; // how many optimized implementation generated in each iteration
+ // of the directed simulated annealing
- //Random rand;
-
public MCImplSynthesis(State state,
TaskAnalysis ta,
OwnershipAnalysis oa) {
this.scheduleThreshold = 1000;
this.probThreshold = 0;
this.generateThreshold = 30;
- //this.rand = new Random();
}
public int getCoreNum() {
// for later restoration.
PrintStream origOut = System.out;
- // Create a new output stream for the standard output.
+ // Create a new output stream for the stcriticalPathandard output.
PrintStream stdout = null;
try {
stdout = new PrintStream(
// Set the System out and err streams to use our replacements.
System.setOut(stdout);
- // generate multiple schedulings
- this.scheduleAnalysis.setScheduleThreshold(1000);
- this.scheduleAnalysis.schedule(20);
- this.generateThreshold = 5;
- this.probThreshold = 0;
+ if(false) {
+ this.scheduleAnalysis.setScheduleThreshold(100000);
+ this.scheduleAnalysis.schedule(-1);
- Vector<Vector<ScheduleNode>> scheduleGraphs = null;
- Vector<Vector<ScheduleNode>> totestscheduleGraphs =
- this.scheduleAnalysis.getScheduleGraphs();
- Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
- Vector<Integer> selectedSchedulings = new Vector<Integer>();
- Vector<Vector<SimExecutionEdge>> selectedSimExeGraphs =
- new Vector<Vector<SimExecutionEdge>>();
-
- // check all multi-parameter tasks
- Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
- Iterator it_tasks = this.state.getTaskSymbolTable().getDescriptorsIterator();
- while(it_tasks.hasNext()) {
- TaskDescriptor td = (TaskDescriptor)it_tasks.next();
- if(td.numParameters() > 1) {
- multiparamtds.addElement(td);
- }
- }
- it_tasks = null;
-
- File file=new File(this.state.outputdir + "distributeinfo_s_" + this.coreNum + ".out");
- FileOutputStream dotstream = null;
- File file2=new File(this.state.outputdir + "distributeinfo_o_" + this.coreNum + ".out");
- FileOutputStream dotstream2 = null;
- try {
- dotstream = new FileOutputStream(file,false);
- dotstream2 = new FileOutputStream(file2,false);
- } catch (Exception e) {
- e.printStackTrace();
- System.exit(-1);
- }
- PrintWriter output = new java.io.PrintWriter(dotstream, true);
- PrintWriter output2 = new java.io.PrintWriter(dotstream2, true);
- output.println("start time(1,000,000 cycles): " + totestscheduleGraphs.size());
- output2.println("optimized time(1,000,000 cycles): " + totestscheduleGraphs.size());
- for(int ii = 0; ii < 1/*totestscheduleGraphs.size()*/; ii++) {
- Vector<Vector<ScheduleNode>> newscheduleGraphs =
- new Vector<Vector<ScheduleNode>>();
- newscheduleGraphs.add(totestscheduleGraphs.elementAt(ii));
- int tryindex = 1;
- int bestexetime = Integer.MAX_VALUE;
- int gid = 1;
- Vector<Schedule> scheduling = null;
- Vector<ScheduleNode> schedulinggraph = null;
- boolean isfirst = true;
- Random rand = new Random();
- // simulate the generated schedulings and try to optimize it
- System.out.print("=========================================================\n");
- System.out.print("# " + ii + ": \n");
- do {
- System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
- System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
- gid += newscheduleGraphs.size();
- if(scheduleGraphs != null) {
- for(int i = 0; i < scheduleGraphs.size(); i++) {
- Vector<ScheduleNode> tmpgraph = scheduleGraphs.elementAt(i);
- for(int j = 0; j < tmpgraph.size(); j++) {
- ScheduleNode snode = tmpgraph.elementAt(j);
- snode.getEdgeVector().clear();
- snode.getInedgeVector().clear();
- snode.getScheduleEdges().clear();
- snode.getClassNodes().clear();
- }
- tmpgraph.clear();
- tmpgraph = null;
- }
- scheduleGraphs.clear();
+ Vector<Vector<ScheduleNode>> totestscheduleGraphs =
+ this.scheduleAnalysis.getScheduleGraphs();
+ Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
+ Vector<Integer> selectedSchedulings = new Vector<Integer>();
+ Vector<Vector<SimExecutionEdge>> selectedSimExeGraphs =
+ new Vector<Vector<SimExecutionEdge>>();
+
+ // check all multi-parameter tasks
+ Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
+ Iterator it_tasks = this.state.getTaskSymbolTable().getDescriptorsIterator();
+ while(it_tasks.hasNext()) {
+ TaskDescriptor td = (TaskDescriptor)it_tasks.next();
+ if(td.numParameters() > 1) {
+ multiparamtds.addElement(td);
}
- scheduleGraphs = newscheduleGraphs;
+ }
+ it_tasks = null;
+
+ File file=new File(this.state.outputdir + "distributeinfo_s_" + this.coreNum + ".out");
+ FileOutputStream dotstream = null;
+ try {
+ dotstream = new FileOutputStream(file,false);
+ } catch (Exception e) {
+ e.printStackTrace();
+ System.exit(-1);
+ }
+ PrintWriter output = new java.io.PrintWriter(dotstream, true);
+ output.println("start time(1,000,000 cycles): " + totestscheduleGraphs.size());
+ for(int ii = 0; ii < totestscheduleGraphs.size(); ii++) {
+ Vector<Vector<ScheduleNode>> newscheduleGraphs =
+ new Vector<Vector<ScheduleNode>>();
+ newscheduleGraphs.add(totestscheduleGraphs.elementAt(ii));
+ // simulate the generated schedulings and try to optimize it
schedulings.clear();
// get scheduling layouts from schedule graphs
- for(int i = 0; i < scheduleGraphs.size(); i++) {
- Vector<ScheduleNode> scheduleGraph = scheduleGraphs.elementAt(i);
+ for(int i = 0; i < newscheduleGraphs.size(); i++) {
+ Vector<ScheduleNode> scheduleGraph = newscheduleGraphs.elementAt(i);
Vector<Schedule> tmpscheduling =
generateScheduling(scheduleGraph, multiparamtds);
schedulings.add(tmpscheduling);
}
selectedSimExeGraphs.clear();
int tmpexetime = this.scheduleSimulator.simulate(schedulings,
- selectedSchedulings,
- selectedSimExeGraphs);
- if(isfirst) {
- output.println(((float)tmpexetime/1000000));
- isfirst = false;
+ selectedSchedulings,
+ selectedSimExeGraphs);
+ output.println(((float)tmpexetime/1000000));
+ }
+ } else {
+ // generate multiple schedulings
+ this.scheduleThreshold = 20;
+ this.generateThreshold = 30;
+ this.probThreshold = 0;
+ this.scheduleAnalysis.setScheduleThreshold(1000);
+ this.scheduleAnalysis.schedule(this.generateThreshold);
+
+ Vector<Vector<ScheduleNode>> scheduleGraphs = null;
+ Vector<Vector<ScheduleNode>> totestscheduleGraphs =
+ this.scheduleAnalysis.getScheduleGraphs();
+ Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
+ Vector<Integer> selectedSchedulings = new Vector<Integer>();
+ Vector<Vector<SimExecutionEdge>> selectedSimExeGraphs =
+ new Vector<Vector<SimExecutionEdge>>();
+
+ // check all multi-parameter tasks
+ Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
+ Iterator it_tasks = this.state.getTaskSymbolTable().getDescriptorsIterator();
+ while(it_tasks.hasNext()) {
+ TaskDescriptor td = (TaskDescriptor)it_tasks.next();
+ if(td.numParameters() > 1) {
+ multiparamtds.addElement(td);
}
- if(tmpexetime < bestexetime) {
- bestexetime = tmpexetime;
- if(scheduling != null) {
- scheduling.clear();
- for(int j = 0; j < schedulinggraph.size(); j++) {
- ScheduleNode snode = schedulinggraph.elementAt(j);
- snode.getEdgeVector().clear();
- snode.getInedgeVector().clear();
- snode.getScheduleEdges().clear();
- snode.getClassNodes().clear();
+ }
+ it_tasks = null;
+
+ File file=new File(this.state.outputdir + "distributeinfo_s_" + this.coreNum + ".out");
+ FileOutputStream dotstream = null;
+ File file2=new File(this.state.outputdir + "distributeinfo_o_" + this.coreNum + ".out");
+ FileOutputStream dotstream2 = null;
+ try {
+ dotstream = new FileOutputStream(file,false);
+ dotstream2 = new FileOutputStream(file2,false);
+ } catch (Exception e) {
+ e.printStackTrace();
+ System.exit(-1);
+ }
+ PrintWriter output = new java.io.PrintWriter(dotstream, true);
+ PrintWriter output2 = new java.io.PrintWriter(dotstream2, true);
+ output.println("start time(1,000,000 cycles): " + totestscheduleGraphs.size());
+ output2.println("optimized time(1,000,000 cycles): " + totestscheduleGraphs.size());
+ for(int ii = 0; ii < totestscheduleGraphs.size(); ii++) {
+ Vector<Vector<ScheduleNode>> newscheduleGraphs =
+ new Vector<Vector<ScheduleNode>>();
+ newscheduleGraphs.add(totestscheduleGraphs.elementAt(ii));
+ int tryindex = 1;
+ int bestexetime = Integer.MAX_VALUE;
+ int gid = 1;
+ Vector<Schedule> scheduling = null;
+ Vector<ScheduleNode> schedulinggraph = null;
+ boolean isfirst = true;
+ Random rand = new Random();
+ // simulate the generated schedulings and try to optimize it
+ System.out.print("=========================================================\n");
+ System.out.print("# " + ii + ": \n");
+ do {
+ System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
+ System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
+ gid += newscheduleGraphs.size();
+ if(scheduleGraphs != null) {
+ for(int i = 0; i < scheduleGraphs.size(); i++) {
+ Vector<ScheduleNode> tmpgraph = scheduleGraphs.elementAt(i);
+ for(int j = 0; j < tmpgraph.size(); j++) {
+ ScheduleNode snode = tmpgraph.elementAt(j);
+ snode.getEdgeVector().clear();
+ snode.getInedgeVector().clear();
+ snode.getScheduleEdges().clear();
+ snode.getClassNodes().clear();
+ }
+ tmpgraph.clear();
+ tmpgraph = null;
}
- schedulinggraph.clear();
+ scheduleGraphs.clear();
}
- scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0));
- schedulinggraph = scheduleGraphs.elementAt(selectedSchedulings.elementAt(0));
- tryindex++;
- System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n");
- System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
- } else if(tmpexetime == bestexetime) {
- System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n");
- System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
- tryindex++;
- if((Math.abs(rand.nextInt()) % 100) < this.probThreshold) {
+ scheduleGraphs = newscheduleGraphs;
+ schedulings.clear();
+ // get scheduling layouts from schedule graphs
+ for(int i = 0; i < scheduleGraphs.size(); i++) {
+ Vector<ScheduleNode> scheduleGraph = scheduleGraphs.elementAt(i);
+ Vector<Schedule> tmpscheduling =
+ generateScheduling(scheduleGraph, multiparamtds);
+ schedulings.add(tmpscheduling);
+ scheduleGraph = null;
+ tmpscheduling = null;
+ }
+ selectedSchedulings.clear();
+ for(int i = 0; i < selectedSimExeGraphs.size(); i++) {
+ Vector<SimExecutionEdge> tmpgraph =
+ selectedSimExeGraphs.elementAt(i);
+ for(int j = 0; j < tmpgraph.size(); j++) {
+ tmpgraph.elementAt(j).destroy();
+ }
+ tmpgraph.clear();
+ }
+ selectedSimExeGraphs.clear();
+ int tmpexetime = this.scheduleSimulator.simulate(schedulings,
+ selectedSchedulings,
+ selectedSimExeGraphs);
+ if(isfirst) {
+ output.println(((float)tmpexetime/1000000));
+ isfirst = false;
+ }
+ if(tmpexetime < bestexetime) {
+ bestexetime = tmpexetime;
+ if(scheduling != null) {
+ scheduling.clear();
+ for(int j = 0; j < schedulinggraph.size(); j++) {
+ ScheduleNode snode = schedulinggraph.elementAt(j);
+ snode.getEdgeVector().clear();
+ snode.getInedgeVector().clear();
+ snode.getScheduleEdges().clear();
+ snode.getClassNodes().clear();
+ }
+ schedulinggraph.clear();
+ }
+ scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0));
+ schedulinggraph = scheduleGraphs.elementAt(selectedSchedulings.elementAt(0));
+ tryindex++;
+ System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n");
+ System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
+ } else if(tmpexetime == bestexetime) {
+ System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n");
+ System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
+ tryindex++;
+ if((Math.abs(rand.nextInt()) % 100) < this.probThreshold) {
+ break;
+ }
+ } else {
break;
}
- } else {
- break;
- }
- // try to optimize theschedulings best one scheduling
- newscheduleGraphs = optimizeScheduling(scheduleGraphs,
- selectedSchedulings,
- selectedSimExeGraphs,
- gid,
- this.scheduleThreshold);
- if(tmpexetime < bestexetime) {
- scheduleGraphs.remove(selectedSchedulings.elementAt(0));
+ // try to optimize theschedulings best one scheduling
+ newscheduleGraphs = optimizeScheduling(scheduleGraphs,
+ selectedSchedulings,
+ selectedSimExeGraphs,
+ gid,
+ this.scheduleThreshold);
+ if(tmpexetime < bestexetime) {
+ scheduleGraphs.remove(selectedSchedulings.elementAt(0));
+ }
+ }while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
+
+ scheduleGraphs.clear();
+ scheduleGraphs = null;
+ scheduling = null;
+ schedulinggraph = null;
+ if(newscheduleGraphs != null) {
+ newscheduleGraphs.clear();
+ }
+ newscheduleGraphs = null;
+ totestscheduleGraphs.elementAt(ii).clear();
+ for(int i = 0; i < schedulings.size(); i++) {
+ schedulings.elementAt(i).clear();
+ }
+ schedulings.clear();
+ selectedSchedulings.clear();
+ for(int i = 0; i < selectedSimExeGraphs.size(); i++) {
+ selectedSimExeGraphs.elementAt(i).clear();
}
- }while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
+ selectedSimExeGraphs.clear();
- scheduleGraphs.clear();
- scheduleGraphs = null;
- scheduling = null;
- schedulinggraph = null;
- if(newscheduleGraphs != null) {
- newscheduleGraphs.clear();
+ output2.println(((float)bestexetime/1000000));
+ System.out.print("=========================================================\n");
+ }
+
+ if(scheduleGraphs != null) {
+ scheduleGraphs.clear();
}
- newscheduleGraphs = null;
- totestscheduleGraphs.elementAt(ii).clear();
+ scheduleGraphs = null;
+ totestscheduleGraphs = null;
for(int i = 0; i < schedulings.size(); i++) {
schedulings.elementAt(i).clear();
}
schedulings.clear();
+ schedulings = null;
selectedSchedulings.clear();
- for(int i = 0; i < selectedSimExeGraphs.size(); i++) {
- selectedSimExeGraphs.elementAt(i).clear();
- }
+ selectedSchedulings = null;
selectedSimExeGraphs.clear();
-
- output2.println(((float)bestexetime/1000000));
- System.out.print("=========================================================\n");
- }
+ selectedSimExeGraphs = null;
+ multiparamtds.clear();
+ multiparamtds = null;
- if(scheduleGraphs != null) {
- scheduleGraphs.clear();
- }
- scheduleGraphs = null;
- totestscheduleGraphs = null;
- for(int i = 0; i < schedulings.size(); i++) {
- schedulings.elementAt(i).clear();
- }
- schedulings.clear();
- schedulings = null;
- selectedSchedulings.clear();
- selectedSchedulings = null;
- selectedSimExeGraphs.clear();
- selectedSimExeGraphs = null;
- multiparamtds.clear();
- multiparamtds = null;
- // Close the streams.
- try {
- output.close();
- stdout.close();
- output = null;
- stdout = null;
- System.setOut(origOut);
- } catch (Exception e) {
- origOut.println("Redirect: Unable to close files!");
+ // Close the streams.
+ try {
+ output.close();
+ stdout.close();
+ output = null;
+ stdout = null;
+ System.setOut(origOut);
+ } catch (Exception e) {
+ origOut.println("Redirect: Unable to close files!");
+ }
}
return;
return criticalPath;
}
- private void computeBestStartPoint(Vector<SimExecutionEdge> criticalPath) {
- // calculate the earliest start time of each task on the critial path
- for(int i = 0; i < criticalPath.size(); i++) {
- SimExecutionEdge seedge = criticalPath.elementAt(i);
- Vector<SimExecutionEdge> predicates = seedge.getPredicates();
- if(predicates != null) {
- // have predicates
- int starttime = 0;
- // check the latest finish time of all the predicates
- for(int j = 0; j < predicates.size(); j++) {
- SimExecutionEdge predicate = predicates.elementAt(j);
- int tmptime = predicate.getBestStartPoint() + predicate.getWeight();
- if(tmptime > starttime) {
- starttime = tmptime;
- seedge.setLastpredicateEdge(predicate);
- if(predicate.getTd() != null) {
- seedge.setLastpredicateNode((SimExecutionNode)predicate.getTarget());
- } else {
- // transfer edge
- seedge.setLastpredicateNode((SimExecutionNode)predicate.getSource());
- }
- }
- }
- seedge.setBestStartPoint(starttime);
- } else if(seedge.getSource().getInedgeVector().size() > 0) {
- // should have only one in edge
- int starttime = ((SimExecutionNode)seedge.getSource()).getTimepoint();
- seedge.setBestStartPoint(starttime);
- } else {
- // no predicates
- seedge.setBestStartPoint(0);
- }
- predicates = null;
- }
- }
-
// TODO: currently only get one critical path. It's possible that there are
// multiple critical paths and some of them can not be optimized while others
// can. Need to fix up for this situation.
subcriticalpath = null;
return sum;
}
+
+ private void computeBestStartPoint(Vector<SimExecutionEdge> criticalPath) {
+ // calculate the earliest start time of each task on the critial path
+ for(int i = 0; i < criticalPath.size(); i++) {
+ SimExecutionEdge seedge = criticalPath.elementAt(i);
+ Vector<SimExecutionEdge> predicates = seedge.getPredicates();
+ if(predicates != null) {
+ // have predicates
+ int starttime = 0;
+ // check the latest finish time of all the predicates
+ for(int j = 0; j < predicates.size(); j++) {
+ SimExecutionEdge predicate = predicates.elementAt(j);
+ int tmptime = predicate.getBestStartPoint() + predicate.getWeight();
+ if(tmptime > starttime) {
+ starttime = tmptime;
+ seedge.setLastpredicateEdge(predicate);
+ if(predicate.getTd() != null) {
+ seedge.setLastpredicateNode((SimExecutionNode)predicate.getTarget());
+ } else {
+ // transfer edge
+ seedge.setLastpredicateNode((SimExecutionNode)predicate.getSource());
+ }
+ }
+ }
+ seedge.setBestStartPoint(starttime);
+ } else if(seedge.getSource().getInedgeVector().size() > 0) {
+ // should have only one in edge
+ int starttime = ((SimExecutionNode)seedge.getSource()).getTimepoint();
+ seedge.setBestStartPoint(starttime);
+ } else {
+ // no predicates
+ seedge.setBestStartPoint(0);
+ }
+ predicates = null;
+ }
+ }
private Vector<Vector<ScheduleNode>> optimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
Vector<SimExecutionEdge> criticalPath,
// earliest start time and group them
int opcheckpoint = Integer.MAX_VALUE;
Vector<Integer> sparecores = null;
- // first group according to core index,
- // then group according to task type
- Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>> tooptimize =
- new Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>>();
+ // group according to core index
+ Hashtable<Integer, Hashtable<Integer, Vector<SimExecutionEdge>>> toselects =
+ new Hashtable<Integer, Hashtable<Integer, Vector<SimExecutionEdge>>>();
+ Random rand = new Random();
for(int i = 0; i < criticalPath.size(); i++) {
SimExecutionEdge seedge = criticalPath.elementAt(i);
int starttime = seedge.getBestStartPoint();
// consider to optimize it only when its predicates can NOT
// be optimized, otherwise first considering optimize its predicates
SimExecutionEdge lastpredicateedge = seedge.getLastpredicateEdge();
- if(lastpredicateedge.isFixedTime()) {
- if(opcheckpoint >= starttime) {
- // only consider the tasks with smallest best start time
- if(opcheckpoint > starttime) {
- tooptimize.clear();
- opcheckpoint = starttime;
- SimExecutionNode lastpredicatenode = seedge.getLastpredicateNode();
- int timepoint = lastpredicatenode.getTimepoint();
- if(lastpredicateedge.getTd() == null) {
- // transfer edge
- timepoint += lastpredicateedge.getWeight();
- }
- // mapping to critical path
- for(int index = 0; index < criticalPath.size(); index++) {
- SimExecutionEdge tmpseedge = criticalPath.elementAt(index);
- SimExecutionNode tmpsenode =
- (SimExecutionNode)tmpseedge.getTarget();
- if(tmpsenode.getTimepoint() > timepoint) {
- // get the spare core info
- sparecores = tmpsenode.getSpareCores();
- break;
- }
- }
- }
- int corenum = seedge.getCoreNum();
- if(!tooptimize.containsKey(corenum)) {
- tooptimize.put(corenum,
- new Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>());
- }
- if(!tooptimize.get(corenum).containsKey(seedge.getTd())) {
- tooptimize.get(corenum).put(seedge.getTd(),
- new Vector<SimExecutionEdge>());
- }
- tooptimize.get(corenum).get(seedge.getTd()).add(seedge);
+ if(lastpredicateedge.isFixedTime()) {
+ int corenum = seedge.getCoreNum();
+ if(!toselects.containsKey(starttime)) {
+ toselects.put(starttime,
+ new Hashtable<Integer, Vector<SimExecutionEdge>>());
+ }
+ if(!toselects.get(starttime).containsKey(corenum)) {
+ toselects.get(starttime).put(corenum,
+ new Vector<SimExecutionEdge>());
}
+ toselects.get(starttime).get(corenum).add(seedge);
}
}
}
+
+ // Randomly choose the tasks to optimize(previously only
+ // consider the tasks with smallest best start time)
+ Vector<Integer> keys = new Vector<Integer>(toselects.keySet());
+ do{
+ int length = keys.size();
+ if(length == 0) {
+ return optimizeschedulegraphs;
+ }
+ int tochoose = Math.abs(rand.nextInt()) % length;
+ opcheckpoint = (keys.elementAt(tochoose)).intValue();
+ keys.removeElementAt(tochoose);
+ Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize =
+ toselects.get(opcheckpoint);
+ SimExecutionEdge seedge = tooptimize.values().iterator().next().elementAt(0);
+ SimExecutionNode lastpredicatenode = seedge.getLastpredicateNode();
+ SimExecutionEdge lastpredicateedge = seedge.getLastpredicateEdge();
+ int timepoint = lastpredicatenode.getTimepoint();
+ if(lastpredicateedge.getTd() == null) {
+ // transfer edge
+ timepoint += lastpredicateedge.getWeight();
+ }
+ // mapping to critical path
+ for(int index = 0; index < criticalPath.size(); index++) {
+ SimExecutionEdge tmpseedge = criticalPath.elementAt(index);
+ SimExecutionNode tmpsenode =
+ (SimExecutionNode)tmpseedge.getTarget();
+ if(tmpsenode.getTimepoint() > timepoint) {
+ // get the spare core info
+ sparecores = tmpsenode.getSpareCores();
+ break;
+ }
+ }
- if(tooptimize.size() > 0) {
- Iterator<Integer> it_cores = tooptimize.keySet().iterator();
- // check if it is possible to optimize these tasks
- if((sparecores == null) || (sparecores.size() == 0)) {
- // lack of spare cores
- while(it_cores.hasNext()) {
- int corenum = it_cores.next();
- Hashtable<TaskDescriptor, Vector<SimExecutionEdge>> candidatetasks =
- tooptimize.get(corenum);
- if(candidatetasks.keySet().size() > 1) {
- // there are multiple tasks could be optimized to start from
- // this timepoint, try to change original execution order
- Iterator<TaskDescriptor> it_tds = candidatetasks.keySet().iterator();
- TaskDescriptor td = null;
- int starttime = Integer.MAX_VALUE;
- do {
- TaskDescriptor tmptd = it_tds.next();
- Vector<SimExecutionEdge> seedges = candidatetasks.get(td);
- int tmptime = ((SimExecutionNode)seedges.elementAt(0).getSource()).getTimepoint();
- for(int i = 1; i < seedges.size(); i++) {
- int ttime = ((SimExecutionNode)seedges.elementAt(i).getSource()).getTimepoint();
- if(ttime < tmptime) {
- tmptime = ttime;
+ if(tooptimize.size() > 0) {
+ Iterator<Integer> it_cores = tooptimize.keySet().iterator();
+ // check if it is possible to optimize these tasks
+ if((sparecores == null) || (sparecores.size() == 0)) {
+ // lack of spare cores
+ while(it_cores.hasNext()) {
+ int corenum = it_cores.next();
+ Vector<SimExecutionEdge> tmptasks = tooptimize.get(corenum);
+ // group the task instantiations according to whether it
+ // has backward data dependences or not
+ Vector<SimExecutionEdge> candidatetasks = new Vector();
+ for(int ii= 0; ii < tmptasks.size(); ii++) {
+ SimExecutionEdge tmpseedge = tmptasks.elementAt(ii);
+ SimExecutionNode target = (SimExecutionNode)tmpseedge.getTarget();
+ Vector<SimExecutionEdge> children =
+ (Vector<SimExecutionEdge>)target.getEdgeVector();
+ int jj = 0;
+ for(; jj < children.size(); jj++) {
+ SimExecutionEdge tmpedge = children.elementAt(jj);
+ if(tmpedge.getTd() != null) {
+ Vector<SimExecutionEdge> predicates =
+ tmpedge.getPredicates();
+ if((predicates != null) &&
+ (predicates.contains(tmpseedge))) {
+ break;
+ }
+ predicates = null;
+ } else if(tmpedge.getWeight() != 0) {
+ // transfer edge
+ if(((SimExecutionNode)tmpedge.getTarget()).getTimepoint()
+ == tmpedge.getWeight() + target.getTimepoint()) {
+ break;
+ }
}
}
- if(tmptime < starttime) {
- starttime = tmptime;
- td = tmptd;
+ if(jj == children.size()) {
+ candidatetasks.add(tmpseedge);
}
- seedges = null;
- }while(it_tds.hasNext());
- it_tds = null;
- // TODO: only consider non-multi-param tasks currently
- if(td.numParameters() == 1) {
- Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>> tooptimize2 =
- new Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>>();
+ }
+ if((candidatetasks.size() > 0) &&
+ (candidatetasks.size() < tmptasks.size())) {
+ // there are less important tasks which have no backward
+ // data dependences at this timepoint, try to change
+ // original execution order
+ Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize2 =
+ new Hashtable<Integer, Vector<SimExecutionEdge>>();
tooptimize2.put(corenum, candidatetasks);
Vector<Vector<ScheduleNode>> ops = innerOptimizeCriticalPath(scheduleGraph,
- tooptimize2,
- null,
- lgid,
- left);
+ tooptimize2,
+ null,
+ lgid,
+ left);
if(ops != null) {
if(optimizeschedulegraphs == null) {
optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
}
optimizeschedulegraphs.addAll(ops);
- lgid += optimizeschedulegraphs.size();
- left -= optimizeschedulegraphs.size();
+ lgid += ops.size();
+ left -= ops.size();
}
- tooptimize2.clear();
tooptimize2 = null;
ops = null;
}
+ tmptasks = null;
+ candidatetasks = null;
+ }
+
+ if(left == 0) {
+ it_cores = null;
+ return optimizeschedulegraphs;
}
- candidatetasks = null;
- }
-
- if(left == 0) {
- it_cores = null;
- return optimizeschedulegraphs;
- }
- // flush the dependences and earliest start time
- it_cores = tooptimize.keySet().iterator();
- while(it_cores.hasNext()) {
- Hashtable<TaskDescriptor, Vector<SimExecutionEdge>> candidatetasks =
- tooptimize.get(it_cores.next());
- Iterator<Vector<SimExecutionEdge>> it_edgevecs =
- candidatetasks.values().iterator();
- while(it_edgevecs.hasNext()) {
- Vector<SimExecutionEdge> edgevec = it_edgevecs.next();
+ // flush the dependences and earliest start time
+ it_cores = tooptimize.keySet().iterator();
+ while(it_cores.hasNext()) {
+ int corenum = it_cores.next();
+ Vector<SimExecutionEdge> edgevec =
+ tooptimize.get(corenum);
for(int j = 0; j < edgevec.size(); j++) {
SimExecutionEdge edge = edgevec.elementAt(j);
- SimExecutionEdge lastpredicateedge = edge.getLastpredicateEdge();
- SimExecutionNode lastpredicatenode = edge.getLastpredicateNode();
+ lastpredicateedge = edge.getLastpredicateEdge();
+ lastpredicatenode = edge.getLastpredicateNode();
// if(edge.getCoreNum() != lastpredicate.getCoreNum()) // should never hit this
- int timepoint = lastpredicatenode.getTimepoint();
+ timepoint = lastpredicatenode.getTimepoint();
if(lastpredicateedge.getTd() == null) {
// transfer edge
timepoint += lastpredicateedge.getWeight();
}
edgevec = null;
}
- candidatetasks = null;
- it_edgevecs = null;
- }
- it_cores = null;
- computeBestStartPoint(criticalPath);
- Vector<Vector<ScheduleNode>> ops = optimizeCriticalPath(scheduleGraph,
- criticalPath,
- lgid,
- left);
- if(ops != null) {
- if(optimizeschedulegraphs == null) {
- optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
+ it_cores = null;
+ computeBestStartPoint(criticalPath);
+ Vector<Vector<ScheduleNode>> ops = optimizeCriticalPath(scheduleGraph,
+ criticalPath,
+ lgid,
+ left);
+ if(ops != null) {
+ if(optimizeschedulegraphs == null) {
+ optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
+ }
+ optimizeschedulegraphs.addAll(ops);
+ lgid += ops.size();
+ left -= ops.size();
}
- optimizeschedulegraphs.addAll(ops);
- }
- ops = null;
- } else {
- // there are spare cores, try to reorganize the tasks to the spare
- // cores
- Vector<Vector<ScheduleNode>> ops = innerOptimizeCriticalPath(scheduleGraph,
- tooptimize,
- sparecores,
- lgid,
- left);
- if(ops != null) {
- if(optimizeschedulegraphs == null) {
- optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
+ ops = null;
+ } else {
+ // there are spare cores, try to reorganize the tasks to the spare
+ // cores
+ Vector<Vector<ScheduleNode>> ops = innerOptimizeCriticalPath(scheduleGraph,
+ tooptimize,
+ sparecores,
+ lgid,
+ left);
+ if(ops != null) {
+ if(optimizeschedulegraphs == null) {
+ optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
+ }
+ optimizeschedulegraphs.addAll(ops);
+ lgid += ops.size();
+ left -= ops.size();
}
- optimizeschedulegraphs.addAll(ops);
+ ops = null;
}
- ops = null;
}
- }
- sparecores = null;
- tooptimize.clear();
- tooptimize = null;
+ sparecores = null;
+ tooptimize.clear();
+ tooptimize = null;
+ }while(left > 0);
+ toselects.clear();
+ toselects = null;
return optimizeschedulegraphs;
}
private Vector<Vector<ScheduleNode>> innerOptimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
- Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>> tooptimize,
+ Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize,
Vector<Integer> sparecores,
int gid,
int count) {
Iterator<Integer> it_cores = tooptimize.keySet().iterator();
while(it_cores.hasNext()) {
int corenum = it_cores.next();
- Hashtable<TaskDescriptor, Vector<SimExecutionEdge>> candidatetasks =
+ Vector<SimExecutionEdge> candidatetasks =
tooptimize.get(corenum);
- Iterator<TaskDescriptor> it_tds = candidatetasks.keySet().iterator();
- while(it_tds.hasNext()) {
- TaskDescriptor td = it_tds.next();
- int numtosplit = candidatetasks.get(td).size();
+ for(int i = 0; i < candidatetasks.size(); i++) {
+ TaskDescriptor td = candidatetasks.elementAt(i).getTd();
// TODO: currently do not consider multi-param tasks
if(td.numParameters() == 1) {
ClassDescriptor cd = td.getParamType(0).getClassDesc();
ScheduleNode snode = newscheduleGraph.elementAt(corenum); // corresponding ScheduleNode
Iterator<ClassNode> it_cnodes = snode.getClassNodesIterator();
- Vector<ClassNode> tosplit = new Vector<ClassNode>();
- while((numtosplit > 0) && (it_cnodes.hasNext())) {
+ ClassNode tosplit = null;
+ while(it_cnodes.hasNext()) {
ClassNode cnode = it_cnodes.next();
if(cnode.getClassDescriptor().equals(cd)) {
- tosplit.add(cnode);
- numtosplit--;
+ tosplit= cnode;
+ break;
}
}
it_cnodes = null;
- // split these node
- for(int i = 0; i < tosplit.size(); i++) {
- ScheduleNode splitnode = snode.spliteClassNode(tosplit.elementAt(i));
- newscheduleGraph.add(splitnode);
- tocombines.add(splitnode);
- }
+ // split the node
+ ScheduleNode splitnode = snode.spliteClassNode(tosplit);
+ newscheduleGraph.add(splitnode);
+ tocombines.add(splitnode);
tosplit = null;
}
}
candidatetasks = null;
- it_tds = null;
}
it_cores = null;
projects / IRC.git / commitdiff