--- /dev/null
+package Analysis.Scheduling;
+
+import java.util.Hashtable;
+import java.util.Queue;
+import java.util.Vector;
+
+import Analysis.TaskStateAnalysis.FlagState;
+import IR.ClassDescriptor;
+import IR.TaskDescriptor;
+
+public class CoreSimulator {
+ Vector<TaskSimulator> tasks;
+ RuntimeSchedule rSchedule;
+ TaskSimulator rtask;
+ Hashtable<FlagState, Queue<Integer>> targetCSimulator;
+ Hashtable<FlagState, FlagState> targetFState;
+ int coreNum;
+ int activeTime;
+
+ public CoreSimulator(RuntimeSchedule schedule, int coreNum) {
+ super();
+ reset();
+ this.rSchedule = schedule;
+ this.coreNum = coreNum;
+ }
+
+ public CoreSimulator(int coreNum) {
+ super();
+ reset();
+ this.coreNum = coreNum;
+ }
+
+ public void reset() {
+ this.activeTime = 0;
+ this.tasks = null;
+ this.targetCSimulator = null;
+ this.targetFState = null;
+ this.rSchedule = null;
+ this.rtask = null;
+ }
+
+ public void deployTasks(Vector<TaskDescriptor> tasks) {
+ if(tasks == null) {
+ return;
+ }
+
+ if(this.tasks == null) {
+ this.tasks = new Vector<TaskSimulator>();
+ } else {
+ this.tasks.clear();
+ }
+
+ for(int i = 0; i < tasks.size(); i++) {
+ TaskDescriptor td = tasks.elementAt(i);
+ this.tasks.add(new TaskSimulator(td, this));
+ }
+ }
+
+ public Queue<Integer> getTargetCores(FlagState fstate) {
+ if(targetCSimulator == null) {
+ return null;
+ }
+ return targetCSimulator.get(fstate);
+ }
+
+ public void setTargetCSimulator(
+ Hashtable<FlagState, Queue<Integer>> targetCSimulator) {
+ this.targetCSimulator = targetCSimulator;
+ }
+
+ public FlagState getTargetFState(FlagState fstate) {
+ if(targetFState == null) {
+ return null;
+ }
+ return targetFState.get(fstate);
+ }
+
+ public void setTargetFState(Hashtable<FlagState, FlagState> targetFState) {
+ this.targetFState = targetFState;
+ }
+
+ public int getActiveTime() {
+ return activeTime;
+ }
+
+ public int getCoreNum() {
+ return coreNum;
+ }
+
+ public Vector<TaskSimulator> getTasks() {
+ return tasks;
+ }
+
+ public RuntimeSchedule getRSchedule() {
+ return rSchedule;
+ }
+
+ public void setRSchedule(RuntimeSchedule schedule) {
+ rSchedule = schedule;
+ }
+
+ public TaskSimulator getRtask() {
+ return rtask;
+ }
+
+ public void addObject(ObjectSimulator newObj) {
+ if(this.tasks == null) {
+ return;
+ }
+ for(int i = 0; i < this.tasks.size(); i++) {
+ this.tasks.elementAt(i).enquePara(newObj);
+ }
+ }
+
+ public Vector<ObjectSimulator> finishTask() {
+ assert(this.rtask != null);
+
+ Vector<ObjectSimulator> transObjs = null;
+ Vector<Queue<ObjectSimulator>> paraQueues = this.rtask.getParaQueues();
+ for(int i = 0; i < paraQueues.size(); i++) {
+ ObjectSimulator obj = paraQueues.elementAt(i).poll();
+ boolean remove = false;
+ if((this.targetFState != null) && (this.targetFState.containsKey(obj.getCurrentFS()))) {
+ if(transObjs == null) {
+ transObjs = new Vector<ObjectSimulator>();
+ }
+ transObjs.add(obj);
+ remove = true;
+ }
+ for(int j = 0; j < this.tasks.size(); j++) {
+ this.tasks.elementAt(j).refreshPara(obj, remove);
+ }
+ }
+ this.activeTime += this.rtask.getCurrentRun().getFinishTime();
+ this.rtask.finish();
+ this.rtask = null;
+ return transObjs;
+ }
+
+ public void updateTask(int time) {
+ this.activeTime += time;
+ this.rtask.updateFinishTime(time);
+ }
+
+ public TaskSimulator process() {
+ TaskSimulator next = rSchedule.schedule(tasks);
+ this.rtask = next;
+ return next;
+ }
+
+}
\ No newline at end of file
--- /dev/null
+package Analysis.Scheduling;
+
+import java.util.Queue;
+import java.util.Vector;
+
+public class FIFORSchedule extends RuntimeSchedule {
+ static FIFORSchedule rschedule;
+
+ public static FIFORSchedule getFIFORSchedule() {
+ if(rschedule == null) {
+ rschedule = new FIFORSchedule();
+ }
+ return rschedule;
+ }
+
+ public FIFORSchedule() {
+ super("FIFO Algorithm");
+ }
+
+ public TaskSimulator schedule(Vector<TaskSimulator> tasks) {
+ if(tasks == null) {
+ return null;
+ }
+ TaskSimulator next = null;
+ int i = 0;
+ for(; i < tasks.size(); i++) {
+ next = tasks.elementAt(i);
+ int paraNum = next.getTd().numParameters();
+ Vector<Queue<ObjectSimulator>> pqueues = next.getParaQueues();
+ if((pqueues == null) || (pqueues.size() < paraNum)) {
+ continue;
+ }
+ int j = 0;
+ for(; j < pqueues.size(); j++) {
+ Queue<ObjectSimulator> objs = pqueues.elementAt(j);
+ if((objs == null) || (objs.size() == 0)) {
+ break;
+ }
+ }
+ if(j == pqueues.size()) {
+ return next;
+ }
+ }
+ if(i == tasks.size()) {
+ return null;
+ }
+ return next;
+ }
+}
\ No newline at end of file
--- /dev/null
+package Analysis.Scheduling;
+
+import Analysis.TaskStateAnalysis.FEdge;
+import Analysis.TaskStateAnalysis.FlagState;
+import IR.ClassDescriptor;
+
+public class ObjectSimulator {
+ ClassDescriptor cd;
+ FlagState currentFS;
+ boolean changed;
+
+ public ObjectSimulator(ClassDescriptor cd, FlagState currentFS) {
+ super();
+ this.cd = cd;
+ this.currentFS = currentFS;
+ this.changed = true;
+ }
+
+ public void applyEdge(FEdge fedge) {
+ if(!currentFS.equals((FlagState)fedge.getTarget())) {
+ this.changed = true;
+ currentFS = (FlagState)fedge.getTarget();
+ } else {
+ this.changed = false;
+ }
+ }
+
+ public ClassDescriptor getCd() {
+ return cd;
+ }
+
+ public FlagState getCurrentFS() {
+ return currentFS;
+ }
+
+ public boolean isChanged() {
+ return changed;
+ }
+
+ public void setCurrentFS(FlagState currentFS) {
+ /*if(!this.currentFS.equals(currentFS)) {
+ changed = true;
+ this.currentFS = currentFS;
+ } else {
+ changed = false;
+ }*/
+ changed = true;
+ this.currentFS = currentFS;
+ }
+
+}
\ No newline at end of file
--- /dev/null
+package Analysis.Scheduling;
+
+import java.util.Vector;
+import java.lang.String;
+
+public abstract class RuntimeSchedule {
+ String rsAlgorithm;
+
+ public RuntimeSchedule(String rsAlgorithm) {
+ super();
+ this.rsAlgorithm = rsAlgorithm;
+ }
+
+ public abstract TaskSimulator schedule(Vector<TaskSimulator> tasks);
+
+ public String algorithm() {
+ return rsAlgorithm;
+ }
+}
\ No newline at end of file
--- /dev/null
+package Analysis.Scheduling;
+
+import java.util.Hashtable;
+import java.util.LinkedList;
+import java.util.Queue;
+import java.util.Vector;
+
+import Analysis.TaskStateAnalysis.FlagState;
+import IR.TaskDescriptor;
+
+/** This class holds flag transition diagram(s) can be put on one core.
+ */
+public class Schedule {
+ private int coreNum;
+ private Vector<TaskDescriptor> tasks;
+ private Hashtable<FlagState, Queue<Integer>> targetCores;
+ private Hashtable<FlagState, FlagState> targetFState;
+
+ public Schedule(int coreNum) {
+ super();
+ this.coreNum = coreNum;
+ this.tasks = null;
+ this.targetCores = null;
+ this.targetFState = null;
+ }
+
+ public int getCoreNum() {
+ return coreNum;
+ }
+
+ public Hashtable<FlagState, Queue<Integer>> getTargetCoreTable() {
+ return targetCores;
+ }
+
+ public Queue<Integer> getTargetCores(FlagState fstate) {
+ if(targetCores == null) {
+ return null;
+ }
+ return targetCores.get(fstate);
+ }
+
+ public Hashtable<FlagState, FlagState> getTargetFStateTable() {
+ return targetFState;
+ }
+
+ public FlagState getTargetFState(FlagState fstate) {
+ if(targetFState == null) {
+ return null;
+ }
+ return targetFState.get(fstate);
+ }
+
+ public void addTargetCore(FlagState fstate, Integer targetCore/*, Integer num*/) {
+ if(this.targetCores == null) {
+ this.targetCores = new Hashtable<FlagState, Queue<Integer>>();
+ }
+ if(!this.targetCores.containsKey(fstate)) {
+ this.targetCores.put(fstate, new LinkedList<Integer>());
+ }
+ this.targetCores.get(fstate).add(targetCore);
+ }
+
+ public void addTargetCore(FlagState fstate, Integer targetCore, FlagState tfstate) {
+ if(this.targetCores == null) {
+ this.targetCores = new Hashtable<FlagState, Queue<Integer>>();
+ }
+ if(!this.targetCores.containsKey(fstate)) {
+ this.targetCores.put(fstate, new LinkedList<Integer>());
+ }
+ this.targetCores.get(fstate).add(targetCore);
+ if(this.targetFState == null) {
+ this.targetFState = new Hashtable<FlagState, FlagState>();
+ }
+ this.targetFState.put(fstate, tfstate);
+ }
+
+ public Vector<TaskDescriptor> getTasks() {
+ return tasks;
+ }
+
+ public void addTask(TaskDescriptor task) {
+ if(this.tasks == null) {
+ this.tasks = new Vector<TaskDescriptor>();
+ }
+ if(!this.tasks.contains(task)) {
+ this.tasks.add(task);
+ }
+ }
+}
\ No newline at end of file
package Analysis.Scheduling;
import Analysis.TaskStateAnalysis.*;
-import Analysis.TaskStateAnalysis.FEdge.NewObjInfo;
import IR.*;
import java.util.*;
-import java.io.*;
-
-import Util.Edge;
-import Util.GraphNode;
-import Util.Namer;
/** This class holds flag transition diagram(s) can be put on one core.
*/
public class ScheduleAnalysis {
- TaskAnalysis taskanalysis;
State state;
+ TaskAnalysis taskanalysis;
Vector<ScheduleNode> scheduleNodes;
Vector<ClassNode> classNodes;
+ Vector<ScheduleEdge> scheduleEdges;
Hashtable<ClassDescriptor, ClassNode> cd2ClassNode;
boolean sorted = false;
- Vector<ScheduleEdge> scheduleEdges;
int transThreshold;
int coreNum;
- Vector<Vector<ScheduleNode>> schedules;
+ Vector<Vector<ScheduleNode>> scheduleGraphs;
+ Vector<Vector<Schedule>> schedulings;
public ScheduleAnalysis(State state, TaskAnalysis taskanalysis) {
this.state = state;
this.cd2ClassNode = new Hashtable<ClassDescriptor, ClassNode>();
this.transThreshold = 45;
this.coreNum = -1;
+ this.scheduleGraphs = null;
+ this.schedulings = null;
}
public void setTransThreshold(int tt) {
this.transThreshold = tt;
}
+ public int getCoreNum() {
+ return coreNum;
+ }
+
public void setCoreNum(int coreNum) {
this.coreNum = coreNum;
}
- public Iterator getSchedules() {
- return this.schedules.iterator();
+ public Iterator getScheduleGraphs() {
+ return this.scheduleGraphs.iterator();
+ }
+
+ public Iterator getSchedulingsIter() {
+ return this.schedulings.iterator();
+ }
+
+ public Vector<Vector<Schedule>> getSchedulings() {
+ return this.schedulings;
}
// for test
// fake creating edge, do not need to create corresponding 'new' edge
continue;
}
+ if(noi.getRoot() == null) {
+ // set root FlagState
+ noi.setRoot(root);
+ }
FlagState pfs = (FlagState)pfe.getTarget();
ClassDescriptor pcd = pfs.getClassDescriptor();
ClassNode pcNode = cdToCNodes.get(pcd);
- ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", cd, 0);
+ ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", root, 0);//new ScheduleEdge(sNode, "new", cd, 0);
sEdge.setFEdge(pfe);
sEdge.setSourceCNode(pcNode);
sEdge.setTargetCNode(cNode);
}
}
- printScheduleGraph("scheduling_ori.dot", this.scheduleNodes);
+ SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes);
}
public void scheduleAnalysis() {
fe2ses = null;
sn2fes = null;
- printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
+ SchedulingUtil.printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
}
private void handleScheduleEdge(ScheduleEdge se, boolean merge) {
ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
ScheduleEdge se;
if(tse.getIsNew()) {
- se = new ScheduleEdge(csNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0);
+ se = new ScheduleEdge(csNode, "new", tse.getFstate(), tse.getIsNew(), 0); //new ScheduleEdge(csNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0);
se.setProbability(100);
se.setNewRate(1);
- se.setFEdge(tse.getFEdge());
} else {
- se = new ScheduleEdge(csNode, "transmit", tse.getClassDescriptor(), false, 0);
+ se = new ScheduleEdge(csNode, "transmit", tse.getFstate(), false, 0);//new ScheduleEdge(csNode, "transmit", tse.getClassDescriptor(), false, 0);
}
se.setSourceCNode(tse.getSourceCNode());
se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
+ se.setFEdge(tse.getFEdge());
+ se.setTargetFState(tse.getTargetFState());
+ se.setIsclone(true);
tse.getSource().addEdge(se);
scheduleEdges.add(se);
}
sEdge.setTarget(csNode);
csNode.getInedgeVector().add(sEdge);
sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
- sEdge.setTargetFState(null);
+ //sEdge.setTargetFState(null);
+ sEdge.setIsclone(true);
}
Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>();
qcn2cn.add(tocn2cn);
ScheduleEdge se = null;
if(tse.getIsNew()) {
- se = new ScheduleEdge(tSNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0);
+ se = new ScheduleEdge(tSNode, "new", tse.getFstate(), tse.getIsNew(), 0);//new ScheduleEdge(tSNode, "new", tse.getClassDescriptor(), tse.getIsNew(), 0);
se.setProbability(tse.getProbability());
se.setNewRate(tse.getNewRate());
} else {
- se = new ScheduleEdge(tSNode, "transmit", tse.getClassDescriptor(), false, 0);
+ se = new ScheduleEdge(tSNode, "transmit", tse.getFstate(), false, 0);//new ScheduleEdge(tSNode, "transmit", tse.getClassDescriptor(), false, 0);
}
se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
+ se.setFEdge(tse.getFEdge());
+ se.setTargetFState(tse.getTargetFState());
+ se.setIsclone(true);
csNode.addEdge(se);
scheduleEdges.add(se);
}
toiterate = null;
// create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode
- ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
+ ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", (FlagState)fe.getTarget(), false, 0);//new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
sEdge.setTargetFState(fs);
sEdge.setFEdge(fe);
sEdge.setSourceCNode(sCNode);
throw new Exception("Error: un-initialized coreNum when doing scheduling.");
}
- if(this.schedules == null) {
- this.schedules = new Vector<Vector<ScheduleNode>>();
+ if(this.scheduleGraphs == null) {
+ this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
}
int reduceNum = this.scheduleNodes.size() - this.coreNum;
// Enough cores, no need to merge more ScheduleEdge
if(!(reduceNum > 0)) {
- this.schedules.addElement(this.scheduleNodes);
+ this.scheduleGraphs.addElement(this.scheduleNodes);
} else {
// sort the ScheduleEdges in dececending order of transmittime
Vector<ScheduleEdge> sEdges = new Vector<ScheduleEdge>();
reduceEdges.add(sEdges.elementAt(((Integer)toreduce.elementAt(i)).intValue()));
}
Vector<ScheduleNode> sNodes = generateScheduling(reduceEdges, gid++);
- this.schedules.add(sNodes);
+ this.scheduleGraphs.add(sNodes);
reduceEdges = null;
sNodes = null;
} else {
sEdges = null;
candidates = null;
- /*
- // Assign a core to each ScheduleNode
- int i = 0;
- int coreNum = 1;
- for(i = 0; i < scheduleNodes.size(); i++) {
- ScheduleNode sn = scheduleNodes.elementAt(i);
- sn.setCoreNum(coreNum++);
- sn.listTasks();
+ }
+
+ if(this.schedulings == null) {
+ this.schedulings = new Vector<Vector<Schedule>>();
+ }
+
+ for(int i = 0; i < this.scheduleGraphs.size(); i++) {
+ 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);
+ }
+ 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);
+ }
+ }
+ }
+
// 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();
- sn.addTargetSNode(se.getTargetFState().getClassDescriptor(), target);
+ if(se.getIsNew()) {
+ for(int k = 0; k < se.getNewRate(); k++) {
+ tmpSchedule.addTargetCore(se.getFstate(), sn2coreNum.get(target));
+ }
+ } else {
+ // 'transmit' edge
+ tmpSchedule.addTargetCore(se.getFstate(), sn2coreNum.get(target), se.getTargetFState());
+ }
+ }
+ it_edges = sn.getScheduleEdgesIterator();
+ while(it_edges.hasNext()) {
+ ScheduleEdge se = (ScheduleEdge)it_edges.next();
+ if(se.getIsNew()) {
+ for(int k = 0; k < se.getNewRate(); k++) {
+ tmpSchedule.addTargetCore(se.getFstate(), j);
+ }
+ } else {
+ // 'transmit' edge
+ tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState());
+ }
}
- }*/
+ scheduling.add(tmpSchedule);
+ }
+ this.schedulings.add(scheduling);
}
}
Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
ScheduleEdge se;
if(sse.getIsNew()) {
- se = new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
+ se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getIsNew(), gid);//new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
se.setProbability(sse.getProbability());
se.setNewRate(sse.getNewRate());
- se.setFEdge(sse.getFEdge());
} else {
- se = new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
+ se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), false, gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
}
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);
if(reduceEdges.contains(sse)) {
toMerge.add(se);
toMerge = null;
String path = "scheduling_" + gid + ".dot";
- printScheduleGraph(path, result);
+ SchedulingUtil.printScheduleGraph(path, result);
return result;
}
- public void printScheduleGraph(String path, Vector<ScheduleNode> sNodes) {
- try {
- File file=new File(path);
- FileOutputStream dotstream=new FileOutputStream(file,false);
- PrintWriter output = new java.io.PrintWriter(dotstream, true);
- output.println("digraph G {");
- output.println("\tcompound=true;\n");
- traverseSNodes(output, sNodes);
- output.println("}\n");
- } catch (Exception e) {
- e.printStackTrace();
- System.exit(-1);
- }
- }
-
- private void traverseSNodes(PrintWriter output, Vector<ScheduleNode> sNodes){
- //Draw clusters representing ScheduleNodes
- Iterator it = sNodes.iterator();
- while (it.hasNext()) {
- ScheduleNode gn = (ScheduleNode) it.next();
- Iterator edges = gn.edges();
- output.println("\tsubgraph " + gn.getLabel() + "{");
- output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
- Iterator it_cnodes = gn.getClassNodesIterator();
- traverseCNodes(output, it_cnodes);
- //Draw the internal 'new' edges
- Iterator it_edges =gn.getScheduleEdgesIterator();
- while(it_edges.hasNext()) {
- ScheduleEdge se = (ScheduleEdge)it_edges.next();
- output.print("\t");
- if(se.getSourceCNode().isclone()) {
- output.print(se.getSourceCNode().getLabel());
- } else {
- if(se.getSourceFState() == null) {
- output.print(se.getSourceCNode().getClusterLabel());
- } else {
- output.print(se.getSourceFState().getLabel());
- }
- }
-
- output.print(" -> ");
- if(se.getTargetFState() == null) {
- if(se.getTargetCNode().isclone()) {
- output.print(se.getTargetCNode().getLabel());
- } else {
- output.print(se.getTargetCNode().getClusterLabel());
- }
- output.println(" [label=\"" + se.getLabel() + "\", color=red];");
- } else {
- output.print(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail=");
- if(se.getSourceCNode().isclone()) {
- output.println(se.getSourceCNode().getLabel() + "];");
- } else {
- output.println(se.getSourceCNode().getClusterLabel() + "];");
- }
- }
- }
- output.println("\t}\n");
- //Draw 'new' edges of this ScheduleNode
- while(edges.hasNext()) {
- ScheduleEdge se = (ScheduleEdge)edges.next();
- output.print("\t");
- if(se.getSourceCNode().isclone()) {
- output.print(se.getSourceCNode().getLabel());
- } else {
- if(se.getSourceFState() == null) {
- output.print(se.getSourceCNode().getClusterLabel());
- } else {
- output.print(se.getSourceFState().getLabel());
- }
- }
-
- output.print(" -> ");
- if(se.getTargetFState() == null) {
- if(se.getTargetCNode().isclone()) {
- output.print(se.getTargetCNode().getLabel());
- } else {
- output.print(se.getTargetCNode().getClusterLabel());
- }
- output.println(" [label=\"" + se.getLabel() + "\", color=red, style=dashed]");
- } else {
- output.println(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed]");
- }
- }
- }
- }
-
- private void traverseCNodes(PrintWriter output, Iterator it){
- //Draw clusters representing ClassNodes
- while (it.hasNext()) {
- ClassNode gn = (ClassNode) it.next();
- if(gn.isclone()) {
- output.println("\t\t" + gn.getLabel() + " [style=dashed, label=\"" + gn.getTextLabel() + "\", shape=box];");
- } else {
- output.println("\tsubgraph " + gn.getClusterLabel() + "{");
- output.println("\t\tstyle=dashed;");
- output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
- traverseFlagStates(output, gn.getFlagStates());
- output.println("\t}\n");
- }
- }
- }
-
- private void traverseFlagStates(PrintWriter output, Collection nodes) {
- Set cycleset=GraphNode.findcycles(nodes);
- Vector namers=new Vector();
- namers.add(new Namer());
- namers.add(new Allocations());
- //namers.add(new TaskEdges());
-
- Iterator it = nodes.iterator();
- while (it.hasNext()) {
- GraphNode gn = (GraphNode) it.next();
- Iterator edges = gn.edges();
- String label = "";
- String dotnodeparams="";
-
- for(int i=0;i<namers.size();i++) {
- Namer name=(Namer) namers.get(i);
- String newlabel=name.nodeLabel(gn);
- String newparams=name.nodeOption(gn);
-
- if (!newlabel.equals("") && !label.equals("")) {
- label+=", ";
- }
- if (!newparams.equals("")) {
- dotnodeparams+=", " + name.nodeOption(gn);
- }
- label+=name.nodeLabel(gn);
- }
- label += ":[" + ((FlagState)gn).getExeTime() + "]";
-
- if (!gn.merge)
- output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
-
- if (!gn.merge)
- while (edges.hasNext()) {
- Edge edge = (Edge) edges.next();
- GraphNode node = edge.getTarget();
- if (nodes.contains(node)) {
- for(Iterator nodeit=nonmerge(node, nodes).iterator();nodeit.hasNext();) {
- GraphNode node2=(GraphNode)nodeit.next();
- String edgelabel = "";
- String edgedotnodeparams="";
-
- for(int i=0;i<namers.size();i++) {
- Namer name=(Namer) namers.get(i);
- String newlabel=name.edgeLabel(edge);
- String newoption=name.edgeOption(edge);
- if (!newlabel.equals("")&& ! edgelabel.equals(""))
- edgelabel+=", ";
- edgelabel+=newlabel;
- if (!newoption.equals(""))
- edgedotnodeparams+=", "+newoption;
- }
- edgelabel+=":[" + ((FEdge)edge).getExeTime() + "]";
- Hashtable<ClassDescriptor, NewObjInfo> hashtable = ((FEdge)edge).getNewObjInfoHashtable();
- if(hashtable != null) {
- Set<ClassDescriptor> keys = hashtable.keySet();
- Iterator it_keys = keys.iterator();
- while(it_keys.hasNext()) {
- ClassDescriptor cd = (ClassDescriptor)it_keys.next();
- NewObjInfo noi = hashtable.get(cd);
- edgelabel += ":{ class " + cd.getSymbol() + " | " + noi.getNewRate() + " | (" + noi.getProbability() + "%) }";
- }
- }
- output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
- }
- }
- }
- }
- }
-
- private Set nonmerge(GraphNode gn, Collection nodes) {
- HashSet newset=new HashSet();
- HashSet toprocess=new HashSet();
- toprocess.add(gn);
- while(!toprocess.isEmpty()) {
- GraphNode gn2=(GraphNode)toprocess.iterator().next();
- toprocess.remove(gn2);
- if (!gn2.merge)
- newset.add(gn2);
- else {
- Iterator edges = gn2.edges();
- while (edges.hasNext()) {
- Edge edge = (Edge) edges.next();
- GraphNode node = edge.getTarget();
- if (!newset.contains(node)&&nodes.contains(node))
- toprocess.add(node);
- }
- }
- }
- return newset;
- }
-
class Combination{
Combination tail;
Object head;
package Analysis.Scheduling;
+
import java.util.Iterator;
import IR.*;
private static int nodeID=0;
private String label;
- private final ClassDescriptor cd;
+ //private final ClassDescriptor cd;
+ private final FlagState fstate;
private boolean isNew = true;
private FlagState targetFState;
private FEdge fedge;
private int newRate;
+ private boolean isclone;
+
/** Class Constructor
*
*/
- public ScheduleEdge(ScheduleNode target, String label, ClassDescriptor cd, int gid) {
+ public ScheduleEdge(ScheduleNode target, String label, /*ClassDescriptor cd,*/FlagState fstate, int gid) {
super(target);
this.uid = ScheduleEdge.nodeID++;
this.gid = gid;
this.sourceCNode = null;
this.targetCNode = null;
this.label = label;
- this.cd = cd;
+ //this.cd = cd;
+ this.fstate = fstate;
this.newRate = -1;
this.probability = 100;
this.transTime = -1;
this.listExeTime = -1;
+ this.isclone = false;
}
- public ScheduleEdge(ScheduleNode target, String label, ClassDescriptor cd, boolean isNew, int gid) {
+ public ScheduleEdge(ScheduleNode target, String label, /*ClassDescriptor cd,*/FlagState fstate, boolean isNew, int gid) {
super(target);
this.uid = ScheduleEdge.nodeID++;
this.gid = gid;
this.sourceCNode = null;
this.targetCNode = null;
this.label = label;
- this.cd = cd;
+ //this.cd = cd;
+ this.fstate = fstate;
this.newRate = -1;
this.probability = 100;
this.transTime = -1;
this.listExeTime = -1;
this.isNew = isNew;
+ this.isclone = false;
}
+ public boolean isclone() {
+ return isclone;
+ }
+
+ public void setIsclone(boolean isclone) {
+ this.isclone = isclone;
+ }
+
public void setTarget(GraphNode sn) {
this.target = sn;
}
return completeLabel;
}
- public ClassDescriptor getClassDescriptor() {
+ /*public ClassDescriptor getClassDescriptor() {
return cd;
+ }*/
+
+ public FlagState getFstate() {
+ return fstate;
}
public boolean getIsNew() {
if ((e.label.equals(label))&&
(e.target.equals(target))&&
(e.source.equals(source)) &&
- (e.cd.equals(cd)) &&
+ //(e.cd.equals(cd)) &&
+ (e.fstate.equals(fstate)) &&
(e.sourceCNode.equals(sourceCNode)) &&
(e.targetCNode.equals(targetCNode)) &&
(e.newRate == newRate) &&
}
public int hashCode(){
- int hashcode = gid^uid^label.hashCode()^target.hashCode()^source.hashCode()^cd.hashCode()^
+ int hashcode = gid^uid^label.hashCode()^target.hashCode()^source.hashCode()^fstate.hashCode()^//cd.hashCode()^
sourceCNode.hashCode()^targetCNode.hashCode()^newRate^probability^
Boolean.toString(isNew).hashCode()^transTime^listExeTime;
if(targetFState != null) {
package Analysis.Scheduling;
-import Analysis.TaskStateAnalysis.*;
-import IR.*;
import java.util.*;
import Util.GraphNode;
Vector<ScheduleEdge> scheduleEdges;
private int executionTime;
-
- private int coreNum;
- private Vector tasks;
- private Hashtable<ClassDescriptor, Vector<ScheduleNode>> targetSNodes;
- private boolean sorted = false;
/** Class constructor
* @param cd ClassDescriptor
public ScheduleNode(int gid) {
this.uid = ScheduleNode.nodeID++;
this.gid = gid;
- this.coreNum = -1;
this.executionTime = -1;
+ this.classNodes = null;
+ this.scheduleEdges = null;
}
public ScheduleNode(ClassNode cn, int gid) {
this.uid = ScheduleNode.nodeID++;
this.gid = gid;
- this.coreNum = -1;
this.classNodes = new Vector<ClassNode>();
this.scheduleEdges = new Vector<ScheduleEdge>();
this.classNodes.add(cn);
return uid;
}
- public int getCoreNum() {
- return this.coreNum;
- }
-
- public void setCoreNum(int coreNum) {
- this.coreNum = coreNum;
- }
-
- public void addTargetSNode(ClassDescriptor cd, ScheduleNode sn) {
- if(this.targetSNodes == null) {
- this.targetSNodes = new Hashtable<ClassDescriptor, Vector<ScheduleNode>>();
- }
-
- if(!this.targetSNodes.containsKey(cd)) {
- this.targetSNodes.put(cd, new Vector<ScheduleNode>());
- }
- this.targetSNodes.get(cd).add(sn);
- }
-
- public void listTasks() {
- if(this.tasks == null) {
- this.tasks = new Vector();
- }
-
- int i = 0;
- for(i = 0; i < classNodes.size(); i++) {
- Iterator it_flags = classNodes.elementAt(i).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();
- if(!this.tasks.contains(td)) {
- this.tasks.add(td);
- }
- }
- }
- }
- }
-
- public void addTask(TaskDescriptor task){
- tasks.add(task);
- }
-
- public Vector getTasks(){
- return tasks;
- }
-
- public boolean isSorted() {
- return sorted;
- }
-
- public void setSorted(boolean sorted) {
- this.sorted = sorted;
- }
-
public String toString() {
String temp = new String("");
for(int i = 0; i < classNodes.size(); i++) {
return false;
}
}
- if ((fs.sorted != this.sorted) ||
- (fs.executionTime != this.executionTime)){
+ if ((fs.executionTime != this.executionTime)){
return false;
}
if(fs.classNodes != null) {
}
public int hashCode() {
- int hashcode = gid^uid^Boolean.toString(sorted).hashCode()^executionTime;//^scheduleEdges.hashCode();
+ int hashcode = gid^uid^executionTime;
if(this.classNodes != null) {
hashcode ^= classNodes.hashCode();
}
public String getTextLabel() {
String label=null;
- if(this.coreNum != -1) {
- label = "Core " + this.coreNum;
- }
if (label==null)
return " ";
ScheduleEdge temp = this.scheduleEdges.elementAt(i);
ScheduleEdge se = null;
if(!temp.getIsNew()) {
- se = new ScheduleEdge(o, "transmit",temp.getClassDescriptor(), false, gid);
+ se = new ScheduleEdge(o, "transmit",temp.getFstate(), false, gid);//new ScheduleEdge(o, "transmit",temp.getClassDescriptor(), false, gid);
} else {
- se = new ScheduleEdge(o, "new",temp.getClassDescriptor(), gid);
+ se = new ScheduleEdge(o, "new",temp.getFstate(), gid);//new ScheduleEdge(o, "new",temp.getClassDescriptor(), gid);
}
se.setSourceCNode(cn2cn.get(temp.getSourceCNode()));
se.setTargetCNode(cn2cn.get(temp.getTargetCNode()));
se.setProbability(temp.getProbability());
se.setNewRate(temp.getNewRate());
se.setTransTime(temp.getTransTime());
+ se.setFEdge(temp.getFEdge());
+ se.setTargetFState(temp.getTargetFState());
+ se.setIsclone(true);
tses.add(se);
}
o.classNodes = tcns;
--- /dev/null
+package Analysis.Scheduling;
+
+import java.util.Hashtable;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.Queue;
+import java.util.Vector;
+import java.util.Map.Entry;
+
+import Analysis.TaskStateAnalysis.FlagState;
+import Analysis.TaskStateAnalysis.TaskAnalysis;
+import IR.ClassDescriptor;
+import IR.State;
+import IR.TaskDescriptor;
+import IR.TypeUtil;
+
+public class ScheduleSimulator {
+ private int coreNum;
+ 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;
+ 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) {
+ super();
+ 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;
+ this.taskanalysis = taskanalysis;
+ applyScheduling();
+ }
+
+ public Vector<CheckPoint> getCheckpoints() {
+ return checkpoints;
+ }
+
+ public int getCoreNum() {
+ return coreNum;
+ }
+
+ public void setCoreNum(int coreNum) {
+ this.coreNum = coreNum;
+ if(this.cores != null) {
+ this.cores.clear();
+ }
+ this.cores = new Vector<CoreSimulator>(this.coreNum);
+ for(int i = 0; i < this.coreNum; i++) {
+ this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
+ }
+ if(this.scheduling != null) {
+ applyScheduling();
+ }
+ }
+
+ public int getUtility(int index) {
+ return (this.cores.elementAt(index).getActiveTime() * 100) / this.processTime;
+ }
+
+ public Vector<Schedule> getScheduling() {
+ return scheduling;
+ }
+
+ public void setScheduling(Vector<Schedule> scheduling) {
+ this.scheduling = scheduling;
+ if(this.tasks == null) {
+ this.tasks = new Vector<TaskSimulator>();
+ } else {
+ this.tasks.clear();
+ }
+ if(this.cores != null) {
+ for(int i = 0; i < this.coreNum; i++) {
+ CoreSimulator core = this.cores.elementAt(i);
+ core.reset();
+ core.setRSchedule(FIFORSchedule.getFIFORSchedule());
+ }
+ } else {
+ this.cores = new Vector<CoreSimulator>(this.coreNum);
+ for(int i = 0; i < this.coreNum; i++) {
+ this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
+ }
+ }
+
+ applyScheduling();
+ }
+
+ public void applyScheduling() {
+ assert(this.state != null);
+
+ for(int i = 0; i < this.scheduling.size(); i++) {
+ Schedule temp = this.scheduling.elementAt(i);
+ CoreSimulator cs = this.cores.elementAt(temp.getCoreNum());
+ cs.deployTasks(temp.getTasks());
+ cs.setTargetCSimulator(temp.getTargetCoreTable());
+ cs.setTargetFState(temp.getTargetFStateTable());
+ }
+ // inject a Startup Object to each core
+ for(int i = 0; i < this.coreNum; i++) {
+ ClassDescriptor startupobject=(ClassDescriptor)state.getClassSymbolTable().get(TypeUtil.StartupClass);
+ FlagState fsstartup = (FlagState)taskanalysis.getRootNodes(startupobject).elementAt(0);
+ ObjectSimulator newObj = new ObjectSimulator(startupobject, fsstartup);
+ this.cores.elementAt(i).addObject(newObj);
+ }
+ }
+
+ public Vector<TaskSimulator> getTasks() {
+ return tasks;
+ }
+
+ public int process() {
+ assert(this.scheduling != null);
+
+ if(this.checkpoints == null) {
+ this.checkpoints = new Vector<CheckPoint>();
+ } else {
+ this.checkpoints.clear();
+ }
+
+ this.processTime = 0;
+
+ // first decide next task to execute on each core
+ int i = 0;
+ for(i = 0; i < this.cores.size(); i++) {
+ CoreSimulator cs = this.cores.elementAt(i);
+ TaskSimulator task = cs.process();
+ if(task != null) {
+ this.tasks.add(task);
+ }
+ }
+
+ // add STARTTASK checkpoint for all the initial tasks
+ CheckPoint cp = new CheckPoint(this.processTime);
+ 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());
+ cp.addAction(action);
+ }
+ this.checkpoints.add(cp);
+
+ while(true) {
+ // if no more tasks on each core, simulation finish
+ if(this.tasks.size() == 0) {
+ break;
+ }
+
+ // 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++) {
+ TaskSimulator task = this.tasks.elementAt(i);
+ task.process();
+ int tempTime = task.getCurrentRun().getFinishTime();
+ if(tempTime < finishTime) {
+ finishTime = tempTime;
+ finishTasks.clear();
+ finishTasks.add(task);
+ } else if (tempTime == finishTime) {
+ finishTasks.add(task);
+ }
+ }
+ for(i = 0; i < this.tasks.size(); i++) {
+ TaskSimulator task = this.tasks.elementAt(i);
+ if(!finishTasks.contains(task)) {
+ task.getCs().updateTask(finishTime);
+ }
+ }
+ 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();
+ ObjectSimulator nobj = tmptask.refreshTask();
+ this.cores.elementAt(targetCoreNum).addObject(nobj);
+ 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);
+ }
+ 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());
+ cp.addAction(action);
+ }
+ }
+ } else {
+ CoreSimulator cs = task.getCs();
+ int coreNum = cs.getCoreNum();
+ Hashtable<Integer, Queue<ObjectSimulator>> transObjQueues = new Hashtable<Integer, Queue<ObjectSimulator>>();
+ 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();
+ //Schedule schedule = this.scheduling.elementAt(coreNum);
+ 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) {
+ // this obj will reside on this core
+ cs.addObject(nobj);
+ } else {
+ Integer targetCore = cores.poll();
+ if(targetCore == coreNum) {
+ // this obj will reside on this core
+ cs.addObject(nobj);
+ } else {
+ if(!transObjQueues.containsKey(targetCore)) {
+ transObjQueues.put(targetCore, new LinkedList<ObjectSimulator>());
+ }
+ Queue<ObjectSimulator> tmpqueue = transObjQueues.get(targetCore);
+ tmpqueue.add(nobj);
+ }
+ // enqueue this core again
+ cores.add(targetCore);
+ }
+ }
+ }
+ 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) {
+ // this obj will reside on this core
+ cs.addObject(tobj);
+ } else {
+ Integer targetCore = cores.peek();
+ if(targetCore == coreNum) {
+ // this obj will reside on this core
+ cs.addObject(tobj);
+ } else {
+ if(!transObjQueues.containsKey(targetCore)) {
+ transObjQueues.put(targetCore, new LinkedList<ObjectSimulator>());
+ }
+ Queue<ObjectSimulator> tmpqueue = transObjQueues.get(targetCore);
+ tmpqueue.add(tobj);
+ }
+ }
+ }
+ }
+ // add 'transport' tasks
+ Iterator it_entries = transObjQueues.entrySet().iterator();
+ while(it_entries.hasNext()) {
+ Entry<Integer, Queue<ObjectSimulator>> tmpentry = (Entry<Integer, Queue<ObjectSimulator>>)it_entries.next();
+ Integer tmpCoreNum = tmpentry.getKey();
+ Queue<ObjectSimulator> nobjs = tmpentry.getValue();
+ TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs);
+ this.tasks.add(tmptask);
+ }
+ // 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);
+ }
+
+ 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.invoketime++;
+ return this.processTime;
+ }
+
+ public class CheckPoint {
+ private int timepoint;
+ private Vector<Action> actions;
+
+ public CheckPoint(int timepoint) {
+ super();
+ this.timepoint = timepoint;
+ this.actions = new Vector<Action>();
+ }
+
+ public Vector<Action> getActions() {
+ return actions;
+ }
+
+ public void addAction(Action action) {
+ this.actions.add(action);
+ }
+
+ public int getTimepoint() {
+ return timepoint;
+ }
+ }
+
+ public class Action {
+ public static final int ADDOBJ = 0;
+ public static final int TASKFINISH = 1;
+ public static final int TFWITHOBJ = 2;
+ public static final int TASKSTART = 3;
+
+ private int coreNum;
+ private int type;
+ private TaskDescriptor td;
+ private Hashtable<ClassDescriptor, Integer> nObjs;
+ private int nObjNum;
+ private ClassDescriptor transObj;
+
+ public Action(int coreNum, int type) {
+ super();
+ this.coreNum = coreNum;
+ this.type = type;
+ this.td = 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();
+ assert(type == ADDOBJ);
+ this.coreNum = coreNum;
+ this.type = type;
+ this.td = null;
+ this.nObjNum = objNum;
+ this.transObj = transObj;
+ }
+
+ public void addNewObj(ClassDescriptor cd, Integer num) {
+ assert(this.type == TFWITHOBJ);
+
+ if(this.nObjs.containsKey(cd)) {
+ Integer sum = this.nObjs.get(cd) + num;
+ this.nObjs.put(cd, sum);
+ } else {
+ this.nObjs.put(cd, num);
+ }
+ }
+
+ public int getCoreNum() {
+ return coreNum;
+ }
+
+ public int getType() {
+ return type;
+ }
+
+ public int getNObjNum() {
+ return nObjNum;
+ }
+
+ public ClassDescriptor getTransObj() {
+ return transObj;
+ }
+
+ public TaskDescriptor getTd() {
+ return td;
+ }
+
+ public void setTd(TaskDescriptor td) {
+ this.td = td;
+ }
+
+ public Hashtable<ClassDescriptor, Integer> getNObjs() {
+ return nObjs;
+ }
+ }
+
+}
\ No newline at end of file
--- /dev/null
+package Analysis.Scheduling;
+
+import java.io.File;
+import java.io.FileOutputStream;
+import java.io.PrintWriter;
+import java.util.Collection;
+import java.util.Enumeration;
+import java.util.HashSet;
+import java.util.Hashtable;
+import java.util.Iterator;
+import java.util.Set;
+import java.util.Vector;
+import java.util.Map.Entry;
+
+import Analysis.Scheduling.ScheduleSimulator.Action;
+import Analysis.Scheduling.ScheduleSimulator.CheckPoint;
+import Analysis.TaskStateAnalysis.Allocations;
+import Analysis.TaskStateAnalysis.FEdge;
+import Analysis.TaskStateAnalysis.FlagState;
+import Analysis.TaskStateAnalysis.FEdge.NewObjInfo;
+import IR.ClassDescriptor;
+import IR.Operation;
+import IR.Tree.FlagExpressionNode;
+import IR.Tree.FlagNode;
+import IR.Tree.FlagOpNode;
+import Util.Edge;
+import Util.GraphNode;
+import Util.Namer;
+
+public class SchedulingUtil {
+
+ /*public static int maxDivisor(int l, int r) {
+ int a = l;
+ int b = r;
+ int c = 0;
+
+ while(true) {
+ if(a == 0) {
+ return b << c;
+ } else if(b == 0) {
+ return a << c;
+ }
+
+ if(((a&1)==0) && ((b&1)==0)) {
+ // a and b are both even
+ a >>= 1;
+ b >>= 1;
+ ++c;
+ } else if(((a&1)==0) && ((b&1)!=0)) {
+ // a is even, b is odd
+ a >>= 1;
+ } else if (((a&1)!=0) && ((b&1)==0)) {
+ // a is odd, b is even
+ b >>= 1;
+ } else if (((a&1)!=0) && ((b&1)!=0)) {
+ // a and b are both odd
+ int tmp = a>b? b:a;
+ a = a>b ? (a-b):(b-a);
+ b = tmp;
+ }
+ }
+ }*/
+
+ public static boolean isTaskTrigger_flag(FlagExpressionNode fen,FlagState fs) {
+ if (fen==null)
+ return true;
+ else if (fen instanceof FlagNode)
+ return fs.get(((FlagNode)fen).getFlag());
+ else
+ switch (((FlagOpNode)fen).getOp().getOp()) {
+ case Operation.LOGIC_AND:
+ return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
+ case Operation.LOGIC_OR:
+ return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
+ case Operation.LOGIC_NOT:
+ return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
+ default:
+ return false;
+ }
+ }
+
+ public static void printScheduleGraph(String path, Vector<ScheduleNode> sNodes) {
+ try {
+ File file=new File(path);
+ FileOutputStream dotstream=new FileOutputStream(file,false);
+ PrintWriter output = new java.io.PrintWriter(dotstream, true);
+ output.println("digraph G {");
+ output.println("\tcompound=true;\n");
+ traverseSNodes(output, sNodes);
+ output.println("}\n");
+ output.close();
+ } catch (Exception e) {
+ e.printStackTrace();
+ System.exit(-1);
+ }
+ }
+
+ private static void traverseSNodes(PrintWriter output, Vector<ScheduleNode> sNodes){
+ //Draw clusters representing ScheduleNodes
+ Iterator it = sNodes.iterator();
+ while (it.hasNext()) {
+ ScheduleNode gn = (ScheduleNode) it.next();
+ Iterator edges = gn.edges();
+ output.println("\tsubgraph " + gn.getLabel() + "{");
+ output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
+ Iterator it_cnodes = gn.getClassNodesIterator();
+ traverseCNodes(output, it_cnodes);
+ //Draw the internal 'new' edges
+ Iterator it_edges =gn.getScheduleEdgesIterator();
+ while(it_edges.hasNext()) {
+ ScheduleEdge se = (ScheduleEdge)it_edges.next();
+ output.print("\t");
+ if(se.getSourceCNode().isclone()) {
+ output.print(se.getSourceCNode().getLabel());
+ } else {
+ if(se.getSourceFState() == null) {
+ output.print(se.getSourceCNode().getClusterLabel());
+ } else {
+ output.print(se.getSourceFState().getLabel());
+ }
+ }
+
+ output.print(" -> ");
+ //if(se.getTargetFState() == null) {
+ if(se.isclone()) {
+ if(se.getTargetCNode().isclone()) {
+ output.print(se.getTargetCNode().getLabel());
+ } else {
+ output.print(se.getTargetCNode().getClusterLabel());
+ }
+ output.println(" [label=\"" + se.getLabel() + "\", color=red];");
+ } else {
+ output.print(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, ltail=");
+ if(se.getSourceCNode().isclone()) {
+ output.println(se.getSourceCNode().getLabel() + "];");
+ } else {
+ output.println(se.getSourceCNode().getClusterLabel() + "];");
+ }
+ }
+ }
+ output.println("\t}\n");
+ //Draw 'new' edges of this ScheduleNode
+ while(edges.hasNext()) {
+ ScheduleEdge se = (ScheduleEdge)edges.next();
+ output.print("\t");
+ if(se.getSourceCNode().isclone()) {
+ output.print(se.getSourceCNode().getLabel());
+ } else {
+ if(se.getSourceFState() == null) {
+ output.print(se.getSourceCNode().getClusterLabel());
+ } else {
+ output.print(se.getSourceFState().getLabel());
+ }
+ }
+
+ output.print(" -> ");
+ //if(se.getTargetFState() == null) {
+ if(se.isclone()) {
+ if(se.getTargetCNode().isclone()) {
+ output.print(se.getTargetCNode().getLabel());
+ } else {
+ output.print(se.getTargetCNode().getClusterLabel());
+ }
+ output.println(" [label=\"" + se.getLabel() + "\", color=red, style=dashed]");
+ } else {
+ output.println(se.getTargetFState().getLabel() + " [label=\"" + se.getLabel() + "\", color=red, style=dashed]");
+ }
+ }
+ }
+ }
+
+ private static void traverseCNodes(PrintWriter output, Iterator it){
+ //Draw clusters representing ClassNodes
+ while (it.hasNext()) {
+ ClassNode gn = (ClassNode) it.next();
+ if(gn.isclone()) {
+ output.println("\t\t" + gn.getLabel() + " [style=dashed, label=\"" + gn.getTextLabel() + "\", shape=box];");
+ } else {
+ output.println("\tsubgraph " + gn.getClusterLabel() + "{");
+ output.println("\t\tstyle=dashed;");
+ output.println("\t\tlabel=\"" + gn.getTextLabel() + "\";");
+ traverseFlagStates(output, gn.getFlagStates());
+ output.println("\t}\n");
+ }
+ }
+ }
+
+ private static void traverseFlagStates(PrintWriter output, Collection nodes) {
+ Set cycleset=GraphNode.findcycles(nodes);
+ Vector namers=new Vector();
+ namers.add(new Namer());
+ namers.add(new Allocations());
+ //namers.add(new TaskEdges());
+
+ Iterator it = nodes.iterator();
+ while (it.hasNext()) {
+ GraphNode gn = (GraphNode) it.next();
+ Iterator edges = gn.edges();
+ String label = "";
+ String dotnodeparams="";
+
+ for(int i=0;i<namers.size();i++) {
+ Namer name=(Namer) namers.get(i);
+ String newlabel=name.nodeLabel(gn);
+ String newparams=name.nodeOption(gn);
+
+ if (!newlabel.equals("") && !label.equals("")) {
+ label+=", ";
+ }
+ if (!newparams.equals("")) {
+ dotnodeparams+=", " + name.nodeOption(gn);
+ }
+ label+=name.nodeLabel(gn);
+ }
+ label += ":[" + ((FlagState)gn).getExeTime() + "]";
+
+ if (!gn.merge)
+ output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
+
+ if (!gn.merge)
+ while (edges.hasNext()) {
+ Edge edge = (Edge) edges.next();
+ GraphNode node = edge.getTarget();
+ if (nodes.contains(node)) {
+ for(Iterator nodeit=nonmerge(node, nodes).iterator();nodeit.hasNext();) {
+ GraphNode node2=(GraphNode)nodeit.next();
+ String edgelabel = "";
+ String edgedotnodeparams="";
+
+ for(int i=0;i<namers.size();i++) {
+ Namer name=(Namer) namers.get(i);
+ String newlabel=name.edgeLabel(edge);
+ String newoption=name.edgeOption(edge);
+ if (!newlabel.equals("")&& ! edgelabel.equals(""))
+ edgelabel+=", ";
+ edgelabel+=newlabel;
+ if (!newoption.equals(""))
+ edgedotnodeparams+=", "+newoption;
+ }
+ edgelabel+=":[" + ((FEdge)edge).getExeTime() + "]";
+ Hashtable<ClassDescriptor, NewObjInfo> hashtable = ((FEdge)edge).getNewObjInfoHashtable();
+ if(hashtable != null) {
+ Set<ClassDescriptor> keys = hashtable.keySet();
+ Iterator it_keys = keys.iterator();
+ while(it_keys.hasNext()) {
+ ClassDescriptor cd = (ClassDescriptor)it_keys.next();
+ NewObjInfo noi = hashtable.get(cd);
+ edgelabel += ":{ class " + cd.getSymbol() + " | " + noi.getNewRate() + " | (" + noi.getProbability() + "%) }";
+ }
+ }
+ output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
+ }
+ }
+ }
+ }
+ }
+
+ private static Set nonmerge(GraphNode gn, Collection nodes) {
+ HashSet newset=new HashSet();
+ HashSet toprocess=new HashSet();
+ toprocess.add(gn);
+ while(!toprocess.isEmpty()) {
+ GraphNode gn2=(GraphNode)toprocess.iterator().next();
+ toprocess.remove(gn2);
+ if (!gn2.merge)
+ newset.add(gn2);
+ else {
+ Iterator edges = gn2.edges();
+ while (edges.hasNext()) {
+ Edge edge = (Edge) edges.next();
+ GraphNode node = edge.getTarget();
+ if (!newset.contains(node)&&nodes.contains(node))
+ toprocess.add(node);
+ }
+ }
+ }
+ return newset;
+ }
+
+ 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);
+ 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");
+ int j = 0;
+
+ // the capital line
+ output.print("{rank=source; \"Time\"; ");
+ for(j = 0; j < coreNum; j++) {
+ output.print("\"core " + j + "\"; ");
+ }
+ output.println("}");
+ // time coordinate nodes
+ Vector<String> timeNodes = new Vector<String>();
+ String[] lastTaskNodes = new String[coreNum];
+ boolean[] isTaskFinish = new boolean[coreNum];
+ for(j = 0; j < coreNum; j++) {
+ lastTaskNodes[j] = "first";
+ isTaskFinish[j] = true;
+ }
+ timeNodes.add("0");
+ for(j = 0; j < checkpoints.size(); j++) {
+ CheckPoint tcp = checkpoints.elementAt(j);
+ String tnode = String.valueOf(tcp.getTimepoint());
+ if(!timeNodes.contains(tnode)) {
+ timeNodes.add(tnode);
+ }
+ Vector<Action> actions = tcp.getActions();
+ Hashtable<String, StringBuffer> tmpTaskNodes = new Hashtable<String, StringBuffer>();
+ //Vector<String> sortedttnodes = new Vector<String>();
+ for(int i = 0; i < actions.size(); i++) {
+ Action taction = actions.elementAt(i);
+ int cNum = taction.getCoreNum();
+ String tmpTaskNode = "\"" + tnode + "core" + cNum + "\"";
+ StringBuffer tmpLabel = null;
+ boolean isfirst = false;
+ if(!tmpTaskNodes.containsKey(tmpTaskNode)) {
+ tmpTaskNodes.put(tmpTaskNode, new StringBuffer(tnode + ":"));
+ isfirst = true;
+ /*int length = sortedttnodes.size();
+ int k = length;
+ for(; k > 0; k--) {
+ String tmptnode = sortedttnodes.elementAt(k-1);
+ int tcorenum = Integer.parseInt(tmptnode.substring(tmptnode.indexOf("core") + 4, tmptnode.length() - 1));
+ if(tcorenum < cNum) {
+ break;
+ }
+ }
+ sortedttnodes.add(k, tmpTaskNode);*/
+ }
+ tmpLabel = tmpTaskNodes.get(tmpTaskNode);
+ switch(taction.getType()){
+ case Action.ADDOBJ: {
+ if(!isfirst) {
+ tmpLabel.append("\\n");
+ }
+ tmpLabel.append("(" + taction.getTransObj().getSymbol() + ")arrives;");
+ if(!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
+ output.print("\t");
+ if(lastTaskNodes[cNum].equals("first")) {
+ output.println("\"core " + cNum + "\"->" + tmpTaskNode);
+ } else {
+ output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
+ }
+ if(isTaskFinish[cNum]) {
+ output.print(" [style=invis]");
+ }
+ output.println(";");
+ lastTaskNodes[cNum] = tmpTaskNode;
+ }
+ break;
+ }
+ case Action.TASKFINISH: {
+ if(!isfirst) {
+ tmpLabel.append("\\n");
+ }
+ tmpLabel.append("<" + taction.getTd().getSymbol() + ">finishes;");
+ if(!(lastTaskNodes[cNum].equals("first")) &&
+ !(lastTaskNodes[cNum].equals(tmpTaskNode))) {
+ output.print("\t");
+ output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
+ lastTaskNodes[cNum] = tmpTaskNode;
+ isTaskFinish[cNum] = true;
+ } else {
+ throw new Exception("Error: unexpected task finish");
+ }
+ break;
+ }
+ case Action.TFWITHOBJ: {
+ if(!isfirst) {
+ tmpLabel.append("\\n");
+ }
+ tmpLabel.append("<" + taction.getTd().getSymbol() + ">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();
+ tmpLabel.append(entry.getValue() + "(" + entry.getKey().getSymbol() + ")");
+ if(it_entry.hasNext()) {
+ tmpLabel.append(",");
+ } else {
+ tmpLabel.append(";");
+ }
+ }
+ if(!(lastTaskNodes[cNum].equals("first")) &&
+ !(lastTaskNodes[cNum].equals(tmpTaskNode))) {
+ output.print("\t");
+ output.println(lastTaskNodes[cNum] + "->" + tmpTaskNode);
+ lastTaskNodes[cNum] = tmpTaskNode;
+ isTaskFinish[cNum] = true;
+ } else {
+ throw new Exception("Error: unexpected task finish");
+ }
+ break;
+ }
+ case Action.TASKSTART: {
+ if(!isfirst) {
+ tmpLabel.append("\\n");
+ }
+ tmpLabel.append("<" + taction.getTd().getSymbol() + ">starts;");
+
+ if (!(lastTaskNodes[cNum].equals(tmpTaskNode))) {
+ output.print("\t");
+ if(lastTaskNodes[cNum].equals("first")) {
+ output.print("\"core " + cNum + "\"->" + tmpTaskNode);
+ } else {
+ output.print(lastTaskNodes[cNum] + "->" + tmpTaskNode);
+ }
+ if(isTaskFinish[cNum]) {
+ output.print(" [style=invis]");
+ }
+ output.println(";");
+ lastTaskNodes[cNum] = tmpTaskNode;
+ }
+ isTaskFinish[cNum] = false;
+ break;
+ }
+ }
+ }
+ Enumeration<String> keys = tmpTaskNodes.keys();
+ while(keys.hasMoreElements()) {
+ String tmpTaskNode = keys.nextElement();
+ output.print("\t");
+ output.println(tmpTaskNode + "[label=\"" + tmpTaskNodes.get(tmpTaskNode).toString() + "\"]");
+ }
+ output.print("\t");
+ output.print("{rank=same; rankdir=LR; " + tnode + "; ");
+ /*for(int k = 0; k < sortedttnodes.size(); k++) {
+ output.print(sortedttnodes.elementAt(k));
+ output.print("; ");
+ }*/
+ keys = tmpTaskNodes.keys();
+ while(keys.hasMoreElements()) {
+ String tmpTaskNode = keys.nextElement();
+ output.print(tmpTaskNode);
+ output.print("; ");
+ }
+ output.println("}");
+ output.print("\t");
+ /*output.print(tnode + "->");
+ for(int k = 0; k < sortedttnodes.size() - 1; k++) {
+ output.print(sortedttnodes.elementAt(k) + "->");
+ }
+ output.println(sortedttnodes.lastElement() + " [style=dashed];");*/
+ }
+ output.print("\t");
+ //output.println("node [shape=point, color=blue];");
+ output.print("\t");
+ output.println("\"Time\"->" + timeNodes.elementAt(0) + "[style=invis];");
+ //for(j = 0; j < timeNodes.size() - 1; j++) {
+ for(j = 0; j < time; j++) {
+ output.print(j + "->");
+ }
+ output.println(timeNodes.lastElement() + ";");
+ 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.Iterator;
+import java.util.LinkedList;
+import java.util.Queue;
+import java.util.Vector;
+
+import Analysis.TaskStateAnalysis.FEdge;
+import Analysis.TaskStateAnalysis.FlagState;
+import Analysis.TaskStateAnalysis.FEdge.NewObjInfo;
+import IR.ClassDescriptor;
+import IR.TaskDescriptor;
+import IR.VarDescriptor;
+import IR.Tree.FlagExpressionNode;
+
+public class TaskSimulator {
+ TaskDescriptor td;
+ Vector<Queue<ObjectSimulator>> paraQueues;
+ ExeResult currentRun;
+ CoreSimulator cs;
+ boolean finish;
+
+ public class ExeResult {
+ int finishTime;
+ Vector<ObjectSimulator> newObjs;
+
+ public ExeResult() {
+ finishTime = 0;
+ newObjs = null;
+ }
+
+ public int getFinishTime() {
+ return finishTime;
+ }
+
+ public void setFinishTime(int finishTime) {
+ this.finishTime = finishTime;
+ }
+
+ public Vector<ObjectSimulator> getNewObjs() {
+ return newObjs;
+ }
+
+ public void addNewObj(ObjectSimulator newObj) {
+ if(this.newObjs == null) {
+ this.newObjs = new Vector<ObjectSimulator>();
+ }
+
+ this.newObjs.add(newObj);
+ }
+
+ }
+
+ public TaskSimulator(TaskDescriptor td, CoreSimulator cs) {
+ super();
+ this.td = td;
+ this.paraQueues = null;
+ this.currentRun = null;
+ this.cs = cs;
+ this.finish = true;
+ }
+
+ public CoreSimulator getCs() {
+ return cs;
+ }
+
+ public TaskDescriptor getTd() {
+ return td;
+ }
+
+ public ExeResult getCurrentRun() {
+ return currentRun;
+ }
+
+ public Vector<Queue<ObjectSimulator>> getParaQueues() {
+ return paraQueues;
+ }
+
+ public void enquePara(ObjectSimulator obj) {
+ ClassDescriptor cd = obj.getCd();
+ int paraNum = td.numParameters();
+ for(int i = 0; i < paraNum; i++) {
+ VarDescriptor para = td.getParameter(i);
+ if(cd.equals(para.getType().getClassDesc())) {
+ // check if the status is right
+ FlagExpressionNode fen = td.getFlag(para);
+ if(SchedulingUtil.isTaskTrigger_flag(fen, obj.getCurrentFS())) {
+ if(this.paraQueues == null) {
+ this.paraQueues = new Vector<Queue<ObjectSimulator>>();
+ for(int j = 0; j < paraNum; j++) {
+ this.paraQueues.add(null);
+ }
+ }
+ if(this.paraQueues.elementAt(i) == null) {
+ this.paraQueues.setElementAt(new LinkedList<ObjectSimulator>(), i);
+ }
+ this.paraQueues.elementAt(i).add(obj);
+ }
+ }
+ }
+ }
+
+ public void refreshPara(ObjectSimulator obj, boolean remove) {
+ ClassDescriptor cd = obj.getCd();
+ int paraNum = td.numParameters();
+ for(int i = 0; i < paraNum; i++) {
+ VarDescriptor para = td.getParameter(i);
+ if(cd.equals(para.getType().getClassDesc())) {
+ if(remove) {
+ if((this.paraQueues != null) &&
+ (this.paraQueues.elementAt(i) != null) &&
+ (this.paraQueues.elementAt(i).contains(obj))){
+ this.paraQueues.elementAt(i).remove(obj);
+ }
+ } else {
+ // check if the status is right
+ FlagExpressionNode fen = td.getFlag(para);
+ if(SchedulingUtil.isTaskTrigger_flag(fen, obj.getCurrentFS())) {
+ if(this.paraQueues == null) {
+ this.paraQueues = new Vector<Queue<ObjectSimulator>>();
+ for(int j = 0; j < paraNum; j++) {
+ this.paraQueues.add(null);
+ }
+ }
+ if(this.paraQueues.elementAt(i) == null) {
+ this.paraQueues.setElementAt(new LinkedList<ObjectSimulator>(), i);
+ }
+ this.paraQueues.elementAt(i).add(obj);
+ } else {
+ if((this.paraQueues != null) &&
+ (this.paraQueues.elementAt(i) != null) &&
+ (this.paraQueues.elementAt(i).contains(obj))){
+ this.paraQueues.elementAt(i).remove(obj);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ public void process() {
+ if(!finish) {
+ return;
+ } else {
+ finish = false;
+ }
+
+ if(this.currentRun == null) {
+ this.currentRun = new ExeResult();
+ }
+
+ int finishTime = 0;
+ // According to runtime statistic information, decide the execution path of this task this time.
+ // Mainly following things:
+ // 1.the result, i.e. the result FlagState reached by each parameter.
+ // 2.the finish time
+ // 3.any new objects
+ for(int i = 0; i < paraQueues.size(); i++) {
+ ObjectSimulator tpara = paraQueues.elementAt(i).peek();
+ // remove this object from the remaining parameter queues
+ for(int j = i + 1; j < paraQueues.size(); j++) {
+ paraQueues.elementAt(j).remove(tpara);
+ }
+ FlagState tfstate = tpara.getCurrentFS();
+ FEdge toexecute = tfstate.process(td);
+ finishTime += toexecute.getExeTime();
+ if((toexecute.getNewObjInfoHashtable() != null) && (toexecute.getNewObjInfoHashtable().size() > 0)) {
+ // have new objects
+ Iterator it = toexecute.getNewObjInfoHashtable().keySet().iterator();
+ int invokeNum = toexecute.getInvokeNum();
+ while(it.hasNext()) {
+ ClassDescriptor cd = (ClassDescriptor)it.next();
+ NewObjInfo noi = toexecute.getNewObjInfo(cd);
+ if(noi.getInvokeNum() < ((int)Math.round(((noi.getProbability() / 100) * noi.getNewRate() * invokeNum)))) {
+ for(int j = 0; j < noi.getNewRate(); j++) {
+ ObjectSimulator tmpObj = new ObjectSimulator(cd, noi.getRoot());
+ this.currentRun.addNewObj(tmpObj);
+ noi.incInvokeNum();
+ }
+ }
+ }
+ }
+ //FlagState tFState = (FlagState)toexecute.getTarget();
+ //tpara.setCurrentFS(tFState);
+ tpara.applyEdge(toexecute);
+ }
+ finishTime /= paraQueues.size();
+ this.currentRun.setFinishTime(finishTime);
+ }
+
+ public void updateFinishTime(int time) {
+ this.currentRun.setFinishTime(this.currentRun.finishTime - time);
+ finish = false;
+ }
+
+ public void finish() {
+ this.finish = true;
+ }
+}
\ No newline at end of file
--- /dev/null
+package Analysis.Scheduling;\r
+\r
+import java.util.Queue;\r
+\r
+public class TransTaskSimulator extends TaskSimulator {\r
+ private int targetCoreNum;\r
+ private Queue<ObjectSimulator> newObjs;\r
+\r
+ public TransTaskSimulator(CoreSimulator cs, int targetCoreNum, Queue<ObjectSimulator> nobjs) {\r
+ super(null, cs);\r
+ this.targetCoreNum = targetCoreNum;\r
+ this.newObjs = nobjs;\r
+ }\r
+ \r
+ public void process() {\r
+ if(this.currentRun == null) {\r
+ this.currentRun = new ExeResult();\r
+ }\r
+\r
+ this.currentRun.finishTime = 1 * sizeof(this.newObjs.peek().getCd());\r
+ }\r
+ \r
+ public ObjectSimulator refreshTask() {\r
+ return this.newObjs.poll();\r
+ }\r
+ \r
+ private int sizeof(Object obj) {\r
+ return 1;\r
+ }\r
+\r
+ public boolean isFinished() {\r
+ return this.newObjs.isEmpty();\r
+ }\r
+\r
+ public int getTargetCoreNum() {\r
+ return targetCoreNum;\r
+ }\r
+}
\ No newline at end of file
// jzhou
private int executeTime;
private Hashtable<ClassDescriptor, NewObjInfo> newObjInfos;
+ private int probability;
+ private int invokeNum;
+ private int expInvokeNum;
public class NewObjInfo {
int newRate;
int probability;
+ FlagState root;
+ int invokeNum;
public NewObjInfo() {
newRate = 0;
probability = 0;
+ root = null;
+ invokeNum = 0;
}
public NewObjInfo(int newRate, int probability) {
this.probability = probability;
}
- public boolean equals(Object o) {
+ public FlagState getRoot() {
+ return root;
+ }
+
+ public void setRoot(FlagState root) {
+ this.root = root;
+ }
+
+ public int getInvokeNum() {
+ return invokeNum;
+ }
+
+ public void incInvokeNum() {
+ this.invokeNum++;
+ }
+
+ public boolean equals(Object o) {
if (o instanceof NewObjInfo) {
NewObjInfo e=(NewObjInfo)o;
if (e.newRate == this.newRate &&
- e.probability == this.probability) {
+ e.probability == this.probability &&
+ e.invokeNum == this.invokeNum &&
+ e.root.equals(this.root)) {
return true;
}
}
this.parameterindex=parameterindex;
this.executeTime = -1;
this.newObjInfos = null;
+ this.probability = -1;
+ this.invokeNum = 0;
+ this.expInvokeNum = 0;
}
-
+
+ public int getProbability() {
+ return probability;
+ }
+
+ public void setProbability(int probability) {
+ this.probability = probability;
+ }
+
public String getLabel() {
return label;
}
}
this.newObjInfos.put(cd, new NewObjInfo(newRate, probability));
}
+
+ public void process() {
+ this.invokeNum++;
+ }
+
+ public int getInvokeNum() {
+ return invokeNum;
+ }
+
+ public int getInvokeNumGap() {
+ return expInvokeNum - invokeNum;
+ }
+
+ public void setExpInvokeNum(int expInvokeNum) {
+ this.expInvokeNum = expInvokeNum;
+ }
+
}
package Analysis.TaskStateAnalysis;
-import Analysis.Scheduling.ClassNode;
+
import Analysis.TaskStateAnalysis.*;
import IR.*;
import IR.Tree.*;
// jzhou
private int executeTime;
+ private int invokeNum;
/** Class constructor
* Creates a new flagstate with all flags set to false.
this.uid=FlagState.nodeid++;
this.issourcenode=false;
this.executeTime = -1;
+ this.invokeNum = 0;
}
/** Class constructor
this.uid=FlagState.nodeid++;
this.issourcenode=false;
this.executeTime = -1;
+ this.invokeNum = 0;
}
public int getuid() {
}
return o;
}
+
+ public void init4Simulate() {
+ this.invokeNum = 0;
+ }
+
+ public FEdge process(TaskDescriptor td) {
+ FEdge next = null;
+ this.invokeNum++;
+ // refresh all the expInvokeNum of each edge
+ for(int i = 0; i < this.edges.size(); i++) {
+ next = (FEdge)this.edges.elementAt(i);
+ next.setExpInvokeNum((int)Math.round(this.invokeNum * (next.getProbability() / 100)));
+ }
+
+ // find the one with the biggest gap between its actual invoke time and the expected invoke time
+ // and associated with task td
+ int index = 0;
+ int gap = 0;
+ for(int i = 0; i < this.edges.size(); i++) {
+ int temp = ((FEdge)this.edges.elementAt(index)).getInvokeNumGap();
+ if((temp > gap) && (next.getTask().equals(td))){
+ index = i;
+ gap = temp;
+ }
+ }
+ next = (FEdge)this.edges.elementAt(index);
+ next.process();
+
+ return next;
+ }
}
*/
-private 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)
package Main;
+import java.io.FileOutputStream;
+import java.io.InputStream;
+import java.io.PrintStream;
import java.io.Reader;
import java.io.BufferedReader;
import java.io.FileReader;
import IR.State;
import IR.TaskDescriptor;
import IR.TypeUtil;
+import Analysis.Scheduling.Schedule;
import Analysis.Scheduling.ScheduleAnalysis;
import Analysis.Scheduling.ScheduleEdge;
import Analysis.Scheduling.ScheduleNode;
+import Analysis.Scheduling.ScheduleSimulator;
import Analysis.TaskStateAnalysis.TaskAnalysis;
import Analysis.TaskStateAnalysis.TaskTagAnalysis;
import Analysis.TaskStateAnalysis.TaskGraph;
}
if (state.SCHEDULING) {
+ // 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("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);
+
+ // 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.");
+
// for test
// Randomly set the newRate and probability of FEdges
java.util.Random r=new java.util.Random();
TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
Vector<FEdge> fev = (Vector<FEdge>)ta.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) {
+ do {
+ tint = r.nextInt()%total;
+ } while(tint <= 0);
+ }
+ pfe.setProbability(tint);
+ total -= tint;
+ }
do {
tint = r.nextInt()%10;
} while(tint <= 0);
}
}
+ // generate multiple schedulings
ScheduleAnalysis scheduleAnalysis = new ScheduleAnalysis(state, ta);
scheduleAnalysis.preSchedule();
+ scheduleAnalysis.scheduleAnalysis();
+ scheduleAnalysis.setCoreNum(scheduleAnalysis.getSEdges4Test().size());
+ scheduleAnalysis.schedule();
+
+ //simulate these schedulings
+ ScheduleSimulator scheduleSimulator = new ScheduleSimulator(scheduleAnalysis.getCoreNum(), state, ta);
+ Iterator it_scheduling = scheduleAnalysis.getSchedulingsIter();
+ int index = 0;
+ Vector<Integer> selectedScheduling = new Vector<Integer>();
+ int processTime = Integer.MAX_VALUE;
+ while(it_scheduling.hasNext()) {
+ Vector<Schedule> scheduling = (Vector<Schedule>)it_scheduling.next();
+ scheduleSimulator.setScheduling(scheduling);
+ int tmpTime = scheduleSimulator.process();
+ if(tmpTime < processTime) {
+ selectedScheduling.clear();
+ selectedScheduling.add(index);
+ processTime = tmpTime;
+ } else if(tmpTime == processTime) {
+ selectedScheduling.add(index);
+ }
+ index++;
+ }
+ 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) + ", ");
+ }
+ System.out.println();
+
+ /*ScheduleSimulator scheduleSimulator = new ScheduleSimulator(4, state, ta);
+ Vector<Schedule> scheduling = new Vector<Schedule>();
+ for(int i = 0; i < 4; i++) {
+ Schedule schedule = new Schedule(i);
+ scheduling.add(schedule);
+ }
+ Iterator it_tasks = state.getTaskSymbolTable().getAllDescriptorsIterator();
+ while(it_tasks.hasNext()) {
+ TaskDescriptor td = (TaskDescriptor)it_tasks.next();
+ if(td.getSymbol().equals("t10")) {
+ scheduling.elementAt(1).addTask(td);
+ } else {
+ scheduling.elementAt(0).addTask(td);
+ }
+ }
+ ClassDescriptor cd = (ClassDescriptor)state.getClassSymbolTable().get("E");
+ scheduling.elementAt(0).addTargetCore(cd, 1);
+ scheduleSimulator.setScheduling(scheduling);
+ scheduleSimulator.process();
- // Randomly set the newRate and probability of ScheduleEdges
- /*Vector<ScheduleEdge> sedges = scheduleAnalysis.getSEdges4Test();
- java.util.Random r=new java.util.Random();
- for(int i = 0; i < sedges.size(); i++) {
- ScheduleEdge temp = sedges.elementAt(i);
- int tint = 0;
- do {
- tint = r.nextInt()%100;
- }while(tint <= 0);
- temp.setProbability(tint);
- do {
- tint = r.nextInt()%10;
- } while(tint <= 0);
- temp.setNewRate(tint);
- //temp.setNewRate((i+1)%2+1);
- }
- //sedges.elementAt(3).setNewRate(2);*/
- scheduleAnalysis.scheduleAnalysis();
- scheduleAnalysis.setCoreNum(scheduleAnalysis.getSEdges4Test().size() - 1);
- scheduleAnalysis.schedule();
+ Vector<Schedule> scheduling1 = new Vector<Schedule>();
+ for(int i = 0; i < 4; i++) {
+ Schedule schedule = new Schedule(i);
+ scheduling1.add(schedule);
+ }
+ Iterator it_tasks1 = state.getTaskSymbolTable().getAllDescriptorsIterator();
+ while(it_tasks1.hasNext()) {
+ TaskDescriptor td = (TaskDescriptor)it_tasks1.next();
+ scheduling1.elementAt(0).addTask(td);
+ }
+ scheduleSimulator.setScheduling(scheduling1);
+ scheduleSimulator.process();*/
+
+ // Close the streams.
+ try {
+ stdout.close ();
+ System.setOut(origOut);
+ } catch (Exception e) {
+ origOut.println ("Redirect: Unable to close files!");
+ }
}
}
projects / IRC.git / commitdiff