Robust/src/Analysis/Scheduling/ScheduleSimulator.java

   1 package Analysis.Scheduling;
   2
   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;
   9
  10 import Analysis.TaskStateAnalysis.FlagState;
  11 import Analysis.TaskStateAnalysis.TaskAnalysis;
  12 import IR.ClassDescriptor;
  13 import IR.State;
  14 import IR.TaskDescriptor;
  15 import IR.TypeUtil;
  16
  17 public class ScheduleSimulator {
  18     private int coreNum;
  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;
  25
  26     State state;
  27     TaskAnalysis taskanalysis;
  28
  29     public ScheduleSimulator(int coreNum, State state, TaskAnalysis taskanalysis) {
  30         super();
  31         this.coreNum = coreNum;
  32         this.scheduling = null;
  33         this.cores = null;
  34         this.tasks = null;
  35         this.checkpoints = null;
  36         this.processTime = 0;
  37         this.invoketime = 0;
  38         this.state = state;
  39         this.taskanalysis = taskanalysis;
  40     }
  41
  42     public ScheduleSimulator(int coreNum, Vector<Schedule> scheduling, State state, TaskAnalysis taskanalysis) {
  43         super();
  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));
  49         }
  50         this.tasks = new Vector<TaskSimulator>();
  51         this.checkpoints = null;
  52         this.processTime = 0;
  53         this.invoketime = 0;
  54         this.state = state;
  55         this.taskanalysis = taskanalysis;
  56         applyScheduling();
  57     }
  58
  59     public Vector<CheckPoint> getCheckpoints() {
  60         return checkpoints;
  61     }
  62
  63     public int getCoreNum() {
  64         return coreNum;
  65     }
  66
  67     public void setCoreNum(int coreNum) {
  68         this.coreNum = coreNum;
  69         if(this.cores != null) {
  70             this.cores.clear();
  71         }
  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));
  75         }
  76         if(this.scheduling != null) {
  77             applyScheduling();
  78         }
  79     }
  80
  81     public int getUtility(int index) {
  82         return (this.cores.elementAt(index).getActiveTime() * 100) / this.processTime;
  83     }
  84
  85     public Vector<Schedule> getScheduling() {
  86         return scheduling;
  87     }
  88
  89     public void setScheduling(Vector<Schedule> scheduling) {
  90         this.scheduling = scheduling;
  91         if(this.tasks == null) {
  92             this.tasks = new Vector<TaskSimulator>();
  93         } else {
  94             this.tasks.clear();
  95         }
  96         if(this.cores != null) {
  97             for(int i = 0; i < this.coreNum; i++) {
  98                 CoreSimulator core = this.cores.elementAt(i);
  99                 core.reset();
 100                 core.setRSchedule(FIFORSchedule.getFIFORSchedule());
 101             }
 102         } else {
 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));
 106             }
 107         }
 108
 109         applyScheduling();
 110     }
 111
 112     public void applyScheduling() {
 113         assert(this.state != null);
 114
 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());
 121         }
 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);
 128         }
 129     }
 130
 131     public Vector<TaskSimulator> getTasks() {
 132         return tasks;
 133     }
 134
 135     public int process() {
 136         assert(this.scheduling != null);
 137
 138         if(this.checkpoints == null) {
 139             this.checkpoints = new Vector<CheckPoint>();
 140         } else {
 141             this.checkpoints.clear();
 142         }
 143
 144         this.processTime = 0;
 145
 146         // first decide next task to execute on each core
 147         int i = 0;
 148         for(i = 0; i < this.cores.size(); i++) {
 149             CoreSimulator cs = this.cores.elementAt(i);
 150             TaskSimulator task = cs.process();
 151             if(task != null) {
 152                 this.tasks.add(task);
 153             }
 154         }
 155
 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);
 163         }
 164         this.checkpoints.add(cp);
 165
 166         while(true) {
 167             // if no more tasks on each core, simulation finish
 168             if(this.tasks.size() == 0) {
 169                 break;
 170             }
 171
 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);
 179                 task.process();
 180                 int tempTime = task.getCurrentRun().getFinishTime();
 181                 if(tempTime < finishTime) {
 182                     finishTime = tempTime;
 183                     finishTasks.clear();
 184                     finishTasks.add(task);
 185                 } else if (tempTime == finishTime) {
 186                     finishTasks.add(task);
 187                 }
 188             }
 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);
 193                 }
 194             }
 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);
 212                     }
 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);
 221                         }
 222                     }
 223                 } else {
 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());
 230                     } else {
 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());
 240                             if(cores == null) {
 241                                 // this obj will reside on this core
 242                                 cs.addObject(nobj);
 243                             } else {
 244                                 Integer targetCore = cores.poll();
 245                                 if(targetCore == coreNum) {
 246                                     // this obj will reside on this core
 247                                     cs.addObject(nobj);
 248                                 } else {
 249                                     if(!transObjQueues.containsKey(targetCore)) {
 250                                         transObjQueues.put(targetCore, new LinkedList<ObjectSimulator>());
 251                                     }
 252                                     Queue<ObjectSimulator> tmpqueue = transObjQueues.get(targetCore);
 253                                     tmpqueue.add(nobj);
 254                                 }
 255                                 // enqueue this core again
 256                                 cores.add(targetCore);
 257                             }
 258                         }
 259                     }
 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()));
 268                             if(cores == null) {
 269                                 // this obj will reside on this core
 270                                 cs.addObject(tobj);
 271                             } else {
 272                                 Integer targetCore = cores.peek();
 273                                 if(targetCore == coreNum) {
 274                                     // this obj will reside on this core
 275                                     cs.addObject(tobj);
 276                                 } else {
 277                                     if(!transObjQueues.containsKey(targetCore)) {
 278                                         transObjQueues.put(targetCore, new LinkedList<ObjectSimulator>());
 279                                     }
 280                                     Queue<ObjectSimulator> tmpqueue = transObjQueues.get(targetCore);
 281                                     tmpqueue.add(tobj);
 282                                 }
 283                             }
 284                         }
 285                     }
 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);
 294                     }
 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);
 303                     }
 304                 }
 305             }
 306             this.checkpoints.add(cp);
 307         }
 308
 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) + "%");
 316         }
 317         this.invoketime++;
 318         return this.processTime;
 319     }
 320
 321     public class CheckPoint {
 322         private int timepoint;
 323         private Vector<Action> actions;
 324
 325         public CheckPoint(int timepoint) {
 326             super();
 327             this.timepoint = timepoint;
 328             this.actions = new Vector<Action>();
 329         }
 330
 331         public Vector<Action> getActions() {
 332             return actions;
 333         }
 334
 335         public void addAction(Action action) {
 336             this.actions.add(action);
 337         }
 338
 339         public int getTimepoint() {
 340             return timepoint;
 341         }
 342     }
 343
 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;
 349
 350         private int coreNum;
 351         private int type;
 352         private TaskDescriptor td;
 353         private Hashtable<ClassDescriptor, Integer> nObjs;
 354         private int nObjNum;
 355         private ClassDescriptor transObj;
 356
 357         public Action(int coreNum, int type) {
 358             super();
 359             this.coreNum = coreNum;
 360             this.type = type;
 361             this.td = null;
 362             if(this.type == TFWITHOBJ) {
 363                 this.nObjs = new Hashtable<ClassDescriptor, Integer>();
 364             } else {
 365                 this.nObjs = null;
 366             }
 367             this.nObjNum = -1;
 368             this.transObj = null;
 369         }
 370
 371         public Action(int coreNum, int type, int objNum, ClassDescriptor transObj) {
 372             super();
 373             assert(type == ADDOBJ);
 374             this.coreNum = coreNum;
 375             this.type = type;
 376             this.td = null;
 377             this.nObjNum = objNum;
 378             this.transObj = transObj;
 379         }
 380
 381         public void addNewObj(ClassDescriptor cd, Integer num) {
 382             assert(this.type == TFWITHOBJ);
 383
 384             if(this.nObjs.containsKey(cd)) {
 385                 Integer sum = this.nObjs.get(cd) + num;
 386                 this.nObjs.put(cd, sum);
 387             } else {
 388                 this.nObjs.put(cd, num);
 389             }
 390         }
 391
 392         public int getCoreNum() {
 393             return coreNum;
 394         }
 395
 396         public int getType() {
 397             return type;
 398         }
 399
 400         public int getNObjNum() {
 401             return nObjNum;
 402         }
 403
 404         public ClassDescriptor getTransObj() {
 405             return transObj;
 406         }
 407
 408         public TaskDescriptor getTd() {
 409             return td;
 410         }
 411
 412         public void setTd(TaskDescriptor td) {
 413             this.td = td;
 414         }
 415
 416         public Hashtable<ClassDescriptor, Integer> getNObjs() {
 417             return nObjs;
 418         }
 419     }
 420
 421 }