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