fdschedule.java

一种将c高级语言转化给VHDL的编译器

/*
 *
 LA-CC 05-135 Trident 0.7.1

Copyright Notice
Copyright 2006 (c) the Regents of the University of California.

This Software was produced under a U.S. Government contract
(W-7405-ENG-36) by Los Alamos National Laboratory, which is operated
by the University of California for the U.S. Department of Energy. The
U.S. Government is licensed to use, reproduce, and distribute this
Software. Permission is granted to the public to copy and use this
Software without charge, provided that this Notice and any statement
of authorship are reproduced on all copies. Neither the Government nor
the University makes any warranty, express or implied, or assumes any
liability or responsibility for the user of this Software.


 */


package fp.flowgraph;

import java.util.*;
import fp.util.*;
import fp.*;
import java.io.*;
import java.util.Random;
import fp.hardware.*;

public class FDSchedule extends Schedule
{
  
  private float _schedCycleFraction = 40;
  private float _schedCycleFractionMod = (float)1;
  private DependenceFlowGraph _dfg;
  private  _Conns _connectionCalculator = new _Conns();
  private  OwnRanNumGen ranNum; 
  
  /*public FDSchedule(DependenceFlowGraph dfg) {
    super(false, null);
    _dfg = dfg;
    ranNum = new OwnRanNumGen((int)System.currentTimeMillis());
  }
  public FDSchedule(DependenceFlowGraph dfg, boolean packNicht) {
    super(packNicht, null);
    _dfg = dfg;
    ranNum = new OwnRanNumGen((int)System.currentTimeMillis());
  }*/
  public FDSchedule(DependenceFlowGraph dfg, BlockNode node) {
    super(node);    
    _dfg = dfg;
    ranNum = new OwnRanNumGen((int)System.currentTimeMillis());
  }

  /*
  force Directed Scheduling
     
  force directed scheduling attempts to spread out the execution of the same type of instructions (e.g. adds, muls, and divs)
    so that they are executed, as much as possible at different times.  
       
  step 1)
  calculate windows when instructions can be executed, based on the times found by ASAP and ALAP
  and calculate a "force" due to the same type of instruction being executed at the same time
    foreach instruction
      find the ASAP and ALAP execution times
  minTime = minimum of two
  maxTime = max of two
  save window (instruction, minTime, maxtime)
  for(n_int=minTime => maxTime)
    set weight(operator, n_int, += 1/(maxTime + instr_exec_time - minTime)
  end foreach
     
  Step 2)
  here is where actual scheduling is done.  this can be divided into three substeps
  foreach instruction
    substep a)
  calculate forces for instruction
    foreach instruction
      for(n_int=window(instr, min)=> window(instr,max))
        sum(instr) += weight(n_int)*(1/(max-min))
  end foreach
    for(n_int=window(instr, min)=> window(instr,max))
      force(n_int) = -(sum(instr) - 2 * weight(n_int)*(1/(max-min))) +
        recursivePredecessorForces(instr, n_int) +
  recursiveSuccessorForces(instr, n_int + this instruction's exec time);
  it is done this way, because the force is equal to weight(n_int)*(1/(max-min)) - weight(all other ns)*(1/(max-min))
    because we are calculating the change in force due to not placing the instructions in all those other ns, but
      placing it at n_int.  We also need to calculate how this move will change all predecessors and successors.
  
  recursivePredecessorForces is defined so:
  predecessorForce = 0
  foreach instruction
    if(instr predecessor of above instr && new max < this instruction's old max)
      sumtmp1 = sum(instr);
  for(n_int=max => new max - this instructions execution time; n_int--)
    sumtmp1-=2 * weight(n_int) * 1/(this instruction's max-min)
  predecessorForce = recursivePredecessorForces(this instruction, n_int)
  else
    sumtmp1 = 0;
  endif
    end foreach
      this calculates the change in weights due to shrinking or growing the size of the window
  return sumtmp1 + predecessorForce;
  
  recursiveSuccessorForces is defined so:
  successorForce = 0
  foreach instruction
    if(instr predecessor of above instr && new min > this instruction's old min)
      sumtmp1 = sum(instr);
  for(n_int=min => new min; n_int++)
    sumtmp1-=2 * weight(n_int) * 1/(this instruction's max-min)
  successorForce = recursiveSuccessorForces(this instruction, n_int + this instruction's exec time)
  else
    sumtmp1 = 0;
  endif
    end foreach
      this calculates the change in weights due to shrinking or growing the size of the window
  return sumtmp1 + successorForce;
   
  end for
     
  substep b)
  schedule instruction at the point of its minimum force
    for(n_int=min=>max)
      find min force, save n_int
        setexecTime(instruction, n_int)
   
  substep c)
  recalculate weights and windows
  savewindow(instruction, n_int, n_int + instruction execution time)
   
  setWindowSuccessors(inst, n_int + instruction execution time)
  setWindowPredecessors(inst, n_int + instruction execution time)
   
  where setWindowSuccessors is
  foreach sucessor
    if(n_int + instruction execution time > old min)
      setwindow(sucessor, n_int + instruction execution time, oldmax)
  setWindowSuccessors(list, n_int + instruction execution time)
  end foreach
     
  and where setWindowPredecessors is
  foreach sucessor
    if(n_int + instruction execution time < old max)
      setwindow(sucessor, oldmin, n_int + instruction execution time)
  setWindowPredecessors(list, n_int + instruction execution time)
  end foreach
     
  for(n_int= 0 => end of setweight database) 
    setweight(instr.getoperator, n_int, 0)
  foreach instruction in savewindows
    for(n_int=instr min => max) 
      setweight(instr.getoperator, n_int, += 1/(max + instruction exec time - min)
   
   
  */
  
  private class Randomator extends Random {
  
    public Randomator() {
      super();
    }
    public Randomator(long seed) {
      super(seed);
    }
    public double nextDouble() {
      return (double)ranNum.ran2();
      //return (double)ranNum.gaussRan();
    }
    public float nextFloat() {
      return ranNum.ran2();
      //return ranNum.gaussRan();
    }
  
  }
    
  /** This method performs a force-directed schedule of the list of instructions
   *  saved in @param instrlist.  It can ignore instruction predicates and 
   *  schedule operations to be executed regardless of whether the predicate is 
   *  true or not (except when the instruction writes to a primal).
   * 
   * @param instrlist list of unscheduled instructions from hyperblock
   * @param aSAPlist copy of the list of instructions from the           
   *      hyperblock, which has been ASAP scheduled
   * @param aLAPlist copy of the list of instructions from the           
   *      hyperblock, which has been ALAP scheduled
   * @param ignorePredsNicht tells the scheduler to ignore predicates    
   *      except when the instruction is writing to a primal; true=do not     
   *      ignore them, false=ignore them
   * @param chipDef contains chip and board information such as where   
   *      arrays have been stored to memory and the availability of hardware.
   * @return whether scheduling was successful
   */
  public boolean fD_Schedule(ArrayList instrlist, FDWindows windowMap, 
                             boolean ignorePredsNicht, ChipDef chipDef) {
    HashMap defLists = new HashMap();
    HashMap useLists = new HashMap();
    HashMap dG = new HashMap(); //force table
    
    //chipDef.resetBusCntsAtAllTimes();
    
    //initialize use and deflists and save how many of each type of operator 
    //are used
    initVariables(instrlist, defLists, useLists, chipDef, ignorePredsNicht);
		   
    
    resetDG(dG, windowMap, chipDef);

    
    //Step 2)
    //here is where actual scheduling is done.  this can be divided into three substeps
    //Random ranNum2 = new Random(System.currentTimeMillis());
    Random ranNum2 = (Random)new Randomator(System.currentTimeMillis());
    ArrayList instrucListCopy = new ArrayList(instrlist);
    while(0 < instrucListCopy.size()){
      Collections.shuffle(instrucListCopy, ranNum2);
      //instrucListCopy = orderInstructsForFD(instrucListCopy);
      
      //find the guy with the smallest window:      
      Instruction instr = windowMap.findInstWithMinWin(instrucListCopy);    
      //find random instruction (this is much slower since the windows are bigger):
      //Instruction instr = (Instruction)instrucListCopy.iterator().next();    
     
     //remove him from the list so he won't be scheduled again
      instrucListCopy.remove(instr);
      
      //substep a)
      //calculate forces for instruction
      ArrayList force = new ArrayList();
      if(!calcForceTable(dG, windowMap, chipDef, instrlist, instr, force, defLists,
                         useLists)) {
        System.out.println("failed calc force");
	return false;
      }
      //=========================================================================================================================== 
      //substep b)
      //schedule instruction at the point of its minimum force
      float smallestLoc = findScheduleTime(windowMap, chipDef, instr, force, 
                                           instrlist, useLists, defLists);


      if(smallestLoc == -1/*||
    	 (!chipDef.analyzeHardwareUse(_node, instr, (int)smallestLoc))*/) {
        System.out.println("failed on instr "+ instr);
        //System.out.println("smallestLoc "+ smallestLoc);
    	return false;
      }
      else {
      /*if((smallestLoc != -1)/*&&
    	 (chipDef.analyzeHardwareUse(instr, (int)smallestLoc))) {*/
    	  
        chipDef.saveNewHardwareUsage(_node, instr, (int)smallestLoc);
    	 
        //set the execution and clock times 
    	instr.setExecTime(smallestLoc);
    	instr.setExecClkCnt((int)smallestLoc);
    	 
    	//=========================================================================================================================== 
    	//substep c)
    	//recalculate weights and windows

        //reset window size for this instruction to its execution time
    	windowMap.putWin(instr, smallestLoc, smallestLoc);
    	
    	//reset his successor's and predecessor's windows
        //setWindowSuccessors(inst, n_int + instruction execution time)
    	if(!setWindowSuccessors(instrlist, instr, useLists, defLists, windowMap, 
        		        smallestLoc + getInstrRunLength(instr, chipDef) /*+
				          (1/_schedCycleFraction)*/, 
        		        chipDef)) {
          System.out.println("set window sucs");
	  return false;	
    	}
	//setWindowPredecessors(inst, n_int + instruction execution time)
    	if(!setWindowPredecessors(instrlist, instr, useLists, defLists, windowMap, 
        		          smallestLoc /*- (1/_schedCycleFraction)*/, chipDef)) {
          System.out.println("set window preds");
	  return false;	  
        }
    	//change weights:
	resetDG(dG, windowMap, chipDef);
    	

      } 
      //return false;
       
    }//end foreach instruction
    
    chipDef.saveSharedOps();	  
     
     
    return true;
       
  }
   
  //debug methods:
   
  /** This methode was written for helping to debug the force directed 
   *  scheduler.  It takes the list of instructions, @param instrlist, and 
   *  saves text representing the possible execution window for each 
   *  instruction.  This execution window is initialized with the ASAP 
   *  scheduled time as the minimum possible time for the Force-directed 
   *  scheduler to schedule an instruction, and with the ALAP as the maximum 
   *  possible.  This method goes recursively up through the instruction 
   *  hierarchy determining analyzing to know how to print.
   * 
   * @param instrlist list of instructions from hyperblock, whcih the 
   *	 force-directed scheduler is working on
   * @param childInstr the starting instruction, from which this     
   *	  recursive algorithm should attempt to go up from through the      
   *	  dependence hierarchy
   * @param useLists a hashmap saving a list of all operands being   
   *	  used for a given instruction (key=instruction; value=list of used 
   *	  operands)
   * @param defLists a hashmap saving a list of all operands being   
   *	  defined by a given instruction (key=instruction; value=list of    
   *	  defined operands)
   * @param windowMax a hashmap saving the upper limit for scheduling
   *	  a given instruction (key=instruction; value=float value of the    
   *	  upper limit
   * @param windowMin a hashmap saving the lower limit for scheduling
   *	  a given instruction (key=instruction; value=float value of the    
   *	  lower limit
   * @param n_int time step, which for which information is currently
   *	  being printed
   * @param printOutVarName a boolean variable telling how to print  
   *	  the output operand
   * @param depthInfo a hashmap saving text representing the	     
   *	  execution windows for each instruction
   * @param depth ???
   * @NewTag ...
   */
  public void printPredecessorWindows(ArrayList instrlist, 
  				      Instruction childInstr, HashMap useLists, 
        			      HashMap defLists, HashMap windowMax, 
  				      HashMap windowMin, int n_int, 
        			      boolean printOutVarName, HashMap depthInfo, 
        			      int depth) {
    for (Iterator it = ((ArrayList)instrlist).iterator(); it.hasNext(); ) {
      Instruction instr = (Instruction)it.next();   
      if((isInstrPred((ArrayList) useLists.get(childInstr), 
         (ArrayList) defLists.get(instr)))&&
         (areOutsNotPrimals((ArrayList) defLists.get(instr)))) {
  	printPredecessorWindows(instrlist, instr, useLists, defLists, 
        			windowMax, windowMin, n_int, 
        			printOutVarName, depthInfo, depth);
  	depth--;
  	if(!(depthInfo.containsKey(instr))) {
  	  depthInfo.put(instr, new ArrayList());
  	  ((ArrayList)(depthInfo.get(instr))).add(new Integer(depth));
  	  ((ArrayList)(depthInfo.get(instr))).add("");
  	}
  	else
  	  if(depth <  ((Integer)(((ArrayList)(depthInfo.get(instr)))
        					      .get(0))).intValue())
  	    ((ArrayList)(depthInfo.get(instr))).set(0, new Integer(depth));