timing_place_lookup.c

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

#include <stdio.h>
#include <math.h>
#include <string.h>
#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "route_common.h"
#include "place_and_route.h"
#include "route_tree_timing.h"
#include "route_timing.h"
#include "timing_place_lookup.h"
#include "rr_graph.h"
#include "mst.h"
#include "route_export.h"
#include <assert.h>


/*this file contains routines that generate the array containing*/
/*the delays between blocks, this is used in the timing driven  */
/*placement routines */

/*To compute delay between blocks we place temporary blocks at */
/*different locations in the FPGA and route nets  between      */
/*the blocks.  From this procedure we generate a lookup table  */
/*which tells us the delay between different locations in      */
/*the FPGA */

/*Note: these routines assume that there is a uniform and even */
/*distribution of the different wire segments. If this is not  */
/*the case, then this lookup table will be off */

/*Note: This code removes all heterogeneous types and creates an
artificial 1x1 tile.  A good lookup for heterogeniety 
requires more research */

#define NET_COUNT 1		/*we only use one net in these routines,   */
		    /*it is repeatedly routed and ripped up    */
		    /*to compute delays between different      */
		    /*locations, this value should not change  */
#define NET_USED 0		/*we use net at location zero of the net    */
		   /*structure                                 */
#define NET_USED_SOURCE_BLOCK 0	/*net.block[0] is source block */
#define NET_USED_SINK_BLOCK 1	/*net.block[1] is sink block */
#define SOURCE_BLOCK 0		/*block[0] is source */
#define SINK_BLOCK 1		/*block[1] is sink */

#define BLOCK_COUNT 2		/*use 2 blocks to compute delay between  */
		      /*the various FPGA locations             */
		      /*do not change this number unless you   */
		      /*really know what you are doing, it is  */
		      /*assumed that the net only connects to  */
		      /*two blocks */

#define NUM_TYPES_USED 3	/* number of types used in look up */

#define DEBUG_TIMING_PLACE_LOOKUP	/*initialize arrays to known state */

#define DUMPFILE "lookup_dump.echo"
/* #define PRINT_ARRAYS *//*only used during debugging, calls routine to  */
		     /*print out the various lookup arrays           */

/***variables that are exported to other modules***/

/*the delta arrays are used to contain the best case routing delay */
/*between different locations on the FPGA. */


float **delta_io_to_fb;
float **delta_fb_to_fb;
float **delta_fb_to_io;
float **delta_io_to_io;


/*** Other Global Arrays ******/
/* I could have allocated these as local variables, and passed them all */
/* around, but was too lazy, since this is a small file, it should not  */
/* be a big problem */

static float **net_delay;
static float **net_slack;
static float *pin_criticality;
static int *sink_order;
static t_rt_node **rt_node_of_sink;
static t_type_ptr IO_TYPE_BACKUP;
static t_type_ptr EMPTY_TYPE_BACKUP;
static t_type_ptr FILL_TYPE_BACKUP;
static t_type_descriptor dummy_type_descriptors[NUM_TYPES_USED];
static t_type_descriptor *type_descriptors_backup;
static struct s_grid_tile **grid_backup;
static int num_types_backup;

static t_ivec **clb_opins_used_locally;

#ifdef PRINT_ARRAYS
static FILE *lookup_dump;	/* If debugging mode is on, print out to
				 * the file defined in DUMPFILE */
#endif /* PRINT_ARRAYS */

/*** Function Prototypes *****/

static void alloc_net(void);

static void alloc_block(void);

static void load_simplified_device(void);
static void restore_original_device(void);

static void alloc_and_assign_internal_structures(struct s_net **original_net,
						 struct s_block
						 **original_block,
						 int *original_num_nets,
						 int *original_num_blocks);

static void free_and_reset_internal_structures(struct s_net *original_net,
					       struct s_block *original_block,
					       int original_num_nets,
					       int original_num_blocks);

static void setup_chan_width(struct s_router_opts router_opts,
			     t_chan_width_dist chan_width_dist);

static void alloc_routing_structs(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);

static void free_routing_structs(struct s_router_opts router_opts,
				 struct s_det_routing_arch det_routing_arch,
				 t_segment_inf * segment_inf,
				 t_timing_inf timing_inf);

static void assign_locations(t_type_ptr source_type,
			     int source_x_loc,
			     int source_y_loc,
			     int source_z_loc,
			     t_type_ptr sink_type,
			     int sink_x_loc,
			     int sink_y_loc,
			     int sink_z_loc);

static float assign_blocks_and_route_net(t_type_ptr source_type,
					 int source_x_loc,
					 int source_y_loc,
					 t_type_ptr sink_type,
					 int sink_x_loc,
					 int sink_y_loc,
					 struct s_router_opts router_opts,
					 struct s_det_routing_arch
					 det_routing_arch,
					 t_segment_inf * segment_inf,
					 t_timing_inf timing_inf);

static void alloc_delta_arrays(void);

static void free_delta_arrays(void);

static void generic_compute_matrix(float ***matrix_ptr,
				   t_type_ptr source_type,
				   t_type_ptr sink_type,
				   int source_x,
				   int source_y,
				   int start_x,
				   int end_x,
				   int start_y,
				   int end_y,
				   struct s_router_opts router_opts,
				   struct s_det_routing_arch det_routing_arch,
				   t_segment_inf * segment_inf,
				   t_timing_inf timing_inf);

static void compute_delta_fb_to_fb(struct s_router_opts router_opts,
				   struct s_det_routing_arch det_routing_arch,
				   t_segment_inf * segment_inf,
				   t_timing_inf timing_inf,
				   int longest_length);

static void compute_delta_io_to_fb(struct s_router_opts router_opts,
				   struct s_det_routing_arch det_routing_arch,
				   t_segment_inf * segment_inf,
				   t_timing_inf timing_inf);

static void compute_delta_fb_to_io(struct s_router_opts router_opts,
				   struct s_det_routing_arch det_routing_arch,
				   t_segment_inf * segment_inf,
				   t_timing_inf timing_inf);

static void compute_delta_io_to_io(struct s_router_opts router_opts,
				   struct s_det_routing_arch det_routing_arch,
				   t_segment_inf * segment_inf,
				   t_timing_inf timing_inf);

static void compute_delta_arrays(struct s_router_opts router_opts,
				 struct s_det_routing_arch det_routing_arch,
				 t_segment_inf * segment_inf,
				 t_timing_inf timing_inf,
				 int longest_length);

static int get_first_pin(enum e_pin_type pintype,
			 t_type_ptr type);

static int get_longest_segment_length(struct s_det_routing_arch
				      det_routing_arch,
				      t_segment_inf * segment_inf);
static void reset_placement(void);

#ifdef PRINT_ARRAYS
static void print_array(float **array_to_print,
			int x1,
			int x2,
			int y1,
			int y2);
#endif
/**************************************/
static int
get_first_pin(enum e_pin_type pintype,
	      t_type_ptr type)
{

    /*this code assumes logical equivilance between all driving pins */
    /*global pins are not hooked up to the temporary net */

    int i, currpin;

    currpin = 0;
    for(i = 0; i < type->num_class; i++)
	{
	    if(type->class_inf[i].type == pintype
	       && !type->is_global_pin[currpin])
		return (type->class_inf[i].pinlist[0]);
	    else
		currpin += type->class_inf[i].num_pins;
	}
    assert(0);
    exit(0);			/*should never hit this line */
}

/**************************************/
static int
get_longest_segment_length(struct s_det_routing_arch det_routing_arch,
			   t_segment_inf * segment_inf)
{

    int i, length;

    length = 0;
    for(i = 0; i < det_routing_arch.num_segment; i++)
	{
	    if(segment_inf[i].length > length)
		length = segment_inf[i].length;
	}
    return (length);
}

/**************************************/
static void
alloc_net(void)
{

    int i, len;

    net = (struct s_net *)my_malloc(num_nets * sizeof(struct s_net));
    for(i = 0; i < NET_COUNT; i++)
	{
	    /* FIXME: We *really* shouldn't be allocating write-once copies */
	    len = strlen("TEMP_NET");
	    net[i].name = (char *)my_malloc((len + 1) * sizeof(char));
	    net[i].is_global = FALSE;
	    strcpy(net[NET_USED].name, "TEMP_NET");

	    net[i].num_sinks = (BLOCK_COUNT - 1);
	    net[i].node_block = (int *)my_malloc(BLOCK_COUNT * sizeof(int));
	    net[i].node_block[NET_USED_SOURCE_BLOCK] = NET_USED_SOURCE_BLOCK;	/*driving block */
	    net[i].node_block[NET_USED_SINK_BLOCK] = NET_USED_SINK_BLOCK;	/*target block */

	    net[i].node_block_pin =
		(int *)my_malloc(BLOCK_COUNT * sizeof(int));
	    /*the values for this are allocated in assign_blocks_and_route_net */

	}
}

/**************************************/
static void
alloc_block(void)
{

    /*allocates block structure, and assigns values to known parameters */
    /*type and x,y fields are left undefined at this stage since they  */
    /*are not known until we start moving blocks through the clb array */

    int ix_b, ix_p, len, i;
    int max_pins;

    max_pins = 0;
    for(i = 0; i < NUM_TYPES_USED; i++)
	{
	    max_pins = max(max_pins, type_descriptors[i].num_pins);
	}

    block = (struct s_block *)my_malloc(num_blocks * sizeof(struct s_block));

    for(ix_b = 0; ix_b < BLOCK_COUNT; ix_b++)
	{
	    len = strlen("TEMP_BLOCK");
	    block[ix_b].name = (char *)my_malloc((len + 1) * sizeof(char));
	    strcpy(block[ix_b].name, "TEMP_BLOCK");

	    block[ix_b].nets = (int *)my_malloc(max_pins * sizeof(int));
	    block[ix_b].nets[0] = 0;
	    for(ix_p = 1; ix_p < max_pins; ix_p++)
		block[ix_b].nets[ix_p] = OPEN;
	}
}

/**************************************/
static void
load_simplified_device(void)
{
    int i, j;

    /* Backup original globals */
    EMPTY_TYPE_BACKUP = EMPTY_TYPE;
    IO_TYPE_BACKUP = IO_TYPE;
    FILL_TYPE_BACKUP = FILL_TYPE;
    type_descriptors_backup = type_descriptors;
    num_types_backup = num_types;
    num_types = NUM_TYPES_USED;

    /* Fill in homogeneous core type info */
    dummy_type_descriptors[0] = *EMPTY_TYPE;
    dummy_type_descriptors[0].index = 0;
    dummy_type_descriptors[1] = *IO_TYPE;
    dummy_type_descriptors[1].index = 1;
    dummy_type_descriptors[2] = *FILL_TYPE;
    dummy_type_descriptors[2].index = 2;
    type_descriptors = dummy_type_descriptors;
    EMPTY_TYPE = &dummy_type_descriptors[0];
    IO_TYPE = &dummy_type_descriptors[1];
    FILL_TYPE = &dummy_type_descriptors[2];

    /* Fill in homogeneous core grid info */
    grid_backup = grid;
    grid =
	(struct s_grid_tile **)alloc_matrix(0, nx + 1, 0, ny + 1,
					    sizeof(struct s_grid_tile));
    for(i = 0; i < nx + 2; i++)
	{
	    for(j = 0; j < ny + 2; j++)
		{
		    if((i == 0 && j == 0) ||
		       (i == nx + 1 && j == 0) ||
		       (i == 0 && j == ny + 1) || (i == nx + 1
						   && j == ny + 1))
			{
			    grid[i][j].type = EMPTY_TYPE;
			}
		    else if(i == 0 || i == nx + 1 || j == 0 || j == ny + 1)
			{
			    grid[i][j].type = IO_TYPE;
			}
		    else
			{
			    grid[i][j].type = FILL_TYPE;
			}
		    grid[i][j].blocks =
			my_malloc(grid[i][j].type->capacity * sizeof(int));
		    grid[i][j].offset = 0;
		}
	}
}
static void
restore_original_device(void)
{
    int i, j;

    /* restore previous globals */
    IO_TYPE = IO_TYPE_BACKUP;
    EMPTY_TYPE = EMPTY_TYPE_BACKUP;
    FILL_TYPE = FILL_TYPE_BACKUP;
    type_descriptors = type_descriptors_backup;
    num_types = num_types_backup;

    /* free allocatd data */
    for(i = 0; i < nx + 2; i++)
	{
	    for(j = 0; j < ny + 2; j++)
		{
		    free(grid[i][j].blocks);
		}
	}
    free_matrix(grid, 0, nx + 1, 0, sizeof(struct s_grid_tile));
    grid = grid_backup;
}

/**************************************/
static void
reset_placement(void)
{
    int i, j, k;

    for(i = 0; i <= nx + 1; i++)
	{
	    for(j = 0; j <= ny + 1; j++)
		{
		    grid[i][j].usage = 0;
		    for(k = 0; k < grid[i][j].type->capacity; k++)
			{
			    grid[i][j].blocks[k] = EMPTY;
			}
		}
	}
}

/**************************************/
static void
alloc_and_assign_internal_structures(struct s_net **original_net,
				     struct s_block **original_block,
				     int *original_num_nets,
				     int *original_num_blocks)
{
    /*allocate new data structures to hold net, and block info */

    *original_net = net;