route_breadth_first.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
boolean	try_breadth_first_route (struct s_router_opts router_opts, t_ivec **clb_opins_used_locally, int width_fac)

Function Documentation

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

Definition at line 23 of file route_breadth_first.c.

                                                         {

    /* 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 (clb_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) {
                    vpr_printf(TIO_MESSAGE_INFO, "Routing failed.\n");
                    return (FALSE);
                }

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

            }
        }

        /* Make sure any CLB 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,
                clb_opins_used_locally);

        success = feasible_routing();
        if (success) {
            vpr_printf(TIO_MESSAGE_INFO, "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 = std::min(pres_fac, static_cast<float>(HUGE_POSITIVE_FLOAT / 1e5));

        pathfinder_update_cost(pres_fac, router_opts.acc_fac);
    }

    vpr_printf(TIO_MESSAGE_INFO, "Routing failed.\n");
    return (FALSE);
}

Here is the call graph for this function:

Here is the caller graph for this function: