route_breadth_first.c

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

#include <stdio.h>
#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "mst.h"
#include "route_export.h"
#include "route_common.h"
#include "route_breadth_first.h"


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

static boolean breadth_first_route_net(int inet,
				       float bend_cost);

static void breadth_first_expand_trace_segment(struct s_trace *start_ptr,
					       int
					       remaining_connections_to_sink);

static void breadth_first_expand_neighbours(int inode,
					    float pcost,
					    int inet,
					    float bend_cost);

static void breadth_first_add_source_to_heap(int inet);


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

boolean
try_breadth_first_route(struct s_router_opts router_opts,
			t_ivec ** fb_opins_used_locally,
			int width_fac)
{

/* Iterated maze router ala Pathfinder Negotiated Congestion algorithm,  *
 * (FPGA 95 p. 111).  Returns TRUE if it can route this FPGA, FALSE if   *
 * it can't.                                                             */

    float pres_fac;
    boolean success, is_routable, rip_up_local_opins;
    int itry, inet;

/* Usually the first iteration uses a very small (or 0) pres_fac to find  *
 * the shortest path and get a congestion map.  For fast compiles, I set  *
 * pres_fac high even for the first iteration.                            */

    pres_fac = router_opts.first_iter_pres_fac;

    for(itry = 1; itry <= router_opts.max_router_iterations; itry++)
	{

	    for(inet = 0; inet < num_nets; inet++)
		{
		    if(net[inet].is_global == FALSE)
			{	/* Skip global nets. */

			    pathfinder_update_one_cost(trace_head[inet], -1,
						       pres_fac);

			    is_routable =
				breadth_first_route_net(inet,
							router_opts.
							bend_cost);

			    /* Impossible to route? (disconnected rr_graph) */

			    if(!is_routable)
				{
				    printf("Routing failed.\n");
				    return (FALSE);
				}

			    pathfinder_update_one_cost(trace_head[inet], 1,
						       pres_fac);

			}
		}

	    /* Make sure any FB OPINs used up by subblocks being hooked directly     *
	     * to them are reserved for that purpose.                                 */

	    if(itry == 1)
		rip_up_local_opins = FALSE;
	    else
		rip_up_local_opins = TRUE;

	    reserve_locally_used_opins(pres_fac, rip_up_local_opins,
				       fb_opins_used_locally);

	    success = feasible_routing();
	    if(success)
		{
		    printf
			("Successfully routed after %d routing iterations.\n",
			 itry);
		    return (TRUE);
		}

	    if(itry == 1)
		pres_fac = router_opts.initial_pres_fac;
	    else
		pres_fac *= router_opts.pres_fac_mult;

	    pathfinder_update_cost(pres_fac, router_opts.acc_fac);
	}

    printf("Routing failed.\n");
    return (FALSE);
}


static boolean
breadth_first_route_net(int inet,
			float bend_cost)
{

/* Uses a maze routing (Dijkstra's) algorithm to route a net.  The net       *
 * begins at the net output, and expands outward until it hits a target      *
 * pin.  The algorithm is then restarted with the entire first wire segment  *
 * included as part of the source this time.  For an n-pin net, the maze     *
 * router is invoked n-1 times to complete all the connections.  Inet is     *
 * the index of the net to be routed.  Bends are penalized by bend_cost      *
 * (which is typically zero for detailed routing and nonzero only for global *
 * routing), since global routes with lots of bends are tougher to detailed  *
 * route (using a detailed router like SEGA).                                *
 * If this routine finds that a net *cannot* be connected (due to a complete *
 * lack of potential paths, rather than congestion), it returns FALSE, as    *
 * routing is impossible on this architecture.  Otherwise it returns TRUE.   */

    int i, inode, prev_node, remaining_connections_to_sink;
    float pcost, new_pcost;
    struct s_heap *current;
    struct s_trace *tptr;

    free_traceback(inet);
    breadth_first_add_source_to_heap(inet);
    mark_ends(inet);

    tptr = NULL;
    remaining_connections_to_sink = 0;

    for(i = 1; i <= net[inet].num_sinks; i++)
	{			/* Need n-1 wires to connect n pins */
	    breadth_first_expand_trace_segment(tptr,
					       remaining_connections_to_sink);
	    current = get_heap_head();

	    if(current == NULL)
		{		/* Infeasible routing.  No possible path for net. */
		    reset_path_costs();	/* Clean up before leaving. */
		    return (FALSE);
		}

	    inode = current->index;

	    while(rr_node_route_inf[inode].target_flag == 0)
		{
		    pcost = rr_node_route_inf[inode].path_cost;
		    new_pcost = current->cost;
		    if(pcost > new_pcost)
			{	/* New path is lowest cost. */
			    rr_node_route_inf[inode].path_cost = new_pcost;
			    prev_node = current->u.prev_node;
			    rr_node_route_inf[inode].prev_node = prev_node;
			    rr_node_route_inf[inode].prev_edge =
				current->prev_edge;

			    if(pcost > 0.99 * HUGE_FLOAT)	/* First time touched. */
				add_to_mod_list(&rr_node_route_inf[inode].
						path_cost);

			    breadth_first_expand_neighbours(inode, new_pcost,
							    inet, bend_cost);
			}

		    free_heap_data(current);
		    current = get_heap_head();

		    if(current == NULL)
			{	/* Impossible routing. No path for net. */
			    reset_path_costs();
			    return (FALSE);
			}

		    inode = current->index;
		}

	    rr_node_route_inf[inode].target_flag--;	/* Connected to this SINK. */
	    remaining_connections_to_sink =
		rr_node_route_inf[inode].target_flag;
	    tptr = update_traceback(current, inet);
	    free_heap_data(current);
	}

    empty_heap();
    reset_path_costs();
    return (TRUE);
}


static void
breadth_first_expand_trace_segment(struct s_trace *start_ptr,
				   int remaining_connections_to_sink)
{

/* Adds all the rr_nodes in the traceback segment starting at tptr (and     *
 * continuing to the end of the traceback) to the heap with a cost of zero. *
 * This allows expansion to begin from the existing wiring.  The            *
 * remaining_connections_to_sink value is 0 if the route segment ending     *
 * at this location is the last one to connect to the SINK ending the route *
 * segment.  This is the usual case.  If it is not the last connection this *
 * net must make to this SINK, I have a hack to ensure the next connection  *
 * to this SINK goes through a different IPIN.  Without this hack, the      *
 * router would always put all the connections from this net to this SINK   *
 * through the same IPIN.  With LUTs or cluster-based logic blocks, you     *
 * should never have a net connecting to two logically-equivalent pins on   *
 * the same logic block, so the hack will never execute.  If your logic     *
 * block is an and-gate, however, nets might connect to two and-inputs on   *
 * the same logic block, and since the and-inputs are logically-equivalent, *
 * this means two connections to the same SINK.                             */

    struct s_trace *tptr, *next_ptr;
    int inode, sink_node, last_ipin_node;

    tptr = start_ptr;

    if(remaining_connections_to_sink == 0)
	{			/* Usual case. */
	    while(tptr != NULL)
		{
		    node_to_heap(tptr->index, 0., NO_PREVIOUS, NO_PREVIOUS,
				 OPEN, OPEN);
		    tptr = tptr->next;
		}
	}

    else
	{			/* This case never executes for most logic blocks. */

/* Weird case.  Lots of hacks. The cleanest way to do this would be to empty *
 * the heap, update the congestion due to the partially-completed route, put *
 * the whole route so far (excluding IPINs and SINKs) on the heap with cost  *
 * 0., and expand till you hit the next SINK.  That would be slow, so I      *
 * do some hacks to enable incremental wavefront expansion instead.          */

	    if(tptr == NULL)
		return;		/* No route yet */

	    next_ptr = tptr->next;
	    last_ipin_node = OPEN;	/* Stops compiler from complaining. */

/* Can't put last SINK on heap with NO_PREVIOUS, etc, since that won't let  *
 * us reach it again.  Instead, leave the last traceback element (SINK) off *
 * the heap.                                                                */

	    while(next_ptr != NULL)
		{
		    inode = tptr->index;
		    node_to_heap(inode, 0., NO_PREVIOUS, NO_PREVIOUS, OPEN,
				 OPEN);

		    if(rr_node[inode].type == IPIN)
			last_ipin_node = inode;

		    tptr = next_ptr;
		    next_ptr = tptr->next;
		}

/* This will stop the IPIN node used to get to this SINK from being         *
 * reexpanded for the remainder of this net's routing.  This will make us   *
 * hook up more IPINs to this SINK (which is what we want).  If IPIN        *
 * doglegs are allowed in the graph, we won't be able to use this IPIN to   *
 * do a dogleg, since it won't be re-expanded.  Shouldn't be a big problem. */

	    rr_node_route_inf[last_ipin_node].path_cost = -HUGE_FLOAT;

/* Also need to mark the SINK as having high cost, so another connection can *
 * be made to it.                                                            */

	    sink_node = tptr->index;
	    rr_node_route_inf[sink_node].path_cost = HUGE_FLOAT;

/* Finally, I need to remove any pending connections to this SINK via the    *
 * IPIN I just used (since they would result in congestion).  Scan through   *
 * the heap to do this.                                                      */

	    invalidate_heap_entries(sink_node, last_ipin_node);
	}
}


static void
breadth_first_expand_neighbours(int inode,
				float pcost,
				int inet,
				float bend_cost)
{

/* Puts all the rr_nodes adjacent to inode on the heap.  rr_nodes outside   *
 * the expanded bounding box specified in route_bb are not added to the     *
 * heap.  pcost is the path_cost to get to inode.                           */

    int iconn, to_node, num_edges;
    t_rr_type from_type, to_type;
    float tot_cost;

    num_edges = rr_node[inode].num_edges;
    for(iconn = 0; iconn < num_edges; iconn++)
	{
	    to_node = rr_node[inode].edges[iconn];

	    if(rr_node[to_node].xhigh < route_bb[inet].xmin ||
	       rr_node[to_node].xlow > route_bb[inet].xmax ||
	       rr_node[to_node].yhigh < route_bb[inet].ymin ||
	       rr_node[to_node].ylow > route_bb[inet].ymax)
		continue;	/* Node is outside (expanded) bounding box. */

	    tot_cost = pcost + get_rr_cong_cost(to_node);

	    if(bend_cost != 0.)
		{
		    from_type = rr_node[inode].type;
		    to_type = rr_node[to_node].type;
		    if((from_type == CHANX && to_type == CHANY) ||
		       (from_type == CHANY && to_type == CHANX))
			tot_cost += bend_cost;
		}

	    node_to_heap(to_node, tot_cost, inode, iconn, OPEN, OPEN);
	}
}


static void
breadth_first_add_source_to_heap(int inet)
{

/* Adds the SOURCE of this net to the heap.  Used to start a net's routing. */

    int inode;
    float cost;

    inode = net_rr_terminals[inet][0];	/* SOURCE */
    cost = get_rr_cong_cost(inode);

    node_to_heap(inode, cost, NO_PREVIOUS, NO_PREVIOUS, OPEN, OPEN);
}