place.c

fpga设计评估软件

       bb_coords[inet] = bb_coord_new[bb_index];
       if (net[inet].num_pins > SMALL_NET) 
          bb_num_on_edges[inet] = bb_edge_new[bb_index];

       bb_index++;

       net_cost[inet] = temp_net_cost[inet];
       temp_net_cost[inet] = -1;  
    }

 /* Update Clb data structures since we kept the move. */

    if (block[b_from].type == CLB) {
       if (b_to != EMPTY) {
          clb[x_from][y_from].u.block = b_to; 
          clb[x_to][y_to].u.block = b_from;
       }
       else {
          clb[x_to][y_to].u.block = b_from;   
          clb[x_to][y_to].occ = 1;
          clb[x_from][y_from].occ = 0; 
       }
    }

    else {     /* io block was selected for moving */

     /* Get the "sub_block" number of the b_from block. */

       for (off_from=0;;off_from++) {
          if (clb[x_from][y_from].u.io_blocks[off_from] == b_from) break;
       }

       if (b_to != EMPTY) {   /* Swapped two blocks. */
          clb[x_to][y_to].u.io_blocks[io_num] = b_from;
          clb[x_from][y_from].u.io_blocks[off_from] = b_to;
       }
       else {                 /* Moved to an empty location */
          clb[x_to][y_to].u.io_blocks[clb[x_to][y_to].occ] = b_from;  
          clb[x_to][y_to].occ++;   
          for  (k=off_from;k<clb[x_from][y_from].occ-1;k++) { /* prevent gap  */
             clb[x_from][y_from].u.io_blocks[k] =          /* in io_blocks */
                clb[x_from][y_from].u.io_blocks[k+1];
          }
          clb[x_from][y_from].occ--;
       }
    }  
 }  

 else {    /* Move was rejected.  */

/* Reset the net cost function flags first. */
    for (k=0;k<num_nets_affected;k++) {
       inet = nets_to_update[k];
       temp_net_cost[inet] = -1;
    }
    
 /* Restore the block data structures to their state before the move. */
    block[b_from].x = x_from;
    block[b_from].y = y_from;
    if (b_to != EMPTY) {
       block[b_to].x = x_to;
       block[b_to].y = y_to;
    }

/* Restore the region occupancies to their state before the move. */
    if (place_cost_type == NONLINEAR_CONG) {
       restore_region_occ (old_region_occ_x, old_region_occ_y, num_regions);
    }

 }
 
 return(keep_switch);
}


static void save_region_occ (float **old_region_occ_x, 
      float **old_region_occ_y, int num_regions) {

/* Saves the old occupancies of the placement subregions in case the  *
 * current move is not accepted.  Used only for NONLINEAR_CONG.       */

 int i, j;

 for (i=0;i<num_regions;i++) { 
    for (j=0;j<num_regions;j++) { 
       old_region_occ_x[i][j] = place_region_x[i][j].occupancy; 
       old_region_occ_y[i][j] = place_region_y[i][j].occupancy; 
    } 
 } 
}


static void restore_region_occ (float **old_region_occ_x, 
       float **old_region_occ_y, int num_regions) {

/* Restores the old occupancies of the placement subregions when the  *
 * current move is not accepted.  Used only for NONLINEAR_CONG.       */

 int i, j;
 
 for (i=0;i<num_regions;i++) {
    for (j=0;j<num_regions;j++) {
       place_region_x[i][j].occupancy = old_region_occ_x[i][j];
       place_region_y[i][j].occupancy = old_region_occ_y[i][j];
    }
 }
}


static int find_affected_nets (int *nets_to_update, int *net_block_moved,
    int b_from, int b_to, int num_of_pins) {

/* Puts a list of all the nets connected to b_from and b_to into          *
 * nets_to_update.  Returns the number of affected nets.  Net_block_moved *
 * is either FROM, TO or FROM_AND_TO -- the block connected to this net   *
 * that has moved.                                                        */

 int k, inet, affected_index, count;

 affected_index = 0;

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

    if (is_global[inet]) 
       continue;

/* This is here in case the same block connects to a net twice. */

    if (temp_net_cost[inet] > 0.)  
       continue;

    nets_to_update[affected_index] = inet;
    net_block_moved[affected_index] = FROM;
    affected_index++;
    temp_net_cost[inet] = 1.;         /* Flag to say we've marked this net. */
 }

 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;

       if (temp_net_cost[inet] > 0.) {         /* Net already marked. */
          for (count=0;count<affected_index;count++) {
             if (nets_to_update[count] == inet) {
                if (net_block_moved[count] == FROM) 
                   net_block_moved[count] = FROM_AND_TO;
                break;
             }
          }

#ifdef DEBUG
          if (count > affected_index) {
             printf("Error in find_affected_nets -- count = %d,"
              " affected index = %d.\n", count, affected_index);
             exit (1);
          }
#endif
       }
                 
       else {           /* Net not marked yet. */

          nets_to_update[affected_index] = inet;
          net_block_moved[affected_index] = TO;
          affected_index++;
          temp_net_cost[inet] = 1.;    /* Flag means we've  marked net. */
       }
    }
 }

 return (affected_index);
}


static void find_to (int x_from, int y_from, int type, float rlim, 
    int *x_to, int *y_to) {

 /* Returns the point to which I want to swap, properly range limited. *
  * rlim must always be between 1 and nx (inclusive) for this routine  *
  * to work.                                                           */

 int x_rel, y_rel, iside, iplace, rlx, rly;

 rlx = min(nx,rlim);   /* Only needed when nx < ny. */
 rly = min (ny,rlim);  /* Added rly for aspect_ratio != 1 case. */

#ifdef DEBUG
 if (rlx < 1 || rlx > nx) {
    printf("Error in find_to: rlx = %d\n",rlx);
    exit(1);
 }
#endif

 do {              /* Until (x_to, y_to) different from (x_from, y_from) */
    if (type == CLB) {
       x_rel = my_irand (2*rlx);    
       y_rel = my_irand (2*rly);
       *x_to = x_from - rlx + x_rel;
       *y_to = y_from - rly + y_rel;
       if (*x_to > nx) *x_to = *x_to - nx;    /* better spectral props. */
       if (*x_to < 1) *x_to = *x_to + nx;     /* than simple min, max   */
       if (*y_to > ny) *y_to = *y_to - ny;    /* clipping.              */
       if (*y_to < 1) *y_to = *y_to + ny;
    }
    else {                 /* io_block to be moved. */
       if (rlx >= nx) {
          iside = my_irand(3);
/*                              *
 *       +-----1----+           *
 *       |          |           *
 *       |          |           *
 *       0          2           *
 *       |          |           *
 *       |          |           *
 *       +-----3----+           *
 *                              */
          switch (iside) {
          case 0:
             iplace = my_irand (ny-1) + 1;
             *x_to = 0;
             *y_to = iplace;
             break;
          case 1:
             iplace = my_irand (nx-1) + 1;
             *x_to = iplace;
             *y_to = ny+1;
             break;
          case 2:
             iplace = my_irand (ny-1) + 1;
             *x_to = nx+1;
             *y_to = iplace;
             break;
          case 3:
             iplace = my_irand (nx-1) + 1;
             *x_to = iplace;
             *y_to = 0;
             break;
          default:
             printf("Error in find_to.  Unexpected io swap location.\n");
             exit (1);
          }
       }
       else {   /* rlx is less than whole chip */
          if (x_from == 0) {
             iplace = my_irand (2*rly);
             *y_to = y_from - rly + iplace;
             *x_to = x_from;
             if (*y_to > ny) {
                *y_to = ny + 1;
                *x_to = my_irand (rlx - 1) + 1;
             }
             else if (*y_to < 1) {
                *y_to = 0;
                *x_to = my_irand (rlx - 1) + 1;
             }
          }
          else if (x_from == nx+1) {
             iplace = my_irand (2*rly);
             *y_to = y_from - rly + iplace;
             *x_to = x_from;
             if (*y_to > ny) {
                *y_to = ny + 1;
                *x_to = nx - my_irand (rlx - 1); 
             }
             else if (*y_to < 1) {
                *y_to = 0;
                *x_to = nx - my_irand (rlx - 1);
             }
          }
          else if (y_from == 0) {
             iplace = my_irand (2*rlx);
             *x_to = x_from - rlx + iplace;
             *y_to = y_from;
             if (*x_to > nx) {
                *x_to = nx + 1;
                *y_to = my_irand (rly - 1) + 1;
             }
             else if (*x_to < 1) {
                *x_to = 0;
                *y_to = my_irand (rly -1) + 1;
             }
          }
          else {  /* *y_from == ny + 1 */
             iplace = my_irand (2*rlx);
             *x_to = x_from - rlx + iplace;
             *y_to = y_from;
             if (*x_to > nx) {
                *x_to = nx + 1;
                *y_to = ny - my_irand (rly - 1);
             }
             else if (*x_to < 1) {
                *x_to = 0;
                *y_to = ny - my_irand (rly - 1);
             }
          }
       }    /* End rlx if */
    }    /* end type if */
 } while ((x_from == *x_to) && (y_from == *y_to));

#ifdef DEBUG
   if (*x_to < 0 || *x_to > nx+1 || *y_to < 0 || *y_to > ny+1) {
      printf("Error in routine find_to:  (x_to,y_to) = (%d,%d)\n",
            *x_to, *y_to);
      exit(1);
   }

   if (type == CLB) {
     if (clb[*x_to][*y_to].type != CLB) {
        printf("Error: Moving CLB to illegal type block at (%d,%d)\n",
          *x_to,*y_to);
        exit(1);
     }
   }
   else {
     if (clb[*x_to][*y_to].type != IO) {
        printf("Error: Moving IO block to illegal type location at "
              "(%d,%d)\n", *x_to, *y_to);
        exit(1);
     }
   }
#endif

/* printf("(%d,%d) moved to (%d,%d)\n",x_from,y_from,*x_to,*y_to); */
}


static int assess_swap (float delta_c, float t) {

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

 int accept;
 float prob_fac, fnum;

 if (delta_c <= 0) {

#ifdef SPEC          /* Reduce variation in final solution due to round off */
    fnum = my_frand();
#endif

    accept = 1;
    return(accept);
 }

 if (t == 0.) 
    return(0);

 fnum = my_frand();
 prob_fac = exp(-delta_c/t);
 if (prob_fac > fnum) {
    accept = 1;
 }
 else {
    accept = 0;
 }
 return(accept);
}


static float recompute_bb_cost (int place_cost_type, int num_regions) {

/* Recomputes the cost to eliminate roundoff that may have accrued.  *
 * This routine does as little work as possible to compute this new  *
 * cost.                                                             */

 int i, j, inet;
 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 (inet=0;inet<num_nets;inet++) {     /* for each net ... */
 
    if (is_global[inet] == FALSE) {    /* Do only if not global. */

       /* Bounding boxes don't have to be recomputed; they're correct. */ 
  
       if (place_cost_type != NONLINEAR_CONG) {
          cost += net_cost[inet];
       }