rr_graph.c

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

#include <stdio.h>
#include <math.h>
#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "rr_graph_util.h"
#include "rr_graph.h"
#include "rr_graph2.h"
#include "rr_graph_sbox.h"
#include "check_rr_graph.h"
#include "rr_graph_timing_params.h"
#include "rr_graph_indexed_data.h"
#include <assert.h>


/******************* Variables local to this module. ***********************/

static struct s_linked_vptr *rr_mem_chunk_list_head = NULL;   
/* Used to free "chunked" memory.  If NULL, no rr_graph exists right now.  */

static int chunk_bytes_avail = 0;
static char *chunk_next_avail_mem = NULL;
/* Status of current chunk being dished out by calls to my_chunk_malloc.   */



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

static int ***alloc_and_load_clb_pin_to_tracks (enum e_pin_type pin_type,
         int nodes_per_chan, int Fc, boolean perturb_switch_pattern); 

static void load_uniform_switch_pattern (int ***tracks_connected_to_pin, 
         int num_phys_pins, int *pin_num_ordering, int *side_ordering, 
         int nodes_per_chan, int Fc, float step_size);

static void load_perturbed_switch_pattern (int ***tracks_connected_to_pin, 
         int num_phys_pins, int *pin_num_ordering, int *side_ordering, 
         int nodes_per_chan, int Fc, float step_size);

static void check_all_tracks_reach_pins (int ***tracks_connected_to_pin,
         int nodes_per_chan, int Fc, enum e_pin_type ipin_or_opin);

static struct s_ivec **alloc_and_load_tracks_to_clb_ipin (int nodes_per_chan,
         int Fc, int ***clb_ipin_to_tracks); 

static int **alloc_and_load_pads_to_tracks (int nodes_per_chan, int Fc_pad); 

static struct s_ivec *alloc_and_load_tracks_to_pads (int **pads_to_tracks, 
         int nodes_per_chan, int Fc_pad); 

static int track_side (int clb_side); 

static void alloc_and_load_rr_graph (int **rr_node_indices, 
       int ***clb_opin_to_tracks, struct s_ivec **tracks_to_clb_ipin,
       int **pads_to_tracks, struct s_ivec *tracks_to_pads, int Fc_output,
       int Fc_input, int Fc_pad, int nodes_per_chan, enum e_route_type 
       route_type, struct s_det_routing_arch det_routing_arch,
       t_seg_details *seg_details_x, t_seg_details *seg_details_y); 

static void build_rr_clb (int **rr_node_indices, int Fc_output, int ***
         clb_opin_to_tracks, int nodes_per_chan, int i, int j,
         int delayless_switch, t_seg_details *seg_details_x, 
         t_seg_details *seg_details_y);

static void build_rr_pads (int **rr_node_indices, int Fc_pad, int 
          **pads_to_tracks, int nodes_per_chan, int i, int j, int 
          delayless_switch, t_seg_details *seg_details_x, t_seg_details 
          *seg_details_y);

static void build_rr_xchan (int **rr_node_indices, enum e_route_type
          route_type, struct s_ivec **tracks_to_clb_ipin, struct s_ivec *
          tracks_to_pads, int i, int j, int nodes_per_chan, enum 
          e_switch_block_type switch_block_type, int wire_to_ipin_switch,
          t_seg_details *seg_details_x, t_seg_details *seg_details_y,
          int cost_index_offset); 

static void build_rr_ychan (int **rr_node_indices, enum e_route_type
          route_type, struct s_ivec **tracks_to_clb_ipin, struct s_ivec *
          tracks_to_pads, int i, int j, int nodes_per_chan, enum
          e_switch_block_type switch_block_type, int wire_to_ipin_switch,
          t_seg_details *seg_details_x, t_seg_details *seg_details_y,
          int cost_index_offset);

void alloc_and_load_edges_and_switches (int inode, int num_edges, 
          t_linked_edge *edge_list_head);

static void alloc_net_rr_terminals (void);

static void alloc_and_load_rr_clb_source (int **rr_node_indices,
          int nodes_per_chan);

static int which_io_block (int iblk); 


/*define a structure to keep track of the internal variables allocated inside */
/*build_rr_graph. This is required so that we can later free them in          */
/*free_rr_graph_internals. If this seems like a hack, it is. The original code*/
/*was able to do everything within one procedure, however since the timing    */
/*driven placer needs to continuously change the mappping of the nets to the  */
/*rr terminals, we need to keep the internal structures active until we finish*/
/*placement -Sandy Nov 10/98*/


struct s_rr_graph_internal_vars {
  int nodes_per_chan;
  int **rr_node_indices;
  int **pads_to_tracks;
  struct s_ivec **tracks_to_clb_ipin;
  struct s_ivec *tracks_to_pads;
  int ***clb_opin_to_tracks;
  int ***clb_ipin_to_tracks;
  t_seg_details *seg_details_x;
  t_seg_details *seg_details_y;
};

static struct s_rr_graph_internal_vars rr_graph_internal_vars;

/******************* Subroutine definitions *******************************/
int **get_rr_node_indices(){

  return (rr_graph_internal_vars.rr_node_indices);
}

int get_nodes_per_chan() {
  return (rr_graph_internal_vars.nodes_per_chan);
}

void build_rr_graph (enum e_route_type route_type, struct s_det_routing_arch
         det_routing_arch, t_segment_inf *segment_inf, t_timing_inf 
         timing_inf, enum e_base_cost_type base_cost_type) {

/* Builds the routing resource graph needed for routing.  Does all the   *
 * necessary allocation and initialization.  If route_type is DETAILED   *
 * then the routing graph built is for detailed routing, otherwise it is *
 * for GLOBAL routing.                                                   */

 int nodes_per_clb, nodes_per_pad, nodes_per_chan;
 float Fc_ratio;
 boolean perturb_ipin_switch_pattern;
 int **rr_node_indices;
 int Fc_output, Fc_input, Fc_pad;
 int **pads_to_tracks;
 struct s_ivec **tracks_to_clb_ipin, *tracks_to_pads;

/* [0..pins_per_clb-1][0..3][0..Fc_output-1].  List of tracks this pin *
 * connects to.  Second index is the side number (see pr.h).  If a pin *
 * is not an output or input, respectively, or doesn't connect to      *
 * anything on this side, the [ipin][iside][0] element is OPEN.        */

 int ***clb_opin_to_tracks, ***clb_ipin_to_tracks;
 t_seg_details *seg_details_x, *seg_details_y;  /* [0 .. nodes_per_chan-1] */


 nodes_per_clb = num_class + pins_per_clb;
 nodes_per_pad = 4 * io_rat;    /* SOURCE, SINK, OPIN, and IPIN */

 if (route_type == GLOBAL) {
    nodes_per_chan = 1;
 }
 else {
    nodes_per_chan = chan_width_x[0];
 }

 seg_details_x = alloc_and_load_seg_details (nodes_per_chan, segment_inf, 
                 det_routing_arch.num_segment, nx);

 seg_details_y = alloc_and_load_seg_details (nodes_per_chan, segment_inf, 
                 det_routing_arch.num_segment, ny);

#ifdef DEBUG
 dump_seg_details (seg_details_x, nodes_per_chan, "x.echo");
 dump_seg_details (seg_details_y, nodes_per_chan, "y.echo");
#endif

/* To set up the routing graph I need to choose an order for the rr_indices. *
 * For each (i,j) slot in the FPGA, the index order is [source+sink]/pins/   *
 * chanx/chany. The dummy source and sink are ordered by class number or pad *
 * number; the pins are ordered by pin number or pad number, and the channel *
 * segments are ordered by track number.  Track 1 is closest to the "owning" *
 * block; i.e. it is towards the left of y-chans and the bottom of x-chans.  *
 *                                                                           *
 * The maximize cache effectiveness, I put all the rr_nodes associated with  *
 * a block together (this includes the "owned" channel segments).  I start   *
 * at (0,0) (empty), go to (1,0), (2,0) ... (0,1) and so on.                 */

/* NB:  Allocates data structures for fast index computations -- more than *
 * just rr_node_indices are allocated by this routine.                     */

 rr_node_indices = alloc_and_load_rr_node_indices (nodes_per_clb, 
         nodes_per_pad, nodes_per_chan, seg_details_x, seg_details_y);

 num_rr_nodes = rr_node_indices[nx+1][ny+1];

 if (det_routing_arch.Fc_type == ABSOLUTE) {
    Fc_output = min (det_routing_arch.Fc_output, nodes_per_chan);
    Fc_input = min (det_routing_arch.Fc_input, nodes_per_chan);
    Fc_pad = min (det_routing_arch.Fc_pad, nodes_per_chan);
 }
 else {    /* FRACTIONAL */
/* Make Fc_output round up so all tracks are driven when                    *
 * Fc = W/(Nequivalent outputs), regardless of W.                           */
    Fc_output = ceil (nodes_per_chan * det_routing_arch.Fc_output - 0.005);
/*  Fc_output = nint (nodes_per_chan * det_routing_arch.Fc_output); */
    Fc_output = max (1, Fc_output);
    Fc_input = nint (nodes_per_chan * det_routing_arch.Fc_input);
    Fc_input = max (1, Fc_input);
    Fc_pad = nint (nodes_per_chan * det_routing_arch.Fc_pad);
    Fc_pad = max (1, Fc_pad);
 }

 alloc_and_load_switch_block_conn (nodes_per_chan, 
        det_routing_arch.switch_block_type);

 clb_opin_to_tracks = alloc_and_load_clb_pin_to_tracks (DRIVER, nodes_per_chan,
        Fc_output, FALSE);

/* Perturb ipin switch pattern if it will line up perfectly with the output  *
 * pin pattern, and there are not so many switches that this would cause 1   *
 * track to connect to the same pin twice.                                   */

 if (Fc_input > Fc_output) 
    Fc_ratio = (float) Fc_input / (float) Fc_output;
 else 
    Fc_ratio = (float) Fc_output / (float) Fc_input;

 if (Fc_input <= nodes_per_chan - 2 && fabs (Fc_ratio - nint (Fc_ratio)) < 
      .5 / (float) nodes_per_chan)
    perturb_ipin_switch_pattern = TRUE;
 else
    perturb_ipin_switch_pattern = FALSE;

 clb_ipin_to_tracks = alloc_and_load_clb_pin_to_tracks (RECEIVER,
        nodes_per_chan, Fc_input, perturb_ipin_switch_pattern);

 tracks_to_clb_ipin = alloc_and_load_tracks_to_clb_ipin (nodes_per_chan,
        Fc_input, clb_ipin_to_tracks);

 pads_to_tracks = alloc_and_load_pads_to_tracks (nodes_per_chan, Fc_pad);
 
 tracks_to_pads = alloc_and_load_tracks_to_pads (pads_to_tracks, 
          nodes_per_chan, Fc_pad);

 rr_edge_done = (boolean *) my_calloc (num_rr_nodes, sizeof (boolean));

 alloc_and_load_rr_graph (rr_node_indices, clb_opin_to_tracks,
       tracks_to_clb_ipin, pads_to_tracks, tracks_to_pads, Fc_output,
       Fc_input, Fc_pad, nodes_per_chan, route_type, det_routing_arch, 
       seg_details_x, seg_details_y);

 add_rr_graph_C_from_switches (timing_inf.C_ipin_cblock); 

 alloc_and_load_rr_indexed_data (segment_inf, det_routing_arch.num_segment,
        rr_node_indices, nodes_per_chan, det_routing_arch.wire_to_ipin_switch,
        base_cost_type);
        
/* dump_rr_graph ("rr_graph.echo");  */
 check_rr_graph (route_type, det_routing_arch.num_switch);

 rr_graph_internal_vars.clb_opin_to_tracks = clb_opin_to_tracks;
 rr_graph_internal_vars.clb_ipin_to_tracks = clb_ipin_to_tracks;
 rr_graph_internal_vars.tracks_to_clb_ipin = tracks_to_clb_ipin;
 rr_graph_internal_vars.tracks_to_pads = tracks_to_pads;
 rr_graph_internal_vars.pads_to_tracks = pads_to_tracks;
 rr_graph_internal_vars.nodes_per_chan = nodes_per_chan;
 rr_graph_internal_vars.seg_details_x = seg_details_x;
 rr_graph_internal_vars.seg_details_y = seg_details_y;
 rr_graph_internal_vars.rr_node_indices = rr_node_indices;
}


void free_rr_graph_internals (enum e_route_type route_type, struct s_det_routing_arch
         det_routing_arch, t_segment_inf *segment_inf, t_timing_inf 
         timing_inf, enum e_base_cost_type base_cost_type)
{
  /* frees the variables that are internal to build_rr_graph.        */
  /* this procedure should typically be called immediatley after     */
  /* build_rr_graph, except for in the timing driven placer, which   */
  /* is constantly modifying some of the rr_graph structures         */

 int nodes_per_chan;
 int **rr_node_indices;
 int **pads_to_tracks;
 struct s_ivec **tracks_to_clb_ipin, *tracks_to_pads;
 int ***clb_opin_to_tracks, ***clb_ipin_to_tracks;
 t_seg_details *seg_details_x, *seg_details_y;  /* [0 .. nodes_per_chan-1] */


 clb_opin_to_tracks = rr_graph_internal_vars.clb_opin_to_tracks;
 clb_ipin_to_tracks = rr_graph_internal_vars.clb_ipin_to_tracks;
 tracks_to_clb_ipin = rr_graph_internal_vars.tracks_to_clb_ipin;
 tracks_to_pads = rr_graph_internal_vars.tracks_to_pads;
 pads_to_tracks = rr_graph_internal_vars.pads_to_tracks;
 nodes_per_chan = rr_graph_internal_vars.nodes_per_chan;
 seg_details_x = rr_graph_internal_vars.seg_details_x;
 seg_details_y = rr_graph_internal_vars.seg_details_y;
 rr_node_indices = rr_graph_internal_vars.rr_node_indices;


 free (rr_edge_done);
 free_matrix3 (clb_opin_to_tracks, 0, pins_per_clb-1, 0, 3, 0, sizeof(int));
 free_matrix3 (clb_ipin_to_tracks, 0, pins_per_clb-1, 0, 3, 0, sizeof(int));
 free_ivec_matrix (tracks_to_clb_ipin, 0, nodes_per_chan-1, 0, 3);
 free_ivec_vector (tracks_to_pads, 0, nodes_per_chan-1);
 free_matrix (pads_to_tracks, 0, io_rat-1, 0, sizeof(int));
 free_switch_block_conn (nodes_per_chan);
 free_edge_list_hard (&free_edge_list_head);
 free_seg_details (seg_details_x, nodes_per_chan);
 free_seg_details (seg_details_y, nodes_per_chan);

 free_rr_node_indices (rr_node_indices);
}


static void alloc_and_load_rr_graph (int **rr_node_indices, 
       int ***clb_opin_to_tracks, struct s_ivec **tracks_to_clb_ipin,
       int **pads_to_tracks, struct s_ivec *tracks_to_pads, int Fc_output,
       int Fc_input, int Fc_pad, int nodes_per_chan, enum e_route_type 
       route_type, struct s_det_routing_arch det_routing_arch, 
       t_seg_details *seg_details_x, t_seg_details *seg_details_y) {

/* Does the actual work of allocating the rr_graph and filling all the *
 * appropriate values.  Everything up to this was just a prelude!      */

 int i, j;
 enum e_switch_block_type switch_block_type;
 int delayless_switch, wire_to_ipin_switch, num_segment;


/* Allocate storage for the graph nodes.  Storage for the edges will be *
 * allocated as I fill in the graph.                                    */

 if (rr_mem_chunk_list_head != NULL) {
    printf("Error in alloc_and_load_rr_graph:  rr_mem_chunk_list_head = %p.\n",
            rr_mem_chunk_list_head);
    printf("Expected NULL.  It appears an old rr_graph has not been freed.\n");
    exit (1);
 }

 alloc_net_rr_terminals ();
 load_net_rr_terminals (rr_node_indices, nodes_per_chan);

 alloc_and_load_rr_clb_source (rr_node_indices, nodes_per_chan);

 rr_node = (t_rr_node *) my_malloc (num_rr_nodes * sizeof (t_rr_node));
 
 switch_block_type = det_routing_arch.switch_block_type;
 delayless_switch = det_routing_arch.delayless_switch;
 wire_to_ipin_switch = det_routing_arch.wire_to_ipin_switch;
 num_segment = det_routing_arch.num_segment;

 for (i=0;i<=nx+1;i++) {
    for (j=0;j<=ny+1;j++) {

       if (clb[i][j].type == CLB) {
          build_rr_clb (rr_node_indices, Fc_output, clb_opin_to_tracks, 
                 nodes_per_chan, i, j, delayless_switch, seg_details_x, 
                 seg_details_y);
          build_rr_xchan (rr_node_indices, route_type, tracks_to_clb_ipin, 
                 tracks_to_pads, i, j, nodes_per_chan, switch_block_type, 
                 wire_to_ipin_switch, seg_details_x, seg_details_y,
                 CHANX_COST_INDEX_START);
          build_rr_ychan (rr_node_indices, route_type, tracks_to_clb_ipin, 
                 tracks_to_pads, i, j, nodes_per_chan, switch_block_type, 
                 wire_to_ipin_switch, seg_details_x, seg_details_y,
                 CHANX_COST_INDEX_START + num_segment);
       }

       else if (clb[i][j].type == IO) {
          build_rr_pads (rr_node_indices, Fc_pad, pads_to_tracks,
                  nodes_per_chan, i, j, delayless_switch, seg_details_x, 
                  seg_details_y);

          if (j == 0)  /* Bottom-most channel. */
             build_rr_xchan (rr_node_indices, route_type, tracks_to_clb_ipin, 
                    tracks_to_pads, i, j, nodes_per_chan, switch_block_type, 
                    wire_to_ipin_switch, seg_details_x, seg_details_y,
                    CHANX_COST_INDEX_START);

          if (i == 0)  /* Left-most channel.   */
             build_rr_ychan (rr_node_indices, route_type, tracks_to_clb_ipin,
                 tracks_to_pads, i, j, nodes_per_chan, switch_block_type, 
                 wire_to_ipin_switch, seg_details_x, seg_details_y, 
                 CHANX_COST_INDEX_START + num_segment);
       }

       else if (clb[i][j].type != ILLEGAL) {
          printf ("Error in alloc_and_load_rr_graph.\n"
                  "Block at (%d, %d) has unknown type (%d).\n", i, j, 
                   clb[i][j].type);
          exit (1);
       }

    }
 }

}


void free_rr_graph (void) {

/* Frees all the routing graph data structures, if they have been       *
 * allocated.  I use rr_mem_chunk_list_head as a flag to indicate       *
 * whether or not the graph has been allocated -- if it is not NULL,    *
 * a routing graph exists and can be freed.  Hence, you can call this   *
 * routine even if you're not sure of whether a rr_graph exists or not. */