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