int coreNum;
int scheduleThreshold; // # of starting points generated by schedule analysis
- int probThreshold; // the probability to stop when no accelaration achieved
+ int probThreshold; // the probability to stop when no accelaration achieved
// in the directed simulated annealing
- int generateThreshold; // how many optimized implementation generated in
+ int generateThreshold; // how many optimized implementation generated in
// each iteration of the directed simulated annealing
- int skipThreshold; // the probability to skip to producing more optimization
+ int skipThreshold; // the probability to skip to producing more optimization
// with the same root sets(see ScheduleAnalysis.coremapping)
- public MCImplSynthesis(State state,
+ public MCImplSynthesis(State state,
TaskAnalysis ta,
OwnershipAnalysis oa) {
this.state = state;
this.taskAnalysis = ta;
this.ownershipAnalysis = oa;
this.scheduleAnalysis = new ScheduleAnalysis(state,
- ta);
+ ta);
this.scheduleAnalysis.setCoreNum(this.coreNum);
this.scheduleSimulator = new ScheduleSimulator(this.coreNum,
- state,
- ta);
+ state,
+ ta);
this.scheduleThreshold = 1000;
this.probThreshold = 0;
this.generateThreshold = 30;
PrintStream stdout = null;
try {
if(!state.BAMBOOCOMPILETIME) {
- stdout = new PrintStream(
- new FileOutputStream(this.state.outputdir + "SimulatorResult_"
- + this.coreNum + ".out"));
+ stdout = new PrintStream(
+ new FileOutputStream(this.state.outputdir + "SimulatorResult_"
+ + this.coreNum + ".out"));
}
} catch (Exception e) {
// Sigh. Couldn't open the file.
Vector<Schedule> scheduling = null;
Vector<ScheduleNode> schedulinggraph = null;
int gid = 1;
-
+
// check all multi-parameter tasks
Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
- Iterator it_tasks =
+ Iterator it_tasks =
this.state.getTaskSymbolTable().getDescriptorsIterator();
while(it_tasks.hasNext()) {
TaskDescriptor td = (TaskDescriptor)it_tasks.next();
// generate multiple schedulings
this.scheduleAnalysis.setScheduleThreshold(this.scheduleThreshold);
- boolean tooptimize =
- this.scheduleAnalysis.schedule(this.generateThreshold,
+ boolean tooptimize =
+ this.scheduleAnalysis.schedule(this.generateThreshold,
this.skipThreshold,
multiparamtds);
if(this.generateThreshold > 5) {
this.scheduleSimulator.init();
Vector<Vector<ScheduleNode>> scheduleGraphs = null;
- Vector<Vector<ScheduleNode>> newscheduleGraphs =
+ Vector<Vector<ScheduleNode>> newscheduleGraphs =
this.scheduleAnalysis.getScheduleGraphs();
- Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
+ Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
this.scheduleAnalysis.getTd2maincd();
Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
Vector<Integer> selectedSchedulings = new Vector<Integer>();
- Vector<SimExecutionNode> selectedSimExeGraphs =
+ Vector<SimExecutionNode> selectedSimExeGraphs =
new Vector<SimExecutionNode>();
SimExecutionNode selectedSimExeGraph_bk = null;
int threshold = this.scheduleThreshold;
// simulate the generated schedulings and try to optimize it
do {
- if(!state.BAMBOOCOMPILETIME) {
- System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
- System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
- }
+ if(!state.BAMBOOCOMPILETIME) {
+ 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++) {
// get scheduling layouts from schedule graphs
for(int i = 0; i < scheduleGraphs.size(); i++) {
Vector<ScheduleNode> scheduleGraph = scheduleGraphs.elementAt(i);
- Vector<Schedule> tmpscheduling =
+ Vector<Schedule> tmpscheduling =
generateScheduling(scheduleGraph, td2maincd);
schedulings.add(tmpscheduling);
scheduleGraph = null;
}
selectedSchedulings.clear();
selectedSimExeGraphs.clear();
- long tmpexetime = this.scheduleSimulator.simulate(schedulings,
- selectedSchedulings,
- selectedSimExeGraphs);
+ long tmpexetime = this.scheduleSimulator.simulate(schedulings,
+ selectedSchedulings,
+ selectedSimExeGraphs);
boolean remove = false;
if(tmpexetime < bestexetime) {
remove = true;
}
scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0));
schedulinggraph = scheduleGraphs.elementAt(
- selectedSchedulings.elementAt(0));
+ selectedSchedulings.elementAt(0));
selectedSimExeGraph_bk = selectedSimExeGraphs.elementAt(0);
-
+
if(!state.BAMBOOCOMPILETIME) {
- System.out.print("end of: #" + tryindex + " (bestexetime: "
- + bestexetime + ")\n");
- System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
+ System.out.print("end of: #" + tryindex + " (bestexetime: "
+ + bestexetime + ")\n");
+ System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
}
tryindex++;
threshold = this.scheduleThreshold;
} else if(tmpexetime == bestexetime) {
if(!state.BAMBOOCOMPILETIME) {
- System.out.print("end of: #" + tryindex + " (bestexetime: "
- + bestexetime + ")\n");
- System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
+ System.out.print("end of: #" + tryindex + " (bestexetime: "
+ + bestexetime + ")\n");
+ System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
}
tryindex++;
threshold += 10;
- if((threshold > 40) ||
- ((Math.abs(rand.nextInt()) % 100) < this.probThreshold + 10)) {
+ if((threshold > 40) ||
+ ((Math.abs(rand.nextInt()) % 100) < this.probThreshold + 10)) {
break;
}
} else {
if(!state.BAMBOOCOMPILETIME) {
- System.out.print("end of: #" + tryindex + " (bestexetime: "
- + bestexetime + ")\n");
- System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
+ System.out.print("end of: #" + tryindex + " (bestexetime: "
+ + bestexetime + ")\n");
+ System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
}
tryindex++;
if(threshold == this.scheduleThreshold) {
selectedSimExeGraphs.addElement(selectedSimExeGraph_bk);
}
threshold += 10;
- if( (threshold > 40) ||
+ if( (threshold > 40) ||
((Math.abs(rand.nextInt()) % 100) < this.probThreshold + 1)) {
break;
}
}
if(tooptimize) {
- // try to optimize the best one scheduling
- //do {
- newscheduleGraphs = optimizeScheduling(scheduleGraphs,
- selectedSchedulings,
- selectedSimExeGraphs,
- gid,
- threshold);
- /*if(newscheduleGraphs != null) {
- if(this.generateThreshold < 30) {
- this.generateThreshold = 30;
- }
- break;
- } else {
- threshold += 10;
- if(this.generateThreshold > 0) {
- this.generateThreshold -= 3;
- }
- if((Math.abs(rand.nextInt()) % 10000) < this.probThreshold + 1) {
- break;
+ // try to optimize the best one scheduling
+ //do {
+ newscheduleGraphs = optimizeScheduling(scheduleGraphs,
+ selectedSchedulings,
+ selectedSimExeGraphs,
+ gid,
+ threshold);
+ /*if(newscheduleGraphs != null) {
+ if(this.generateThreshold < 30) {
+ this.generateThreshold = 30;
+ }
+ break;
+ } else {
+ threshold += 10;
+ if(this.generateThreshold > 0) {
+ this.generateThreshold -= 3;
+ }
+ if((Math.abs(rand.nextInt()) % 10000) < this.probThreshold + 1) {
+ break;
+ }
+ }
+ }while(true);*/
+ if(remove) {
+ scheduleGraphs.removeElementAt(selectedSchedulings.elementAt(0));
+ selectedSimExeGraphs.removeElementAt(0);
}
- }
- }while(true);*/
- if(remove) {
- scheduleGraphs.removeElementAt(selectedSchedulings.elementAt(0));
- selectedSimExeGraphs.removeElementAt(0);
- }
} else {
break;
}
- }while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
+ } while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
if(scheduleGraphs != null) {
scheduleGraphs.clear();
td2maincd = null;
if(!state.BAMBOOCOMPILETIME) {
- System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
+ System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
}
System.out.print("selected bestexetime: " + bestexetime + "\n");
if(!state.BAMBOOCOMPILETIME) {
- String path = this.state.outputdir + "scheduling_selected.dot";
- SchedulingUtil.printScheduleGraph(path, schedulinggraph);
+ String path = this.state.outputdir + "scheduling_selected.dot";
+ SchedulingUtil.printScheduleGraph(path, schedulinggraph);
}
// Close the streams.
try {
if(!state.BAMBOOCOMPILETIME) {
- stdout.close();
- stdout = null;
- System.setOut(origOut);
+ stdout.close();
+ stdout = null;
+ System.setOut(origOut);
}
} catch (Exception e) {
origOut.println("Redirect: Unable to close files!");
PrintStream stdout = null;
try {
stdout = new PrintStream(
- new FileOutputStream(this.state.outputdir + "SimulatorResult_"
- + this.coreNum + ".out"));
+ new FileOutputStream(this.state.outputdir + "SimulatorResult_"
+ + this.coreNum + ".out"));
} catch (Exception e) {
// Sigh. Couldn't open the file.
System.out.println("Redirect: Unable to open output file!");
if(isall) {
// check all multi-parameter tasks
Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
- Iterator it_tasks =
+ Iterator it_tasks =
this.state.getTaskSymbolTable().getDescriptorsIterator();
while(it_tasks.hasNext()) {
TaskDescriptor td = (TaskDescriptor)it_tasks.next();
}
}
it_tasks = null;
-
+
// Generate all possible schedulings
//this.scheduleAnalysis.setScheduleThreshold(Integer.MAX_VALUE);
//this.scheduleAnalysis.schedule(-1, multiparamtds);
this.scheduleAnalysis.setScheduleThreshold(10000);
- this.scheduleAnalysis.schedule(80,
+ this.scheduleAnalysis.schedule(80,
20, // might skip
multiparamtds);
this.scheduleSimulator.init();
- Vector<Vector<ScheduleNode>> totestscheduleGraphs =
+ Vector<Vector<ScheduleNode>> totestscheduleGraphs =
this.scheduleAnalysis.getScheduleGraphs();
- Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
+ Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
this.scheduleAnalysis.getTd2maincd();
Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
Vector<Integer> selectedSchedulings = new Vector<Integer>();
- Vector<SimExecutionNode> selectedSimExeGraphs =
+ Vector<SimExecutionNode> selectedSimExeGraphs =
new Vector<SimExecutionNode>();
-
+
File file=new File(this.state.outputdir+"distributeinfo_s_"+this.coreNum
+".out");
- FileOutputStream dotstream = null;
+ FileOutputStream dotstream = null;
try {
dotstream = new FileOutputStream(file,false);
} catch (Exception e) {
System.exit(-1);
}
PrintWriter output = new java.io.PrintWriter(dotstream, true);
- output.println("start time(1,000,000 cycles): "
+ output.println("start time(1,000,000 cycles): "
+ totestscheduleGraphs.size());
for(int ii = 0; ii < totestscheduleGraphs.size(); ii++) {
- Vector<Vector<ScheduleNode>> newscheduleGraphs =
+ Vector<Vector<ScheduleNode>> newscheduleGraphs =
new Vector<Vector<ScheduleNode>>();
newscheduleGraphs.add(totestscheduleGraphs.elementAt(ii));
- // simulate the generated schedulings and try to optimize it
+ // simulate the generated schedulings and try to optimize it
schedulings.clear();
// get scheduling layouts from schedule graphs
for(int i = 0; i < newscheduleGraphs.size(); i++) {
Vector<ScheduleNode> scheduleGraph = newscheduleGraphs.elementAt(i);
- Vector<Schedule> tmpscheduling =
+ Vector<Schedule> tmpscheduling =
generateScheduling(scheduleGraph, td2maincd);
schedulings.add(tmpscheduling);
scheduleGraph = null;
}
selectedSchedulings.clear();
selectedSimExeGraphs.clear();
- long tmpexetime = this.scheduleSimulator.simulate(schedulings,
- selectedSchedulings,
- selectedSimExeGraphs);
+ long tmpexetime = this.scheduleSimulator.simulate(schedulings,
+ selectedSchedulings,
+ selectedSimExeGraphs);
output.println(((float)tmpexetime/100000000));
}
} else {
// check all multi-parameter tasks
Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
- Iterator it_tasks =
+ Iterator it_tasks =
this.state.getTaskSymbolTable().getDescriptorsIterator();
while(it_tasks.hasNext()) {
TaskDescriptor td = (TaskDescriptor)it_tasks.next();
}
}
it_tasks = null;
-
+
// generate multiple schedulings
this.scheduleThreshold = 20;
this.generateThreshold = 30;
this.probThreshold = 0;
this.scheduleAnalysis.setScheduleThreshold(1000);
- boolean tooptimize =
- this.scheduleAnalysis.schedule(this.generateThreshold,
+ boolean tooptimize =
+ this.scheduleAnalysis.schedule(this.generateThreshold,
60, // might skip
multiparamtds);
this.scheduleSimulator.init();
Vector<Vector<ScheduleNode>> scheduleGraphs = null;
- Vector<Vector<ScheduleNode>> totestscheduleGraphs =
+ Vector<Vector<ScheduleNode>> totestscheduleGraphs =
this.scheduleAnalysis.getScheduleGraphs();
- Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
+ Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
this.scheduleAnalysis.getTd2maincd();
Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
Vector<Integer> selectedSchedulings = new Vector<Integer>();
- Vector<SimExecutionNode> selectedSimExeGraphs =
+ Vector<SimExecutionNode> selectedSimExeGraphs =
new Vector<SimExecutionNode>();
SimExecutionNode selectedSimExeGraph_bk = null;
- File file=new File(this.state.outputdir + "distributeinfo_s_"
+ File file=new File(this.state.outputdir + "distributeinfo_s_"
+ this.coreNum + ".out");
- FileOutputStream dotstream = null;
- File file2=new File(this.state.outputdir + "distributeinfo_o_"
+ FileOutputStream dotstream = null;
+ File file2=new File(this.state.outputdir + "distributeinfo_o_"
+ this.coreNum + ".out");
- FileOutputStream dotstream2 = null;
+ FileOutputStream dotstream2 = null;
try {
dotstream = new FileOutputStream(file,false);
dotstream2 = new FileOutputStream(file2,false);
}
PrintWriter output = new java.io.PrintWriter(dotstream, true);
PrintWriter output2 = new java.io.PrintWriter(dotstream2, true);
- output.println("start time(100,000,000 cycles): "
+ output.println("start time(100,000,000 cycles): "
+ totestscheduleGraphs.size());
- output2.println("optimized time(100,000,000 cycles): "
+ output2.println("optimized time(100,000,000 cycles): "
+ totestscheduleGraphs.size());
for(int ii = startnum; ii < totestscheduleGraphs.size(); ii++) {
- Vector<Vector<ScheduleNode>> newscheduleGraphs =
+ Vector<Vector<ScheduleNode>> newscheduleGraphs =
new Vector<Vector<ScheduleNode>>();
newscheduleGraphs.add(totestscheduleGraphs.elementAt(ii));
int tryindex = 1;
System.out.print("# " + ii + ": \n");
do {
System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
- System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
+ System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
gid += newscheduleGraphs.size();
if(scheduleGraphs != null) {
for(int i = 0; i < scheduleGraphs.size(); i++) {
// get scheduling layouts from schedule graphs
for(int i = 0; i < scheduleGraphs.size(); i++) {
Vector<ScheduleNode> scheduleGraph = scheduleGraphs.elementAt(i);
- Vector<Schedule> tmpscheduling =
+ Vector<Schedule> tmpscheduling =
generateScheduling(scheduleGraph, td2maincd);
schedulings.add(tmpscheduling);
scheduleGraph = null;
}
selectedSchedulings.clear();
selectedSimExeGraphs.clear();
- long tmpexetime = this.scheduleSimulator.simulate(schedulings,
- selectedSchedulings,
- selectedSimExeGraphs);
+ long tmpexetime = this.scheduleSimulator.simulate(schedulings,
+ selectedSchedulings,
+ selectedSimExeGraphs);
if(isfirst) {
output.println(((float)tmpexetime/100000000));
isfirst = false;
}
scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0));
schedulinggraph = scheduleGraphs.elementAt(
- selectedSchedulings.elementAt(0));
+ selectedSchedulings.elementAt(0));
selectedSimExeGraph_bk = selectedSimExeGraphs.elementAt(0);
tryindex++;
threshold = this.scheduleThreshold;
- System.out.print("end of: #" + tryindex + " (bestexetime: "
+ System.out.print("end of: #" + tryindex + " (bestexetime: "
+ bestexetime + ")\n");
System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
} else if(tmpexetime == bestexetime) {
- System.out.print("end of: #" + tryindex + " (bestexetime: "
+ System.out.print("end of: #" + tryindex + " (bestexetime: "
+ bestexetime + ")\n");
System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
tryindex++;
break;
}
} else {
- System.out.print("end of: #" + tryindex + " (bestexetime: "
- + bestexetime + ")\n");
+ System.out.print("end of: #" + tryindex + " (bestexetime: "
+ + bestexetime + ")\n");
System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
tryindex++;
if(threshold == this.scheduleThreshold) {
}
if(tooptimize) {
- // 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));
+ }
} else {
break;
}
- }while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
+ } while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
scheduleGraphs.clear();
scheduleGraphs = null;
return;
}
- private Vector<Vector<ScheduleNode>>
+ private Vector<Vector<ScheduleNode>>
optimizeScheduling(Vector<Vector<ScheduleNode>> scheduleGraphs,
Vector<Integer> selectedScheduleGraphs,
Vector<SimExecutionNode> selectedSimExeGraphs,
for(int i = 0; i < selectedScheduleGraphs.size(); i++) {
Vector<ScheduleNode> schedulegraph = scheduleGraphs.elementAt(
- selectedScheduleGraphs.elementAt(i));
+ selectedScheduleGraphs.elementAt(i));
SimExecutionNode startnode = selectedSimExeGraphs.elementAt(i);
- Vector<SimExecutionEdge> criticalPath = analyzeCriticalPath(startnode);
+ Vector<SimExecutionEdge> criticalPath = analyzeCriticalPath(startnode);
// for Test
if(this.state.PRINTCRITICALPATH) {
System.err.println("gid: " + lgid + " endpoint: " + startnode.getTimepoint());
}
- Vector<Vector<ScheduleNode>> tmposchedulegraphs =
- optimizeCriticalPath(schedulegraph,
+ Vector<Vector<ScheduleNode>> tmposchedulegraphs =
+ optimizeCriticalPath(schedulegraph,
criticalPath,
lgid,
left);
tmposchedulegraphs = null;
break;
}
- }
+ }
schedulegraph = null;
criticalPath = null;
tmposchedulegraphs = null;
return optimizeschedulegraphs;
}
- private Vector<SimExecutionEdge>
+ private Vector<SimExecutionEdge>
analyzeCriticalPath(SimExecutionNode startnode) {
// first figure out the critical path
Vector<SimExecutionEdge> criticalPath = new Vector<SimExecutionEdge>();
// 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.
- private long getCriticalPath(SimExecutionNode startnode,
+ private long getCriticalPath(SimExecutionNode startnode,
Vector<SimExecutionEdge> criticalPath) {
long sum = 0;
SimExecutionNode snode = startnode;
// go reversely to find the critical path
while(snode != null) {
SimExecutionNode nsnode = null;
- Iterator<SimExecutionEdge> it_iedges =
+ Iterator<SimExecutionEdge> it_iedges =
(Iterator<SimExecutionEdge>)snode.inedges();
while(it_iedges.hasNext()) {
SimExecutionEdge sedge = it_iedges.next();
- //if(sedge.getWeight() != 0) {
- SimExecutionNode tsnode = (SimExecutionNode)(sedge.getSource());
- if(tsnode.getTimepoint() + sedge.getWeight() == snode.getTimepoint()) {
- nsnode = tsnode;
- criticalPath.insertElementAt(sedge, 0);
- sum += sedge.getWeight();
- break;
- }
+ //if(sedge.getWeight() != 0) {
+ SimExecutionNode tsnode = (SimExecutionNode)(sedge.getSource());
+ if(tsnode.getTimepoint() + sedge.getWeight() == snode.getTimepoint()) {
+ nsnode = tsnode;
+ criticalPath.insertElementAt(sedge, 0);
+ sum += sedge.getWeight();
+ break;
+ }
//}
}
it_iedges = null;
seedge.setLastpredicateEdge(predicate);
if(predicate.getTd() != null) {
seedge.setLastpredicateNode(
- (SimExecutionNode)predicate.getTarget());
+ (SimExecutionNode)predicate.getTarget());
} else {
// transfer edge
seedge.setLastpredicateNode(
- (SimExecutionNode)predicate.getSource());
+ (SimExecutionNode)predicate.getSource());
}
}
}
}
}
- private Vector<Vector<ScheduleNode>>
+ private Vector<Vector<ScheduleNode>>
optimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
Vector<SimExecutionEdge> criticalPath,
int gid,
// for test, print out the criticalPath
if(this.state.PRINTCRITICALPATH) {
- SchedulingUtil.printCriticalPath(this.state.outputdir + "criticalpath_"
+ SchedulingUtil.printCriticalPath(this.state.outputdir + "criticalpath_"
+ lgid + ".dot", criticalPath);
}
long opcheckpoint = Long.MAX_VALUE;
Vector<Integer> sparecores = null;
// group according to core index
- Hashtable<Long, Hashtable<Integer, Vector<SimExecutionEdge>>> toselects =
+ Hashtable<Long, Hashtable<Integer, Vector<SimExecutionEdge>>> toselects =
new Hashtable<Long, Hashtable<Integer, Vector<SimExecutionEdge>>>();
Random rand = new Random();
for(int i = 0; i < criticalPath.size(); i++) {
SimExecutionEdge seedge = criticalPath.elementAt(i);
long starttime = seedge.getBestStartPoint();
- if((starttime < ((SimExecutionNode)seedge.getSource()).getTimepoint())
- && (seedge.getTd() != null)){
+ if((starttime < ((SimExecutionNode)seedge.getSource()).getTimepoint())
+ && (seedge.getTd() != null)) {
// Note: must be a task related edge, can not be an object transfer edge
// no restrictions due to data dependencies
// have potential to be parallelled and start execution earlier
seedge.setFixedTime(false);
- // consider to optimize it only when its predicates can NOT
+ // consider to optimize it only when its predicates can NOT
// be optimized, otherwise first considering optimize its predicates
//SimExecutionEdge lastpredicateedge = seedge.getLastpredicateEdge();
// TODO
- //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);
+ //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
+ // Randomly choose the tasks to optimize(previously only
// consider the tasks with smallest best start time)
Vector<Long> keys = new Vector<Long>(toselects.keySet());
- do{
+ do {
int length = keys.size();
if(length == 0) {
return optimizeschedulegraphs;
int tochoose = Math.abs(rand.nextInt()) % length;
opcheckpoint = (keys.elementAt(tochoose)).longValue();
keys.removeElementAt(tochoose);
- Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize =
+ Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize =
toselects.get(opcheckpoint);
- SimExecutionEdge seedge =
+ SimExecutionEdge seedge =
tooptimize.values().iterator().next().elementAt(0);
SimExecutionNode lastpredicatenode = seedge.getLastpredicateNode();
SimExecutionEdge lastpredicateedge = seedge.getLastpredicateEdge();
// mapping to critical path
for(int index = 0; index < criticalPath.size(); index++) {
SimExecutionEdge tmpseedge = criticalPath.elementAt(index);
- SimExecutionNode tmpsenode =
+ SimExecutionNode tmpsenode =
(SimExecutionNode)tmpseedge.getTarget();
if(tmpsenode.getTimepoint() > timepoint) {
// get the spare core info
while(it_cores.hasNext()) {
int corenum = it_cores.next();
Vector<SimExecutionEdge> tmptasks = tooptimize.get(corenum);
- // group the task instantiations according to whether it
+ // 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> 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 =
+ Vector<SimExecutionEdge> predicates =
tmpedge.getPredicates();
- if((predicates != null) &&
- (predicates.contains(tmpseedge))) {
+ 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()) {
+ if(((SimExecutionNode)tmpedge.getTarget()).getTimepoint()
+ == tmpedge.getWeight() + target.getTimepoint()) {
break;
}
}
candidatetasks.add(tmpseedge);
}
}
- if((candidatetasks.size() > 0) &&
- (candidatetasks.size() < tmptasks.size())) {
+ 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
+ // data dependences at this timepoint, try to change
// original execution order
- Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize2 =
+ Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize2 =
new Hashtable<Integer, Vector<SimExecutionEdge>>();
tooptimize2.put(corenum, candidatetasks);
- Vector<Vector<ScheduleNode>> ops =
+ Vector<Vector<ScheduleNode>> ops =
innerOptimizeCriticalPath(scheduleGraph,
tooptimize2,
null,
// flush the dependences and earliest start time
if(!state.BAMBOOCOMPILETIME) {
- 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);
- lastpredicateedge = edge.getLastpredicateEdge();
- lastpredicatenode = edge.getLastpredicateNode();
- // if(edge.getCoreNum() != lastpredicate.getCoreNum()) // should never hit this
- 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) {
- // update the predicate info
- if(edge.getPredicates() != null) {
- edge.getPredicates().remove(lastpredicateedge);
+ 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);
+ lastpredicateedge = edge.getLastpredicateEdge();
+ lastpredicatenode = edge.getLastpredicateNode();
+ // if(edge.getCoreNum() != lastpredicate.getCoreNum()) // should never hit this
+ 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) {
+ // update the predicate info
+ if(edge.getPredicates() != null) {
+ edge.getPredicates().remove(lastpredicateedge);
+ }
+ edge.addPredicate(criticalPath.elementAt(index));
+ break;
}
- edge.addPredicate(criticalPath.elementAt(index));
- break;
}
}
+ edgevec = null;
}
- edgevec = 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);
- lgid += ops.size();
- left -= ops.size();
- }
- ops = null;
+ ops = null;
}
} else {
- // there are spare cores, try to reorganize the tasks to the spare
+ // there are spare cores, try to reorganize the tasks to the spare
// cores
- Vector<Vector<ScheduleNode>> ops =
+ Vector<Vector<ScheduleNode>> ops =
innerOptimizeCriticalPath(scheduleGraph,
tooptimize,
sparecores,
sparecores = null;
tooptimize.clear();
tooptimize = null;
- }while(left > 0);
+ } while(left > 0);
toselects.clear();
toselects = null;
return optimizeschedulegraphs;
}
- private Vector<Vector<ScheduleNode>>
+ private Vector<Vector<ScheduleNode>>
innerOptimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize,
Vector<Integer> sparecores,
Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
// first clone the whole graph
- Vector<ScheduleNode> newscheduleGraph =
+ Vector<ScheduleNode> newscheduleGraph =
cloneScheduleGraph(scheduleGraph, lgid);
-
+
if(newscheduleGraph.size() == 0) {
//System.err.println("empty schedule graph!");
return optimizeschedulegraphs;
}
}
- // map the tasks associated to SimExecutionedges to original
- // ClassNode in the ScheduleGraph and split them from previous
+ // map the tasks associated to SimExecutionedges to original
+ // ClassNode in the ScheduleGraph and split them from previous
// ScheduleGraph
Vector<ScheduleNode> tocombines = new Vector<ScheduleNode>();
Iterator<Integer> it_cores = tooptimize.keySet().iterator();
while(it_cores.hasNext()) {
int corenum = it_cores.next();
- Vector<SimExecutionEdge> candidatetasks =
+ Vector<SimExecutionEdge> candidatetasks =
tooptimize.get(corenum);
for(int i = 0; i < candidatetasks.size(); i++) {
TaskDescriptor td = candidatetasks.elementAt(i).getTd();
it_cnodes = null;
// split the node
- ScheduleNode splitnode = snode.spliteClassNode(tosplit);
+ ScheduleNode splitnode = snode.spliteClassNode(tosplit);
newscheduleGraph.add(splitnode);
tocombines.add(splitnode);
tosplit = null;
Vector<ScheduleEdge> scheduleEdges = new Vector<ScheduleEdge>();
for(int i= 0; i < newscheduleGraph.size(); i++) {
scheduleEdges.addAll(
- (Vector<ScheduleEdge>)newscheduleGraph.elementAt(i).getEdgeVector());
+ (Vector<ScheduleEdge>)newscheduleGraph.elementAt(i).getEdgeVector());
}
- Vector<Vector<ScheduleNode>> rootNodes =
+ Vector<Vector<ScheduleNode>> rootNodes =
SchedulingUtil.rangeScheduleNodes(roots);
if(rootNodes == null) {
return optimizeschedulegraphs;
}
- Vector<Vector<ScheduleNode>> nodes2combine =
+ Vector<Vector<ScheduleNode>> nodes2combine =
SchedulingUtil.rangeScheduleNodes(tocombines);
if(nodes2combine == null) {
return optimizeschedulegraphs;
}
- CombinationUtil.CombineGenerator cGen =
+ CombinationUtil.CombineGenerator cGen =
CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine);
Random rand = new Random();
while ((left > 0) && (cGen.nextGen())) {
- //while ((left > 0) && (cGen.randomGenE())) {
+ //while ((left > 0) && (cGen.randomGenE())) {
if(Math.abs(rand.nextInt()) % 100 > this.generateThreshold) {
Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
- Vector<ScheduleNode> sNodes =
+ Vector<ScheduleNode> sNodes =
SchedulingUtil.generateScheduleGraph(this.state,
newscheduleGraph,
scheduleEdges,
- rootNodes,
- combine,
+ rootNodes,
+ combine,
lgid++);
if(optimizeschedulegraphs == null) {
optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
return optimizeschedulegraphs;
}
- private Vector<ScheduleNode>
+ private Vector<ScheduleNode>
cloneScheduleGraph(Vector<ScheduleNode> scheduleGraph,
int gid) {
Vector<ScheduleNode> result = new Vector<ScheduleNode>();
Vector<ScheduleEdge> scheduleEdges = new Vector<ScheduleEdge>();
for(int i= 0; i < scheduleGraph.size(); i++) {
scheduleEdges.addAll(
- (Vector<ScheduleEdge>)scheduleGraph.elementAt(i).getEdgeVector());
+ (Vector<ScheduleEdge>)scheduleGraph.elementAt(i).getEdgeVector());
}
- Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash =
+ Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash =
new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
- Hashtable<ScheduleNode, ScheduleNode> sn2sn =
+ Hashtable<ScheduleNode, ScheduleNode> sn2sn =
new Hashtable<ScheduleNode, ScheduleNode>();
SchedulingUtil.cloneScheduleGraph(scheduleGraph,
- scheduleEdges,
- sn2hash,
- sn2sn,
- result,
- gid);
+ scheduleEdges,
+ sn2hash,
+ sn2sn,
+ result,
+ gid);
SchedulingUtil.assignCids(result);
scheduleEdges.clear();
return result;
}
- private Vector<Schedule>
+ private Vector<Schedule>
generateScheduling(Vector<ScheduleNode> scheduleGraph,
Hashtable<TaskDescriptor, ClassDescriptor> td2maincd) {
- Hashtable<TaskDescriptor, Vector<Schedule>> td2cores =
+ Hashtable<TaskDescriptor, Vector<Schedule>> td2cores =
new Hashtable<TaskDescriptor, Vector<Schedule>>(); // tasks reside on which cores
Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
// for each ScheduleNode create a schedule node representing a core
- Hashtable<ScheduleNode, Integer> sn2coreNum =
+ Hashtable<ScheduleNode, Integer> sn2coreNum =
new Hashtable<ScheduleNode, Integer>();
- Hashtable<TaskDescriptor, Integer> td2maincore =
+ Hashtable<TaskDescriptor, Integer> td2maincore =
new Hashtable<TaskDescriptor, Integer>();
- Hashtable<TaskDescriptor, Vector<Schedule>> td2allycores =
- new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks --
- // ally cores which might have parameters
- // for the task
-
+ Hashtable<TaskDescriptor, Vector<Schedule>> td2allycores =
+ new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks --
+ // ally cores which might have parameters
+ // for the task
+
int j = 0;
for(j = 0; j < scheduleGraph.size(); j++) {
sn2coreNum.put(scheduleGraph.elementAt(j), j);
TaskDescriptor td = (tmpfe).getTask();
boolean contain = true;
if(td.numParameters() > 1) {
- // td is a multi-param task, check if this core contains the
+ // td is a multi-param task, check if this core contains the
// main cd of it
ClassDescriptor cd1 = td2maincd.get(td);
if(td2maincd.get(td).equals(cd)) {
allycores = null;
}
// If the FlagState can be fed to some multi-param tasks,
- // need to record corresponding ally cores later.
+ // need to record corresponding ally cores later.
tmpSchedule.addFState4TD(td, fs);
}
if(contain) {
tmpcores = null;
}
if(td.getParamType(0).getClassDesc().getSymbol().equals(
- TypeUtil.StartupClass)) {
+ TypeUtil.StartupClass)) {
assert(!setstartupcore);
startupcore = j;
startup = tmpSchedule;
}
cNodes = null;
- // For each of the ScheduleEdge out of this ScheduleNode, add the
+ // For each of the ScheduleEdge out of this ScheduleNode, add the
// target ScheduleNode into the queue inside sn
Iterator it_edges = sn.edges();
while(it_edges.hasNext()) {
switch(se.getType()) {
case ScheduleEdge.NEWEDGE: {
FlagState fs = se.getFstate();
- // Check if the new obj could be fed to some
- // multi-parameter task, if so, add for ally cores
+ // Check if the new obj could be fed to some
+ // multi-parameter task, if so, add for ally cores
// checking
Iterator it = fs.edges();
boolean canTriggerSTask = false; // Flag indicates if fs can trigger
while(it.hasNext()) {
TaskDescriptor td = ((FEdge)it.next()).getTask();
if(td.numParameters() > 1) {
- tmpSchedule.addFState4TD(td, fs); // TODO
+ tmpSchedule.addFState4TD(td, fs); // TODO
// add this core as a allycore of td
if(!td2allycores.containsKey(td)) {
td2allycores.put(td, new Vector<Schedule>());
case ScheduleEdge.TRANSEDGE: {
// 'transmit' edge
- tmpSchedule.addTargetCore(se.getFstate(),
- targetcore,
+ tmpSchedule.addTargetCore(se.getFstate(),
+ targetcore,
se.getTargetFState());
- // check if missed some FlagState associated with some
- // multi-parameter task, which has been cloned when
+ // check if missed some FlagState associated with some
+ // multi-parameter task, which has been cloned when
// splitting a ClassNode
FlagState fs = se.getSourceFState();
FlagState tfs = se.getTargetFState();
case ScheduleEdge.NEWEDGE: {
// TODO, added 09/07/06
FlagState fs = se.getFstate();
- // Check if the new obj could be fed to some
- // multi-parameter task, if so, add for ally cores
+ // Check if the new obj could be fed to some
+ // multi-parameter task, if so, add for ally cores
// checking
Iterator it = fs.edges();
boolean canTriggerSTask = false; // Flag indicates if fs can trigger
while(it.hasNext()) {
TaskDescriptor td = ((FEdge)it.next()).getTask();
if(td.numParameters() > 1) {
- tmpSchedule.addFState4TD(td, fs); // TODO
+ tmpSchedule.addFState4TD(td, fs); // TODO
// add this core as a allycore of td
if(!td2allycores.containsKey(td)) {
td2allycores.put(td, new Vector<Schedule>());
case ScheduleEdge.TRANSEDGE: {
// 'transmit' edge
- tmpSchedule.addTargetCore(se.getFstate(),
- j,
+ tmpSchedule.addTargetCore(se.getFstate(),
+ j,
se.getTargetFState());
- // check if missed some FlagState associated with some
- // multi-parameter task, which has been cloned when
+ // check if missed some FlagState associated with some
+ // multi-parameter task, which has been cloned when
// splitting a ClassNode
FlagState fs = se.getSourceFState();
FlagState tfs = se.getTargetFState();
while(it_mptds.hasNext()) {
TaskDescriptor td = it_mptds.next();
Vector<FEdge> fes = (Vector<FEdge>) this.taskAnalysis.getFEdgesFromTD(td);
- Vector<Schedule> cores = td2cores.get(td);
+ Vector<Schedule> cores = td2cores.get(td);
assert(cores.size() == 1); // should have only one core
for(int k = 0; k < cores.size(); ++k) {
Schedule tmpSchedule = cores.elementAt(k);
- // Make sure all the parameter objs of a multi-parameter
+ // Make sure all the parameter objs of a multi-parameter
// task would be send to right place after the task finished
for(int h = 0; h < fes.size(); ++h) {
FEdge tmpfe = fes.elementAt(h);
FlagState tmpfs = (FlagState)tmpfe.getTarget();
Vector<TaskDescriptor> tmptds = new Vector<TaskDescriptor>();
- if((tmpSchedule.getTargetCoreTable() == null)
- || (!tmpSchedule.getTargetCoreTable().containsKey(tmpfs))) {
+ if((tmpSchedule.getTargetCoreTable() == null)
+ || (!tmpSchedule.getTargetCoreTable().containsKey(tmpfs))) {
// add up all possible cores' info
Iterator it_edges = tmpfs.edges();
while(it_edges.hasNext()) {
projects / IRC.git / blobdiff