SRC/route_breadth_first.c

Go to the documentation of this file.

#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;

                pres_fac = min (pres_fac, HUGE_FLOAT / 1e5);

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

---