public class ClassNode extends GraphNode implements Cloneable {
private int uid;
+ private int cid;
private static int nodeID=0;
+ private static int colorID = 1;
+ private static Hashtable<ClassDescriptor, Integer> cd2cid =
+ new Hashtable<ClassDescriptor, Integer>();
private final ClassDescriptor cd;
private ScheduleNode sn;
* @param cd ClassDescriptor
* @param fStates
*/
- public ClassNode(ClassDescriptor cd, Vector<FlagState> fStates) {
+ public ClassNode(ClassDescriptor cd,
+ Vector<FlagState> fStates) {
this.cd=cd;
this.flagStates = fStates;
this.sn = null;
this.uid=ClassNode.nodeID++;
+ // TODO: potential bug here
+ // DO NOT consider splitting a class node here.
+ // need to fix: 1. when a class node is splitted, the pieces should have
+ // different cid
+ // 2. when two pieces merged, it should have right cid as have
+ // never been splitted
+ // 3. NOTE: a piece could be splitted further
+ if(this.cd2cid.containsKey(cd)) {
+ this.cid = this.cd2cid.get(cd);
+ } else {
+ this.cid = ClassNode.colorID++;
+ this.cd2cid.put(this.cd, this.cid);
+ }
this.transTime = 0;
}
return uid;
}
+ public int getCid() {
+ return cid;
+ }
+
public ScheduleNode getScheduleNode() {
return this.sn;
}
if (o instanceof ClassNode) {
ClassNode fs=(ClassNode)o;
if ((fs.getClassDescriptor()!= cd) ||
+ (fs.getuid()!= uid) ||
+ (fs.getCid()!= cid) ||
(fs.isSorted() != sorted) ||
(fs.clone != this.clone) ||
(fs.transTime != this.transTime)) {
}
public int hashCode() {
- return cd.hashCode()^Boolean.toString(sorted).hashCode()^Boolean.toString(clone).hashCode()^
- transTime^flagStates.hashCode();
+ return cd.hashCode()^uid^cid^Boolean.toString(sorted).hashCode()^
+ Boolean.toString(clone).hashCode()^transTime^flagStates.hashCode();
}
public String getLabel() {
e.printStackTrace();
}
o.uid = ClassNode.nodeID++;
+ o.cid = this.cid;
o.clone = true;
return o;
}
return cu;
}
- public static RootsGenerator allocateRootsGenerator(Vector<Vector<ScheduleNode>> snodevecs, int rootNum) {
+ public static RootsGenerator allocateRootsGenerator(Vector<Vector<ScheduleNode>> snodevecs,
+ int rootNum) {
return CombinationUtil.allocateCombinationUtil().new RootsGenerator(snodevecs, rootNum);
}
- public static CombineGenerator allocateCombineGenerator(Vector<Vector<ScheduleNode>> rootnodes, Vector<Vector<ScheduleNode>> node2combine) {
+ public static CombineGenerator allocateCombineGenerator(Vector<Vector<ScheduleNode>> rootnodes,
+ Vector<Vector<ScheduleNode>> node2combine) {
return CombinationUtil.allocateCombinationUtil().new CombineGenerator(rootnodes, node2combine);
}
int coreNum;
int activeTime;
- public CoreSimulator(RuntimeSchedule schedule, int coreNum) {
+ public CoreSimulator(RuntimeSchedule schedule,
+ int coreNum) {
super();
reset();
this.rSchedule = schedule;
return targetCSimulator.get(fstate);
}
- public void setTargetCSimulator(Hashtable<FlagState, Queue<Integer>> targetCSimulator) {
+ public void setTargetCSimulator(Hashtable<FlagState,
+ Queue<Integer>> targetCSimulator) {
this.targetCSimulator = targetCSimulator;
}
return allyCSimulator.get(fstate);
}
- public void setAllyCSimulator(Hashtable<FlagState, Vector<Integer>> allyCSimulator) {
+ public void setAllyCSimulator(Hashtable<FlagState,
+ Vector<Integer>> allyCSimulator) {
this.allyCSimulator = allyCSimulator;
}
}
}
- public void addObject(ObjectSimulator newObj, FlagState fs, int version) {
+ public void addObject(ObjectSimulator newObj,
+ FlagState fs,
+ int version) {
if(this.tasks == null) {
return;
}
ObjectSimulator obj = paraQueues.elementAt(i).poll();
obj.setHold(false);
boolean remove = false;
- if((this.targetFState != null) && (this.targetFState.containsKey(obj.getCurrentFS()))) {
+ if((this.targetFState != null)
+ && (this.targetFState.containsKey(obj.getCurrentFS()))) {
if(transObjs == null) {
transObjs = new Vector<ObjectSimulator>();
}
--- /dev/null
+package Analysis.Scheduling;
+
+import java.io.FileOutputStream;
+import java.io.PrintStream;
+import java.util.Hashtable;
+import java.util.Iterator;
+import java.util.Vector;
+
+import Analysis.OwnershipAnalysis.OwnershipAnalysis;
+import Analysis.TaskStateAnalysis.FEdge;
+import Analysis.TaskStateAnalysis.FlagState;
+import Analysis.TaskStateAnalysis.TaskAnalysis;
+import IR.ClassDescriptor;
+import IR.State;
+import IR.TaskDescriptor;
+import IR.TypeUtil;
+
+public class MCImplSynthesis {
+
+ State state;
+ ScheduleAnalysis scheduleAnalysis;
+ TaskAnalysis taskAnalysis;
+ OwnershipAnalysis ownershipAnalysis;
+ ScheduleSimulator scheduleSimulator;
+
+ int coreNum;
+ int scheduleThreshold;
+
+ public MCImplSynthesis(State state,
+ TaskAnalysis ta,
+ OwnershipAnalysis oa) {
+ this.state = state;
+ this.coreNum = state.CORENUM;
+ this.taskAnalysis = ta;
+ this.ownershipAnalysis = oa;
+ this.scheduleAnalysis = new ScheduleAnalysis(state,
+ ta);
+ scheduleAnalysis.setCoreNum(this.coreNum);
+ this.scheduleSimulator = new ScheduleSimulator(this.coreNum,
+ state,
+ ta);
+ this.scheduleThreshold = 1000;
+ }
+
+ public int getCoreNum() {
+ return this.scheduleAnalysis.getCoreNum();
+ }
+
+ public int getScheduleThreshold() {
+ return scheduleThreshold;
+ }
+
+ public void setScheduleThreshold(int scheduleThreshold) {
+ this.scheduleThreshold = scheduleThreshold;
+ }
+
+ public Vector<Schedule> synthesis() {
+ // Print stuff to the original output and error streams.
+ // The stuff printed through the 'origOut' and 'origErr' references
+ // should go to the console on most systems while the messages
+ // printed through the 'System.out' and 'System.err' will end up in
+ // the files we created for them.
+ //origOut.println ("\nRedirect: Round #2");
+ //System.out.println ("Test output via 'SimulatorResult.out'.");
+ //origOut.println ("Test output via 'origOut' reference.");
+
+ // Save the current standard input, output, and error streams
+ // for later restoration.
+ PrintStream origOut = System.out;
+
+ // Create a new output stream for the standard output.
+ PrintStream stdout = null;
+ try {
+ stdout = new PrintStream(new FileOutputStream("/scratch/SimulatorResult.out"));
+ } catch (Exception e) {
+ // Sigh. Couldn't open the file.
+ System.out.println("Redirect: Unable to open output file!");
+ System.exit(1);
+ }
+
+ // Print stuff to the original output and error streams.
+ // On most systems all of this will end up on your console when you
+ // run this application.
+ //origOut.println ("\nRedirect: Round #1");
+ //System.out.println ("Test output via 'System.out'.");
+ //origOut.println ("Test output via 'origOut' reference.");
+
+ // Set the System out and err streams to use our replacements.
+ System.setOut(stdout);
+
+ Vector<Schedule> scheduling = null;
+ Vector<ScheduleNode> schedulinggraph = null;
+ int gid = 1;
+
+ // generate multiple schedulings
+ this.scheduleAnalysis.setScheduleThreshold(this.scheduleThreshold);
+ this.scheduleAnalysis.schedule();
+
+ Vector<Vector<ScheduleNode>> scheduleGraphs = null;
+ Vector<Vector<ScheduleNode>> newscheduleGraphs =
+ 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);
+ }
+ }
+
+ int tryindex = 1;
+ int bestexetime = Integer.MAX_VALUE;
+ // simulate the generated schedulings and try to optimize it
+ do {
+ System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
+ System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
+ gid += newscheduleGraphs.size();
+ 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);
+ }
+ selectedSchedulings.clear();
+ selectedSimExeGraphs.clear();
+ int tmpexetime = this.scheduleSimulator.simulate(schedulings,
+ selectedSchedulings,
+ selectedSimExeGraphs);
+ if(tmpexetime < bestexetime) {
+ bestexetime = tmpexetime;
+ scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0));
+ schedulinggraph = newscheduleGraphs.elementAt(selectedSchedulings.elementAt(0));
+ System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n");
+ System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
+ tryindex++;
+ } else {
+ break;
+ }
+
+ // try to optimize the best one scheduling
+ newscheduleGraphs = optimizeScheduling(scheduleGraphs,
+ selectedSchedulings,
+ selectedSimExeGraphs,
+ gid,
+ this.scheduleThreshold);
+ }while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
+
+ scheduleGraphs = null;
+ newscheduleGraphs = null;
+ schedulings = null;
+ selectedSchedulings = null;
+ selectedSimExeGraphs = null;
+ multiparamtds = null;
+
+ String path = "scheduling_selected.dot";
+ SchedulingUtil.printScheduleGraph(path, schedulinggraph);
+
+ // Close the streams.
+ try {
+ stdout.close();
+ System.setOut(origOut);
+ } catch (Exception e) {
+ origOut.println("Redirect: Unable to close files!");
+ }
+
+ return scheduling;
+ }
+
+ private Vector<Vector<ScheduleNode>> optimizeScheduling(Vector<Vector<ScheduleNode>> scheduleGraphs,
+ Vector<Integer> selectedScheduleGraphs,
+ Vector<Vector<SimExecutionEdge>> selectedSimExeGraphs,
+ int gid,
+ int count) {
+ if(this.coreNum == 1) {
+ // single core
+ return null;
+ }
+
+ Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
+ int lgid = gid;
+ int left = count;
+ int num2try = (gid - 1) / this.scheduleThreshold;
+
+ for(int i = 0; i < selectedScheduleGraphs.size(); i++) {
+ Vector<ScheduleNode> schedulegraph = scheduleGraphs.elementAt(
+ selectedScheduleGraphs.elementAt(i));
+ Vector<SimExecutionEdge> simexegraph = selectedSimExeGraphs.elementAt(i);
+ Vector<SimExecutionEdge> criticalPath = analyzeCriticalPath(simexegraph);
+ // for test, print out the criticalPath
+ if(this.state.PRINTCRITICALPATH) {
+ SchedulingUtil.printCriticalPath("criticalpath_" + num2try + ".dot", criticalPath);
+ }
+ num2try++;
+ Vector<Vector<ScheduleNode>> tmposchedulegraphs = optimizeCriticalPath(schedulegraph,
+ criticalPath,
+ lgid,
+ left);
+ if(tmposchedulegraphs != null) {
+ if(optimizeschedulegraphs == null) {
+ optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
+ }
+ optimizeschedulegraphs.addAll(tmposchedulegraphs);
+ lgid += tmposchedulegraphs.size();
+ left -= tmposchedulegraphs.size();
+ if(left == 0) {
+ schedulegraph = null;
+ simexegraph = null;
+ criticalPath = null;
+ tmposchedulegraphs = null;
+ break;
+ }
+ }
+ schedulegraph = null;
+ simexegraph = null;
+ criticalPath = null;
+ tmposchedulegraphs = null;
+ }
+
+ return optimizeschedulegraphs;
+ }
+
+ private Vector<SimExecutionEdge> analyzeCriticalPath(Vector<SimExecutionEdge> simexegraph) {
+ // first figure out the critical path
+ Vector<SimExecutionEdge> criticalPath = new Vector<SimExecutionEdge>();
+ SimExecutionNode senode = (SimExecutionNode)simexegraph.elementAt(0).getSource();
+ getCriticalPath(senode, criticalPath);
+ computeBestStartPoint(criticalPath);
+
+ 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.size() > 0) {
+ // 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.
+ private int getCriticalPath(SimExecutionNode senode,
+ Vector<SimExecutionEdge> criticalPath) {
+ Vector<SimExecutionEdge> edges = (Vector<SimExecutionEdge>)senode.getEdgeVector();
+ if((edges == null) || (edges.size() == 0)) {
+ edges = null;
+ return 0;
+ }
+ Vector<SimExecutionEdge> subcriticalpath = new Vector<SimExecutionEdge>();
+ SimExecutionEdge edge = edges.elementAt(0);
+ int sum = edge.getWeight() + getCriticalPath((SimExecutionNode)edge.getTarget(),
+ subcriticalpath);
+ criticalPath.clear();
+ criticalPath.add(edge);
+ criticalPath.addAll(subcriticalpath);
+ for(int i = 1; i < edges.size(); i++) {
+ edge = edges.elementAt(i);
+ subcriticalpath.clear();
+ int tmpsum = edge.getWeight()
+ + getCriticalPath((SimExecutionNode)edge.getTarget(),
+ subcriticalpath);
+ if(tmpsum > sum) {
+ // find a longer path
+ sum = tmpsum;
+ criticalPath.clear();
+ criticalPath.add(edge);
+ criticalPath.addAll(subcriticalpath);
+ }
+ }
+ edges = null;
+ subcriticalpath.clear();
+ subcriticalpath = null;
+ return sum;
+ }
+
+ private Vector<Vector<ScheduleNode>> optimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
+ Vector<SimExecutionEdge> criticalPath,
+ int gid,
+ int count) {
+ Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
+ int lgid = gid;
+ int left = count;
+
+ // first check all seedges whose real start point is late than predicted
+ // 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>>>();
+ for(int i = 0; i < criticalPath.size(); i++) {
+ SimExecutionEdge seedge = criticalPath.elementAt(i);
+ int starttime = seedge.getBestStartPoint();
+ if(starttime < ((SimExecutionNode)seedge.getSource()).getTimepoint()) {
+ // 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
+ // be optimized, otherwise first considering optimize its predicates
+ if(seedge.getLastpredicateEdge().isFixedTime()) {
+ if(opcheckpoint >= starttime) {
+ // only consider the tasks with smallest best start time
+ if(opcheckpoint > starttime) {
+ tooptimize.clear();
+ opcheckpoint = starttime;
+ sparecores = seedge.getLastpredicateNode().getSpareCores();
+ }
+ 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(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(tmptime < starttime) {
+ starttime = tmptime;
+ td = tmptd;
+ }
+ 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>>>();
+ tooptimize2.put(corenum, candidatetasks);
+ Vector<Vector<ScheduleNode>> ops = innerOptimizeCriticalPath(scheduleGraph,
+ tooptimize2,
+ lgid,
+ left);
+ if(ops != null) {
+ if(optimizeschedulegraphs == null) {
+ optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
+ }
+ optimizeschedulegraphs.addAll(ops);
+ lgid += optimizeschedulegraphs.size();
+ left -= optimizeschedulegraphs.size();
+ }
+ tooptimize2.clear();
+ tooptimize2 = null;
+ ops = null;
+ }
+ }
+ 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();
+ for(int j = 0; j < edgevec.size(); j++) {
+ SimExecutionEdge edge = edgevec.elementAt(j);
+ SimExecutionEdge lastpredicateedge = edge.getLastpredicateEdge();
+ SimExecutionNode lastpredicatenode = edge.getLastpredicateNode();
+ // if(edge.getCoreNum() != lastpredicate.getCoreNum()) // should never hit this
+ 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) {
+ // update the predicate info
+ edge.getPredicates().remove(lastpredicateedge);
+ edge.addPredicate(criticalPath.elementAt(index));
+ break;
+ }
+ }
+ }
+ 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>>();
+ }
+ 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,
+ lgid,
+ left);
+ if(ops != null) {
+ if(optimizeschedulegraphs == null) {
+ optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
+ }
+ optimizeschedulegraphs.addAll(ops);
+ }
+ ops = null;
+ }
+ }
+ sparecores = null;
+ tooptimize.clear();
+ tooptimize = null;
+
+ return optimizeschedulegraphs;
+ }
+
+ private Vector<Vector<ScheduleNode>> innerOptimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
+ Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>> tooptimize,
+ int gid,
+ int count) {
+ int lgid = gid;
+ int left = count;
+ Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
+
+ // first clone the whole graph
+ Vector<ScheduleNode> newscheduleGraph =
+ cloneScheduleGraph(scheduleGraph, lgid);
+
+ // these nodes are root nodes
+ Vector<ScheduleNode> roots = new Vector<ScheduleNode>();
+ for(int i = 0; i < newscheduleGraph.size(); i++) {
+ roots.add(newscheduleGraph.elementAt(i));
+ }
+
+ // 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();
+ Hashtable<TaskDescriptor, 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();
+ // 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 cnode = it_cnodes.next();
+ if(cnode.getClassDescriptor().equals(cd)) {
+ tosplit.add(cnode);
+ numtosplit--;
+ }
+ }
+ 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);
+ }
+ tosplit = null;
+ }
+ }
+ candidatetasks = null;
+ it_tds = null;
+ }
+ it_cores = null;
+
+ if(tocombines.size() == 0) {
+ return optimizeschedulegraphs;
+ }
+
+ SchedulingUtil.assignCids(newscheduleGraph);
+
+ // get all the ScheduleEdge
+ Vector<ScheduleEdge> scheduleEdges = new Vector<ScheduleEdge>();
+ for(int i= 0; i < newscheduleGraph.size(); i++) {
+ scheduleEdges.addAll((Vector<ScheduleEdge>)newscheduleGraph.elementAt(i).getEdgeVector());
+ }
+
+ Vector<Vector<ScheduleNode>> rootNodes =
+ SchedulingUtil.rangeScheduleNodes(roots);
+ Vector<Vector<ScheduleNode>> nodes2combine =
+ SchedulingUtil.rangeScheduleNodes(tocombines);
+
+ CombinationUtil.CombineGenerator cGen =
+ CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine);
+ while ((left > 0) && (cGen.nextGen())) {
+ Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
+ Vector<ScheduleNode> sNodes = SchedulingUtil.generateScheduleGraph(this.state,
+ newscheduleGraph,
+ scheduleEdges,
+ rootNodes,
+ combine,
+ lgid++);
+ if(optimizeschedulegraphs == null) {
+ optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
+ }
+ optimizeschedulegraphs.add(sNodes);
+ combine = null;
+ sNodes = null;
+ left--;
+ }
+ rootNodes = null;
+ nodes2combine = null;
+ newscheduleGraph = null;
+ scheduleEdges.clear();
+ scheduleEdges = null;
+
+ return optimizeschedulegraphs;
+ }
+
+ private Vector<ScheduleNode> cloneScheduleGraph(Vector<ScheduleNode> scheduleGraph,
+ int gid) {
+ Vector<ScheduleNode> result = new Vector<ScheduleNode>();
+
+ // get all the ScheduleEdge
+ Vector<ScheduleEdge> scheduleEdges = new Vector<ScheduleEdge>();
+ for(int i= 0; i < scheduleGraph.size(); i++) {
+ scheduleEdges.addAll((Vector<ScheduleEdge>)scheduleGraph.elementAt(i).getEdgeVector());
+ }
+ Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash =
+ new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
+ Hashtable<ScheduleNode, ScheduleNode> sn2sn =
+ new Hashtable<ScheduleNode, ScheduleNode>();
+ SchedulingUtil.cloneScheduleGraph(scheduleGraph,
+ scheduleEdges,
+ sn2hash,
+ sn2sn,
+ result,
+ gid);
+
+ SchedulingUtil.assignCids(result);
+ scheduleEdges.clear();
+ scheduleEdges = null;
+ sn2hash.clear();
+ sn2hash = null;
+ sn2sn.clear();
+ sn2sn = null;
+
+ return result;
+ }
+
+ private Vector<Schedule> generateScheduling(Vector<ScheduleNode> scheduleGraph,
+ Vector<TaskDescriptor> multiparamtds) {
+ Hashtable<TaskDescriptor, Vector<Schedule>> td2cores =
+ new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam 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 =
+ new Hashtable<ScheduleNode, Integer>();
+ int j = 0;
+ for(j = 0; j < scheduleGraph.size(); j++) {
+ sn2coreNum.put(scheduleGraph.elementAt(j), j);
+ }
+ int startupcore = 0;
+ boolean setstartupcore = false;
+ Schedule startup = null;
+ int gid = scheduleGraph.elementAt(0).getGid();
+ for(j = 0; j < scheduleGraph.size(); j++) {
+ Schedule tmpSchedule = new Schedule(j, gid);
+ ScheduleNode sn = scheduleGraph.elementAt(j);
+
+ Vector<ClassNode> cNodes = sn.getClassNodes();
+ for(int k = 0; k < cNodes.size(); k++) {
+ Iterator it_flags = cNodes.elementAt(k).getFlags();
+ while(it_flags.hasNext()) {
+ FlagState fs = (FlagState)it_flags.next();
+ Iterator it_edges = fs.edges();
+ while(it_edges.hasNext()) {
+ TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
+ tmpSchedule.addTask(td);
+ if(!td2cores.containsKey(td)) {
+ td2cores.put(td, new Vector<Schedule>());
+ }
+ Vector<Schedule> tmpcores = td2cores.get(td);
+ if(!tmpcores.contains(tmpSchedule)) {
+ tmpcores.add(tmpSchedule);
+ }
+ tmpcores = null;
+ // if the FlagState can be fed to some multi-param tasks,
+ // need to record corresponding ally cores later
+ if(td.numParameters() > 1) {
+ tmpSchedule.addFState4TD(td, fs);
+ }
+ if(td.getParamType(0).getClassDesc().getSymbol().equals(
+ TypeUtil.StartupClass)) {
+ assert(!setstartupcore);
+ startupcore = j;
+ startup = tmpSchedule;
+ setstartupcore = true;
+ }
+ }
+ }
+ it_flags = null;
+ }
+ cNodes = null;
+
+ // 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()) {
+ ScheduleEdge se = (ScheduleEdge)it_edges.next();
+ ScheduleNode target = (ScheduleNode)se.getTarget();
+ Integer targetcore = sn2coreNum.get(target);
+ switch(se.getType()) {
+ case ScheduleEdge.NEWEDGE: {
+ for(int k = 0; k < se.getNewRate(); k++) {
+ tmpSchedule.addTargetCore(se.getFstate(), targetcore);
+ }
+ break;
+ }
+
+ case ScheduleEdge.TRANSEDGE: {
+ // 'transmit' edge
+ tmpSchedule.addTargetCore(se.getFstate(),
+ targetcore,
+ se.getTargetFState());
+ // 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();
+ Iterator it = tfs.edges();
+ while(it.hasNext()) {
+ TaskDescriptor td = ((FEdge)it.next()).getTask();
+ if(td.numParameters() > 1) {
+ if(tmpSchedule.getTasks().contains(td)) {
+ tmpSchedule.addFState4TD(td, fs);
+ }
+ }
+ }
+ break;
+ }
+ }
+ }
+ it_edges = sn.getScheduleEdgesIterator();
+ while(it_edges.hasNext()) {
+ ScheduleEdge se = (ScheduleEdge)it_edges.next();
+ switch(se.getType()) {
+ case ScheduleEdge.NEWEDGE: {
+ for(int k = 0; k < se.getNewRate(); k++) {
+ tmpSchedule.addTargetCore(se.getFstate(), j);
+ }
+ break;
+ }
+
+ case ScheduleEdge.TRANSEDGE: {
+ // 'transmit' edge
+ tmpSchedule.addTargetCore(se.getFstate(),
+ j,
+ se.getTargetFState());
+ break;
+ }
+ }
+ }
+ it_edges = null;
+ scheduling.add(tmpSchedule);
+ }
+
+ int number = this.coreNum;
+ if(scheduling.size() < number) {
+ number = scheduling.size();
+ }
+
+ // set up all the associate ally cores
+ if(multiparamtds.size() > 0) {
+ for(j = 0; j < multiparamtds.size(); ++j) {
+ TaskDescriptor td = multiparamtds.elementAt(j);
+ Vector<FEdge> fes =
+ (Vector<FEdge>) this.taskAnalysis.getFEdgesFromTD(td);
+ Vector<Schedule> cores = td2cores.get(td);
+ for(int k = 0; k < cores.size(); ++k) {
+ Schedule tmpSchedule = cores.elementAt(k);
+
+ 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))) {
+ // add up all possible cores' info
+ Iterator it_edges = tmpfs.edges();
+ while(it_edges.hasNext()) {
+ TaskDescriptor tmptd = ((FEdge)it_edges.next()).getTask();
+ if(!tmptds.contains(tmptd)) {
+ tmptds.add(tmptd);
+ Vector<Schedule> tmpcores = td2cores.get(tmptd);
+ for(int m = 0; m < tmpcores.size(); ++m) {
+ if(m != tmpSchedule.getCoreNum()) {
+ // if the FlagState can be fed to some multi-param tasks,
+ // need to record corresponding ally cores later
+ if(tmptd.numParameters() > 1) {
+ tmpSchedule.addAllyCore(tmpfs,
+ tmpcores.elementAt(m).getCoreNum());
+ } else {
+ tmpSchedule.addTargetCore(tmpfs,
+ tmpcores.elementAt(m).getCoreNum());
+ }
+ }
+ }
+ tmpcores = null;
+ }
+ }
+ it_edges = null;
+ }
+ tmptds = null;
+ }
+
+ if(cores.size() > 1) {
+ Vector<FlagState> tmpfss = tmpSchedule.getFStates4TD(td);
+ for(int h = 0; h < tmpfss.size(); ++h) {
+ for(int l = 0; l < cores.size(); ++l) {
+ if(l != k) {
+ tmpSchedule.addAllyCore(tmpfss.elementAt(h),
+ cores.elementAt(l).getCoreNum());
+ }
+ }
+ }
+ tmpfss = null;
+ }
+ }
+ fes = null;
+ cores = null;
+ }
+ }
+ td2cores = null;
+ sn2coreNum = null;
+
+ return scheduling;
+ }
+}
import IR.ClassDescriptor;
public class ObjectSimulator {
+ static int objid = 0;
+
+ int oid;
ClassDescriptor cd;
FlagState currentFS;
boolean changed;
boolean hold;
int version;
- public ObjectSimulator(ClassDescriptor cd, FlagState currentFS) {
+ public ObjectSimulator(ClassDescriptor cd,
+ FlagState currentFS) {
super();
+ this.oid = ObjectSimulator.objid++;
this.cd = cd;
this.currentFS = currentFS;
this.changed = true;
}
}
+ public int getOid() {
+ return oid;
+ }
+
public ClassDescriptor getCd() {
return cd;
}
/** This class holds flag transition diagram(s) can be put on one core.
*/
public class Schedule {
+ private int gid;
private int coreNum;
private Vector<TaskDescriptor> tasks;
private Hashtable<FlagState, Queue<Integer>> targetCores;
private Hashtable<FlagState, Vector<Integer>> allyCores;
private Hashtable<TaskDescriptor, Vector<FlagState>> td2fs;
- public Schedule(int coreNum) {
- super();
+ public Schedule(int coreNum,
+ int gid) {
+ this.gid = gid;
this.coreNum = coreNum;
this.tasks = null;
this.targetCores = null;
this.td2fs = null;
}
+ public int getGid() {
+ return gid;
+ }
+
public int getCoreNum() {
return coreNum;
}
return this.td2fs.get(td);
}
- public void addTargetCore(FlagState fstate, Integer targetCore) {
+ public void addTargetCore(FlagState fstate,
+ Integer targetCore) {
if(this.targetCores == null) {
this.targetCores = new Hashtable<FlagState, Queue<Integer>>();
}
// which reflects probabilities.
}
- public void addTargetCore(FlagState fstate, Integer targetCore, FlagState tfstate) {
+ public void addTargetCore(FlagState fstate,
+ Integer targetCore,
+ FlagState tfstate) {
if(this.targetCores == null) {
this.targetCores = new Hashtable<FlagState, Queue<Integer>>();
}
this.targetFState.put(fstate, tfstate);
}
- public void addAllyCore(FlagState fstate, Integer targetCore) {
+ public void addAllyCore(FlagState fstate,
+ Integer targetCore) {
if(this.allyCores == null) {
this.allyCores = new Hashtable<FlagState, Vector<Integer>>();
}
}
}
- public void addFState4TD(TaskDescriptor td, FlagState fstate) {
+ public void addFState4TD(TaskDescriptor td,
+ FlagState fstate) {
if(this.td2fs == null) {
this.td2fs = new Hashtable<TaskDescriptor, Vector<FlagState>>();
}
State state;
TaskAnalysis taskanalysis;
+
Vector<ScheduleNode> scheduleNodes;
Vector<ClassNode> classNodes;
Vector<ScheduleEdge> scheduleEdges;
int transThreshold;
+ int scheduleThreshold;
int coreNum;
Vector<Vector<ScheduleNode>> scheduleGraphs;
- Vector<Vector<Schedule>> schedulings;
- public ScheduleAnalysis(State state, TaskAnalysis taskanalysis) {
+ public ScheduleAnalysis(State state,
+ TaskAnalysis taskanalysis) {
this.state = state;
this.taskanalysis = taskanalysis;
this.scheduleNodes = new Vector<ScheduleNode>();
this.classNodes = new Vector<ClassNode>();
this.scheduleEdges = new Vector<ScheduleEdge>();
this.cd2ClassNode = new Hashtable<ClassDescriptor, ClassNode>();
- this.transThreshold = 45;
+ this.transThreshold = 45; // defaultly 45
+ this.scheduleThreshold = 1000; // defaultly 1000
this.coreNum = -1;
this.scheduleGraphs = null;
- this.schedulings = null;
}
public void setTransThreshold(int tt) {
this.transThreshold = tt;
}
+
+ public void setScheduleThreshold(int stt) {
+ this.scheduleThreshold = stt;
+ }
public int getCoreNum() {
return coreNum;
this.coreNum = coreNum;
}
- public Iterator getScheduleGraphs() {
- return this.scheduleGraphs.iterator();
- }
-
- public Iterator getSchedulingsIter() {
- return this.schedulings.iterator();
- }
-
- public Vector<Vector<Schedule>> getSchedulings() {
- return this.schedulings;
+ public Vector<Vector<ScheduleNode>> getScheduleGraphs() {
+ return this.scheduleGraphs;
}
// for test
public Vector<ScheduleEdge> getSEdges4Test() {
return scheduleEdges;
}
+
+ public void schedule() {
+ try {
+ Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
+ ScheduleNode startupNode = null;
+
+ // necessary preparation such as read profile info etc.
+ preSchedule();
+ // build the CFSTG
+ startupNode = buildCFSTG(toBreakDown);
+ // do Tree transform
+ treeTransform(toBreakDown, startupNode);
+ // do CFSTG transform to explore the potential parallelism as much
+ // as possible
+ CFSTGTransform();
+ // mappint to real multi-core processor
+ coreMapping();
+ } catch (Exception e) {
+ e.printStackTrace();
+ System.exit(-1);
+ }
+ }
+
+ private void preSchedule() {
+ this.checkBackEdge();
- public void preparation() {
+ // set up profiling data
+ if(state.USEPROFILE) {
+ java.util.Hashtable<String, TaskInfo> taskinfos =
+ new java.util.Hashtable<String, TaskInfo>();
+ this.readProfileInfo(taskinfos);
+
+ int tint = 0;
+ Iterator it_classes =
+ state.getClassSymbolTable().getDescriptorsIterator();
+ while(it_classes.hasNext()) {
+ ClassDescriptor cd = (ClassDescriptor) it_classes.next();
+ if(cd.hasFlags()) {
+ Vector rootnodes = this.taskanalysis.getRootNodes(cd);
+ if(rootnodes!=null) {
+ Iterator it_rootnodes = rootnodes.iterator();
+ while(it_rootnodes.hasNext()) {
+ FlagState root = (FlagState)it_rootnodes.next();
+ Vector allocatingTasks = root.getAllocatingTasks();
+ if(allocatingTasks != null) {
+ for(int k = 0; k < allocatingTasks.size(); k++) {
+ TaskDescriptor td =
+ (TaskDescriptor)allocatingTasks.elementAt(k);
+ Vector<FEdge> fev =
+ this.taskanalysis.getFEdgesFromTD(td);
+ int numEdges = fev.size();
+ for(int j = 0; j < numEdges; j++) {
+ FEdge pfe = fev.elementAt(j);
+ TaskInfo taskinfo =
+ taskinfos.get(td.getSymbol());
+ tint = taskinfo.m_exetime[pfe.getTaskExitIndex()];
+ pfe.setExeTime(tint);
+ double idouble =
+ taskinfo.m_probability[pfe.getTaskExitIndex()];
+ pfe.setProbability(idouble);
+ int newRate = 0;
+ if((taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()) != null)
+ && (taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()).containsKey(cd.getSymbol()))) {
+ newRate = taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()).get(cd.getSymbol());
+ }
+ pfe.addNewObjInfo(cd, newRate, idouble);
+ if(taskinfo.m_byObj != -1) {
+ ((FlagState)pfe.getSource()).setByObj(taskinfo.m_byObj);
+ }
+ }
+ fev = null;
+ }
+ }
+ }
+ }
+ Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator();
+ while(it_flags.hasNext()) {
+ FlagState fs = (FlagState)it_flags.next();
+ Iterator it_edges = fs.edges();
+ while(it_edges.hasNext()) {
+ FEdge edge = (FEdge)it_edges.next();
+ TaskInfo taskinfo = taskinfos.get(edge.getTask().getSymbol());
+ tint = taskinfo.m_exetime[edge.getTaskExitIndex()];
+ edge.setExeTime(tint);
+ double idouble = taskinfo.m_probability[edge.getTaskExitIndex()];
+ edge.setProbability(idouble);
+ if(taskinfo.m_byObj != -1) {
+ ((FlagState)edge.getSource()).setByObj(taskinfo.m_byObj);
+ }
+ }
+ }
+ }
+ }
+ taskinfos = null;
+ } else {
+ randomProfileSetting();
+ }
+ }
+
+ private void checkBackEdge() {
// Indentify backedges
- for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) {
+ Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();
+ while(it_classes.hasNext()) {
ClassDescriptor cd=(ClassDescriptor) it_classes.next();
if(cd.hasFlags()) {
Set<FlagState> fss = this.taskanalysis.getFlagStates(cd);
fss = null;
}
}
-
- // set up profiling data
- if(state.USEPROFILE) {
- try {
- // read in profile data and set
- FileInputStream inStream = new FileInputStream("/scratch/profile.rst");
- byte[] b = new byte[1024 * 100];
- int length = inStream.read(b);
- if(length < 0) {
- System.out.print("No content in input file: /scratch/profile.rst\n");
- System.exit(-1);
+ }
+
+ private void readProfileInfo(java.util.Hashtable<String, TaskInfo> taskinfos) {
+ try {
+ // read in profile data and set
+ FileInputStream inStream = new FileInputStream("/scratch/profile.rst");
+ byte[] b = new byte[1024 * 100];
+ int length = inStream.read(b);
+ if(length < 0) {
+ System.out.print("No content in input file: /scratch/profile.rst\n");
+ System.exit(-1);
+ }
+ String profiledata = new String(b, 0, length);
+
+ // profile data format:
+ // taskname, numoftaskexits(; exetime, probability, numofnewobjtypes(, newobj type, num of objs)+)+
+ int inindex = profiledata.indexOf('\n');
+ while((inindex != -1) ) {
+ String inline = profiledata.substring(0, inindex);
+ profiledata = profiledata.substring(inindex + 1);
+ //System.printString(inline + "\n");
+ int tmpinindex = inline.indexOf(',');
+ if(tmpinindex == -1) {
+ break;
+ }
+ String inname = inline.substring(0, tmpinindex);
+ String inint = inline.substring(tmpinindex + 1);
+ while(inint.startsWith(" ")) {
+ inint = inint.substring(1);
+ }
+ tmpinindex = inint.indexOf(',');
+ if(tmpinindex == -1) {
+ break;
+ }
+ int numofexits = Integer.parseInt(inint.substring(0, tmpinindex));
+ TaskInfo tinfo = new TaskInfo(numofexits);
+ inint = inint.substring(tmpinindex + 1);
+ while(inint.startsWith(" ")) {
+ inint = inint.substring(1);
}
- String profiledata = new String(b, 0, length);
- java.util.Hashtable<String, TaskInfo> taskinfos = new java.util.Hashtable<String, TaskInfo>();
+ tmpinindex = inint.indexOf(';');
+ int byObj = Integer.parseInt(inint.substring(0, tmpinindex));
+ if(byObj != -1) {
+ tinfo.m_byObj = byObj;
+ }
+ inint = inint.substring(tmpinindex + 1);
+ while(inint.startsWith(" ")) {
+ inint = inint.substring(1);
+ }
+ for(int i = 0; i < numofexits; i++) {
+ String tmpinfo = null;
+ if(i < numofexits - 1) {
+ tmpinindex = inint.indexOf(';');
+ tmpinfo = inint.substring(0, tmpinindex);
+ inint = inint.substring(tmpinindex + 1);
+ while(inint.startsWith(" ")) {
+ inint = inint.substring(1);
+ }
+ } else {
+ tmpinfo = inint;
+ }
- // profile data format:
- // taskname, numoftaskexits(; exetime, probability, numofnewobjtypes(, newobj type, num of objs)+)+
- int inindex = profiledata.indexOf('\n');
- while((inindex != -1) ) {
- String inline = profiledata.substring(0, inindex);
- profiledata = profiledata.substring(inindex + 1);
- //System.printString(inline + "\n");
- int tmpinindex = inline.indexOf(',');
- if(tmpinindex == -1) {
- break;
+ tmpinindex = tmpinfo.indexOf(',');
+ tinfo.m_exetime[i] = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
+ tmpinfo = tmpinfo.substring(tmpinindex + 1);
+ while(tmpinfo.startsWith(" ")) {
+ tmpinfo = tmpinfo.substring(1);
}
- String inname = inline.substring(0, tmpinindex);
- String inint = inline.substring(tmpinindex + 1);
- while(inint.startsWith(" ")) {
- inint = inint.substring(1);
+ tmpinindex = tmpinfo.indexOf(',');
+ tinfo.m_probability[i] = Double.parseDouble(tmpinfo.substring(0, tmpinindex));
+ tmpinfo = tmpinfo.substring(tmpinindex + 1);
+ while(tmpinfo.startsWith(" ")) {
+ tmpinfo = tmpinfo.substring(1);
}
- tmpinindex = inint.indexOf(',');
+ tmpinindex = tmpinfo.indexOf(',');
+ int numofnobjs = 0;
if(tmpinindex == -1) {
- break;
- }
- int numofexits = Integer.parseInt(inint.substring(0, tmpinindex));
- TaskInfo tinfo = new TaskInfo(numofexits);
- inint = inint.substring(tmpinindex + 1);
- while(inint.startsWith(" ")) {
- inint = inint.substring(1);
- }
- tmpinindex = inint.indexOf(';');
- int byObj = Integer.parseInt(inint.substring(0, tmpinindex));
- if(byObj != -1) {
- tinfo.m_byObj = byObj;
- }
- inint = inint.substring(tmpinindex + 1);
- while(inint.startsWith(" ")) {
- inint = inint.substring(1);
- }
- for(int i = 0; i < numofexits; i++) {
- String tmpinfo = null;
- if(i < numofexits - 1) {
- tmpinindex = inint.indexOf(';');
- tmpinfo = inint.substring(0, tmpinindex);
- inint = inint.substring(tmpinindex + 1);
- while(inint.startsWith(" ")) {
- inint = inint.substring(1);
- }
- } else {
- tmpinfo = inint;
- }
-
- tmpinindex = tmpinfo.indexOf(',');
- tinfo.m_exetime[i] = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
- tmpinfo = tmpinfo.substring(tmpinindex + 1);
- while(tmpinfo.startsWith(" ")) {
- tmpinfo = tmpinfo.substring(1);
+ numofnobjs = Integer.parseInt(tmpinfo);
+ if(numofnobjs != 0) {
+ System.err.println("Error profile data format!");
+ System.exit(-1);
}
- tmpinindex = tmpinfo.indexOf(',');
- tinfo.m_probability[i] = Double.parseDouble(tmpinfo.substring(0, tmpinindex));
+ } else {
+ tinfo.m_newobjinfo.setElementAt(new Hashtable<String,Integer>(), i);
+ numofnobjs = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
tmpinfo = tmpinfo.substring(tmpinindex + 1);
while(tmpinfo.startsWith(" ")) {
tmpinfo = tmpinfo.substring(1);
}
- tmpinindex = tmpinfo.indexOf(',');
- int numofnobjs = 0;
- if(tmpinindex == -1) {
- numofnobjs = Integer.parseInt(tmpinfo);
- if(numofnobjs != 0) {
- System.err.println("Error profile data format!");
- System.exit(-1);
- }
- } else {
- tinfo.m_newobjinfo.setElementAt(new Hashtable<String,Integer>(), i);
- numofnobjs = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
+ for(int j = 0; j < numofnobjs; j++) {
+ tmpinindex = tmpinfo.indexOf(',');
+ String nobjtype = tmpinfo.substring(0, tmpinindex);
tmpinfo = tmpinfo.substring(tmpinindex + 1);
while(tmpinfo.startsWith(" ")) {
tmpinfo = tmpinfo.substring(1);
}
- for(int j = 0; j < numofnobjs; j++) {
+ int objnum = 0;
+ if(j < numofnobjs - 1) {
tmpinindex = tmpinfo.indexOf(',');
- String nobjtype = tmpinfo.substring(0, tmpinindex);
+ objnum = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
tmpinfo = tmpinfo.substring(tmpinindex + 1);
while(tmpinfo.startsWith(" ")) {
tmpinfo = tmpinfo.substring(1);
}
- int objnum = 0;
- if(j < numofnobjs - 1) {
- tmpinindex = tmpinfo.indexOf(',');
- objnum = Integer.parseInt(tmpinfo.substring(0, tmpinindex));
- tmpinfo = tmpinfo.substring(tmpinindex + 1);
- while(tmpinfo.startsWith(" ")) {
- tmpinfo = tmpinfo.substring(1);
- }
- } else {
- objnum = Integer.parseInt(tmpinfo);
- }
- tinfo.m_newobjinfo.elementAt(i).put(nobjtype, objnum);
+ } else {
+ objnum = Integer.parseInt(tmpinfo);
}
+ tinfo.m_newobjinfo.elementAt(i).put(nobjtype, objnum);
}
}
- taskinfos.put(inname, tinfo);
- inindex = profiledata.indexOf('\n');
}
+ taskinfos.put(inname, tinfo);
+ inindex = profiledata.indexOf('\n');
+ }
+ } catch(Exception e) {
+ e.printStackTrace();
+ }
+ }
- int tint = 0;
- for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) {
- ClassDescriptor cd=(ClassDescriptor) it_classes.next();
- if(cd.hasFlags()) {
- Vector rootnodes=this.taskanalysis.getRootNodes(cd);
- if(rootnodes!=null) {
- for(Iterator it_rootnodes=rootnodes.iterator(); it_rootnodes.hasNext();) {
- FlagState root=(FlagState)it_rootnodes.next();
- Vector allocatingTasks = root.getAllocatingTasks();
- if(allocatingTasks != null) {
- for(int k = 0; k < allocatingTasks.size(); k++) {
- TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
- Vector<FEdge> fev = (Vector<FEdge>)this.taskanalysis.getFEdgesFromTD(td);
- int numEdges = fev.size();
- int total = 100;
- for(int j = 0; j < numEdges; j++) {
- FEdge pfe = fev.elementAt(j);
- TaskInfo taskinfo = taskinfos.get(td.getSymbol());
- tint = taskinfo.m_exetime[pfe.getTaskExitIndex()];
- pfe.setExeTime(tint);
- double idouble = taskinfo.m_probability[pfe.getTaskExitIndex()];
- pfe.setProbability(idouble);
- int newRate = 0;
- if((taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()) != null)
- && (taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()).containsKey(cd.getSymbol()))) {
- newRate = taskinfo.m_newobjinfo.elementAt(pfe.getTaskExitIndex()).get(cd.getSymbol());
- }
- pfe.addNewObjInfo(cd, newRate, idouble);
- if(taskinfo.m_byObj != -1) {
- ((FlagState)pfe.getSource()).setByObj(taskinfo.m_byObj);
- }
+ // for test
+ private void randomProfileSetting() {
+ // Randomly set the newRate and probability of FEdges
+ java.util.Random r=new java.util.Random();
+ int tint = 0;
+ for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) {
+ ClassDescriptor cd=(ClassDescriptor) it_classes.next();
+ if(cd.hasFlags()) {
+ Vector rootnodes=this.taskanalysis.getRootNodes(cd);
+ if(rootnodes!=null) {
+ for(Iterator it_rootnodes=rootnodes.iterator(); it_rootnodes.hasNext();) {
+ FlagState root=(FlagState)it_rootnodes.next();
+ Vector allocatingTasks = root.getAllocatingTasks();
+ if(allocatingTasks != null) {
+ for(int k = 0; k < allocatingTasks.size(); k++) {
+ TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
+ Vector<FEdge> fev = (Vector<FEdge>)this.taskanalysis.getFEdgesFromTD(td);
+ int numEdges = fev.size();
+ int total = 100;
+ for(int j = 0; j < numEdges; j++) {
+ FEdge pfe = fev.elementAt(j);
+ if(numEdges - j == 1) {
+ pfe.setProbability(total);
+ } else {
+ if((total != 0) && (total != 1)) {
+ do {
+ tint = r.nextInt()%total;
+ } while(tint <= 0);
}
- fev = null;
+ pfe.setProbability(tint);
+ total -= tint;
}
- }
- }
- }
- Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator();
- while(it_flags.hasNext()) {
- FlagState fs = (FlagState)it_flags.next();
- Iterator it_edges = fs.edges();
- int total = 100;
- while(it_edges.hasNext()) {
- FEdge edge = (FEdge)it_edges.next();
- TaskInfo taskinfo = taskinfos.get(edge.getTask().getSymbol());
- tint = taskinfo.m_exetime[edge.getTaskExitIndex()];
- edge.setExeTime(tint);
- double idouble = taskinfo.m_probability[edge.getTaskExitIndex()];
- edge.setProbability(idouble);
- if(taskinfo.m_byObj != -1) {
- ((FlagState)edge.getSource()).setByObj(taskinfo.m_byObj);
- }
- }
- }
- }
- }
- taskinfos = null;
- } catch(Exception e) {
- e.printStackTrace();
- }
- } else {
- // for test
- // Randomly set the newRate and probability of FEdges
- java.util.Random r=new java.util.Random();
- int tint = 0;
- for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext();) {
- ClassDescriptor cd=(ClassDescriptor) it_classes.next();
- if(cd.hasFlags()) {
- Vector rootnodes=this.taskanalysis.getRootNodes(cd);
- if(rootnodes!=null) {
- for(Iterator it_rootnodes=rootnodes.iterator(); it_rootnodes.hasNext();) {
- FlagState root=(FlagState)it_rootnodes.next();
- Vector allocatingTasks = root.getAllocatingTasks();
- if(allocatingTasks != null) {
- for(int k = 0; k < allocatingTasks.size(); k++) {
- TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
- Vector<FEdge> fev = (Vector<FEdge>)this.taskanalysis.getFEdgesFromTD(td);
- int numEdges = fev.size();
- int total = 100;
- for(int j = 0; j < numEdges; j++) {
- FEdge pfe = fev.elementAt(j);
- if(numEdges - j == 1) {
- pfe.setProbability(total);
- } else {
- if((total != 0) && (total != 1)) {
- do {
- tint = r.nextInt()%total;
- } while(tint <= 0);
- }
- pfe.setProbability(tint);
- total -= tint;
- }
- //do {
+ //do {
// tint = r.nextInt()%10;
- // } while(tint <= 0);
- //int newRate = tint;
- //int newRate = (j+1)%2+1;
- int newRate = 1;
- String cdname = cd.getSymbol();
- if((cdname.equals("SeriesRunner")) ||
- (cdname.equals("MDRunner")) ||
- (cdname.equals("Stage")) ||
- (cdname.equals("AppDemoRunner")) ||
- (cdname.equals("FilterBankAtom")) ||
- (cdname.equals("Grid")) ||
- (cdname.equals("Fractal"))) {
- newRate = 16;
- } else if(cdname.equals("SentenceParser")) {
- newRate = 4;
- }
- //do {
- // tint = r.nextInt()%100;
- // } while(tint <= 0);
- // int probability = tint;
- int probability = 100;
- pfe.addNewObjInfo(cd, newRate, probability);
+ // } while(tint <= 0);
+ //int newRate = tint;
+ //int newRate = (j+1)%2+1;
+ int newRate = 1;
+ String cdname = cd.getSymbol();
+ if((cdname.equals("SeriesRunner")) ||
+ (cdname.equals("MDRunner")) ||
+ (cdname.equals("Stage")) ||
+ (cdname.equals("AppDemoRunner")) ||
+ (cdname.equals("FilterBankAtom")) ||
+ (cdname.equals("Grid")) ||
+ (cdname.equals("Fractal"))) {
+ newRate = 16;
+ } else if(cdname.equals("SentenceParser")) {
+ newRate = 4;
}
- fev = null;
+ //do {
+ // tint = r.nextInt()%100;
+ // } while(tint <= 0);
+ // int probability = tint;
+ int probability = 100;
+ pfe.addNewObjInfo(cd, newRate, probability);
}
+ fev = null;
}
}
}
+ }
- Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator();
- while(it_flags.hasNext()) {
- FlagState fs = (FlagState)it_flags.next();
- Iterator it_edges = fs.edges();
- int total = 100;
- while(it_edges.hasNext()) {
- //do {
- // tint = r.nextInt()%10;
- // } while(tint <= 0);
- tint = 3;
- FEdge edge = (FEdge)it_edges.next();
- edge.setExeTime(tint);
- if((fs.getClassDescriptor().getSymbol().equals("MD")) && (edge.getTask().getSymbol().equals("t6"))) {
- if(edge.isbackedge()) {
- if(edge.getTarget().equals(edge.getSource())) {
- edge.setProbability(93.75);
- } else {
- edge.setProbability(3.125);
- }
+ Iterator it_flags = this.taskanalysis.getFlagStates(cd).iterator();
+ while(it_flags.hasNext()) {
+ FlagState fs = (FlagState)it_flags.next();
+ Iterator it_edges = fs.edges();
+ int total = 100;
+ while(it_edges.hasNext()) {
+ //do {
+ // tint = r.nextInt()%10;
+ // } while(tint <= 0);
+ tint = 3;
+ FEdge edge = (FEdge)it_edges.next();
+ edge.setExeTime(tint);
+ if((fs.getClassDescriptor().getSymbol().equals("MD"))
+ && (edge.getTask().getSymbol().equals("t6"))) {
+ if(edge.isbackedge()) {
+ if(edge.getTarget().equals(edge.getSource())) {
+ edge.setProbability(93.75);
} else {
edge.setProbability(3.125);
}
- continue;
- }
- if(!it_edges.hasNext()) {
- edge.setProbability(total);
} else {
- if((total != 0) && (total != 1)) {
- do {
- tint = r.nextInt()%total;
- } while(tint <= 0);
- }
- edge.setProbability(tint);
- total -= tint;
+ edge.setProbability(3.125);
+ }
+ continue;
+ }
+ if(!it_edges.hasNext()) {
+ edge.setProbability(total);
+ } else {
+ if((total != 0) && (total != 1)) {
+ do {
+ tint = r.nextInt()%total;
+ } while(tint <= 0);
}
+ edge.setProbability(tint);
+ total -= tint;
}
}
}
}
}
- public void preSchedule() {
- Hashtable<ClassDescriptor, ClassNode> cdToCNodes = new Hashtable<ClassDescriptor, ClassNode>();
+ private ScheduleNode buildCFSTG(Vector<ScheduleEdge> toBreakDown) {
+ Hashtable<ClassDescriptor, ClassNode> cdToCNodes =
+ new Hashtable<ClassDescriptor, ClassNode>();
// Build the combined flag transition diagram
// First, for each class create a ClassNode
- for(Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext(); ) {
+ Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator();
+ while(it_classes.hasNext()) {
ClassDescriptor cd = (ClassDescriptor) it_classes.next();
Set<FlagState> fStates = taskanalysis.getFlagStates(cd);
Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
Vector rootnodes = taskanalysis.getRootNodes(cd);
- if(((rootnodes != null) && (rootnodes.size() > 0)) || (cd.getSymbol().equals(TypeUtil.StartupClass))) {
+ if(((rootnodes != null) && (rootnodes.size() > 0))
+ || (cd.getSymbol().equals(TypeUtil.StartupClass))) {
ClassNode cNode = new ClassNode(cd, sFStates);
cNode.setSorted(true);
classNodes.add(cNode);
}
// Create 'new' edges between the ScheduleNodes.
- Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
+ //Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
for(i = 0; i < classNodes.size(); i++) {
ClassNode cNode = classNodes.elementAt(i);
ClassDescriptor cd = cNode.getClassDescriptor();
ClassDescriptor pcd = pfs.getClassDescriptor();
ClassNode pcNode = cdToCNodes.get(pcd);
- ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", root, ScheduleEdge.NEWEDGE, 0);
+ ScheduleEdge sEdge = new ScheduleEdge(sNode,
+ "new",
+ root,
+ ScheduleEdge.NEWEDGE,
+ 0);
sEdge.setFEdge(pfe);
sEdge.setSourceCNode(pcNode);
sEdge.setTargetCNode(cNode);
}
}
cdToCNodes = null;
-
+
+ return startupNode;
+ }
+
+ private void treeTransform(Vector<ScheduleEdge> toBreakDown,
+ ScheduleNode startupNode) {
+ int i = 0;
+
// Break down the 'cycle's
try {
for(i = 0; i < toBreakDown.size(); i++ ) {
toVisit = null;
if(this.state.PRINTSCHEDULING) {
- SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes);
+ SchedulingUtil.printScheduleGraph("scheduling_ori.dot",
+ this.scheduleNodes);
}
}
- public void scheduleAnalysis() {
+ private void CFSTGTransform() {
// First iteration
int i = 0;
//Access the ScheduleEdges in reverse topology order
ses = null;
}
keys = null;
- fe2ses.clear();
- sn2fes.clear();
}
+ fe2ses.clear();
+ sn2fes.clear();
fe2ses = null;
sn2fes = null;
}
}
- private void handleScheduleEdge(ScheduleEdge se, boolean merge) {
+ private void handleScheduleEdge(ScheduleEdge se,
+ boolean merge) {
try {
int rate = 0;
int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
scheduleNodes.remove(se.getTarget());
scheduleEdges.remove(se);
// As se has been changed into an internal edge inside a ScheduleNode,
- // change the source and target of se from original ScheduleNodes into ClassNodes.
+ // change the source and target of se from original ScheduleNodes
+ // into ClassNodes.
if(se.getType() == ScheduleEdge.NEWEDGE) {
se.setTarget(se.getTargetCNode());
- se.setSource(se.getSourceCNode());
- se.getTargetCNode().addEdge(se);
+ //se.setSource(se.getSourceCNode());
+ //se.getTargetCNode().addEdge(se);
+ se.getSourceCNode().addEdge(se);
}
} else {
// clone the whole ScheduleNode lists starting with se's target
}
}
- private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) throws Exception {
+ private void cloneSNodeList(ScheduleEdge sEdge,
+ boolean copyIE) throws Exception {
Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>(); // hashtable from classnode in orignal se's targe to cloned one
ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
scheduleNodes.add(csNode);
return exeTime;
}
- private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) {
+ private ScheduleNode splitSNode(ScheduleEdge se,
+ boolean copy) {
assert(ScheduleEdge.NEWEDGE == se.getType());
FEdge fe = se.getFEdge();
sEdge.setTransTime(cNode.getTransTime());
se.getSource().addEdge(sEdge);
scheduleEdges.add(sEdge);
- // remove the ClassNodes and internal ScheduleEdges out of this subtree to the new ScheduleNode
+ // remove the ClassNodes and internal ScheduleEdges out of this subtree
+ // to the new ScheduleNode
ScheduleNode oldSNode = (ScheduleNode)se.getSource();
Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
while(it_isEdges.hasNext()) {
ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
if(rCNodes.contains(tse.getSourceCNode())) {
- if(sCNode == tse.getSourceCNode()) {
- if ((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
+ if(sCNode.equals(tse.getSourceCNode())) {
+ if (!(tse.getSourceFState().equals(fs))
+ && (sFStates.contains(tse.getSourceFState()))) {
tse.setSource(cNode);
tse.setSourceCNode(cNode);
} else {
Iterator it_sEdges = se.getSource().edges();
while(it_sEdges.hasNext()) {
ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
- if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
- if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
+ if(!(tse.equals(se)) && !(tse.equals(sEdge))
+ && (tse.getSourceCNode().equals(sCNode))) {
+ if(!(tse.getSourceFState().equals(fs))
+ && (sFStates.contains(tse.getSourceFState()))) {
tse.setSource(sNode);
tse.setSourceCNode(cNode);
sNode.getEdgeVector().addElement(tse);
scheduleNodes.remove(se.getTarget());
scheduleEdges.removeElement(se);
// As se has been changed into an internal edge inside a ScheduleNode,
- // change the source and target of se from original ScheduleNodes into ClassNodes.
+ // change the source and target of se from original ScheduleNodes
+ // into ClassNodes.
if(se.getType() == ScheduleEdge.NEWEDGE) {
se.setTarget(se.getTargetCNode());
- se.setSource(se.getSourceCNode());
- se.getTargetCNode().addEdge(se);
+ //se.setSource(se.getSourceCNode());
+ //se.getTargetCNode().addEdge(se);
+ se.getSourceCNode().addEdge(se);
}
} else {
sNode.setCid(ScheduleNode.colorID++);
return sNode;
}
- public void schedule() throws Exception {
+ // TODO: restrict the number of generated scheduling according to the setted
+ // scheduleThreshold
+ private void coreMapping() throws Exception {
if(this.coreNum == -1) {
throw new Exception("Error: un-initialized coreNum when doing scheduling.");
}
SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
}
} else {
- // Go through all the Scheudle Nodes, organize them in order of their cid
- Vector<Vector<ScheduleNode>> sNodeVecs = new Vector<Vector<ScheduleNode>>();
- for(int i = 0; i < this.scheduleNodes.size(); i++) {
- ScheduleNode tmpn = this.scheduleNodes.elementAt(i);
- int index = tmpn.getCid();
- while(sNodeVecs.size() <= index) {
- sNodeVecs.add(null);
- }
- if(sNodeVecs.elementAt(index) == null) {
- sNodeVecs.setElementAt(new Vector<ScheduleNode>(), index);
- }
- sNodeVecs.elementAt(index).add(tmpn);
- }
+ // Go through all the Schedule Nodes, organize them in order of their cid
+ Vector<Vector<ScheduleNode>> sNodeVecs =
+ SchedulingUtil.rangeScheduleNodes(this.scheduleNodes);
- CombinationUtil.RootsGenerator rGen = CombinationUtil.allocateRootsGenerator(sNodeVecs, this.coreNum);
+ CombinationUtil.RootsGenerator rGen =
+ CombinationUtil.allocateRootsGenerator(sNodeVecs,
+ this.coreNum);
int gid = 1;
- while(rGen.nextGen()) {
+ while((gid <= this.scheduleThreshold) && (rGen.nextGen())) {
// first get the chosen rootNodes
Vector<Vector<ScheduleNode>> rootNodes = rGen.getRootNodes();
Vector<Vector<ScheduleNode>> nodes2combine = rGen.getNode2Combine();
- CombinationUtil.CombineGenerator cGen = CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine);
- while (cGen.nextGen()) {
+ CombinationUtil.CombineGenerator cGen =
+ CombinationUtil.allocateCombineGenerator(rootNodes,
+ nodes2combine);
+ while((gid <= this.scheduleThreshold) && cGen.nextGen()) {
Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
- Vector<ScheduleNode> sNodes = generateScheduling(rootNodes, combine, gid++);
+ Vector<ScheduleNode> sNodes = SchedulingUtil.generateScheduleGraph(this.state,
+ this.scheduleNodes,
+ this.scheduleEdges,
+ rootNodes,
+ combine,
+ gid++);
this.scheduleGraphs.add(sNodes);
combine = null;
sNodes = null;
}
sNodeVecs = null;
}
-
- // Generate schedulings according to result schedule graph
- if(this.schedulings == null) {
- this.schedulings = new Vector<Vector<Schedule>>();
- }
-
- Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
- Iterator it_tasks = state.getTaskSymbolTable().getDescriptorsIterator();
- while(it_tasks.hasNext()) {
- TaskDescriptor td = (TaskDescriptor)it_tasks.next();
- if(td.numParameters() > 1) {
- multiparamtds.addElement(td);
- }
- }
-
- for(int i = 0; i < this.scheduleGraphs.size(); i++) {
- Hashtable<TaskDescriptor, Vector<Schedule>> td2cores = new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks reside on which cores
- Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
- Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
- // for each ScheduleNode create a schedule node representing a core
- Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
- int j = 0;
- for(j = 0; j < scheduleGraph.size(); j++) {
- sn2coreNum.put(scheduleGraph.elementAt(j), j);
- }
- int startupcore = 0;
- boolean setstartupcore = false;
- Schedule startup = null;
- for(j = 0; j < scheduleGraph.size(); j++) {
- Schedule tmpSchedule = new Schedule(j);
- ScheduleNode sn = scheduleGraph.elementAt(j);
-
- Vector<ClassNode> cNodes = sn.getClassNodes();
- for(int k = 0; k < cNodes.size(); k++) {
- Iterator it_flags = cNodes.elementAt(k).getFlags();
- while(it_flags.hasNext()) {
- FlagState fs = (FlagState)it_flags.next();
- Iterator it_edges = fs.edges();
- while(it_edges.hasNext()) {
- TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
- tmpSchedule.addTask(td);
- if(!td2cores.containsKey(td)) {
- td2cores.put(td, new Vector<Schedule>());
- }
- Vector<Schedule> tmpcores = td2cores.get(td);
- if(!tmpcores.contains(tmpSchedule)) {
- tmpcores.add(tmpSchedule);
- }
- tmpcores = null;
- // if the FlagState can be fed to some multi-param tasks,
- // need to record corresponding ally cores later
- if(td.numParameters() > 1) {
- tmpSchedule.addFState4TD(td, fs);
- }
- if(td.getParamType(0).getClassDesc().getSymbol().equals(TypeUtil.StartupClass)) {
- assert(!setstartupcore);
- startupcore = j;
- startup = tmpSchedule;
- setstartupcore = true;
- }
- }
- }
- }
- cNodes = null;
-
- // 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()) {
- ScheduleEdge se = (ScheduleEdge)it_edges.next();
- ScheduleNode target = (ScheduleNode)se.getTarget();
- Integer targetcore = sn2coreNum.get(target);
- switch(se.getType()) {
- case ScheduleEdge.NEWEDGE: {
- for(int k = 0; k < se.getNewRate(); k++) {
- tmpSchedule.addTargetCore(se.getFstate(), targetcore);
- }
- break;
- }
-
- case ScheduleEdge.TRANSEDGE: {
- // 'transmit' edge
- tmpSchedule.addTargetCore(se.getFstate(), targetcore, se.getTargetFState());
- // 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();
- Iterator it = tfs.edges();
- while(it.hasNext()) {
- TaskDescriptor td = ((FEdge)it.next()).getTask();
- if(td.numParameters() > 1) {
- if(tmpSchedule.getTasks().contains(td)) {
- tmpSchedule.addFState4TD(td, fs);
- }
- }
- }
- break;
- }
- }
- }
- it_edges = sn.getScheduleEdgesIterator();
- while(it_edges.hasNext()) {
- ScheduleEdge se = (ScheduleEdge)it_edges.next();
- switch(se.getType()) {
- case ScheduleEdge.NEWEDGE: {
- for(int k = 0; k < se.getNewRate(); k++) {
- tmpSchedule.addTargetCore(se.getFstate(), j);
- }
- break;
- }
-
- case ScheduleEdge.TRANSEDGE: {
- // 'transmit' edge
- tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState());
- break;
- }
- }
- }
- scheduling.add(tmpSchedule);
- }
-
- int number = this.coreNum;
- if(scheduling.size() < number) {
- number = scheduling.size();
- }
-
- // set up all the associate ally cores
- if(multiparamtds.size() > 0) {
- for(j = 0; j < multiparamtds.size(); ++j) {
- TaskDescriptor td = multiparamtds.elementAt(j);
- Vector<FEdge> fes = (Vector<FEdge>) this.taskanalysis.getFEdgesFromTD(td);
- Vector<Schedule> cores = td2cores.get(td);
- for(int k = 0; k < cores.size(); ++k) {
- Schedule tmpSchedule = cores.elementAt(k);
-
- 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().contains(tmpfs))) {
- // add up all possible cores' info
- Iterator it_edges = tmpfs.edges();
- while(it_edges.hasNext()) {
- TaskDescriptor tmptd = ((FEdge)it_edges.next()).getTask();
- if(!tmptds.contains(tmptd)) {
- tmptds.add(tmptd);
- Vector<Schedule> tmpcores = td2cores.get(tmptd);
- for(int m = 0; m < tmpcores.size(); ++m) {
- if(m != tmpSchedule.getCoreNum()) {
- // if the FlagState can be fed to some multi-param tasks,
- // need to record corresponding ally cores later
- if(tmptd.numParameters() > 1) {
- tmpSchedule.addAllyCore(tmpfs, tmpcores.elementAt(m).getCoreNum());
- } else {
- tmpSchedule.addTargetCore(tmpfs, tmpcores.elementAt(m).getCoreNum());
- }
- }
- }
- tmpcores = null;
- }
- }
- }
- tmptds = null;
- }
-
- if(cores.size() > 1) {
- Vector<FlagState> tmpfss = tmpSchedule.getFStates4TD(td);
- for(int h = 0; h < tmpfss.size(); ++h) {
- for(int l = 0; l < cores.size(); ++l) {
- if(l != k) {
- tmpSchedule.addAllyCore(tmpfss.elementAt(h), cores.elementAt(l).getCoreNum());
- }
- }
- }
- tmpfss = null;
- }
- }
- fes = null;
- cores = null;
- }
- }
- this.schedulings.add(scheduling);
- td2cores = null;
- scheduleGraph = null;
- scheduling = null;
- sn2coreNum = null;
- }
- multiparamtds = null;
- }
-
- public Vector<ScheduleNode> generateScheduling(Vector<Vector<ScheduleNode>> rootnodes, Vector<Vector<CombinationUtil.Combine>> combine, int gid) {
- Vector<ScheduleNode> result = new Vector<ScheduleNode>();
-
- // clone the ScheduleNodes
- Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
- Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
- for(int i = 0; i < this.scheduleNodes.size(); i++) {
- Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
- ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
- ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
- result.add(i, temp);
- sn2hash.put(temp, cn2cn);
- sn2sn.put(tocopy, temp);
- cn2cn = null;
- }
- // clone the ScheduleEdges
- for(int i = 0; i < this.scheduleEdges.size(); i++) {
- ScheduleEdge sse = this.scheduleEdges.elementAt(i);
- ScheduleNode csource = sn2sn.get(sse.getSource());
- ScheduleNode ctarget = sn2sn.get(sse.getTarget());
- Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
- Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
- ScheduleEdge se = null;
- switch(sse.getType()) {
- case ScheduleEdge.NEWEDGE: {
- se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid); //new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
- se.setProbability(sse.getProbability());
- se.setNewRate(sse.getNewRate());
- break;
- }
-
- case ScheduleEdge.TRANSEDGE: {
- se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid); //new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
- break;
- }
- }
- se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
- se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
- se.setFEdge(sse.getFEdge());
- se.setTargetFState(sse.getTargetFState());
- se.setIsclone(true);
- csource.addEdge(se);
- sourcecn2cn = null;
- targetcn2cn = null;
- }
-
- // combine those nodes in combine with corresponding rootnodes
- for(int i = 0; i < combine.size(); i++) {
- if(combine.elementAt(i) != null) {
- for(int j = 0; j < combine.elementAt(i).size(); j++) {
- CombinationUtil.Combine tmpcombine = combine.elementAt(i).elementAt(j);
- ScheduleNode tocombine = sn2sn.get(tmpcombine.node);
- ScheduleNode root = sn2sn.get(rootnodes.elementAt(tmpcombine.root).elementAt(tmpcombine.index));
- ScheduleEdge se = (ScheduleEdge)tocombine.inedges().next();
- try {
- if(root.equals(((ScheduleNode)se.getSource()))) {
- root.mergeSEdge(se);
- if(ScheduleEdge.NEWEDGE == se.getType()) {
- // As se has been changed into an internal edge inside a ScheduleNode,
- // change the source and target of se from original ScheduleNodes into ClassNodes.
- se.setTarget(se.getTargetCNode());
- se.setSource(se.getSourceCNode());
- se.getTargetCNode().addEdge(se);
- }
- } else {
- root.mergeSNode(tocombine);
- }
- } catch(Exception e) {
- e.printStackTrace();
- System.exit(-1);
- }
- result.removeElement(tocombine);
- }
- }
- }
-
- sn2hash = null;
- sn2sn = null;
-
- if(this.state.PRINTSCHEDULING) {
- String path = "scheduling_" + gid + ".dot";
- SchedulingUtil.printScheduleGraph(path, result);
- }
-
- return result;
}
static class TaskInfo {
/** Class Constructor
*
*/
- public ScheduleEdge(ScheduleNode target, String label, FlagState fstate, int type, int gid) {
+ public ScheduleEdge(ScheduleNode target,
+ String label,
+ FlagState fstate,
+ int type,
+ int gid) {
super(target);
this.uid = ScheduleEdge.nodeID++;
this.gid = gid;
public static int colorID = 0;
private Vector<ClassNode> classNodes;
- Vector<ScheduleEdge> scheduleEdges;
+ private Vector<ScheduleEdge> scheduleEdges;
private int executionTime;
+
+ private int hashcid;
/** Class constructor
* @param cd ClassDescriptor
this.executionTime = -1;
this.classNodes = null;
this.scheduleEdges = null;
+ this.hashcid = 0;
}
public ScheduleNode(ClassNode cn, int gid) {
this.classNodes.add(cn);
this.addEdge(cn.getEdgeVector());
this.executionTime = -1;
+ this.hashcid = 0;
+ }
+
+ public int getGid() {
+ return gid;
}
public int getuid() {
scheduleEdges = null;
}
+ public int getHashcid() {
+ return hashcid;
+ }
+
+ public void computeHashcid() {
+ this.hashcid = 0;
+ /*if(this.mergedcids != null) {
+ for(int i = 0; i < this.mergedcids.size(); i++) {
+ this.hashcid = this.hashcid * 31 + this.mergedcids.elementAt(i);
+ }
+ }*/
+ Vector<Integer> mergedcids = new Vector<Integer>();
+ for(int i = 0; i < this.classNodes.size(); i++) {
+ int tomerge = this.classNodes.elementAt(i).getCid();
+ mergedcids.add(tomerge);
+ // insert tomerge in accent order
+ int j = mergedcids.size() - 1;
+ for( ; j > 0; j--) {
+ int tmp = mergedcids.elementAt(j-1);
+ if(tmp > tomerge) {
+ mergedcids.setElementAt(tmp, j);
+ } else {
+ break;
+ }
+ }
+ mergedcids.setElementAt(tomerge, j);
+ }
+ for(int i = 0; i < mergedcids.size(); i++) {
+ this.hashcid = this.hashcid * 31 + mergedcids.elementAt(i);
+ }
+ }
+
public int getExeTime() {
if(this.executionTime == -1) {
try {
return label;
}
- public Object clone(Hashtable<ClassNode, ClassNode> cn2cn, int gid) {
+ public Object clone(Hashtable<ClassNode, ClassNode> cn2cn,
+ int gid) {
ScheduleNode o = null;
try {
o = (ScheduleNode) super.clone();
ScheduleEdge se = null;
switch(temp.getType()) {
case ScheduleEdge.NEWEDGE: {
- se = new ScheduleEdge(o, "new", temp.getFstate(), ScheduleEdge.NEWEDGE, gid);
+ se = new ScheduleEdge(o,
+ "new",
+ temp.getFstate(),
+ ScheduleEdge.NEWEDGE,
+ gid);
se.setProbability(temp.getProbability());
se.setNewRate(temp.getNewRate());
break;
}
case ScheduleEdge.TRANSEDGE: {
- se = new ScheduleEdge(o, "transmit", temp.getFstate(), ScheduleEdge.TRANSEDGE, gid);
+ se = new ScheduleEdge(o,
+ "transmit",
+ temp.getFstate(),
+ ScheduleEdge.TRANSEDGE,
+ gid);
se.setProbability(temp.getProbability());
se.setNewRate(temp.getNewRate());
break;
se.setTargetFState(temp.getTargetFState());
se.setIsclone(true);
tses.add(se);
+ // internal edge, it's source and target have been redirected to ClassNodes
+ se.setTarget(se.getTargetCNode());
+ se.getSourceCNode().addEdge(se);
}
o.classNodes = tcns;
o.scheduleEdges = tses;
}
}
- public void mergeSNode(ScheduleNode sn) throws Exception {
+ public void mergeSNode(ScheduleNode sn) {
Vector<ClassNode> targetCNodes = (Vector<ClassNode>)sn.getClassNodes();
Vector<ScheduleEdge> targetSEdges = (Vector<ScheduleEdge>)sn.getScheduleEdges();
this.executionTime = 0;
}
this.executionTime += sn.getExeTime();
-
+ }
+
+ public ScheduleNode spliteClassNode(ClassNode cd) {
+ ScheduleNode sNode = new ScheduleNode(cd, this.gid);
+
+ this.classNodes.remove(cd);
+ cd.setScheduleNode(sNode);
+ try {
+ sNode.calExeTime();
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+
+ // redirct all corresponding internal ScheduleEdge to the new snode
+ Iterator it_innersEdges = this.scheduleEdges.iterator();
+ Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
+ if(it_innersEdges != null) {
+ while(it_innersEdges.hasNext()) {
+ ScheduleEdge tse = (ScheduleEdge)it_innersEdges.next();
+ if((cd.equals(tse.getSourceCNode())) || (cd.equals(tse.getTargetCNode()))) {
+ // related edge
+ toremove.addElement(tse);
+ }
+ }
+ }
+ this.scheduleEdges.removeAll(toremove);
+ for(int i = 0; i < toremove.size(); i++) {
+ ScheduleEdge tse = toremove.elementAt(i);
+ if(cd.equals(tse.getSourceCNode())) {
+ // outedge
+ tse.setTarget(this);
+ sNode.addEdge(tse);
+ } else if(cd.equals(tse.getTargetCNode())){
+ // inedge
+ tse.setTarget(sNode);
+ this.addEdge(tse);
+ }
+ }
+ toremove.clear();
+ // redirect external ScheudleEdges out of this cd to the new ScheduleNode
+ Iterator it_exsEdges = this.edges();
+ while(it_exsEdges.hasNext()) {
+ ScheduleEdge tse = (ScheduleEdge)it_exsEdges.next();
+ if(tse.getSourceCNode().equals(cd)) {
+ this.removeEdge(tse);
+ sNode.addEdge(tse);
+ }
+ }
+ // redirect inedges whose target is this Classnode to new ScheduleNode
+ Iterator it_insEdges = this.inedges();
+ while(it_insEdges.hasNext()) {
+ ScheduleEdge tse = (ScheduleEdge)it_insEdges.next();
+ if(tse.getTargetCNode().equals(cd)) {
+ toremove.add(tse);
+ tse.setTarget(sNode);
+ }
+ }
+ this.inedges.removeAll(toremove);
+ toremove.clear();
+ toremove = null;
+
+ // As all tasks inside one ScheduleNode are executed sequentially,
+ // simply subtract the execution time of the ClassNode .
+ assert(this.executionTime != -1);
+ this.executionTime -= sNode.getExeTime();
+
+ return sNode;
}
}
private Vector<Schedule> scheduling;
private Vector<CoreSimulator> cores;
private Vector<TaskSimulator> tasks;
- private Vector<CheckPoint> checkpoints;
private int processTime;
private int invoketime;
State state;
TaskAnalysis taskanalysis;
- public ScheduleSimulator(int coreNum, State state, TaskAnalysis taskanalysis) {
- super();
- this.coreNum = coreNum;
+ public ScheduleSimulator(int corenum,
+ State state,
+ TaskAnalysis taskanalysis) {
+ this.coreNum = corenum;
this.scheduling = null;
this.cores = null;
this.tasks = null;
- this.checkpoints = null;
this.processTime = 0;
this.invoketime = 0;
this.state = state;
this.taskanalysis = taskanalysis;
}
- public ScheduleSimulator(int coreNum, Vector<Schedule> scheduling, State state, TaskAnalysis taskanalysis) {
+ public ScheduleSimulator(int corenum,
+ Vector<Schedule> scheduling,
+ State state,
+ TaskAnalysis taskanalysis) {
super();
- this.coreNum = coreNum;
+ this.coreNum = corenum;
this.scheduling = scheduling;
this.cores = new Vector<CoreSimulator>(this.coreNum);
for(int i = 0; i < this.coreNum; i++) {
this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
}
this.tasks = new Vector<TaskSimulator>();
- this.checkpoints = null;
this.processTime = 0;
this.invoketime = 0;
this.state = state;
applyScheduling();
}
- public Vector<Integer> simulate(Vector<Vector<Schedule>> schedulings) {
- // Print stuff to the original output and error streams.
- // The stuff printed through the 'origOut' and 'origErr' references
- // should go to the console on most systems while the messages
- // printed through the 'System.out' and 'System.err' will end up in
- // the files we created for them.
- //origOut.println ("\nRedirect: Round #2");
- //System.out.println ("Test output via 'SimulatorResult.out'.");
- //origOut.println ("Test output via 'origOut' reference.");
-
- // Save the current standard input, output, and error streams
- // for later restoration.
- PrintStream origOut = System.out;
-
- // Create a new output stream for the standard output.
- PrintStream stdout = null;
- try {
- stdout = new PrintStream(new FileOutputStream("/scratch/SimulatorResult.out"));
- } catch (Exception e) {
- // Sigh. Couldn't open the file.
- System.out.println("Redirect: Unable to open output file!");
- System.exit(1);
- }
-
- // Print stuff to the original output and error streams.
- // On most systems all of this will end up on your console when you
- // run this application.
- //origOut.println ("\nRedirect: Round #1");
- //System.out.println ("Test output via 'System.out'.");
- //origOut.println ("Test output via 'origOut' reference.");
-
- // Set the System out and err streams to use our replacements.
- System.setOut(stdout);
-
- Vector<Integer> selectedScheduling = new Vector<Integer>();
+ public int simulate(Vector<Vector<Schedule>> schedulings,
+ Vector<Integer> selectedScheduling,
+ Vector<Vector<SimExecutionEdge>> selectedSimExeGraphs) {
int processTime = Integer.MAX_VALUE;
- if(schedulings.size() > 1500) {
+ /*if(schedulings.size() > 1500) {
int index = 0;
int upperbound = schedulings.size();
long seed = 0;
java.util.Random r = new java.util.Random(seed);
for(int ii = 0; ii < 1500; ii++) {
- index = (int)((Math.abs((double)r.nextInt() / (double)Integer.MAX_VALUE)) * upperbound);
+ index = (int)((Math.abs((double)r.nextInt()
+ /(double)Integer.MAX_VALUE)) * upperbound);
System.out.println("Scheduling index:" + index);
- //System.err.println("Scheduling index:" + index);
Vector<Schedule> scheduling = schedulings.elementAt(index);
this.setScheduling(scheduling);
- int tmpTime = this.process();
+ Vector<SimExecutionEdge> simexegraph = new Vector<SimExecutionEdge>();
+ Vector<CheckPoint> checkpoints = new Vector<CheckPoint>();
+ int tmpTime = this.process(checkpoints, simexegraph);
if(tmpTime < processTime) {
selectedScheduling.clear();
selectedScheduling.add(index);
+ selectedSimExeGraphs.clear();
+ selectedSimExeGraphs.add(simexegraph);
processTime = tmpTime;
} else if(tmpTime == processTime) {
selectedScheduling.add(index);
+ selectedSimExeGraphs.add(simexegraph);
}
scheduling = null;
+ checkpoints = null;
+ simexegraph = null;
}
- } else {
+ } else {*/
Iterator it_scheduling = schedulings.iterator();
int index = 0;
while(it_scheduling.hasNext()) {
- Vector<Schedule> scheduling = (Vector<Schedule>)it_scheduling.next();
+ Vector<Schedule> scheduling =
+ (Vector<Schedule>)it_scheduling.next();
+ System.out.println("Scheduling index:" + scheduling.elementAt(0).getGid());
this.setScheduling(scheduling);
- int tmpTime = this.process();
+ Vector<SimExecutionEdge> simexegraph = new Vector<SimExecutionEdge>();
+ Vector<CheckPoint> checkpoints = new Vector<CheckPoint>();
+ int tmpTime = this.process(checkpoints, simexegraph);
if(tmpTime < processTime) {
selectedScheduling.clear();
selectedScheduling.add(index);
+ selectedSimExeGraphs.clear();
+ selectedSimExeGraphs.add(simexegraph);
processTime = tmpTime;
} else if(tmpTime == processTime) {
selectedScheduling.add(index);
+ selectedSimExeGraphs.add(simexegraph);
}
scheduling = null;
+ checkpoints = null;
index++;
}
- }
-
+ it_scheduling = null;
+ //}
+
System.out.print("Selected schedulings with least exectution time " + processTime + ": \n\t");
for(int i = 0; i < selectedScheduling.size(); i++) {
- System.out.print((selectedScheduling.elementAt(i) + 1) + ", ");
+ int gid = schedulings.elementAt(selectedScheduling.elementAt(i)).elementAt(0).getGid();
+ System.out.print(gid + ", ");
}
System.out.println();
- // Close the streams.
- try {
- stdout.close();
- System.setOut(origOut);
- } catch (Exception e) {
- origOut.println("Redirect: Unable to close files!");
- }
-
- return selectedScheduling;
- }
-
- public Vector<CheckPoint> getCheckpoints() {
- return checkpoints;
+ return processTime;
}
public int getCoreNum() {
- return coreNum;
+ return this.coreNum;
}
- public void setCoreNum(int coreNum) {
- this.coreNum = coreNum;
+ public void setCoreNum(int corenum) {
+ this.coreNum = corenum;
if(this.cores != null) {
this.cores.clear();
}
this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
}
}
- if(this.checkpoints != null) {
- this.checkpoints.clear();
- }
applyScheduling();
}
return tasks;
}
- public int process() {
+ public int process(Vector<CheckPoint> checkpoints,
+ Vector<SimExecutionEdge> simexegraph) {
assert(this.scheduling != null);
this.invoketime++;
-
- if(this.checkpoints == null) {
- this.checkpoints = new Vector<CheckPoint>();
- } /*else {
- this.checkpoints.clear();
- }*/
-
this.processTime = 0;
+
+ // helper structures for building SimExecutionGraph
+ Hashtable<SimExecutionNode, Action> senode2action =
+ new Hashtable<SimExecutionNode, Action>();
+ SimExecutionNode[] lastseNodes = new SimExecutionNode[this.cores.size()];
+ Hashtable<Action, Integer> action2exetime =
+ new Hashtable<Action, Integer>();
+ Hashtable<TransTaskSimulator, SimExecutionNode> tttask2senode =
+ new Hashtable<TransTaskSimulator, SimExecutionNode>();
+ Hashtable<Integer, Integer> obj2transtime =
+ new Hashtable<Integer, Integer>();
+ Hashtable<Integer, SimExecutionEdge> obj2lastseedge =
+ new Hashtable<Integer, SimExecutionEdge>();
// first decide next task to execute on each core
int i = 0;
if(task != null) {
this.tasks.add(task);
}
+ lastseNodes[i] = null;
}
// add STARTTASK checkpoint for all the initial tasks
- CheckPoint cp = new CheckPoint(this.processTime);
+ CheckPoint cp = new CheckPoint(this.processTime,
+ this.coreNum);
for(i = 0; i < this.tasks.size(); i++) {
TaskSimulator task = this.tasks.elementAt(i);
- Action action = new Action(task.getCs().getCoreNum(), Action.TASKSTART);
- action.setTd(task.getTd());
+ int coreid = task.getCs().getCoreNum();
+ Action action = new Action(coreid,
+ Action.TASKSTART,
+ task);
cp.addAction(action);
+ if(!(task instanceof TransTaskSimulator)) {
+ cp.removeSpareCore(coreid);
+ SimExecutionNode seNode = new SimExecutionNode(coreid, this.processTime);
+ seNode.setSpareCores(cp.getSpareCores());
+ senode2action.put(seNode, action);
+ action2exetime.put(action, -1);
+ lastseNodes[coreid] = seNode;
+ }
}
- this.checkpoints.add(cp);
+ checkpoints.add(cp);
while(true) {
// if no more tasks on each core, simulation finish
// for each task in todo queue, decide the execution path of this time
// according to statistic information
- //int index = 0; // indicate the task to finish first
int finishTime = Integer.MAX_VALUE;
Vector<TaskSimulator> finishTasks = new Vector<TaskSimulator>();
for(i = 0; i < this.tasks.size(); i++) {
finishTasks.add(task);
}
}
+
+ // advance to next finish point
+ this.processTime += finishTime;
+ cp = new CheckPoint(this.processTime,
+ this.coreNum);
for(i = 0; i < this.tasks.size(); i++) {
TaskSimulator task = this.tasks.elementAt(i);
if(!finishTasks.contains(task)) {
task.getCs().updateTask(finishTime);
+ if(!(task instanceof TransTaskSimulator)) {
+ cp.removeSpareCore(task.getCs().getCoreNum());
+ }
}
}
- this.processTime += finishTime;
- cp = new CheckPoint(this.processTime);
+
Action action = null;
for(i = 0; i < finishTasks.size(); i++) {
TaskSimulator task = finishTasks.elementAt(i);
this.tasks.removeElement(task);
if(task instanceof TransTaskSimulator) {
- TransTaskSimulator tmptask = (TransTaskSimulator)task;
- // add ADDOBJ task to targetCore
- int targetCoreNum = tmptask.getTargetCoreNum();
- ObjectInfo objinfo = tmptask.refreshTask();
- ObjectSimulator nobj = objinfo.obj;
- FlagState fs = objinfo.fs;
- int version = objinfo.version;
- this.cores.elementAt(targetCoreNum).addObject(nobj, fs, version);
- action = new Action(targetCoreNum, Action.ADDOBJ, 1, nobj.getCd());
- cp.addAction(action);
- if(!tmptask.isFinished()) {
- // still have some objects to be transpotted
- this.tasks.add(task);
+ // handle TransTaskSimulator task's completion
+ finishTransTaskSimulator(task,
+ cp,
+ simexegraph,
+ senode2action,
+ lastseNodes,
+ action2exetime,
+ tttask2senode,
+ obj2transtime);
+ } else {
+ CoreSimulator cs = task.getCs();
+ Vector<TransTaskSimulator> tttasks = new Vector<TransTaskSimulator>();
+
+ Vector<ObjectSimulator> transObjs = null;
+ if(task.getCurrentRun().getExetype() == 0) {
+ // normal execution of a task
+ transObjs = finishTaskNormal(task,
+ cp,
+ tttasks,
+ senode2action,
+ lastseNodes,
+ action2exetime);
+ } else if (task.getCurrentRun().getExetype() == 1) {
+ // task abort
+ finishTaskAbnormal(cs,
+ cp,
+ senode2action,
+ lastseNodes,
+ action2exetime,
+ Action.TASKABORT);
+ } else if (task.getCurrentRun().getExetype() == 2) {
+ // task remove
+ finishTaskAbnormal(cs,
+ cp,
+ senode2action,
+ lastseNodes,
+ action2exetime,
+ Action.TASKREMOVE);
}
- if(this.cores.elementAt(targetCoreNum).getRtask() == null) {
- TaskSimulator newTask = this.cores.elementAt(targetCoreNum).process();
- if(newTask != null) {
+
+ // Choose a new task for this core
+ generateNewTask(cs,
+ cp,
+ transObjs,
+ tttasks,
+ simexegraph,
+ senode2action,
+ lastseNodes,
+ action2exetime,
+ tttask2senode,
+ obj2transtime,
+ obj2lastseedge);
+ tttasks.clear();
+ tttasks = null;
+ transObjs = null;
+ }// end of if(task instanceof TransTaskSimulator) else
+ }
+ checkpoints.add(cp);
+ finishTasks = null;
+ } // end of while(true)
+
+ // add the end node into the SimExecutionGraph
+ SimExecutionNode seNode = new SimExecutionNode(this.coreNum, this.processTime);
+ for(int j = 0; j < lastseNodes.length; j++) {
+ SimExecutionNode lastsenode = lastseNodes[j];
+ // create edges between previous senode on this core to this node
+ if(lastsenode != null) {
+ Action tmpaction = senode2action.get(lastsenode);
+ int weight = tmpaction != null? action2exetime.get(tmpaction) : 0; // TODO ????
+ SimExecutionEdge seEdge = new SimExecutionEdge(seNode,
+ lastsenode.getCoreNum(),
+ tmpaction != null? tmpaction.getTd():null,
+ weight,
+ tmpaction != null? tmpaction.getTaskParams():null);
+ lastsenode.addEdge(seEdge);
+
+ // setup data dependencies for the task
+ Vector<Integer> taskparams = seEdge.getTaskparams();
+ if(taskparams != null) {
+ for(int k = 0; k < taskparams.size(); k++) {
+ Integer tparam = taskparams.elementAt(k);
+ SimExecutionEdge lastedge = obj2lastseedge.get(tparam);
+ if(lastedge != null) {
+ if(lastedge.getCoreNum() != seEdge.getCoreNum()) {
+ // the obj is transferred from another core
+ // create an seEdge for this transfer
+ int transweight = obj2transtime.get(tparam);
+ SimExecutionEdge transseEdge = new SimExecutionEdge((SimExecutionNode)seEdge.getSource(),
+ lastedge.getCoreNum(),
+ null, // TODO: not sure if this is enough
+ transweight,
+ null);
+ if(((SimExecutionNode)seEdge.getSource()).getTimepoint() <
+ ((SimExecutionNode)lastedge.getTarget()).getTimepoint()) {
+ System.err.println("ScheduleSimulator:393");
+ System.exit(-1);
+ }
+ lastedge.getTarget().addEdge(transseEdge);
+ simexegraph.add(transseEdge);
+ transseEdge.addPredicate(lastedge);
+ seEdge.addPredicate(transseEdge);
+ } else {
+ seEdge.addPredicate(lastedge);
+ }
+ }
+ // update the last edge associated to the parameter obj
+ obj2lastseedge.put(tparam, seEdge);
+ }
+ }
+ taskparams = null;
+ simexegraph.add(seEdge); // add the seEdge afger all corresponding transfer edges
+ }
+ lastseNodes[j] = null;
+ }
+
+ senode2action.clear();
+ senode2action = null;
+ lastseNodes = null;
+ action2exetime.clear();
+ action2exetime = null;
+ tttask2senode.clear();
+ tttask2senode = null;
+ obj2transtime.clear();
+ obj2transtime = null;
+ obj2lastseedge.clear();
+ obj2lastseedge = null;
+
+ int gid = this.scheduling.elementAt(0).getGid();
+ if(this.state.PRINTSCHEDULESIM) {
+ SchedulingUtil.printSimulationResult("SimulatorResult_" + gid + ".dot",
+ this.processTime,
+ this.coreNum,
+ checkpoints);
+ }
+ System.out.println("Simulate scheduling #" + gid + ": ");
+ System.out.println("\tTotal execution time is: " + this.processTime);
+ System.out.println("\tUtility of cores: ");
+ for(int j = 0; j < this.cores.size(); j++) {
+ System.out.println("\t\tcore" + j + ": " + getUtility(j) + "%");
+ }
+
+ return this.processTime;
+ }
+
+ private void finishTransTaskSimulator(TaskSimulator task,
+ CheckPoint cp,
+ Vector<SimExecutionEdge> simexegraph,
+ Hashtable<SimExecutionNode, Action> senode2action,
+ SimExecutionNode[] lastseNodes,
+ Hashtable<Action, Integer> action2exetime,
+ Hashtable<TransTaskSimulator, SimExecutionNode> tttask2senode,
+ Hashtable<Integer, Integer> obj2transtime) {
+ TransTaskSimulator tmptask = (TransTaskSimulator)task;
+ // add ADDOBJ task to targetCore
+ int targetCoreNum = tmptask.getTargetCoreNum();
+ ObjectInfo objinfo = tmptask.refreshTask();
+ ObjectSimulator nobj = objinfo.obj;
+ FlagState fs = objinfo.fs;
+ int version = objinfo.version;
+ this.cores.elementAt(targetCoreNum).addObject(nobj, fs, version);
+ Action action = new Action(targetCoreNum, Action.ADDOBJ, 1, nobj.getCd());
+ cp.addAction(action);
+
+ // get the obj transfer time and associated senode
+ SimExecutionNode senode = tttask2senode.get(tmptask);
+ obj2transtime.put(nobj.getOid(), this.processTime - senode.getTimepoint());
+
+ if(!tmptask.isFinished()) {
+ // still have some objects to be transferred
+ this.tasks.add(task);
+ }
+ if(this.cores.elementAt(targetCoreNum).getRtask() == null) {
+ TaskSimulator newTask = this.cores.elementAt(targetCoreNum).process();
+ if(newTask != null) {
this.tasks.add(newTask);
// add a TASKSTART action into this checkpoint
- action = new Action(targetCoreNum, Action.TASKSTART);
- action.setTd(newTask.getTd());
+ action = new Action(targetCoreNum,
+ Action.TASKSTART,
+ newTask);
cp.addAction(action);
- }
+ if(!(newTask instanceof TransTaskSimulator)) {
+ cp.removeSpareCore(targetCoreNum);
+ SimExecutionNode seNode = new SimExecutionNode(targetCoreNum, this.processTime);
+ seNode.setSpareCores(cp.getSpareCores());
+ senode2action.put(seNode, action);
+ action2exetime.put(action, -1);
+
+ SimExecutionNode lastsenode = lastseNodes[targetCoreNum];
+ // create edges between previous senode on this core to this node
+ if(lastsenode != null) {
+ Action tmpaction = senode2action.get(lastsenode);
+ SimExecutionEdge seEdge = null;
+ if(tmpaction == null) {
+ seEdge = new SimExecutionEdge(seNode,
+ lastsenode.getCoreNum(),
+ null,
+ 0,
+ null);
+ } else {
+ int weight = action2exetime.get(tmpaction);
+ seEdge = new SimExecutionEdge(seNode,
+ lastsenode.getCoreNum(),
+ tmpaction.getTd(),
+ weight,
+ tmpaction.getTaskParams());
+ }
+ lastsenode.addEdge(seEdge);
+ simexegraph.add(seEdge);
+ }
+ lastseNodes[targetCoreNum] = seNode;
+ }
}
- } else {
- CoreSimulator cs = task.getCs();
- int coreNum = cs.getCoreNum();
- if(task.getCurrentRun().getExetype() == 0) {
- Hashtable<Integer, Queue<ObjectInfo>> transObjQueues = new Hashtable<Integer, Queue<ObjectInfo>>();
- if(task.getCurrentRun().getNewObjs() == null) {
- action = new Action(coreNum, Action.TASKFINISH);
- action.setTd(cs.getRtask().getTd());
- } else {
- action = new Action(coreNum, Action.TFWITHOBJ);
- action.setTd(cs.getRtask().getTd());
- Vector<ObjectSimulator> nobjs = task.getCurrentRun().getNewObjs();
- for(int j = 0; j < nobjs.size(); j++) {
- ObjectSimulator nobj = nobjs.elementAt(j);
- action.addNewObj(nobj.getCd(), Integer.valueOf(1));
- // send the new object to target core according to pre-decide scheduling
- Queue<Integer> cores = cs.getTargetCores(nobj.getCurrentFS());
- if(cores == null) {
+ }
+ }
+
+ private Vector<ObjectSimulator> finishTaskNormal(TaskSimulator task,
+ CheckPoint cp,
+ Vector<TransTaskSimulator> tttasks,
+ Hashtable<SimExecutionNode, Action> senode2action,
+ SimExecutionNode[] lastseNodes,
+ Hashtable<Action, Integer> action2exetime) {
+ Vector<ObjectSimulator> totransObjs = new Vector<ObjectSimulator>();
+ CoreSimulator cs = task.getCs();
+ int corenum = cs.getCoreNum();
+ Hashtable<Integer, Queue<ObjectInfo>> transObjQueues =
+ new Hashtable<Integer, Queue<ObjectInfo>>();
+ Action action = null;
+ if(task.getCurrentRun().getNewObjs() == null) {
+ // task finish without new objects
+ action = new Action(corenum,
+ Action.TASKFINISH,
+ cs.getRtask());
+ // get the execution time of this task
+ SimExecutionNode lastsenode = lastseNodes[corenum];
+ Action startaction = senode2action.get(lastsenode);
+ action2exetime.put(startaction, cp.getTimepoint() - lastsenode.getTimepoint());
+
+ } else {
+ // task finish with new objects
+ action = new Action(corenum,
+ Action.TFWITHOBJ,
+ cs.getRtask());
+ // get the execution time of this task
+ SimExecutionNode lastsenode = lastseNodes[corenum];
+ Action startaction = senode2action.get(lastsenode);
+ action2exetime.put(startaction, cp.getTimepoint() - lastsenode.getTimepoint());
+
+ // get the infomation of how to send new objects
+ Vector<ObjectSimulator> nobjs = task.getCurrentRun().getNewObjs();
+ for(int j = 0; j < nobjs.size(); j++) {
+ ObjectSimulator nobj = nobjs.elementAt(j);
+ totransObjs.add(nobj);
+
+ action.addNewObj(nobj.getCd(), Integer.valueOf(1));
+ // send the new object to target core according to pre-decide scheduling
+ Queue<Integer> cores = cs.getTargetCores(nobj.getCurrentFS());
+ if(cores == null) {
// this obj will reside on this core
cs.addObject(nobj);
- } else {
+ } else {
Integer targetCore = cores.poll();
- if(targetCore == coreNum) {
- // this obj will reside on this core
- cs.addObject(nobj);
+ if(targetCore == corenum) {
+ // this obj will reside on this core
+ cs.addObject(nobj);
} else {
- if(!transObjQueues.containsKey(targetCore)) {
- transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
- }
- Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
- tmpqueue.add(new ObjectInfo(nobj));
- tmpqueue = null;
+ if(!transObjQueues.containsKey(targetCore)) {
+ transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
+ }
+ Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
+ tmpqueue.add(new ObjectInfo(nobj));
+ tmpqueue = null;
}
// enqueue this core again
cores.add(targetCore);
- }
- cores = null;
- // check if this object becoming shared or not
- Vector<Integer> allycores = cs.getAllyCores(nobj.getCurrentFS());
- if(allycores != null) {
+ }
+ cores = null;
+ // check if this object becoming shared or not
+ Vector<Integer> allycores = cs.getAllyCores(nobj.getCurrentFS());
+ if(allycores != null) {
nobj.setShared(true);
for(int k = 0; k < allycores.size(); ++k) {
- Integer allyCore = allycores.elementAt(k);
- if(allyCore == coreNum) {
- cs.addObject(nobj);
- } else {
- if(!transObjQueues.containsKey(allyCore)) {
- transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
- }
- Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
- ObjectInfo nobjinfo = new ObjectInfo(nobj);
- if(!tmpqueue.contains(nobjinfo)) {
- tmpqueue.add(nobjinfo);
+ Integer allyCore = allycores.elementAt(k);
+ if(allyCore == corenum) {
+ cs.addObject(nobj);
+ } else {
+ if(!transObjQueues.containsKey(allyCore)) {
+ transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
+ }
+ Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
+ ObjectInfo nobjinfo = new ObjectInfo(nobj);
+ if(!tmpqueue.contains(nobjinfo)) {
+ tmpqueue.add(nobjinfo);
+ }
+ tmpqueue = null;
}
- tmpqueue = null;
- }
}
allycores = null;
- }
}
- nobjs = null;
- }
- cp.addAction(action);
- Vector<ObjectSimulator> transObjs = cs.finishTask();
- if(transObjs != null) {
- for(int j = 0; j < transObjs.size(); j++) {
- ObjectSimulator tobj = transObjs.elementAt(j);
- // send the object to target core according to pre-decide scheduling
- Queue<Integer> cores = cs.getTargetCores(tobj.getCurrentFS());
- tobj.setCurrentFS(cs.getTargetFState(tobj.getCurrentFS()));
- if(cores == null) {
+ }
+ nobjs = null;
+ }
+ cp.addAction(action);
+
+ // group the new objects need to transfer
+ Vector<ObjectSimulator> transObjs = cs.finishTask();
+ if(transObjs != null) {
+ totransObjs.addAll(transObjs);
+ for(int j = 0; j < transObjs.size(); j++) {
+ ObjectSimulator tobj = transObjs.elementAt(j);
+ // send the object to target core according to pre-decide scheduling
+ Queue<Integer> cores = cs.getTargetCores(tobj.getCurrentFS());
+ tobj.setCurrentFS(cs.getTargetFState(tobj.getCurrentFS()));
+ if(cores == null) {
// this obj will reside on this core
cs.addObject(tobj);
- } else {
+ } else {
Integer targetCore = cores.poll();
- if(targetCore == coreNum) {
- // this obj will reside on this core
- cs.addObject(tobj);
+ if(targetCore == corenum) {
+ // this obj will reside on this core
+ cs.addObject(tobj);
} else {
- if(!transObjQueues.containsKey(targetCore)) {
- transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
- }
- Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
- tmpqueue.add(new ObjectInfo(tobj));
- tmpqueue = null;
+ if(!transObjQueues.containsKey(targetCore)) {
+ transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
+ }
+ Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
+ tmpqueue.add(new ObjectInfo(tobj));
+ tmpqueue = null;
}
cores.add(targetCore);
- }
- cores = null;
- // check if this object becoming shared or not
- Vector<Integer> allycores = cs.getAllyCores(tobj.getCurrentFS());
- if(allycores != null) {
+ }
+ cores = null;
+ // check if this object becoming shared or not
+ Vector<Integer> allycores = cs.getAllyCores(tobj.getCurrentFS());
+ if(allycores != null) {
tobj.setShared(true);
for(int k = 0; k < allycores.size(); ++k) {
- Integer allyCore = allycores.elementAt(k);
- if(allyCore == coreNum) {
- cs.addObject(tobj);
- } else {
- if(!transObjQueues.containsKey(allyCore)) {
- transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
+ Integer allyCore = allycores.elementAt(k);
+ if(allyCore == corenum) {
+ cs.addObject(tobj);
+ } else {
+ if(!transObjQueues.containsKey(allyCore)) {
+ transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
+ }
+ Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
+ ObjectInfo nobjinfo = new ObjectInfo(tobj);
+ if(!tmpqueue.contains(nobjinfo)) {
+ tmpqueue.add(nobjinfo);
+ }
+ tmpqueue = null;
}
- Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
- ObjectInfo nobjinfo = new ObjectInfo(tobj);
- if(!tmpqueue.contains(nobjinfo)) {
- tmpqueue.add(nobjinfo);
- }
- tmpqueue = null;
- }
}
allycores = null;
- }
}
- transObjs = null;
- }
- // add 'transport' tasks
- Iterator it_entries = transObjQueues.entrySet().iterator();
- while(it_entries.hasNext()) {
- Entry<Integer, Queue<ObjectInfo>> tmpentry = (Entry<Integer, Queue<ObjectInfo>>)it_entries.next();
- Integer tmpCoreNum = tmpentry.getKey();
- Queue<ObjectInfo> nobjs = tmpentry.getValue();
- TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs);
- this.tasks.add(tmptask);
- tmpentry = null;
- nobjs = null;
- }
- transObjQueues = null;
- } else if (task.getCurrentRun().getExetype() == 1) {
- action = new Action(coreNum, Action.TASKABORT);
- action.setTd(cs.getRtask().getTd());
- cp.addAction(action);
- Vector<ObjectSimulator> transObjs = cs.finishTask();
- } else if (task.getCurrentRun().getExetype() == 2) {
- action = new Action(coreNum, Action.TASKREMOVE);
- action.setTd(cs.getRtask().getTd());
- cp.addAction(action);
- Vector<ObjectSimulator> transObjs = cs.finishTask();
}
- // Choose a new task for this core
- TaskSimulator newTask = cs.process();
- if(newTask != null) {
- this.tasks.add(newTask);
- // add a TASKSTART action into this checkpoint
- action = new Action(coreNum, Action.TASKSTART);
- action.setTd(cs.getRtask().getTd());
- cp.addAction(action);
- }
- }
}
- this.checkpoints.add(cp);
- finishTasks = null;
- }
-
- if(this.state.PRINTSCHEDULESIM) {
- SchedulingUtil.printSimulationResult("SimulatorResult_" + this.invoketime + ".dot", this.processTime,
- this.coreNum, this.checkpoints);
- }
- System.out.println("Simulate scheduling #" + this.invoketime + ": ");
- System.out.println("\tTotal execution time is: " + this.processTime);
- System.out.println("\tUtility of cores: ");
- for(int j = 0; j < this.cores.size(); j++) {
- System.out.println("\t\tcore" + j + ": " + getUtility(j) + "%");
- }
-
- this.checkpoints.clear();
- this.checkpoints = null;
- return this.processTime;
+ transObjs = null;
+
+ // add 'transport' tasks
+ Iterator it_entries = transObjQueues.entrySet().iterator();
+ while(it_entries.hasNext()) {
+ Entry<Integer, Queue<ObjectInfo>> tmpentry = (Entry<Integer, Queue<ObjectInfo>>)it_entries.next();
+ Integer tmpCoreNum = tmpentry.getKey();
+ Queue<ObjectInfo> nobjs = tmpentry.getValue();
+ TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs);
+ this.tasks.add(tmptask);
+ tttasks.add(tmptask);
+ tmpentry = null;
+ nobjs = null;
+ }
+ transObjQueues = null;
+
+ return totransObjs;
}
+ private void generateNewTask(CoreSimulator cs,
+ CheckPoint cp,
+ Vector<ObjectSimulator> nobjs,
+ Vector<TransTaskSimulator> tttasks,
+ Vector<SimExecutionEdge> simexegraph,
+ Hashtable<SimExecutionNode, Action> senode2action,
+ SimExecutionNode[] lastseNodes,
+ Hashtable<Action, Integer> action2exetime,
+ Hashtable<TransTaskSimulator, SimExecutionNode> tttask2senode,
+ Hashtable<Integer, Integer> obj2transtime,
+ Hashtable<Integer, SimExecutionEdge> obj2lastseedge) {
+ TaskSimulator newTask = cs.process();
+ int corenum = cs.getCoreNum();
+ SimExecutionEdge seEdge = null;
+ if(newTask != null) {
+ this.tasks.add(newTask);
+ // add a TASKSTART action into this checkpoint
+ Action action = new Action(corenum,
+ Action.TASKSTART,
+ newTask);
+ cp.addAction(action);
+ if(!(newTask instanceof TransTaskSimulator)) {
+ cp.removeSpareCore(cs.getCoreNum());
+ SimExecutionNode seNode = new SimExecutionNode(corenum, this.processTime);
+ seNode.setSpareCores(cp.getSpareCores());
+ senode2action.put(seNode, action);
+ action2exetime.put(action, -1);
+ SimExecutionNode lastsenode = lastseNodes[corenum];
+ // create edges between previous senode on this core to this node
+ if(lastsenode != null) {
+ Action tmpaction = senode2action.get(lastsenode);
+ int weight = tmpaction != null? action2exetime.get(tmpaction):0;
+ seEdge = new SimExecutionEdge(seNode,
+ lastsenode.getCoreNum(),
+ tmpaction!= null?tmpaction.getTd():null,
+ weight,
+ tmpaction!=null?tmpaction.getTaskParams():null);
+ lastsenode.addEdge(seEdge);
+ }
+ lastseNodes[corenum] = seNode;
+ for(int tmpindex = 0; tmpindex < tttasks.size(); tmpindex++) {
+ tttask2senode.put(tttasks.elementAt(tmpindex), seNode);
+ }
+ }
+ } else if(tttasks.size() > 0) {
+ SimExecutionNode seNode = new SimExecutionNode(corenum, this.processTime);
+ seNode.setSpareCores(cp.getSpareCores());
+ // no action associated here
+ SimExecutionNode lastsenode = lastseNodes[corenum];
+ // create edges between previous senode on this core to this node
+ if(lastsenode != null) {
+ Action tmpaction = senode2action.get(lastsenode);
+ int weight = action2exetime.get(tmpaction);
+ seEdge = new SimExecutionEdge(seNode,
+ lastsenode.getCoreNum(),
+ tmpaction.getTd(),
+ weight,
+ tmpaction.getTaskParams());
+ lastsenode.addEdge(seEdge);
+ }
+ lastseNodes[corenum] = seNode;
+ for(int tmpindex = 0; tmpindex < tttasks.size(); tmpindex++) {
+ tttask2senode.put(tttasks.elementAt(tmpindex), seNode);
+ }
+ }
+ if(seEdge != null) {
+ // setup data dependencies for the task
+ Vector<Integer> taskparams = seEdge.getTaskparams();
+ if(taskparams != null) {
+ for(int i = 0; i < taskparams.size(); i++) {
+ Integer tparam = taskparams.elementAt(i);
+ SimExecutionEdge lastedge = obj2lastseedge.get(tparam);
+ if(lastedge != null) {
+ if(lastedge.getCoreNum() != seEdge.getCoreNum()) {
+ // the obj is transferred from another core
+ // create an seEdge for this transfer
+ int weight = obj2transtime.get(tparam);
+ SimExecutionEdge transseEdge = new SimExecutionEdge((SimExecutionNode)seEdge.getSource(),
+ lastedge.getCoreNum(),
+ null, // TODO: not sure if this is enough
+ weight,
+ null);
+ if(((SimExecutionNode)seEdge.getSource()).getTimepoint() <
+ ((SimExecutionNode)lastedge.getTarget()).getTimepoint()) {
+ System.err.println("ScheduleSimulator:757");
+ System.exit(-1);
+ }
+ lastedge.getTarget().addEdge(transseEdge);
+ simexegraph.add(transseEdge);
+ transseEdge.addPredicate(lastedge);
+ seEdge.addPredicate(transseEdge);
+ } else {
+ seEdge.addPredicate(lastedge);
+ }
+ }
+ // update the last edge associated to the parameter obj
+ obj2lastseedge.put(tparam, seEdge);
+ }
+ }
+ taskparams = null;
+ simexegraph.add(seEdge); // add the seEdge afger all corresponding transfer edges
+
+ // set seEdge as the last execution edge for all newly created objs
+ if(nobjs != null) {
+ for(int i = 0; i < nobjs.size(); i++) {
+ ObjectSimulator nobj = nobjs.elementAt(i);
+ obj2lastseedge.put(nobj.getOid(), seEdge);
+ }
+ }
+ }
+ }
+
+ private void finishTaskAbnormal(CoreSimulator cs,
+ CheckPoint cp,
+ Hashtable<SimExecutionNode, Action> senode2action,
+ SimExecutionNode[] lastseNodes,
+ Hashtable<Action, Integer> action2exetime,
+ int type) {
+ Action action = new Action(cs.getCoreNum(),
+ type,
+ cs.getRtask());
+ cp.addAction(action);
+ cs.finishTask();
+
+ // remove the corresponding action on the starting SimExecutionNode
+ SimExecutionNode lastsenode = lastseNodes[cs.getCoreNum()];
+ /*if(lastsenode.getInedgeVector().size() > 0) {
+ //SimExecutionEdge inseedge = (SimExecutionEdge)lastsenode.getinedge(0);
+ //lastseNodes[cs.getCoreNum()] = (SimExecutionNode)inseedge.getSource();
+ } /*else {
+ lastseNodes[cs.getCoreNum()] = null;
+ }*/
+ Action tmpaction = senode2action.remove(lastsenode);
+ action2exetime.remove(tmpaction);
+ }
+
public class CheckPoint {
private int timepoint;
private Vector<Action> actions;
+ private Vector<Integer> spareCores;
- public CheckPoint(int timepoint) {
+ public CheckPoint(int timepoint,
+ int corenum) {
super();
this.timepoint = timepoint;
this.actions = new Vector<Action>();
+ this.spareCores = new Vector<Integer>();
+ for(int i = 0; i < corenum; i++) {
+ this.spareCores.add(i);
+ }
}
public Vector<Action> getActions() {
public void addAction(Action action) {
this.actions.add(action);
}
+
+ public void removeSpareCore(int core) {
+ for(int i = 0 ; i < this.spareCores.size(); i++) {
+ if(this.spareCores.elementAt(i) == core) {
+ for(int j = i; j < this.spareCores.size() - 1; j++) {
+ this.spareCores.setElementAt(this.spareCores.elementAt(j + 1), j);
+ }
+ this.spareCores.remove(this.spareCores.size() - 1);
+ return;
+ }
+ }
+ }
public int getTimepoint() {
return timepoint;
}
+
+ public Vector<Integer> getSpareCores() {
+ return spareCores;
+ }
}
public class Action {
private int coreNum;
private int type;
private TaskDescriptor td;
+ private Vector<Integer> taskparams;
private Hashtable<ClassDescriptor, Integer> nObjs;
private int nObjNum;
private ClassDescriptor transObj;
- public Action(int coreNum, int type) {
- super();
- this.coreNum = coreNum;
+ public Action(int corenum,
+ int type) {
+ this.coreNum = corenum;
this.type = type;
this.td = null;
+ this.taskparams = null;
if(this.type == TFWITHOBJ) {
this.nObjs = new Hashtable<ClassDescriptor, Integer>();
} else {
this.nObjNum = -1;
this.transObj = null;
}
+
+ public Action(int corenum,
+ int type,
+ TaskSimulator ts) {
+ assert(this.type != ADDOBJ);
+
+ this.coreNum = corenum;
+ this.type = type;
+ this.td = ts.getTd();
+ Vector<Queue<ObjectSimulator>> paraQueues = ts.getParaQueues();
+ this.taskparams = new Vector<Integer>();
+ if((this.type != TASKABORT) && (this.type != TASKREMOVE)) {
+ for(int i = 0; i < paraQueues.size(); i++) {
+ ObjectSimulator tpara = paraQueues.elementAt(i).peek();
+ this.taskparams.add(tpara.getOid());
+ }
+ paraQueues = null;
+ }
+ if(this.type == TFWITHOBJ) {
+ this.nObjs = new Hashtable<ClassDescriptor, Integer>();
+ } else {
+ this.nObjs = null;
+ }
+ this.nObjNum = -1;
+ this.transObj = null;
+ }
- public Action(int coreNum, int type, int objNum, ClassDescriptor transObj) {
- super();
+ public Action(int corenum,
+ int type,
+ int objNum,
+ ClassDescriptor transObj) {
assert(type == ADDOBJ);
- this.coreNum = coreNum;
+ this.coreNum = corenum;
this.type = type;
this.td = null;
+ this.taskparams = null;
this.nObjNum = objNum;
this.transObj = transObj;
}
- public void addNewObj(ClassDescriptor cd, Integer num) {
+ public void addNewObj(ClassDescriptor cd,
+ Integer num) {
assert(this.type == TFWITHOBJ);
if(this.nObjs.containsKey(cd)) {
}
public int getCoreNum() {
- return coreNum;
+ return this.coreNum;
}
public int getType() {
public TaskDescriptor getTd() {
return td;
}
-
- public void setTd(TaskDescriptor td) {
- this.td = td;
+
+ public Vector<Integer> getTaskParams() {
+ return this.taskparams;
}
public Hashtable<ClassDescriptor, Integer> getNObjs() {
import Analysis.TaskStateAnalysis.FEdge.NewObjInfo;
import IR.ClassDescriptor;
import IR.Operation;
+import IR.State;
import IR.Tree.FlagExpressionNode;
import IR.Tree.FlagNode;
import IR.Tree.FlagOpNode;
import Util.Namer;
public class SchedulingUtil {
+
+ public static Vector<ScheduleNode> generateScheduleGraph(State state,
+ Vector<ScheduleNode> scheduleNodes,
+ Vector<ScheduleEdge> scheduleEdges,
+ Vector<Vector<ScheduleNode>> rootnodes,
+ Vector<Vector<CombinationUtil.Combine>> combine,
+ int gid) {
+ Vector<ScheduleNode> result = new Vector<ScheduleNode>();
+
+ // clone the ScheduleNodes
+ Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash =
+ new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
+ Hashtable<ScheduleNode, ScheduleNode> sn2sn =
+ new Hashtable<ScheduleNode, ScheduleNode>();
+ cloneScheduleGraph(scheduleNodes,
+ scheduleEdges,
+ sn2hash,
+ sn2sn,
+ result,
+ gid);
+
+ // combine those nodes in combine with corresponding rootnodes
+ for(int i = 0; i < combine.size(); i++) {
+ if(combine.elementAt(i) != null) {
+ for(int j = 0; j < combine.elementAt(i).size(); j++) {
+ CombinationUtil.Combine tmpcombine = combine.elementAt(i).elementAt(j);
+ ScheduleNode tocombine = sn2sn.get(tmpcombine.node);
+ ScheduleNode root = sn2sn.get(rootnodes.elementAt(tmpcombine.root).elementAt(tmpcombine.index));
+ ScheduleEdge se = (ScheduleEdge)tocombine.inedges().next();
+ try {
+ if(root.equals(((ScheduleNode)se.getSource()))) {
+ root.mergeSEdge(se);
+ if(ScheduleEdge.NEWEDGE == se.getType()) {
+ // As se has been changed into an internal edge inside a ScheduleNode,
+ // change the source and target of se from original ScheduleNodes into ClassNodes.
+ se.setTarget(se.getTargetCNode());
+ //se.setSource(se.getSourceCNode());
+ //se.getTargetCNode().addEdge(se);
+ se.getSourceCNode().addEdge(se);
+ }
+ } else {
+ root.mergeSNode(tocombine);
+ }
+ } catch(Exception e) {
+ e.printStackTrace();
+ System.exit(-1);
+ }
+ result.removeElement(tocombine);
+ }
+ }
+ }
+
+ assignCids(result);
+
+ sn2hash.clear();
+ sn2hash = null;
+ sn2sn.clear();
+ sn2sn = null;
+
+ if(state.PRINTSCHEDULING) {
+ String path = "scheduling_" + gid + ".dot";
+ SchedulingUtil.printScheduleGraph(path, result);
+ }
+
+ return result;
+ }
+
+ public static void cloneScheduleGraph(Vector<ScheduleNode> scheduleNodes,
+ Vector<ScheduleEdge> scheduleEdges,
+ Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash,
+ Hashtable<ScheduleNode, ScheduleNode> sn2sn,
+ Vector<ScheduleNode> result,
+ int gid) {
+ for(int i = 0; i < scheduleNodes.size(); i++) {
+ Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
+ ScheduleNode tocopy = scheduleNodes.elementAt(i);
+ ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
+ result.add(i, temp);
+ sn2hash.put(temp, cn2cn);
+ sn2sn.put(tocopy, temp);
+ cn2cn = null;
+ }
+ // clone the ScheduleEdges
+ for(int i = 0; i < scheduleEdges.size(); i++) {
+ ScheduleEdge sse = scheduleEdges.elementAt(i);
+ ScheduleNode csource = sn2sn.get(sse.getSource());
+ ScheduleNode ctarget = sn2sn.get(sse.getTarget());
+ Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
+ Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
+ ScheduleEdge se = null;
+ switch(sse.getType()) {
+ case ScheduleEdge.NEWEDGE: {
+ se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid); //new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
+ se.setProbability(sse.getProbability());
+ se.setNewRate(sse.getNewRate());
+ break;
+ }
+
+ case ScheduleEdge.TRANSEDGE: {
+ se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid); //new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
+ break;
+ }
+ }
+ se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
+ se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
+ se.setFEdge(sse.getFEdge());
+ se.setTargetFState(sse.getTargetFState());
+ se.setIsclone(true);
+ csource.addEdge(se);
+ sourcecn2cn = null;
+ targetcn2cn = null;
+ }
+ }
+
+ public static void assignCids(Vector<ScheduleNode> result) {
+ Hashtable<Integer, Integer> hcid2cid = new Hashtable<Integer, Integer>();
+ int ncid = 0;
+ for(int i = 0; i < result.size(); i++) {
+ ScheduleNode tmpnode = result.elementAt(i);
+ tmpnode.computeHashcid();
+ int hcid = tmpnode.getHashcid();
+ if(hcid2cid.containsKey(hcid)) {
+ // already have a cid for this node
+ tmpnode.setCid(hcid2cid.get(hcid));
+ } else {
+ // generate a new cid for such node
+ tmpnode.setCid(ncid);
+ hcid2cid.put(hcid, ncid);
+ ncid++;
+ }
+ }
+ hcid2cid.clear();
+ hcid2cid = null;
+ }
+
+ // Organize the scheduleNodes in order of their cid
+ public static Vector<Vector<ScheduleNode>> rangeScheduleNodes(Vector<ScheduleNode> scheduleNodes) {
+ Vector<Vector<ScheduleNode>> sNodeVecs = new Vector<Vector<ScheduleNode>>();
+
+ for(int i = 0; i < scheduleNodes.size(); i++) {
+ ScheduleNode tmpn = scheduleNodes.elementAt(i);
+ int index = tmpn.getCid();
+ while(sNodeVecs.size() <= index) {
+ sNodeVecs.add(null);
+ }
+ if(sNodeVecs.elementAt(index) == null) {
+ sNodeVecs.setElementAt(new Vector<ScheduleNode>(), index);
+ }
+ sNodeVecs.elementAt(index).add(tmpn);
+ }
+
+ return sNodeVecs;
+ }
/*public static int maxDivisor(int l, int r) {
int a = l;
}
}*/
- public static boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
+ public static boolean isTaskTrigger_flag(FlagExpressionNode fen,
+ FlagState fs) {
if (fen==null)
return true;
else if (fen instanceof FlagNode)
}
}
- public static void printScheduleGraph(String path, Vector<ScheduleNode> sNodes) {
+ public static void printScheduleGraph(String path,
+ Vector<ScheduleNode> sNodes) {
try {
File file=new File(path);
FileOutputStream dotstream=new FileOutputStream(file,false);
}
}
- private static void traverseSNodes(PrintWriter output, Vector<ScheduleNode> sNodes) {
+ private static void traverseSNodes(PrintWriter output,
+ Vector<ScheduleNode> sNodes) {
//Draw clusters representing ScheduleNodes
Iterator it = sNodes.iterator();
while (it.hasNext()) {
}
}
- private static void traverseCNodes(PrintWriter output, Iterator it) {
+ private static void traverseCNodes(PrintWriter output,
+ Iterator it) {
//Draw clusters representing ClassNodes
while (it.hasNext()) {
ClassNode gn = (ClassNode) it.next();
}
}
- private static void traverseFlagStates(PrintWriter output, Collection nodes) {
+ private static void traverseFlagStates(PrintWriter output,
+ Collection nodes) {
Set cycleset=GraphNode.findcycles(nodes);
Vector namers=new Vector();
namers.add(new Namer());
}
}
- private static Set nonmerge(GraphNode gn, Collection nodes) {
+ private static Set nonmerge(GraphNode gn,
+ Collection nodes) {
HashSet newset=new HashSet();
HashSet toprocess=new HashSet();
toprocess.add(gn);
return newset;
}
- public static void printSimulationResult(String path, int time, int coreNum, Vector<CheckPoint> checkpoints) {
+ public static void printSimulationResult(String path,
+ int time,
+ int coreNum,
+ Vector<CheckPoint> checkpoints) {
try {
File file=new File(path);
FileOutputStream dotstream=new FileOutputStream(file,false);
for(int i = 0; i < actions.size(); i++) {
Action taction = actions.elementAt(i);
int cNum = taction.getCoreNum();
- if(!tmplastTasks.contains(cNum)) {
+ if(!tmplastTasks.containsKey(cNum)) {
tmplastTasks.put(cNum, lastTasks[cNum]);
}
- if(!(tmpisset.contains(cNum)) && (isTaskFinish[cNum]) && !(tmpisTaskFinish.contains(cNum))) {
- tmpisTaskFinish.add(cNum); // records those with task finished the first time visit it
+ if(!(tmpisset.contains(cNum))
+ && (isTaskFinish[cNum])
+ && !(tmpisTaskFinish.contains(cNum))) {
+ tmpisTaskFinish.add(cNum); // records those with task finished the first time visit it
}
String tmpTaskNode = "\"" + tnode + "core" + cNum + "\"";
StringBuffer tmpLabel = null;
if(!isfirst) {
tmpLabel.append("\\n");
}
- tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes;");
+ tmpLabel.append("<" + taction.getTd().getSymbol() + "(");
+ /*Vector<Integer> taskparams = taction.getTaskParams();
+ for(int ii = 0; ii < taskparams.size(); ii++) {
+ tmpLabel.append(taskparams.elementAt(ii));
+ if(ii < taskparams.size() - 1) {
+ tmpLabel.append(",");
+ }
+ }*/
+ tmpLabel.append(")>finishes;");
if(!(lastTaskNodes[cNum].equals("first"))) {
if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
output.print("\t");
if(!isfirst) {
tmpLabel.append("\\n");
}
- tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes; ");
+ tmpLabel.append("<" + taction.getTd().getSymbol() + "(");
+ /*Vector<Integer> taskparams = taction.getTaskParams();
+ for(int ii = 0; ii < taskparams.size(); ii++) {
+ tmpLabel.append(taskparams.elementAt(ii));
+ if(ii < taskparams.size() - 1) {
+ tmpLabel.append(",");
+ }
+ }*/
+ tmpLabel.append(")>finishes;");
Iterator<Entry<ClassDescriptor, Integer>> it_entry = (Iterator<Entry<ClassDescriptor, Integer>>)taction.getNObjs().entrySet().iterator();
while(it_entry.hasNext()) {
Entry<ClassDescriptor, Integer> entry = it_entry.next();
if(!isfirst) {
tmpLabel.append("\\n");
}
- tmpLabel.append("<" + taction.getTd().getSymbol() + ">starts;");
+ tmpLabel.append("<" + taction.getTd().getSymbol() + "(");
+ /*Vector<Integer> taskparams = taction.getTaskParams();
+ for(int ii = 0; ii < taskparams.size(); ii++) {
+ tmpLabel.append(taskparams.elementAt(ii));
+ if(ii < taskparams.size() - 1) {
+ tmpLabel.append(",");
+ }
+ }*/
+ tmpLabel.append(")>starts;");
lastTasks[cNum] = taction.getTd().getSymbol();
if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
if(!isfirst) {
tmpLabel.append("\\n");
}
- tmpLabel.append("<" + taction.getTd().getSymbol() + ">aborts;");
+ tmpLabel.append("<" + taction.getTd().getSymbol() + "(");
+ /*Vector<Integer> taskparams = taction.getTaskParams();
+ for(int ii = 0; ii < taskparams.size(); ii++) {
+ tmpLabel.append(taskparams.elementAt(ii));
+ if(ii < taskparams.size() - 1) {
+ tmpLabel.append(",");
+ }
+ }*/
+ tmpLabel.append(")>aborts;");
if(!(lastTaskNodes[cNum].equals("first")) &&
(tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) {
if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
if(!isfirst) {
tmpLabel.append("\\n");
}
- tmpLabel.append("<" + taction.getTd().getSymbol() + ">removes;");
+ tmpLabel.append("<" + taction.getTd().getSymbol() + "(");
+ /*Vector<Integer> taskparams = taction.getTaskParams();
+ for(int ii = 0; ii < taskparams.size(); ii++) {
+ tmpLabel.append(taskparams.elementAt(ii));
+ if(ii < taskparams.size() - 1) {
+ tmpLabel.append(",");
+ }
+ }*/
+ tmpLabel.append(")>removes;");
if(!(lastTaskNodes[cNum].equals("first")) &&
(tmplastTasks.get(cNum).equals(taction.getTd().getSymbol()))) {
if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
System.exit(-1);
}
}
+
+ public static void printCriticalPath(String path,
+ Vector<SimExecutionEdge> criticalPath) {
+ try {
+ File file=new File(path);
+ FileOutputStream dotstream=new FileOutputStream(file,false);
+ PrintWriter output = new java.io.PrintWriter(dotstream, true);
+ output.println("digraph simulation{");
+ output.print("\t");
+ output.println("node [shape=plaintext];");
+ output.print("\t");
+ output.println("edge [dir=none];");
+ output.print("\t");
+ output.println("ranksep=.05;");
+ output.println();
+ output.print("\t");
+ Vector<SimExecutionNode> nodes = new Vector<SimExecutionNode>();
+ String label = "";
+ String dotnodeparams="";
+
+ for(int i = 0; i < criticalPath.size(); i++) {
+ SimExecutionEdge seedge = criticalPath.elementAt(i);
+ SimExecutionNode startnode = (SimExecutionNode)seedge.getSource();
+ SimExecutionNode endnode = (SimExecutionNode)seedge.getTarget();
+ if(!nodes.contains(startnode)) {
+ label = startnode.getCoreNum() + ":" + startnode.getTimepoint();
+ output.println("\t" + startnode.getLabel() + " [label=\""
+ + label + "\" ];");
+ }
+ if(!nodes.contains(endnode)) {
+ label = endnode.getCoreNum() + ":" + endnode.getTimepoint();
+ output.println("\t" + endnode.getLabel() + " [label=\""
+ + label + "\" ];");
+ }
+ output.println("\t" + startnode.getLabel() + " -> " + endnode.getLabel()
+ + " [" + "label=\"" + seedge.getLabel() + "\"];");
+ }
+ output.println("}");
+ output.close();
+ } catch (Exception e) {
+ e.printStackTrace();
+ System.exit(-1);
+ }
+ }
}
\ No newline at end of file
--- /dev/null
+package Analysis.Scheduling;
+
+import java.util.Vector;
+
+import IR.TaskDescriptor;
+import Util.Edge;
+
+public class SimExecutionEdge extends Edge {
+
+ private int eid;
+ private static int nodeID=0;
+
+ private int coreNum;
+ private TaskDescriptor td;
+ private Vector<Integer> taskparams;
+ private int weight;
+
+ private int bestStartPoint;
+ private SimExecutionNode lastpredicatenode;
+ private SimExecutionEdge lastpredicateedge;
+ private Vector<SimExecutionEdge> predicates;
+ private boolean isFixedTime;
+
+ public SimExecutionEdge(SimExecutionNode target,
+ int corenum,
+ TaskDescriptor td,
+ int weight,
+ Vector<Integer> taskparams) {
+ super(target);
+ this.eid = SimExecutionEdge.nodeID++;
+ this.coreNum = corenum;
+ this.td = td;
+ this.taskparams = taskparams;
+ this.weight = weight;
+ this.bestStartPoint = -1;
+ this.lastpredicatenode = null;
+ this.lastpredicateedge = null;
+ this.predicates = new Vector<SimExecutionEdge>();
+ this.isFixedTime = true;
+ }
+
+ public int getBestStartPoint() {
+ if(this.bestStartPoint == -1) {
+ if(this.predicates.size() > 0) {
+ // have predicates
+ int starttime = 0;
+ // check the latest finish time of all the predicates
+ for(int j = 0; j < this.predicates.size(); j++) {
+ SimExecutionEdge predicate = this.predicates.elementAt(j);
+ int tmptime = predicate.getBestStartPoint() + predicate.getWeight();
+ if(tmptime > starttime) {
+ starttime = tmptime;
+ this.lastpredicateedge = predicate;
+ if(predicate.getTd() != null) {
+ this.lastpredicatenode = (SimExecutionNode)predicate.getTarget();
+ } else {
+ // transfer edge
+ this.lastpredicatenode = (SimExecutionNode)predicate.getSource();
+ }
+ }
+ }
+ this.bestStartPoint = starttime;
+ } else {
+ // no predicates
+ this.bestStartPoint = 0;
+ }
+ }
+ return bestStartPoint;
+ }
+
+ public void setBestStartPoint(int bestStartPoint) {
+ this.bestStartPoint = bestStartPoint;
+ }
+
+ public Vector<SimExecutionEdge> getPredicates() {
+ return predicates;
+ }
+
+ public void addPredicate(SimExecutionEdge predicate) {
+ if(!this.predicates.contains(predicate)) {
+ this.predicates.add(predicate);
+ }
+ }
+
+ public Vector<Integer> getTaskparams() {
+ return taskparams;
+ }
+
+ public TaskDescriptor getTd() {
+ return td;
+ }
+
+ public int getWeight() {
+ return weight;
+ }
+
+ public void setWeight(int weight) {
+ this.weight = weight;
+ }
+
+ public int getCoreNum() {
+ return coreNum;
+ }
+
+ public SimExecutionNode getLastpredicateNode() {
+ return lastpredicatenode;
+ }
+
+ public void setLastpredicateNode(SimExecutionNode lastpredicatenode) {
+ this.lastpredicatenode = lastpredicatenode;
+ }
+
+ public SimExecutionEdge getLastpredicateEdge() {
+ return lastpredicateedge;
+ }
+
+ public void setLastpredicateEdge(SimExecutionEdge lastpredicateedge) {
+ this.lastpredicateedge = lastpredicateedge;
+ }
+
+ public boolean isFixedTime() {
+ return isFixedTime;
+ }
+
+ public void setFixedTime(boolean isFixedTime) {
+ this.isFixedTime = isFixedTime;
+ }
+
+ public String getLabel() {
+ String completeLabel = (this.td != null? this.td.getSymbol():"")
+ + "(" + this.weight + " | " + this.bestStartPoint + ")";
+ return completeLabel;
+ }
+}
--- /dev/null
+package Analysis.Scheduling;
+
+import java.util.Vector;
+
+import Util.GraphNode;
+
+public class SimExecutionNode extends GraphNode {
+
+ private int nid;
+ private static int nodeID=0;
+
+ private int coreNum;
+ private int timepoint;
+ public Vector<Integer> spareCores;
+
+ public SimExecutionNode(int corenum,
+ int timepoint) {
+ this.nid = SimExecutionNode.nodeID++;
+ this.coreNum = corenum;
+ this.timepoint = timepoint;
+ this.spareCores = null;
+ }
+
+ public int getNid() {
+ return nid;
+ }
+
+ public int getTimepoint() {
+ return timepoint;
+ }
+
+ public int getCoreNum() {
+ return coreNum;
+ }
+
+ public Vector<Integer> getSpareCores() {
+ return spareCores;
+ }
+
+ public void setSpareCores(Vector<Integer> spareCores) {
+ this.spareCores = spareCores;
+ }
+
+ public String getLabel() {
+ return "N" + this.nid;
+ }
+}
}
}
- public TaskSimulator(TaskDescriptor td, CoreSimulator cs) {
+ public TaskSimulator(TaskDescriptor td,
+ CoreSimulator cs) {
super();
this.td = td;
this.paraQueues = null;
return this.objVersionTbl.get(os).intValue();
}
- public void enquePara(ObjectSimulator obj, FlagState fs, int version, boolean inherent) {
+ public void enquePara(ObjectSimulator obj,
+ FlagState fs,
+ int version,
+ boolean inherent) {
ClassDescriptor cd = obj.getCd();
int paraNum = td.numParameters();
for(int i = 0; i < paraNum; i++) {
}
}
- public void refreshPara(ObjectSimulator obj, boolean remove) {
+ public void refreshPara(ObjectSimulator obj,
+ boolean remove) {
ClassDescriptor cd = obj.getCd();
int paraNum = td.numParameters();
for(int i = 0; i < paraNum; i++) {
FlagState tfstate = tpara.getCurrentFS();
FEdge toexecute = tfstate.process(td);
finishTime += toexecute.getExeTime();
- if((toexecute.getNewObjInfoHashtable() != null) && (toexecute.getNewObjInfoHashtable().size() > 0)) {
+ if((toexecute.getNewObjInfoHashtable() != null)
+ && (toexecute.getNewObjInfoHashtable().size() > 0)) {
// have new objects
Iterator it = toexecute.getNewObjInfoHashtable().keySet().iterator();
int invokeNum = toexecute.getInvokeNum();
private int targetCoreNum;
private Queue<ObjectInfo> newObjs;
- public TransTaskSimulator(CoreSimulator cs, int targetCoreNum, Queue<ObjectInfo> nobjs) {
+ public TransTaskSimulator(CoreSimulator cs,
+ int targetCoreNum,
+ Queue<ObjectInfo> nobjs) {
super(null, cs);
this.targetCoreNum = targetCoreNum;
this.newObjs = nobjs;
public int getTargetCoreNum() {
return targetCoreNum;
}
+
+ public Queue<ObjectInfo> getNewObjs() {
+ return newObjs;
+ }
+
}
\ No newline at end of file
projects / IRC.git / commitdiff