place_and_route.c

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

#include <stdio.h>
#include <sys/types.h>
#include "util.h"
#include "vpr_types.h"
#include "vpr_utils.h"
#include "globals.h"
#include "place_and_route.h"
#include "mst.h"
#include "place.h"
#include "read_place.h"
#include "route_export.h"
#include "draw.h"
#include "stats.h"
#include "check_route.h"
#include "rr_graph.h"
#include "path_delay.h"
#include "net_delay.h"
#include "timing_place.h"
#include <assert.h>

/******************* Subroutines local to this module ************************/

static int binary_search_place_and_route(struct s_placer_opts placer_opts,
					 char *place_file,
					 char *net_file,
					 char *arch_file,
					 char *route_file,
					 boolean full_stats,
					 boolean verify_binary_search,
					 struct s_annealing_sched
					 annealing_sched,
					 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_ptr,
					 t_chan_width_dist chan_width_dist,
					 t_mst_edge ** mst);

static float comp_width(t_chan * chan,
			float x,
			float separation);


void post_place_sync(IN int num_blocks,
		     INOUT const struct s_block block_list[],
		     INOUT t_subblock_data * subblock_data_ptr);

void free_subblock_data(t_subblock_data * subblock_data_ptr);


/************************* Subroutine Definitions ****************************/

void
place_and_route(enum e_operation operation,
		struct s_placer_opts placer_opts,
		char *place_file,
		char *net_file,
		char *arch_file,
		char *route_file,
		struct s_annealing_sched annealing_sched,
		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_ptr,
		t_chan_width_dist chan_width_dist)
{

/* This routine controls the overall placement and routing of a circuit. */

    char msg[BUFSIZE];
    int width_fac, inet, i;
    boolean success, Fc_clipped;
    float **net_delay, **net_slack;
    struct s_linked_vptr *net_delay_chunk_list_head;
    t_ivec **fb_opins_used_locally;	/* [0..num_blocks-1][0..num_class-1] */
    t_mst_edge **mst = NULL;	/* Make sure mst is never undefined */
    int max_pins_per_fb;

	Fc_clipped = FALSE;

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

    if(placer_opts.place_freq == PLACE_NEVER)
	{
	    /* Read the placement from a file */
	    read_place(place_file, net_file, arch_file, nx, ny, num_blocks,
		       block);
	    sync_grid_to_blocks(num_blocks, block, nx, ny, grid);
	}
    else
	{
	    assert((PLACE_ONCE == placer_opts.place_freq) ||
		   (PLACE_ALWAYS == placer_opts.place_freq));

	    try_place(placer_opts, annealing_sched, chan_width_dist,
		      router_opts, det_routing_arch, segment_inf,
		      timing_inf, subblock_data_ptr, &mst);
	    print_place(place_file, net_file, arch_file);
	}
    post_place_sync(num_blocks, block, subblock_data_ptr);


    fflush(stdout);
    if(operation == PLACE_ONLY)
	return;

    width_fac = router_opts.fixed_channel_width;

    /* If channel width not fixed, use binary search to find min W */
    if(NO_FIXED_CHANNEL_WIDTH == width_fac)
	{
	    binary_search_place_and_route(placer_opts, place_file,
					  net_file, arch_file, route_file,
					  router_opts.full_stats, router_opts.verify_binary_search,
					  annealing_sched, router_opts,
					  det_routing_arch, segment_inf,
					  timing_inf, subblock_data_ptr,
					  chan_width_dist, mst);
	}
    else
	{
	    if(det_routing_arch.directionality == UNI_DIRECTIONAL)
		{
		    if(width_fac % 2 != 0)
			{
			    printf
				("Error: place_and_route.c: given odd chan width (%d) for udsd architecture\n",
				 width_fac);
			    exit(1);
			}
		}
	    /* Other constraints can be left to rr_graph to check since this is one pass routing */


	    /* Allocate the major routing structures. */

	    fb_opins_used_locally = alloc_route_structs(*subblock_data_ptr);

	    if(timing_inf.timing_analysis_enabled)
		{
		    net_slack =
			alloc_and_load_timing_graph(timing_inf,
						    *subblock_data_ptr);
		    net_delay = alloc_net_delay(&net_delay_chunk_list_head);
		}
	    else
		{
		    net_delay = NULL;	/* Defensive coding. */
		    net_slack = NULL;
		}

	    success =
		try_route(width_fac, router_opts, det_routing_arch,
			  segment_inf, timing_inf, net_slack, net_delay,
			  chan_width_dist, fb_opins_used_locally, mst,
			  &Fc_clipped);

	    if(Fc_clipped)
		{
		    printf
			("Warning: Fc_output was too high and was clipped to full (maximum) connectivity.\n");
		}

	    if(success == FALSE)
		{
		    printf
			("Circuit is unrouteable with a channel width factor of %d\n\n",
			 width_fac);
		    sprintf(msg,
			    "Routing failed with a channel width factor of %d.  ILLEGAL routing shown.",
			    width_fac);
		}

	    else
		{
		    check_route(router_opts.route_type,
				det_routing_arch.num_switch,
				fb_opins_used_locally);
		    get_serial_num();

		    printf
			("Circuit successfully routed with a channel width factor of %d.\n\n",
			 width_fac);

			routing_stats(router_opts.full_stats, router_opts.route_type,
				  det_routing_arch.num_switch, segment_inf,
				  det_routing_arch.num_segment,
				  det_routing_arch.R_minW_nmos,
				  det_routing_arch.R_minW_pmos,
				  det_routing_arch.directionality,
				  timing_inf.timing_analysis_enabled,
				  net_slack, net_delay, *subblock_data_ptr);

		    print_route(route_file);

#ifdef CREATE_ECHO_FILES
		    /*print_sink_delays("routing_sink_delays.echo"); */
#endif /* CREATE_ECHO_FILES */

		    sprintf(msg,
			    "Routing succeeded with a channel width factor of %d.\n\n",
			    width_fac);
		}
	    free_subblock_data(subblock_data_ptr);

	    init_draw_coords(max_pins_per_fb);
	    update_screen(MAJOR, msg, ROUTING,
			  timing_inf.timing_analysis_enabled);

	    if(timing_inf.timing_analysis_enabled)
		{
		    assert(net_slack);
		    free_timing_graph(net_slack);

		    assert(net_delay);
		    free_net_delay(net_delay, &net_delay_chunk_list_head);
		}

	    free_route_structs(fb_opins_used_locally);
	    fflush(stdout);
	}

    /*WMF: cleaning up memory usage */
    if(mst)
	{
	    for(inet = 0; inet < num_nets; inet++)
		{
		    assert(mst[inet]);
		    free(mst[inet]);
		}
	    free(mst);
	    mst = NULL;
	}

}



static int
binary_search_place_and_route(struct s_placer_opts placer_opts,
			      char *place_file,
			      char *net_file,
			      char *arch_file,
			      char *route_file,
			      boolean full_stats,
			      boolean verify_binary_search,
			      struct s_annealing_sched annealing_sched,
			      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_ptr,
			      t_chan_width_dist chan_width_dist,
			      t_mst_edge ** mst)
{

/* This routine performs a binary search to find the minimum number of      *
 * tracks per channel required to successfully route a circuit, and returns *
 * that minimum width_fac.                                                  */

    struct s_trace **best_routing;	/* Saves the best routing found so far. */
    int current, low, high, final;
    int max_pins_per_fb, i;
    boolean success, prev_success, prev2_success, Fc_clipped = FALSE;
    char msg[BUFSIZE];
    float **net_delay, **net_slack;
    struct s_linked_vptr *net_delay_chunk_list_head;
    int try_w_limit;
    t_ivec **fb_opins_used_locally, **saved_clb_opins_used_locally;

    /* [0..num_blocks-1][0..num_class-1] */
    int attempt_count;
    int udsd_multiplier;
    int warnings;

	t_graph_type graph_type;

/* Allocate the major routing structures. */

	if(router_opts.route_type == GLOBAL) {
		graph_type = GRAPH_GLOBAL;
	} else {
		graph_type = (det_routing_arch.directionality ==
		    BI_DIRECTIONAL ? GRAPH_BIDIR : GRAPH_UNIDIR);
	}

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

    fb_opins_used_locally = alloc_route_structs(*subblock_data_ptr);
    best_routing = alloc_saved_routing(fb_opins_used_locally,
				       &saved_clb_opins_used_locally);

    if(timing_inf.timing_analysis_enabled)
	{
	    net_slack =
		alloc_and_load_timing_graph(timing_inf, *subblock_data_ptr);
	    net_delay = alloc_net_delay(&net_delay_chunk_list_head);
	}
    else
	{
	    net_delay = NULL;	/* Defensive coding. */
	    net_slack = NULL;
	}

    /* UDSD by AY Start */
    if(det_routing_arch.directionality == BI_DIRECTIONAL)
	udsd_multiplier = 1;
    else
	udsd_multiplier = 2;
    /* UDSD by AY End */

    if(router_opts.fixed_channel_width != NO_FIXED_CHANNEL_WIDTH)
	{
	    current = router_opts.fixed_channel_width + 5 * udsd_multiplier;
	    low = router_opts.fixed_channel_width - 1 * udsd_multiplier;
	}
    else
	{
	    current = max_pins_per_fb + max_pins_per_fb % 2;	/* Binary search part */
	    low = -1;
	}

    /* Constraints must be checked to not break rr_graph generator */
    if(det_routing_arch.directionality == UNI_DIRECTIONAL)
	{
	    if(current % 2 != 0)
		{
		    printf
			("Error: place_and_route.c: tried odd chan width (%d) for udsd architecture\n",
			 current);
		    exit(1);
		}
	}

    else
	{
	    if(det_routing_arch.Fs % 3)
		{
		    printf("Fs must be three in bidirectional mode\n");
		    exit(1);
		}
	}

    high = -1;
    final = -1;
    try_w_limit = 0;

    attempt_count = 0;

    while(final == -1)
	{

	    printf("low, high, current %d %d %d\n", low, high, current);
	    fflush(stdout);

/* Check if the channel width is huge to avoid overflow.  Assume the *
 * circuit is unroutable with the current router options if we're    *
 * going to overflow.                                                */
	    if(router_opts.fixed_channel_width != NO_FIXED_CHANNEL_WIDTH)
		{
		    if(current > router_opts.fixed_channel_width * 4)
			{
			    printf
				("This circuit appears to be unroutable with the current "
				 "router options. Last failed at %d\n", low);
			    printf("Aborting routing procedure.\n");
			    exit(1);
			}
		}
	    else
		{
		    if(current > 305)
			{
			    printf
				("This circuit appears to be unroutable with the current "
				 "router options. Last failed at %d\n", low);
			    printf("Aborting routing procedure.\n");
			    exit(1);
			}
		}

	    if((current * 3) < det_routing_arch.Fs)
		{
		    printf
			("width factor is now below specified Fs. Stop search.\n");
		    final = high;
		    break;
		}

	    if(placer_opts.place_freq == PLACE_ALWAYS)
		{
		    placer_opts.place_chan_width = current;
		    try_place(placer_opts, annealing_sched, chan_width_dist,
			      router_opts, det_routing_arch, segment_inf,
			      timing_inf, subblock_data_ptr, &mst);
		}
	    success =
		try_route(current, router_opts, det_routing_arch, segment_inf,
			  timing_inf, net_slack, net_delay, chan_width_dist,
			  fb_opins_used_locally, mst, &Fc_clipped);
	    attempt_count++;
	    fflush(stdout);
#if 1
	    if(success && (Fc_clipped == FALSE))
		{
#else
	    if(success
	       && (Fc_clipped == FALSE
		   || det_routing_arch.Fc_type == FRACTIONAL))
		{
#endif
		    high = current;

		    /* If Fc_output is too high, set to full connectivity but warn the user */
		    if(Fc_clipped)
			{
			    printf
				("Warning: Fc_output was too high and was clipped to full (maximum) connectivity.\n");
			}

/* If we're re-placing constantly, save placement in case it is best. */
#if 0
		    if(placer_opts.place_freq == PLACE_ALWAYS)
			{
			    print_place(place_file, net_file, arch_file);
			}
#endif

		    /* Save routing in case it is best. */
		    save_routing(best_routing, fb_opins_used_locally,
				 saved_clb_opins_used_locally);

		    if((high - low) <= 1 * udsd_multiplier)
			final = high;

		    if(low != -1)