place_and_route.c

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

#include <stdio.h>
#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "place_and_route.h"
#include "place.h"
#include "read_place.h"
#include "route_export.h"
#include "draw.h"
#include "stats.h"
#include "check_route.h"
#include "rr_graph.h"
#include "path_delay.h"
#include "net_delay.h"
#include "timing_place.h"


/******************* Subroutines local to this module ************************/

static int binary_search_place_and_route (struct s_placer_opts
      placer_opts, char *place_file, char *net_file, char *arch_file,
      char *route_file, boolean full_stats, boolean verify_binary_search,
      struct s_annealing_sched annealing_sched, struct s_router_opts
      router_opts, struct s_det_routing_arch det_routing_arch,
      t_segment_inf *segment_inf, t_timing_inf timing_inf, t_subblock_data
      *subblock_data_ptr, t_chan_width_dist chan_width_dist);

static float comp_width (t_chan *chan, float x, float separation);


/************************* Subroutine Definitions ****************************/

void place_and_route (enum e_operation operation, struct s_placer_opts
   placer_opts, char *place_file, char *net_file, char *arch_file,
   char *route_file, boolean full_stats, boolean verify_binary_search,
   struct s_annealing_sched annealing_sched, struct s_router_opts router_opts,
   struct s_det_routing_arch det_routing_arch, t_segment_inf
   *segment_inf, t_timing_inf timing_inf, t_subblock_data
   *subblock_data_ptr, t_chan_width_dist chan_width_dist) {

/* This routine controls the overall placement and routing of a circuit. */

 char msg[BUFSIZE];
 int width_fac;
 boolean success;
 float **net_delay, **net_slack;
 struct s_linked_vptr *net_delay_chunk_list_head;
 t_ivec **clb_opins_used_locally;  /* [0..num_blocks-1][0..num_class-1] */


 if (placer_opts.place_freq == PLACE_NEVER) {
    read_place (place_file, net_file, arch_file, placer_opts, router_opts,
                chan_width_dist, det_routing_arch, segment_inf, timing_inf,
                subblock_data_ptr);
 }

 else if (placer_opts.place_freq == PLACE_ONCE) {
    try_place (placer_opts, annealing_sched, chan_width_dist,
               router_opts, det_routing_arch, segment_inf,
               timing_inf, subblock_data_ptr);
    print_place (place_file, net_file, arch_file);
 }
 
 else if (placer_opts.place_freq == PLACE_ALWAYS &&
          router_opts.fixed_channel_width != NO_FIXED_CHANNEL_WIDTH) {
    placer_opts.place_chan_width = router_opts.fixed_channel_width;
    try_place (placer_opts, annealing_sched, chan_width_dist,
               router_opts, det_routing_arch, segment_inf,
               timing_inf, subblock_data_ptr);
    print_place (place_file, net_file, arch_file);
 }
 
 
 fflush (stdout);
 if (operation == PLACE_ONLY)
    return;
 
/* Binary search over channel width required? */
 
 if (router_opts.fixed_channel_width == NO_FIXED_CHANNEL_WIDTH) {
 
    width_fac = binary_search_place_and_route (placer_opts, place_file,
           net_file, arch_file, route_file, full_stats, verify_binary_search,
           annealing_sched, router_opts, det_routing_arch, segment_inf,
           timing_inf, subblock_data_ptr, chan_width_dist);
 
    return;
 }
 
 else {    /* Only need to route (or try to route) once. */
 
    width_fac = router_opts.fixed_channel_width;
 
   /* Allocate the major routing structures. */
 
    clb_opins_used_locally = alloc_route_structs (*subblock_data_ptr); 
 
    if (timing_inf.timing_analysis_enabled) {
       net_slack = alloc_and_load_timing_graph (timing_inf, *subblock_data_ptr);       
       net_delay = alloc_net_delay (&net_delay_chunk_list_head);
    }
    else {
       net_delay = NULL;    /* Defensive coding. */
       net_slack = NULL;
    }
 
/* Only needed to build timing graph and clb_opins_used_locally */
 
    free_subblock_data (subblock_data_ptr);
 
    success = try_route (width_fac, router_opts, det_routing_arch, segment_inf,
                         timing_inf, net_slack, net_delay, chan_width_dist,
                         clb_opins_used_locally);
 }
 
 
 if (success == FALSE) {
    printf ("Circuit is unrouteable with a channel width factor of %d.\n\n",
             width_fac);
    sprintf (msg,"Routing failed with a channel width factor of %d.  ILLEGAL "
                 "routing shown.", width_fac);
 }
 
 else {
    check_route (router_opts.route_type, det_routing_arch.num_switch,
                clb_opins_used_locally);
    get_serial_num ();
 
    printf("Circuit successfully routed with a channel width factor of %d."
           "\n\n", width_fac);
 
    routing_stats (full_stats, router_opts.route_type,
           det_routing_arch.num_switch, segment_inf,
           det_routing_arch.num_segment, det_routing_arch.R_minW_nmos,
           det_routing_arch.R_minW_pmos, timing_inf.timing_analysis_enabled,
           net_slack, net_delay);
 
    print_route (route_file);

#ifdef PRINT_SINK_DELAYS
    print_sink_delays("Routing_Sink_Delays.echo");
#endif

    sprintf(msg,"Routing succeeded with a channel width factor of %d.",
       width_fac);
 }
 
 init_draw_coords (pins_per_clb);
 update_screen (MAJOR, msg, ROUTING, timing_inf.timing_analysis_enabled);
 
 if (timing_inf.timing_analysis_enabled) {
    free_timing_graph (net_slack);
    free_net_delay (net_delay, &net_delay_chunk_list_head);
 }
 
 free_route_structs (clb_opins_used_locally);
 fflush (stdout);
}
 
 
static int binary_search_place_and_route (struct s_placer_opts
      placer_opts, char *place_file, char *net_file, char *arch_file,
      char *route_file, boolean full_stats, boolean verify_binary_search,
      struct s_annealing_sched annealing_sched, struct s_router_opts
      router_opts, struct s_det_routing_arch det_routing_arch,
      t_segment_inf *segment_inf, t_timing_inf timing_inf, t_subblock_data
      *subblock_data_ptr, t_chan_width_dist chan_width_dist) {
 
/* This routine performs a binary search to find the minimum number of      *
 * tracks per channel required to successfully route a circuit, and returns *
 * that minimum width_fac.                                                  */
 
 struct s_trace **best_routing;  /* Saves the best routing found so far. */
 int current, low, high, final;
 boolean success, prev_success, prev2_success;
 char msg[BUFSIZE];
 float **net_delay, **net_slack;
 struct s_linked_vptr *net_delay_chunk_list_head;

 t_ivec **clb_opins_used_locally, **saved_clb_opins_used_locally; 
                 /* [0..num_blocks-1][0..num_class-1] */
 
 
/* Allocate the major routing structures. */
 
 clb_opins_used_locally = alloc_route_structs (*subblock_data_ptr); 
 best_routing = alloc_saved_routing (clb_opins_used_locally, 
           &saved_clb_opins_used_locally);
 
 if (timing_inf.timing_analysis_enabled) {
    net_slack = alloc_and_load_timing_graph (timing_inf, *subblock_data_ptr);
    net_delay = alloc_net_delay (&net_delay_chunk_list_head);
 }
 else {
    net_delay = NULL;    /* Defensive coding. */
    net_slack = NULL;
 }
 
/* Only needed to build timing graph */
 
 free_subblock_data (subblock_data_ptr);
 
 
 current = 2 * pins_per_clb;     /* Binary search part */
 low = high = -1;
 final = -1;
 
 
 while (final == -1) {
    fflush (stdout);
#ifdef VERBOSE
    printf ("low, high, current %d %d %d\n",low,high,current);
#endif
 
/* Check if the channel width is huge to avoid overflow.  Assume the *
 * circuit is unroutable with the current router options if we're    *
 * going to overflow.                                                */
 
    if (current > MAX_CHANNEL_WIDTH) {
       printf("This circuit appears to be unroutable with the current "
         "router options.\n");
       printf("Aborting routing procedure.\n");
       exit (1);
    }
 
    if (placer_opts.place_freq == PLACE_ALWAYS) {
       placer_opts.place_chan_width = current;
       try_place (placer_opts, annealing_sched, chan_width_dist,
                  router_opts, det_routing_arch, segment_inf,
                  timing_inf, subblock_data_ptr);
    }
    success = try_route (current, router_opts, det_routing_arch, segment_inf,
                         timing_inf, net_slack, net_delay, chan_width_dist,
                         clb_opins_used_locally);
 
    if (success) {
       high = current;
 
/* If we're re-placing constantly, save placement in case it is best. */
 
       if (placer_opts.place_freq == PLACE_ALWAYS) {
          print_place (place_file, net_file, arch_file);
       } 

            /* Save routing in case it is best. */
       save_routing (best_routing, clb_opins_used_locally,
                     saved_clb_opins_used_locally);   

       if ((high - low) <= 1)
          final = high;
 
       if (low != -1) {