Robust/src/Analysis/Scheduling/MCImplSynthesis.java

   1 package Analysis.Scheduling;
   2
   3 import java.io.File;
   4 import java.io.FileOutputStream;
   5 import java.io.PrintStream;
   6 import java.io.PrintWriter;
   7 import java.util.Hashtable;
   8 import java.util.Iterator;
   9 import java.util.Random;
  10 import java.util.Vector;
  11
  12 import Analysis.OwnershipAnalysis.OwnershipAnalysis;
  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 MCImplSynthesis {
  22
  23     State state;
  24     ScheduleAnalysis scheduleAnalysis;
  25     TaskAnalysis taskAnalysis;
  26     OwnershipAnalysis ownershipAnalysis;
  27     ScheduleSimulator scheduleSimulator;
  28
  29     int coreNum;
  30     int scheduleThreshold;
  31     int probThreshold;
  32     int generateThreshold;
  33
  34     //Random rand;
  35
  36     public MCImplSynthesis(State state,
  37                            TaskAnalysis ta,
  38                            OwnershipAnalysis oa) {
  39         this.state = state;
  40         this.coreNum = state.CORENUM;
  41         this.taskAnalysis = ta;
  42         this.ownershipAnalysis = oa;
  43         this.scheduleAnalysis = new ScheduleAnalysis(state,
  44                                                      ta);
  45         this.scheduleAnalysis.setCoreNum(this.coreNum);
  46         this.scheduleSimulator = new ScheduleSimulator(this.coreNum,
  47                                                        state,
  48                                                        ta);
  49         this.scheduleThreshold = 1000;
  50         this.probThreshold = 0;
  51         this.generateThreshold = 30;
  52         //this.rand = new Random();
  53     }
  54
  55     public int getCoreNum() {
  56         return this.scheduleAnalysis.getCoreNum();
  57     }
  58
  59     public int getScheduleThreshold() {
  60         return scheduleThreshold;
  61     }
  62
  63     public void setScheduleThreshold(int scheduleThreshold) {
  64         this.scheduleThreshold = scheduleThreshold;
  65     }
  66
  67     public int getProbThreshold() {
  68         return probThreshold;
  69     }
  70
  71     public void setProbThreshold(int probThreshold) {
  72         this.probThreshold = probThreshold;
  73     }
  74
  75     public int getGenerateThreshold() {
  76         return generateThreshold;
  77     }
  78
  79     public void setGenerateThreshold(int generateThreshold) {
  80         this.generateThreshold = generateThreshold;
  81     }
  82
  83     public Vector<Schedule> synthesis() {
  84         // Print stuff to the original output and error streams.
  85         // The stuff printed through the 'origOut' and 'origErr' references
  86         // should go to the console on most systems while the messages
  87         // printed through the 'System.out' and 'System.err' will end up in
  88         // the files we created for them.
  89         //origOut.println ("\nRedirect:  Round #2");
  90         //System.out.println ("Test output via 'SimulatorResult.out'.");
  91         //origOut.println ("Test output via 'origOut' reference.");
  92
  93         // Save the current standard input, output, and error streams
  94         // for later restoration.
  95         PrintStream origOut = System.out;
  96
  97         // Create a new output stream for the standard output.
  98         PrintStream stdout  = null;
  99         try {
 100             stdout = new PrintStream(
 101                     new FileOutputStream(this.state.outputdir + "SimulatorResult_"
 102                                          + this.coreNum + ".out"));
 103         } catch (Exception e) {
 104             // Sigh.  Couldn't open the file.
 105             System.out.println("Redirect:  Unable to open output file!");
 106             System.exit(1);
 107         }
 108
 109         // Print stuff to the original output and error streams.
 110         // On most systems all of this will end up on your console when you
 111         // run this application.
 112         //origOut.println ("\nRedirect:  Round #1");
 113         //System.out.println ("Test output via 'System.out'.");
 114         //origOut.println ("Test output via 'origOut' reference.");
 115
 116         // Set the System out and err streams to use our replacements.
 117         System.setOut(stdout);
 118
 119         Vector<Schedule> scheduling = null;
 120         Vector<ScheduleNode> schedulinggraph = null;
 121         int gid = 1;
 122
 123         // generate multiple schedulings
 124         this.scheduleAnalysis.setScheduleThreshold(this.scheduleThreshold);
 125         this.scheduleAnalysis.schedule(this.generateThreshold);
 126         if(this.generateThreshold > 5) {
 127             this.generateThreshold = 5;
 128         }
 129
 130         Vector<Vector<ScheduleNode>> scheduleGraphs = null;
 131         Vector<Vector<ScheduleNode>> newscheduleGraphs =
 132             this.scheduleAnalysis.getScheduleGraphs();
 133         Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
 134         Vector<Integer> selectedSchedulings = new Vector<Integer>();
 135         Vector<Vector<SimExecutionEdge>> selectedSimExeGraphs =
 136             new Vector<Vector<SimExecutionEdge>>();
 137
 138         // check all multi-parameter tasks
 139         Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
 140         Iterator it_tasks = this.state.getTaskSymbolTable().getDescriptorsIterator();
 141         while(it_tasks.hasNext()) {
 142             TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 143             if(td.numParameters() > 1) {
 144                 multiparamtds.addElement(td);
 145             }
 146         }
 147         it_tasks = null;
 148
 149         int tryindex = 1;
 150         int bestexetime = Integer.MAX_VALUE;
 151         Random rand = new Random();
 152         // simulate the generated schedulings and try to optimize it
 153         do {
 154             System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 155             System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
 156             gid += newscheduleGraphs.size();
 157             if(scheduleGraphs != null) {
 158                 for(int i = 0; i < scheduleGraphs.size(); i++) {
 159                     Vector<ScheduleNode> tmpgraph = scheduleGraphs.elementAt(i);
 160                     for(int j = 0; j < tmpgraph.size(); j++) {
 161                         tmpgraph.elementAt(j).getEdgeVector().clear();
 162                         tmpgraph.elementAt(j).getInedgeVector().clear();
 163                     }
 164                     tmpgraph.clear();
 165                     tmpgraph = null;
 166                 }
 167                 scheduleGraphs.clear();
 168             }
 169             scheduleGraphs = newscheduleGraphs;
 170             schedulings.clear();
 171             // get scheduling layouts from schedule graphs
 172             for(int i = 0; i < scheduleGraphs.size(); i++) {
 173                 Vector<ScheduleNode> scheduleGraph = scheduleGraphs.elementAt(i);
 174                 Vector<Schedule> tmpscheduling =
 175                     generateScheduling(scheduleGraph, multiparamtds);
 176                 schedulings.add(tmpscheduling);
 177                 scheduleGraph = null;
 178                 tmpscheduling = null;
 179             }
 180             selectedSchedulings.clear();
 181             for(int i = 0; i < selectedSimExeGraphs.size(); i++) {
 182                 selectedSimExeGraphs.elementAt(i).clear();
 183             }
 184             selectedSimExeGraphs.clear();
 185             int tmpexetime = this.scheduleSimulator.simulate(schedulings,
 186                                                              selectedSchedulings,
 187                                                              selectedSimExeGraphs);
 188             if(tmpexetime < bestexetime) {
 189                 bestexetime = tmpexetime;
 190                 if(scheduling != null) {
 191                     scheduling.clear();
 192                     for(int j = 0; j < schedulinggraph.size(); j++) {
 193                         schedulinggraph.elementAt(j).getEdgeVector().clear();
 194                         schedulinggraph.elementAt(j).getInedgeVector().clear();
 195                     }
 196                     schedulinggraph.clear();
 197                 }
 198                 scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0));
 199                 schedulinggraph = scheduleGraphs.elementAt(selectedSchedulings.elementAt(0));
 200                 System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n");
 201                 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 202                 tryindex++;
 203             } else if(tmpexetime == bestexetime) {
 204                 System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n");
 205                 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 206                 tryindex++;
 207                 if((Math.abs(rand.nextInt()) % 100) < this.probThreshold) {
 208                     break;
 209                 }
 210             } else {
 211                 break;
 212             }
 213
 214             // try to optimize the best one scheduling
 215             newscheduleGraphs = optimizeScheduling(scheduleGraphs,
 216                                                    selectedSchedulings,
 217                                                    selectedSimExeGraphs,
 218                                                    gid,
 219                                                    this.scheduleThreshold);
 220             if(tmpexetime < bestexetime) {
 221                 scheduleGraphs.remove(selectedSchedulings.elementAt(0));
 222             }
 223         }while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
 224
 225         if(scheduleGraphs != null) {
 226             scheduleGraphs.clear();
 227         }
 228         scheduleGraphs = null;
 229         newscheduleGraphs = null;
 230         schedulings.clear();
 231         schedulings = null;
 232         selectedSchedulings.clear();
 233         selectedSchedulings = null;
 234         for(int i = 0; i < selectedSimExeGraphs.size(); i++) {
 235             selectedSimExeGraphs.elementAt(i).clear();
 236         }
 237         selectedSimExeGraphs.clear();
 238         selectedSimExeGraphs = null;
 239         multiparamtds.clear();
 240         multiparamtds = null;
 241
 242         System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 243         System.out.print("selected bestexetime: " + bestexetime + "\n");
 244         String path = this.state.outputdir + "scheduling_selected.dot";
 245         SchedulingUtil.printScheduleGraph(path, schedulinggraph);
 246
 247         // Close the streams.
 248         try {
 249             stdout.close();
 250             stdout = null;
 251             System.setOut(origOut);
 252         } catch (Exception e) {
 253             origOut.println("Redirect:  Unable to close files!");
 254         }
 255
 256         schedulinggraph.clear();
 257         schedulinggraph = null;
 258
 259         return scheduling;
 260     }
 261
 262     // for test
 263     // get the distribution info of new search algorithm
 264     public void distribution() {
 265         // Print stuff to the original output and error streams.
 266         // The stuff printed through the 'origOut' and 'origErr' references
 267         // should go to the console on most systems while the messages
 268         // printed through the 'System.out' and 'System.err' will end up in
 269         // the files we created for them.
 270         //origOut.println ("\nRedirect:  Round #2");
 271         //System.out.println ("Test output via 'SimulatorResult.out'.");
 272         //origOut.println ("Test output via 'origOut' reference.");
 273
 274         // Save the current standard input, output, and error streams
 275         // for later restoration.
 276         PrintStream origOut = System.out;
 277
 278         // Create a new output stream for the standard output.
 279         PrintStream stdout  = null;
 280         try {
 281             stdout = new PrintStream(
 282                     new FileOutputStream(this.state.outputdir + "SimulatorResult_"
 283                                          + this.coreNum + ".out"));
 284         } catch (Exception e) {
 285             // Sigh.  Couldn't open the file.
 286             System.out.println("Redirect:  Unable to open output file!");
 287             System.exit(1);
 288         }
 289
 290         // Print stuff to the original output and error streams.
 291         // On most systems all of this will end up on your console when you
 292         // run this application.
 293         //origOut.println ("\nRedirect:  Round #1");
 294         //System.out.println ("Test output via 'System.out'.");
 295         //origOut.println ("Test output via 'origOut' reference.");
 296
 297         // Set the System out and err streams to use our replacements.
 298         System.setOut(stdout);
 299
 300         // generate multiple schedulings
 301         this.scheduleAnalysis.setScheduleThreshold(1000);
 302         this.scheduleAnalysis.schedule(20);
 303         this.generateThreshold = 5;
 304         this.probThreshold = 0;
 305
 306         Vector<Vector<ScheduleNode>> scheduleGraphs = null;
 307         Vector<Vector<ScheduleNode>> totestscheduleGraphs =
 308             this.scheduleAnalysis.getScheduleGraphs();
 309         Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
 310         Vector<Integer> selectedSchedulings = new Vector<Integer>();
 311         Vector<Vector<SimExecutionEdge>> selectedSimExeGraphs =
 312             new Vector<Vector<SimExecutionEdge>>();
 313
 314         // check all multi-parameter tasks
 315         Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
 316         Iterator it_tasks = this.state.getTaskSymbolTable().getDescriptorsIterator();
 317         while(it_tasks.hasNext()) {
 318             TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 319             if(td.numParameters() > 1) {
 320                 multiparamtds.addElement(td);
 321             }
 322         }
 323         it_tasks = null;
 324
 325         File file=new File(this.state.outputdir + "distributeinfo_s_" + this.coreNum + ".out");
 326         FileOutputStream dotstream = null;
 327         File file2=new File(this.state.outputdir + "distributeinfo_o_" + this.coreNum + ".out");
 328         FileOutputStream dotstream2 = null;
 329         try {
 330             dotstream = new FileOutputStream(file,false);
 331             dotstream2 = new FileOutputStream(file2,false);
 332         } catch (Exception e) {
 333             e.printStackTrace();
 334             System.exit(-1);
 335         }
 336         PrintWriter output = new java.io.PrintWriter(dotstream, true);
 337         PrintWriter output2 = new java.io.PrintWriter(dotstream2, true);
 338         output.println("start time(1,000,000 cycles): " + totestscheduleGraphs.size());
 339         output2.println("optimized time(1,000,000 cycles): " + totestscheduleGraphs.size());
 340         for(int ii = 0; ii < 1/*totestscheduleGraphs.size()*/; ii++) {
 341             Vector<Vector<ScheduleNode>> newscheduleGraphs =
 342                 new Vector<Vector<ScheduleNode>>();
 343             newscheduleGraphs.add(totestscheduleGraphs.elementAt(ii));
 344             int tryindex = 1;
 345             int bestexetime = Integer.MAX_VALUE;
 346             int gid = 1;
 347             Vector<Schedule> scheduling = null;
 348             Vector<ScheduleNode> schedulinggraph = null;
 349             boolean isfirst = true;
 350             Random rand = new Random();
 351             // simulate the generated schedulings and try to optimize it
 352             System.out.print("=========================================================\n");
 353             System.out.print("# " + ii + ": \n");
 354             do {
 355                 System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 356                 System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
 357                 gid += newscheduleGraphs.size();
 358                 if(scheduleGraphs != null) {
 359                     for(int i = 0; i < scheduleGraphs.size(); i++) {
 360                         Vector<ScheduleNode> tmpgraph = scheduleGraphs.elementAt(i);
 361                         for(int j = 0; j < tmpgraph.size(); j++) {
 362                             ScheduleNode snode = tmpgraph.elementAt(j);
 363                             snode.getEdgeVector().clear();
 364                             snode.getInedgeVector().clear();
 365                             snode.getScheduleEdges().clear();
 366                             snode.getClassNodes().clear();
 367                         }
 368                         tmpgraph.clear();
 369                         tmpgraph = null;
 370                     }
 371                     scheduleGraphs.clear();
 372                 }
 373                 scheduleGraphs = newscheduleGraphs;
 374                 schedulings.clear();
 375                 // get scheduling layouts from schedule graphs
 376                 for(int i = 0; i < scheduleGraphs.size(); i++) {
 377                     Vector<ScheduleNode> scheduleGraph = scheduleGraphs.elementAt(i);
 378                     Vector<Schedule> tmpscheduling =
 379                         generateScheduling(scheduleGraph, multiparamtds);
 380                     schedulings.add(tmpscheduling);
 381                     scheduleGraph = null;
 382                     tmpscheduling = null;
 383                 }
 384                 selectedSchedulings.clear();
 385                 for(int i = 0; i < selectedSimExeGraphs.size(); i++) {
 386                     selectedSimExeGraphs.elementAt(i).clear();
 387                 }
 388                 selectedSimExeGraphs.clear();
 389                 int tmpexetime = this.scheduleSimulator.simulate(schedulings,
 390                                                                  selectedSchedulings,
 391                                                                  selectedSimExeGraphs);
 392                 if(isfirst) {
 393                     output.println(((float)tmpexetime/1000000));
 394                     isfirst = false;
 395                 }
 396                 if(tmpexetime < bestexetime) {
 397                     bestexetime = tmpexetime;
 398                     if(scheduling != null) {
 399                         scheduling.clear();
 400                         for(int j = 0; j < schedulinggraph.size(); j++) {
 401                             ScheduleNode snode = schedulinggraph.elementAt(j);
 402                             snode.getEdgeVector().clear();
 403                             snode.getInedgeVector().clear();
 404                             snode.getScheduleEdges().clear();
 405                             snode.getClassNodes().clear();
 406                         }
 407                         schedulinggraph.clear();
 408                     }
 409                     scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0));
 410                     schedulinggraph = scheduleGraphs.elementAt(selectedSchedulings.elementAt(0));
 411                     tryindex++;
 412                     System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n");
 413                     System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 414                 } else if(tmpexetime == bestexetime) {
 415                     System.out.print("end of: #" + tryindex + " (bestexetime: " + bestexetime + ")\n");
 416                     System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 417                     tryindex++;
 418                     if((Math.abs(rand.nextInt()) % 100) < this.probThreshold) {
 419                         break;
 420                     }
 421                 } else {
 422                     break;
 423                 }
 424
 425                 // try to optimize theschedulings best one scheduling
 426                 newscheduleGraphs = optimizeScheduling(scheduleGraphs,
 427                                                        selectedSchedulings,
 428                                                        selectedSimExeGraphs,
 429                                                        gid,
 430                                                        this.scheduleThreshold);
 431                 if(tmpexetime < bestexetime) {
 432                     scheduleGraphs.remove(selectedSchedulings.elementAt(0));
 433                 }
 434             }while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
 435
 436             scheduleGraphs.clear();
 437             scheduleGraphs = null;
 438             scheduling = null;
 439             schedulinggraph = null;
 440             if(newscheduleGraphs != null) {
 441                 newscheduleGraphs.clear();
 442             }
 443             newscheduleGraphs = null;
 444             totestscheduleGraphs.elementAt(ii).clear();
 445             for(int i = 0; i < schedulings.size(); i++) {
 446                 schedulings.elementAt(i).clear();
 447             }
 448             schedulings.clear();
 449             selectedSchedulings.clear();
 450             for(int i = 0; i < selectedSimExeGraphs.size(); i++) {
 451                 selectedSimExeGraphs.elementAt(i).clear();
 452             }
 453             selectedSimExeGraphs.clear();
 454
 455             output2.println(((float)bestexetime/1000000));
 456             System.out.print("=========================================================\n");
 457         }
 458
 459         if(scheduleGraphs != null) {
 460             scheduleGraphs.clear();
 461         }
 462         scheduleGraphs = null;
 463         totestscheduleGraphs = null;
 464         for(int i = 0; i < schedulings.size(); i++) {
 465             schedulings.elementAt(i).clear();
 466         }
 467         schedulings.clear();
 468         schedulings = null;
 469         selectedSchedulings.clear();
 470         selectedSchedulings = null;
 471         selectedSimExeGraphs.clear();
 472         selectedSimExeGraphs = null;
 473         multiparamtds.clear();
 474         multiparamtds = null;
 475
 476         // Close the streams.
 477         try {
 478             output.close();
 479             stdout.close();
 480             output = null;
 481             stdout = null;
 482             System.setOut(origOut);
 483         } catch (Exception e) {
 484             origOut.println("Redirect:  Unable to close files!");
 485         }
 486
 487         return;
 488     }
 489
 490     private Vector<Vector<ScheduleNode>> optimizeScheduling(Vector<Vector<ScheduleNode>> scheduleGraphs,
 491                                                             Vector<Integer> selectedScheduleGraphs,
 492                                                             Vector<Vector<SimExecutionEdge>> selectedSimExeGraphs,
 493                                                             int gid,
 494                                                             int count) {
 495         if(this.coreNum == 1) {
 496             // single core
 497             return null;
 498         }
 499
 500         Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
 501         int lgid = gid;
 502         int left = count;
 503
 504         for(int i = 0; i < selectedScheduleGraphs.size(); i++) {
 505             Vector<ScheduleNode> schedulegraph = scheduleGraphs.elementAt(
 506                     selectedScheduleGraphs.elementAt(i));
 507             Vector<SimExecutionEdge> simexegraph = selectedSimExeGraphs.elementAt(i);
 508             Vector<SimExecutionEdge> criticalPath = analyzeCriticalPath(simexegraph);
 509             Vector<Vector<ScheduleNode>> tmposchedulegraphs = optimizeCriticalPath(schedulegraph,
 510                                                                                    criticalPath,
 511                                                                                    lgid,
 512                                                                                    left);
 513             if(tmposchedulegraphs != null) {
 514                 if(optimizeschedulegraphs == null) {
 515                     optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
 516                 }
 517                 optimizeschedulegraphs.addAll(tmposchedulegraphs);
 518                 lgid += tmposchedulegraphs.size();
 519                 left -= tmposchedulegraphs.size();
 520                 if(left == 0) {
 521                     schedulegraph = null;
 522                     simexegraph = null;
 523                     criticalPath = null;
 524                     tmposchedulegraphs = null;
 525                     break;
 526                 }
 527             }
 528             schedulegraph = null;
 529             simexegraph = null;
 530             criticalPath = null;
 531             tmposchedulegraphs = null;
 532         }
 533
 534         return optimizeschedulegraphs;
 535     }
 536
 537     private Vector<SimExecutionEdge> analyzeCriticalPath(Vector<SimExecutionEdge> simexegraph) {
 538         // first figure out the critical path
 539         Vector<SimExecutionEdge> criticalPath = new Vector<SimExecutionEdge>();
 540         SimExecutionNode senode = (SimExecutionNode)simexegraph.elementAt(0).getSource();
 541         getCriticalPath(senode, criticalPath);
 542         computeBestStartPoint(criticalPath);
 543
 544         return criticalPath;
 545     }
 546
 547     private void computeBestStartPoint(Vector<SimExecutionEdge> criticalPath) {
 548         // calculate the earliest start time of each task on the critial path
 549         for(int i = 0; i < criticalPath.size(); i++) {
 550             SimExecutionEdge seedge = criticalPath.elementAt(i);
 551             Vector<SimExecutionEdge> predicates = seedge.getPredicates();
 552             if(predicates != null) {
 553                 // have predicates
 554                 int starttime = 0;
 555                 // check the latest finish time of all the predicates
 556                 for(int j = 0; j < predicates.size(); j++) {
 557                     SimExecutionEdge predicate = predicates.elementAt(j);
 558                     int tmptime = predicate.getBestStartPoint() + predicate.getWeight();
 559                     if(tmptime > starttime) {
 560                         starttime = tmptime;
 561                         seedge.setLastpredicateEdge(predicate);
 562                         if(predicate.getTd() != null) {
 563                             seedge.setLastpredicateNode((SimExecutionNode)predicate.getTarget());
 564                         } else {
 565                             // transfer edge
 566                             seedge.setLastpredicateNode((SimExecutionNode)predicate.getSource());
 567                         }
 568                     }
 569                 }
 570                 seedge.setBestStartPoint(starttime);
 571             } else if(seedge.getSource().getInedgeVector().size() > 0) {
 572                 // should have only one in edge
 573                 int starttime = ((SimExecutionNode)seedge.getSource()).getTimepoint();
 574                 seedge.setBestStartPoint(starttime);
 575             } else {
 576                 // no predicates
 577                 seedge.setBestStartPoint(0);
 578             }
 579             predicates = null;
 580         }
 581     }
 582
 583     // TODO: currently only get one critical path. It's possible that there are
 584     // multiple critical paths and some of them can not be optimized while others
 585     // can. Need to fix up for this situation.
 586     private int getCriticalPath(SimExecutionNode senode,
 587                                 Vector<SimExecutionEdge> criticalPath) {
 588         Vector<SimExecutionEdge> edges = (Vector<SimExecutionEdge>)senode.getEdgeVector();
 589         if((edges == null) || (edges.size() == 0)) {
 590             edges = null;
 591             return 0;
 592         }
 593         Vector<SimExecutionEdge> subcriticalpath = new Vector<SimExecutionEdge>();
 594         SimExecutionEdge edge = edges.elementAt(0);
 595         int sum = edge.getWeight() + getCriticalPath((SimExecutionNode)edge.getTarget(),
 596                                                       subcriticalpath);
 597         criticalPath.clear();
 598         criticalPath.add(edge);
 599         criticalPath.addAll(subcriticalpath);
 600         for(int i = 1; i < edges.size(); i++) {
 601             edge = edges.elementAt(i);
 602             subcriticalpath.clear();
 603             int tmpsum = edge.getWeight()
 604                        + getCriticalPath((SimExecutionNode)edge.getTarget(),
 605                                          subcriticalpath);
 606             if(tmpsum > sum) {
 607                 // find a longer path
 608                 sum = tmpsum;
 609                 criticalPath.clear();
 610                 criticalPath.add(edge);
 611                 criticalPath.addAll(subcriticalpath);
 612             }
 613         }
 614         edges = null;
 615         subcriticalpath.clear();
 616         subcriticalpath = null;
 617         return sum;
 618     }
 619
 620     private Vector<Vector<ScheduleNode>> optimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
 621                                                               Vector<SimExecutionEdge> criticalPath,
 622                                                               int gid,
 623                                                               int count) {
 624         Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
 625         int lgid = gid;
 626         int left = count;
 627
 628         // for test, print out the criticalPath
 629         if(this.state.PRINTCRITICALPATH) {
 630             SchedulingUtil.printCriticalPath(this.state.outputdir + "criticalpath_" + lgid + ".dot",
 631                                              criticalPath);
 632         }
 633
 634         // first check all seedges whose real start point is late than predicted
 635         // earliest start time and group them
 636         int opcheckpoint = Integer.MAX_VALUE;
 637         Vector<Integer> sparecores = null;
 638         // first group according to core index,
 639         // then group according to task type
 640         Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>> tooptimize =
 641             new Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>>();
 642         for(int i = 0; i < criticalPath.size(); i++) {
 643             SimExecutionEdge seedge = criticalPath.elementAt(i);
 644             int starttime = seedge.getBestStartPoint();
 645             if(starttime < ((SimExecutionNode)seedge.getSource()).getTimepoint()) {
 646                 // no restrictions due to data dependencies
 647                 // have potential to be parallelled and start execution earlier
 648                 seedge.setFixedTime(false);
 649                 // consider to optimize it only when its predicates can NOT
 650                 // be optimized, otherwise first considering optimize its predicates
 651                 SimExecutionEdge lastpredicateedge = seedge.getLastpredicateEdge();
 652                 if(lastpredicateedge.isFixedTime()) {
 653                     if(opcheckpoint >= starttime) {
 654                         // only consider the tasks with smallest best start time
 655                         if(opcheckpoint > starttime) {
 656                             tooptimize.clear();
 657                             opcheckpoint = starttime;
 658                             SimExecutionNode lastpredicatenode = seedge.getLastpredicateNode();
 659                             int timepoint = lastpredicatenode.getTimepoint();
 660                             if(lastpredicateedge.getTd() == null) {
 661                                 // transfer edge
 662                                 timepoint += lastpredicateedge.getWeight();
 663                             }
 664                             // mapping to critical path
 665                             for(int index = 0; index < criticalPath.size(); index++) {
 666                                 SimExecutionEdge tmpseedge = criticalPath.elementAt(index);
 667                                 SimExecutionNode tmpsenode =
 668                                     (SimExecutionNode)tmpseedge.getTarget();
 669                                 if(tmpsenode.getTimepoint() > timepoint) {
 670                                     // get the spare core info
 671                                     sparecores = tmpsenode.getSpareCores();
 672                                     break;
 673                                 }
 674                             }
 675                         }
 676                         int corenum = seedge.getCoreNum();
 677                         if(!tooptimize.containsKey(corenum)) {
 678                             tooptimize.put(corenum,
 679                                     new Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>());
 680                         }
 681                         if(!tooptimize.get(corenum).containsKey(seedge.getTd())) {
 682                             tooptimize.get(corenum).put(seedge.getTd(),
 683                                     new Vector<SimExecutionEdge>());
 684                         }
 685                         tooptimize.get(corenum).get(seedge.getTd()).add(seedge);
 686                     }
 687                 }
 688             }
 689         }
 690
 691         if(tooptimize.size() > 0) {
 692             Iterator<Integer> it_cores = tooptimize.keySet().iterator();
 693             // check if it is possible to optimize these tasks
 694             if((sparecores == null) || (sparecores.size() == 0)) {
 695                 // lack of spare cores
 696                 while(it_cores.hasNext()) {
 697                     int corenum = it_cores.next();
 698                     Hashtable<TaskDescriptor, Vector<SimExecutionEdge>> candidatetasks =
 699                         tooptimize.get(corenum);
 700                     if(candidatetasks.keySet().size() > 1) {
 701                         // there are multiple tasks could be optimized to start from
 702                         // this timepoint, try to change original execution order
 703                         Iterator<TaskDescriptor> it_tds = candidatetasks.keySet().iterator();
 704                         TaskDescriptor td = null;
 705                         int starttime = Integer.MAX_VALUE;
 706                         do {
 707                             TaskDescriptor tmptd = it_tds.next();
 708                             Vector<SimExecutionEdge> seedges = candidatetasks.get(td);
 709                             int tmptime = ((SimExecutionNode)seedges.elementAt(0).getSource()).getTimepoint();
 710                             for(int i = 1; i < seedges.size(); i++) {
 711                                 int ttime = ((SimExecutionNode)seedges.elementAt(i).getSource()).getTimepoint();
 712                                 if(ttime < tmptime) {
 713                                     tmptime = ttime;
 714                                 }
 715                             }
 716                             if(tmptime < starttime) {
 717                                 starttime = tmptime;
 718                                 td = tmptd;
 719                             }
 720                             seedges = null;
 721                         }while(it_tds.hasNext());
 722                         it_tds = null;
 723                         // TODO: only consider non-multi-param tasks currently
 724                         if(td.numParameters() == 1) {
 725                             Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>> tooptimize2 =
 726                                 new Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>>();
 727                             tooptimize2.put(corenum, candidatetasks);
 728                             Vector<Vector<ScheduleNode>> ops = innerOptimizeCriticalPath(scheduleGraph,
 729                                                                                          tooptimize2,
 730                                                                                          null,
 731                                                                                          lgid,
 732                                                                                          left);
 733                             if(ops != null) {
 734                                 if(optimizeschedulegraphs == null) {
 735                                     optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
 736                                 }
 737                                 optimizeschedulegraphs.addAll(ops);
 738                                 lgid += optimizeschedulegraphs.size();
 739                                 left -= optimizeschedulegraphs.size();
 740                             }
 741                             tooptimize2.clear();
 742                             tooptimize2 = null;
 743                             ops = null;
 744                         }
 745                     }
 746                     candidatetasks = null;
 747                 }
 748
 749                 if(left == 0) {
 750                     it_cores = null;
 751                     return optimizeschedulegraphs;
 752                 }
 753
 754                 // flush the dependences and earliest start time
 755                 it_cores = tooptimize.keySet().iterator();
 756                 while(it_cores.hasNext()) {
 757                     Hashtable<TaskDescriptor, Vector<SimExecutionEdge>> candidatetasks =
 758                         tooptimize.get(it_cores.next());
 759                     Iterator<Vector<SimExecutionEdge>> it_edgevecs =
 760                         candidatetasks.values().iterator();
 761                     while(it_edgevecs.hasNext()) {
 762                         Vector<SimExecutionEdge> edgevec = it_edgevecs.next();
 763                         for(int j = 0; j < edgevec.size(); j++) {
 764                             SimExecutionEdge edge = edgevec.elementAt(j);
 765                             SimExecutionEdge lastpredicateedge = edge.getLastpredicateEdge();
 766                             SimExecutionNode lastpredicatenode = edge.getLastpredicateNode();
 767                             // if(edge.getCoreNum() != lastpredicate.getCoreNum()) // should never hit this
 768                             int timepoint = lastpredicatenode.getTimepoint();
 769                             if(lastpredicateedge.getTd() == null) {
 770                                 // transfer edge
 771                                 timepoint += lastpredicateedge.getWeight();
 772                             }
 773                             // mapping to critical path
 774                             for(int index = 0; index < criticalPath.size(); index++) {
 775                                 SimExecutionEdge tmpseedge = criticalPath.elementAt(index);
 776                                 SimExecutionNode tmpsenode =
 777                                     (SimExecutionNode)tmpseedge.getTarget();
 778                                 if(tmpsenode.getTimepoint() > timepoint) {
 779                                     // update the predicate info
 780                                     if(edge.getPredicates() != null) {
 781                                         edge.getPredicates().remove(lastpredicateedge);
 782                                     }
 783                                     edge.addPredicate(criticalPath.elementAt(index));
 784                                     break;
 785                                 }
 786                             }
 787                         }
 788                         edgevec = null;
 789                     }
 790                     candidatetasks = null;
 791                     it_edgevecs = null;
 792                 }
 793                 it_cores = null;
 794                 computeBestStartPoint(criticalPath);
 795                 Vector<Vector<ScheduleNode>> ops = optimizeCriticalPath(scheduleGraph,
 796                                                                         criticalPath,
 797                                                                         lgid,
 798                                                                         left);
 799                 if(ops != null) {
 800                     if(optimizeschedulegraphs == null) {
 801                         optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
 802                     }
 803                     optimizeschedulegraphs.addAll(ops);
 804                 }
 805                 ops = null;
 806             } else {
 807                 // there are spare cores, try to reorganize the tasks to the spare
 808                 // cores
 809                 Vector<Vector<ScheduleNode>> ops = innerOptimizeCriticalPath(scheduleGraph,
 810                                                                              tooptimize,
 811                                                                              sparecores,
 812                                                                              lgid,
 813                                                                              left);
 814                 if(ops != null) {
 815                     if(optimizeschedulegraphs == null) {
 816                         optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
 817                     }
 818                     optimizeschedulegraphs.addAll(ops);
 819                 }
 820                 ops = null;
 821             }
 822         }
 823         sparecores = null;
 824         tooptimize.clear();
 825         tooptimize = null;
 826
 827         return optimizeschedulegraphs;
 828     }
 829
 830     private Vector<Vector<ScheduleNode>> innerOptimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
 831                                                                    Hashtable<Integer, Hashtable<TaskDescriptor, Vector<SimExecutionEdge>>> tooptimize,
 832                                                                    Vector<Integer> sparecores,
 833                                                                    int gid,
 834                                                                    int count) {
 835         int lgid = gid;
 836         int left = count;
 837         Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
 838
 839         // first clone the whole graph
 840         Vector<ScheduleNode> newscheduleGraph =
 841             cloneScheduleGraph(scheduleGraph, lgid);
 842
 843         // these nodes are root nodes
 844         Vector<ScheduleNode> roots = new Vector<ScheduleNode>();
 845         for(int i = 0; i < newscheduleGraph.size(); i++) {
 846             if((sparecores == null) || (sparecores.contains(i))) {
 847                 roots.add(newscheduleGraph.elementAt(i));
 848             }
 849         }
 850
 851         // map the tasks associated to SimExecutionedges to original
 852         // ClassNode in the ScheduleGraph and split them from previous
 853         // ScheduleGraph
 854         Vector<ScheduleNode> tocombines = new Vector<ScheduleNode>();
 855         Iterator<Integer> it_cores = tooptimize.keySet().iterator();
 856         while(it_cores.hasNext()) {
 857             int corenum = it_cores.next();
 858             Hashtable<TaskDescriptor, Vector<SimExecutionEdge>> candidatetasks =
 859                 tooptimize.get(corenum);
 860             Iterator<TaskDescriptor> it_tds = candidatetasks.keySet().iterator();
 861             while(it_tds.hasNext()) {
 862                 TaskDescriptor td = it_tds.next();
 863                 int numtosplit = candidatetasks.get(td).size();
 864                 // TODO: currently do not consider multi-param tasks
 865                 if(td.numParameters() == 1) {
 866                     ClassDescriptor cd = td.getParamType(0).getClassDesc();
 867                     ScheduleNode snode = newscheduleGraph.elementAt(corenum); // corresponding ScheduleNode
 868                     Iterator<ClassNode> it_cnodes = snode.getClassNodesIterator();
 869                     Vector<ClassNode> tosplit = new Vector<ClassNode>();
 870                     while((numtosplit > 0) && (it_cnodes.hasNext())) {
 871                         ClassNode cnode = it_cnodes.next();
 872                         if(cnode.getClassDescriptor().equals(cd)) {
 873                             tosplit.add(cnode);
 874                             numtosplit--;
 875                         }
 876                     }
 877                     it_cnodes = null;
 878                     // split these node
 879                     for(int i = 0; i < tosplit.size(); i++) {
 880                         ScheduleNode splitnode = snode.spliteClassNode(tosplit.elementAt(i));
 881                         newscheduleGraph.add(splitnode);
 882                         tocombines.add(splitnode);
 883                     }
 884                     tosplit = null;
 885                 }
 886             }
 887             candidatetasks = null;
 888             it_tds = null;
 889         }
 890         it_cores = null;
 891
 892         if(tocombines.size() == 0) {
 893             return optimizeschedulegraphs;
 894         }
 895
 896         SchedulingUtil.assignCids(newscheduleGraph);
 897
 898         // get all the ScheduleEdge
 899         Vector<ScheduleEdge> scheduleEdges = new Vector<ScheduleEdge>();
 900         for(int i= 0; i < newscheduleGraph.size(); i++) {
 901             scheduleEdges.addAll((Vector<ScheduleEdge>)newscheduleGraph.elementAt(i).getEdgeVector());
 902         }
 903
 904         Vector<Vector<ScheduleNode>> rootNodes =
 905             SchedulingUtil.rangeScheduleNodes(roots);
 906         Vector<Vector<ScheduleNode>> nodes2combine =
 907             SchedulingUtil.rangeScheduleNodes(tocombines);
 908
 909         CombinationUtil.CombineGenerator cGen =
 910             CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine);
 911         Random rand = new Random();
 912         while ((left > 0) && (cGen.nextGen())) {
 913             if(Math.abs(rand.nextInt()) % 100 > this.generateThreshold) {
 914                 Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
 915                 Vector<ScheduleNode> sNodes = SchedulingUtil.generateScheduleGraph(this.state,
 916                                                                                    newscheduleGraph,
 917                                                                                    scheduleEdges,
 918                                                                                    rootNodes,
 919                                                                                    combine,
 920                                                                                    lgid++);
 921                 if(optimizeschedulegraphs == null) {
 922                     optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
 923                 }
 924                 optimizeschedulegraphs.add(sNodes);
 925                 combine = null;
 926                 sNodes = null;
 927                 left--;
 928             }
 929         }
 930         cGen.clear();
 931         rootNodes = null;
 932         nodes2combine = null;
 933         newscheduleGraph = null;
 934         scheduleEdges.clear();
 935         scheduleEdges = null;
 936         roots = null;
 937         tocombines = null;
 938
 939         return optimizeschedulegraphs;
 940     }
 941
 942     private Vector<ScheduleNode> cloneScheduleGraph(Vector<ScheduleNode> scheduleGraph,
 943                                                     int gid) {
 944         Vector<ScheduleNode> result = new Vector<ScheduleNode>();
 945
 946         // get all the ScheduleEdge
 947         Vector<ScheduleEdge> scheduleEdges = new Vector<ScheduleEdge>();
 948         for(int i= 0; i < scheduleGraph.size(); i++) {
 949             scheduleEdges.addAll((Vector<ScheduleEdge>)scheduleGraph.elementAt(i).getEdgeVector());
 950         }
 951         Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash =
 952             new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
 953         Hashtable<ScheduleNode, ScheduleNode> sn2sn =
 954             new Hashtable<ScheduleNode, ScheduleNode>();
 955         SchedulingUtil.cloneScheduleGraph(scheduleGraph,
 956                                           scheduleEdges,
 957                                           sn2hash,
 958                                           sn2sn,
 959                                           result,
 960                                           gid);
 961
 962         SchedulingUtil.assignCids(result);
 963         scheduleEdges.clear();
 964         scheduleEdges = null;
 965         sn2hash.clear();
 966         sn2hash = null;
 967         sn2sn.clear();
 968         sn2sn = null;
 969
 970         return result;
 971     }
 972
 973     private Vector<Schedule> generateScheduling(Vector<ScheduleNode> scheduleGraph,
 974                                                 Vector<TaskDescriptor> multiparamtds) {
 975         Hashtable<TaskDescriptor, Vector<Schedule>> td2cores =
 976             new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks reside on which cores
 977         Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
 978         // for each ScheduleNode create a schedule node representing a core
 979         Hashtable<ScheduleNode, Integer> sn2coreNum =
 980             new Hashtable<ScheduleNode, Integer>();
 981         int j = 0;
 982         for(j = 0; j < scheduleGraph.size(); j++) {
 983             sn2coreNum.put(scheduleGraph.elementAt(j), j);
 984         }
 985         int startupcore = 0;
 986         boolean setstartupcore = false;
 987         Schedule startup = null;
 988         int gid = scheduleGraph.elementAt(0).getGid();
 989         for(j = 0; j < scheduleGraph.size(); j++) {
 990             Schedule tmpSchedule = new Schedule(j, gid);
 991             ScheduleNode sn = scheduleGraph.elementAt(j);
 992
 993             Vector<ClassNode> cNodes = sn.getClassNodes();
 994             for(int k = 0; k < cNodes.size(); k++) {
 995                 Iterator it_flags = cNodes.elementAt(k).getFlags();
 996                 while(it_flags.hasNext()) {
 997                     FlagState fs = (FlagState)it_flags.next();
 998                     Iterator it_edges = fs.edges();
 999                     while(it_edges.hasNext()) {
1000                         TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
1001                         tmpSchedule.addTask(td);
1002                         if(!td2cores.containsKey(td)) {
1003                             td2cores.put(td, new Vector<Schedule>());
1004                         }
1005                         Vector<Schedule> tmpcores = td2cores.get(td);
1006                         if(!tmpcores.contains(tmpSchedule)) {
1007                             tmpcores.add(tmpSchedule);
1008                         }
1009                         tmpcores = null;
1010                         // if the FlagState can be fed to some multi-param tasks,
1011                         // need to record corresponding ally cores later
1012                         if(td.numParameters() > 1) {
1013                             tmpSchedule.addFState4TD(td, fs);
1014                         }
1015                         if(td.getParamType(0).getClassDesc().getSymbol().equals(
1016                                 TypeUtil.StartupClass)) {
1017                             assert(!setstartupcore);
1018                             startupcore = j;
1019                             startup = tmpSchedule;
1020                             setstartupcore = true;
1021                         }
1022                     }
1023                     it_edges = null;
1024                 }
1025                 it_flags = null;
1026             }
1027             cNodes = null;
1028
1029             //  For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
1030             Iterator it_edges = sn.edges();
1031             while(it_edges.hasNext()) {
1032                 ScheduleEdge se = (ScheduleEdge)it_edges.next();
1033                 ScheduleNode target = (ScheduleNode)se.getTarget();
1034                 Integer targetcore = sn2coreNum.get(target);
1035                 switch(se.getType()) {
1036                 case ScheduleEdge.NEWEDGE: {
1037                     for(int k = 0; k < se.getNewRate(); k++) {
1038                         tmpSchedule.addTargetCore(se.getFstate(), targetcore);
1039                     }
1040                     break;
1041                 }
1042
1043                 case ScheduleEdge.TRANSEDGE: {
1044                     // 'transmit' edge
1045                     tmpSchedule.addTargetCore(se.getFstate(),
1046                                               targetcore,
1047                                               se.getTargetFState());
1048                     // check if missed some FlagState associated with some multi-parameter
1049                     // task, which has been cloned when splitting a ClassNode
1050                     FlagState fs = se.getSourceFState();
1051                     FlagState tfs = se.getTargetFState();
1052                     Iterator it = tfs.edges();
1053                     while(it.hasNext()) {
1054                         TaskDescriptor td = ((FEdge)it.next()).getTask();
1055                         if(td.numParameters() > 1) {
1056                             if(tmpSchedule.getTasks().contains(td)) {
1057                                 tmpSchedule.addFState4TD(td, fs);
1058                             }
1059                         }
1060                     }
1061                     break;
1062                 }
1063                 }
1064             }
1065             it_edges = sn.getScheduleEdgesIterator();
1066             while(it_edges.hasNext()) {
1067                 ScheduleEdge se = (ScheduleEdge)it_edges.next();
1068                 switch(se.getType()) {
1069                 case ScheduleEdge.NEWEDGE: {
1070                     for(int k = 0; k < se.getNewRate(); k++) {
1071                         tmpSchedule.addTargetCore(se.getFstate(), j);
1072                     }
1073                     break;
1074                 }
1075
1076                 case ScheduleEdge.TRANSEDGE: {
1077                     // 'transmit' edge
1078                     tmpSchedule.addTargetCore(se.getFstate(),
1079                                               j,
1080                                               se.getTargetFState());
1081                     break;
1082                 }
1083                 }
1084             }
1085             it_edges = null;
1086             scheduling.add(tmpSchedule);
1087         }
1088
1089         int number = this.coreNum;
1090         if(scheduling.size() < number) {
1091             number = scheduling.size();
1092         }
1093
1094         // set up all the associate ally cores
1095         if(multiparamtds.size() > 0) {
1096             for(j = 0; j < multiparamtds.size(); ++j) {
1097                 TaskDescriptor td = multiparamtds.elementAt(j);
1098                 Vector<FEdge> fes =
1099                     (Vector<FEdge>) this.taskAnalysis.getFEdgesFromTD(td);
1100                 Vector<Schedule> cores = td2cores.get(td);
1101                 for(int k = 0; k < cores.size(); ++k) {
1102                     Schedule tmpSchedule = cores.elementAt(k);
1103
1104                     for(int h = 0; h < fes.size(); ++h) {
1105                         FEdge tmpfe = fes.elementAt(h);
1106                         FlagState tmpfs = (FlagState)tmpfe.getTarget();
1107                         Vector<TaskDescriptor> tmptds = new Vector<TaskDescriptor>();
1108                         if((tmpSchedule.getTargetCoreTable() == null)
1109                                 || (!tmpSchedule.getTargetCoreTable().containsKey(tmpfs))) {
1110                             // add up all possible cores' info
1111                             Iterator it_edges = tmpfs.edges();
1112                             while(it_edges.hasNext()) {
1113                                 TaskDescriptor tmptd = ((FEdge)it_edges.next()).getTask();
1114                                 if(!tmptds.contains(tmptd)) {
1115                                     tmptds.add(tmptd);
1116                                     Vector<Schedule> tmpcores = td2cores.get(tmptd);
1117                                     for(int m = 0; m < tmpcores.size(); ++m) {
1118                                         if(m != tmpSchedule.getCoreNum()) {
1119                                             // if the FlagState can be fed to some multi-param tasks,
1120                                             // need to record corresponding ally cores later
1121                                             if(tmptd.numParameters() > 1) {
1122                                                 tmpSchedule.addAllyCore(tmpfs,
1123                                                                         tmpcores.elementAt(m).getCoreNum());
1124                                             } else {
1125                                                 tmpSchedule.addTargetCore(tmpfs,
1126                                                                           tmpcores.elementAt(m).getCoreNum());
1127                                             }
1128                                         }
1129                                     }
1130                                     tmpcores = null;
1131                                 }
1132                             }
1133                             it_edges = null;
1134                         }
1135                         tmptds = null;
1136                     }
1137
1138                     if(cores.size() > 1) {
1139                         Vector<FlagState> tmpfss = tmpSchedule.getFStates4TD(td);
1140                         for(int h = 0; h < tmpfss.size(); ++h) {
1141                             for(int l = 0; l < cores.size(); ++l) {
1142                                 if(l != k) {
1143                                     tmpSchedule.addAllyCore(tmpfss.elementAt(h),
1144                                                             cores.elementAt(l).getCoreNum());
1145                                 }
1146                             }
1147                         }
1148                         tmpfss = null;
1149                     }
1150                 }
1151                 fes = null;
1152                 cores = null;
1153             }
1154         }
1155         td2cores = null;
1156         sn2coreNum = null;
1157
1158         return scheduling;
1159     }
1160 }