1 package Analysis.Scheduling;
3 import java.util.Hashtable;
4 import java.util.Iterator;
5 import java.util.LinkedList;
6 import java.util.Queue;
7 import java.util.Vector;
8 import java.util.Map.Entry;
10 import Analysis.TaskStateAnalysis.FlagState;
11 import Analysis.TaskStateAnalysis.TaskAnalysis;
12 import IR.ClassDescriptor;
14 import IR.TaskDescriptor;
17 public class ScheduleSimulator {
19 private Vector<Schedule> scheduling;
20 private Vector<CoreSimulator> cores;
21 private Vector<TaskSimulator> tasks;
22 private Vector<CheckPoint> checkpoints;
23 private int processTime;
24 private int invoketime;
27 TaskAnalysis taskanalysis;
29 public ScheduleSimulator(int coreNum, State state, TaskAnalysis taskanalysis) {
31 this.coreNum = coreNum;
32 this.scheduling = null;
35 this.checkpoints = null;
39 this.taskanalysis = taskanalysis;
42 public ScheduleSimulator(int coreNum, Vector<Schedule> scheduling, State state, TaskAnalysis taskanalysis) {
44 this.coreNum = coreNum;
45 this.scheduling = scheduling;
46 this.cores = new Vector<CoreSimulator>(this.coreNum);
47 for(int i = 0; i < this.coreNum; i++) {
48 this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
50 this.tasks = new Vector<TaskSimulator>();
51 this.checkpoints = null;
55 this.taskanalysis = taskanalysis;
59 public Vector<CheckPoint> getCheckpoints() {
63 public int getCoreNum() {
67 public void setCoreNum(int coreNum) {
68 this.coreNum = coreNum;
69 if(this.cores != null) {
72 this.cores = new Vector<CoreSimulator>(this.coreNum);
73 for(int i = 0; i < this.coreNum; i++) {
74 this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
76 if(this.scheduling != null) {
81 public int getUtility(int index) {
82 return (this.cores.elementAt(index).getActiveTime() * 100) / this.processTime;
85 public Vector<Schedule> getScheduling() {
89 public void setScheduling(Vector<Schedule> scheduling) {
90 this.scheduling = scheduling;
91 if(this.tasks == null) {
92 this.tasks = new Vector<TaskSimulator>();
96 if(this.cores != null) {
97 for(int i = 0; i < this.coreNum; i++) {
98 CoreSimulator core = this.cores.elementAt(i);
100 core.setRSchedule(FIFORSchedule.getFIFORSchedule());
103 this.cores = new Vector<CoreSimulator>(this.coreNum);
104 for(int i = 0; i < this.coreNum; i++) {
105 this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
112 public void applyScheduling() {
113 assert(this.state != null);
115 for(int i = 0; i < this.scheduling.size(); i++) {
116 Schedule temp = this.scheduling.elementAt(i);
117 CoreSimulator cs = this.cores.elementAt(temp.getCoreNum());
118 cs.deployTasks(temp.getTasks());
119 cs.setTargetCSimulator(temp.getTargetCoreTable());
120 cs.setTargetFState(temp.getTargetFStateTable());
122 // inject a Startup Object to each core
123 for(int i = 0; i < this.coreNum; i++) {
124 ClassDescriptor startupobject=(ClassDescriptor)state.getClassSymbolTable().get(TypeUtil.StartupClass);
125 FlagState fsstartup = (FlagState)taskanalysis.getRootNodes(startupobject).elementAt(0);
126 ObjectSimulator newObj = new ObjectSimulator(startupobject, fsstartup);
127 this.cores.elementAt(i).addObject(newObj);
131 public Vector<TaskSimulator> getTasks() {
135 public int process() {
136 assert(this.scheduling != null);
138 if(this.checkpoints == null) {
139 this.checkpoints = new Vector<CheckPoint>();
141 this.checkpoints.clear();
144 this.processTime = 0;
146 // first decide next task to execute on each core
148 for(i = 0; i < this.cores.size(); i++) {
149 CoreSimulator cs = this.cores.elementAt(i);
150 TaskSimulator task = cs.process();
152 this.tasks.add(task);
156 // add STARTTASK checkpoint for all the initial tasks
157 CheckPoint cp = new CheckPoint(this.processTime);
158 for(i = 0; i < this.tasks.size(); i++) {
159 TaskSimulator task = this.tasks.elementAt(i);
160 Action action = new Action(task.getCs().getCoreNum(), Action.TASKSTART);
161 action.setTd(task.getTd());
162 cp.addAction(action);
164 this.checkpoints.add(cp);
167 // if no more tasks on each core, simulation finish
168 if(this.tasks.size() == 0) {
172 // for each task in todo queue, decide the execution path of this time
173 // according to statistic information
174 //int index = 0; // indicate the task to finish first
175 int finishTime = Integer.MAX_VALUE;
176 Vector<TaskSimulator> finishTasks = new Vector<TaskSimulator>();
177 for(i = 0; i < this.tasks.size(); i++) {
178 TaskSimulator task = this.tasks.elementAt(i);
180 int tempTime = task.getCurrentRun().getFinishTime();
181 if(tempTime < finishTime) {
182 finishTime = tempTime;
184 finishTasks.add(task);
185 } else if (tempTime == finishTime) {
186 finishTasks.add(task);
189 for(i = 0; i < this.tasks.size(); i++) {
190 TaskSimulator task = this.tasks.elementAt(i);
191 if(!finishTasks.contains(task)) {
192 task.getCs().updateTask(finishTime);
195 this.processTime += finishTime;
196 cp = new CheckPoint(this.processTime);
197 Action action = null;
198 for(i = 0; i < finishTasks.size(); i++) {
199 TaskSimulator task = finishTasks.elementAt(i);
200 this.tasks.removeElement(task);
201 if(task instanceof TransTaskSimulator) {
202 TransTaskSimulator tmptask = (TransTaskSimulator)task;
203 // add ADDOBJ task to targetCore
204 int targetCoreNum = tmptask.getTargetCoreNum();
205 ObjectSimulator nobj = tmptask.refreshTask();
206 this.cores.elementAt(targetCoreNum).addObject(nobj);
207 action = new Action(targetCoreNum, Action.ADDOBJ, 1, nobj.getCd());
208 cp.addAction(action);
209 if(!tmptask.isFinished()) {
210 // still have some objects to be transpotted
211 this.tasks.add(task);
213 if(this.cores.elementAt(targetCoreNum).getRtask() == null) {
214 TaskSimulator newTask = this.cores.elementAt(targetCoreNum).process();
215 if(newTask != null) {
216 this.tasks.add(newTask);
217 // add a TASKSTART action into this checkpoint
218 action = new Action(targetCoreNum, Action.TASKSTART);
219 action.setTd(newTask.getTd());
220 cp.addAction(action);
224 CoreSimulator cs = task.getCs();
225 int coreNum = cs.getCoreNum();
226 Hashtable<Integer, Queue<ObjectSimulator>> transObjQueues = new Hashtable<Integer, Queue<ObjectSimulator>>();
227 if(task.getCurrentRun().getNewObjs() == null) {
228 action = new Action(coreNum, Action.TASKFINISH);
229 action.setTd(cs.getRtask().getTd());
231 action = new Action(coreNum, Action.TFWITHOBJ);
232 action.setTd(cs.getRtask().getTd());
233 Vector<ObjectSimulator> nobjs = task.getCurrentRun().getNewObjs();
234 //Schedule schedule = this.scheduling.elementAt(coreNum);
235 for(int j = 0; j < nobjs.size(); j++) {
236 ObjectSimulator nobj = nobjs.elementAt(j);
237 action.addNewObj(nobj.getCd(), Integer.valueOf(1));
238 // send the new object to target core according to pre-decide scheduling
239 Queue<Integer> cores = cs.getTargetCores(nobj.getCurrentFS());
241 // this obj will reside on this core
244 Integer targetCore = cores.poll();
245 if(targetCore == coreNum) {
246 // this obj will reside on this core
249 if(!transObjQueues.containsKey(targetCore)) {
250 transObjQueues.put(targetCore, new LinkedList<ObjectSimulator>());
252 Queue<ObjectSimulator> tmpqueue = transObjQueues.get(targetCore);
255 // enqueue this core again
256 cores.add(targetCore);
260 cp.addAction(action);
261 Vector<ObjectSimulator> transObjs = cs.finishTask();
262 if(transObjs != null) {
263 for(int j = 0; j < transObjs.size(); j++) {
264 ObjectSimulator tobj = transObjs.elementAt(j);
265 // send the object to target core according to pre-decide scheduling
266 Queue<Integer> cores = cs.getTargetCores(tobj.getCurrentFS());
267 tobj.setCurrentFS(cs.getTargetFState(tobj.getCurrentFS()));
269 // this obj will reside on this core
272 Integer targetCore = cores.peek();
273 if(targetCore == coreNum) {
274 // this obj will reside on this core
277 if(!transObjQueues.containsKey(targetCore)) {
278 transObjQueues.put(targetCore, new LinkedList<ObjectSimulator>());
280 Queue<ObjectSimulator> tmpqueue = transObjQueues.get(targetCore);
286 // add 'transport' tasks
287 Iterator it_entries = transObjQueues.entrySet().iterator();
288 while(it_entries.hasNext()) {
289 Entry<Integer, Queue<ObjectSimulator>> tmpentry = (Entry<Integer, Queue<ObjectSimulator>>)it_entries.next();
290 Integer tmpCoreNum = tmpentry.getKey();
291 Queue<ObjectSimulator> nobjs = tmpentry.getValue();
292 TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs);
293 this.tasks.add(tmptask);
295 // Choose a new task for this core
296 TaskSimulator newTask = cs.process();
297 if(newTask != null) {
298 this.tasks.add(newTask);
299 // add a TASKSTART action into this checkpoint
300 action = new Action(coreNum, Action.TASKSTART);
301 action.setTd(cs.getRtask().getTd());
302 cp.addAction(action);
306 this.checkpoints.add(cp);
309 SchedulingUtil.printSimulationResult("SimulatorResult_" + this.invoketime + ".dot", this.processTime,
310 this.coreNum, this.checkpoints);
311 System.out.println("Simulate scheduling #" + this.invoketime + ": ");
312 System.out.println("\tTotal execution time is: " + this.processTime);
313 System.out.println("\tUtility of cores: ");
314 for(int j = 0; j < this.cores.size(); j++) {
315 System.out.println("\t\tcore" + j + ": " + getUtility(j) + "%");
318 return this.processTime;
321 public class CheckPoint {
322 private int timepoint;
323 private Vector<Action> actions;
325 public CheckPoint(int timepoint) {
327 this.timepoint = timepoint;
328 this.actions = new Vector<Action>();
331 public Vector<Action> getActions() {
335 public void addAction(Action action) {
336 this.actions.add(action);
339 public int getTimepoint() {
344 public class Action {
345 public static final int ADDOBJ = 0;
346 public static final int TASKFINISH = 1;
347 public static final int TFWITHOBJ = 2;
348 public static final int TASKSTART = 3;
352 private TaskDescriptor td;
353 private Hashtable<ClassDescriptor, Integer> nObjs;
355 private ClassDescriptor transObj;
357 public Action(int coreNum, int type) {
359 this.coreNum = coreNum;
362 if(this.type == TFWITHOBJ) {
363 this.nObjs = new Hashtable<ClassDescriptor, Integer>();
368 this.transObj = null;
371 public Action(int coreNum, int type, int objNum, ClassDescriptor transObj) {
373 assert(type == ADDOBJ);
374 this.coreNum = coreNum;
377 this.nObjNum = objNum;
378 this.transObj = transObj;
381 public void addNewObj(ClassDescriptor cd, Integer num) {
382 assert(this.type == TFWITHOBJ);
384 if(this.nObjs.containsKey(cd)) {
385 Integer sum = this.nObjs.get(cd) + num;
386 this.nObjs.put(cd, sum);
388 this.nObjs.put(cd, num);
392 public int getCoreNum() {
396 public int getType() {
400 public int getNObjNum() {
404 public ClassDescriptor getTransObj() {
408 public TaskDescriptor getTd() {
412 public void setTd(TaskDescriptor td) {
416 public Hashtable<ClassDescriptor, Integer> getNObjs() {