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