cluster.c

fpga设计评估软件

/* This routine returns a block which has not been clustered, has  *
 * no connection to the current cluster, satisfies the cluster     *
 * clock constraints, and has ext_inps external inputs.  If        *
 * there is no such block it returns NO_CLUSTER.  Remove_flag      *
 * controls whether or not blocks that have already been clustered *
 * are removed from the unclustered_list data structures.  NB:     *
 * to get a block regardless of clock constraints just set clocks_ *
 * avail > 0.                                                      */

 struct s_ilink *ptr, *prev_ptr;
 int iblk;
 
 prev_ptr = &unclustered_list_head[ext_inps];
 ptr = unclustered_list_head[ext_inps].next;

 while (ptr != NULL) {
    iblk = ptr->iblk;

    if (cluster_of_block[iblk] == NO_CLUSTER) {
       if (clocks_feasible (iblk, 0, clocks_avail, lut_size, NULL)) 
          return (iblk);

       prev_ptr = ptr;

    }

    else if (remove_flag == REMOVE_CLUSTERED) {
       prev_ptr->next = ptr->next;
    }

    ptr = ptr->next;
 }
 
 return (NO_CLUSTER);
}


/*****************************************/
static int get_free_block_with_most_ext_inputs (int lut_size, int inputs_avail, 
       int clocks_avail) {

/* This routine is used to find the first seed block for the clustering   *
 * and to find new blocks for clustering when there are no feasible       *
 * blocks with any attraction to the current cluster (i.e. it finds       *
 * blocks which are unconnected from the current cluster).  It returns    *
 * the block with the largest number of used inputs that satisfies the    *
 * clocking and number of inputs constraints.  If no suitable block is    *
 * found, the routine returns NO_CLUSTER.                                 */

 int iblk, ext_inps, istart;

 istart = min (lut_size, inputs_avail);

 for (ext_inps=istart;ext_inps>=0;ext_inps--) {
    iblk = get_block_by_num_ext_inputs (ext_inps, lut_size, clocks_avail, 
                    REMOVE_CLUSTERED);
    if (iblk != NO_CLUSTER) 
       return (iblk);
 }

 return (NO_CLUSTER);   /* No suitable block found. */
}


/*****************************************/
static void reset_cluster (int *inputs_used, int *luts_used, 
       int *clocks_used, int* next_empty_location_in_cluster, 
       int *block_in_cluster, int cluster_size) {

/* Call this routine when starting to fill up a new cluster.  It resets *
 * the gain vector, etc.                                                */

 int i;

/* If statement below is for speed.  If nets are reasonably low-fanout,  *
 * only a relatively small number of blocks will be marked, and updating *
 * only those block structures will be fastest.  If almost all blocks    *
 * have been touched it should be faster to just run through them all    *
 * in order (less addressing and better cache locality).                 */

 *inputs_used = 0;
 *luts_used = 0;
 *clocks_used = 0;
 *next_empty_location_in_cluster=0;

 for (i=0;i<num_marked_blocks;i++){ 
   gain[marked_blocks[i]] = 0.0;
   lengthgain[marked_blocks[i]]=0.0;
   sharinggain[marked_blocks[i]]=NOT_VALID;
   hillgain[marked_blocks[i]]=NOT_VALID;
   connectiongain[marked_blocks[i]]=0;
 }


 num_marked_blocks = 0;
                                                          
 for (i=0;i<num_marked_nets;i++) {
   num_pins_of_net_in_cluster[marked_nets[i]] = 0;
   net_output_in_cluster[marked_nets[i]] = FALSE;
 }

 for (i=0; i<cluster_size;i++)
   block_in_cluster[i]=NO_CLUSTER;

 num_marked_nets = 0;
}
/*****************************************/
static void update_connection_gain_values (int inet, int clustered_block, 
					   int pin_on_clustered_block,
					   boolean *is_clock) {
  /*This function is called when the connectiongain values on the net*
   *inet require updating.   */

  enum e_net_relation_to_clustered_block net_relation_to_clustered_block;
  int iblk, ipin;



  if (pin_on_clustered_block==0){  
    /*these designations are only valid for non-clock nets*/
    net_relation_to_clustered_block=OUTPUT;
  }
  else{
    net_relation_to_clustered_block=INPUT;
  }
    
  if (net_relation_to_clustered_block==OUTPUT && !is_clock[inet]){
    for (ipin=1;ipin<net[inet].num_pins;ipin++) {
      iblk = net[inet].pins[ipin];
      if (cluster_of_block[iblk] == NO_CLUSTER) {
	connectiongain[iblk] ++;
      }
    }
  }

  if(net_relation_to_clustered_block==INPUT && !is_clock[inet]){ 
    /*Calculate the connectiongain for the block which is driving *
     *the net that is an input to a block in the cluster */

    iblk=net[inet].pins[0];
    if (cluster_of_block[iblk] == NO_CLUSTER) {
      connectiongain[iblk] ++;
    }
  }
}
/*****************************************/
static void update_length_gain_values (int inet, int clustered_block, 
				       int pin_on_clustered_block,
				       boolean *is_clock) {

  /*This function is called when the length_gain values on the net*
   *inet requires updating.   */

  enum e_net_relation_to_clustered_block net_relation_to_clustered_block;
  float lengain;
  int newblk, netpin, ifirst;
  int iblk, ipin;


/* Check if this net lists its driving block twice.  If so, avoid  *
 * double counting this block by skipping the first (driving) pin. */
   if (net_output_feeds_driving_block_input[inet] == FALSE) 
    ifirst = 0;
  else
    ifirst = 1;

  if (pin_on_clustered_block==0){  
    /*these designations are only valid for non-clock nets*/
    net_relation_to_clustered_block=OUTPUT;
  }
  else{
    net_relation_to_clustered_block=INPUT;
  }
    
  if (net_relation_to_clustered_block==OUTPUT && !is_clock[inet]){
    for (ipin=ifirst;ipin<net[inet].num_pins;ipin++) {
      iblk = net[inet].pins[ipin];
      if (cluster_of_block[iblk] == NO_CLUSTER) {
	lengain=get_net_pin_backward_criticality(inet, ipin);
	if (lengain>lengthgain[iblk])
	  lengthgain[iblk]=lengain;
      }
    }
  }

  if(net_relation_to_clustered_block==INPUT && !is_clock[inet]){ 
    /*Calculate the length gain for the block which is driving *
     *the net that is an input to a block in the cluster */

    newblk=net[inet].pins[0];
    if (cluster_of_block[newblk] == NO_CLUSTER) {
      netpin= get_net_pin_number(clustered_block, pin_on_clustered_block);
      lengain=get_net_pin_forward_criticality(inet, netpin);
      if (lengain>lengthgain[newblk])
	lengthgain[newblk]=lengain;
    }
  }
}
/*****************************************/
static void mark_and_update_partial_gain (int inet, 
       enum e_gain_update gain_flag,
       int lut_size, int clustered_block, int pin_on_clustered_block,
       boolean* is_clock, boolean timing_driven, boolean connection_driven) {

/* Updates the marked data structures, and if gain_flag is GAIN,  *
 * the gain when a logic block is added to a cluster.  The        *
 * sharinggain is the number of inputs that a block shares with   *
 * blocks that are already in the cluster. Hillgain is the        *
 * reduction in number of pins-required by adding a block to the  *
 * cluster. The lengthgain is the criticality of the most critical*
 * net between this block and a block in the cluster.             */

 int iblk, ipin, ifirst;

/* Mark net as being visited, if necessary. */

 if (num_pins_of_net_in_cluster[inet] == 0) {
    marked_nets[num_marked_nets] = inet;
    num_marked_nets++;
 }

/* Update gains of affected blocks. */

 if (gain_flag == GAIN) {

/* Check if this net lists its driving block twice.  If so, avoid  *
 * double counting this block by skipping the first (driving) pin. */
  
    if (net_output_feeds_driving_block_input[inet] == FALSE) 
       ifirst = 0;
    else
       ifirst = 1;
       
   if (num_pins_of_net_in_cluster[inet]==0) {
     for (ipin=ifirst;ipin<net[inet].num_pins;ipin++) {
       iblk = net[inet].pins[ipin];
       if (cluster_of_block[iblk] == NO_CLUSTER) {

	 if (sharinggain[iblk] == NOT_VALID) {
	   marked_blocks[num_marked_blocks] = iblk;
	   num_marked_blocks++;
	   sharinggain[iblk]=1;
	   hillgain[iblk] = 1 - num_ext_inputs (iblk, lut_size);
	 }
	 else {
	   sharinggain[iblk]++;
	   hillgain[iblk]++;
	 }
       }
     }
   }

   if (connection_driven) {
     update_connection_gain_values(inet, clustered_block, pin_on_clustered_block, 
				   is_clock);
   }
   else if (timing_driven) {
     update_length_gain_values(inet, clustered_block, pin_on_clustered_block,
			       is_clock);
   }	       
 }
    
 num_pins_of_net_in_cluster[inet]++;
}
/*****************************************/
static void  recompute_length_gain_values(int *block_in_cluster, 
					  int next_empty_location_in_cluster,
					  int lut_size,
					  boolean global_clocks, 
					  boolean *is_clock) {

  /*This function recomputes all of the length_gain values for any *
   *nets that are affected by blocks that have been added to       *
   *current cluster.                                               */

  int ipin, inet, iblk;
  int i,idx;

  for (i=0;i<num_marked_blocks;i++){ 
    iblk=marked_blocks[i];
    lengthgain[iblk] = 0.0;
  }
  
  for (idx=0; idx < next_empty_location_in_cluster; idx++) {
    iblk=block_in_cluster[idx];
    
    inet = block[iblk].nets[0];  /*output pin first */
    if (inet != OPEN) {
      if (!is_clock[inet] || !global_clocks) 
	update_length_gain_values(inet, iblk, 0, is_clock);
    }

    for (ipin=1;ipin<=lut_size;ipin++) {   /*  LUT input pins. */
      inet = block[iblk].nets[ipin];
      if (inet != OPEN)
      	update_length_gain_values(inet, iblk, ipin, is_clock);
    }
  }
}
/*****************************************/
static void update_total_gain(float alpha, boolean timing_driven, boolean 
			      connection_driven){

  /*Updates the total  gain array to reflect the desired tradeoff between*
   *input sharing (sharinggain) and path_length minimization (lengthgain)*/

  int i, iblk;
  
  if (connection_driven) {
    /*try to absorb as many connections as possible*/
    for (i=0;i<num_marked_blocks;i++){ 
      iblk=marked_blocks[i];    
      gain[iblk] = (1-alpha)*(float)sharinggain[iblk] + alpha*(float)connectiongain[iblk];
    }
  }

  else if (timing_driven) {
    for (i=0;i<num_marked_blocks;i++){ 
      iblk=marked_blocks[i];
      gain[iblk] = alpha*lengthgain[iblk]+
	gain_for_each_net_shared*(float)sharinggain[iblk]; /*1-alpha term is accounted*
							    *for in gain_for_each...  *
							    *this saves overhead of   *
							    *dividing every time      */
    }
  }
  else { /*non timing_driven, minimize number of inputs used*/
    for (i=0;i<num_marked_blocks;i++){ 
      iblk=marked_blocks[i];
      gain[iblk] = (float)sharinggain[iblk];
    }
  }
}
/*****************************************/
static void add_to_cluster (int new_blk, int cluster_index, int lut_size, 
      boolean *is_clock, boolean global_clocks, int *inputs_used,
      int *luts_used, int *clocks_used, float alpha, boolean timing_driven, 
      boolean connection_driven) {

/* Marks new_blk as belonging to cluster cluster_index and updates  *
 * all the gain, etc. structures.  Cluster_index should always      *
 * be the index of the currently open cluster.                      */

 int ipin, inet;

 cluster_of_block[new_blk] = cluster_index;
 (*luts_used)++;
 
 inet = block[new_blk].nets[0];    /* Output pin first. */

/* Output should never be open but I check anyway.  I don't change  *
 * the gain for clock outputs when clocks are globally distributed  *
 * because I assume there is no real need to pack similarly clocked *
 * FFs together then.  Note that by updating the gain when the      *
 * clock driver is placed in a cluster implies that the output of   *
 * LUTs can be connected to clock inputs internally.  Probably not  *
 * true, but it doesn't make much difference, since it will still   *
 * make local routing of this clock very short, and none of my      *
 * benchmarks actually generate local clocks (all come from pads).  */

 if (inet != OPEN) {
    if (!is_clock[inet] || !global_clocks) 
      mark_and_update_partial_gain (inet, GAIN, lut_size, new_blk, 0, is_clock,
				    timing_driven, connection_driven);
    else
       mark_and_update_partial_gain (inet, NO_GAIN, lut_size, new_blk, 0, 
				     is_clock, timing_driven, connection_driven);

    net_output_in_cluster[inet] = TRUE;

    if (num_pins_of_net_in_cluster[inet] > 1 && !is_clock[inet])
       (*inputs_used)--;
 }

 for (ipin=1;ipin<=lut_size;ipin++) {   /*  LUT input pins. */

    inet = block[new_blk].nets[ipin];
    if (inet != OPEN) {
       mark_and_update_partial_gain (inet, GAIN, lut_size, new_blk, ipin, 
				     is_clock, timing_driven, connection_driven);

/* If num_pins_of_net_in_cluster != 1, then either the output is *
 * in the cluster or an input for this net is already in the     *
 * cluster.  In either case we don't need a new pin.             */

       if (num_pins_of_net_in_cluster[inet] == 1) 
          (*inputs_used)++;
    }
 }

/* Note:  The code below ONLY WORKS when nets that go to clock inputs *
 * NEVER go to the input of a LUT.  It doesn't really make electrical *
 * sense for that to happen, and I check this in the check_clocks     *
 * function.  Don't disable that sanity check.                        */

 inet = block[new_blk].nets[lut_size+1];    /* Clock input pin. */
 if (inet != OPEN) {
    if (global_clocks) 
       mark_and_update_partial_gain (inet, NO_GAIN, lut_size, new_blk, 
				     lut_size+1, is_clock, timing_driven,
				     connection_driven);
    else
       mark_and_update_partial_gain (inet, GAIN, lut_size, new_blk, 
				     lut_size+1, is_clock, timing_driven,