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