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