place.c

fpga设计评估软件

  /*computes net_pin_index array, this array allows us to quickley*/
  /*find what pin on the net a block pin corresponds to */

  int inet, netpin, blk, iblk, ipin;

  /*initialize values to OPEN */
  for (iblk=0; iblk<num_blocks; iblk++)
    for (ipin=0; ipin < pins_per_clb; ipin++)
      net_pin_index[iblk][ipin] = OPEN;

  for (inet=0; inet<num_nets; inet++) {

    if (is_global[inet]) 
      continue;

    for(netpin=0;netpin<net[inet].num_pins;netpin++) {
      blk=net[inet].blocks[netpin];
      if (block[blk].type == INPAD)
	net_pin_index[blk][0] = 0; /*there is only one block pin,so it is 0, and it */
                                   /*is driving the net since this is an INPAD*/
      else if (block[blk].type == OUTPAD) 
	net_pin_index[blk][0] = netpin;  /*there is only one block pin,it is 0*/
      else {
	net_pin_index[blk][net[inet].blk_pin[netpin]] = netpin;
      }  
    }  
  }
}


static double get_std_dev (int n, double sum_x_squared, double av_x) {

/* Returns the standard deviation of data set x.  There are n sample points, *
 * sum_x_squared is the summation over n of x^2 and av_x is the average x.   *
 * All operations are done in double precision, since round off error can be *
 * a problem in the initial temp. std_dev calculation for big circuits.      */

 double std_dev;
 
 if (n <= 1) 
    std_dev = 0.;
 else 
    std_dev = (sum_x_squared - n * av_x * av_x) / (double) (n - 1);

 if (std_dev > 0.)        /* Very small variances sometimes round negative */
    std_dev = sqrt (std_dev);
 else
    std_dev = 0.;

 return (std_dev);
}


static void update_rlim (float *rlim, float success_rat) {

 /* Update the range limited to keep acceptance prob. near 0.44.  Use *
  * a floating point rlim to allow gradual transitions at low temps.  */

 float upper_lim;

 *rlim = (*rlim) * (1. - 0.44 + success_rat);
 upper_lim = max(nx,ny);
 *rlim = min(*rlim,upper_lim);
 *rlim = max(*rlim,1.);  
/* *rlim = (float) nx; */
}


static void update_t (float *t, float std_dev, float rlim, 
     float success_rat, struct s_annealing_sched annealing_sched) {

/* Update the temperature according to the annealing schedule selected. */

/*  float fac; */

 if (annealing_sched.type == USER_SCHED) {
    *t = annealing_sched.alpha_t * (*t);
 }

/* Old standard deviation based stuff is below.  This bogs down hopelessly *
 * for big circuits (alu4 and especially bigkey_mod).                      */
/* #define LAMBDA .7  */
/* ------------------------------------ */
/* else if (std_dev == 0.) {  
    *t = 0.;
 }
 else {
    fac = exp (-LAMBDA*(*t)/std_dev);
    fac = max(0.5,fac);   
    *t = (*t) * fac;
 }   */
/* ------------------------------------- */

 else {                             /* AUTO_SCHED */
    if (success_rat > 0.96) {
       *t = (*t) * 0.5; 
    }
    else if (success_rat > 0.8) {
       *t = (*t) * 0.9;
    }
    else if (success_rat > 0.15 || rlim > 1.) {
       *t = (*t) * 0.95;
    }
    else {
       *t = (*t) * 0.8; 
    }
 }
}


static int exit_crit (float t, float cost, struct s_annealing_sched 
         annealing_sched) {

/* Return 1 when the exit criterion is met.                        */

 if (annealing_sched.type == USER_SCHED) {
    if (t < annealing_sched.exit_t) {
       return(1);
    }
    else {
       return(0);
    }
 } 
 
 /* Automatic annealing schedule */

 if (t < 0.005 * cost / num_nets) {
    return(1);
 }
 else {
    return(0);
 }
}


static float starting_t (float *cost_ptr, float *bb_cost_ptr, float *timing_cost_ptr,
    int *pins_on_block, int place_cost_type, float **old_region_occ_x, 
    float **old_region_occ_y, int num_regions, boolean fixed_pins, 
    struct s_annealing_sched annealing_sched, int max_moves, float rlim, 
    enum e_place_algorithm place_algorithm, float timing_tradeoff,
    float inverse_prev_bb_cost, float inverse_prev_timing_cost, float *delay_cost_ptr) {

/* Finds the starting temperature (hot condition).              */

 int i, num_accepted, move_lim;
 double std_dev, av, sum_of_squares;  /* Double important to avoid round off */

 if (annealing_sched.type == USER_SCHED) 
    return (annealing_sched.init_t);  

 move_lim = min (max_moves, num_blocks);

 num_accepted = 0;
 av = 0.;
 sum_of_squares = 0.;

/* Try one move per block.  Set t high so essentially all accepted. */

 for (i=0;i<move_lim;i++) {
    if (try_swap (1.e30, cost_ptr, bb_cost_ptr, timing_cost_ptr, rlim, 
              pins_on_block, place_cost_type,
              old_region_occ_x, old_region_occ_y, num_regions, 
              fixed_pins, place_algorithm, timing_tradeoff,
	      inverse_prev_bb_cost, inverse_prev_timing_cost,
	      delay_cost_ptr) == 1) {
       num_accepted++; 
       av += *cost_ptr;
       sum_of_squares += *cost_ptr * (*cost_ptr);
    }   
 }   

/* Initial Temp = 20*std_dev. */

 if (num_accepted != 0)
    av /= num_accepted;
 else 
    av = 0.;
 
 std_dev = get_std_dev (num_accepted, sum_of_squares, av);
 
#ifdef DEBUG
 if (num_accepted != move_lim) {
    printf("Warning:  Starting t: %d of %d configurations accepted.\n",
        num_accepted, move_lim);
 }
#endif

#ifdef VERBOSE
    printf("std_dev: %g, average cost: %g, starting temp: %g\n",
        std_dev, av, 20. * std_dev);
#endif

 return (20. * std_dev); 
/* return (15.225523	); */
}


static int try_swap (float t, float *cost, float *bb_cost, float *timing_cost, 
		     float rlim, int *pins_on_block, 
		     int place_cost_type, float **old_region_occ_x, 
		     float **old_region_occ_y, int num_regions, boolean fixed_pins,
		     enum e_place_algorithm place_algorithm, float timing_tradeoff,
		     float inverse_prev_bb_cost, float inverse_prev_timing_cost,
		     float *delay_cost) {

/* Picks some block and moves it to another spot.  If this spot is   *
 * occupied, switch the blocks.  Assess the change in cost function  *
 * and accept or reject the move.  If rejected, return 0.  If        *
 * accepted return 1.  Pass back the new value of the cost function. * 
 * rlim is the range limiter.  pins_on_block gives the number of     *
 * pins on each type of block (improves efficiency).                 */

 int b_from, x_to, y_to, x_from, y_from, b_to; 
 int off_from, k, inet, keep_switch, io_num, num_of_pins;
 int num_nets_affected, bb_index;
 float delta_c, bb_delta_c, timing_delta_c, delay_delta_c, newcost;
 static struct s_bb *bb_coord_new = NULL;
 static struct s_bb *bb_edge_new = NULL;
 static int *nets_to_update = NULL, *net_block_moved = NULL;

/* Allocate the local bb_coordinate storage, etc. only once. */

 if (bb_coord_new == NULL) {
    bb_coord_new = (struct s_bb *) my_malloc (2 * pins_per_clb * 
          sizeof (struct s_bb));
    bb_edge_new = (struct s_bb *) my_malloc (2 * pins_per_clb *
          sizeof (struct s_bb));
    nets_to_update = (int *) my_malloc (2 * pins_per_clb * sizeof (int));
    net_block_moved = (int *) my_malloc (2 * pins_per_clb * sizeof (int));
 }

    
 b_from = my_irand(num_blocks - 1);

/* If the pins are fixed we never move them from their initial    *
 * random locations.  The code below could be made more efficient *
 * by using the fact that pins appear first in the block list,    *
 * but this shouldn't cause any significant slowdown and won't be *
 * broken if I ever change the parser so that the pins aren't     *
 * necessarily at the start of the block list.                    */

 if (fixed_pins == TRUE) {
    while (block[b_from].type != CLB) {
       b_from = my_irand(num_blocks - 1);
    }
 }

 x_from = block[b_from].x;
 y_from = block[b_from].y;
 find_to (x_from, y_from, block[b_from].type, rlim, &x_to, &y_to);

/* Make the switch in order to make computing the new bounding *
 * box simpler.  If the cost increase is too high, switch them *
 * back.  (block data structures switched, clbs not switched   *
 * until success of move is determined.)                       */

 if (block[b_from].type == CLB) {
    io_num = -1;            /* Don't need, but stops compiler warning. */
    if (clb[x_to][y_to].occ == 1) {         /* Occupied -- do a switch */
       b_to = clb[x_to][y_to].u.block;
       block[b_from].x = x_to;
       block[b_from].y = y_to;
       block[b_to].x = x_from;
       block[b_to].y = y_from; 
    }    
    else {
       b_to = EMPTY;
       block[b_from].x = x_to;
       block[b_from].y = y_to; 
    }
 }
 else {   /* io block was selected for moving */
    io_num = my_irand(io_rat - 1);
    if (io_num >= clb[x_to][y_to].occ) {  /* Moving to an empty location */
       b_to = EMPTY;
       block[b_from].x = x_to;
       block[b_from].y = y_to;
    }
    else {          /* Swapping two blocks */
       b_to = *(clb[x_to][y_to].u.io_blocks+io_num);
       block[b_to].x = x_from;
       block[b_to].y = y_from;
       block[b_from].x = x_to;
       block[b_from].y = y_to;
    }

 }

/* Now update the cost function.  May have to do major optimizations *
 * here later.                                                       */

/* I'm using negative values of temp_net_cost as a flag, so DO NOT   *
 * use cost functions that can go negative.                          */

 delta_c = 0;                    /* Change in cost due to this swap. */
 bb_delta_c = 0;
 timing_delta_c = 0;

 num_of_pins = pins_on_block[block[b_from].type];    

 num_nets_affected = find_affected_nets (nets_to_update, net_block_moved, 
     b_from, b_to, num_of_pins);

 if (place_cost_type == NONLINEAR_CONG) {
    save_region_occ (old_region_occ_x, old_region_occ_y, num_regions);
 }

 bb_index = 0;               /* Index of new bounding box. */

 for (k=0;k<num_nets_affected;k++) {
    inet = nets_to_update[k];

/* If we swapped two blocks connected to the same net, its bounding box *
 * doesn't change.                                                      */

    if (net_block_moved[k] == FROM_AND_TO) 
       continue;

    if (net[inet].num_pins <= SMALL_NET) {
       get_non_updateable_bb (inet, &bb_coord_new[bb_index]);
    }
    else {
       if (net_block_moved[k] == FROM) 
          update_bb (inet, &bb_coord_new[bb_index], &bb_edge_new[bb_index],
             x_from, y_from, x_to, y_to);      
       else
          update_bb (inet, &bb_coord_new[bb_index], &bb_edge_new[bb_index],
             x_to, y_to, x_from, y_from);      
    }

    if (place_cost_type != NONLINEAR_CONG) {
       temp_net_cost[inet] = get_net_cost (inet, &bb_coord_new[bb_index]);
       bb_delta_c += temp_net_cost[inet] - net_cost[inet];
    }
    else {
           /* Rip up, then replace with new bb. */
       update_region_occ (inet, &bb_coords[inet], -1, num_regions);  
       update_region_occ (inet, &bb_coord_new[bb_index],1, num_regions);
    }

    bb_index++;
 }   

 if (place_cost_type == NONLINEAR_CONG) {
    newcost = nonlinear_cong_cost(num_regions);
    bb_delta_c = newcost - *bb_cost;
 }


 if (place_algorithm == NET_TIMING_DRIVEN_PLACE ||
     place_algorithm == PATH_TIMING_DRIVEN_PLACE) {   
   /*in this case we redefine delta_c as a combination of timing and bb.  *
    *additionally, we normalize all values, therefore delta_c is in       *
    *relation to 1*/
   
   comp_delta_td_cost(b_from, b_to, num_of_pins, &timing_delta_c,	
		      &delay_delta_c);

   delta_c = (1-timing_tradeoff) * bb_delta_c * inverse_prev_bb_cost + 
     timing_tradeoff * timing_delta_c * inverse_prev_timing_cost;
 }
 else {
   delta_c = bb_delta_c;
 }
 

 keep_switch = assess_swap (delta_c, t); 

 /* 1 -> move accepted, 0 -> rejected. */ 

 if (keep_switch) {
    *cost = *cost + delta_c;    
    *bb_cost = *bb_cost + bb_delta_c;


    if (place_algorithm == NET_TIMING_DRIVEN_PLACE ||
	place_algorithm == PATH_TIMING_DRIVEN_PLACE) {      
      /*update the point_to_point_timing_cost and point_to_point_delay_cost 
	values from the temporary values*/
      *timing_cost = *timing_cost + timing_delta_c;
      *delay_cost = *delay_cost + delay_delta_c;

      update_td_cost(b_from, b_to, num_of_pins);
    }

 /* update net cost functions and reset flags. */

    bb_index = 0;

    for (k=0;k<num_nets_affected;k++) {
       inet = nets_to_update[k];

/* If we swapped two blocks connected to the same net, its bounding box *
 * doesn't change.                                                      */

       if (net_block_moved[k] == FROM_AND_TO) {
          temp_net_cost[inet] = -1;  
          continue;
       }