place.c

fpga设计评估软件

 else  /*don't do an inner recompute */
   inner_recompute_limit = move_lim + 1;
                                        

/* Sometimes I want to run the router with a random placement.  Avoid *
 * using 0 moves to stop division by 0 and 0 length vector problems,  *
 * by setting move_lim to 1 (which is still too small to do any       *
 * significant optimization).                                         */

 if (move_lim <= 0) 
    move_lim = 1;  

 rlim = (float) max (nx, ny);

 first_rlim = rlim; /*used in timing-driven placement for exponent computation*/
 final_rlim = 1;
 inverse_delta_rlim = 1 / (first_rlim - final_rlim);

 t = starting_t (&cost, &bb_cost, &timing_cost, 
                 pins_on_block, placer_opts.place_cost_type,
		 old_region_occ_x, old_region_occ_y, placer_opts.num_regions, 
		 fixed_pins, annealing_sched, move_lim, rlim, 
		 placer_opts.place_algorithm, placer_opts.timing_tradeoff,
		 inverse_prev_bb_cost, inverse_prev_timing_cost, &delay_cost);
 tot_iter = 0;
 moves_since_cost_recompute = 0;
 printf("Initial Placement Cost: %g bb_cost: %g td_cost: %g delay_cost: %g\n\n",
	cost, bb_cost, timing_cost, delay_cost);

#ifndef SPEC
 printf("%11s  %10s %11s  %11s  %11s %11s  %11s %9s %8s  %7s  %7s  %10s  %7s\n", "T", "Cost", "Av. BB Cost", 
	"Av. TD Cost", "Av Tot Del", "P to P Del", "d_max", "Ac Rate", "Std Dev", "R limit", "Exp", 
	"Tot. Moves", "Alpha");
 printf("%11s  %10s %11s  %11s  %11s %11s  %11s %9s %8s  %7s  %7s  %10s  %7s\n", "--------", "----------", 
	"-----------", "-----------", "---------", "----------", "-----", "-------", "-------",  "-------", 
	 "-------","----------", "-----");
#endif

 sprintf(msg,"Initial Placement.  Cost: %g  BB Cost: %g  TD Cost %g  Delay Cost: %g "
	 "\t d_max %g Channel Factor: %d",
   cost, bb_cost, timing_cost, delay_cost, d_max, width_fac);
 update_screen(MAJOR, msg, PLACEMENT, FALSE);

 while (exit_crit(t, cost, annealing_sched) == 0) {

   if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE ||
       placer_opts.place_algorithm == PATH_TIMING_DRIVEN_PLACE) {
     cost = 1;
   }

    av_cost = 0.;
    av_bb_cost = 0.;
    av_delay_cost = 0.;
    av_timing_cost = 0.;
    sum_of_squares = 0.;
    success_sum = 0;

    if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE ||
	placer_opts.place_algorithm == PATH_TIMING_DRIVEN_PLACE) {

      if (outer_crit_iter_count >= placer_opts.recompute_crit_iter ||
	  placer_opts.inner_loop_recompute_divider != 0) {
#ifdef VERBOSE
	printf("Outer Loop Recompute Criticalities\n");
#endif
	place_delay_value = delay_cost / num_connections;
	 
	if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE)
	  load_constant_net_delay (net_delay, place_delay_value);
	/*note, for path_based, the net delay is not updated since it is current,
	 *because it accesses point_to_point_delay array */

	load_timing_graph_net_delays(net_delay);
	d_max = load_net_slack(net_slack, 0);
	load_criticalities( placer_opts, net_slack, d_max, crit_exponent);
	/*recompute costs from scratch, based on new criticalities*/
	comp_td_costs(&timing_cost, &delay_cost); 
	outer_crit_iter_count = 0;
      } 
      outer_crit_iter_count ++;

      /*at each temperature change we update these values to be used     */
      /*for normalizing the tradeoff between timing and wirelength (bb)  */
      inverse_prev_bb_cost = 1/bb_cost;
      inverse_prev_timing_cost = 1/timing_cost;
    }

    inner_crit_iter_count = 1;

    for (inner_iter=0; inner_iter < move_lim; inner_iter++) {
      if (try_swap(t, &cost, &bb_cost, &timing_cost, 
	     rlim, pins_on_block, placer_opts.place_cost_type,
             old_region_occ_x, old_region_occ_y, placer_opts.num_regions,
             fixed_pins, placer_opts.place_algorithm, 
	     placer_opts.timing_tradeoff, inverse_prev_bb_cost, 
	     inverse_prev_timing_cost, &delay_cost) == 1) {
	success_sum++;
	av_cost += cost;
	av_bb_cost += bb_cost;
	av_timing_cost += timing_cost;
	av_delay_cost += delay_cost;
	sum_of_squares += cost * cost;
      }

      if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE ||
	  placer_opts.place_algorithm == PATH_TIMING_DRIVEN_PLACE) {

	if (inner_crit_iter_count >= inner_recompute_limit 
	    && inner_iter != move_lim-1) { /*on last iteration don't recompute*/

	  inner_crit_iter_count = 0;
#ifdef VERBOSE
	  printf("Inner Loop Recompute Criticalities\n");
#endif
	  if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE) {
	    place_delay_value = delay_cost / num_connections;
	    load_constant_net_delay (net_delay, place_delay_value);
	  }
	  
	  load_timing_graph_net_delays(net_delay);
	  d_max = load_net_slack(net_slack, 0);
	  load_criticalities( placer_opts, net_slack, d_max, crit_exponent);
	  comp_td_costs(&timing_cost, &delay_cost); 
	}
	inner_crit_iter_count ++;
      }

#ifdef VERBOSE
      printf("t = %g  cost = %g   bb_cost = %g timing_cost = %g move = %d dmax = %g\n",
	     t, cost, bb_cost, timing_cost, inner_iter, d_max);
      if (fabs(bb_cost - comp_bb_cost(CHECK, placer_opts.place_cost_type, 
				      placer_opts.num_regions)) > bb_cost * ERROR_TOL) 
	exit(1);
#endif 
    }

/* Lines below prevent too much round-off error from accumulating *
 * in the cost over many iterations.  This round-off can lead to  *
 * error checks failing because the cost is different from what   *
 * you get when you recompute from scratch.                       */
 
    moves_since_cost_recompute += move_lim;
    if (moves_since_cost_recompute > MAX_MOVES_BEFORE_RECOMPUTE) {
       new_bb_cost = recompute_bb_cost (placer_opts.place_cost_type, 
                     placer_opts.num_regions);       
       if (fabs(new_bb_cost - bb_cost) > bb_cost * ERROR_TOL) {
          printf("Error in try_place:  new_bb_cost = %g, old bb_cost = %g.\n",
              new_bb_cost, bb_cost);
          exit (1);
       }
       bb_cost = new_bb_cost;

       if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE ||
           placer_opts.place_algorithm == PATH_TIMING_DRIVEN_PLACE) {
	 comp_td_costs(&new_timing_cost, &new_delay_cost);
	 if (fabs(new_timing_cost - timing_cost) > timing_cost * ERROR_TOL) {
	   printf("Error in try_place:  new_timing_cost = %g, old timing_cost = %g.\n",
		  new_timing_cost, timing_cost);
	   exit (1);
	 }
	 if (fabs(new_delay_cost - delay_cost) > delay_cost * ERROR_TOL) {
	   printf("Error in try_place:  new_delay_cost = %g, old delay_cost = %g.\n",
		  new_delay_cost, delay_cost);
	   exit (1);
	 }
	 timing_cost = new_timing_cost;
       }

       if (placer_opts.place_algorithm ==BOUNDING_BOX_PLACE) {
	 cost = new_bb_cost;
       }
       moves_since_cost_recompute = 0;
    }

    tot_iter += move_lim;
    success_rat = ((float) success_sum)/ move_lim;
    if (success_sum == 0) {
       av_cost = cost;
       av_bb_cost = bb_cost;
       av_timing_cost = timing_cost;
       av_delay_cost = delay_cost;
    }
    else {
       av_cost /= success_sum;
       av_bb_cost /= success_sum;
       av_timing_cost /= success_sum;
       av_delay_cost /= success_sum;
    }
    std_dev = get_std_dev (success_sum, sum_of_squares, av_cost);

#ifndef SPEC
    printf("%11.5g  %10.6g %11.6g  %11.6g  %11.6g %11.6g %11.4g %9.4g %8.3g  %7.4g  %7.4g  %10d  ",t, av_cost, 
	   av_bb_cost, av_timing_cost, av_delay_cost, place_delay_value, d_max, success_rat, std_dev, 
	   rlim, crit_exponent,tot_iter);
#endif

    oldt = t;  /* for finding and printing alpha. */
    update_t (&t, std_dev, rlim, success_rat, annealing_sched);

#ifndef SPEC
    printf("%7.4g\n",t/oldt);
#endif

    sprintf(msg,"Cost: %g  BB Cost %g  TD Cost %g  Temperature: %g  d_max: %g",cost, 
	    bb_cost, timing_cost, t, d_max);
    update_screen(MINOR, msg, PLACEMENT, FALSE);
    update_rlim (&rlim, success_rat);

    if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE ||
	placer_opts.place_algorithm == PATH_TIMING_DRIVEN_PLACE) {
      crit_exponent = (1 - (rlim - final_rlim) * inverse_delta_rlim)*
	(placer_opts.td_place_exp_last - placer_opts.td_place_exp_first) + 
	placer_opts.td_place_exp_first;
    }
#ifdef VERBOSE 
 dump_clbs();
#endif
 }

 t = 0;   /* freeze out */
 av_cost = 0.;
 av_bb_cost = 0.;
 av_timing_cost = 0.;
 sum_of_squares = 0.;
 av_delay_cost = 0.;
 success_sum = 0;

 if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE ||
     placer_opts.place_algorithm == PATH_TIMING_DRIVEN_PLACE) {
   /*at each temperature change we update these values to be used     */
   /*for normalizing the tradeoff between timing and wirelength (bb)  */
   if (outer_crit_iter_count >= placer_opts.recompute_crit_iter ||
       placer_opts.inner_loop_recompute_divider != 0) {

#ifdef VERBOSE
     printf("Outer Loop Recompute Criticalities\n");
#endif
     place_delay_value = delay_cost / num_connections;

     if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE)
       load_constant_net_delay (net_delay, place_delay_value);

     load_timing_graph_net_delays(net_delay);
     d_max = load_net_slack(net_slack, 0);
     load_criticalities( placer_opts, net_slack, d_max, crit_exponent); 
     /*recompute criticaliies */
     comp_td_costs(&timing_cost, &delay_cost);  
     outer_crit_iter_count = 0;
   }
   outer_crit_iter_count ++;

   inverse_prev_bb_cost = 1/(bb_cost);
   inverse_prev_timing_cost = 1/(timing_cost);
 }

 inner_crit_iter_count = 1;

 for (inner_iter=0; inner_iter < move_lim; inner_iter++) {
   if (try_swap(t, &cost, &bb_cost, &timing_cost, 
	  rlim, pins_on_block, placer_opts.place_cost_type, 
          old_region_occ_x, old_region_occ_y, placer_opts.num_regions,
          fixed_pins, placer_opts.place_algorithm, placer_opts.timing_tradeoff,
	  inverse_prev_bb_cost, inverse_prev_timing_cost, &delay_cost) == 1) {
     success_sum++;
     av_cost += cost;
     av_bb_cost += bb_cost;
     av_delay_cost += delay_cost;
     av_timing_cost += timing_cost;
     sum_of_squares += cost * cost;

     if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE ||
	 placer_opts.place_algorithm == PATH_TIMING_DRIVEN_PLACE) {

	 if (inner_crit_iter_count >= inner_recompute_limit
	      && inner_iter != move_lim-1) {

	   inner_crit_iter_count = 0;
#ifdef VERBOSE
	   printf("Inner Loop Recompute Criticalities\n");
#endif
	   if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE) {
	     place_delay_value = delay_cost / num_connections;
	     load_constant_net_delay (net_delay, place_delay_value);
	   }
	  
	   load_timing_graph_net_delays(net_delay);
	   d_max = load_net_slack(net_slack, 0);
	   load_criticalities( placer_opts, net_slack, d_max, crit_exponent);
	   comp_td_costs(&timing_cost, &delay_cost); 
	 }
	 inner_crit_iter_count ++;
     }
   }
#ifdef VERBOSE 
   printf("t = %g  cost = %g   move = %d\n",t, cost, tot_iter);
#endif
 }
 tot_iter += move_lim;
 success_rat = ((float) success_sum) / move_lim;
 if (success_sum == 0) {
    av_cost = cost;
    av_bb_cost = bb_cost;
    av_delay_cost = delay_cost;
    av_timing_cost = timing_cost;
 }
 else {
    av_cost /= success_sum;
    av_bb_cost /= success_sum;
    av_delay_cost /= success_sum;
    av_timing_cost /= success_sum;
 }

 std_dev = get_std_dev (success_sum, sum_of_squares, av_cost);


#ifndef SPEC
    printf("%11.5g  %10.6g %11.6g  %11.6g  %11.6g %11.6g %11.4g %9.4g %8.3g  %7.4g  %7.4g  %10d  \n\n",t, av_cost, 
	   av_bb_cost, av_timing_cost, av_delay_cost, place_delay_value, d_max, success_rat, std_dev, 
	   rlim, crit_exponent, tot_iter);

#endif

#ifdef VERBOSE 
 dump_clbs();
#endif
 
 check_place(bb_cost, timing_cost, placer_opts.place_cost_type, placer_opts.num_regions,
	     placer_opts.place_algorithm, delay_cost);

 if (placer_opts.enable_timing_computations &&
     placer_opts.place_algorithm == BOUNDING_BOX_PLACE) {
   /*need this done since the timing data has not been kept up to date*
    *in bounding_box mode */
   for (inet = 0; inet<num_nets; inet++)  
     for (ipin=1; ipin<net[inet].num_pins; ipin++)
       timing_place_crit[inet][ipin] = 0;  /*dummy crit values*/
   comp_td_costs(&timing_cost, &delay_cost); /*computes point_to_point_delay_cost*/
 }

 if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE ||
     placer_opts.place_algorithm == PATH_TIMING_DRIVEN_PLACE ||
     placer_opts.enable_timing_computations) {
   net_delay = point_to_point_delay_cost;/*this makes net_delay up to date with    *
					  *the same values that the placer is using*/
   load_timing_graph_net_delays(net_delay);
   est_crit = load_net_slack(net_slack, 0);
#ifdef PRINT_SINK_DELAYS
   print_sink_delays("Placement_Sink_Delays.echo");
#endif
#ifdef PRINT_NET_SLACKS
   print_net_slack("Placement_Net_Slacks.echo", net_slack);
#endif
#ifdef PRINT_PLACE_CRIT_PATH
   print_critical_path("Placement_Crit_Path.echo");
#endif
   printf("Placement Estimated Crit Path Delay: %g\n\n", est_crit);
 }


 sprintf(msg,"Placement. Cost: %g  bb_cost: %g td_cost: %g Channel Factor: %d d_max: %g",
	 cost, bb_cost, timing_cost, width_fac, d_max);
 printf("Placement. Cost: %g  bb_cost: %g  td_cost: %g  delay_cost: %g.\n",
	cost, bb_cost, timing_cost,delay_cost);
 update_screen(MAJOR, msg, PLACEMENT, FALSE);

#ifdef SPEC
 printf ("Total moves attempted: %d.0\n", tot_iter);
#endif
 
 if (placer_opts.place_algorithm == NET_TIMING_DRIVEN_PLACE ||
     placer_opts.place_algorithm == PATH_TIMING_DRIVEN_PLACE ||
     placer_opts.enable_timing_computations) {

   net_delay = remember_net_delay_original_ptr;

   free_placement_structs (placer_opts.place_cost_type, placer_opts.num_regions,
			   old_region_occ_x, old_region_occ_y, placer_opts); 
   free_lookups_and_criticalities( &net_delay, &net_slack);
 }
}

static int count_connections() {
  /*only count non-global connections*/

  int count, inet;

  count = 0;

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

    if (is_global[inet]) 
      continue;

    count += (net[inet].num_pins - 1);
  }
  return(count);
}

static void compute_net_pin_index_values() {