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 }