place.c

用c＋＋写的用于FPGA设计中布图布线的工具源码

       else {      /* Must be nonlinear_cong case. */
          update_region_occ (inet, &bb_coords[inet], 1, num_regions);
       } 
    }
 }
 
 if (place_cost_type == NONLINEAR_CONG) {
    cost = nonlinear_cong_cost (num_regions);
 }
 
 return (cost);
}


static float comp_td_point_to_point_delay (int inet, int ipin) {

  /*returns the delay of one point to point connection */

  int source_block, sink_block;
  int delta_x, delta_y;
  enum e_block_types source_type, sink_type;
  float delay_source_to_sink;

  delay_source_to_sink = 0.;

  source_block = net[inet].blocks[0];
  source_type = block[source_block].type;

  sink_block = net[inet].blocks[ipin];
  sink_type = block[sink_block].type;

  delta_x = abs(block[sink_block].x - block[source_block].x);
  delta_y = abs(block[sink_block].y - block[source_block].y);

  if (source_type == CLB) {
    if (sink_type == CLB) 
      delay_source_to_sink = delta_clb_to_clb[delta_x][delta_y];
    else if (sink_type == OUTPAD) 
      delay_source_to_sink = delta_clb_to_outpad[delta_x][delta_y];
    else {
      printf("Error in comp_td_point_to_point_delay in place.c, bad sink_type\n");
      exit(1);
    }
  }
  else if (source_type == INPAD) {
    if (sink_type == CLB) 
      delay_source_to_sink = delta_inpad_to_clb[delta_x][delta_y];
    else if (sink_type == OUTPAD) 
      delay_source_to_sink = delta_inpad_to_outpad[delta_x][delta_y];
    else {
      printf("Error in comp_td_point_to_point_delay in place.c, bad sink_type\n");
      exit(1);
    }
  }
  else {
    printf("Error in comp_td_point_to_point_delay in place.c, bad source_type\n");
    exit(1);
  }
  if (delay_source_to_sink < 0) {
    printf("Error in comp_td_point_to_point_delay in place.c, bad delay_source_to_sink value\n");
    exit(1);
  }

  if (delay_source_to_sink < 0.) {
    printf("Error in comp_td_point_to_point_delay in place.c, delay is less than 0\n");
    exit(1);
  }

  return(delay_source_to_sink);
}



static void update_td_cost(int b_from, int b_to, int num_of_pins) {
  /*update the point_to_point_timing_cost values from the temporary */
  /*values for all connections that have changed */  

  int blkpin, net_pin, inet, ipin;
    
    for (blkpin=0; blkpin<num_of_pins; blkpin++) {
 
      inet = block[b_from].nets[blkpin];

      if (inet == OPEN) 
	continue;
    
      if (is_global[inet]) 
	continue;
   
      net_pin = net_pin_index[b_from][blkpin];

      if (net_pin != 0) { 

	/*the following "if" prevents the value from being updated twice*/
	if (net[inet].blocks[0] != b_to && net[inet].blocks[0] != b_from) {

	  point_to_point_delay_cost[inet][net_pin] = 
	    temp_point_to_point_delay_cost[inet][net_pin];
	  temp_point_to_point_delay_cost[inet][net_pin] = -1;

	  point_to_point_timing_cost[inet][net_pin] = 
	    temp_point_to_point_timing_cost[inet][net_pin];
	  temp_point_to_point_timing_cost[inet][net_pin] = -1;
	}
      }
      else { /*this net is being driven by a moved block, recompute */
	/*all point to point connections on this net.*/
	for (ipin=1; ipin<net[inet].num_pins; ipin++) {

	  point_to_point_delay_cost[inet][ipin] = 
	    temp_point_to_point_delay_cost[inet][ipin];
	  temp_point_to_point_delay_cost[inet][ipin] = -1;

	  point_to_point_timing_cost[inet][ipin] = 
	    temp_point_to_point_timing_cost[inet][ipin];
	  temp_point_to_point_timing_cost[inet][ipin] = -1;
	}
      }
    }

    if (b_to != EMPTY) {
      for (blkpin=0; blkpin<num_of_pins; blkpin++) {
 
	inet = block[b_to].nets[blkpin];

	if (inet == OPEN) 
	  continue;
    
	if (is_global[inet]) 
	  continue;
   
	net_pin = net_pin_index[b_to][blkpin];

	if (net_pin != 0) { 

	/*the following "if" prevents the value from being updated 2x*/
	if (net[inet].blocks[0] != b_to && net[inet].blocks[0] != b_from) {

	    point_to_point_delay_cost[inet][net_pin] = 
	      temp_point_to_point_delay_cost[inet][net_pin];
	    temp_point_to_point_delay_cost[inet][net_pin] = -1;

	    point_to_point_timing_cost[inet][net_pin] = 
	      temp_point_to_point_timing_cost[inet][net_pin];
	    temp_point_to_point_timing_cost[inet][net_pin] = -1;
	  }
	}
	else { /*this net is being driven by a moved block, recompute */
	  /*all point to point connections on this net.*/
	  for (ipin=1; ipin<net[inet].num_pins; ipin++) {

	      point_to_point_delay_cost[inet][ipin] = 
		temp_point_to_point_delay_cost[inet][ipin];
	      temp_point_to_point_delay_cost[inet][ipin] = -1;

	      point_to_point_timing_cost[inet][ipin] = 
		temp_point_to_point_timing_cost[inet][ipin];
	      temp_point_to_point_timing_cost[inet][ipin] = -1;
	  }
	}
      }
    }
}


static void comp_delta_td_cost(int b_from, int b_to, 
				int num_of_pins, float *delta_timing, 
				float *delta_delay) {

  /*a net that is being driven by a moved block must have all of its  */
  /*sink timing costs recomputed. A net that is driving a moved block */
  /*must only have the timing cost on the connection driving the input*/
  /*pin computed*/

  int inet, k, net_pin, ipin;
  float delta_timing_cost, delta_delay_cost, temp_delay;

  delta_timing_cost = 0.;
  delta_delay_cost = 0.;


  for (k=0;k<num_of_pins;k++) { 
    inet = block[b_from].nets[k];

    if (inet == OPEN) 
      continue;
    
    if (is_global[inet]) 
      continue;
   
    net_pin = net_pin_index[b_from][k];

    if (net_pin != 0) { /*this net is driving a moved block               */

      /*if this net is being driven by a block that has moved, we do not  */
      /*need to compute the change in the timing cost (here) since it will*/
      /*be computed in the fanout of the net on  the driving block, also  */     
      /*computing it here would double count the change, and mess up the  */
      /*delta_timing_cost value */ 
      if (net[inet].blocks[0] != b_to && net[inet].blocks[0] != b_from) {
	temp_delay = comp_td_point_to_point_delay(inet, net_pin);

	temp_point_to_point_delay_cost[inet][net_pin] = temp_delay;
	temp_point_to_point_timing_cost[inet][net_pin] =
	  timing_place_crit[inet][net_pin] * temp_delay;

	delta_delay_cost += temp_point_to_point_delay_cost[inet][net_pin] -
	  point_to_point_delay_cost[inet][net_pin];

	delta_timing_cost += temp_point_to_point_timing_cost[inet][net_pin] - 
	  point_to_point_timing_cost[inet][net_pin];
      }
    }
    else { /*this net is being driven by a moved block, recompute */
      /*all point to point connections on this net.*/
      for (ipin=1; ipin<net[inet].num_pins; ipin++) {
	temp_delay = comp_td_point_to_point_delay(inet, ipin);
	
	temp_point_to_point_delay_cost[inet][ipin] = temp_delay;
	temp_point_to_point_timing_cost[inet][ipin] =
	  timing_place_crit[inet][ipin] * temp_delay;

	delta_delay_cost += temp_point_to_point_delay_cost[inet][ipin] -
	  point_to_point_delay_cost[inet][ipin];

	delta_timing_cost += temp_point_to_point_timing_cost[inet][ipin] - 
	  point_to_point_timing_cost[inet][ipin];
      }
    }
  }

  if (b_to != EMPTY) {
    for (k=0;k<num_of_pins;k++) { 
      inet = block[b_to].nets[k];

      if (inet == OPEN) 
	continue;
    
      if (is_global[inet]) 
	continue;
   
      net_pin = net_pin_index[b_to][k];

      if (net_pin != 0) { /*this net is driving a moved block*/

	/*if this net is being driven by a block that has moved, we do not */
	/*need to compute the change in the timing cost (here) since it was*/
	/*computed in the fanout of the net on  the driving block, also    */     
	/*computing it here would double count the change, and mess up the */
	/*delta_timing_cost value */ 
	if (net[inet].blocks[0] != b_to && net[inet].blocks[0] != b_from) {
	  temp_delay = comp_td_point_to_point_delay(inet, net_pin);

	  temp_point_to_point_delay_cost[inet][net_pin] = temp_delay;
	  temp_point_to_point_timing_cost[inet][net_pin] =
	    timing_place_crit[inet][net_pin] * temp_delay;

	  delta_delay_cost += temp_point_to_point_delay_cost[inet][net_pin] -
	    point_to_point_delay_cost[inet][net_pin];
	  delta_timing_cost += temp_point_to_point_timing_cost[inet][net_pin] - 
	    point_to_point_timing_cost[inet][net_pin];
	}
      }
      else { /*this net is being driven by a moved block, recompute */
	/*all point to point connections on this net.*/
	for (ipin=1; ipin<net[inet].num_pins; ipin++) {

	  temp_delay = comp_td_point_to_point_delay(inet, ipin);

	  temp_point_to_point_delay_cost[inet][ipin] = temp_delay;
	  temp_point_to_point_timing_cost[inet][ipin] =
	    timing_place_crit[inet][ipin] * temp_delay;
	    

	  delta_delay_cost += temp_point_to_point_delay_cost[inet][ipin] -
	    point_to_point_delay_cost[inet][ipin];
	  delta_timing_cost += temp_point_to_point_timing_cost[inet][ipin] - 
	    point_to_point_timing_cost[inet][ipin];
	}
      }
    }
  }

  *delta_timing = delta_timing_cost;
  *delta_delay = delta_delay_cost;
}

static void comp_td_costs (float *timing_cost, float *connection_delay_sum) {
  /*computes the cost (from scratch) due to the delays and criticalities*
   *on all point to point connections, we define the timing cost of     *
   *each connection as criticality*delay */

  int inet , ipin;
  float loc_timing_cost, loc_connection_delay_sum, temp_delay_cost, temp_timing_cost;

  loc_timing_cost = 0.;
  loc_connection_delay_sum = 0.;

  for (inet=0;inet<num_nets;inet++) {     /* for each net ... */
    if (is_global[inet] == FALSE) {    /* Do only if not global. */

      for (ipin=1; ipin<net[inet].num_pins; ipin++) {

	temp_delay_cost = comp_td_point_to_point_delay(inet, ipin);
	temp_timing_cost = temp_delay_cost *timing_place_crit[inet][ipin];

	loc_connection_delay_sum += temp_delay_cost;
	point_to_point_delay_cost[inet][ipin] = temp_delay_cost;
	temp_point_to_point_delay_cost[inet][ipin] = -1; /*undefined*/
	
	point_to_point_timing_cost[inet][ipin] = temp_timing_cost;
	temp_point_to_point_timing_cost[inet][ipin] = -1; /*undefined*/
	loc_timing_cost += temp_timing_cost;
      }
    }
  }
  *timing_cost = loc_timing_cost;
  *connection_delay_sum = loc_connection_delay_sum;
}


static float comp_bb_cost (int method, int place_cost_type, int num_regions) {

/* Finds the cost from scratch.  Done only when the placement   *
 * has been radically changed (i.e. after initial placement).   *
 * Otherwise find the cost change incrementally.  If method     *
 * check is NORMAL, we find bounding boxes that are updateable  *
 * for the larger nets.  If method is CHECK, all bounding boxes *
 * are found via the non_updateable_bb routine, to provide a    *
 * cost which can be used to check the correctness of the       *
 * other routine.                                               */

 int i, j, k; 
 float cost;

 cost = 0;

/* Initialize occupancies to zero if regions are being used. */

 if (place_cost_type == NONLINEAR_CONG) {
    for (i=0;i<num_regions;i++) {
       for (j=0;j<num_regions;j++) {
           place_region_x[i][j].occupancy = 0.;
           place_region_y[i][j].occupancy = 0.;
       }
    }
 }

 for (k=0;k<num_nets;k++) {     /* for each net ... */

    if (is_global[k] == FALSE) {    /* Do only if not global. */

/* Small nets don't use incremental updating on their bounding boxes, *
 * so they can use a fast bounding box calculator.                    */

       if (net[k].num_pins > SMALL_NET && method == NORMAL) {
          get_bb_from_scratch (k, &bb_coords[k], &bb_num_on_edges[k]);
       }
       else {
          get_non_updateable_bb (k, &bb_coords[k]);
       }
       
       if (place_cost_type != NONLINEAR_CONG) {
          net_cost[k] = get_net_cost(k, &bb_coords[k]);
          cost += net_cost[k];
       }
       else {      /* Must be nonlinear_cong case. */
          update_region_occ (k, &bb_coords[k], 1, num_regions);
       }
    }
 }

 if (place_cost_type == NONLINEAR_CONG) {
    cost = nonlinear_cong_cost (num_regions);
 }

 return (cost);
}


static float nonlinear_cong_cost (int num_regions) {

/* This routine computes the cost of a placement when the NONLINEAR_CONG *
 * option is selected.  It assumes that the occupancies of all the       *
 * placement subregions have been properly updated, and simply           *
 * computes the cost due to these occupancies by summing over all        *
 * subregions.  This will be inefficient for moves that don't affect     *
 * many subregions (i.e. small moves late in placement), esp. when there *
 * are a lot of subregions.  May recode later to update only affected    *
 * subregions.                                                           */

 float cost, tmp;
 int i, j;

 cost = 0.;

 for (i=0;i<num_re