mschedhash.java

来自「一种将c高级语言转化给VHDL的编译器」· Java 代码 · 共 1,684 行 · 第 1/5 页

      //for(int i=0; i<10 ; i++)
      //  x++;
      //that i could be incremented faster (or slower) than x, and the loop
      //might stop before (or after) x has been incremented 10 times.  
      //To prevent timing problems, I force all loads to time 0, and all
      //stores to time ii-1.  
      //(note, the loads and stores I am talking about here are ones
      //originally in the code and not those, which I insert myself)
      if((Load.conforms(inst))&&(Load.getSource(inst).isPrimal())) {
	if(_estart > _loadStore.getLoadTime())
	  _iiCnt = _eIICnt + 1;
	else
	  _iiCnt = _eIICnt;
        return (float)0.0;
      }
    
      //see the comments above
      if((Store.conforms(inst))&&(Store.getDestination(inst).isPrimal())) {
        
	//_iiCnt = _eIICnt + (int)((_estart)/(ii-1));
	_iiCnt = _eIICnt + (int)((_estart)/(ii));
	float corrctedEstart = adjustTimes.getCorrectedStartTime(_estart);
	if(corrctedEstart >= 1)
	  return corrctedEstart;
	else
	  return (float)1;
      }
    
    
      float currTime = _estart;
      float scheduleTime = -1;

      //first look for a time_int between min and max, where the instruction can 
      //be placed without causing resource conflicts--and if a instruction is 
      //placed later than one of its child instrutions needs it to be, the 
      //child will be unscheduled and later rescheduled

//make two while loops and add in stuff for load and store on loop edges
//and to make sure that pipelined instructions start on even cycles and 
//the others don't spill over cycle boundaries!!!!!
      
      while((scheduleTime == -1)&&(currTime <= ii)) {
	if((!_chipdef.analyzeHardwareUse(_bNode, inst, (int)currTime))||
	   (!_loadStore.testObsGenugZeitGibt(this, ii, currTime))||
	   (Math.abs(adjustTimes.getCorrectedStartTime(currTime)-currTime) 
	        > 0.001))//||
	   //((int)pStTime <= (int)currTime)) 
          currTime += _schedTimePrecision;
	else
          scheduleTime = currTime;
      }
      //keep track of the unroll time for calculating the ii cnt (number of
      //mod sched block itertions before execution of this instruction):
      float unrollOffset = currTime - _estart;
      currTime = 0;
      
      //if no time was found, wrap over and consider from 0 to estart (
      //this is legal, even though it is later than estart, because it
      //is one iteration of hte mod sched block later):
      while((scheduleTime == -1) && (currTime <= _estart)) {
	if((!_chipdef.analyzeHardwareUse(_bNode, inst, (int)currTime))||
	   (!_loadStore.testObsGenugZeitGibt(this, ii, currTime))||
	   (Math.abs(adjustTimes.getCorrectedStartTime(currTime)-currTime) 
	        > 0.001))//||
	   //((int)pStTime <= (int)currTime)) 
          currTime += _schedTimePrecision;
	else 
          scheduleTime = currTime;
      }
      //still keep track of the un roll offset:
      unrollOffset += currTime;
      
      
      //if no place was found, then just place it at the first spot (almost--
      //but I'll get back to that) and later the scheduler will unschedule
      //all other instructions in conflict.  This algorithm could possibly
      //get stuck in an infinite loop with instructions conintiuously 
      //pushing each other out of place, and so, the spot where the instruction
      //is to be placed is slowly moved forward in time to hopefully allow the
      //two instructions to miss each other.
      if(scheduleTime < 0) {
	//if estart is legal and later than the last starting time, 
	//schedule to estart:
	if(((oldStartTime < 0) || (_estart > oldStartTime))&&
	   (_loadStore.testObsGenugZeitGibt(this, ii, _estart))) { //&&
	   //((int)pStTime > (int)_estart)) {
          scheduleTime = adjustTimes.getCorrectedStartTime(_estart);
	}
	else {
	
	  //I search randomly for a time slot to place the instruction in
	  //this is different from Rau, who simply increments the last 
	  //schedule time.  This way, I hope to get greater variety between
	  //different attempts to schedule so that hopefully there is a
	  //greater probability that one will work
	  float roundingFactor = 1/_schedTimePrecision;
	  if(getRunLength() > 1)
            roundingFactor = 1;
	  float stoppingPoint = ii * roundingFactor -
	                        _triedTimes.size();
	
	  HashSet alreadyTried = new HashSet();
          boolean stop = false;
	  boolean reachedEnd = false;
	  do {
	    
            do {
	      //randomly choose a time from 0 to ii, and round off this 
	      //number to _schedTimePrecision-ths of a cycle
	      oldStartTime = (float)Math.random() * ii;
              oldStartTime = ((float)Math.round(oldStartTime * roundingFactor))/
	                                           roundingFactor;
	    //make sure this one hasn't been attempted already, either 
	    //this time (in alreadyTried) or ever (_triedTimes)
	    } while((alreadyTried.contains(new Float((float)oldStartTime)))||
	            (_triedTimes.contains(new Float((float)oldStartTime))));
	    
	    alreadyTried.add(new Float((float)oldStartTime));
	    //to prevent getting stuck in infinite loops, we need to notice
	    //when all legal slots have been tried and exit the loop
	    if(alreadyTried.size()>=stoppingPoint) {
	      stop = true;
	    }
	    oldStartTime = adjustTimes.getCorrectedStartTime(oldStartTime);
	  //make sure that this time allows enough space for loads and
	  //stores
	  }while((!_loadStore.testObsGenugZeitGibt(this, ii, oldStartTime))&&
	          (!stop));
	         //((int)pStTime <= (int)oldStartTime))&&(!stop));
	  if(stop)
	    oldStartTime = -1; //no valid time was found; do not schedule
	  else
	    _triedTimes.add(new Float((float)oldStartTime));
	  scheduleTime = oldStartTime;
	}
	oldStartTime = scheduleTime;
	
	//save unrolled schedule
	if(scheduleTime < _estart) {
	  unrollOffset = ii-_estart;
	  unrollOffset += scheduleTime;
	}
	else {
	  unrollOffset = scheduleTime;
	}
      }
      
      //set the number of iterations of the mod sched block (which is the 
      //estart ii cnt + the time in this iteration until starting (which is
      //the sum of the estart (which is the time from the beginning of this
      //iteration until exection) + the unroll offset, which is the time
      //after estart when scheduling is set to) divided by ii -1):
      //_iiCnt = _eIICnt + (int)((unrollOffset+_estart)/(ii-1));
      _iiCnt = _eIICnt + (int)((unrollOffset+_estart)/(ii));
      return scheduleTime;

    }
    
    /**
    Once again, it is useful to refer to Rau's paper.  Modulo scheduling is
    a type of list scheduling, where the order that instructions are
    considered for scheduling is based on a priority.  The priority used
    here is their "height", which is the distance from an instruction to the
    end of the schedule.  See the nested class min distance matrix defined
    below, for more.
    */
    public float getHeight() {
      return _minDistMat.getHeight(inst);
    }
  }//end nested class MSchedInstObject
  
  /**
  * This nested class is for inserting loads and stores into the schedule.  
  * If an unrolled loop is 12 cycles long, and modulo scheduling decides on 
  * an II of 4, the mod sched block of instructions will be 4 cycles long
  * and the instructions from cycle 0 in the unrolled loop will run in
  * parallel with those from cycle 4 and 8, and those from cycle 1 will run
  * in parallel with those from 5 and 9, and so on (this is not totally true
  * but is a nice simplification for understanding).  When the mod sched
  * block is iterated over, three iterations of the main loop run in
  * parallel executing different thirds.  But whereas the original loop
  * could communicate between cycles 3 and 4 and between 7 and 8 using
  * wires, since these cycles sit in different iterations of the mod sched
  * loop body, they need to have their values saved to and read from
  * registers.  During scheduling, I ensure that there is space for these
  * loads and stores, but after scheduling, the loads and stores must be 
  * inserted.  This class was created to do that.  It does it in two main
  * steps.  First, MSchedHash uses one of its own methods to search for 
  * places where a load and store is necessary and it calls the method 
  * "saveLS" from SaveStoresNLoads to save the location of a load and store
  * as well as the net that is being transferred, and the iteration of the
  * modulo scheduled block that it must be sent to. For example, in the 
  * schedule described above, if a value needs to be transfered from 3 to 4
  * it will save that there is a load and store necessary from iteration 0
  * to iteration 1, and if there is a value that needs to be transfered from
  * 3 to 7, it will save that a value needs to be saved from iteration 0 to
  * 1 and again from 1 to 2 (there needs to be 2 loads and stores or there
  * will be timing problems because it will try to use values from the next
  * iteration of the main, unrolled loop!).  The second major method in this
  * class is called "addLS".  After the times and nets have been saved for
  * all loads and stores, they need to be created, and scheduled into the 
  * block.
  */
  private class SaveStoresNLoads extends HashSet {
    
    //private HashMap _op2PrimMap = new HashMap();
    //private HashMap _op2LoadBlockVarMap = new HashMap();
    //private HashMap _op2StoreBlockVarMap = new HashMap();
  
    /**
    *  This nested class is used to save all the necessary information for 
    *  any load or store
    */
    private class LSObject {
    
      /**
      iteration where parent stops
      */
      public int startII=-1;
      /**
      iteration where child starts - iteration where parent stops
      */
      public int iiDiff = -1;
      /**
      time where parent stops exection (its schedule time plus effective
      delay)
      */
      public float parentStopTime = (float)-1;
      /**
      when creating the load and store instructions we need to know the
      necessary "Type" 
      */
      public Type type = null;
      /**
      the source wire that is being saved
      */
      public Operand op = null;
      /**
      the name of this wire at the end (it needs to have a different name to
      ensure it is really a different wire and that iteration 0 and 2 can't
      talk directly to each other)
      */
      public Operand newOp = null;
      
      /**
      constructor allowing all values to be set at once
      */
      public LSObject (int sII, int iiD, float pST, Type t, Operand o, 
                       Operand n) {
        startII=sII;
        iiDiff=iiD;
        parentStopTime=pST;
        type=t;
        op=o;
        newOp=n;
      }
    
    }//end class LSObject
    
    /**
    *  This nested class generates ModPrim variables which are primal
    *  variables (registers) for transfering data between blocks.  It 
    *  creates specific variables for different operands and for different
    *  iterations
    */
    private class ModPrimCreator extends HashMap {
      
      /**
      *  This nested class saves the modPrim variables for different times
      *  and the count associated with a specific operand to be transfered
      */
      private class ModPrimTable {
        public HashMap modprimsForTimes = null;
	public int primCreateCnt = -1;
	public ModPrimTable(HashMap mpTble, int primCnt) {
	  modprimsForTimes = mpTble;
	  primCreateCnt = primCnt;
	}
      }//end class ModPrimTable
      
      public ModPrimCreator() {
        super();
      }
      
      /**
      this method takes an Operand and the iteration where it was transfered
      from and creates a specific modPrim primal
      */
      public PrimalOperand getPrim(Operand op, int iiCnt) {
      
        HashMap modprimsForTimes = null;
        int primCreateCnt = -1;
        if(!containsKey(op)) { //if this operand does not have a modPrim yet
	  //increment the counter
	  _primCreateCnt++;
	  //save this counter for this operand
	  primCreateCnt = _primCreateCnt;
	  //make a table for different primals at different times
	  modprimsForTimes = new HashMap();
	  ModPrimTable modPrimTble = new ModPrimTable(modprimsForTimes, 
	                                              _primCreateCnt);
	  put(op, modPrimTble);
	}
	else {
	//if it does exist get it:
	  modprimsForTimes = ((ModPrimTable)get(op)).modprimsForTimes;
	  primCreateCnt = ((ModPrimTable)get(op)).primCreateCnt;
        }
	PrimalOperand modPrim = null;
	if(!modprimsForTimes.containsKey(new Integer(iiCnt))) {
	  //if a primal doesn't exist yet, create it
	  modPrim = Operand.newPrimal("modPrim" + primCreateCnt + "_" +
	                              iiCnt);
	  //save the new primal			      
	  modprimsForTimes.put(new Integer(iiCnt), modPrim);
	}
	else //otherwise get the saved one
	  modPrim = (PrimalOperand)modprimsForTimes.get(new Integer(iiCnt));
	//return the modprim
	return modPrim;
      }
      
    }//end class ModPrimCreator
    
    /**
    *  This nested class is similar to ModPrimCreator except that it creates
    *  new block variables to be used in the future iterations of the mod 
    *  sched block
    */
    private class NewBlockCreator extends HashMap {
      
      //becuase of the existence of the "nextBlock" method, saving a count
      //for each block is unnecessary
      
      public NewBlockCreator() {
        super();
      }