timing_place_lookup.c

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

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

    reset_placement();
}

/**************************************/
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].node_block);
	    free(net[i].node_block_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));

}

/**************************************/
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, i, max_pins_per_fb;

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

    if(router_opts.fixed_channel_width == NO_FIXED_CHANNEL_WIDTH)
	width_fac = 4 * max_pins_per_fb;	/*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;
    int warnings;
    t_graph_type graph_type;
    
    /*calls routines that set up routing resource graph and associated structures */


    /*must set up dummy blocks for the first pass through to setup locally used opins */
    /* Only one block per tile */
    assign_locations(FILL_TYPE, 1, 1, 0, FILL_TYPE, nx, ny, 0);

    clb_opins_used_locally = alloc_route_structs(subblock_data);

    free_rr_graph();
	
	if(router_opts.route_type == GLOBAL) {
		graph_type = GRAPH_GLOBAL;
	} else {
		graph_type = (det_routing_arch.directionality ==
		    BI_DIRECTIONAL ? GRAPH_BIDIR : GRAPH_UNIDIR);
	}
    
	build_rr_graph(graph_type, num_types, dummy_type_descriptors, nx,
		       ny, grid, chan_width_x[0], NULL,
		       det_routing_arch.switch_block_type,
			   det_routing_arch.Fs, det_routing_arch.num_segment, det_routing_arch.num_switch,
		       segment_inf, det_routing_arch.global_route_switch,
		       det_routing_arch.delayless_switch, timing_inf,
		       det_routing_arch.wire_to_ipin_switch,
		       router_opts.base_cost_type, &warnings);

    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();

    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(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)
{
    /*all routing occurs between block 0 (source) and block 1 (sink) */
    block[SOURCE_BLOCK].type = source_type;
    block[SOURCE_BLOCK].x = source_x_loc;
    block[SOURCE_BLOCK].y = source_y_loc;
    block[SOURCE_BLOCK].z = source_z_loc;

    block[SINK_BLOCK].type = sink_type;
    block[SINK_BLOCK].x = sink_x_loc;
    block[SINK_BLOCK].y = sink_y_loc;
    block[SINK_BLOCK].z = sink_z_loc;

    grid[source_x_loc][source_y_loc].blocks[source_z_loc] = SOURCE_BLOCK;
    grid[sink_x_loc][sink_y_loc].blocks[sink_z_loc] = SINK_BLOCK;

    net[NET_USED].node_block_pin[NET_USED_SOURCE_BLOCK] =
	get_first_pin(DRIVER, block[SOURCE_BLOCK].type);
    net[NET_USED].node_block_pin[NET_USED_SINK_BLOCK] =
	get_first_pin(RECEIVER, block[SINK_BLOCK].type);

    grid[source_x_loc][source_y_loc].usage += 1;
    grid[sink_x_loc][sink_y_loc].usage += 1;

}

/**************************************/
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)
{
    /*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 source_z_loc, sink_z_loc;

    /* Only one block per tile */
    source_z_loc = 0;
    sink_z_loc = 0;

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

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

    load_net_rr_terminals(rr_node_indices);

    T_crit = 1;
    pres_fac = 0;		/* ignore congestion */

    for(ipin = 1; ipin <= net[NET_USED].num_sinks; 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];

    grid[source_x_loc][source_y_loc].usage = 0;
    grid[source_x_loc][source_y_loc].blocks[source_z_loc] = EMPTY;
    grid[sink_x_loc][sink_y_loc].usage = 0;
    grid[sink_x_loc][sink_y_loc].blocks[sink_z_loc] = EMPTY;

    return (net_delay_value);
}

/**************************************/
static void
alloc_delta_arrays(void)
{
    int id_x, id_y;

    delta_fb_to_fb =
	(float **)alloc_matrix(0, nx - 1, 0, ny - 1, sizeof(float));
    delta_io_to_fb = (float **)alloc_matrix(0, nx, 0, ny, sizeof(float));
    delta_fb_to_io = (float **)alloc_matrix(0, nx, 0, ny, sizeof(float));
    delta_io_to_io =
	(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_io_to_fb[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_fb_to_fb[id_x][id_y] = IMPOSSIBLE;
		}
	}
    for(id_x = 0; id_x <= nx; id_x++)
	{
	    for(id_y = 0; id_y <= ny; id_y++)
		{
		    delta_fb_to_io[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_io_to_io[id_x][id_y] = IMPOSSIBLE;
		}
	}
}

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

    free_matrix(delta_io_to_fb, 0, nx, 0, sizeof(float));
    free_matrix(delta_fb_to_fb, 0, nx - 1, 0, sizeof(float));
    free_matrix(delta_fb_to_io, 0, nx, 0, sizeof(float));
    free_matrix(delta_io_to_io, 0, nx + 1, 0, sizeof(float));

}

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

    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_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)
{

    /*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 FB at the center as the source FB */

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

    source_type = FILL_TYPE;
    sink_type = FILL_TYPE;

    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_fb_to_fb[delta_x][delta_y] = 0.0;
			    continue;
			}
		    delta_fb_to_fb[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;