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         this.invoketime++;
 139
 140         if(this.checkpoints == null) {
 141             this.checkpoints = new Vector<CheckPoint>();
 142         } else {
 143             this.checkpoints.clear();
 144         }
 145
 146         this.processTime = 0;
 147
 148         // first decide next task to execute on each core
 149         int i = 0;
 150         for(i = 0; i < this.cores.size(); i++) {
 151             CoreSimulator cs = this.cores.elementAt(i);
 152             TaskSimulator task = cs.process();
 153             if(task != null) {
 154                 this.tasks.add(task);
 155             }
 156         }
 157
 158         // add STARTTASK checkpoint for all the initial tasks
 159         CheckPoint cp = new CheckPoint(this.processTime);
 160         for(i = 0; i < this.tasks.size(); i++) {
 161             TaskSimulator task = this.tasks.elementAt(i);
 162             Action action = new Action(task.getCs().getCoreNum(), Action.TASKSTART);
 163             action.setTd(task.getTd());
 164             cp.addAction(action);
 165         }
 166         this.checkpoints.add(cp);
 167
 168         while(true) {
 169             // if no more tasks on each core, simulation finish
 170             if(this.tasks.size() == 0) {
 171                 break;
 172             }
 173
 174             // for each task in todo queue, decide the execution path of this time
 175             // according to statistic information
 176             //int index = 0;  // indicate the task to finish first
 177             int finishTime = Integer.MAX_VALUE;
 178             Vector<TaskSimulator> finishTasks = new Vector<TaskSimulator>();
 179             for(i = 0; i < this.tasks.size(); i++) {
 180                 TaskSimulator task = this.tasks.elementAt(i);
 181                 task.process();
 182                 int tempTime = task.getCurrentRun().getFinishTime();
 183                 if(tempTime < finishTime) {
 184                     finishTime = tempTime;
 185                     finishTasks.clear();
 186                     finishTasks.add(task);
 187                 } else if (tempTime == finishTime) {
 188                     finishTasks.add(task);
 189                 }
 190             }
 191             for(i = 0; i < this.tasks.size(); i++) {
 192                 TaskSimulator task = this.tasks.elementAt(i);
 193                 if(!finishTasks.contains(task)) {
 194                     task.getCs().updateTask(finishTime);
 195                 }
 196             }
 197             this.processTime += finishTime;
 198             cp = new CheckPoint(this.processTime);
 199             Action action = null;
 200             for(i = 0; i < finishTasks.size(); i++) {
 201                 TaskSimulator task = finishTasks.elementAt(i);
 202                 this.tasks.removeElement(task);
 203                 if(task instanceof TransTaskSimulator) {
 204                     TransTaskSimulator tmptask = (TransTaskSimulator)task;
 205                     // add ADDOBJ task to targetCore
 206                     int targetCoreNum = tmptask.getTargetCoreNum();
 207                     ObjectSimulator nobj = tmptask.refreshTask();
 208                     this.cores.elementAt(targetCoreNum).addObject(nobj);
 209                     action = new Action(targetCoreNum, Action.ADDOBJ, 1, nobj.getCd());
 210                     cp.addAction(action);
 211                     if(!tmptask.isFinished()) {
 212                         // still have some objects to be transpotted
 213                         this.tasks.add(task);
 214                     }
 215                     if(this.cores.elementAt(targetCoreNum).getRtask() == null) {
 216                         TaskSimulator newTask = this.cores.elementAt(targetCoreNum).process();
 217                         if(newTask != null) {
 218                             this.tasks.add(newTask);
 219                             // add a TASKSTART action into this checkpoint
 220                             action = new Action(targetCoreNum, Action.TASKSTART);
 221                             action.setTd(newTask.getTd());
 222                             cp.addAction(action);
 223                         }
 224                     }
 225                 } else {
 226                     CoreSimulator cs = task.getCs();
 227                     int coreNum = cs.getCoreNum();
 228                     Hashtable<Integer, Queue<ObjectSimulator>> transObjQueues = new Hashtable<Integer, Queue<ObjectSimulator>>();
 229                     if(task.getCurrentRun().getNewObjs() == null) {
 230                         action = new Action(coreNum, Action.TASKFINISH);
 231                         action.setTd(cs.getRtask().getTd());
 232                     } else {
 233                         action = new Action(coreNum, Action.TFWITHOBJ);
 234                         action.setTd(cs.getRtask().getTd());
 235                         Vector<ObjectSimulator> nobjs = task.getCurrentRun().getNewObjs();
 236                         //Schedule schedule = this.scheduling.elementAt(coreNum);
 237                         for(int j = 0; j < nobjs.size(); j++) {
 238                             ObjectSimulator nobj = nobjs.elementAt(j);
 239                             action.addNewObj(nobj.getCd(), Integer.valueOf(1));
 240                             // send the new object to target core according to pre-decide scheduling
 241                             Queue<Integer> cores = cs.getTargetCores(nobj.getCurrentFS());
 242                             if(cores == null) {
 243                                 // this obj will reside on this core
 244                                 cs.addObject(nobj);
 245                             } else {
 246                                 Integer targetCore = cores.poll();
 247                                 if(targetCore == coreNum) {
 248                                     // this obj will reside on this core
 249                                     cs.addObject(nobj);
 250                                 } else {
 251                                     if(!transObjQueues.containsKey(targetCore)) {
 252                                         transObjQueues.put(targetCore, new LinkedList<ObjectSimulator>());
 253                                     }
 254                                     Queue<ObjectSimulator> tmpqueue = transObjQueues.get(targetCore);
 255                                     tmpqueue.add(nobj);
 256                                 }
 257                                 // enqueue this core again
 258                                 cores.add(targetCore);
 259                             }
 260                         }
 261                     }
 262                     cp.addAction(action);
 263                     Vector<ObjectSimulator> transObjs = cs.finishTask();
 264                     if(transObjs != null) {
 265                         for(int j = 0; j < transObjs.size(); j++) {
 266                             ObjectSimulator tobj = transObjs.elementAt(j);
 267                             // send the object to target core according to pre-decide scheduling
 268                             Queue<Integer> cores = cs.getTargetCores(tobj.getCurrentFS());
 269                             tobj.setCurrentFS(cs.getTargetFState(tobj.getCurrentFS()));
 270                             if(cores == null) {
 271                                 // this obj will reside on this core
 272                                 cs.addObject(tobj);
 273                             } else {
 274                                 Integer targetCore = cores.peek();
 275                                 if(targetCore == coreNum) {
 276                                     // this obj will reside on this core
 277                                     cs.addObject(tobj);
 278                                 } else {
 279                                     if(!transObjQueues.containsKey(targetCore)) {
 280                                         transObjQueues.put(targetCore, new LinkedList<ObjectSimulator>());
 281                                     }
 282                                     Queue<ObjectSimulator> tmpqueue = transObjQueues.get(targetCore);
 283                                     tmpqueue.add(tobj);
 284                                 }
 285                             }
 286                         }
 287                     }
 288                     // add 'transport' tasks
 289                     Iterator it_entries = transObjQueues.entrySet().iterator();
 290                     while(it_entries.hasNext()) {
 291                         Entry<Integer, Queue<ObjectSimulator>> tmpentry = (Entry<Integer, Queue<ObjectSimulator>>)it_entries.next();
 292                         Integer tmpCoreNum = tmpentry.getKey();
 293                         Queue<ObjectSimulator> nobjs = tmpentry.getValue();
 294                         TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs);
 295                         this.tasks.add(tmptask);
 296                     }
 297                     // Choose a new task for this core
 298                     TaskSimulator newTask = cs.process();
 299                     if(newTask != null) {
 300                         this.tasks.add(newTask);
 301                         // add a TASKSTART action into this checkpoint
 302                         action = new Action(coreNum, Action.TASKSTART);
 303                         action.setTd(cs.getRtask().getTd());
 304                         cp.addAction(action);
 305                     }
 306                 }
 307             }
 308             this.checkpoints.add(cp);
 309         }
 310
 311         SchedulingUtil.printSimulationResult("SimulatorResult_" + this.invoketime + ".dot", this.processTime,
 312                 this.coreNum, this.checkpoints);
 313         System.out.println("Simulate scheduling #" + this.invoketime + ": ");
 314         System.out.println("\tTotal execution time is: " + this.processTime);
 315         System.out.println("\tUtility of cores: ");
 316         for(int j = 0; j < this.cores.size(); j++) {
 317             System.out.println("\t\tcore" + j + ": " + getUtility(j) + "%");
 318         }
 319         return this.processTime;
 320     }
 321
 322     public class CheckPoint {
 323         private int timepoint;
 324         private Vector<Action> actions;
 325
 326         public CheckPoint(int timepoint) {
 327             super();
 328             this.timepoint = timepoint;
 329             this.actions = new Vector<Action>();
 330         }
 331
 332         public Vector<Action> getActions() {
 333             return actions;
 334         }
 335
 336         public void addAction(Action action) {
 337             this.actions.add(action);
 338         }
 339
 340         public int getTimepoint() {
 341             return timepoint;
 342         }
 343     }
 344
 345     public class Action {
 346         public static final int ADDOBJ = 0;
 347         public static final int TASKFINISH = 1;
 348         public static final int TFWITHOBJ = 2;
 349         public static final int TASKSTART = 3;
 350
 351         private int coreNum;
 352         private int type;
 353         private TaskDescriptor td;
 354         private Hashtable<ClassDescriptor, Integer> nObjs;
 355         private int nObjNum;
 356         private ClassDescriptor transObj;
 357
 358         public Action(int coreNum, int type) {
 359             super();
 360             this.coreNum = coreNum;
 361             this.type = type;
 362             this.td = null;
 363             if(this.type == TFWITHOBJ) {
 364                 this.nObjs = new Hashtable<ClassDescriptor, Integer>();
 365             } else {
 366                 this.nObjs = null;
 367             }
 368             this.nObjNum = -1;
 369             this.transObj = null;
 370         }
 371
 372         public Action(int coreNum, int type, int objNum, ClassDescriptor transObj) {
 373             super();
 374             assert(type == ADDOBJ);
 375             this.coreNum = coreNum;
 376             this.type = type;
 377             this.td = null;
 378             this.nObjNum = objNum;
 379             this.transObj = transObj;
 380         }
 381
 382         public void addNewObj(ClassDescriptor cd, Integer num) {
 383             assert(this.type == TFWITHOBJ);
 384
 385             if(this.nObjs.containsKey(cd)) {
 386                 Integer sum = this.nObjs.get(cd) + num;
 387                 this.nObjs.put(cd, sum);
 388             } else {
 389                 this.nObjs.put(cd, num);
 390             }
 391         }
 392
 393         public int getCoreNum() {
 394             return coreNum;
 395         }
 396
 397         public int getType() {
 398             return type;
 399         }
 400
 401         public int getNObjNum() {
 402             return nObjNum;
 403         }
 404
 405         public ClassDescriptor getTransObj() {
 406             return transObj;
 407         }
 408
 409         public TaskDescriptor getTd() {
 410             return td;
 411         }
 412
 413         public void setTd(TaskDescriptor td) {
 414             this.td = td;
 415         }
 416
 417         public Hashtable<ClassDescriptor, Integer> getNObjs() {
 418             return nObjs;
 419         }
 420     }
 421
 422 }