timing_place_lookup.c

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

#include <stdio.h>
#include <math.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 "route_export.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: if you do not have logically equivalent output and    */
/*inputs, some of this code must be re-written.               */

/*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 */

#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 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_inpad_to_clb;
float **delta_clb_to_clb;
float **delta_clb_to_outpad;
float **delta_inpad_to_outpad;


/*** 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;

t_ivec **clb_opins_used_locally;

static FILE *lookup_dump; /*if debugging mode is on, print out to   */
			    /*the file defined in DUMPFILE */

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

static void alloc_net(void);

static void alloc_block(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 (enum e_block_types source_type, 
			      int source_x_loc, int source_y_loc, 
			      enum e_block_types sink_type,
			      int sink_x_loc, int sink_y_loc);

static float assign_blocks_and_route_net (enum e_block_types source_type, 
				   int source_x_loc, int source_y_loc, 
				   enum e_block_types 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, 
				   enum e_block_types source_type, 
				   enum e_block_types 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_clb_to_clb (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_inpad_to_clb (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_clb_to_outpad(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_inpad_to_outpad(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);

static int get_longest_segment_length(struct s_det_routing_arch det_routing_arch,
				      t_segment_inf *segment_inf);
static void init_occ(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) {
  /*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<num_class; i++) {
    if (class_inf[i].type == pintype && !is_global_clb_pin[currpin]) 
      return(class_inf[i].pinlist[0]);
    else 
      currpin += class_inf[i].num_pins;
  } 
  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++) {

    len = strlen ("TEMP_NET");
    net[i].name = (char *) my_malloc ((len + 1) * sizeof(char));
    strcpy (net[NET_USED].name,"TEMP_NET");

    net[i].num_pins = BLOCK_COUNT;
    net[i].blocks = (int *) my_malloc(BLOCK_COUNT * sizeof(int));
    net[i].blocks[NET_USED_SOURCE_BLOCK] = NET_USED_SOURCE_BLOCK;  /*driving block*/
    net[i].blocks[NET_USED_SINK_BLOCK] = NET_USED_SINK_BLOCK;  /*target block */

    net[i].blk_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;

  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 (pins_per_clb * sizeof(int));
    block[ix_b].nets[0] = 0;
    for (ix_p=1; ix_p < pins_per_clb; ix_p++) 
      block[ix_b].nets[ix_p] = OPEN;
  }
}
/**************************************/
static void init_occ(void){ 
  
  int i, j;

  for (i=0;i<=nx+1;i++) {
    for (j=0;j<=ny+1; j++) {
      clb[i][j].occ = 0;
    }
  }
}
/**************************************/
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;
  *original_num_nets = num_nets;
  num_nets = NET_COUNT;
  alloc_net();

  *original_block = block;
  *original_num_blocks = num_blocks;
  num_blocks = BLOCK_COUNT;
  alloc_block();

  
  /* [0..num_nets-1][1..num_pins-1] */
  net_delay = (float**) alloc_matrix(0,NET_COUNT-1,1,BLOCK_COUNT-1,sizeof(float));
  net_slack = (float**) alloc_matrix(0,NET_COUNT-1,1,BLOCK_COUNT-1,sizeof(float));

  init_occ();

}

/**************************************/
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) {
  /*reset gloabal data structures to the state that they were in before these*/
  /*lookup computation routines were called */

  int i;


  /*there should be only one net to free, but this is safer*/
  for (i=0; i<NET_COUNT; i++) {
    free (net[i].name);
    free (net[i].blocks);
    free (net[i].blk_pin);
  }
  free (net);
  net = original_net;

  for (i=0; i< BLOCK_COUNT; i++) {
    free (block[i].name);
    free (block[i].nets); 
  }
  free (block);
  block = original_block;
  
  num_nets = original_num_nets;
  num_blocks = original_num_blocks;
  
  free_matrix (net_delay, 0,NET_COUNT-1,1, sizeof(float));
  free_matrix (net_slack, 0,NET_COUNT-1,1, sizeof(float));