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                             //Schedule schedule = this.scheduling.elementAt(coreNum);
 242                             for(int j = 0; j < nobjs.size(); j++) {
 243                                 ObjectSimulator nobj = nobjs.elementAt(j);
 244                                 action.addNewObj(nobj.getCd(), Integer.valueOf(1));
 245                                 // send the new object to target core according to pre-decide scheduling
 246                                 Queue<Integer> cores = cs.getTargetCores(nobj.getCurrentFS());
 247                                 if(cores == null) {
 248                                     // this obj will reside on this core
 249                                     cs.addObject(nobj);
 250                                 } else {
 251                                     Integer targetCore = cores.poll();
 252                                     if(targetCore == coreNum) {
 253                                         // this obj will reside on this core
 254                                         cs.addObject(nobj);
 255                                     } else {
 256                                         if(!transObjQueues.containsKey(targetCore)) {
 257                                             transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
 258                                         }
 259                                         Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
 260                                         tmpqueue.add(new ObjectInfo(nobj));
 261                                     }
 262                                     // enqueue this core again
 263                                     cores.add(targetCore);
 264                                 }
 265                                 // check if this object becoming shared or not
 266                                 Vector<Integer> allycores = cs.getAllyCores(nobj.getCurrentFS());
 267                                 if(allycores != null) {
 268                                     nobj.setShared(true);
 269                                     for(int k = 0; k < allycores.size(); ++k) {
 270                                         Integer allyCore = allycores.elementAt(k);
 271                                         if(allyCore == coreNum) {
 272                                             cs.addObject(nobj);
 273                                         } else {
 274                                             if(!transObjQueues.containsKey(allyCore)) {
 275                                                 transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
 276                                             }
 277                                             Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
 278                                             ObjectInfo nobjinfo = new ObjectInfo(nobj);
 279                                             if(!tmpqueue.contains(nobjinfo)) {
 280                                                 tmpqueue.add(nobjinfo);
 281                                             }
 282                                         }
 283                                     }
 284                                 }
 285                             }
 286                         }
 287                         cp.addAction(action);
 288                         Vector<ObjectSimulator> transObjs = cs.finishTask();
 289                         if(transObjs != null) {
 290                             for(int j = 0; j < transObjs.size(); j++) {
 291                                 ObjectSimulator tobj = transObjs.elementAt(j);
 292                                 // send the object to target core according to pre-decide scheduling
 293                                 Queue<Integer> cores = cs.getTargetCores(tobj.getCurrentFS());
 294                                 tobj.setCurrentFS(cs.getTargetFState(tobj.getCurrentFS()));
 295                                 if(cores == null) {
 296                                     // this obj will reside on this core
 297                                     cs.addObject(tobj);
 298                                 } else {
 299                                     Integer targetCore = cores.peek();
 300                                     if(targetCore == coreNum) {
 301                                         // this obj will reside on this core
 302                                         cs.addObject(tobj);
 303                                     } else {
 304                                         if(!transObjQueues.containsKey(targetCore)) {
 305                                             transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
 306                                         }
 307                                         Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
 308                                         tmpqueue.add(new ObjectInfo(tobj));
 309                                     }
 310                                 }
 311                                 // check if this object becoming shared or not
 312                                 Vector<Integer> allycores = cs.getAllyCores(tobj.getCurrentFS());
 313                                 if(allycores != null) {
 314                                     tobj.setShared(true);
 315                                     for(int k = 0; k < allycores.size(); ++k) {
 316                                         Integer allyCore = allycores.elementAt(k);
 317                                         if(allyCore == coreNum) {
 318                                             cs.addObject(tobj);
 319                                         } else {
 320                                             if(!transObjQueues.containsKey(allyCore)) {
 321                                                 transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
 322                                             }
 323                                             Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
 324                                             ObjectInfo nobjinfo = new ObjectInfo(tobj);
 325                                             if(!tmpqueue.contains(nobjinfo)) {
 326                                                 tmpqueue.add(nobjinfo);
 327                                             }
 328                                         }
 329                                     }
 330                                 }
 331                             }
 332                         }
 333                         // add 'transport' tasks
 334                         Iterator it_entries = transObjQueues.entrySet().iterator();
 335                         while(it_entries.hasNext()) {
 336                             Entry<Integer, Queue<ObjectInfo>> tmpentry = (Entry<Integer, Queue<ObjectInfo>>)it_entries.next();
 337                             Integer tmpCoreNum = tmpentry.getKey();
 338                             Queue<ObjectInfo> nobjs = tmpentry.getValue();
 339                             TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs);
 340                             this.tasks.add(tmptask);
 341                         }
 342                         // Choose a new task for this core
 343                         TaskSimulator newTask = cs.process();
 344                         if(newTask != null) {
 345                             this.tasks.add(newTask);
 346                             // add a TASKSTART action into this checkpoint
 347                             action = new Action(coreNum, Action.TASKSTART);
 348                             action.setTd(cs.getRtask().getTd());
 349                             cp.addAction(action);
 350                         }
 351                     } else if (task.getCurrentRun().getExetype() == 1) {
 352                         action = new Action(coreNum, Action.TASKABORT);
 353                         action.setTd(cs.getRtask().getTd());
 354                         cp.addAction(action);
 355                     } else if (task.getCurrentRun().getExetype() == 2) {
 356                         action = new Action(coreNum, Action.TASKREMOVE);
 357                         action.setTd(cs.getRtask().getTd());
 358                         cp.addAction(action);
 359                     }
 360                 }
 361             }
 362             this.checkpoints.add(cp);
 363         }
 364
 365         SchedulingUtil.printSimulationResult("SimulatorResult_" + this.invoketime + ".dot", this.processTime,
 366                 this.coreNum, this.checkpoints);
 367         System.out.println("Simulate scheduling #" + this.invoketime + ": ");
 368         System.out.println("\tTotal execution time is: " + this.processTime);
 369         System.out.println("\tUtility of cores: ");
 370         for(int j = 0; j < this.cores.size(); j++) {
 371             System.out.println("\t\tcore" + j + ": " + getUtility(j) + "%");
 372         }
 373         return this.processTime;
 374     }
 375
 376     public class CheckPoint {
 377         private int timepoint;
 378         private Vector<Action> actions;
 379
 380         public CheckPoint(int timepoint) {
 381             super();
 382             this.timepoint = timepoint;
 383             this.actions = new Vector<Action>();
 384         }
 385
 386         public Vector<Action> getActions() {
 387             return actions;
 388         }
 389
 390         public void addAction(Action action) {
 391             this.actions.add(action);
 392         }
 393
 394         public int getTimepoint() {
 395             return timepoint;
 396         }
 397     }
 398
 399     public class Action {
 400         public static final int ADDOBJ = 0;
 401         public static final int TASKFINISH = 1;
 402         public static final int TFWITHOBJ = 2;
 403         public static final int TASKSTART = 3;
 404         public static final int TASKABORT = 4;
 405         public static final int TASKREMOVE = 5;
 406
 407         private int coreNum;
 408         private int type;
 409         private TaskDescriptor td;
 410         private Hashtable<ClassDescriptor, Integer> nObjs;
 411         private int nObjNum;
 412         private ClassDescriptor transObj;
 413
 414         public Action(int coreNum, int type) {
 415             super();
 416             this.coreNum = coreNum;
 417             this.type = type;
 418             this.td = null;
 419             if(this.type == TFWITHOBJ) {
 420                 this.nObjs = new Hashtable<ClassDescriptor, Integer>();
 421             } else {
 422                 this.nObjs = null;
 423             }
 424             this.nObjNum = -1;
 425             this.transObj = null;
 426         }
 427
 428         public Action(int coreNum, int type, int objNum, ClassDescriptor transObj) {
 429             super();
 430             assert(type == ADDOBJ);
 431             this.coreNum = coreNum;
 432             this.type = type;
 433             this.td = null;
 434             this.nObjNum = objNum;
 435             this.transObj = transObj;
 436         }
 437
 438         public void addNewObj(ClassDescriptor cd, Integer num) {
 439             assert(this.type == TFWITHOBJ);
 440
 441             if(this.nObjs.containsKey(cd)) {
 442                 Integer sum = this.nObjs.get(cd) + num;
 443                 this.nObjs.put(cd, sum);
 444             } else {
 445                 this.nObjs.put(cd, num);
 446             }
 447         }
 448
 449         public int getCoreNum() {
 450             return coreNum;
 451         }
 452
 453         public int getType() {
 454             return type;
 455         }
 456
 457         public int getNObjNum() {
 458             return nObjNum;
 459         }
 460
 461         public ClassDescriptor getTransObj() {
 462             return transObj;
 463         }
 464
 465         public TaskDescriptor getTd() {
 466             return td;
 467         }
 468
 469         public void setTd(TaskDescriptor td) {
 470             this.td = td;
 471         }
 472
 473         public Hashtable<ClassDescriptor, Integer> getNObjs() {
 474             return nObjs;
 475         }
 476     }
 477
 478 }