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.poll();
 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.add(targetCore);
 319                 }
 320                 cores = null;
 321                 // check if this object becoming shared or not
 322                 Vector<Integer> allycores = cs.getAllyCores(tobj.getCurrentFS());
 323                 if(allycores != null) {
 324                   tobj.setShared(true);
 325                   for(int k = 0; k < allycores.size(); ++k) {
 326                     Integer allyCore = allycores.elementAt(k);
 327                     if(allyCore == coreNum) {
 328                       cs.addObject(tobj);
 329                     } else {
 330                       if(!transObjQueues.containsKey(allyCore)) {
 331                         transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
 332                       }
 333                       Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
 334                       ObjectInfo nobjinfo = new ObjectInfo(tobj);
 335                       if(!tmpqueue.contains(nobjinfo)) {
 336                         tmpqueue.add(nobjinfo);
 337                       }
 338                       tmpqueue = null;
 339                     }
 340                   }
 341                   allycores = null;
 342                 }
 343               }
 344               transObjs = null;
 345             }
 346             // add 'transport' tasks
 347             Iterator it_entries = transObjQueues.entrySet().iterator();
 348             while(it_entries.hasNext()) {
 349               Entry<Integer, Queue<ObjectInfo>> tmpentry = (Entry<Integer, Queue<ObjectInfo>>)it_entries.next();
 350               Integer tmpCoreNum = tmpentry.getKey();
 351               Queue<ObjectInfo> nobjs = tmpentry.getValue();
 352               TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs);
 353               this.tasks.add(tmptask);
 354               tmpentry = null;
 355               nobjs = null;
 356             }
 357             transObjQueues = null;
 358           } else if (task.getCurrentRun().getExetype() == 1) {
 359             action = new Action(coreNum, Action.TASKABORT);
 360             action.setTd(cs.getRtask().getTd());
 361             cp.addAction(action);
 362             Vector<ObjectSimulator> transObjs = cs.finishTask();
 363           } else if (task.getCurrentRun().getExetype() == 2) {
 364             action = new Action(coreNum, Action.TASKREMOVE);
 365             action.setTd(cs.getRtask().getTd());
 366             cp.addAction(action);
 367             Vector<ObjectSimulator> transObjs = cs.finishTask();
 368           }
 369           // Choose a new task for this core
 370           TaskSimulator newTask = cs.process();
 371           if(newTask != null) {
 372             this.tasks.add(newTask);
 373             // add a TASKSTART action into this checkpoint
 374             action = new Action(coreNum, Action.TASKSTART);
 375             action.setTd(cs.getRtask().getTd());
 376             cp.addAction(action);
 377           }
 378         }
 379       }
 380       this.checkpoints.add(cp);
 381       finishTasks = null;
 382     }
 383
 384     if(this.state.PRINTSCHEDULESIM) {
 385         SchedulingUtil.printSimulationResult("SimulatorResult_" + this.invoketime + ".dot", this.processTime,
 386                 this.coreNum, this.checkpoints);
 387     }
 388     System.out.println("Simulate scheduling #" + this.invoketime + ": ");
 389     System.out.println("\tTotal execution time is: " + this.processTime);
 390     System.out.println("\tUtility of cores: ");
 391     for(int j = 0; j < this.cores.size(); j++) {
 392       System.out.println("\t\tcore" + j + ": " + getUtility(j) + "%");
 393     }
 394
 395     this.checkpoints.clear();
 396     this.checkpoints = null;
 397     return this.processTime;
 398   }
 399
 400   public class CheckPoint {
 401     private int timepoint;
 402     private Vector<Action> actions;
 403
 404     public CheckPoint(int timepoint) {
 405       super();
 406       this.timepoint = timepoint;
 407       this.actions = new Vector<Action>();
 408     }
 409
 410     public Vector<Action> getActions() {
 411       return actions;
 412     }
 413
 414     public void addAction(Action action) {
 415       this.actions.add(action);
 416     }
 417
 418     public int getTimepoint() {
 419       return timepoint;
 420     }
 421   }
 422
 423   public class Action {
 424     public static final int ADDOBJ = 0;
 425     public static final int TASKFINISH = 1;
 426     public static final int TFWITHOBJ = 2;
 427     public static final int TASKSTART = 3;
 428     public static final int TASKABORT = 4;
 429     public static final int TASKREMOVE = 5;
 430
 431     private int coreNum;
 432     private int type;
 433     private TaskDescriptor td;
 434     private Hashtable<ClassDescriptor, Integer> nObjs;
 435     private int nObjNum;
 436     private ClassDescriptor transObj;
 437
 438     public Action(int coreNum, int type) {
 439       super();
 440       this.coreNum = coreNum;
 441       this.type = type;
 442       this.td = null;
 443       if(this.type == TFWITHOBJ) {
 444         this.nObjs = new Hashtable<ClassDescriptor, Integer>();
 445       } else {
 446         this.nObjs = null;
 447       }
 448       this.nObjNum = -1;
 449       this.transObj = null;
 450     }
 451
 452     public Action(int coreNum, int type, int objNum, ClassDescriptor transObj) {
 453       super();
 454       assert(type == ADDOBJ);
 455       this.coreNum = coreNum;
 456       this.type = type;
 457       this.td = null;
 458       this.nObjNum = objNum;
 459       this.transObj = transObj;
 460     }
 461
 462     public void addNewObj(ClassDescriptor cd, Integer num) {
 463       assert(this.type == TFWITHOBJ);
 464
 465       if(this.nObjs.containsKey(cd)) {
 466         Integer sum = this.nObjs.get(cd) + num;
 467         this.nObjs.put(cd, sum);
 468       } else {
 469         this.nObjs.put(cd, num);
 470       }
 471     }
 472
 473     public int getCoreNum() {
 474       return coreNum;
 475     }
 476
 477     public int getType() {
 478       return type;
 479     }
 480
 481     public int getNObjNum() {
 482       return nObjNum;
 483     }
 484
 485     public ClassDescriptor getTransObj() {
 486       return transObj;
 487     }
 488
 489     public TaskDescriptor getTd() {
 490       return td;
 491     }
 492
 493     public void setTd(TaskDescriptor td) {
 494       this.td = td;
 495     }
 496
 497     public Hashtable<ClassDescriptor, Integer> getNObjs() {
 498       return nObjs;
 499     }
 500   }
 501
 502 }