fdschedule.java

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

      /*if((isInstrPred((ArrayList) useLists.get(childInstr),(ArrayList)defLists
        		      .get(instr))) && 
        		      (newMax - getInstrRunLength(instr, chipDef) < 
        		      windowMap.getMax(instr)) &&
  			(areOutsNotPrimals((ArrayList) defLists.get(instr)))){*/
      if((isParentOf(instr, childInstr, useLists))&& 
         (newMax - getInstrRunLength(instr, chipDef) < 
	                              windowMap.getMax(instr))){
  	//sumtmp1 = ((Float)(sum.get(instr))).floatValue();
  	//for(int n_int =  (int)windowMap.getMax(instr); 
        	//n_int >= newMax - getInstrRunLength(instr, chipDef); n_int--){
        ArrayList forceTableForOp = ((ArrayList)(dG.get(instr.operator())));
	float oldWin = windowMap.getWinSize(instr);
	oldWin = (int)(oldWin + 0.999);
	if(oldWin == 0) oldWin = 1;
  	for(int n_int =  (int)windowMap.getMin(instr); 
        	n_int < (int)newMax; n_int++){
  	  if(n_int<0) {
  	    CanCalc = new Boolean(false);
  	    return 0;
  	  }
	  float newWin = newMax - windowMap.getMax(instr);
	  newWin = (int)(newWin + 0.999);
	  if(newWin == 0) newWin = 1;
	  int minIndex = (int)(n_int* timeMod);
	  float maxIndex =  (n_int + getInstrRunLength(instr, chipDef)) * timeMod;
	  for(int x = minIndex; x < maxIndex; x++) {
	  
	    float offset = ((Float)forceTableForOp.get(x)).floatValue();
	    force += (1/newWin - 1/oldWin) * offset;
	  
	  }
	  
  	  //float selfforcetmp = 1;
  	  //if(windowMap.getWinSize(instr) > 1)
  	    //selfforcetmp = (float)((int)((1/windowMap.getWinSize(instr))
        	//			 + 0.9));
  	  //sumtmp1 -= 2 * ((Float)(((ArrayList)(dG.get(instr.operator())))
        	//				    .get(n_int))).floatValue()
        	  //   * selfforcetmp;
  	}
  	for(int n_int =  (int)newMax; 
        	n_int <= (int)(windowMap.getMax(instr)+0.999); n_int++){
  	  if(n_int<0) {
  	    CanCalc = new Boolean(false);
  	    return 0;
  	  }
	  int minIndex = (int)(n_int* timeMod);
	  float maxIndex =  (n_int + getInstrRunLength(instr, chipDef)) * timeMod;
	  for(int x = minIndex; x < maxIndex; x++) {
	  
	    float offset = ((Float)forceTableForOp.get(x)).floatValue();
	    force += - (1/oldWin) * offset;
	  
	  }
  	}
  	//newMax -= getInstrRunLength(instr, chipDef);
	predecessorForce = recursivePredecessorForces(dG, instrlist, instr, 
        					      useLists, defLists, 
        					      newMax, windowMap, /*sum, */
        					      CanCalc, chipDef);
      }
      //else
  	//sumtmp1 = 0;
      //endif
    }//end foreach
    //this calculates the change in weights due to shrinking or growing the size of the window
    return force + predecessorForce;
  }
  
  //recursiveSuccessorForces is defined so:
  /** This method calculates forces acting on an instruction if it is placed 
   *  at a given time, as a result of earlier instructions in the hierarchy.
   * 
   * @param dG Weights as a result of other like operations (e.g. other add 
   *	 instructions) being executed or possibly being executed in tis time
   *	  step
   * @param instrlist list of instructions from hyperblock, whcih the
   *	  force-directed scheduler is working on
   * @param parentInstr the starting instruction, from which this    
   *	  recursive algorithm should attempt to go down 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 newMin ????
   * @param windowMin a hashmap saving the lower limit for scheduling
   *	  a given instruction (key=instruction; value=float value of the    
   *	  lower limit
   * @param windowMax a hashmap saving the upper limit for scheduling
   *	  a given instruction (key=instruction; value=float value of the    
   *	  upper limit
   * @param sum a sum of all forces acting in a timeslot
   * @param CanCalc ????
   * @param chipDef contains chip and board information such as     
   *	  where    arrays have been stored to memory and the availability of
   *	  hardware.
   * @return some of forces due to predecessors
   */
  public float recursiveSuccessorForces(HashMap dG, ArrayList instrlist, 
  					Instruction parentInstr, 
        				HashMap useLists, HashMap defLists, 
  					float newMin, FDWindows windowMap, 
        				/*HashMap sum,*/ Boolean CanCalc, 
        				ChipDef chipDef) {
    float successorForce = 0;
    //float sumtmp1 = 0;
    float force = 0;
    //foreach instruction
    for (Iterator it = ((ArrayList)instrlist).iterator(); it.hasNext(); ) {
      Instruction instr = (Instruction)it.next();   
      float timeMod = 1;
      if(getInstrRunLength(instr, chipDef) < 1)
	timeMod = _schedCycleFraction * _schedCycleFractionMod;
      //if(instr predecessor of above instr && new min > this instruction's old min)
      /*if((isInstrPred((ArrayList) useLists.get(instr), 
        			    (ArrayList) defLists.get(parentInstr)))
         &&  (newMin > windowMap.getMin(instr)) 
  	 &&  (areOutsNotPrimals((ArrayList) useLists.get(instr)))) {*/
      if((isParentOf(parentInstr, instr, useLists))&&  
         (newMin > windowMap.getMin(instr))) {
         
  	//sumtmp1 = ((Float)(sum.get(instr))).floatValue();
  	//for(n_int=min => new min; n_int++)
  	for(int n_int =  (int)windowMap.getMin(instr); 
               //(n_int <= newMin) && (n_int <  windowMap.getabsMax()); 
                n_int < (int)newMin; 
	        n_int++) {
  	  if(n_int<0) {
  	    CanCalc = new Boolean(false);
  	    return 0;
  	  }
  	  //float selfforcetmp = 1;
  	  //if(windowMap.getWinSize(instr) > 1)
          //  selfforcetmp = (float)((int)((1/windowMap.getWinSize(instr))
          //		  + 0.9));

        		
          ArrayList forceTableForOp = ((ArrayList)(dG.get(instr.operator())));
	  //sumtmp1 -= 2 * ((Float)(forceTableForOp.get(n_int))).floatValue()
          //	     * selfforcetmp;
	  
	  float oldWin = windowMap.getWinSize(instr);
	  oldWin = (int)(oldWin + 0.999);
	  if(oldWin == 0) oldWin = 1;
	  int minIndex = (int)(n_int* timeMod);
	  float maxIndex =  (n_int + getInstrRunLength(instr, chipDef)) *  
            		     timeMod;
	  /*System.out.println("timeMod " + timeMod) ;
	  System.out.println("n_int " + n_int) ;
	  System.out.println("minIndex " + minIndex) ;
	  System.out.println("timeMod " + timeMod) ;
	  System.out.println("maxIndex " + maxIndex) ;
	  System.out.println("instr " + instr) ;
	  System.out.println("newMin " + newMin) ;
	  System.out.println("getInstrRunLength(instr, chipDef) " + getInstrRunLength(instr, chipDef)) ;
	  */
	  for(int x = minIndex; x < maxIndex; x++) {
	  
	    float offset = ((Float)forceTableForOp.get(x)).floatValue();
	    force += - (1/oldWin) * offset;
	  
	  }
	  
  	}
  	for(int n_int = (int)newMin; 
               //(n_int <= newMin) && (n_int <  windowMap.getabsMax()); 
                n_int <= (int)(windowMap.getMax(instr)+0.999); 
	        n_int++) {
  	  if(n_int<0) {
  	    CanCalc = new Boolean(false);
  	    return 0;
  	  }

        		
          ArrayList forceTableForOp = ((ArrayList)(dG.get(instr.operator())));
	  
	  float oldWin = windowMap.getWinSize(instr);
	  oldWin = (int)(oldWin + 0.999);
	  if(oldWin == 0) oldWin = 1;
	  float newWin = windowMap.getMax(instr) - newMin;
	  newWin = (int)(newWin + 0.999);
	  if(newWin == 0) newWin = 1;
	  int minIndex = (int)(n_int* timeMod);
	  float maxIndex =  (n_int + getInstrRunLength(instr, chipDef)) *  
            		     timeMod;
	  for(int x = minIndex; x < maxIndex; x++) {
	  
	    float offset = ((Float)forceTableForOp.get(x)).floatValue();
	    force += (1/newWin - 1/oldWin) * offset;
	  
	  }
	  
  	}
  	successorForce = recursiveSuccessorForces(dG, instrlist, instr, 
        					  useLists, defLists, 
        					  newMin + 
        				   getInstrRunLength(instr, chipDef), 
        					  windowMap, /*sum, */
        					  CanCalc, chipDef);
  	//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 force + successorForce;
  } 

  public void initVariables(ArrayList instrlist, HashMap defLists, 
                            HashMap useLists, ChipDef chipDef, 
			    boolean ignorePredsNicht) {
    for (Iterator it = ((ArrayList)instrlist).iterator(); it.hasNext(); ) {
      Instruction instr = (Instruction)it.next();
      defLists.put(instr, new ArrayList());
      useLists.put(instr, new ArrayList());
      getDefandUseLists(instr,(ArrayList)defLists.get(instr),
                       (ArrayList)useLists.get(instr), ignorePredsNicht);
      chipDef.initOpUseLists(instr.operator());
    }
  }  
  /** this method was written to try and spread out instructions depending on 
   *  what kind of operator they used.  I wrote it to help with force-directed
   *  scheduling, but, it turns out it was unnecessary, because the great 
   *  Heather, had the answer to my problem all along!
   * 
   * @param instrList list of instructions from the hyperblock
   * @return new ordered list of instructions
   */
  public ArrayList orderInstructsForFD(ArrayList instrList) {
    HashMap opLists = new HashMap();
    ArrayList newList = new ArrayList();
    
    for (Iterator its = instrList.iterator(); 
      its.hasNext(); ) {
      Instruction inst = (Instruction)its.next();
      Operator op = inst.operator();
      if(!opLists.containsKey(op))
        opLists.put(op, new ArrayList());
      ((ArrayList)opLists.get(op)).add(inst);

    }
    
    Random rand = new Random();
    float randNum = 0;
    int leftToSchedule = instrList.size();
    while(leftToSchedule > 0) {
    
      randNum = rand.nextFloat();
      float prob = 0;
      for (Iterator its = opLists.keySet().iterator(); 
  	its.hasNext(); ) {
  	Operator op = (Operator)its.next();
        float oldProb = prob;
        prob += (float)((ArrayList)opLists.get(op)).size() / (float)leftToSchedule;
        if((oldProb < randNum)&&(randNum <= prob)) {
          newList.add(((ArrayList)opLists.get(op)).get(0));
          ((ArrayList)opLists.get(op)).remove(0);
          leftToSchedule--;
        }
      }  
    }
    /*for (Iterator its = instrList.iterator(); 
      its.hasNext(); ) {
      Instruction inst = (Instruction)its.next();
      Operator op = inst.operator();
      System.out.println("op " + op);
    }*/
    return  newList;
  }

  public void resetDG(HashMap dG, FDWindows windowMap, ChipDef chipDef) {
  
    dG.clear();
    
    for (Iterator it = (((HashMap)windowMap).keySet()).iterator(); 
    	 it.hasNext(); ) {
      Instruction instr = (Instruction)it.next();
      Operator op = instr.operator();
      ArrayList listofOps = new ArrayList();
      dG.put(op, listofOps);
      float max = windowMap.getMax(instr) + 
    		  getInstrRunLength(instr, chipDef);
      
      //System.out.println("abs instr " + instr);
      //System.out.println("max " + max);
      //System.out.println("abs max " + windowMap.getabsMax());
      //System.out.println("abs max+ runlength " + (windowMap.getabsMax()+ getInstrRunLength(instr, chipDef)));
      float timeMod = 1;
      if(getInstrRunLength(instr, chipDef) < 1)
        timeMod = _schedCycleFraction * _schedCycleFractionMod;
      
      while(listofOps.size() <= (windowMap.getabsMax() + 
    		                getInstrRunLength(instr, chipDef))*
				timeMod)
        listofOps.add(new Float(0));

      //for(n_int=instr min => max) 
      //   setweight(instr.getoperator, n_int, += 1/(max + instruction exec time - min)
      int minIndex = (int)(windowMap.getMin(instr)*
                           timeMod);
      float maxIndex =  max *  timeMod;
				  
      for(int n_int = minIndex;
    	      //(n_int <  max) && (n_int <  windowMap.getabsMax()); 
    	      n_int <  maxIndex; 
	      n_int++) {
    	
	float newWeight;
    	float winSize = (int)(windowMap.getWinSize(instr) + 
    	                      getInstrRunLength(instr, chipDef)+0.999);
	if(winSize == 0) winSize = 1;
	
	/*if(windowMap.getWinSize(instr) + 
    	    getInstrRunLength(instr, chipDef) < 1) {
	  float oldWeight = ((Float)listofOps.get(n_int)).floatValue();
    	  newWeight = oldWeight + 1;
    	}
	else {
	  float oldWeight = ((Float)listofOps.get(n_int)).floatValue();
	  float adjustment = 1/(windowMap.getWinSize(instr) 
    		                + getInstrRunLength(instr, chipDef));
    	  newWeight = oldWeight + adjustment;
    	}*/
	float adjustment = 1/winSize;
	float oldWeight = ((Float)listofOps.get(n_int)).floatValue();
    	newWeight = oldWeight + adjustment;
	listofOps.set(n_int, new Float(newWeight));
      }
    } 
    
  
  }
  
  public boolean calcForceTable(HashMap dG, FDWindows windowMap, ChipDef chipDef,
                                ArrayList instrlist, Instruction instr, 
				ArrayList force, HashMap defLists, HashMap useLists) {
    //HashMap sum = new HashMap();
    float sum = 0;
    Operator op1 = instr.operator();
    ArrayList forceTableForOp1 = (ArrayList)dG.get(op1);
    
    //foreach instruction
    //for (Iterator it = ((ArrayList)instrlist).iterator(); 
       //  it.hasNext(); ) {
      //Instruction instrTmp = (Instruction)it.next();
      //float runlength = getInstrRunLength(instrTmp, chipDef);
      //Operator op = instrTmp.operator();
      //ArrayList forceTableForOp = (ArrayList)dG.get(op);
      //ArrayList forceTableForOp = (ArrayList)dG.get(op1);
      //sum.put(instrTmp, new Float(0));
      
      float timeMod = 1;