rr_graph.c

用于学术研究的FPGA布局布线软件VPR

#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <string.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 "vpr_utils.h"

/* UDSD Modifications by WMF Begin */
/* WMF: I'm using this macro to reverse the order for wire muxes, so opins
 * connect to the highest track first. This way, the leftover imbalance
 * is in reverse to the leftover imbalance due to Fs generation 
 * May 15, I revamped the imbalance solution, so this feature is not useful
 * anymore. */
#define REVERSE_OPIN_ORDER

/* #define ENABLE_DUMP */
#define MUX_SIZE_DIST_DISPLAY

/* mux size statistic data structures */

typedef struct s_mux
{
    int size;
    struct s_mux *next;
}
t_mux;

typedef struct s_mux_size_distribution
{
    int mux_count;
    int max_index;
    int *distr;
    struct s_mux_size_distribution *next;
}
t_mux_size_distribution;

/* UDSD Modifications by WMF End */


/******************* 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_pin_to_track_map(IN enum e_pin_type pin_type,
					       IN int nodes_per_chan,
					       IN int Fc,
					       IN t_type_ptr Type,
					       IN boolean
					       perturb_switch_pattern,
					       IN enum e_directionality
					       directionality);

static struct s_ivec ***alloc_and_load_track_to_pin_lookup(IN int
							   ****pin_to_track_map,
							   IN int Fc,
							   IN int height,
							   IN int num_pins,
							   IN int
							   nodes_per_chan);

static void build_bidir_rr_opins(IN int i,
				 IN int j,
				 INOUT t_rr_node * rr_node,
				 IN t_ivec *** rr_node_indices,
				 IN int *****opin_to_track_map,
				 IN int *Fc_out,
				 IN boolean * rr_edge_done,
				 IN t_seg_details * seg_details,
				 IN struct s_grid_tile **grid);

static void build_unidir_rr_opins(IN int i,
				  IN int j,
				  IN struct s_grid_tile **grid,
				  IN int *Fc_out,
				  IN int nodes_per_chan,
				  IN t_seg_details * seg_details,
				  INOUT int **Fc_xofs,
				  INOUT int **Fc_yofs,
				  INOUT t_rr_node * rr_node,
				  INOUT boolean * rr_edge_done,
				  OUT boolean * Fc_clipped,
				  IN t_ivec *** rr_node_indices);

static void alloc_and_load_rr_graph(IN int num_nodes,
				    IN t_rr_node * rr_node,
				    IN int num_seg_types,
				    IN t_seg_details * seg_details,
				    IN boolean * rr_edge_done,
				    IN struct s_ivec ****track_to_ipin_lookup,
				    IN int *****opin_to_track_map,
				    IN struct s_ivec ***switch_block_conn,
				    IN struct s_grid_tile **grid,
				    IN int nx,
				    IN int ny,
				    IN int Fs,
				    IN short *****sblock_pattern,
				    IN int *Fc_out,
				    IN int **Fc_xofs,
				    IN int **Fc_yofs,
				    IN t_ivec *** rr_node_indices,
				    IN int nodes_per_chan,
				    IN enum e_switch_block_type sb_type,
				    IN int delayless_switch,
				    IN enum e_directionality directionality,
				    IN int wire_to_ipin_switch,
				    OUT boolean * Fc_clipped);

static void load_uniform_switch_pattern(IN t_type_ptr type,
					INOUT int ****tracks_connected_to_pin,
					IN int num_phys_pins,
					IN int *pin_num_ordering,
					IN int *side_ordering,
					IN int *offset_ordering,
					IN int nodes_per_chan,
					IN int Fc,
					IN enum e_directionality
					directionality);

static void load_perturbed_switch_pattern(IN t_type_ptr type,
					  INOUT int
					  ****tracks_connected_to_pin,
					  IN int num_phys_pins,
					  IN int *pin_num_ordering,
					  IN int *side_ordering,
					  IN int *offset_ordering,
					  IN int nodes_per_chan,
					  IN int Fc,
					  IN enum e_directionality
					  directionality);

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

static int track_side(int clb_side);

static boolean *alloc_and_load_perturb_ipins(IN int nodes_per_chan,
					     IN int num_types,
					     IN int *Fc_in,
					     IN int *Fc_out,
					     IN enum e_directionality
					     directionality);


static void print_rr_node(FILE * fp,
			  t_rr_node * rr_node,
			  int inode);

static void build_rr_sinks_sources(IN int i,
				   IN int j,
				   IN t_rr_node * rr_node,
				   IN t_ivec *** rr_node_indices,
				   IN int delayless_switch,
				   IN struct s_grid_tile **grid);

static void build_rr_xchan(IN int i,
			   IN int j,
			   IN struct s_ivec ****track_to_ipin_lookup,
			   IN struct s_ivec ***switch_block_conn,
			   IN int cost_index_offset,
			   IN int nodes_per_chan,
			   IN int *opin_mux_size,
			   IN short *****sblock_pattern,
			   IN int Fs_per_side,
			   IN t_seg_details * seg_details,
			   IN t_ivec *** rr_node_indices,
			   IN boolean * rr_edge_done,
			   INOUT t_rr_node * rr_node,
			   IN int wire_to_ipin_switch,
			   IN enum e_directionality directionality);

static void build_rr_ychan(IN int i,
			   IN int j,
			   IN struct s_ivec ****track_to_ipin_lookup,
			   IN struct s_ivec ***switch_block_conn,
			   IN int cost_index_offset,
			   IN int nodes_per_chan,
			   IN int *opin_mux_size,
			   IN short *****sblock_pattern,
			   IN int Fs_per_side,
			   IN t_seg_details * seg_details,
			   IN t_ivec *** rr_node_indices,
			   IN boolean * rr_edge_done,
			   INOUT t_rr_node * rr_node,
			   IN int wire_to_ipin_switch,
			   IN enum e_directionality directionality);


static void rr_graph_externals(
			       t_timing_inf timing_inf,
			       t_segment_inf * segment_inf,
			       int num_seg_types,
			       int nodes_per_chan,
			       int wire_to_ipin_switch,
			       enum e_base_cost_type base_cost_type);

void alloc_and_load_edges_and_switches(IN t_rr_node * rr_node,
				       IN int inode,
				       IN int num_edges,
				       IN boolean * rr_edge_done,
				       IN t_linked_edge * edge_list_head);

static void alloc_net_rr_terminals(void);

static void alloc_and_load_rr_clb_source(t_ivec *** rr_node_indices);


static void load_uniform_opin_switch_pattern_paired(IN int *Fc_out,
						    IN int num_pins,
						    IN int *pins_in_chan_seg,
						    IN int num_wire_inc_muxes,
						    IN int num_wire_dec_muxes,
						    IN int *wire_inc_muxes,
						    IN int *wire_dec_muxes,
						    INOUT t_rr_node * rr_node,
						    INOUT boolean *
						    rr_edge_done,
						    IN t_seg_details *
						    seg_details,
						    OUT boolean * Fc_clipped);

static int *get_adj_opins(IN int i,
			  IN int j,
			  OUT int *num_pins,
			  IN t_ivec *** rr_node_indices,
			  IN enum e_rr_type chan_type);

void watch_edges(int inode,
		 t_linked_edge * edge_list_head);

static void view_mux_size_distribution(t_ivec *** rr_node_indices,
				       int nodes_per_chan,
				       t_seg_details * seg_details_x,
				       t_seg_details * seg_details_y);

static void print_distribution(FILE * fptr,
			       t_mux_size_distribution * distr_struct);

static void free_type_pin_to_track_map(int***** ipin_to_track_map, t_type_ptr types, int* fc_in);

static void free_type_track_to_ipin_map(struct s_ivec**** track_to_pin_map, t_type_ptr types, int nodes_per_chan);

static t_seg_details *alloc_and_load_global_route_seg_details(IN int
							      nodes_per_chan,
							      IN int
							      global_route_switch);

/* UDSD Modifications by WMF End */

static int *alloc_and_load_actual_fc(IN int num_types,
				     IN t_type_ptr types,
				     IN int nodes_per_chan,
				     IN boolean is_Fc_out,
				     IN enum e_directionality directionality,
				     OUT boolean * Fc_clipped);

/******************* Subroutine definitions *******************************/


void
build_rr_graph(IN t_graph_type graph_type,
	       IN int num_types,
	       IN t_type_ptr types,
	       IN int nx,
	       IN int ny,
	       IN struct s_grid_tile **grid,
	       IN int chan_width,
	       IN struct s_chan_width_dist *chan_capacity_inf,
	       IN enum e_switch_block_type sb_type,
	       IN int Fs,
	       IN int num_seg_types,
		   IN int num_switches,
	       IN t_segment_inf * segment_inf,
	       IN int global_route_switch,
	       IN int delayless_switch,
	       IN t_timing_inf timing_inf,
	       IN int wire_to_ipin_switch,
	       IN enum e_base_cost_type base_cost_type,
	       OUT int *Warnings)
{
    /* Temp structures used to build graph */
    int nodes_per_chan, i, j;
    t_seg_details *seg_details = NULL;
    int *Fc_in = NULL;
    int *Fc_out = NULL;
   
    int *****opin_to_track_map = NULL;	/* [0..num_types-1][0..num_pins-1][0..height][0..3][0..Fc-1] */
    int *****ipin_to_track_map = NULL;	/* [0..num_types-1][0..num_pins-1][0..height][0..3][0..Fc-1] */
    t_ivec ****track_to_ipin_lookup = NULL;	/* [0..num_types-1][0..nodes_per_chan-1][0..height][0..3] */
    t_ivec ***switch_block_conn = NULL;
    short *****unidir_sb_pattern = NULL;
    boolean *rr_edge_done = NULL;
    boolean is_global_graph;
    boolean Fc_clipped;
    boolean use_full_seg_groups;
    boolean *perturb_ipins = NULL;
    enum e_directionality directionality;
    int **Fc_xofs = NULL;	/* [0..ny-1][0..nx-1] */
    int **Fc_yofs = NULL;	/* [0..nx-1][0..ny-1] */

	rr_node_indices = NULL;
	rr_node = NULL;
	num_rr_nodes = 0;

    /* Reset warning flag */
    *Warnings = RR_GRAPH_NO_WARN;

    /* Decode the graph_type */
    is_global_graph = FALSE;
    if(GRAPH_GLOBAL == graph_type)
	{
	    is_global_graph = TRUE;
	}
    use_full_seg_groups = FALSE;
    if(GRAPH_UNIDIR_TILEABLE == graph_type)
	{
	    use_full_seg_groups = TRUE;
	}
    directionality = UNI_DIRECTIONAL;
    if(GRAPH_BIDIR == graph_type)
	{
	    directionality = BI_DIRECTIONAL;
	}
    if(is_global_graph)
	{
	    directionality = BI_DIRECTIONAL;
	}


    /* Global routing uses a single longwire track */
    nodes_per_chan = (is_global_graph ? 1 : chan_width);
    assert(nodes_per_chan > 0);



    /* START SEG_DETAILS */
    if(is_global_graph)
	{
	    /* Sets up a single unit length segment type for global routing. */
	    seg_details =
		alloc_and_load_global_route_seg_details(nodes_per_chan,
							global_route_switch);
	}
    else
	{
	    /* Setup segments including distrubuting tracks and staggering.
	     * If use_full_seg_groups is specified, nodes_per_chan may be 
	     * changed. Warning should be singled to caller if this happens. */
	    seg_details = alloc_and_load_seg_details(&nodes_per_chan,
						     max(nx, ny),
						     num_seg_types,
						     segment_inf,
						     use_full_seg_groups,
						     is_global_graph,
						     directionality);
	    if((is_global_graph ? 1 : chan_width) != nodes_per_chan)
		{
		    *Warnings |= RR_GRAPH_WARN_CHAN_WIDTH_CHANGED;
		}
#ifdef CREATE_ECHO_FILES
	    dump_seg_details(seg_details, nodes_per_chan, "seg_details.txt");
#endif /* CREATE_ECHO_FILES */
	}
    /* END SEG_DETAILS */



    /* START FC */
    /* Determine the actual value of Fc */
    if(is_global_graph)
	{
	    Fc_in = (int *)my_malloc(sizeof(int) * num_types);
	    Fc_out = (int *)my_malloc(sizeof(int) * num_types);
	    for(i = 0; i < num_types; ++i)
		{
		    Fc_in[i] = 1;
		    Fc_out[i] = 1;
		}
	}
    else
	{
	    Fc_clipped = FALSE;
	    Fc_in =
		alloc_and_load_actual_fc(num_types, types, nodes_per_chan,
					 FALSE, directionality, &Fc_clipped);
	    if(Fc_clipped)
		{
		    *Warnings |= RR_GRAPH_WARN_FC_CLIPPED;
		}
	    Fc_clipped = FALSE;
	    Fc_out =
		alloc_and_load_actual_fc(num_types, types, nodes_per_chan,
					 TRUE, directionality, &Fc_clipped);
	    if(Fc_clipped)
		{
		    *Warnings |= RR_GRAPH_WARN_FC_CLIPPED;
		}


#ifdef VERBOSE
	    for(i = 1; i < num_types; ++i)
		{		/* Skip "<EMPTY>" */
		    if(type_descriptors[i].is_Fc_out_full_flex)
			{
			    printf
				("Fc Actual Values: Type = %s, Fc_out = full, Fc_in = %d.\n",
				 type_descriptors[i].name, Fc_input[i]);
			}
		    else
			{
			    printf
				("Fc Actual Values: Type = %s, Fc_out = %d, Fc_in = %d.\n",
				 type_descriptors[i].name, Fc_output[i],
				 Fc_input[i]);
			}
		}
#endif /* VERBOSE */
	}
	
	perturb_ipins =
		alloc_and_load_perturb_ipins(nodes_per_chan, num_types, Fc_in,
					     Fc_out, directionality);
    /* END FC */


    /* Alloc node lookups, count nodes, alloc rr nodes */
    num_rr_nodes = 0;
    rr_node_indices =
	alloc_and_load_rr_node_indices(nodes_per_chan, nx, ny, &num_rr_nodes,
				       seg_details);
    rr_node = (t_rr_node *) my_malloc(sizeof(t_rr_node) * num_rr_nodes);
    memset(rr_node, 0, sizeof(t_rr_node) * num_rr_nodes);
    rr_edge_done = (boolean *) my_malloc(sizeof(boolean) * num_rr_nodes);
    memset(rr_edge_done, 0, sizeof(boolean) * num_rr_nodes);

    /* These are data structures used by the the unidir opin mapping. */
    if(UNI_DIRECTIONAL == directionality)
	{
	    Fc_xofs = (int **)alloc_matrix(0, ny, 0, nx, sizeof(int));
	    Fc_yofs = (int **)alloc_matrix(0, nx, 0, ny, sizeof(int));
	    for(i = 0; i <= nx; ++i)
		{
		    for(j = 0; j <= ny; ++j)
			{
			    Fc_xofs[j][i] = 0;
			    Fc_yofs[i][j] = 0;
			}
		}
	}



    /* START SB LOOKUP */
    /* Alloc and load the switch block lookup */