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