route_common.c

VPR布局布线源码

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

/***************** Variables shared only by route modules *******************/

t_rr_node_route_inf *rr_node_route_inf = NULL;	/* [0..num_rr_nodes-1] */

struct s_bb *route_bb = NULL;	/* [0..num_nets-1]. Limits area in which each  */

			      /* net must be routed.                         */


/**************** Static variables local to route_common.c ******************/

static struct s_heap **heap;	/* Indexed from [1..heap_size] */
static int heap_size;		/* Number of slots in the heap array */
static int heap_tail;		/* Index of first unused slot in the heap array */

/* For managing my own list of currently free heap data structures.     */
static struct s_heap *heap_free_head = NULL;

/* For managing my own list of currently free trace data structures.    */
static struct s_trace *trace_free_head = NULL;

#ifdef DEBUG
static int num_trace_allocated = 0;	/* To watch for memory leaks. */
static int num_heap_allocated = 0;
static int num_linked_f_pointer_allocated = 0;
#endif

static struct s_linked_f_pointer *rr_modified_head = NULL;
static struct s_linked_f_pointer *linked_f_pointer_free_head = NULL;



/*  The numbering relation between the channels and clbs is:               *
 *                                                                         *
 *  |   IO    | chan_   |   FB      | chan_   |   FB     |               *
 *  |grid[0][2]| y[0][2] | grid[1][2]  | y[1][2] |  grid[2][2]|               *
 *  +-------- +         +------------+         +-----------+               *
 *                                                           } capacity in *
 *   No channel          chan_x[1][1]          chan_x[2][1]  } chan_width  *
 *                                                           } _x[1]       *
 *  +---------+         +------------+         +-----------+               *
 *  |         | chan_   |            | chan_   |           |               *
 *  |  IO     | y[0][1] |    FB     | y[1][1] |   FB     |               *
 *  |grid[0][1]|         |  grid[1][1] |         | grid[2][1] |               *
 *  |         |         |            |         |           |               *
 *  +---------+         +------------+         +-----------+               *
 *                                                           } capacity in *
 *                      chan_x[1][0]           chan_x[2][0]  } chan_width  * 
 *                                                           } _x[0]       *
 *                      +------------+         +-----------+               *
 *              No      |            | No      |           |               *
 *            Channel   |    IO      | Channel |   IO      |               *
 *                      |  grid[1][0] |         | grid[2][0] |               *
 *                      |            |         |           |               *
 *                      +------------+         +-----------+               *
 *                                                                         *
 *             {=======}              {=======}                            *
 *            Capacity in            Capacity in                           *
 *          chan_width_y[0]        chan_width_y[1]                         *
 *                                                                         */


/******************** Subroutines local to route_common.c *******************/

static void free_trace_data(struct s_trace *tptr);
static void load_route_bb(int bb_factor);

static struct s_trace *alloc_trace_data(void);
static void add_to_heap(struct s_heap *hptr);
static struct s_heap *alloc_heap_data(void);
static struct s_linked_f_pointer *alloc_linked_f_pointer(void);

static t_ivec **alloc_and_load_clb_opins_used_locally(t_subblock_data
						      subblock_data);
static void adjust_one_rr_occ_and_pcost(int inode,
					int add_or_sub,
					float pres_fac);



/************************** Subroutine definitions ***************************/

void
save_routing(struct s_trace **best_routing,
	     t_ivec ** fb_opins_used_locally,
	     t_ivec ** saved_clb_opins_used_locally)
{

/* This routing frees any routing currently held in best routing,       *
 * then copies over the current routing (held in trace_head), and       *
 * finally sets trace_head and trace_tail to all NULLs so that the      *
 * connection to the saved routing is broken.  This is necessary so     *
 * that the next iteration of the router does not free the saved        *
 * routing elements.  Also saves any data about locally used clb_opins, *
 * since this is also part of the routing.                              */

    int inet, iblk, iclass, ipin, num_local_opins;
    struct s_trace *tptr, *tempptr;
    t_type_ptr type;

    for(inet = 0; inet < num_nets; inet++)
	{

/* Free any previously saved routing.  It is no longer best. */
	    tptr = best_routing[inet];
	    while(tptr != NULL)
		{
		    tempptr = tptr->next;
		    free_trace_data(tptr);
		    tptr = tempptr;
		}

/* Save a pointer to the current routing in best_routing. */
	    best_routing[inet] = trace_head[inet];

/* Set the current (working) routing to NULL so the current trace       *
 * elements won't be reused by the memory allocator.                    */

	    trace_head[inet] = NULL;
	    trace_tail[inet] = NULL;
	}

/* Save which OPINs are locally used.                           */

    for(iblk = 0; iblk < num_blocks; iblk++)
	{
	    type = block[iblk].type;
	    for(iclass = 0; iclass < type->num_class; iclass++)
		{
		    num_local_opins =
			fb_opins_used_locally[iblk][iclass].nelem;
		    for(ipin = 0; ipin < num_local_opins; ipin++)
			{
			    saved_clb_opins_used_locally[iblk][iclass].
				list[ipin] =
				fb_opins_used_locally[iblk][iclass].
				list[ipin];
			}
		}
	}
}


void
restore_routing(struct s_trace **best_routing,
		t_ivec ** fb_opins_used_locally,
		t_ivec ** saved_clb_opins_used_locally)
{

/* Deallocates any current routing in trace_head, and replaces it with    *
 * the routing in best_routing.  Best_routing is set to NULL to show that *
 * it no longer points to a valid routing.  NOTE:  trace_tail is not      *
 * restored -- it is set to all NULLs since it is only used in            *
 * update_traceback.  If you need trace_tail restored, modify this        *
 * routine.  Also restores the locally used opin data.                    */

    int inet, iblk, ipin, iclass, num_local_opins;
    t_type_ptr type;

    for(inet = 0; inet < num_nets; inet++)
	{

	    /* Free any current routing. */
	    free_traceback(inet);

	    /* Set the current routing to the saved one. */
	    trace_head[inet] = best_routing[inet];
	    best_routing[inet] = NULL;	/* No stored routing. */
	}

/* Save which OPINs are locally used.                           */

    for(iblk = 0; iblk < num_blocks; iblk++)
	{
	    type = block[iblk].type;
	    for(iclass = 0; iclass < type->num_class; iclass++)
		{
		    num_local_opins =
			fb_opins_used_locally[iblk][iclass].nelem;
		    for(ipin = 0; ipin < num_local_opins; ipin++)
			{
			    fb_opins_used_locally[iblk][iclass].list[ipin] =
				saved_clb_opins_used_locally[iblk][iclass].
				list[ipin];
			}
		}

	}
}


void
get_serial_num(void)
{

/* This routine finds a "magic cookie" for the routing and prints it.    *
 * Use this number as a routing serial number to ensure that programming *
 * changes do not break the router.                                      */

    int inet, serial_num, inode;
    struct s_trace *tptr;

    serial_num = 0;

    for(inet = 0; inet < num_nets; inet++)
	{

/* Global nets will have null trace_heads (never routed) so they *
 * are not included in the serial number calculation.            */

	    tptr = trace_head[inet];
	    while(tptr != NULL)
		{
		    inode = tptr->index;
		    serial_num +=
			(inet + 1) * (rr_node[inode].xlow * (nx + 1) -
				      rr_node[inode].yhigh);

		    serial_num -= rr_node[inode].ptc_num * (inet + 1) * 10;

		    serial_num -= rr_node[inode].type * (inet + 1) * 100;
		    serial_num %= 2000000000;	/* Prevent overflow */
		    tptr = tptr->next;
		}
	}
    printf("Serial number (magic cookie) for the routing is: %d\n",
	   serial_num);
}


boolean
try_route(int width_fac,
	  struct s_router_opts router_opts,
	  struct s_det_routing_arch det_routing_arch,
	  t_segment_inf * segment_inf,
	  t_timing_inf timing_inf,
	  float **net_slack,
	  float **net_delay,
	  t_chan_width_dist chan_width_dist,
	  t_ivec ** fb_opins_used_locally,
	  t_mst_edge ** mst,
	  boolean * Fc_clipped)
{

/* Attempts a routing via an iterated maze router algorithm.  Width_fac *
 * specifies the relative width of the channels, while the members of   *
 * router_opts determine the value of the costs assigned to routing     *
 * resource node, etc.  det_routing_arch describes the detailed routing *
 * architecture (connection and switch boxes) of the FPGA; it is used   *
 * only if a DETAILED routing has been selected.                        */

    int tmp;
    boolean success;
	t_graph_type graph_type;

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

/* Set the channel widths */

    init_chan(width_fac, chan_width_dist);

/* Free any old routing graph, if one exists. */

    free_rr_graph();

/* Set up the routing resource graph defined by this FPGA architecture. */

    build_rr_graph(graph_type,
		   num_types, 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, &tmp);

/* Allocate and load some additional rr_graph information needed only by *
 * the router.                                                           */

    alloc_and_load_rr_node_route_structs();

    init_route_structs(router_opts.bb_factor);

    if(router_opts.router_algorithm == BREADTH_FIRST)
	{
	    printf("Confirming Router Algorithm: BREADTH_FIRST.\n");
	    success =
		try_breadth_first_route(router_opts, fb_opins_used_locally,
					width_fac);
	}
    else if(router_opts.router_algorithm == TIMING_DRIVEN)
	{			/* TIMING_DRIVEN route */
	    printf("Confirming Router Algorithm: TIMING_DRIVEN.\n");
	    assert(router_opts.route_type != GLOBAL);
	    success =
		try_timing_driven_route(router_opts, net_slack, net_delay,
					fb_opins_used_locally);
	}
    else
	{			/* Directed Search Routability Driven */
	    printf("Confirming Router Algorithm: DIRECTED_SEARCH.\n");
	    success =
		try_directed_search_route(router_opts, fb_opins_used_locally,
					  width_fac, mst);
	}

    free_rr_node_route_structs();

    return (success);
}


boolean
feasible_routing(void)
{

/* This routine checks to see if this is a resource-feasible routing.      *
 * That is, are all rr_node capacity limitations respected?  It assumes    *
 * that the occupancy arrays are up to date when it is called.             */

    int inode;

    for(inode = 0; inode < num_rr_nodes; inode++)
	if(rr_node[inode].occ > rr_node[inode].capacity)
	    return (FALSE);

    return (TRUE);
}


void
pathfinder_update_one_cost(struct s_trace *route_segment_start,
			   int add_or_sub,
			   float pres_fac)
{

/* This routine updates the occupancy and pres_cost of the rr_nodes that are *
 * affected by the portion of the routing of one net that starts at          *
 * route_segment_start.  If route_segment_start is trace_head[inet], the     *
 * cost of all the nodes in the routing of net inet are updated.  If         *
 * add_or_sub is -1 the net (or net portion) is ripped up, if it is 1 the    *
 * net is added to the routing.  The size of pres_fac determines how severly *
 * oversubscribed rr_nodes are penalized.                                    */

    struct s_trace *tptr;
    int inode, occ, capacity;

    tptr = route_segment_start;
    if(tptr == NULL)		/* No routing yet. */
	return;

    for(;;)
	{
	    inode = tptr->index;

	    occ = rr_node[inode].occ + add_or_sub;
	    capacity = rr_node[inode].capacity;

	    rr_node[inode].occ = occ;

/* pres_cost is Pn in the Pathfinder paper. I set my pres_cost according to *
 * the overuse that would result from having ONE MORE net use this routing  *
 * node.                                                                    */

	    if(occ < capacity)
		{
		    rr_node_route_inf[inode].pres_cost = 1.;
		}
	    else
		{
		    rr_node_route_inf[inode].pres_cost =
			1. + (occ + 1 - capacity) * pres_fac;
		}

	    if(rr_node[inode].type == SINK)
		{
		    tptr = tptr->next;	/* Skip next segment. */
		    if(tptr == NULL)
			break;
		}

	    tptr = tptr->next;

	}			/* End while loop -- did an entire traceback. */
}


void
pathfinder_update_cost(float pres_fac,
		       float acc_fac)
{

/* This routine recomputes the pres_cost and acc_cost of each routing        *
 * resource for the pathfinder algorithm after all nets have been routed.    *
 * It updates the accumulated cost to by adding in the number of extra       *
 * signals sharing a resource right now (i.e. after each complete iteration) *
 * times acc_fac.  It also updates pres_cost, since pres_fac may have        *
 * changed.  THIS ROUTINE ASSUMES THE OCCUPANCY VALUES IN RR_NODE ARE UP TO  *
 * DATE.                                                                     */

    int inode, occ, capacity;

    for(inode = 0; inode < num_rr_nodes; inode++)
	{
	    occ = rr_node[inode].occ;
	    capacity = rr_node[inode].capacity;

	    if(occ > capacity)
		{
		    rr_node_route_inf[inode].acc_cost +=
			(occ - capacity) * acc_fac;
		    rr_node_route_inf[inode].pres_cost =
			1. + (occ + 1 - capacity) * pres_fac;
		}

/* If occ == capacity, we don't need to increase acc_cost, but a change    *
 * in pres_fac could have made it necessary to recompute the cost anyway.  */

	    else if(occ == capacity)
		{
		    rr_node_route_inf[inode].pres_cost = 1. + pres_fac;
		}
	}
}


void
init_route_structs(int bb_factor)
{

/* Call this before you route any nets.  It frees any old traceback and   *
 * sets the list of rr_nodes touched to empty.                            */

    int i;

    for(i = 0; i < num_nets; i++)
	free_traceback(i);

    load_route_bb(bb_factor);

/* Check that things that should have been emptied after the last routing *
 * really were.                                                           */

    if(rr_modified_head != NULL)
	{
	    printf
		("Error in init_route_structs.  List of modified rr nodes is \n"
		 "not empty.\n");
	    exit(1);
	}

    if(heap_tail != 1)
	{
	    printf("Error in init_route_structs.  Heap is not empty.\n");
	    exit(1);
	}
}


struct s_trace *
update_traceback(struct s_heap *hptr,
		 int inet)
{

/* This routine adds the most recently finished wire segment to the         *
 * traceback linked list.  The first connection starts with the net SOURCE  *
 * and begins at the structure pointed to by trace_head[inet]. Each         *
 * connection ends with a SINK.  After each SINK, the next connection       *
 * begins (if the net has more than 2 pins).  The first element after the   *
 * SINK gives the routing node on a previous piece of the routing, which is *
 * the link from the existing net to this new piece of the net.             *
 * In each traceback I start at the end of a path and trace back through    *
 * its predecessors to the beginning.  I have stored information on the     *
 * predecesser of each node to make traceback easy -- this sacrificies some *
 * memory for easier code maintenance.  This routine returns a pointer to   *
 * the first "new" node in the traceback (node not previously in trace).    */

    struct s_trace *tptr, *prevptr, *temptail, *ret_ptr;
    int inode;
    short iedge;

#ifdef DEBUG
    t_rr_type rr_type;
#endif