timing_place_lookup.c

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

}
/**************************************/
static void setup_chan_width (struct s_router_opts router_opts,
		       t_chan_width_dist chan_width_dist) {
  /*we give plenty of tracks, this increases routability for the */
  /*lookup table generation */ 

  int width_fac; 

  if (router_opts.fixed_channel_width == NO_FIXED_CHANNEL_WIDTH)
    width_fac = 4 * pins_per_clb; /*this is 2x the value that binary search starts*/
                                  /*this should be enough to allow most pins to   */
                                  /*connect to tracks in the architecture */
  else
    width_fac = router_opts.fixed_channel_width;

  init_chan(width_fac, 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) {

  int bb_factor;

  /*calls routines that set up routing resource graph and associated structures*/


  /*must set up dummy blocks for the first pass through*/
  assign_locations(CLB, 1, 1, CLB, nx, ny);

  clb_opins_used_locally = alloc_route_structs(subblock_data);

  free_rr_graph();
  build_rr_graph (router_opts.route_type, det_routing_arch, segment_inf,
		  timing_inf, router_opts.base_cost_type);
  alloc_and_load_rr_node_route_structs();

  alloc_timing_driven_route_structs (&pin_criticality, &sink_order, &rt_node_of_sink);


  bb_factor = nx + ny; /*set it to a huge value*/
  init_route_structs(bb_factor);


}
/**************************************/
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
			   ) {

  free_rr_graph_internals (router_opts.route_type, det_routing_arch, segment_inf,
		  timing_inf, router_opts.base_cost_type);
  free_rr_graph();

  free_rr_node_route_structs();
  free_route_structs(clb_opins_used_locally);
  free_trace_structs();

  free_timing_driven_route_structs (pin_criticality, sink_order, rt_node_of_sink);

}
/**************************************/
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) {
  /*all routing occurs between block 0 (source) and block 1 (sink)*/
  int isubblk;


  block[SOURCE_BLOCK].type = source_type;
  block[SINK_BLOCK].type = sink_type;

  block[SOURCE_BLOCK].x = source_x_loc;
  block[SOURCE_BLOCK].y = source_y_loc;
  
  block[SINK_BLOCK].x = sink_x_loc;
  block[SINK_BLOCK].y = sink_y_loc;


  if (source_type == CLB){
    net[NET_USED].blk_pin[NET_USED_SOURCE_BLOCK] = get_first_pin(DRIVER);
    clb[source_x_loc][source_y_loc].u.block = SOURCE_BLOCK;
    clb[source_x_loc][source_y_loc].occ += 1;
  }
  else {
     net[NET_USED].blk_pin[NET_USED_SOURCE_BLOCK] = OPEN;
     isubblk = clb[source_x_loc][source_y_loc].occ;
     clb[source_x_loc][source_y_loc].u.io_blocks[isubblk] = SOURCE_BLOCK;
     clb[source_x_loc][source_y_loc].occ += 1;
  }
  if (sink_type == CLB){
    net[NET_USED].blk_pin[NET_USED_SINK_BLOCK] = get_first_pin(RECEIVER);
    clb[sink_x_loc][sink_y_loc].u.block = SINK_BLOCK;
    clb[sink_x_loc][sink_y_loc].occ += 1;
  }
  else{
     net[NET_USED].blk_pin[NET_USED_SINK_BLOCK] = OPEN;
     isubblk = clb[sink_x_loc][sink_y_loc].occ;
     clb[sink_x_loc][sink_y_loc].u.io_blocks[isubblk] = SINK_BLOCK;
     clb[sink_x_loc][sink_y_loc].occ += 1;
  }
}
/**************************************/
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
				   ){

  /*places blocks at the specified locations, and routes a net between them*/
  /*returns the delay of this net */

  boolean is_routeable;
  int ipin;
  float pres_fac, T_crit;
  float net_delay_value;
  int **rr_node_indices;
  int nodes_per_chan;



  net_delay_value = IMPOSSIBLE; /*set to known value for debug purposes*/

  assign_locations( source_type, source_x_loc, source_y_loc, 
		 sink_type, sink_x_loc, sink_y_loc);

  rr_node_indices = get_rr_node_indices();
  nodes_per_chan = get_nodes_per_chan();

  load_net_rr_terminals(rr_node_indices, nodes_per_chan);
  
  T_crit = 1;
  pres_fac = 0; /* ignore congestion */

  for (ipin=1; ipin< net[NET_USED].num_pins; ipin ++)
    net_slack[NET_USED][ipin] = 0;

  is_routeable = timing_driven_route_net (NET_USED, pres_fac, 
		 router_opts.max_criticality, router_opts.criticality_exp, 
		 router_opts.astar_fac, router_opts.bend_cost,
                 net_slack[NET_USED], pin_criticality, sink_order,
                 rt_node_of_sink, T_crit, net_delay[NET_USED]);
  
  net_delay_value = net_delay[NET_USED][NET_USED_SINK_BLOCK];

  clb[source_x_loc][source_y_loc].occ = 0;
  clb[sink_x_loc][sink_y_loc].occ = 0;

  return (net_delay_value);

}

/**************************************/
static void alloc_delta_arrays(void) {

  int id_x, id_y;

  delta_clb_to_clb = (float **) alloc_matrix (0, nx-1, 0, ny-1,sizeof(float));
  delta_inpad_to_clb = (float **) alloc_matrix (0, nx, 0, ny, sizeof(float));
  delta_clb_to_outpad = (float **) alloc_matrix (0, nx, 0, ny, sizeof(float));
  delta_inpad_to_outpad = (float **) alloc_matrix (0, nx+1, 0, ny+1, sizeof(float));


  /*initialize all of the array locations to -1*/
  
  for (id_x = 0; id_x <= nx; id_x ++) {
    for (id_y = 0; id_y <= ny; id_y ++) {
      delta_inpad_to_clb[id_x][id_y] = IMPOSSIBLE;
    }
  }
  for (id_x = 0; id_x <= nx-1; id_x ++) {
    for (id_y = 0; id_y <= ny-1; id_y ++) {
      delta_clb_to_clb[id_x][id_y] = IMPOSSIBLE;  
    }
  }
  for (id_x = 0; id_x <= nx; id_x ++) {
    for (id_y = 0; id_y <= ny; id_y ++) {
      delta_clb_to_outpad[id_x][id_y] = IMPOSSIBLE;
    }
  }
  for (id_x = 0; id_x <= nx+1; id_x ++) {
    for (id_y = 0; id_y <= ny+1; id_y ++) {
      delta_inpad_to_outpad[id_x][id_y] = IMPOSSIBLE;
    }
  }
}

/**************************************/
static void free_delta_arrays(void) {

  free_matrix(delta_inpad_to_clb,0, nx, 0, sizeof(float));
  free_matrix(delta_clb_to_clb, 0, nx-1, 0, sizeof(float));
  free_matrix(delta_clb_to_outpad, 0, nx, 0, sizeof(float));
  free_matrix(delta_inpad_to_outpad, 0, nx+1, 0, sizeof(float));

}
/**************************************/
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
			    ){

  int delta_x, delta_y;
  int sink_x, sink_y;

  for (sink_x = start_x; sink_x <= end_x; sink_x ++) {
    for (sink_y = start_y; sink_y <= end_y; sink_y ++) {
      delta_x = abs(sink_x - source_x);
      delta_y = abs(sink_y - source_y);

      if (delta_x == 0 && delta_y ==0) 
	continue;  /*do not compute distance from a block to itself     */
                   /*if a value is desired, pre-assign it somewhere else*/

      (*matrix_ptr)[delta_x][delta_y] = 
	assign_blocks_and_route_net (source_type, source_x, source_y, 
				     sink_type, sink_x, sink_y, router_opts,
				     det_routing_arch, 
				     segment_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) {

  /*this routine must compute delay values in a slightly different way than the*/
  /*other compute routines. We cannot use a location close to the edge as the  */
  /*source location for the majority of the delay computations  because this   */
  /*would give gradually increasing delay values. To avoid this from happening */
  /*a clb that is at least longest_length away from an edge should be chosen   */
  /*as a source , if longest_length is more than 0.5 of the total size then    */
  /*choose a CLB at the center as the source CLB */

  int source_x, source_y, sink_x, sink_y;
  int start_x, start_y, end_x, end_y;
  int delta_x, delta_y;
  enum e_block_types source_type, sink_type;

  source_type = CLB;
  sink_type = CLB;

  if (longest_length < 0.5 * (nx)){
    start_x = longest_length;
  }
  else {
    start_x = (int)(0.5 * nx);
  }
  end_x = nx;
  source_x = start_x;

  if (longest_length < 0.5 * (ny)) {
    start_y = longest_length;
  }
  else {
    start_y = (int) (0.5 * ny);
  }
  end_y = ny;
  source_y = start_y;


  /*don't put the sink all the way to the corner, until it is necessary*/
  for (sink_x = start_x; sink_x <= end_x-1; sink_x ++) {
    for (sink_y = start_y; sink_y <= end_y-1; sink_y ++) {
      delta_x = abs(sink_x - source_x);
      delta_y = abs(sink_y - source_y);

      if (delta_x == 0 && delta_y ==0) {
	delta_clb_to_clb[delta_x][delta_y] = 0.0;
	continue; 
      }
      delta_clb_to_clb[delta_x][delta_y] =
	assign_blocks_and_route_net (source_type, source_x, source_y, sink_type, 
				     sink_x, sink_y, router_opts, det_routing_arch,
				     segment_inf,timing_inf);
    }

  }


  sink_x = end_x-1;
  sink_y = end_y-1;

  for (source_x = start_x-1; source_x >=1; source_x --) {
    for (source_y = start_y; source_y <= end_y-1; source_y ++) {
      delta_x = abs(sink_x - source_x);
      delta_y = abs(sink_y - source_y);

      delta_clb_to_clb[delta_x][delta_y] =
	assign_blocks_and_route_net (source_type, source_x, source_y, sink_type, 
				     sink_x, sink_y, router_opts, det_routing_arch,
				     segment_inf,timing_inf);
    }
  }

  for (source_x = 1; source_x <= end_x-1; source_x ++) {
    for (source_y =1; source_y < start_y; source_y++ ) {
      delta_x = abs(sink_x - source_x);
      delta_y = abs(sink_y - source_y);