Robust/src/Analysis/Scheduling/ScheduleSimulator.java

   1 package Analysis.Scheduling;
   2
   3 import java.io.FileOutputStream;
   4 import java.io.PrintStream;
   5 import java.util.Hashtable;
   6 import java.util.Iterator;
   7 import java.util.LinkedList;
   8 import java.util.Queue;
   9 import java.util.Vector;
  10 import java.util.Map.Entry;
  11
  12 import Analysis.TaskStateAnalysis.FlagState;
  13 import Analysis.TaskStateAnalysis.TaskAnalysis;
  14 import IR.ClassDescriptor;
  15 import IR.State;
  16 import IR.TaskDescriptor;
  17 import IR.TypeUtil;
  18
  19 public class ScheduleSimulator {
  20   private int coreNum;
  21   private Vector<Schedule> scheduling;
  22   private Vector<CoreSimulator> cores;
  23   private Vector<TaskSimulator> tasks;
  24   private Vector<CheckPoint> checkpoints;
  25   private int processTime;
  26   private int invoketime;
  27
  28   State state;
  29   TaskAnalysis taskanalysis;
  30
  31   public ScheduleSimulator(int coreNum, State state, TaskAnalysis taskanalysis) {
  32     super();
  33     this.coreNum = coreNum;
  34     this.scheduling = null;
  35     this.cores = null;
  36     this.tasks = null;
  37     this.checkpoints = null;
  38     this.processTime = 0;
  39     this.invoketime = 0;
  40     this.state = state;
  41     this.taskanalysis = taskanalysis;
  42   }
  43
  44   public ScheduleSimulator(int coreNum, Vector<Schedule> scheduling, State state, TaskAnalysis taskanalysis) {
  45     super();
  46     this.coreNum = coreNum;
  47     this.scheduling = scheduling;
  48     this.cores = new Vector<CoreSimulator>(this.coreNum);
  49     for(int i = 0; i < this.coreNum; i++) {
  50       this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
  51     }
  52     this.tasks = new Vector<TaskSimulator>();
  53     this.checkpoints = null;
  54     this.processTime = 0;
  55     this.invoketime = 0;
  56     this.state = state;
  57     this.taskanalysis = taskanalysis;
  58     applyScheduling();
  59   }
  60
  61   public Vector<Integer> simulate(Vector<Vector<Schedule>> schedulings) {
  62       // Print stuff to the original output and error streams.
  63       // The stuff printed through the 'origOut' and 'origErr' references
  64       // should go to the console on most systems while the messages
  65       // printed through the 'System.out' and 'System.err' will end up in
  66       // the files we created for them.
  67       //origOut.println ("\nRedirect:  Round #2");
  68       //System.out.println ("Test output via 'SimulatorResult.out'.");
  69       //origOut.println ("Test output via 'origOut' reference.");
  70
  71       // Save the current standard input, output, and error streams
  72       // for later restoration.
  73       PrintStream origOut = System.out;
  74
  75       // Create a new output stream for the standard output.
  76       PrintStream stdout  = null;
  77       try {
  78           stdout = new PrintStream(new FileOutputStream("/scratch/SimulatorResult.out"));
  79       } catch (Exception e) {
  80           // Sigh.  Couldn't open the file.
  81           System.out.println("Redirect:  Unable to open output file!");
  82           System.exit(1);
  83       }
  84
  85       // Print stuff to the original output and error streams.
  86       // On most systems all of this will end up on your console when you
  87       // run this application.
  88       //origOut.println ("\nRedirect:  Round #1");
  89       //System.out.println ("Test output via 'System.out'.");
  90       //origOut.println ("Test output via 'origOut' reference.");
  91
  92       // Set the System out and err streams to use our replacements.
  93       System.setOut(stdout);
  94
  95       Vector<Integer> selectedScheduling = new Vector<Integer>();
  96       int processTime = Integer.MAX_VALUE;
  97       if(schedulings.size() > 1500) {
  98           int index = 0;
  99           int upperbound = schedulings.size();
 100           long seed = 0;
 101           java.util.Random r = new java.util.Random(seed);
 102           for(int ii = 0; ii < 1500; ii++) {
 103               index = (int)((Math.abs((double)r.nextInt() / (double)Integer.MAX_VALUE)) * upperbound);
 104               System.out.println("Scheduling index:" + index);
 105               //System.err.println("Scheduling index:" + index);
 106               Vector<Schedule> scheduling = schedulings.elementAt(index);
 107               this.setScheduling(scheduling);
 108               int tmpTime = this.process();
 109               if(tmpTime < processTime) {
 110                   selectedScheduling.clear();
 111                   selectedScheduling.add(index);
 112                   processTime = tmpTime;
 113               } else if(tmpTime == processTime) {
 114                   selectedScheduling.add(index);
 115               }
 116               scheduling = null;
 117           }
 118       } else {
 119           Iterator it_scheduling = schedulings.iterator();
 120           int index = 0;
 121           while(it_scheduling.hasNext()) {
 122               Vector<Schedule> scheduling = (Vector<Schedule>)it_scheduling.next();
 123               this.setScheduling(scheduling);
 124               int tmpTime = this.process();
 125               if(tmpTime < processTime) {
 126                   selectedScheduling.clear();
 127                   selectedScheduling.add(index);
 128                   processTime = tmpTime;
 129               } else if(tmpTime == processTime) {
 130                   selectedScheduling.add(index);
 131               }
 132               scheduling = null;
 133               index++;
 134           }
 135       }
 136
 137       System.out.print("Selected schedulings with least exectution time " + processTime + ": \n\t");
 138       for(int i = 0; i < selectedScheduling.size(); i++) {
 139           System.out.print((selectedScheduling.elementAt(i) + 1) + ", ");
 140       }
 141       System.out.println();
 142
 143       // Close the streams.
 144       try {
 145           stdout.close();
 146           System.setOut(origOut);
 147       } catch (Exception e) {
 148           origOut.println("Redirect:  Unable to close files!");
 149       }
 150
 151       return selectedScheduling;
 152   }
 153
 154   public Vector<CheckPoint> getCheckpoints() {
 155     return checkpoints;
 156   }
 157
 158   public int getCoreNum() {
 159     return coreNum;
 160   }
 161
 162   public void setCoreNum(int coreNum) {
 163     this.coreNum = coreNum;
 164     if(this.cores != null) {
 165       this.cores.clear();
 166     }
 167     this.cores = new Vector<CoreSimulator>(this.coreNum);
 168     for(int i = 0; i < this.coreNum; i++) {
 169       this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
 170     }
 171     if(this.scheduling != null) {
 172       applyScheduling();
 173     }
 174   }
 175
 176   public int getUtility(int index) {
 177     return (this.cores.elementAt(index).getActiveTime() * 100) / this.processTime;
 178   }
 179
 180   public Vector<Schedule> getScheduling() {
 181     return scheduling;
 182   }
 183
 184   public void setScheduling(Vector<Schedule> scheduling) {
 185     this.scheduling = scheduling;
 186     if(this.tasks == null) {
 187       this.tasks = new Vector<TaskSimulator>();
 188     } else {
 189       this.tasks.clear();
 190     }
 191     if(this.cores != null) {
 192       for(int i = 0; i < this.coreNum; i++) {
 193         CoreSimulator core = this.cores.elementAt(i);
 194         core.reset();
 195         core.setRSchedule(FIFORSchedule.getFIFORSchedule());
 196       }
 197     } else {
 198       this.cores = new Vector<CoreSimulator>(this.coreNum);
 199       for(int i = 0; i < this.coreNum; i++) {
 200         this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
 201       }
 202     }
 203     if(this.checkpoints != null) {
 204         this.checkpoints.clear();
 205     }
 206
 207     applyScheduling();
 208   }
 209
 210   public void applyScheduling() {
 211     assert(this.state != null);
 212
 213     for(int i = 0; i < this.scheduling.size(); i++) {
 214       Schedule temp = this.scheduling.elementAt(i);
 215       CoreSimulator cs = this.cores.elementAt(temp.getCoreNum());
 216       cs.deployTasks(temp.getTasks());
 217       cs.setTargetCSimulator(temp.getTargetCoreTable());
 218       cs.setAllyCSimulator(temp.getAllyCoreTable());
 219       cs.setTargetFState(temp.getTargetFStateTable());
 220     }
 221     // inject a Startup Object to each core
 222     for(int i = 0; i < this.coreNum; i++) {
 223       ClassDescriptor startupobject=(ClassDescriptor)state.getClassSymbolTable().get(TypeUtil.StartupClass);
 224       FlagState fsstartup = (FlagState)taskanalysis.getRootNodes(startupobject).elementAt(0);
 225       ObjectSimulator newObj = new ObjectSimulator(startupobject, fsstartup);
 226       this.cores.elementAt(i).addObject(newObj);
 227     }
 228   }
 229
 230   public Vector<TaskSimulator> getTasks() {
 231     return tasks;
 232   }
 233
 234   public int process() {
 235     assert(this.scheduling != null);
 236
 237     this.invoketime++;
 238
 239     if(this.checkpoints == null) {
 240       this.checkpoints = new Vector<CheckPoint>();
 241     } /*else {
 242       this.checkpoints.clear();
 243     }*/
 244
 245     this.processTime = 0;
 246
 247     // first decide next task to execute on each core
 248     int i = 0;
 249     for(i = 0; i < this.cores.size(); i++) {
 250       CoreSimulator cs = this.cores.elementAt(i);
 251       TaskSimulator task = cs.process();
 252       if(task != null) {
 253         this.tasks.add(task);
 254       }
 255     }
 256
 257     // add STARTTASK checkpoint for all the initial tasks
 258     CheckPoint cp = new CheckPoint(this.processTime);
 259     for(i = 0; i < this.tasks.size(); i++) {
 260       TaskSimulator task = this.tasks.elementAt(i);
 261       Action action = new Action(task.getCs().getCoreNum(), Action.TASKSTART);
 262       action.setTd(task.getTd());
 263       cp.addAction(action);
 264     }
 265     this.checkpoints.add(cp);
 266
 267     while(true) {
 268       // if no more tasks on each core, simulation finish
 269       if(this.tasks.size() == 0) {
 270         break;
 271       }
 272
 273       // for each task in todo queue, decide the execution path of this time
 274       // according to statistic information
 275       //int index = 0;  // indicate the task to finish first
 276       int finishTime = Integer.MAX_VALUE;
 277       Vector<TaskSimulator> finishTasks = new Vector<TaskSimulator>();
 278       for(i = 0; i < this.tasks.size(); i++) {
 279         TaskSimulator task = this.tasks.elementAt(i);
 280         task.process();
 281         int tempTime = task.getCurrentRun().getFinishTime();
 282         if(tempTime < finishTime) {
 283           finishTime = tempTime;
 284           finishTasks.clear();
 285           finishTasks.add(task);
 286         } else if (tempTime == finishTime) {
 287           finishTasks.add(task);
 288         }
 289       }
 290       for(i = 0; i < this.tasks.size(); i++) {
 291         TaskSimulator task = this.tasks.elementAt(i);
 292         if(!finishTasks.contains(task)) {
 293           task.getCs().updateTask(finishTime);
 294         }
 295       }
 296       this.processTime += finishTime;
 297       cp = new CheckPoint(this.processTime);
 298       Action action = null;
 299       for(i = 0; i < finishTasks.size(); i++) {
 300         TaskSimulator task = finishTasks.elementAt(i);
 301         this.tasks.removeElement(task);
 302         if(task instanceof TransTaskSimulator) {
 303           TransTaskSimulator tmptask = (TransTaskSimulator)task;
 304           // add ADDOBJ task to targetCore
 305           int targetCoreNum = tmptask.getTargetCoreNum();
 306           ObjectInfo objinfo = tmptask.refreshTask();
 307           ObjectSimulator nobj = objinfo.obj;
 308           FlagState fs = objinfo.fs;
 309           int version = objinfo.version;
 310           this.cores.elementAt(targetCoreNum).addObject(nobj, fs, version);
 311           action = new Action(targetCoreNum, Action.ADDOBJ, 1, nobj.getCd());
 312           cp.addAction(action);
 313           if(!tmptask.isFinished()) {
 314             // still have some objects to be transpotted
 315             this.tasks.add(task);
 316           }
 317           if(this.cores.elementAt(targetCoreNum).getRtask() == null) {
 318             TaskSimulator newTask = this.cores.elementAt(targetCoreNum).process();
 319             if(newTask != null) {
 320               this.tasks.add(newTask);
 321               // add a TASKSTART action into this checkpoint
 322               action = new Action(targetCoreNum, Action.TASKSTART);
 323               action.setTd(newTask.getTd());
 324               cp.addAction(action);
 325             }
 326           }
 327         } else {
 328           CoreSimulator cs = task.getCs();
 329           int coreNum = cs.getCoreNum();
 330           if(task.getCurrentRun().getExetype() == 0) {
 331             Hashtable<Integer, Queue<ObjectInfo>> transObjQueues = new Hashtable<Integer, Queue<ObjectInfo>>();
 332             if(task.getCurrentRun().getNewObjs() == null) {
 333               action = new Action(coreNum, Action.TASKFINISH);
 334               action.setTd(cs.getRtask().getTd());
 335             } else {
 336               action = new Action(coreNum, Action.TFWITHOBJ);
 337               action.setTd(cs.getRtask().getTd());
 338               Vector<ObjectSimulator> nobjs = task.getCurrentRun().getNewObjs();
 339               for(int j = 0; j < nobjs.size(); j++) {
 340                 ObjectSimulator nobj = nobjs.elementAt(j);
 341                 action.addNewObj(nobj.getCd(), Integer.valueOf(1));
 342                 // send the new object to target core according to pre-decide scheduling
 343                 Queue<Integer> cores = cs.getTargetCores(nobj.getCurrentFS());
 344                 if(cores == null) {
 345                   // this obj will reside on this core
 346                   cs.addObject(nobj);
 347                 } else {
 348                   Integer targetCore = cores.poll();
 349                   if(targetCore == coreNum) {
 350                     // this obj will reside on this core
 351                     cs.addObject(nobj);
 352                   } else {
 353                     if(!transObjQueues.containsKey(targetCore)) {
 354                       transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
 355                     }
 356                     Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
 357                     tmpqueue.add(new ObjectInfo(nobj));
 358                     tmpqueue = null;
 359                   }
 360                   // enqueue this core again
 361                   cores.add(targetCore);
 362                 }
 363                 cores = null;
 364                 // check if this object becoming shared or not
 365                 Vector<Integer> allycores = cs.getAllyCores(nobj.getCurrentFS());
 366                 if(allycores != null) {
 367                   nobj.setShared(true);
 368                   for(int k = 0; k < allycores.size(); ++k) {
 369                     Integer allyCore = allycores.elementAt(k);
 370                     if(allyCore == coreNum) {
 371                       cs.addObject(nobj);
 372                     } else {
 373                       if(!transObjQueues.containsKey(allyCore)) {
 374                         transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
 375                       }
 376                       Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
 377                       ObjectInfo nobjinfo = new ObjectInfo(nobj);
 378                       if(!tmpqueue.contains(nobjinfo)) {
 379                         tmpqueue.add(nobjinfo);
 380                       }
 381                       tmpqueue = null;
 382                     }
 383                   }
 384                   allycores = null;
 385                 }
 386               }
 387               nobjs = null;
 388             }
 389             cp.addAction(action);
 390             Vector<ObjectSimulator> transObjs = cs.finishTask();
 391             if(transObjs != null) {
 392               for(int j = 0; j < transObjs.size(); j++) {
 393                 ObjectSimulator tobj = transObjs.elementAt(j);
 394                 // send the object to target core according to pre-decide scheduling
 395                 Queue<Integer> cores = cs.getTargetCores(tobj.getCurrentFS());
 396                 tobj.setCurrentFS(cs.getTargetFState(tobj.getCurrentFS()));
 397                 if(cores == null) {
 398                   // this obj will reside on this core
 399                   cs.addObject(tobj);
 400                 } else {
 401                   Integer targetCore = cores.poll();
 402                   if(targetCore == coreNum) {
 403                     // this obj will reside on this core
 404                     cs.addObject(tobj);
 405                   } else {
 406                     if(!transObjQueues.containsKey(targetCore)) {
 407                       transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
 408                     }
 409                     Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
 410                     tmpqueue.add(new ObjectInfo(tobj));
 411                     tmpqueue = null;
 412                   }
 413                   cores.add(targetCore);
 414                 }
 415                 cores = null;
 416                 // check if this object becoming shared or not
 417                 Vector<Integer> allycores = cs.getAllyCores(tobj.getCurrentFS());
 418                 if(allycores != null) {
 419                   tobj.setShared(true);
 420                   for(int k = 0; k < allycores.size(); ++k) {
 421                     Integer allyCore = allycores.elementAt(k);
 422                     if(allyCore == coreNum) {
 423                       cs.addObject(tobj);
 424                     } else {
 425                       if(!transObjQueues.containsKey(allyCore)) {
 426                         transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
 427                       }
 428                       Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
 429                       ObjectInfo nobjinfo = new ObjectInfo(tobj);
 430                       if(!tmpqueue.contains(nobjinfo)) {
 431                         tmpqueue.add(nobjinfo);
 432                       }
 433                       tmpqueue = null;
 434                     }
 435                   }
 436                   allycores = null;
 437                 }
 438               }
 439               transObjs = null;
 440             }
 441             // add 'transport' tasks
 442             Iterator it_entries = transObjQueues.entrySet().iterator();
 443             while(it_entries.hasNext()) {
 444               Entry<Integer, Queue<ObjectInfo>> tmpentry = (Entry<Integer, Queue<ObjectInfo>>)it_entries.next();
 445               Integer tmpCoreNum = tmpentry.getKey();
 446               Queue<ObjectInfo> nobjs = tmpentry.getValue();
 447               TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs);
 448               this.tasks.add(tmptask);
 449               tmpentry = null;
 450               nobjs = null;
 451             }
 452             transObjQueues = null;
 453           } else if (task.getCurrentRun().getExetype() == 1) {
 454             action = new Action(coreNum, Action.TASKABORT);
 455             action.setTd(cs.getRtask().getTd());
 456             cp.addAction(action);
 457             Vector<ObjectSimulator> transObjs = cs.finishTask();
 458           } else if (task.getCurrentRun().getExetype() == 2) {
 459             action = new Action(coreNum, Action.TASKREMOVE);
 460             action.setTd(cs.getRtask().getTd());
 461             cp.addAction(action);
 462             Vector<ObjectSimulator> transObjs = cs.finishTask();
 463           }
 464           // Choose a new task for this core
 465           TaskSimulator newTask = cs.process();
 466           if(newTask != null) {
 467             this.tasks.add(newTask);
 468             // add a TASKSTART action into this checkpoint
 469             action = new Action(coreNum, Action.TASKSTART);
 470             action.setTd(cs.getRtask().getTd());
 471             cp.addAction(action);
 472           }
 473         }
 474       }
 475       this.checkpoints.add(cp);
 476       finishTasks = null;
 477     }
 478
 479     if(this.state.PRINTSCHEDULESIM) {
 480         SchedulingUtil.printSimulationResult("SimulatorResult_" + this.invoketime + ".dot", this.processTime,
 481                 this.coreNum, this.checkpoints);
 482     }
 483     System.out.println("Simulate scheduling #" + this.invoketime + ": ");
 484     System.out.println("\tTotal execution time is: " + this.processTime);
 485     System.out.println("\tUtility of cores: ");
 486     for(int j = 0; j < this.cores.size(); j++) {
 487       System.out.println("\t\tcore" + j + ": " + getUtility(j) + "%");
 488     }
 489
 490     this.checkpoints.clear();
 491     this.checkpoints = null;
 492     return this.processTime;
 493   }
 494
 495   public class CheckPoint {
 496     private int timepoint;
 497     private Vector<Action> actions;
 498
 499     public CheckPoint(int timepoint) {
 500       super();
 501       this.timepoint = timepoint;
 502       this.actions = new Vector<Action>();
 503     }
 504
 505     public Vector<Action> getActions() {
 506       return actions;
 507     }
 508
 509     public void addAction(Action action) {
 510       this.actions.add(action);
 511     }
 512
 513     public int getTimepoint() {
 514       return timepoint;
 515     }
 516   }
 517
 518   public class Action {
 519     public static final int ADDOBJ = 0;
 520     public static final int TASKFINISH = 1;
 521     public static final int TFWITHOBJ = 2;
 522     public static final int TASKSTART = 3;
 523     public static final int TASKABORT = 4;
 524     public static final int TASKREMOVE = 5;
 525
 526     private int coreNum;
 527     private int type;
 528     private TaskDescriptor td;
 529     private Hashtable<ClassDescriptor, Integer> nObjs;
 530     private int nObjNum;
 531     private ClassDescriptor transObj;
 532
 533     public Action(int coreNum, int type) {
 534       super();
 535       this.coreNum = coreNum;
 536       this.type = type;
 537       this.td = null;
 538       if(this.type == TFWITHOBJ) {
 539         this.nObjs = new Hashtable<ClassDescriptor, Integer>();
 540       } else {
 541         this.nObjs = null;
 542       }
 543       this.nObjNum = -1;
 544       this.transObj = null;
 545     }
 546
 547     public Action(int coreNum, int type, int objNum, ClassDescriptor transObj) {
 548       super();
 549       assert(type == ADDOBJ);
 550       this.coreNum = coreNum;
 551       this.type = type;
 552       this.td = null;
 553       this.nObjNum = objNum;
 554       this.transObj = transObj;
 555     }
 556
 557     public void addNewObj(ClassDescriptor cd, Integer num) {
 558       assert(this.type == TFWITHOBJ);
 559
 560       if(this.nObjs.containsKey(cd)) {
 561         Integer sum = this.nObjs.get(cd) + num;
 562         this.nObjs.put(cd, sum);
 563       } else {
 564         this.nObjs.put(cd, num);
 565       }
 566     }
 567
 568     public int getCoreNum() {
 569       return coreNum;
 570     }
 571
 572     public int getType() {
 573       return type;
 574     }
 575
 576     public int getNObjNum() {
 577       return nObjNum;
 578     }
 579
 580     public ClassDescriptor getTransObj() {
 581       return transObj;
 582     }
 583
 584     public TaskDescriptor getTd() {
 585       return td;
 586     }
 587
 588     public void setTd(TaskDescriptor td) {
 589       this.td = td;
 590     }
 591
 592     public Hashtable<ClassDescriptor, Integer> getNObjs() {
 593       return nObjs;
 594     }
 595   }
 596
 597 }