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.LinkedList;
  10 import java.util.Queue;
  11 import java.util.Random;
  12 import java.util.Vector;
  13
  14 import Analysis.OwnershipAnalysis.OwnershipAnalysis;
  15 import Analysis.TaskStateAnalysis.FEdge;
  16 import Analysis.TaskStateAnalysis.FlagState;
  17 import Analysis.TaskStateAnalysis.TaskAnalysis;
  18 import IR.ClassDescriptor;
  19 import IR.State;
  20 import IR.TaskDescriptor;
  21 import IR.TypeUtil;
  22
  23 public class MCImplSynthesis {
  24
  25   State state;
  26   ScheduleAnalysis scheduleAnalysis;
  27   TaskAnalysis taskAnalysis;
  28   OwnershipAnalysis ownershipAnalysis;
  29   ScheduleSimulator scheduleSimulator;
  30
  31   int coreNum;
  32   int scheduleThreshold; // # of starting points generated by schedule analysis
  33   int probThreshold; // the probability to stop when no accelaration achieved
  34                      // in the directed simulated annealing
  35   int generateThreshold; // how many optimized implementation generated in
  36                          // each iteration of the directed simulated annealing
  37   int skipThreshold; // the probability to skip to producing more optimization
  38                      // with the same root sets(see ScheduleAnalysis.coremapping)
  39
  40   public MCImplSynthesis(State state,
  41                          TaskAnalysis ta,
  42                          OwnershipAnalysis oa) {
  43     this.state = state;
  44     this.coreNum = state.CORENUM;
  45     this.taskAnalysis = ta;
  46     this.ownershipAnalysis = oa;
  47     this.scheduleAnalysis = new ScheduleAnalysis(state,
  48                                                  ta);
  49     this.scheduleAnalysis.setCoreNum(this.coreNum);
  50     this.scheduleSimulator = new ScheduleSimulator(this.coreNum,
  51                                                    state,
  52                                                    ta);
  53     this.scheduleThreshold = 1000;
  54     this.probThreshold = 0;
  55     this.generateThreshold = 30;
  56     this.skipThreshold = 100; // never skip // 30;
  57   }
  58
  59   public int getCoreNum() {
  60     return this.scheduleAnalysis.getCoreNum();
  61   }
  62
  63   public int getScheduleThreshold() {
  64     return scheduleThreshold;
  65   }
  66
  67   public void setScheduleThreshold(int scheduleThreshold) {
  68     this.scheduleThreshold = scheduleThreshold;
  69   }
  70
  71   public int getProbThreshold() {
  72     return probThreshold;
  73   }
  74
  75   public void setProbThreshold(int probThreshold) {
  76     this.probThreshold = probThreshold;
  77   }
  78
  79   public int getGenerateThreshold() {
  80     return generateThreshold;
  81   }
  82
  83   public void setGenerateThreshold(int generateThreshold) {
  84     this.generateThreshold = generateThreshold;
  85   }
  86
  87   public Vector<Schedule> synthesis() {
  88     // Print stuff to the original output and error streams.
  89     // The stuff printed through the 'origOut' and 'origErr' references
  90     // should go to the console on most systems while the messages
  91     // printed through the 'System.out' and 'System.err' will end up in
  92     // the files we created for them.
  93     //origOut.println ("\nRedirect:  Round #2");
  94     //System.out.println ("Test output via 'SimulatorResult.out'.");
  95     //origOut.println ("Test output via 'origOut' reference.");
  96
  97     // Save the current standard input, output, and error streams
  98     // for later restoration.
  99     PrintStream origOut = System.out;
 100
 101     // Create a new output stream for the stcriticalPathandard output.
 102     PrintStream stdout  = null;
 103     try {
 104       if(!state.BAMBOOCOMPILETIME) {
 105         stdout = new PrintStream(
 106           new FileOutputStream(this.state.outputdir + "SimulatorResult_"
 107                                + this.coreNum + ".out"));
 108       }
 109     } catch (Exception e) {
 110       // Sigh.  Couldn't open the file.
 111       System.out.println("Redirect:  Unable to open output file!");
 112       System.exit(1);
 113     }
 114
 115     // Print stuff to the original output and error streams.
 116     // On most systems all of this will end up on your console when you
 117     // run this application.
 118     //origOut.println ("\nRedirect:  Round #1");
 119     //System.out.println ("Test output via 'System.out'.");
 120     //origOut.println ("Test output via 'origOut' reference.");
 121
 122     // Set the System out and err streams to use our replacements.
 123     if(!state.BAMBOOCOMPILETIME) {
 124       System.setOut(stdout);
 125     }
 126
 127     Vector<Schedule> scheduling = null;
 128     Vector<ScheduleNode> schedulinggraph = null;
 129     int gid = 1;
 130
 131     // check all multi-parameter tasks
 132     Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
 133     Iterator it_tasks =
 134       this.state.getTaskSymbolTable().getDescriptorsIterator();
 135     while(it_tasks.hasNext()) {
 136       TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 137       if(td.numParameters() > 1) {
 138         multiparamtds.addElement(td);
 139       }
 140     }
 141     it_tasks = null;
 142
 143     // generate multiple schedulings
 144     this.scheduleAnalysis.setScheduleThreshold(this.scheduleThreshold);
 145     boolean tooptimize =
 146       this.scheduleAnalysis.schedule(this.generateThreshold,
 147                                      this.skipThreshold,
 148                                      multiparamtds);
 149     if(this.generateThreshold > 5) {
 150       this.generateThreshold = 5;
 151     }
 152     this.scheduleSimulator.init();
 153
 154     Vector<Vector<ScheduleNode>> scheduleGraphs = null;
 155     Vector<Vector<ScheduleNode>> newscheduleGraphs =
 156       this.scheduleAnalysis.getScheduleGraphs();
 157     Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
 158       this.scheduleAnalysis.getTd2maincd();
 159     Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
 160     Vector<Integer> selectedSchedulings = new Vector<Integer>();
 161     Vector<SimExecutionNode> selectedSimExeGraphs =
 162       new Vector<SimExecutionNode>();
 163     SimExecutionNode selectedSimExeGraph_bk = null;
 164
 165     int tryindex = 1;
 166     long bestexetime = Long.MAX_VALUE;
 167     Random rand = new Random();
 168     int threshold = this.scheduleThreshold;
 169     // simulate the generated schedulings and try to optimize it
 170     do {
 171       if(!state.BAMBOOCOMPILETIME) {
 172         System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 173         System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
 174       }
 175       gid += newscheduleGraphs.size();
 176       if(scheduleGraphs != null) {
 177         for(int i = 0; i < scheduleGraphs.size(); i++) {
 178           Vector<ScheduleNode> tmpgraph = scheduleGraphs.elementAt(i);
 179           for(int j = 0; j < tmpgraph.size(); j++) {
 180             ScheduleNode snode = tmpgraph.elementAt(j);
 181             snode.getEdgeVector().clear();
 182             snode.getInedgeVector().clear();
 183             snode.getScheduleEdges().clear();
 184             snode.getClassNodes().clear();
 185           }
 186           tmpgraph.clear();
 187           tmpgraph = null;
 188         }
 189         scheduleGraphs.clear();
 190       }
 191       scheduleGraphs = newscheduleGraphs;
 192       schedulings.clear();
 193       // get scheduling layouts from schedule graphs
 194       for(int i = 0; i < scheduleGraphs.size(); i++) {
 195         Vector<ScheduleNode> scheduleGraph = scheduleGraphs.elementAt(i);
 196         Vector<Schedule> tmpscheduling =
 197           generateScheduling(scheduleGraph, td2maincd);
 198         schedulings.add(tmpscheduling);
 199         scheduleGraph = null;
 200         tmpscheduling = null;
 201       }
 202       selectedSchedulings.clear();
 203       selectedSimExeGraphs.clear();
 204       long tmpexetime = this.scheduleSimulator.simulate(schedulings,
 205                                                         selectedSchedulings,
 206                                                         selectedSimExeGraphs);
 207       boolean remove = false;
 208       if(tmpexetime < bestexetime) {
 209         remove = true;
 210         bestexetime = tmpexetime;
 211         if(scheduling != null) {
 212           scheduling.clear();
 213           for(int j = 0; j < schedulinggraph.size(); j++) {
 214             ScheduleNode snode = schedulinggraph.elementAt(j);
 215             snode.getEdgeVector().clear();
 216             snode.getInedgeVector().clear();
 217             snode.getScheduleEdges().clear();
 218             snode.getClassNodes().clear();
 219           }
 220           schedulinggraph.clear();
 221           selectedSimExeGraph_bk = null;
 222         }
 223         scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0));
 224         schedulinggraph = scheduleGraphs.elementAt(
 225           selectedSchedulings.elementAt(0));
 226         selectedSimExeGraph_bk = selectedSimExeGraphs.elementAt(0);
 227
 228         if(!state.BAMBOOCOMPILETIME) {
 229           System.out.print("end of: #" + tryindex + " (bestexetime: "
 230                            + bestexetime + ")\n");
 231           System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 232         }
 233         tryindex++;
 234         threshold = this.scheduleThreshold;
 235       } else if(tmpexetime == bestexetime) {
 236         if(!state.BAMBOOCOMPILETIME) {
 237           System.out.print("end of: #" + tryindex + " (bestexetime: "
 238                            + bestexetime + ")\n");
 239           System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 240         }
 241         tryindex++;
 242         threshold += 10;
 243         if((threshold > 40) ||
 244            ((Math.abs(rand.nextInt()) % 100) < this.probThreshold + 10)) {
 245           break;
 246         }
 247       } else {
 248         if(!state.BAMBOOCOMPILETIME) {
 249           System.out.print("end of: #" + tryindex + " (bestexetime: "
 250                            + bestexetime + ")\n");
 251           System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 252         }
 253         tryindex++;
 254         if(threshold == this.scheduleThreshold) {
 255           if(scheduleGraphs != null) {
 256             scheduleGraphs.clear();
 257           }
 258           scheduleGraphs.addElement(schedulinggraph);
 259           if(selectedSchedulings != null) {
 260             selectedSchedulings.clear();
 261           }
 262           selectedSchedulings.addElement(Integer.valueOf(0));
 263           if(selectedSimExeGraphs != null) {
 264             selectedSimExeGraphs.clear();
 265           }
 266           selectedSimExeGraphs.addElement(selectedSimExeGraph_bk);
 267         }
 268         threshold += 10;
 269         if( (threshold > 40) ||
 270             ((Math.abs(rand.nextInt()) % 100) < this.probThreshold + 1)) {
 271           break;
 272         }
 273         break;
 274       }
 275
 276       if(tooptimize) {
 277         // try to optimize the best one scheduling
 278         //do {
 279         newscheduleGraphs = optimizeScheduling(scheduleGraphs,
 280                                                selectedSchedulings,
 281                                                selectedSimExeGraphs,
 282                                                gid,
 283                                                threshold);
 284         /*if(newscheduleGraphs != null) {
 285            if(this.generateThreshold < 30) {
 286             this.generateThreshold = 30;
 287            }
 288            break;
 289            } else {
 290            threshold += 10;
 291            if(this.generateThreshold > 0) {
 292             this.generateThreshold -= 3;
 293            }
 294            if((Math.abs(rand.nextInt()) % 10000) < this.probThreshold + 1) {
 295             break;
 296            }
 297            }
 298            }while(true);*/
 299         if(remove) {
 300           scheduleGraphs.removeElementAt(selectedSchedulings.elementAt(0));
 301           selectedSimExeGraphs.removeElementAt(0);
 302         }
 303       } else {
 304         break;
 305       }
 306     } while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
 307
 308     if(scheduleGraphs != null) {
 309       scheduleGraphs.clear();
 310     }
 311     scheduleGraphs = null;
 312     newscheduleGraphs = null;
 313     schedulings.clear();
 314     schedulings = null;
 315     selectedSchedulings.clear();
 316     selectedSchedulings = null;
 317     selectedSimExeGraphs.clear();
 318     selectedSimExeGraphs = null;
 319
 320     multiparamtds.clear();
 321     multiparamtds = null;
 322     td2maincd.clear();
 323     td2maincd = null;
 324
 325     if(!state.BAMBOOCOMPILETIME) {
 326       System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 327     }
 328     System.out.print("selected bestexetime: " + bestexetime + "\n");
 329     if(!state.BAMBOOCOMPILETIME) {
 330       String path = this.state.outputdir + "scheduling_selected.dot";
 331       SchedulingUtil.printScheduleGraph(path, schedulinggraph);
 332     }
 333
 334     // Close the streams.
 335     try {
 336       if(!state.BAMBOOCOMPILETIME) {
 337         stdout.close();
 338         stdout = null;
 339         System.setOut(origOut);
 340       }
 341     } catch (Exception e) {
 342       origOut.println("Redirect:  Unable to close files!");
 343     }
 344
 345     schedulinggraph.clear();
 346     schedulinggraph = null;
 347
 348     return scheduling;
 349   }
 350
 351   // for test
 352   // get the distribution info of new search algorithm
 353   public void distribution(boolean isall, int startnum) {
 354     // Print stuff to the original output and error streams.
 355     // The stuff printed through the 'origOut' and 'origErr' references
 356     // should go to the console on most systems while the messages
 357     // printed through the 'System.out' and 'System.err' will end up in
 358     // the files we created for them.
 359     //origOut.println ("\nRedirect:  Round #2");
 360     //System.out.println ("Test output via 'SimulatorResult.out'.");
 361     //origOut.println ("Test output via 'origOut' reference.");
 362
 363     // Save the current standard input, output, and error streams
 364     // for later restoration.
 365     PrintStream origOut = System.out;
 366
 367     // Create a new output stream for the standard output.
 368     PrintStream stdout  = null;
 369     try {
 370       stdout = new PrintStream(
 371         new FileOutputStream(this.state.outputdir + "SimulatorResult_"
 372                              + this.coreNum + ".out"));
 373     } catch (Exception e) {
 374       // Sigh.  Couldn't open the file.
 375       System.out.println("Redirect:  Unable to open output file!");
 376       System.exit(1);
 377     }
 378
 379     // Print stuff to the original output and error streams.
 380     // On most systems all of this will end up on your console when you
 381     // run this application.
 382     //origOut.println ("\nRedirect:  Round #1");
 383     //System.out.println ("Test output via 'System.out'.");
 384     //origOut.println ("Test output via 'origOut' reference.");
 385
 386     // Set the System out and err streams to use our replacements.
 387     System.setOut(stdout);
 388
 389     if(isall) {
 390       // check all multi-parameter tasks
 391       Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
 392       Iterator it_tasks =
 393         this.state.getTaskSymbolTable().getDescriptorsIterator();
 394       while(it_tasks.hasNext()) {
 395         TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 396         if(td.numParameters() > 1) {
 397           multiparamtds.addElement(td);
 398         }
 399       }
 400       it_tasks = null;
 401
 402       // Generate all possible schedulings
 403       //this.scheduleAnalysis.setScheduleThreshold(Integer.MAX_VALUE);
 404       //this.scheduleAnalysis.schedule(-1, multiparamtds);
 405       this.scheduleAnalysis.setScheduleThreshold(10000);
 406       this.scheduleAnalysis.schedule(80,
 407                                      20, // might skip
 408                                      multiparamtds);
 409       this.scheduleSimulator.init();
 410
 411       Vector<Vector<ScheduleNode>> totestscheduleGraphs =
 412         this.scheduleAnalysis.getScheduleGraphs();
 413       Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
 414         this.scheduleAnalysis.getTd2maincd();
 415       Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
 416       Vector<Integer> selectedSchedulings = new Vector<Integer>();
 417       Vector<SimExecutionNode> selectedSimExeGraphs =
 418         new Vector<SimExecutionNode>();
 419
 420       File file=new File(this.state.outputdir+"distributeinfo_s_"+this.coreNum
 421                          +".out");
 422       FileOutputStream dotstream = null;
 423       try {
 424         dotstream = new FileOutputStream(file,false);
 425       } catch (Exception e) {
 426         e.printStackTrace();
 427         System.exit(-1);
 428       }
 429       PrintWriter output = new java.io.PrintWriter(dotstream, true);
 430       output.println("start time(1,000,000 cycles): "
 431                      + totestscheduleGraphs.size());
 432       for(int ii = 0; ii < totestscheduleGraphs.size(); ii++) {
 433         Vector<Vector<ScheduleNode>> newscheduleGraphs =
 434           new Vector<Vector<ScheduleNode>>();
 435         newscheduleGraphs.add(totestscheduleGraphs.elementAt(ii));
 436         // simulate the generated schedulings and try to optimize it
 437         schedulings.clear();
 438         // get scheduling layouts from schedule graphs
 439         for(int i = 0; i < newscheduleGraphs.size(); i++) {
 440           Vector<ScheduleNode> scheduleGraph = newscheduleGraphs.elementAt(i);
 441           Vector<Schedule> tmpscheduling =
 442             generateScheduling(scheduleGraph, td2maincd);
 443           schedulings.add(tmpscheduling);
 444           scheduleGraph = null;
 445           tmpscheduling = null;
 446         }
 447         selectedSchedulings.clear();
 448         selectedSimExeGraphs.clear();
 449         long tmpexetime = this.scheduleSimulator.simulate(schedulings,
 450                                                           selectedSchedulings,
 451                                                           selectedSimExeGraphs);
 452         output.println(((float)tmpexetime/100000000));
 453       }
 454
 455     } else {
 456       // check all multi-parameter tasks
 457       Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
 458       Iterator it_tasks =
 459         this.state.getTaskSymbolTable().getDescriptorsIterator();
 460       while(it_tasks.hasNext()) {
 461         TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 462         if(td.numParameters() > 1) {
 463           multiparamtds.addElement(td);
 464         }
 465       }
 466       it_tasks = null;
 467
 468       // generate multiple schedulings
 469       this.scheduleThreshold = 20;
 470       this.generateThreshold = 30;
 471       this.probThreshold = 0;
 472       this.scheduleAnalysis.setScheduleThreshold(1000);
 473       boolean tooptimize =
 474         this.scheduleAnalysis.schedule(this.generateThreshold,
 475                                        60, // might skip
 476                                        multiparamtds);
 477       this.scheduleSimulator.init();
 478
 479       Vector<Vector<ScheduleNode>> scheduleGraphs = null;
 480       Vector<Vector<ScheduleNode>> totestscheduleGraphs =
 481         this.scheduleAnalysis.getScheduleGraphs();
 482       Hashtable<TaskDescriptor, ClassDescriptor> td2maincd =
 483         this.scheduleAnalysis.getTd2maincd();
 484       Vector<Vector<Schedule>> schedulings = new Vector<Vector<Schedule>>();
 485       Vector<Integer> selectedSchedulings = new Vector<Integer>();
 486       Vector<SimExecutionNode> selectedSimExeGraphs =
 487         new Vector<SimExecutionNode>();
 488       SimExecutionNode selectedSimExeGraph_bk = null;
 489
 490       File file=new File(this.state.outputdir + "distributeinfo_s_"
 491                          + this.coreNum + ".out");
 492       FileOutputStream dotstream = null;
 493       File file2=new File(this.state.outputdir + "distributeinfo_o_"
 494                           + this.coreNum + ".out");
 495       FileOutputStream dotstream2 = null;
 496       try {
 497         dotstream = new FileOutputStream(file,false);
 498         dotstream2 = new FileOutputStream(file2,false);
 499       } catch (Exception e) {
 500         e.printStackTrace();
 501         System.exit(-1);
 502       }
 503       PrintWriter output = new java.io.PrintWriter(dotstream, true);
 504       PrintWriter output2 = new java.io.PrintWriter(dotstream2, true);
 505       output.println("start time(100,000,000 cycles): "
 506                      + totestscheduleGraphs.size());
 507       output2.println("optimized time(100,000,000 cycles): "
 508                       + totestscheduleGraphs.size());
 509       for(int ii = startnum; ii < totestscheduleGraphs.size(); ii++) {
 510         Vector<Vector<ScheduleNode>> newscheduleGraphs =
 511           new Vector<Vector<ScheduleNode>>();
 512         newscheduleGraphs.add(totestscheduleGraphs.elementAt(ii));
 513         int tryindex = 1;
 514         long bestexetime = Long.MAX_VALUE;
 515         int gid = 1;
 516         Vector<Schedule> scheduling = null;
 517         Vector<ScheduleNode> schedulinggraph = null;
 518         boolean isfirst = true;
 519         Random rand = new Random();
 520         int threshold = this.scheduleThreshold;
 521         // simulate the generated schedulings and try to optimize it
 522         System.out.print("=========================================================\n");
 523         System.out.print("# " + ii + ": \n");
 524         do {
 525           System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 526           System.out.print("Simulate and optimize round: #" + tryindex + ": \n");
 527           gid += newscheduleGraphs.size();
 528           if(scheduleGraphs != null) {
 529             for(int i = 0; i < scheduleGraphs.size(); i++) {
 530               Vector<ScheduleNode> tmpgraph = scheduleGraphs.elementAt(i);
 531               for(int j = 0; j < tmpgraph.size(); j++) {
 532                 ScheduleNode snode = tmpgraph.elementAt(j);
 533                 snode.getEdgeVector().clear();
 534                 snode.getInedgeVector().clear();
 535                 snode.getScheduleEdges().clear();
 536                 snode.getClassNodes().clear();
 537               }
 538               tmpgraph.clear();
 539               tmpgraph = null;
 540             }
 541             scheduleGraphs.clear();
 542           }
 543           scheduleGraphs = newscheduleGraphs;
 544           schedulings.clear();
 545           // get scheduling layouts from schedule graphs
 546           for(int i = 0; i < scheduleGraphs.size(); i++) {
 547             Vector<ScheduleNode> scheduleGraph = scheduleGraphs.elementAt(i);
 548             Vector<Schedule> tmpscheduling =
 549               generateScheduling(scheduleGraph, td2maincd);
 550             schedulings.add(tmpscheduling);
 551             scheduleGraph = null;
 552             tmpscheduling = null;
 553           }
 554           selectedSchedulings.clear();
 555           selectedSimExeGraphs.clear();
 556           long tmpexetime = this.scheduleSimulator.simulate(schedulings,
 557                                                             selectedSchedulings,
 558                                                             selectedSimExeGraphs);
 559           if(isfirst) {
 560             output.println(((float)tmpexetime/100000000));
 561             isfirst = false;
 562           }
 563           if(tmpexetime < bestexetime) {
 564             bestexetime = tmpexetime;
 565             if(scheduling != null) {
 566               scheduling.clear();
 567               for(int j = 0; j < schedulinggraph.size(); j++) {
 568                 ScheduleNode snode = schedulinggraph.elementAt(j);
 569                 snode.getEdgeVector().clear();
 570                 snode.getInedgeVector().clear();
 571                 snode.getScheduleEdges().clear();
 572                 snode.getClassNodes().clear();
 573               }
 574               schedulinggraph.clear();
 575               selectedSimExeGraph_bk = null;
 576             }
 577             scheduling = schedulings.elementAt(selectedSchedulings.elementAt(0));
 578             schedulinggraph = scheduleGraphs.elementAt(
 579               selectedSchedulings.elementAt(0));
 580             selectedSimExeGraph_bk = selectedSimExeGraphs.elementAt(0);
 581             tryindex++;
 582             threshold = this.scheduleThreshold;
 583             System.out.print("end of: #" + tryindex + " (bestexetime: "
 584                              + bestexetime + ")\n");
 585             System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 586           } else if(tmpexetime == bestexetime) {
 587             System.out.print("end of: #" + tryindex + " (bestexetime: "
 588                              + bestexetime + ")\n");
 589             System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 590             tryindex++;
 591             threshold = this.scheduleThreshold;
 592             if((Math.abs(rand.nextInt()) % 100) < this.probThreshold) {
 593               break;
 594             }
 595           } else {
 596             System.out.print("end of: #" + tryindex + " (bestexetime: "
 597                              + bestexetime + ")\n");
 598             System.out.print("+++++++++++++++++++++++++++++++++++++++++++++++++++\n");
 599             tryindex++;
 600             if(threshold == this.scheduleThreshold) {
 601               if(scheduleGraphs != null) {
 602                 scheduleGraphs.clear();
 603               }
 604               scheduleGraphs.addElement(schedulinggraph);
 605               if(selectedSchedulings != null) {
 606                 selectedSchedulings.clear();
 607               }
 608               selectedSchedulings.addElement(Integer.valueOf(0));
 609               if(selectedSimExeGraphs != null) {
 610                 selectedSimExeGraphs.clear();
 611               }
 612               selectedSimExeGraphs.addElement(selectedSimExeGraph_bk);
 613             }
 614             threshold += 10;
 615             if((Math.abs(rand.nextInt()) % 100) < this.probThreshold + 1) {
 616               break;
 617             }
 618             //break;
 619           }
 620
 621           if(tooptimize) {
 622             // try to optimize theschedulings best one scheduling
 623             newscheduleGraphs = optimizeScheduling(scheduleGraphs,
 624                                                    selectedSchedulings,
 625                                                    selectedSimExeGraphs,
 626                                                    gid,
 627                                                    this.scheduleThreshold);
 628             if(tmpexetime < bestexetime) {
 629               scheduleGraphs.remove(selectedSchedulings.elementAt(0));
 630             }
 631           } else {
 632             break;
 633           }
 634         } while(newscheduleGraphs != null); // TODO: could it possibly lead to endless loop?
 635
 636         scheduleGraphs.clear();
 637         scheduleGraphs = null;
 638         scheduling = null;
 639         schedulinggraph = null;
 640         if(newscheduleGraphs != null) {
 641           newscheduleGraphs.clear();
 642         }
 643         newscheduleGraphs = null;
 644         totestscheduleGraphs.elementAt(ii).clear();
 645         for(int i = 0; i < schedulings.size(); i++) {
 646           schedulings.elementAt(i).clear();
 647         }
 648         schedulings.clear();
 649         selectedSchedulings.clear();
 650         selectedSimExeGraphs.clear();
 651
 652         output2.println(((float)bestexetime/100000000));
 653         System.out.print("=========================================================\n");
 654       }
 655
 656       if(scheduleGraphs != null) {
 657         scheduleGraphs.clear();
 658       }
 659       scheduleGraphs = null;
 660       totestscheduleGraphs = null;
 661       for(int i = 0; i < schedulings.size(); i++) {
 662         schedulings.elementAt(i).clear();
 663       }
 664       schedulings.clear();
 665       schedulings = null;
 666       selectedSchedulings.clear();
 667       selectedSchedulings = null;
 668       selectedSimExeGraphs.clear();
 669       selectedSimExeGraphs = null;
 670       multiparamtds.clear();
 671       multiparamtds = null;
 672       td2maincd.clear();
 673       td2maincd = null;
 674
 675       // Close the streams.
 676       try {
 677         output.close();
 678         stdout.close();
 679         output = null;
 680         stdout = null;
 681         System.setOut(origOut);
 682       } catch (Exception e) {
 683         origOut.println("Redirect:  Unable to close files!");
 684       }
 685     }
 686
 687     return;
 688   }
 689
 690   private Vector<Vector<ScheduleNode>>
 691   optimizeScheduling(Vector<Vector<ScheduleNode>> scheduleGraphs,
 692                      Vector<Integer> selectedScheduleGraphs,
 693                      Vector<SimExecutionNode> selectedSimExeGraphs,
 694                      int gid,
 695                      int count) {
 696     if(this.coreNum == 1) {
 697       // single core
 698       return null;
 699     }
 700
 701     Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
 702     int lgid = gid;
 703     int left = count;
 704
 705     for(int i = 0; i < selectedScheduleGraphs.size(); i++) {
 706       Vector<ScheduleNode> schedulegraph = scheduleGraphs.elementAt(
 707         selectedScheduleGraphs.elementAt(i));
 708       SimExecutionNode startnode = selectedSimExeGraphs.elementAt(i);
 709       Vector<SimExecutionEdge> criticalPath = analyzeCriticalPath(startnode);
 710       // for Test
 711       if(this.state.PRINTCRITICALPATH) {
 712         System.err.println("gid: " + lgid + " endpoint: " + startnode.getTimepoint());
 713       }
 714       Vector<Vector<ScheduleNode>> tmposchedulegraphs =
 715         optimizeCriticalPath(schedulegraph,
 716                              criticalPath,
 717                              lgid,
 718                              left);
 719       if(tmposchedulegraphs != null) {
 720         if(optimizeschedulegraphs == null) {
 721           optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
 722         }
 723         optimizeschedulegraphs.addAll(tmposchedulegraphs);
 724         lgid += tmposchedulegraphs.size();
 725         left -= tmposchedulegraphs.size();
 726         if(left == 0) {
 727           schedulegraph = null;
 728           criticalPath = null;
 729           tmposchedulegraphs = null;
 730           break;
 731         }
 732       }
 733       schedulegraph = null;
 734       criticalPath = null;
 735       tmposchedulegraphs = null;
 736     }
 737
 738     return optimizeschedulegraphs;
 739   }
 740
 741   private Vector<SimExecutionEdge>
 742   analyzeCriticalPath(SimExecutionNode startnode) {
 743     // first figure out the critical path
 744     Vector<SimExecutionEdge> criticalPath = new Vector<SimExecutionEdge>();
 745     getCriticalPath(startnode, criticalPath);
 746     computeBestStartPoint(criticalPath);
 747
 748     return criticalPath;
 749   }
 750
 751   // TODO: currently only get one critical path. It's possible that there are
 752   // multiple critical paths and some of them can not be optimized while others
 753   // can. Need to fix up for this situation.
 754   private long getCriticalPath(SimExecutionNode startnode,
 755                                Vector<SimExecutionEdge> criticalPath) {
 756     long sum = 0;
 757     SimExecutionNode snode = startnode;
 758     // go reversely to find the critical path
 759     while(snode != null) {
 760       SimExecutionNode nsnode = null;
 761       Iterator<SimExecutionEdge> it_iedges =
 762         (Iterator<SimExecutionEdge>)snode.inedges();
 763       while(it_iedges.hasNext()) {
 764         SimExecutionEdge sedge = it_iedges.next();
 765         //if(sedge.getWeight() != 0) {
 766         SimExecutionNode tsnode = (SimExecutionNode)(sedge.getSource());
 767         if(tsnode.getTimepoint() + sedge.getWeight() == snode.getTimepoint()) {
 768           nsnode = tsnode;
 769           criticalPath.insertElementAt(sedge, 0);
 770           sum += sedge.getWeight();
 771           break;
 772         }
 773         //}
 774       }
 775       it_iedges = null;
 776       snode = nsnode;
 777     }
 778     return sum;
 779   }
 780
 781   private void computeBestStartPoint(Vector<SimExecutionEdge> criticalPath) {
 782     // calculate the earliest start time of each task on the critial path
 783     for(int i = 0; i < criticalPath.size(); i++) {
 784       SimExecutionEdge seedge = criticalPath.elementAt(i);
 785       Vector<SimExecutionEdge> predicates = seedge.getPredicates();
 786       if(predicates != null) {
 787         // have predicates
 788         long starttime = 0;
 789         // check the latest finish time of all the predicates
 790         for(int j = 0; j < predicates.size(); j++) {
 791           SimExecutionEdge predicate = predicates.elementAt(j);
 792           long tmptime = predicate.getBestStartPoint() + predicate.getWeight();
 793           if(tmptime > starttime) {
 794             starttime = tmptime;
 795             seedge.setLastpredicateEdge(predicate);
 796             if(predicate.getTd() != null) {
 797               seedge.setLastpredicateNode(
 798                 (SimExecutionNode)predicate.getTarget());
 799             } else {
 800               // transfer edge
 801               seedge.setLastpredicateNode(
 802                 (SimExecutionNode)predicate.getSource());
 803             }
 804           }
 805         }
 806         seedge.setBestStartPoint(starttime);
 807       } else if(seedge.getSource().getInedgeVector().size() > 0) {
 808         // should have only one in edge
 809         long starttime = ((SimExecutionNode)seedge.getSource()).getTimepoint();
 810         seedge.setBestStartPoint(starttime);
 811       } else {
 812         // no predicates
 813         seedge.setBestStartPoint(0);
 814       }
 815       predicates = null;
 816     }
 817   }
 818
 819   private Vector<Vector<ScheduleNode>>
 820   optimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
 821                        Vector<SimExecutionEdge> criticalPath,
 822                        int gid,
 823                        int count) {
 824     Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
 825     int lgid = gid;
 826     int left = count;
 827
 828     // for test, print out the criticalPath
 829     if(this.state.PRINTCRITICALPATH) {
 830       SchedulingUtil.printCriticalPath(this.state.outputdir + "criticalpath_"
 831                                        + lgid + ".dot",  criticalPath);
 832     }
 833
 834     // first check all seedges whose real start point is late than predicted
 835     // earliest start time and group them
 836     long opcheckpoint = Long.MAX_VALUE;
 837     Vector<Integer> sparecores = null;
 838     // group according to core index
 839     Hashtable<Long, Hashtable<Integer, Vector<SimExecutionEdge>>> toselects =
 840       new Hashtable<Long, Hashtable<Integer, Vector<SimExecutionEdge>>>();
 841     Random rand = new Random();
 842     for(int i = 0; i < criticalPath.size(); i++) {
 843       SimExecutionEdge seedge = criticalPath.elementAt(i);
 844       long starttime = seedge.getBestStartPoint();
 845       if((starttime < ((SimExecutionNode)seedge.getSource()).getTimepoint())
 846          && (seedge.getTd() != null)) {
 847         // Note: must be a task related edge, can not be an object transfer edge
 848         // no restrictions due to data dependencies
 849         // have potential to be parallelled and start execution earlier
 850         seedge.setFixedTime(false);
 851         // consider to optimize it only when its predicates can NOT
 852         // be optimized, otherwise first considering optimize its predicates
 853         //SimExecutionEdge lastpredicateedge = seedge.getLastpredicateEdge();
 854         // TODO
 855         //if(lastpredicateedge.isFixedTime()) {
 856         int corenum = seedge.getCoreNum();
 857         if(!toselects.containsKey(starttime)) {
 858           toselects.put(starttime,
 859                         new Hashtable<Integer, Vector<SimExecutionEdge>>());
 860         }
 861         if(!toselects.get(starttime).containsKey(corenum)) {
 862           toselects.get(starttime).put(corenum,
 863                                        new Vector<SimExecutionEdge>());
 864         }
 865         toselects.get(starttime).get(corenum).add(seedge);
 866         //}
 867       }
 868     }
 869
 870     // Randomly choose the tasks to optimize(previously only
 871     // consider the tasks with smallest best start time)
 872     Vector<Long> keys = new Vector<Long>(toselects.keySet());
 873     do {
 874       int length = keys.size();
 875       if(length == 0) {
 876         return optimizeschedulegraphs;
 877       }
 878       int tochoose = Math.abs(rand.nextInt()) % length;
 879       opcheckpoint = (keys.elementAt(tochoose)).longValue();
 880       keys.removeElementAt(tochoose);
 881       Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize =
 882         toselects.get(opcheckpoint);
 883       SimExecutionEdge seedge =
 884         tooptimize.values().iterator().next().elementAt(0);
 885       SimExecutionNode lastpredicatenode = seedge.getLastpredicateNode();
 886       SimExecutionEdge lastpredicateedge = seedge.getLastpredicateEdge();
 887       long timepoint = lastpredicatenode.getTimepoint();
 888       if(lastpredicateedge.getTd() == null) {
 889         // transfer edge
 890         timepoint += lastpredicateedge.getWeight();
 891       }
 892       // mapping to critical path
 893       for(int index = 0; index < criticalPath.size(); index++) {
 894         SimExecutionEdge tmpseedge = criticalPath.elementAt(index);
 895         SimExecutionNode tmpsenode =
 896           (SimExecutionNode)tmpseedge.getTarget();
 897         if(tmpsenode.getTimepoint() > timepoint) {
 898           // get the spare core info
 899           sparecores = tmpsenode.getSpareCores();
 900           break;
 901         }
 902       }
 903
 904       if(tooptimize.size() > 0) {
 905         Iterator<Integer> it_cores = tooptimize.keySet().iterator();
 906         // check if it is possible to optimize these tasks
 907         if((sparecores == null) || (sparecores.size() == 0)) {
 908           // lack of spare cores
 909           while(it_cores.hasNext()) {
 910             int corenum = it_cores.next();
 911             Vector<SimExecutionEdge> tmptasks = tooptimize.get(corenum);
 912             // group the task instantiations according to whether it
 913             // has backward data dependences or not
 914             Vector<SimExecutionEdge> candidatetasks = new Vector();
 915             for(int ii= 0; ii < tmptasks.size(); ii++) {
 916               SimExecutionEdge tmpseedge = tmptasks.elementAt(ii);
 917               SimExecutionNode target = (SimExecutionNode)tmpseedge.getTarget();
 918               Vector<SimExecutionEdge> children =
 919                 (Vector<SimExecutionEdge>)target.getEdgeVector();
 920               int jj = 0;
 921               for(; jj < children.size(); jj++) {
 922                 SimExecutionEdge tmpedge = children.elementAt(jj);
 923                 if(tmpedge.getTd() != null) {
 924                   Vector<SimExecutionEdge> predicates =
 925                     tmpedge.getPredicates();
 926                   if((predicates != null) &&
 927                      (predicates.contains(tmpseedge))) {
 928                     break;
 929                   }
 930                   predicates = null;
 931                 } else if(tmpedge.getWeight() != 0) {
 932                   // transfer edge
 933                   if(((SimExecutionNode)tmpedge.getTarget()).getTimepoint()
 934                      == tmpedge.getWeight() + target.getTimepoint()) {
 935                     break;
 936                   }
 937                 }
 938               }
 939               if(jj == children.size()) {
 940                 candidatetasks.add(tmpseedge);
 941               }
 942             }
 943             if((candidatetasks.size() > 0) &&
 944                (candidatetasks.size() < tmptasks.size())) {
 945               // there are less important tasks which have no backward
 946               // data dependences at this timepoint, try to change
 947               // original execution order
 948               Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize2 =
 949                 new Hashtable<Integer, Vector<SimExecutionEdge>>();
 950               tooptimize2.put(corenum, candidatetasks);
 951               Vector<Vector<ScheduleNode>> ops =
 952                 innerOptimizeCriticalPath(scheduleGraph,
 953                                           tooptimize2,
 954                                           null,
 955                                           lgid,
 956                                           left);
 957               if(ops != null) {
 958                 if(optimizeschedulegraphs == null) {
 959                   optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
 960                 }
 961                 optimizeschedulegraphs.addAll(ops);
 962                 lgid += ops.size();
 963                 left -= ops.size();
 964               }
 965               tooptimize2 = null;
 966               ops = null;
 967             }
 968             tmptasks = null;
 969             candidatetasks = null;
 970           }
 971
 972           if(left == 0) {
 973             it_cores = null;
 974             return optimizeschedulegraphs;
 975           }
 976
 977           // flush the dependences and earliest start time
 978           if(!state.BAMBOOCOMPILETIME) {
 979             it_cores = tooptimize.keySet().iterator();
 980             while(it_cores.hasNext()) {
 981               int corenum = it_cores.next();
 982               Vector<SimExecutionEdge> edgevec =
 983                 tooptimize.get(corenum);
 984               for(int j = 0; j < edgevec.size(); j++) {
 985                 SimExecutionEdge edge = edgevec.elementAt(j);
 986                 lastpredicateedge = edge.getLastpredicateEdge();
 987                 lastpredicatenode = edge.getLastpredicateNode();
 988                 // if(edge.getCoreNum() != lastpredicate.getCoreNum()) // should never hit this
 989                 timepoint = lastpredicatenode.getTimepoint();
 990                 if(lastpredicateedge.getTd() == null) {
 991                   // transfer edge
 992                   timepoint += lastpredicateedge.getWeight();
 993                 }
 994                 // mapping to critical path
 995                 for(int index = 0; index < criticalPath.size(); index++) {
 996                   SimExecutionEdge tmpseedge = criticalPath.elementAt(index);
 997                   SimExecutionNode tmpsenode =
 998                     (SimExecutionNode)tmpseedge.getTarget();
 999                   if(tmpsenode.getTimepoint() > timepoint) {
1000                     // update the predicate info
1001                     if(edge.getPredicates() != null) {
1002                       edge.getPredicates().remove(lastpredicateedge);
1003                     }
1004                     edge.addPredicate(criticalPath.elementAt(index));
1005                     break;
1006                   }
1007                 }
1008               }
1009               edgevec = null;
1010             }
1011             it_cores = null;
1012             computeBestStartPoint(criticalPath);
1013             Vector<Vector<ScheduleNode>> ops = optimizeCriticalPath(scheduleGraph,
1014                                                                     criticalPath,
1015                                                                     lgid,
1016                                                                     left);
1017             if(ops != null) {
1018               if(optimizeschedulegraphs == null) {
1019                 optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
1020               }
1021               optimizeschedulegraphs.addAll(ops);
1022               lgid += ops.size();
1023               left -= ops.size();
1024             }
1025             ops = null;
1026           }
1027         } else {
1028           // there are spare cores, try to reorganize the tasks to the spare
1029           // cores
1030           Vector<Vector<ScheduleNode>> ops =
1031             innerOptimizeCriticalPath(scheduleGraph,
1032                                       tooptimize,
1033                                       sparecores,
1034                                       lgid,
1035                                       left);
1036           if(ops != null) {
1037             if(optimizeschedulegraphs == null) {
1038               optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
1039             }
1040             optimizeschedulegraphs.addAll(ops);
1041             lgid += ops.size();
1042             left -= ops.size();
1043           }
1044           ops = null;
1045         }
1046       }
1047       sparecores = null;
1048       tooptimize.clear();
1049       tooptimize = null;
1050     } while(left > 0);
1051     toselects.clear();
1052     toselects = null;
1053
1054     return optimizeschedulegraphs;
1055   }
1056
1057   private Vector<Vector<ScheduleNode>>
1058   innerOptimizeCriticalPath(Vector<ScheduleNode> scheduleGraph,
1059                             Hashtable<Integer, Vector<SimExecutionEdge>> tooptimize,
1060                             Vector<Integer> sparecores,
1061                             int gid,
1062                             int count) {
1063     int lgid = gid;
1064     int left = count;
1065     Vector<Vector<ScheduleNode>> optimizeschedulegraphs = null;
1066
1067     // first clone the whole graph
1068     Vector<ScheduleNode> newscheduleGraph =
1069       cloneScheduleGraph(scheduleGraph, lgid);
1070
1071     if(newscheduleGraph.size() == 0) {
1072       //System.err.println("empty schedule graph!");
1073       return optimizeschedulegraphs;
1074     }
1075
1076     // these nodes are root nodes
1077     Vector<ScheduleNode> roots = new Vector<ScheduleNode>();
1078     for(int i = 0; i < newscheduleGraph.size(); i++) {
1079       if((sparecores == null) || (sparecores.contains(i))) {
1080         roots.add(newscheduleGraph.elementAt(i));
1081       }
1082     }
1083
1084     // map the tasks associated to SimExecutionedges to original
1085     // ClassNode in the ScheduleGraph and split them from previous
1086     // ScheduleGraph
1087     Vector<ScheduleNode> tocombines = new Vector<ScheduleNode>();
1088     Iterator<Integer> it_cores = tooptimize.keySet().iterator();
1089     while(it_cores.hasNext()) {
1090       int corenum = it_cores.next();
1091       Vector<SimExecutionEdge> candidatetasks =
1092         tooptimize.get(corenum);
1093       for(int i = 0; i < candidatetasks.size(); i++) {
1094         TaskDescriptor td = candidatetasks.elementAt(i).getTd();
1095         // TODO: currently do not consider multi-param tasks
1096         if(td.numParameters() == 1) {
1097           ClassDescriptor cd = td.getParamType(0).getClassDesc();
1098           ScheduleNode snode = newscheduleGraph.elementAt(corenum); // corresponding ScheduleNode
1099           Iterator<ClassNode> it_cnodes = snode.getClassNodesIterator();
1100           ClassNode tosplit = null;
1101           while(it_cnodes.hasNext()) {
1102             ClassNode cnode = it_cnodes.next();
1103             if(cnode.getClassDescriptor().equals(cd)) {
1104               tosplit= cnode;
1105               break;
1106             }
1107           }
1108           it_cnodes = null;
1109
1110           // split the node
1111           ScheduleNode splitnode = snode.spliteClassNode(tosplit);
1112           newscheduleGraph.add(splitnode);
1113           tocombines.add(splitnode);
1114           tosplit = null;
1115         }
1116       }
1117       candidatetasks = null;
1118     }
1119     it_cores = null;
1120
1121     if(tocombines.size() == 0) {
1122       return optimizeschedulegraphs;
1123     }
1124
1125     SchedulingUtil.assignCids(newscheduleGraph);
1126
1127     // get all the ScheduleEdge
1128     Vector<ScheduleEdge> scheduleEdges = new Vector<ScheduleEdge>();
1129     for(int i= 0; i < newscheduleGraph.size(); i++) {
1130       scheduleEdges.addAll(
1131         (Vector<ScheduleEdge>)newscheduleGraph.elementAt(i).getEdgeVector());
1132     }
1133
1134     Vector<Vector<ScheduleNode>> rootNodes =
1135       SchedulingUtil.rangeScheduleNodes(roots);
1136     if(rootNodes == null) {
1137       return optimizeschedulegraphs;
1138     }
1139     Vector<Vector<ScheduleNode>> nodes2combine =
1140       SchedulingUtil.rangeScheduleNodes(tocombines);
1141     if(nodes2combine == null) {
1142       return optimizeschedulegraphs;
1143     }
1144
1145     CombinationUtil.CombineGenerator cGen =
1146       CombinationUtil.allocateCombineGenerator(rootNodes, nodes2combine);
1147     Random rand = new Random();
1148     while ((left > 0) && (cGen.nextGen())) {
1149       //while ((left > 0) && (cGen.randomGenE())) {
1150       if(Math.abs(rand.nextInt()) % 100 > this.generateThreshold) {
1151         Vector<Vector<CombinationUtil.Combine>> combine = cGen.getCombine();
1152         Vector<ScheduleNode> sNodes =
1153           SchedulingUtil.generateScheduleGraph(this.state,
1154                                                newscheduleGraph,
1155                                                scheduleEdges,
1156                                                rootNodes,
1157                                                combine,
1158                                                lgid++);
1159         if(optimizeschedulegraphs == null) {
1160           optimizeschedulegraphs = new Vector<Vector<ScheduleNode>>();
1161         }
1162         optimizeschedulegraphs.add(sNodes);
1163         combine = null;
1164         sNodes = null;
1165         left--;
1166       }
1167     }
1168     cGen.clear();
1169     for(int i = 0; i < rootNodes.size(); i++) {
1170       if(rootNodes.elementAt(i) != null) {
1171         rootNodes.elementAt(i).clear();
1172       }
1173     }
1174     rootNodes = null;
1175     for(int i = 0; i < nodes2combine.size(); i++) {
1176       if(nodes2combine.elementAt(i) != null) {
1177         nodes2combine.elementAt(i).clear();
1178       }
1179     }
1180     nodes2combine = null;
1181     for(int j = 0; j < newscheduleGraph.size(); j++) {
1182       ScheduleNode snode = newscheduleGraph.elementAt(j);
1183       snode.getEdgeVector().clear();
1184       snode.getInedgeVector().clear();
1185       snode.getScheduleEdges().clear();
1186       snode.getClassNodes().clear();
1187     }
1188     newscheduleGraph = null;
1189     scheduleEdges.clear();
1190     scheduleEdges = null;
1191     roots = null;
1192     tocombines = null;
1193
1194     return optimizeschedulegraphs;
1195   }
1196
1197   private Vector<ScheduleNode>
1198   cloneScheduleGraph(Vector<ScheduleNode> scheduleGraph,
1199                      int gid) {
1200     Vector<ScheduleNode> result = new Vector<ScheduleNode>();
1201
1202     // get all the ScheduleEdge
1203     Vector<ScheduleEdge> scheduleEdges = new Vector<ScheduleEdge>();
1204     for(int i= 0; i < scheduleGraph.size(); i++) {
1205       scheduleEdges.addAll(
1206         (Vector<ScheduleEdge>)scheduleGraph.elementAt(i).getEdgeVector());
1207     }
1208     Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash =
1209       new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
1210     Hashtable<ScheduleNode, ScheduleNode> sn2sn =
1211       new Hashtable<ScheduleNode, ScheduleNode>();
1212     SchedulingUtil.cloneScheduleGraph(scheduleGraph,
1213                                       scheduleEdges,
1214                                       sn2hash,
1215                                       sn2sn,
1216                                       result,
1217                                       gid);
1218
1219     SchedulingUtil.assignCids(result);
1220     scheduleEdges.clear();
1221     scheduleEdges = null;
1222     sn2hash.clear();
1223     sn2hash = null;
1224     sn2sn.clear();
1225     sn2sn = null;
1226
1227     return result;
1228   }
1229
1230   private Vector<Schedule>
1231   generateScheduling(Vector<ScheduleNode> scheduleGraph,
1232                      Hashtable<TaskDescriptor, ClassDescriptor> td2maincd) {
1233     Hashtable<TaskDescriptor, Vector<Schedule>> td2cores =
1234       new Hashtable<TaskDescriptor, Vector<Schedule>>(); // tasks reside on which cores
1235     Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
1236     // for each ScheduleNode create a schedule node representing a core
1237     Hashtable<ScheduleNode, Integer> sn2coreNum =
1238       new Hashtable<ScheduleNode, Integer>();
1239     Hashtable<TaskDescriptor, Integer> td2maincore =
1240       new Hashtable<TaskDescriptor, Integer>();
1241     Hashtable<TaskDescriptor, Vector<Schedule>> td2allycores =
1242       new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks --
1243     // ally cores which might have parameters
1244     // for the task
1245
1246     int j = 0;
1247     for(j = 0; j < scheduleGraph.size(); j++) {
1248       sn2coreNum.put(scheduleGraph.elementAt(j), j);
1249     }
1250     int startupcore = 0;
1251     boolean setstartupcore = false;
1252     Schedule startup = null;
1253     int gid = scheduleGraph.elementAt(0).getGid();
1254     for(j = 0; j < scheduleGraph.size(); j++) {
1255       Schedule tmpSchedule = new Schedule(j, gid);
1256       ScheduleNode sn = scheduleGraph.elementAt(j);
1257
1258       Vector<ClassNode> cNodes = sn.getClassNodes();
1259       for(int k = 0; k < cNodes.size(); k++) {
1260         ClassNode cNode = cNodes.elementAt(k);
1261         ClassDescriptor cd = cNode.getClassDescriptor();
1262         Iterator it_flags = cNode.getFlags();
1263         while(it_flags.hasNext()) {
1264           FlagState fs = (FlagState)it_flags.next();
1265           Iterator it_edges = fs.edges();
1266           while(it_edges.hasNext()) {
1267             FEdge tmpfe = (FEdge)it_edges.next();
1268             TaskDescriptor td = (tmpfe).getTask();
1269             boolean contain = true;
1270             if(td.numParameters() > 1) {
1271               // td is a multi-param task, check if this core contains the
1272               // main cd of it
1273               ClassDescriptor cd1 = td2maincd.get(td);
1274               if(td2maincd.get(td).equals(cd)) {
1275                 contain = true;
1276                 td2maincore.put(td, tmpSchedule.getCoreNum());
1277               } else {
1278                 contain = false;
1279                 if(!td2allycores.containsKey(td)) {
1280                   td2allycores.put(td, new Vector<Schedule>());
1281                 }
1282                 Vector<Schedule> allycores = td2allycores.get(td);
1283                 if(!allycores.contains(tmpSchedule)) {
1284                   allycores.addElement(tmpSchedule);
1285                 }
1286                 allycores = null;
1287               }
1288               // If the FlagState can be fed to some multi-param tasks,
1289               // need to record corresponding ally cores later.
1290               tmpSchedule.addFState4TD(td, fs);
1291             }
1292             if(contain) {
1293               tmpSchedule.addTask(td);
1294               if(!td2cores.containsKey(td)) {
1295                 td2cores.put(td, new Vector<Schedule>());
1296               }
1297               Vector<Schedule> tmpcores = td2cores.get(td);
1298               if(!tmpcores.contains(tmpSchedule)) {
1299                 tmpcores.add(tmpSchedule);
1300               }
1301               tmpcores = null;
1302             }
1303             if(td.getParamType(0).getClassDesc().getSymbol().equals(
1304                  TypeUtil.StartupClass)) {
1305               assert(!setstartupcore);
1306               startupcore = j;
1307               startup = tmpSchedule;
1308               setstartupcore = true;
1309             }
1310           }
1311           it_edges = null;
1312         }
1313         it_flags = null;
1314       }
1315       cNodes = null;
1316
1317       // For each of the ScheduleEdge out of this ScheduleNode, add the
1318       // target ScheduleNode into the queue inside sn
1319       Iterator it_edges = sn.edges();
1320       while(it_edges.hasNext()) {
1321         ScheduleEdge se = (ScheduleEdge)it_edges.next();
1322         ScheduleNode target = (ScheduleNode)se.getTarget();
1323         Integer targetcore = sn2coreNum.get(target);
1324         switch(se.getType()) {
1325         case ScheduleEdge.NEWEDGE: {
1326           FlagState fs = se.getFstate();
1327           // Check if the new obj could be fed to some
1328           // multi-parameter task, if so, add for ally cores
1329           // checking
1330           Iterator it = fs.edges();
1331           boolean canTriggerSTask = false; // Flag indicates if fs can trigger
1332                                            // some single-param task
1333           while(it.hasNext()) {
1334             TaskDescriptor td = ((FEdge)it.next()).getTask();
1335             if(td.numParameters() > 1) {
1336               tmpSchedule.addFState4TD(td, fs);  // TODO
1337               // add this core as a allycore of td
1338               if(!td2allycores.containsKey(td)) {
1339                 td2allycores.put(td, new Vector<Schedule>());
1340               }
1341               Vector<Schedule> allycores = td2allycores.get(td);
1342               if(!allycores.contains(tmpSchedule)) {
1343                 allycores.addElement(tmpSchedule);
1344               }
1345             } else {
1346               canTriggerSTask = true;
1347             }
1348           }
1349           if(canTriggerSTask) {
1350             // Only transfer the obj when it can trigger some single-parm task
1351             // TODO: ensure that multi-param tasks have these objects
1352             for(int k = 0; k < se.getNewRate(); k++) {
1353               tmpSchedule.addTargetCore(fs, targetcore);
1354             }
1355           }
1356           break;
1357         }
1358
1359         case ScheduleEdge.TRANSEDGE: {
1360           // 'transmit' edge
1361           tmpSchedule.addTargetCore(se.getFstate(),
1362                                     targetcore,
1363                                     se.getTargetFState());
1364           // check if missed some FlagState associated with some
1365           // multi-parameter task, which has been cloned when
1366           // splitting a ClassNode
1367           FlagState fs = se.getSourceFState();
1368           FlagState tfs = se.getTargetFState();
1369           Iterator it = tfs.edges();
1370           while(it.hasNext()) {
1371             TaskDescriptor td = ((FEdge)it.next()).getTask();
1372             if(td.numParameters() > 1) {
1373               tmpSchedule.addFState4TD(td, fs);
1374               // add this core as a allycore of td
1375               if(!td2allycores.containsKey(td)) {
1376                 td2allycores.put(td, new Vector<Schedule>());
1377               }
1378               Vector<Schedule> allycores = td2allycores.get(td);
1379               if(!allycores.contains(tmpSchedule)) {
1380                 allycores.addElement(tmpSchedule);
1381               }
1382             }
1383           }
1384           break;
1385         }
1386         }
1387       }
1388       it_edges = sn.getScheduleEdgesIterator();
1389       while(it_edges.hasNext()) {
1390         ScheduleEdge se = (ScheduleEdge)it_edges.next();
1391         switch(se.getType()) {
1392         case ScheduleEdge.NEWEDGE: {
1393           // TODO, added 09/07/06
1394           FlagState fs = se.getFstate();
1395           // Check if the new obj could be fed to some
1396           // multi-parameter task, if so, add for ally cores
1397           // checking
1398           Iterator it = fs.edges();
1399           boolean canTriggerSTask = false; // Flag indicates if fs can trigger
1400                                            // some single-param task
1401           while(it.hasNext()) {
1402             TaskDescriptor td = ((FEdge)it.next()).getTask();
1403             if(td.numParameters() > 1) {
1404               tmpSchedule.addFState4TD(td, fs);  // TODO
1405               // add this core as a allycore of td
1406               if(!td2allycores.containsKey(td)) {
1407                 td2allycores.put(td, new Vector<Schedule>());
1408               }
1409               Vector<Schedule> allycores = td2allycores.get(td);
1410               if(!allycores.contains(tmpSchedule)) {
1411                 allycores.addElement(tmpSchedule);
1412               }
1413             } else {
1414               canTriggerSTask = true;
1415             }
1416           }
1417           if(canTriggerSTask) {
1418             for(int k = 0; k < se.getNewRate(); k++) {
1419               tmpSchedule.addTargetCore(se.getFstate(), j);
1420             }
1421           }
1422           break;
1423         }
1424
1425         case ScheduleEdge.TRANSEDGE: {
1426           // 'transmit' edge
1427           tmpSchedule.addTargetCore(se.getFstate(),
1428                                     j,
1429                                     se.getTargetFState());
1430           // check if missed some FlagState associated with some
1431           // multi-parameter task, which has been cloned when
1432           // splitting a ClassNode
1433           FlagState fs = se.getSourceFState();
1434           FlagState tfs = se.getTargetFState();
1435           Iterator it = tfs.edges();
1436           while(it.hasNext()) {
1437             TaskDescriptor td = ((FEdge)it.next()).getTask();
1438             if(td.numParameters() > 1) {
1439               tmpSchedule.addFState4TD(td, fs);
1440               // add this core as a allycore of td
1441               if(!td2allycores.containsKey(td)) {
1442                 td2allycores.put(td, new Vector<Schedule>());
1443               }
1444               Vector<Schedule> allycores = td2allycores.get(td);
1445               if(!allycores.contains(tmpSchedule)) {
1446                 allycores.addElement(tmpSchedule);
1447               }
1448             }
1449           }
1450           break;
1451         }
1452         }
1453       }
1454       it_edges = null;
1455       scheduling.add(tmpSchedule);
1456     }
1457
1458     int number = this.coreNum;
1459     if(scheduling.size() < number) {
1460       number = scheduling.size();
1461     }
1462
1463     Iterator<TaskDescriptor> it_mptds = td2maincd.keySet().iterator();
1464     while(it_mptds.hasNext()) {
1465       TaskDescriptor td = it_mptds.next();
1466       Vector<FEdge> fes = (Vector<FEdge>) this.taskAnalysis.getFEdgesFromTD(td);
1467       Vector<Schedule> cores = td2cores.get(td);
1468       assert(cores.size() == 1); // should have only one core
1469       for(int k = 0; k < cores.size(); ++k) {
1470         Schedule tmpSchedule = cores.elementAt(k);
1471
1472         // Make sure all the parameter objs of a multi-parameter
1473         // task would be send to right place after the task finished
1474         for(int h = 0; h < fes.size(); ++h) {
1475           FEdge tmpfe = fes.elementAt(h);
1476           FlagState tmpfs = (FlagState)tmpfe.getTarget();
1477           Vector<TaskDescriptor> tmptds = new Vector<TaskDescriptor>();
1478           if((tmpSchedule.getTargetCoreTable() == null)
1479              || (!tmpSchedule.getTargetCoreTable().containsKey(tmpfs))) {
1480             // add up all possible cores' info
1481             Iterator it_edges = tmpfs.edges();
1482             while(it_edges.hasNext()) {
1483               TaskDescriptor tmptd = ((FEdge)it_edges.next()).getTask();
1484               if(!tmptds.contains(tmptd)) {
1485                 tmptds.add(tmptd);
1486                 // only multiparam task will be processed here!!! TODO
1487                 Vector<Schedule> tmpcores = td2cores.get(tmptd);
1488                 for(int m = 0; m < tmpcores.size(); ++m) {
1489                   Schedule target = tmpcores.elementAt(m);
1490                   int targetcore = target.getCoreNum();
1491                   int num = target.getTaskNum(tmptd);
1492                   for(int n = 0; n < num; n++) {
1493                     tmpSchedule.addTargetCore(tmpfs, targetcore);
1494                   }
1495                 }
1496                 tmpcores = null;
1497               }
1498             }
1499             it_edges = null;
1500           }
1501           tmptds = null;
1502         }
1503       }
1504       fes = null;
1505       cores = null;
1506     }
1507     // Make sure all objs which could be feed to a multi-parameter
1508     // task would be send to all the possible task instances
1509     it_mptds = td2allycores.keySet().iterator();
1510     while(it_mptds.hasNext()) {
1511       TaskDescriptor td = it_mptds.next();
1512       Vector<Schedule> allycores = td2allycores.get(td);
1513       for(int i = 0; i < allycores.size(); i++) {
1514         Schedule tSchedule = allycores.elementAt(i);
1515         Vector<FlagState> tmpfss = tSchedule.getFStates4TD(td);
1516         int targetcore = td2maincore.get(td).intValue();
1517         for(int h = 0; h < tmpfss.size(); ++h) {
1518           tSchedule.addAllyCore(tmpfss.elementAt(h), targetcore);
1519         }
1520         tmpfss = null;
1521       }
1522     }
1523     it_mptds = null;
1524     td2cores = null;
1525     sn2coreNum = null;
1526     td2maincore = null;
1527     td2allycores = null;
1528
1529     return scheduling;
1530   }
1531 }