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