This graph shows which files directly or indirectly include this file:
Functions
boolean	try_directed_search_route (struct s_router_opts router_opts, t_ivec clb_opins_used_locally, int width_fac, t_mst_edge mst)
Function Documentation

boolean try_directed_search_route	(	struct s_router_opts	router_opts,
		t_ivec **	clb_opins_used_locally,
		int	width_fac,
		t_mst_edge **	mst
	)
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.
Definition at line 57 of file route_directed_search.c.
{

    float pres_fac;
    boolean success, is_routable, rip_up_local_opins;
    int itry, inet, i;
        clock_t begin, end;

    int bends;
    int wirelength, total_wirelength, available_wirelength;
    int segments;

        float *sinks;
        int *net_index;

        sinks = my_malloc(sizeof(float) * num_nets);
        net_index = my_malloc(sizeof(int) * num_nets);
        for(i = 0; i < num_nets; i++) {
                sinks[i] = clb_net[i].num_sinks;
                net_index[i] = i;
        }
        heapsort(net_index, sinks, num_nets, 1);

    /* char msg[100]; */

        begin = clock();

    /* mst not built as good as it should, ideally, just have it after placement once only
         however, rr_node numbers changed when the channel width changes so forced to do it here */
    if(mst)
        {
            for(inet = 0; inet < num_nets; inet++)
                {
                        free(mst[inet]);
                    mst[inet] = get_mst_of_net(inet);
                }
        }

        end = clock();
        #ifdef CLOCKS_PER_SEC
                printf("mst took %g seconds\n", (float)(end - begin) / CLOCKS_PER_SEC);
        #else
                printf("mst took %g seconds\n", (float)(end - begin) / CLK_PER_SEC);
        #endif


/* 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++)
        {
                                        begin = clock();

                printf("routing iteration %d\n", itry);
                for(i = 0; i < num_nets; i++)
                {
                        inet = net_index[i];
                if(clb_net[inet].is_global == FALSE && clb_net[inet].num_sinks != 0)
                        {       /* Skip global nets and empty nets (empty nets are already reserved using reserve_locally_used_opins). */
                            is_routable =
                                directed_search_route_net(inet, pres_fac,
                                                          router_opts.
                                                          astar_fac,
                                                          router_opts.
                                                          bend_cost, mst);

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

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

                        }
                }
                end = clock();
                #ifdef CLOCKS_PER_SEC
                        printf("routing iteration took %g seconds\n", (float)(end - begin) / CLOCKS_PER_SEC);
                #else
                        printf("routing iteration took %g seconds\n", (float)(end - begin) / CLK_PER_SEC);
                #endif
                fflush(stdout);

                if(itry == 1) {
                        /* Early exit code for cases where it is obvious that a successful route will not be found 
                           Heuristic: If total wirelength used in first routing iteration is X% of total available wirelength, exit
                        */
                        total_wirelength = 0;
                        available_wirelength = 0;

                        for(i = 0; i < num_rr_nodes; i++) {
                                if(rr_node[i].type == CHANX || rr_node[i].type == CHANY)
                                {
                                        available_wirelength += 1 + rr_node[i].xhigh - rr_node[i].xlow +
                                        rr_node[i].yhigh - rr_node[i].ylow;
                                }
                        }

                        for(inet = 0; inet < num_nets; inet++)
                        {
                                if(clb_net[inet].is_global == FALSE && clb_net[inet].num_sinks != 0)
                                {               /* Globals don't count. */
                                        get_num_bends_and_length(inet, &bends, &wirelength,
                                                                 &segments);

                                        total_wirelength += wirelength;
                                }
                        }
                        printf("wirelength after first iteration %d, total available wirelength %d, ratio %g\n", total_wirelength, available_wirelength, (float)(total_wirelength)/(float)(available_wirelength));
                        if((float)(total_wirelength)/(float)(available_wirelength) > FIRST_ITER_WIRELENTH_LIMIT) {
                                printf("Wirelength usage ratio exceeds limit of %g, fail routing\n", FIRST_ITER_WIRELENTH_LIMIT);
                                free(net_index);
                                free(sinks);
                                return FALSE;
                        }
                }


            /* 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)
                {
                    printf
                        ("Successfully routed after %d routing iterations by Directed Search.\n",
                         itry);
                        free(net_index);
                        free(sinks);
                    return (TRUE);
                }
#if 0
            else
                {
                    sprintf(msg,
                            "After iteration %d routing failed (A*) with a channel width factor of %d and Fc_int of %d, Fs_int of %d.",
                            itry, width_fac, Fc_int, Fs_int);
                    init_draw_coords(pins_per_clb);
                    update_screen(MAJOR, msg, ROUTING, FALSE);
                }
#endif


            if(itry == 1)
                {
                    pres_fac = router_opts.initial_pres_fac;
                    pathfinder_update_cost(pres_fac, 0.);       /* Acc_fac=0 for first iter. */
                }
            else
                {
                    pres_fac *= router_opts.pres_fac_mult;
                    pathfinder_update_cost(pres_fac, router_opts.acc_fac);
                }

        }

    printf("Routing failed.\n");
        free(sinks);
        free(net_index);

    return (FALSE);
}
Here is the call graph for this function:
Here is the caller graph for this function:
vpr/SRC/route/route_directed_search.h File Reference

Functions

Function Documentation
