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 int processTime;
  25   private int invoketime;
  26
  27   State state;
  28   TaskAnalysis taskanalysis;
  29
  30   public ScheduleSimulator(int corenum,
  31                            State state,
  32                            TaskAnalysis taskanalysis) {
  33     this.coreNum = corenum;
  34     this.scheduling = null;
  35     this.cores = null;
  36     this.tasks = null;
  37     this.processTime = 0;
  38     this.invoketime = 0;
  39     this.state = state;
  40     this.taskanalysis = taskanalysis;
  41   }
  42
  43   public ScheduleSimulator(int corenum,
  44                            Vector<Schedule> scheduling,
  45                            State state,
  46                            TaskAnalysis taskanalysis) {
  47     super();
  48     this.coreNum = corenum;
  49     this.scheduling = scheduling;
  50     this.cores = new Vector<CoreSimulator>(this.coreNum);
  51     for(int i = 0; i < this.coreNum; i++) {
  52       this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
  53     }
  54     this.tasks = new Vector<TaskSimulator>();
  55     this.processTime = 0;
  56     this.invoketime = 0;
  57     this.state = state;
  58     this.taskanalysis = taskanalysis;
  59     applyScheduling();
  60   }
  61
  62   public int simulate(Vector<Vector<Schedule>> schedulings,
  63                       Vector<Integer> selectedScheduling,
  64                       Vector<Vector<SimExecutionEdge>> selectedSimExeGraphs) {
  65       int processTime = Integer.MAX_VALUE;
  66       /*if(schedulings.size() > 1500) {
  67           int index = 0;
  68           int upperbound = schedulings.size();
  69           long seed = 0;
  70           java.util.Random r = new java.util.Random(seed);
  71           for(int ii = 0; ii < 1500; ii++) {
  72               index = (int)((Math.abs((double)r.nextInt()
  73                            /(double)Integer.MAX_VALUE)) * upperbound);
  74               System.out.println("Scheduling index:" + index);
  75               Vector<Schedule> scheduling = schedulings.elementAt(index);
  76               this.setScheduling(scheduling);
  77               Vector<SimExecutionEdge> simexegraph = new Vector<SimExecutionEdge>();
  78               Vector<CheckPoint> checkpoints = new Vector<CheckPoint>();
  79               int tmpTime = this.process(checkpoints, simexegraph);
  80               if(tmpTime < processTime) {
  81                   selectedScheduling.clear();
  82                   selectedScheduling.add(index);
  83                   selectedSimExeGraphs.clear();
  84                   selectedSimExeGraphs.add(simexegraph);
  85                   processTime = tmpTime;
  86               } else if(tmpTime == processTime) {
  87                   selectedScheduling.add(index);
  88                   selectedSimExeGraphs.add(simexegraph);
  89               }
  90               scheduling = null;
  91               checkpoints = null;
  92               simexegraph = null;
  93           }
  94       } else {*/
  95           Iterator it_scheduling = schedulings.iterator();
  96           int index = 0;
  97           while(it_scheduling.hasNext()) {
  98               Vector<Schedule> scheduling =
  99                   (Vector<Schedule>)it_scheduling.next();
 100               System.out.println("Scheduling index:" + scheduling.elementAt(0).getGid());
 101               this.setScheduling(scheduling);
 102               Vector<SimExecutionEdge> simexegraph = new Vector<SimExecutionEdge>();
 103               Vector<CheckPoint> checkpoints = new Vector<CheckPoint>();
 104               int tmpTime = process(checkpoints, simexegraph);
 105               if(tmpTime < processTime) {
 106                   selectedScheduling.clear();
 107                   selectedScheduling.add(index);
 108                   selectedSimExeGraphs.clear();
 109                   selectedSimExeGraphs.add(simexegraph);
 110                   processTime = tmpTime;
 111               } else if(tmpTime == processTime) {
 112                   selectedScheduling.add(index);
 113                   selectedSimExeGraphs.add(simexegraph);
 114               }
 115               scheduling = null;
 116               checkpoints.clear();
 117               checkpoints = null;
 118               simexegraph = null;
 119               index++;
 120           }
 121           it_scheduling = null;
 122       //}
 123
 124       System.out.print("Selected schedulings with least exectution time " + processTime + ": \n\t");
 125       for(int i = 0; i < selectedScheduling.size(); i++) {
 126           int gid = schedulings.elementAt(selectedScheduling.elementAt(i)).elementAt(0).getGid();
 127           System.out.print(gid + ", ");
 128       }
 129       System.out.println();
 130
 131       return processTime;
 132   }
 133
 134   public int getCoreNum() {
 135     return this.coreNum;
 136   }
 137
 138   public void setCoreNum(int corenum) {
 139     this.coreNum = corenum;
 140     if(this.cores != null) {
 141       this.cores.clear();
 142     }
 143     this.cores = new Vector<CoreSimulator>(this.coreNum);
 144     for(int i = 0; i < this.coreNum; i++) {
 145       this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
 146     }
 147     if(this.scheduling != null) {
 148       applyScheduling();
 149     }
 150   }
 151
 152   public int getUtility(int index) {
 153     return (this.cores.elementAt(index).getActiveTime() * 100) / this.processTime;
 154   }
 155
 156   public Vector<Schedule> getScheduling() {
 157     return scheduling;
 158   }
 159
 160   public void setScheduling(Vector<Schedule> scheduling) {
 161     this.scheduling = scheduling;
 162     if(this.tasks == null) {
 163       this.tasks = new Vector<TaskSimulator>();
 164     } else {
 165       this.tasks.clear();
 166     }
 167     if(this.cores != null) {
 168       for(int i = 0; i < this.coreNum; i++) {
 169         CoreSimulator core = this.cores.elementAt(i);
 170         core.reset();
 171         core.setRSchedule(FIFORSchedule.getFIFORSchedule());
 172       }
 173     } else {
 174       this.cores = new Vector<CoreSimulator>(this.coreNum);
 175       for(int i = 0; i < this.coreNum; i++) {
 176         this.cores.add(new CoreSimulator(FIFORSchedule.getFIFORSchedule(), i));
 177       }
 178     }
 179
 180     applyScheduling();
 181   }
 182
 183   public void applyScheduling() {
 184     assert(this.state != null);
 185
 186     for(int i = 0; i < this.scheduling.size(); i++) {
 187       Schedule temp = this.scheduling.elementAt(i);
 188       CoreSimulator cs = this.cores.elementAt(temp.getCoreNum());
 189       cs.deployTasks(temp.getTasks());
 190       cs.setTargetCSimulator(temp.getTargetCoreTable());
 191       cs.setAllyCSimulator(temp.getAllyCoreTable());
 192       cs.setTargetFState(temp.getTargetFStateTable());
 193     }
 194     // inject a Startup Object to each core
 195     for(int i = 0; i < this.coreNum; i++) {
 196       ClassDescriptor startupobject=(ClassDescriptor)state.getClassSymbolTable().get(TypeUtil.StartupClass);
 197       FlagState fsstartup = (FlagState)taskanalysis.getRootNodes(startupobject).elementAt(0);
 198       ObjectSimulator newObj = new ObjectSimulator(startupobject, fsstartup);
 199       this.cores.elementAt(i).addObject(newObj);
 200     }
 201   }
 202
 203   public Vector<TaskSimulator> getTasks() {
 204     return tasks;
 205   }
 206
 207   public int process(Vector<CheckPoint> checkpoints,
 208                      Vector<SimExecutionEdge> simexegraph) {
 209     assert(this.scheduling != null);
 210
 211     this.invoketime++;
 212     this.processTime = 0;
 213
 214     // helper structures for building SimExecutionGraph
 215     Hashtable<SimExecutionNode, Action> senode2action =
 216             new Hashtable<SimExecutionNode, Action>();
 217     SimExecutionNode[] lastseNodes = new SimExecutionNode[this.cores.size()];
 218     Hashtable<Action, Integer> action2exetime =
 219             new Hashtable<Action, Integer>();
 220     Hashtable<TransTaskSimulator, SimExecutionNode> tttask2senode =
 221             new Hashtable<TransTaskSimulator, SimExecutionNode>();
 222     Hashtable<Integer, Integer> obj2transtime =
 223             new Hashtable<Integer, Integer>();
 224     Hashtable<Integer, SimExecutionEdge> obj2lastseedge =
 225             new Hashtable<Integer, SimExecutionEdge>();
 226
 227     // first decide next task to execute on each core
 228     int i = 0;
 229     for(i = 0; i < this.cores.size(); i++) {
 230       CoreSimulator cs = this.cores.elementAt(i);
 231       TaskSimulator task = cs.process();
 232       if(task != null) {
 233         this.tasks.add(task);
 234       }
 235       lastseNodes[i] = null;
 236     }
 237
 238     // add STARTTASK checkpoint for all the initial tasks
 239     CheckPoint cp = new CheckPoint(this.processTime,
 240                                    this.coreNum);
 241     for(i = 0; i < this.tasks.size(); i++) {
 242       TaskSimulator task = this.tasks.elementAt(i);
 243       int coreid = task.getCs().getCoreNum();
 244       Action action = new Action(coreid,
 245                                  Action.TASKSTART,
 246                                  task);
 247       cp.addAction(action);
 248       if(!(task instanceof TransTaskSimulator)) {
 249           cp.removeSpareCore(coreid);
 250           SimExecutionNode seNode = new SimExecutionNode(coreid, this.processTime);
 251           seNode.setSpareCores(cp.getSpareCores());
 252           senode2action.put(seNode, action);
 253           action2exetime.put(action, -1);
 254           lastseNodes[coreid] = seNode;
 255       }
 256     }
 257     checkpoints.add(cp);
 258
 259     while(true) {
 260       // if no more tasks on each core, simulation finish
 261       if(this.tasks.size() == 0) {
 262         break;
 263       }
 264
 265       // for each task in todo queue, decide the execution path of this time
 266       // according to statistic information
 267       int finishTime = Integer.MAX_VALUE;
 268       Vector<TaskSimulator> finishTasks = new Vector<TaskSimulator>();
 269       for(i = 0; i < this.tasks.size(); i++) {
 270         TaskSimulator task = this.tasks.elementAt(i);
 271         task.process();
 272         int tempTime = task.getCurrentRun().getFinishTime();
 273         if(tempTime < finishTime) {
 274           finishTime = tempTime;
 275           finishTasks.clear();
 276           finishTasks.add(task);
 277         } else if (tempTime == finishTime) {
 278           finishTasks.add(task);
 279         }
 280       }
 281
 282       // advance to next finish point
 283       this.processTime += finishTime;
 284       cp = new CheckPoint(this.processTime,
 285                           this.coreNum);
 286       for(i = 0; i < this.tasks.size(); i++) {
 287         TaskSimulator task = this.tasks.elementAt(i);
 288         if(!finishTasks.contains(task)) {
 289           task.getCs().updateTask(finishTime);
 290           if(!(task instanceof TransTaskSimulator)) {
 291               cp.removeSpareCore(task.getCs().getCoreNum());
 292           }
 293         }
 294       }
 295
 296       Action action = null;
 297       for(i = 0; i < finishTasks.size(); i++) {
 298         TaskSimulator task = finishTasks.elementAt(i);
 299         this.tasks.removeElement(task);
 300         if(task instanceof TransTaskSimulator) {
 301             // handle TransTaskSimulator task's completion
 302             finishTransTaskSimulator(task,
 303                                      cp,
 304                                      simexegraph,
 305                                      senode2action,
 306                                      lastseNodes,
 307                                      action2exetime,
 308                                      tttask2senode,
 309                                      obj2transtime);
 310         } else {
 311           CoreSimulator cs = task.getCs();
 312           Vector<TransTaskSimulator> tttasks = new Vector<TransTaskSimulator>();
 313
 314           Vector<ObjectSimulator> transObjs = null;
 315           if(task.getCurrentRun().getExetype() == 0) {
 316               // normal execution of a task
 317               transObjs = finishTaskNormal(task,
 318                                            cp,
 319                                            tttasks,
 320                                            senode2action,
 321                                            lastseNodes,
 322                                            action2exetime);
 323           } else if (task.getCurrentRun().getExetype() == 1) {
 324               // task abort
 325               finishTaskAbnormal(cs,
 326                                  cp,
 327                                  senode2action,
 328                                  lastseNodes,
 329                                  action2exetime,
 330                                  Action.TASKABORT);
 331           } else if (task.getCurrentRun().getExetype() == 2) {
 332               // task remove
 333               finishTaskAbnormal(cs,
 334                                  cp,
 335                                  senode2action,
 336                                  lastseNodes,
 337                                  action2exetime,
 338                                  Action.TASKREMOVE);
 339           }
 340
 341           // Choose a new task for this core
 342           generateNewTask(cs,
 343                           cp,
 344                           transObjs,
 345                           tttasks,
 346                           simexegraph,
 347                           senode2action,
 348                           lastseNodes,
 349                           action2exetime,
 350                           tttask2senode,
 351                           obj2transtime,
 352                           obj2lastseedge);
 353           tttasks.clear();
 354           tttasks = null;
 355           transObjs = null;
 356         }// end of if(task instanceof TransTaskSimulator) else
 357       }
 358       checkpoints.add(cp);
 359       finishTasks = null;
 360     } // end of while(true)
 361
 362     // add the end node into the SimExecutionGraph
 363     SimExecutionNode seNode = new SimExecutionNode(this.coreNum, this.processTime);
 364     for(int j = 0; j < lastseNodes.length; j++) {
 365         SimExecutionNode lastsenode = lastseNodes[j];
 366         // create edges between previous senode on this core to this node
 367         if(lastsenode != null) {
 368             Action tmpaction = senode2action.get(lastsenode);
 369             int weight = tmpaction != null? action2exetime.get(tmpaction) : 0;  // TODO ????
 370             SimExecutionEdge seEdge = new SimExecutionEdge(seNode,
 371                                                            lastsenode.getCoreNum(),
 372                                                            tmpaction != null? tmpaction.getTd():null,
 373                                                            weight,
 374                                                            tmpaction != null? tmpaction.getTaskParams():null);
 375             lastsenode.addEdge(seEdge);
 376
 377             // setup data dependencies for the task
 378             Vector<Integer> taskparams = seEdge.getTaskparams();
 379             if(taskparams != null) {
 380                 for(int k = 0; k < taskparams.size(); k++) {
 381                     Integer tparam = taskparams.elementAt(k);
 382                     SimExecutionEdge lastedge = obj2lastseedge.get(tparam);
 383                     if(lastedge != null) {
 384                         if(lastedge.getCoreNum() != seEdge.getCoreNum()) {
 385                             // the obj is transferred from another core
 386                             // create an seEdge for this transfer
 387                             int transweight = obj2transtime.get(tparam);
 388                             SimExecutionEdge transseEdge = new SimExecutionEdge((SimExecutionNode)seEdge.getSource(),
 389                                                                                 lastedge.getCoreNum(),
 390                                                                                 null, // TODO: not sure if this is enough
 391                                                                                 transweight,
 392                                                                                 null);
 393                             if(((SimExecutionNode)seEdge.getSource()).getTimepoint() <
 394                                     ((SimExecutionNode)lastedge.getTarget()).getTimepoint()) {
 395                                 System.err.println("ScheduleSimulator:393");
 396                                 System.exit(-1);
 397                             }
 398                             lastedge.getTarget().addEdge(transseEdge);
 399                             simexegraph.add(transseEdge);
 400                             transseEdge.addPredicate(lastedge);
 401                             seEdge.addPredicate(transseEdge);
 402                         } else {
 403                             seEdge.addPredicate(lastedge);
 404                         }
 405                     }
 406                     // update the last edge associated to the parameter obj
 407                     obj2lastseedge.put(tparam, seEdge);
 408                 }
 409             }
 410             taskparams = null;
 411             simexegraph.add(seEdge); // add the seEdge afger all corresponding transfer edges
 412         }
 413         lastseNodes[j] = null;
 414     }
 415
 416     senode2action.clear();
 417     senode2action = null;
 418     lastseNodes = null;
 419     action2exetime.clear();
 420     action2exetime = null;
 421     tttask2senode.clear();
 422     tttask2senode = null;
 423     obj2transtime.clear();
 424     obj2transtime = null;
 425     obj2lastseedge.clear();
 426     obj2lastseedge = null;
 427
 428     int gid = this.scheduling.elementAt(0).getGid();
 429     if(this.state.PRINTSCHEDULESIM) {
 430         SchedulingUtil.printSimulationResult(this.state.outputdir + "SimulatorResult_" + gid + ".dot",
 431                                              this.processTime,
 432                                              this.coreNum,
 433                                              checkpoints);
 434     }
 435     System.out.println("Simulate scheduling #" + gid + ": ");
 436     System.out.println("\tTotal execution time is: " + this.processTime);
 437     System.out.println("\tUtility of cores: ");
 438     for(int j = 0; j < this.cores.size(); j++) {
 439       System.out.println("\t\tcore" + j + ": " + getUtility(j) + "%");
 440     }
 441
 442     return this.processTime;
 443   }
 444
 445   private void finishTransTaskSimulator(TaskSimulator task,
 446                                         CheckPoint cp,
 447                                         Vector<SimExecutionEdge> simexegraph,
 448                                         Hashtable<SimExecutionNode, Action> senode2action,
 449                                         SimExecutionNode[] lastseNodes,
 450                                         Hashtable<Action, Integer> action2exetime,
 451                                         Hashtable<TransTaskSimulator, SimExecutionNode> tttask2senode,
 452                                         Hashtable<Integer, Integer> obj2transtime) {
 453       TransTaskSimulator tmptask = (TransTaskSimulator)task;
 454       // add ADDOBJ task to targetCore
 455       int targetCoreNum = tmptask.getTargetCoreNum();
 456       ObjectInfo objinfo = tmptask.refreshTask();
 457       ObjectSimulator nobj = objinfo.obj;
 458       FlagState fs = objinfo.fs;
 459       int version = objinfo.version;
 460       this.cores.elementAt(targetCoreNum).addObject(nobj, fs, version);
 461       Action action = new Action(targetCoreNum, Action.ADDOBJ, 1, nobj.getCd());
 462       cp.addAction(action);
 463
 464       // get the obj transfer time and associated senode
 465       SimExecutionNode senode = tttask2senode.get(tmptask);
 466       obj2transtime.put(nobj.getOid(), this.processTime - senode.getTimepoint());
 467
 468       if(!tmptask.isFinished()) {
 469           // still have some objects to be transferred
 470           this.tasks.add(task);
 471       }
 472       if(this.cores.elementAt(targetCoreNum).getRtask() == null) {
 473           TaskSimulator newTask = this.cores.elementAt(targetCoreNum).process();
 474           if(newTask != null) {
 475               this.tasks.add(newTask);
 476               // add a TASKSTART action into this checkpoint
 477               action = new Action(targetCoreNum,
 478                                   Action.TASKSTART,
 479                                   newTask);
 480               cp.addAction(action);
 481               if(!(newTask instanceof TransTaskSimulator)) {
 482                   cp.removeSpareCore(targetCoreNum);
 483                   SimExecutionNode seNode = new SimExecutionNode(targetCoreNum, this.processTime);
 484                   seNode.setSpareCores(cp.getSpareCores());
 485                   senode2action.put(seNode, action);
 486                   action2exetime.put(action, -1);
 487
 488                   SimExecutionNode lastsenode = lastseNodes[targetCoreNum];
 489                   // create edges between previous senode on this core to this node
 490                   if(lastsenode != null) {
 491                       Action tmpaction = senode2action.get(lastsenode);
 492                       SimExecutionEdge seEdge = null;
 493                       if(tmpaction == null) {
 494                           seEdge = new SimExecutionEdge(seNode,
 495                                                         lastsenode.getCoreNum(),
 496                                                         null,
 497                                                         0,
 498                                                         null);
 499                       } else {
 500                           int weight =  action2exetime.get(tmpaction);
 501                           seEdge = new SimExecutionEdge(seNode,
 502                                                         lastsenode.getCoreNum(),
 503                                                         tmpaction.getTd(),
 504                                                         weight,
 505                                                         tmpaction.getTaskParams());
 506                       }
 507                       lastsenode.addEdge(seEdge);
 508                       simexegraph.add(seEdge);
 509                   }
 510                   lastseNodes[targetCoreNum] = seNode;
 511               }
 512           }
 513       }
 514   }
 515
 516   private Vector<ObjectSimulator> finishTaskNormal(TaskSimulator task,
 517                                                    CheckPoint cp,
 518                                                    Vector<TransTaskSimulator> tttasks,
 519                                                    Hashtable<SimExecutionNode, Action> senode2action,
 520                                                    SimExecutionNode[] lastseNodes,
 521                                                    Hashtable<Action, Integer> action2exetime) {
 522       Vector<ObjectSimulator> totransObjs = new Vector<ObjectSimulator>();
 523       CoreSimulator cs = task.getCs();
 524       int corenum = cs.getCoreNum();
 525       Hashtable<Integer, Queue<ObjectInfo>> transObjQueues =
 526           new Hashtable<Integer, Queue<ObjectInfo>>();
 527       Action action = null;
 528       if(task.getCurrentRun().getNewObjs() == null) {
 529           // task finish without new objects
 530           action = new Action(corenum,
 531                               Action.TASKFINISH,
 532                               cs.getRtask());
 533           // get the execution time of this task
 534           SimExecutionNode lastsenode = lastseNodes[corenum];
 535           Action startaction = senode2action.get(lastsenode);
 536           action2exetime.put(startaction, cp.getTimepoint() - lastsenode.getTimepoint());
 537
 538       } else {
 539           // task finish with new objects
 540           action = new Action(corenum,
 541                               Action.TFWITHOBJ,
 542                               cs.getRtask());
 543           // get the execution time of this task
 544           SimExecutionNode lastsenode = lastseNodes[corenum];
 545           Action startaction = senode2action.get(lastsenode);
 546           action2exetime.put(startaction, cp.getTimepoint() - lastsenode.getTimepoint());
 547
 548           // get the infomation of how to send new objects
 549           Vector<ObjectSimulator> nobjs = task.getCurrentRun().getNewObjs();
 550           for(int j = 0; j < nobjs.size(); j++) {
 551               ObjectSimulator nobj = nobjs.elementAt(j);
 552               totransObjs.add(nobj);
 553
 554               action.addNewObj(nobj.getCd(), Integer.valueOf(1));
 555               // send the new object to target core according to pre-decide scheduling
 556               Queue<Integer> cores = cs.getTargetCores(nobj.getCurrentFS());
 557               if(cores == null) {
 558                   // this obj will reside on this core
 559                   cs.addObject(nobj);
 560               } else {
 561                   Integer targetCore = cores.poll();
 562                   if(targetCore == corenum) {
 563                       // this obj will reside on this core
 564                       cs.addObject(nobj);
 565                   } else {
 566                       if(!transObjQueues.containsKey(targetCore)) {
 567                           transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
 568                       }
 569                       Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
 570                       tmpqueue.add(new ObjectInfo(nobj));
 571                       tmpqueue = null;
 572                   }
 573                   // enqueue this core again
 574                   cores.add(targetCore);
 575               }
 576               cores = null;
 577               // check if this object becoming shared or not
 578               Vector<Integer> allycores = cs.getAllyCores(nobj.getCurrentFS());
 579               if(allycores != null) {
 580                   nobj.setShared(true);
 581                   for(int k = 0; k < allycores.size(); ++k) {
 582                       Integer allyCore = allycores.elementAt(k);
 583                       if(allyCore == corenum) {
 584                           cs.addObject(nobj);
 585                       } else {
 586                           if(!transObjQueues.containsKey(allyCore)) {
 587                               transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
 588                           }
 589                           Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
 590                           ObjectInfo nobjinfo = new ObjectInfo(nobj);
 591                           if(!tmpqueue.contains(nobjinfo)) {
 592                               tmpqueue.add(nobjinfo);
 593                           }
 594                           tmpqueue = null;
 595                       }
 596                   }
 597                   allycores = null;
 598               }
 599           }
 600           nobjs = null;
 601       }
 602       cp.addAction(action);
 603
 604       // group the new objects need to transfer
 605       Vector<ObjectSimulator> transObjs = cs.finishTask();
 606       if(transObjs != null) {
 607           totransObjs.addAll(transObjs);
 608           for(int j = 0; j < transObjs.size(); j++) {
 609               ObjectSimulator tobj = transObjs.elementAt(j);
 610               // send the object to target core according to pre-decide scheduling
 611               Queue<Integer> cores = cs.getTargetCores(tobj.getCurrentFS());
 612               tobj.setCurrentFS(cs.getTargetFState(tobj.getCurrentFS()));
 613               if(cores == null) {
 614                   // this obj will reside on this core
 615                   cs.addObject(tobj);
 616               } else {
 617                   Integer targetCore = cores.poll();
 618                   if(targetCore == corenum) {
 619                       // this obj will reside on this core
 620                       cs.addObject(tobj);
 621                   } else {
 622                       if(!transObjQueues.containsKey(targetCore)) {
 623                           transObjQueues.put(targetCore, new LinkedList<ObjectInfo>());
 624                       }
 625                       Queue<ObjectInfo> tmpqueue = transObjQueues.get(targetCore);
 626                       tmpqueue.add(new ObjectInfo(tobj));
 627                       tmpqueue = null;
 628                   }
 629                   cores.add(targetCore);
 630               }
 631               cores = null;
 632               // check if this object becoming shared or not
 633               Vector<Integer> allycores = cs.getAllyCores(tobj.getCurrentFS());
 634               if(allycores != null) {
 635                   tobj.setShared(true);
 636                   for(int k = 0; k < allycores.size(); ++k) {
 637                       Integer allyCore = allycores.elementAt(k);
 638                       if(allyCore == corenum) {
 639                           cs.addObject(tobj);
 640                       } else {
 641                           if(!transObjQueues.containsKey(allyCore)) {
 642                               transObjQueues.put(allyCore, new LinkedList<ObjectInfo>());
 643                           }
 644                           Queue<ObjectInfo> tmpqueue = transObjQueues.get(allyCore);
 645                           ObjectInfo nobjinfo = new ObjectInfo(tobj);
 646                           if(!tmpqueue.contains(nobjinfo)) {
 647                               tmpqueue.add(nobjinfo);
 648                           }
 649                           tmpqueue = null;
 650                       }
 651                   }
 652                   allycores = null;
 653               }
 654           }
 655       }
 656       transObjs = null;
 657
 658       // add 'transport' tasks
 659       Iterator it_entries = transObjQueues.entrySet().iterator();
 660       while(it_entries.hasNext()) {
 661           Entry<Integer, Queue<ObjectInfo>> tmpentry = (Entry<Integer, Queue<ObjectInfo>>)it_entries.next();
 662           Integer tmpCoreNum = tmpentry.getKey();
 663           Queue<ObjectInfo> nobjs = tmpentry.getValue();
 664           TransTaskSimulator tmptask = new TransTaskSimulator(cs, tmpCoreNum, nobjs);
 665           this.tasks.add(tmptask);
 666           tttasks.add(tmptask);
 667           tmpentry = null;
 668           nobjs = null;
 669       }
 670       it_entries = null;
 671       transObjQueues = null;
 672
 673       return totransObjs;
 674   }
 675
 676   private void generateNewTask(CoreSimulator cs,
 677                                CheckPoint cp,
 678                                Vector<ObjectSimulator> nobjs,
 679                                Vector<TransTaskSimulator> tttasks,
 680                                Vector<SimExecutionEdge> simexegraph,
 681                                Hashtable<SimExecutionNode, Action> senode2action,
 682                                SimExecutionNode[] lastseNodes,
 683                                Hashtable<Action, Integer> action2exetime,
 684                                Hashtable<TransTaskSimulator, SimExecutionNode> tttask2senode,
 685                                Hashtable<Integer, Integer> obj2transtime,
 686                                Hashtable<Integer, SimExecutionEdge> obj2lastseedge) {
 687       TaskSimulator newTask = cs.process();
 688       int corenum = cs.getCoreNum();
 689       SimExecutionEdge seEdge = null;
 690       if(newTask != null) {
 691           this.tasks.add(newTask);
 692           // add a TASKSTART action into this checkpoint
 693           Action action = new Action(corenum,
 694                                      Action.TASKSTART,
 695                                      newTask);
 696           cp.addAction(action);
 697           if(!(newTask instanceof TransTaskSimulator)) {
 698               cp.removeSpareCore(cs.getCoreNum());
 699               SimExecutionNode seNode = new SimExecutionNode(corenum, this.processTime);
 700               seNode.setSpareCores(cp.getSpareCores());
 701               senode2action.put(seNode, action);
 702               action2exetime.put(action, -1);
 703               SimExecutionNode lastsenode = lastseNodes[corenum];
 704               // create edges between previous senode on this core to this node
 705               if(lastsenode != null) {
 706                   Action tmpaction = senode2action.get(lastsenode);
 707                   int weight = tmpaction != null? action2exetime.get(tmpaction):0;
 708                   seEdge = new SimExecutionEdge(seNode,
 709                                                 lastsenode.getCoreNum(),
 710                                                 tmpaction!= null?tmpaction.getTd():null,
 711                                                 weight,
 712                                                 tmpaction!=null?tmpaction.getTaskParams():null);
 713                   lastsenode.addEdge(seEdge);
 714               }
 715               lastseNodes[corenum] = seNode;
 716               for(int tmpindex = 0; tmpindex < tttasks.size(); tmpindex++) {
 717                   tttask2senode.put(tttasks.elementAt(tmpindex), seNode);
 718               }
 719           }
 720       } else if(tttasks.size() > 0) {
 721           SimExecutionNode seNode = new SimExecutionNode(corenum, this.processTime);
 722           //seNode.setSpareCores(cp.getSpareCores());
 723           // no action associated here
 724           SimExecutionNode lastsenode = lastseNodes[corenum];
 725           // create edges between previous senode on this core to this node
 726           if(lastsenode != null) {
 727               Action tmpaction = senode2action.get(lastsenode);
 728               int weight = action2exetime.get(tmpaction);
 729               seEdge = new SimExecutionEdge(seNode,
 730                                             lastsenode.getCoreNum(),
 731                                             tmpaction.getTd(),
 732                                             weight,
 733                                             tmpaction.getTaskParams());
 734               lastsenode.addEdge(seEdge);
 735           }
 736           lastseNodes[corenum] = seNode;
 737           for(int tmpindex = 0; tmpindex < tttasks.size(); tmpindex++) {
 738               tttask2senode.put(tttasks.elementAt(tmpindex), seNode);
 739           }
 740       }
 741       if(seEdge != null) {
 742           // setup data dependencies for the task
 743           Vector<Integer> taskparams = seEdge.getTaskparams();
 744           if(taskparams != null) {
 745               for(int i = 0; i < taskparams.size(); i++) {
 746                   Integer tparam = taskparams.elementAt(i);
 747                   SimExecutionEdge lastedge = obj2lastseedge.get(tparam);
 748                   if(lastedge != null) {
 749                       if(lastedge.getCoreNum() != seEdge.getCoreNum()) {
 750                           // the obj is transferred from another core
 751                           // create an seEdge for this transfer
 752                           int weight = obj2transtime.get(tparam);
 753                           SimExecutionEdge transseEdge = new SimExecutionEdge((SimExecutionNode)seEdge.getSource(),
 754                                                                               lastedge.getCoreNum(),
 755                                                                               null, // TODO: not sure if this is enough
 756                                                                               weight,
 757                                                                               null);
 758                           if(((SimExecutionNode)seEdge.getSource()).getTimepoint() <
 759                                   ((SimExecutionNode)lastedge.getTarget()).getTimepoint()) {
 760                               System.err.println("ScheduleSimulator:757");
 761                               System.exit(-1);
 762                           }
 763                           lastedge.getTarget().addEdge(transseEdge);
 764                           simexegraph.add(transseEdge);
 765                           transseEdge.addPredicate(lastedge);
 766                           seEdge.addPredicate(transseEdge);
 767                       } else {
 768                           seEdge.addPredicate(lastedge);
 769                       }
 770                   }
 771                   // update the last edge associated to the parameter obj
 772                   obj2lastseedge.put(tparam, seEdge);
 773               }
 774           }
 775           taskparams = null;
 776           simexegraph.add(seEdge); // add the seEdge afger all corresponding transfer edges
 777
 778           // set seEdge as the last execution edge for all newly created objs
 779           if(nobjs != null) {
 780               for(int i = 0; i < nobjs.size(); i++) {
 781                   ObjectSimulator nobj = nobjs.elementAt(i);
 782                   obj2lastseedge.put(nobj.getOid(), seEdge);
 783               }
 784           }
 785       }
 786   }
 787
 788   private void finishTaskAbnormal(CoreSimulator cs,
 789                                   CheckPoint cp,
 790                                   Hashtable<SimExecutionNode, Action> senode2action,
 791                                   SimExecutionNode[] lastseNodes,
 792                                   Hashtable<Action, Integer> action2exetime,
 793                                   int type) {
 794       Action action = new Action(cs.getCoreNum(),
 795                                  type,
 796                                  cs.getRtask());
 797       cp.addAction(action);
 798       cs.finishTask();
 799
 800       // remove the corresponding action on the starting SimExecutionNode
 801       SimExecutionNode lastsenode = lastseNodes[cs.getCoreNum()];
 802       /*if(lastsenode.getInedgeVector().size() > 0) {
 803           //SimExecutionEdge inseedge = (SimExecutionEdge)lastsenode.getinedge(0);
 804           //lastseNodes[cs.getCoreNum()] = (SimExecutionNode)inseedge.getSource();
 805       } /*else {
 806           lastseNodes[cs.getCoreNum()] = null;
 807       }*/
 808       Action tmpaction = senode2action.remove(lastsenode);
 809       action2exetime.remove(tmpaction);
 810   }
 811
 812   public class CheckPoint {
 813     private int timepoint;
 814     private Vector<Action> actions;
 815     private Vector<Integer> spareCores;
 816
 817     public CheckPoint(int timepoint,
 818                       int corenum) {
 819       super();
 820       this.timepoint = timepoint;
 821       this.actions = new Vector<Action>();
 822       this.spareCores = new Vector<Integer>();
 823       for(int i = 0; i < corenum; i++) {
 824           this.spareCores.add(i);
 825       }
 826     }
 827
 828     public Vector<Action> getActions() {
 829       return actions;
 830     }
 831
 832     public void addAction(Action action) {
 833       this.actions.add(action);
 834     }
 835
 836     public void removeSpareCore(int core) {
 837         for(int i = 0 ; i < this.spareCores.size(); i++) {
 838             if(this.spareCores.elementAt(i) == core) {
 839                 for(int j = i; j < this.spareCores.size() - 1; j++) {
 840                     this.spareCores.setElementAt(this.spareCores.elementAt(j + 1), j);
 841                 }
 842                 this.spareCores.remove(this.spareCores.size() - 1);
 843                 return;
 844             }
 845         }
 846     }
 847
 848     public int getTimepoint() {
 849       return timepoint;
 850     }
 851
 852     public Vector<Integer> getSpareCores() {
 853         return spareCores;
 854     }
 855   }
 856
 857   public class Action {
 858     public static final int ADDOBJ = 0;
 859     public static final int TASKFINISH = 1;
 860     public static final int TFWITHOBJ = 2;
 861     public static final int TASKSTART = 3;
 862     public static final int TASKABORT = 4;
 863     public static final int TASKREMOVE = 5;
 864
 865     private int coreNum;
 866     private int type;
 867     private TaskDescriptor td;
 868     private Vector<Integer> taskparams;
 869     private Hashtable<ClassDescriptor, Integer> nObjs;
 870     private int nObjNum;
 871     private ClassDescriptor transObj;
 872
 873     public Action(int corenum,
 874                   int type) {
 875       this.coreNum = corenum;
 876       this.type = type;
 877       this.td = null;
 878       this.taskparams = null;
 879       if(this.type == TFWITHOBJ) {
 880         this.nObjs = new Hashtable<ClassDescriptor, Integer>();
 881       } else {
 882         this.nObjs = null;
 883       }
 884       this.nObjNum = -1;
 885       this.transObj = null;
 886     }
 887
 888     public Action(int corenum,
 889                   int type,
 890                   TaskSimulator ts) {
 891         assert(this.type != ADDOBJ);
 892
 893         this.coreNum = corenum;
 894         this.type = type;
 895         this.td = ts.getTd();
 896         Vector<Queue<ObjectSimulator>> paraQueues = ts.getParaQueues();
 897         if(this.type == TASKSTART) {
 898             this.taskparams = new Vector<Integer>();
 899             for(int i = 0; i < paraQueues.size(); i++) {
 900                 ObjectSimulator tpara = paraQueues.elementAt(i).peek();
 901                 this.taskparams.add(tpara.getOid());
 902             }
 903         } else {
 904             this.taskparams = null;
 905         }
 906         paraQueues = null;
 907         if(this.type == TFWITHOBJ) {
 908             this.nObjs = new Hashtable<ClassDescriptor, Integer>();
 909         } else {
 910             this.nObjs = null;
 911         }
 912         this.nObjNum = -1;
 913         this.transObj = null;
 914     }
 915
 916     public Action(int corenum,
 917                   int type,
 918                   int objNum,
 919                   ClassDescriptor transObj) {
 920       assert(type == ADDOBJ);
 921       this.coreNum = corenum;
 922       this.type = type;
 923       this.td = null;
 924       this.taskparams = null;
 925       this.nObjNum = objNum;
 926       this.transObj = transObj;
 927     }
 928
 929     public void addNewObj(ClassDescriptor cd,
 930                           Integer num) {
 931       assert(this.type == TFWITHOBJ);
 932
 933       if(this.nObjs.containsKey(cd)) {
 934         Integer sum = this.nObjs.get(cd) + num;
 935         this.nObjs.put(cd, sum);
 936       } else {
 937         this.nObjs.put(cd, num);
 938       }
 939     }
 940
 941     public int getCoreNum() {
 942       return this.coreNum;
 943     }
 944
 945     public int getType() {
 946       return type;
 947     }
 948
 949     public int getNObjNum() {
 950       return nObjNum;
 951     }
 952
 953     public ClassDescriptor getTransObj() {
 954       return transObj;
 955     }
 956
 957     public TaskDescriptor getTd() {
 958       return td;
 959     }
 960
 961     public Vector<Integer> getTaskParams() {
 962         return this.taskparams;
 963     }
 964
 965     public Hashtable<ClassDescriptor, Integer> getNObjs() {
 966       return nObjs;
 967     }
 968   }
 969
 970 }