mschedhash.java

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

      float storeStTime = corrstartTime + instObj.getRunLength();

      CorrectStartTimes corrStoreStTime 
	= new CorrectStartTimes(_storeInst, _chipdef, !GlobalOptions.packInstructions);

      float corrStStTime = corrStoreStTime.getCorrectedStartTime(storeStTime);
      float storeEndTime = corrStStTime + getStoreTime();

      if(instObj.getNoSuccs())
        storeEndTime = corrStStTime;
      if(storeEndTime > ii - 1)
        return false;
      
      return true;
      
    }
  
  } //end class LoadStoreObject
  
  /**
  *  This nested class is just a special version of HashSet, which is used
  *  by the main modulo scheduling method, "iterativeSchedule" to save all
  *  the instructions which need to be scheduled.  That method, decides when
  *  to stop its main loop, when this set becomes empty.
  */
  private class InstHashSet extends HashSet{
  
    /**
    We always want to schedule the instruction with the greatest "height"
    (see above for definition of height).  To reduce the amount of searching
    through the set for the highest instruction, this instruction is saved,
    and only needs to be changed when add, addAll, or remove is called--and
    in those cases usually, with minimum effort and not a full search of the
    entire set.
    */
    public MSchedInstObject tallestInst = null;
    
    public InstHashSet() { super(); }
    
    /**
    to initially create the hashset from a collection of MSchedInstObjects
    */
    public boolean addAll(Collection c) {
      if(c==null)
        return false;
      for (Iterator it1 = c.iterator(); it1.hasNext();) {
        MSchedInstObject instObj = (MSchedInstObject)it1.next();
	this.add(instObj);
      }
      return true;
    }
    
    /**
    add an object to the set, and if this object is "higher" than the saved
    "highest" then save it to the tallestInst private variable
    */
    public void add(MSchedInstObject instObj) {
      if((tallestInst == null) ||
         (instObj.getHeight() > tallestInst.getHeight()))
        tallestInst = instObj;
      super.add(instObj);
    }
  
    /**
    when combining two InstHashSets, the tallestInsts of the two need to be
    compared (assuming both are known) and the tallest of the two saved, and
    the rest of the instructions can be added without looking at their
    heights
    */
    public void addAll(InstHashSet c) {
      if(c.tallestInst == null) {
        this.addAll((Collection)c);
	return;
      }
      if((tallestInst == null) ||
         (c.tallestInst.getHeight() > tallestInst.getHeight()))
        tallestInst = c.tallestInst;
      super.addAll(c);
    }
    
    /**
    removes an instruction object from the set.  This is the one time where
    it might be necessary to search through the whole set for the the
    tallestInst--but only if the object that is removed happens to be the
    tallest object.
    */
    public void remove(MSchedInstObject instObjR) {
      super.remove(instObjR);
      if(tallestInst == instObjR) {
        tallestInst = null;
	for (Iterator it1 = this.iterator(); it1.hasNext();) {
          MSchedInstObject instObj = (MSchedInstObject)it1.next();
	  if((tallestInst == null) ||
             (instObj.getHeight() > tallestInst.getHeight()))
            tallestInst = instObj;
	}
      
      }
      
    }
  
  } //end class InstHashSet

  /**
  *  This nested class implements stuff specific to Rau's algorithm and more
  *  information can be obtained by reading his papers.  He generates a
  *  matrix where the x and y axis are all the instructions and the values
  *  in the matrix are the distances between these instructions.  The
  *  distances are the effective delays (see getDistance method above, but 
  *  this equals Delay-distance*II).  Rau inserts two pseudo nodes into the
  *  dependence flow graph, one called start and the other stop.  The
  *  min-distance matrix is used for two things.  First of all, as a
  *  priority assigning tool for use when scheduling instructions, their 
  *  height is calculated based on their min-distance to the stop pseudo
  *  node.  The second use for the min-distance matrix is to determine a
  *  minimum II (mII, which is greater than or equal to the max of the
  *  mResII--the minimum II due to resource constraints--and the mRecII--the
  *  minimum II due to dependencies) to start the modulo scheduling 
  *  algorithm on.  This is done by taking advantage of the fact that the
  *  min-dist matrix varies based on the ii, since the effective delay
  *  changes (see equation above) and that in the matrix, the distance 
  *  between an instruction and itself cannot be positive--which would mean
  *  that the second occurance of that instruction happens later than the
  *  first one in the loop body.  Therefore, to search for this mII, the
  *  min-dist can be continuously recalculated for greater and greater IIs
  *  until a legal min-dist matrix is found. This is the min II, but there 
  *  is no gaurrantee that the scheduler will find a legal schedule at this 
  *  II.  I know this is badly explained, but this is only a paraphrase of 
  *  what I remember from reading Rau's paper. For more help understanding,
  *  refer to him.
  *
  *  the matrix is saved in a hashMap of hashmaps:
  *  key: nodes from dependence flow graph, including start and stop pseudo
  *       nodes
  *  value: HashMap where key: nodes from dependence flow graph
  *                       values: distances
  */
  private class MinDistMatrix extends HashMap {
  
    /**
    This helps me to find a node associated with an instruction
    key: instruction
    value: node in the dependence flow graph
    */
    private HashMap _inst2NodeMap = new HashMap();
    
    
    public MinDistMatrix() {
      super();
    }
    
   /**
   this method was written so that the DependenceFlowGraph method "findNode"
   would not need to be called every time a node needs to be found, since
   that would slow the program down a lot.  Each time a node is found, it is
   saved in the private hashmap _inst2NodeMap, and everytime after that,
   that the node is needed, it is gotten from the hashmap instead of from
   searching through the graph.
   */
    private DependenceFlowNode findNode(Instruction i) {
      if(_inst2NodeMap.containsKey(i))
        return (DependenceFlowNode)_inst2NodeMap.get(i);
      DependenceFlowNode tmpNode = _dfg.findNode(i);
      _inst2NodeMap.put(i, tmpNode);
      return tmpNode;
    }
    
    /**
    calculate the "height" by looking for the distance between a node
    associated with instruction i and the stop pseudo node
    */
    public float getHeight(Instruction i) {
      DependenceFlowNode n = findNode(i);
      if(n == null)
        return (float)0;
      return get(n, _dfg.sTOP());
    }
  
    /**
    get the distance between two instructions
    */
    public float get(Instruction i0, Instruction i1) {
      DependenceFlowNode n0 = findNode(i0);
      DependenceFlowNode n1 = findNode(i1);
      return get(n0, n1);
    }
  
    /**
    get the distance between two nodes
    */
    public float get(DependenceFlowNode n0, DependenceFlowNode n1) {
      HashMap row = (HashMap)this.get(n0);
      return ((Float)row.get(n1)).floatValue();
    }
  
    /**
    save the distance between two instructions
    */
    public void put(Instruction i0, Instruction i1, float v) {
      DependenceFlowNode n0 = findNode(i0);
      DependenceFlowNode n1 = findNode(i1);
      put(n0, n1, v);
    }
    
    /**
    save the distance between two nodes
    */
    public void put(DependenceFlowNode n0, DependenceFlowNode n1, float v) {
      if(!this.containsKey(n0))
        this.put(n0, new HashMap());
      HashMap row = (HashMap)this.get(n0);
      row.put(n1, new Float(v));
    }
    
    /**
    see if a distance exists for the location referenced by instructions i0
    and i1
    */
    public boolean containsKey(Instruction i0, Instruction i1) {
      DependenceFlowNode n0 = findNode(i0);
      DependenceFlowNode n1 = findNode(i1);
      return containsKey(n0, n1);
    }
  
    /**
    see if a distance exists for the location referenced by nodes n0 and n1
    */
    public boolean containsKey(DependenceFlowNode n0, DependenceFlowNode n1) {
      if(!this.containsKey(n0))
        return false;
      HashMap row = (HashMap)this.get(n0);
      return row.containsKey(n1);
    }
  
    /**
    this was copied from Rau's paper.  For each two connecting nodes, save
    the effective delay between them and then save a distance of 0 between
    each node and the stop pseudo node.  Return true or false based on
    whether this matrix is legal
    */
    public boolean compMinDist(int ii) {
    
      HashSet nList = (HashSet)_dfg.getAllNodes();
      for (Iterator it1 = nList.iterator(); 
        	it1.hasNext();) {
	DependenceFlowNode cNode = (DependenceFlowNode)it1.next();
	Instruction cInst = cNode.getInstruction();
	if(cInst == null) continue;
	MSchedInstObject cObj = (MSchedInstObject)instToObjMap.get(cInst);
	if(!cObj.getNoPreds()) {
          for (Iterator it2 = cObj.getListOfPreds().iterator(); 
        	  it2.hasNext();) {
	    MSchedInstObject pObj = (MSchedInstObject)it2.next();
	    DependenceFlowNode pNode = findNode(pObj.inst);
	    float effDelay = pObj.getEffectiveDelay(cInst, ii);
	    put(cNode, pNode, effDelay);
          }
	}
      }
    
      for (Iterator it1 = nList.iterator(); 
        	it1.hasNext();) {
	DependenceFlowNode cNode = (DependenceFlowNode)it1.next();
	put(cNode, _dfg.sTOP(), (float)0);
      }
    
      return (createMinDistMat(ii));
    
    }
    
    /**
    this was also copied from Rau's paper.  For any two nodes who are
    connected through a third node, save the greatest distance (whether that
    be the direct connection or the sum of the two connections)--why a
    MIN-distance matrix wants the max, I'll never understand, but this is
    exactly what Rau does.  If the delay between any node and itself is
    positive, this matrix is illegal and the method will return true.
    */
    public boolean createMinDistMat(int ii) {
    
      HashSet nList = (HashSet)_dfg.getAllNodes();
      for (Iterator m = nList.iterator(); m.hasNext();) {
	DependenceFlowNode nodeM = (DependenceFlowNode)m.next();
	for (Iterator i = nList.iterator(); i.hasNext();) {
          DependenceFlowNode nodeI = (DependenceFlowNode)i.next();
	  //check that there is a connection from nodeI to nodeM
          if(containsKey(nodeI, nodeM)) {
            for (Iterator j = nList.iterator(); j.hasNext();) {
              DependenceFlowNode nodeJ = (DependenceFlowNode)j.next();
	      //check if there is a connection from nodeM to nodeJ
              if(containsKey(nodeM, nodeJ)) {
        	float delay = get(nodeI, nodeM) + get(nodeM, nodeJ);
        	if((!containsKey(nodeI, nodeJ))||(delay < get(nodeI, nodeJ))) {
		      //set distance from nodeI to nodeJ equal to 
		      //the distance from nodeI to nodeM +
		      //the distance from nodeM to nodeJ
		      //longer connections are ignored, but this is how 
		      //this algorithm is described in Rau's paper, and 
		      //implemented in Trimaran
                  put(nodeI, nodeJ, delay);
                  if((nodeI == nodeJ) && (delay > 0)) {
                    //if diagonal is positive, invalid matrix
		    return true;
                  }
        	}
              }
            }
          }
	}
      }
      return false; 
    
    }
  
  /** This method calculates the minimum Inititiation interval due to recursion 
   *  (interiteration data dependencies).  It does this by using the method 
   *  compMinDist, which creates a minimum distance matrix, which is a matrix 
   *  describing the distance between all nodes in the dependence graph.  Each 
   *  row and column corresponds to a node, and the intersection point between 
   *  them has the distance between these two nodes saved.  The diagonal from 
   *  the top left to the bottom right, describes distances between nodes and 
   *  themselves.  If any of these values are positive, we know we must increase 
   *  II, as it is impossible to have any distance between a node and itself.  
   *  CalculateRecMII calls compMinDist repeatedly doubling II, until it fails 
   *  to create a valid minimum distance matrix.  Then it searches between a 
   *  minimum and maximum value of II, slowly cutting the distance between the 
   *  two by half to try and get as close to the correct II as possible.  Please 
   *  read Rau's articles for a better and more full description of this 
   *  algorithm.
   * 
   * @param dfg dependence flow graph
   * @param chipInfo1 chip information
   * @param ii iniitiation interval to use as seed for starting search
   */
    public int calculateRecMII(int ii) { 
    //um, this was