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