fdschedule.java

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

      if(getInstrRunLength(instr, chipDef) < 1)
        timeMod = _schedCycleFraction * _schedCycleFractionMod;
      for(int n_int =  (int)windowMap.getMin(instr); 
    	      n_int <= windowMap.getMax(instr); 
              n_int++) {
        
    	//float sumtmp = 1;
        //if(windowMap.getWinSize(instrTmp) > 1)  		  
        //  sumtmp = 1/windowMap.getWinSize(instrTmp);
        
	float winSize = windowMap.getWinSize(instr);
	winSize = (int)(winSize + 0.999); //round up because it is full cycles
	                                  //that the instruction affects
	if(winSize == 0) winSize = 1;
	int minIndex = (int)(n_int* timeMod);
	float maxIndex =  (n_int + getInstrRunLength(instr, chipDef)) *  
                           timeMod;
	for(int x = minIndex;
	        x < maxIndex;
		x++) {
	  //float oldSum = ((Float)sum.get(instrTmp)).floatValue();
	  float offset = ((Float)forceTableForOp1.get(x)).floatValue();
	  offset *= 1/winSize;
	  //sum.put(instrTmp, new Float(oldSum + offset));
	  sum += offset;
	}
      }
       
    //}//end foreach instruction
     
    //for(n_int=window(instr, min)=> window(instr,max))
    float initMaxIndex =  (windowMap.getabsMax() + 
                           getInstrRunLength(instr, chipDef) ) * timeMod;
    for(int n_int=0; n_int <= initMaxIndex; n_int++) {
      force.add(new Float(0.0));
    }
    for(int n_int=(int)windowMap.getMin(instr); 
    	    n_int <= windowMap.getMax(instr); 
            n_int++) {
    
      Boolean predForcesSetOk = new Boolean(true);
      Boolean succForcesSetOk = new Boolean(true);
      //float selfforcetmp = 1;
    
      //if(windowMap.getWinSize(instr) > 1)			
      //  selfforcetmp = 1/windowMap.getWinSize(instr);
	
      //float oldSum = ((Float)sum.get(instr)).floatValue();
      //offset *= selfforcetmp;
      float tmp = (n_int + getInstrRunLength(instr, chipDef));
      float recursivePredForces = recursivePredecessorForces(dG, instrlist, instr, 
    						  useLists, defLists, n_int,
    						  windowMap, /*sum,*/ 
    						  predForcesSetOk, chipDef);
      float recursiveSuccForces = recursiveSuccessorForces(dG, instrlist, instr, 
    						useLists, defLists, 
    						n_int + getInstrRunLength(instr, 
						                          chipDef),
    						windowMap, /*sum,*/ 
    						succForcesSetOk, chipDef);
    
      int minIndex = (int)(n_int* timeMod);
      float maxIndex =  (n_int + getInstrRunLength(instr, chipDef)) * timeMod;
      for(int x = minIndex;
	      x <= maxIndex;
	      x++) {
	float offset = ((Float)forceTableForOp1.get(x)).floatValue();
	float oldForce = ((Float)force.get(x)).floatValue();

	//force.set(x, new Float( offset - oldSum + oldForce + recursivePredForces 
	force.set(x, new Float( offset - sum + oldForce + recursivePredForces 
    		        	+ recursiveSuccForces));
      }
      //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.
      if((!(predForcesSetOk.booleanValue()))||
    	 (!(succForcesSetOk.booleanValue())))
        return false;
    }//end for
    return true;
  }
  
  
  public float findScheduleTime(FDWindows windowMap, ChipDef chipDef, 
                                Instruction instr, ArrayList force,
				ArrayList instrlist, HashMap useLists, 
        			HashMap defLists ) {
      
    float smallestLoc = -1;
    float smallestForce = 999999999;
    HashSet alreadyTried = new HashSet();
    
    float winSize = windowMap.getWinSize(instr);
    float timeMod = 1;
    //Random ranNum = new Random(System.currentTimeMillis());
    //OwnRanNumGen ranNum = new OwnRanNumGen((int)System.currentTimeMillis());
    if(getInstrRunLength(instr, chipDef) < 1)
      timeMod = _schedCycleFraction * _schedCycleFractionMod;
    //System.out.println("instr " + instr);
    //System.out.println("timeMod " + timeMod);
    //winSize = (int)(winSize + 0.999); 
    float cycle = 0;
    if(winSize == 0) {
      cycle = windowMap.getMin(instr);
	  /*System.out.println("fd instr " + instr);
	  System.out.println("fd cycle " + cycle);
	  System.out.println("fd windowMap.getMin(instr) " + windowMap.getMin(instr));
	  System.out.println("fd windowMap.getMax(instr) " + windowMap.getMax(instr));*/
      if(chipDef.analyzeHardwareUse(_node, instr, (int)cycle))
        smallestLoc = cycle;
      else
        return (float)-1.0;
    }
    else {
      int roundingFactor = (int)_schedCycleFraction;
      if(getInstrRunLength(instr, chipDef) > 1)
        roundingFactor = 1;
      float stoppingPoint = winSize * roundingFactor;
      while(alreadyTried.size() <= stoppingPoint) {
	cycle = 0;
	float correctedCycle = 0;
	do {
	
          //cycle = (float)Math.random() * winSize + windowMap.getMin(instr);
          //System.out.println("ranNum.ran2() " + ranNum.ran2());
	  //int tries=0;
	  //boolean hardwareConflict = false;
	  //boolean stop = false;
	  do {
	    cycle = ranNum.ran2() * winSize + windowMap.getMin(instr);
          //cycle = ranNum.nextFloat() * winSize + windowMap.getMin(instr);
            cycle = ((float)Math.round(cycle * roundingFactor))/roundingFactor;
	    //if(tries>=winSize * roundingFactor)
	      //return (float)-1.0;
	    //tries++;
	  /*System.out.println("fd instr " + instr);
	  System.out.println("fd cycle " + cycle);
	  System.out.println("fd windowMap.getMin(instr) " + windowMap.getMin(instr));
	  System.out.println("fd windowMap.getMax(instr) " + windowMap.getMax(instr));*/
	  //System.out.println("fd cycle " + cycle);
	  //System.out.println("alreadyTried.contains(new Float((double)cycle)) " + alreadyTried.contains(new Float((double)cycle)));
	    //hardwareConflict = !chipDef.analyzeHardwareUse(_node, instr, (int)cycle);
	    /*if(hardwareConflict) {
	      if(alreadyTried.size() > stoppingPoint)
	        return (float)-1.0;
	      else
	        stop = false;
	    }
	    else if(alreadyTried.size() <= stoppingPoint)
	      stop = false;
	    else
	      stop = true;*/
	  //System.out.println("hardwareConflict " + hardwareConflict);
	    /*if(hardwareConflict) {
	      //stoppingPoint--;
	      alreadyTried.add(new Float((double)cycle));
	    }*/
	  //System.out.println("stoppingPoint) " + stoppingPoint);
	  //System.out.println("alreadyTried.size() " + alreadyTried.size());
	  //System.out.println("alreadyTried " + alreadyTried);
	  //}while(!stop);
	  } while((alreadyTried.contains(new Float((double)cycle)))/*&&
	           alreadyTried.size() <= stoppingPoint/*&&
	          (hardwareConflict)*/);
	  //if(alreadyTried.size() > stoppingPoint) return smallestLoc;
	  alreadyTried.add(new Float((double)cycle));
	  //System.out.println("instr " + instr);
	  //System.out.println("windowMap.getMin(instr) " + windowMap.getMin(instr));
	  //System.out.println("windowMap.getMax(instr) " + windowMap.getMax(instr));
	  //System.out.println("cycle " + cycle);
	  //we don't want operations less than a clock tick to start so that 
	  //spill over the cycle boundary
	  //if(((int)cycle) != ((int)(cycle + getInstrRunLength(instr, chipDef))))
	  //   stoppingPoint--;
          CorrectStartTimes adjustTimes = new CorrectStartTimes(instr, chipDef,
					                        !GlobalOptions.packInstructions);
	  correctedCycle = adjustTimes.getCorrectedStartTime(cycle);
	  //if(correctedCycle != cycle) {
	  //  alreadyTried.add(new Float((double)cycle));
	/*System.err.println("instr " + instr);
        System.err.println("windowMap.getMin(instr) " + windowMap.getMin(instr));
        System.err.println("windowMap.getMax(instr) " + windowMap.getMax(instr));
        System.err.println("b4 correctedCycle " + correctedCycle);
        System.err.println("cycle " + cycle);*/
	  //}
	  //System.err.println("alreadyTried.size() " + alreadyTried.size());
	  //System.err.println("stoppingPoint " + stoppingPoint);
        //System.err.println("in 2nd loop");

	}while((//(alreadyTried.contains(new Float((double)cycle)))||
               //(cycle < winSize + windowMap.getMin(instr) ) &&
	       /*(correctedCycle > windowMap.getMax(instr)) ||
	       (correctedCycle < windowMap.getMin(instr)) ||
	       */(!setWindowSuccessors(instrlist, instr, useLists, defLists, (FDWindows)windowMap.copy(), 
        		             correctedCycle + getInstrRunLength(instr, chipDef), chipDef)) ||
	       (!setWindowPredecessors(instrlist, instr, useLists, defLists, windowMap.copy(), 
        		               correctedCycle, chipDef)))&&
	       (alreadyTried.size() <= stoppingPoint));//&&
	        	 //+ getInstrRunLength(instr, chipDef))&&
	        //(((int)cycle) != ((int)(cycle + getInstrRunLength(instr, chipDef)))));
	//alreadyTried.add(new Float((double)cycle));
	cycle = correctedCycle;
        //System.out.println("exited 2nd while loop");

        //CorrectStartTimes adjustTimes = new CorrectStartTimes(instr, chipDef,
	//				                      GlobalOptions.doNotPackInstrucs);
	int forceTableIndex = (int)(cycle * timeMod);
	float forceAtTime = ((Float)force.get(forceTableIndex)).floatValue();

	if((forceAtTime < smallestForce)&&
    	   (chipDef.analyzeHardwareUse(_node, instr, (int)cycle))) {

          smallestForce = forceAtTime;
          smallestLoc = cycle;
	}
      }
    }
    return smallestLoc;
  }
  
  public void seed(int seed) { ranNum.seed(seed);}

  private class OwnRanNumGen { 
    //this is copied and adapted from Numerical Recipes in C, Cambridge
    //University Press, 
    private int _seed;
    /*private long _lword;
    private long _irword;
    private long c1[] = {0xbaa96887, 0x1e17d32c, 0x03bcdc3c,
        	   0x0f33d1b2};
    private long c2[] = {0x4b0f3b58, 0xe874f0c3, 0x6955c5a6,
                   0x55a7ca46};
    private long idums = 0;
    private long jflone = 0x3f800000;
    private long jflmsk = 0x007fffff;
    */
    public OwnRanNumGen() {/*_seed = -1;*/ ran2();}
    public OwnRanNumGen(int seed) {/*_seed = -1; ran2();*/ _seed = seed;}
    
    public void seed(int seed) {_seed = seed;}
    
    /*public void psdes() {
    
      long ia, ib, iswap, itmph=0, itmpl=0;
      for (int i=0;i<4;i++) {
        iswap = _irword;
	ia= iswap ^ c1[i];
	itmpl = ia & 0xffff;
	itmph = ia >> 16;
	ib = itmpl*itmpl + ~(itmph*itmph);
	ia = (ib >> 16) | ((ib & 0xffff) << 16);
	_irword = (_lword) ^ (((ia)^ c2[i])+itmpl*itmph);
	_lword = iswap;
      }
    }
    
    public float ran4() {
    
      long irword, itemp, lword;
      _seed = -1;
      if(_seed < 0) {
        idums = - _seed;
	_seed = 1;
      }
      irword = _seed;
      lword = idums;
      _lword = lword;
      _irword = irword;
      psdes();
      
      itemp = jflone | (jflmsk & _irword);
      ++_seed;
      System.out.println("itemp " + (float)itemp);
      return (float)itemp - (float)1.0;
    }*/

  
    private double standardDev = 0.75;
    private int idum2=123456789;
    private int iy=0;
    private int IM1 = 2147483563;
    private int IM2 = 2147483399;
    private float AM = (float)((float)1.0/(float)IM1);
    private int IMM1 = IM1 - 1;
    private int IA1 = 40014;
    private int IA2 = 40692;
    private int IQ1 = 53668;
    private int IQ2 = 52774;
    private int IR1 = 12211;
    private int IR2 = 3791;
    private int NTAB = 32;
    private float NDIV = (float)(1+(float)IMM1/(float)NTAB);
    private float EPS = (float)1.2e-7;
    private float RNMX = (float)(1.0-EPS);
    private int[] iv = new int[(int)NTAB];
    public float ran2() {

      int j;
      int k;
      float temp;
      if(_seed <= 0) {

	if(-_seed < 1) _seed=1;
	else _seed = -_seed;
	idum2=_seed;
	for(j=(int)(NTAB+7);j>=0;j--) {

          k=_seed/IQ1;
	  _seed=IA1*(_seed-k*IQ1)-k*IR1;
	  if(_seed<0) _seed += IM1;
	  if(j<NTAB) iv[j] = _seed;

	}
	iy=iv[0];

      }
      k=_seed/IQ1;
      _seed=IA1*(_seed-k*IQ1)-k*IR1;
      if(_seed<0) _seed += IM1;
      k=idum2/IQ2;
      idum2=IA2*(idum2-k*IQ2)-k*IR2;
      //System.out.println("start idum2 " + idum2);
      if(idum2<0) idum2+=IM2;
      //System.out.println("idum2 " + idum2);
      j=(int)(iy/NDIV);
      if(j==32) j--;
      /*System.out.println("iy " + iy);
      System.out.println("iy/NDIV " + iy/NDIV);
      System.out.println("(int)(iy/NDIV) " + (int)(iy/NDIV));
      System.out.println("(float)(iy/NDIV) " + (float)(iy/NDIV));
      System.out.println("(int)((float)(iy)/NDIV) " + (int)((float)(iy)/NDIV));
      System.out.println("j " + j);
      System.out.println("iv " + iv);
      System.out.println("iv[j] " + iv[j]);
      System.out.println("idum2 " + idum2);*/
      iy=iv[j]-idum2;
      //System.out.println("end iy " + iy);
      iv[j]=_seed;
      if(iy<1) iy += IMM1;
      if((temp=AM*iy)>RNMX) return RNMX;
      else return temp;

    }
    
    public float gaussRan() {
    
      double ranTmp = Math.log((double)ran2()*standardDev*Math.sqrt(2.0*Math.PI));
      return (float)Math.sqrt(-2.0*standardDev*standardDev*ranTmp);
    
    }
    
  }

}