route_export.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_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_delay, t_slack *slacks, t_chan_width_dist chan_width_dist, t_ivec **clb_opins_used_locally, boolean *Fc_clipped, t_direct_inf *directs, int num_directs)
boolean	feasible_routing (void)
t_ivec **	alloc_route_structs (void)
void	free_route_structs ()
struct s_trace **	alloc_saved_routing (t_ivec **clb_opins_used_locally, t_ivec ***saved_clb_opins_used_locally_ptr)
void	free_saved_routing (struct s_trace **best_routing, t_ivec **saved_clb_opins_used_locally)
void	save_routing (struct s_trace **best_routing, t_ivec **clb_opins_used_locally, t_ivec **saved_clb_opins_used_locally)
void	restore_routing (struct s_trace **best_routing, t_ivec **clb_opins_used_locally, t_ivec **saved_clb_opins_used_locally)
void	get_serial_num (void)
void	print_route (char *name)

Function Documentation

t_ivec** alloc_route_structs

(

void

)

Definition at line 611 of file route_common.c.

                          {

    /* Allocates the data structures needed for routing.    */

    t_ivec **clb_opins_used_locally;

    alloc_route_static_structs();
    clb_opins_used_locally = alloc_and_load_clb_opins_used_locally();

    return (clb_opins_used_locally);
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct s_trace** alloc_saved_routing	(	t_ivec **	clb_opins_used_locally,
		t_ivec ***	saved_clb_opins_used_locally_ptr
	)

Definition at line 638 of file route_common.c.

                                                     {

    /* Allocates data structures into which the key routing data can be saved,   *
     * allowing the routing to be recovered later (e.g. after a another routing  *
     * is attempted).                                                            */

    struct s_trace **best_routing;
    t_ivec **saved_clb_opins_used_locally;
    int iblk, iclass, num_local_opins;
    t_type_ptr type;

    best_routing = (struct s_trace **) my_calloc(num_nets,
            sizeof(struct s_trace *));

    saved_clb_opins_used_locally = (t_ivec **) my_malloc(
            num_blocks * sizeof(t_ivec *));

    for (iblk = 0; iblk < num_blocks; iblk++) {
        type = block[iblk].type;
        saved_clb_opins_used_locally[iblk] = (t_ivec *) my_malloc(
                type->num_class * sizeof(t_ivec));
        for (iclass = 0; iclass < type->num_class; iclass++) {
            num_local_opins = clb_opins_used_locally[iblk][iclass].nelem;
            saved_clb_opins_used_locally[iblk][iclass].nelem = num_local_opins;

            if (num_local_opins == 0) {
                saved_clb_opins_used_locally[iblk][iclass].list = NULL;
            } else {
                saved_clb_opins_used_locally[iblk][iclass].list =
                        (int *) my_malloc(num_local_opins * sizeof(int));
            }
        }
    }

    *saved_clb_opins_used_locally_ptr = saved_clb_opins_used_locally;
    return (best_routing);
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean feasible_routing

(

void

)

Definition at line 298 of file route_common.c.

                               {

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

Here is the caller graph for this function:

void free_route_structs

(

)

Definition at line 750 of file route_common.c.

                          {

    /* Frees the temporary storage needed only during the routing.  The  *
     * final routing result is not freed.                                */
    if(heap != NULL) {
        free(heap + 1);
    }
    if(route_bb != NULL) {
        free(route_bb);
    }

    heap = NULL; /* Defensive coding:  crash hard if I use these. */
    route_bb = NULL;

    /*free the memory chunks that were used by heap and linked f pointer */
    free_chunk_memory(&heap_ch);
    free_chunk_memory(&linked_f_pointer_ch);
    heap_free_head = NULL;
    linked_f_pointer_free_head = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void free_saved_routing	(	struct s_trace **	best_routing,
		t_ivec **	saved_clb_opins_used_locally
	)

Definition at line 771 of file route_common.c.

                                                {

    /* Frees the data structures needed to save a routing.                     */
    int i;

    free(best_routing);
    for (i = 0; i < num_blocks; i++) {
        free_ivec_vector(saved_clb_opins_used_locally[i], 0,
                block[i].type->num_class - 1);
    }
    free(saved_clb_opins_used_locally);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void get_serial_num

(

void

)

Definition at line 188 of file route_common.c.

                          {

    /* 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;
        }
    }
    vpr_printf(TIO_MESSAGE_INFO, "Serial number (magic cookie) for the routing is: %d\n", serial_num);
}

Here is the caller graph for this function:

void print_route

(

char *

name

)

Definition at line 1095 of file route_common.c.

                                   {

    /* Prints out the routing to file route_file.  */

    int inet, inode, ipin, bnum, ilow, jlow, node_block_pin, iclass;
    t_rr_type rr_type;
    struct s_trace *tptr;
    const char *name_type[] = { "SOURCE", "SINK", "IPIN", "OPIN", "CHANX", "CHANY",
            "INTRA_CLUSTER_EDGE" };
    FILE *fp;

    fp = fopen(route_file, "w");

    fprintf(fp, "Array size: %d x %d logic blocks.\n", nx, ny);
    fprintf(fp, "\nRouting:");
    for (inet = 0; inet < num_nets; inet++) {
        if (clb_net[inet].is_global == FALSE) {
            if (clb_net[inet].num_sinks == FALSE) {
                fprintf(fp, "\n\nNet %d (%s)\n\n", inet, clb_net[inet].name);
                fprintf(fp, "\n\nUsed in local cluster only, reserved one CLB pin\n\n");
            } else {
                fprintf(fp, "\n\nNet %d (%s)\n\n", inet, clb_net[inet].name);
                tptr = trace_head[inet];

                while (tptr != NULL) {
                    inode = tptr->index;
                    rr_type = rr_node[inode].type;
                    ilow = rr_node[inode].xlow;
                    jlow = rr_node[inode].ylow;

                    fprintf(fp, "Node:\t%d\t%6s (%d,%d) ", inode, name_type[rr_type], ilow, jlow);

                    if ((ilow != rr_node[inode].xhigh)
                            || (jlow != rr_node[inode].yhigh))
                        fprintf(fp, "to (%d,%d) ", rr_node[inode].xhigh,
                                rr_node[inode].yhigh);

                    switch (rr_type) {

                    case IPIN:
                    case OPIN:
                        if (grid[ilow][jlow].type == IO_TYPE) {
                            fprintf(fp, " Pad: ");
                        } else { /* IO Pad. */
                            fprintf(fp, " Pin: ");
                        }
                        break;

                    case CHANX:
                    case CHANY:
                        fprintf(fp, " Track: ");
                        break;

                    case SOURCE:
                    case SINK:
                        if (grid[ilow][jlow].type == IO_TYPE) {
                            fprintf(fp, " Pad: ");
                        } else { /* IO Pad. */
                            fprintf(fp, " Class: ");
                        }
                        break;

                    default:
                        vpr_printf(TIO_MESSAGE_ERROR, "in print_route: Unexpected traceback element type: %d (%s).\n", 
                                rr_type, name_type[rr_type]);
                        exit(1);
                        break;
                    }

                    fprintf(fp, "%d  ", rr_node[inode].ptc_num);

                    /* Uncomment line below if you're debugging and want to see the switch types *
                     * used in the routing.                                                      */
                    /*          fprintf (fp, "Switch: %d", tptr->iswitch);    */

                    fprintf(fp, "\n");

                    tptr = tptr->next;
                }
            }
        }

        else { /* Global net.  Never routed. */
            fprintf(fp, "\n\nNet %d (%s): global net connecting:\n\n", inet,
                    clb_net[inet].name);

            for (ipin = 0; ipin <= clb_net[inet].num_sinks; ipin++) {
                bnum = clb_net[inet].node_block[ipin];

                node_block_pin = clb_net[inet].node_block_pin[ipin];
                iclass = block[bnum].type->pin_class[node_block_pin];

                fprintf(fp, "Block %s (#%d) at (%d, %d), Pin class %d.\n",
                        block[bnum].name, bnum, block[bnum].x, block[bnum].y,
                        iclass);
            }
        }
    }

    fclose(fp);

    if (getEchoEnabled() && isEchoFileEnabled(E_ECHO_MEM)) {
        fp = my_fopen(getEchoFileName(E_ECHO_MEM), "w", 0);
        fprintf(fp, "\nNum_heap_allocated: %d   Num_trace_allocated: %d\n",
                num_heap_allocated, num_trace_allocated);
        fprintf(fp, "Num_linked_f_pointer_allocated: %d\n",
                num_linked_f_pointer_allocated);
        fclose(fp);
    }

}

Here is the call graph for this function:

Here is the caller graph for this function:

void restore_routing	(	struct s_trace **	best_routing,
		t_ivec **	clb_opins_used_locally,
		t_ivec **	saved_clb_opins_used_locally
	)

Definition at line 149 of file route_common.c.

                                                {

    /* 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 = clb_opins_used_locally[iblk][iclass].nelem;
            for (ipin = 0; ipin < num_local_opins; ipin++) {
                clb_opins_used_locally[iblk][iclass].list[ipin] =
                        saved_clb_opins_used_locally[iblk][iclass].list[ipin];
            }
        }

    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void save_routing	(	struct s_trace **	best_routing,
		t_ivec **	clb_opins_used_locally,
		t_ivec **	saved_clb_opins_used_locally
	)

Definition at line 99 of file route_common.c.

                                                {

    /* 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 = clb_opins_used_locally[iblk][iclass].nelem;
            for (ipin = 0; ipin < num_local_opins; ipin++) {
                saved_clb_opins_used_locally[iblk][iclass].list[ipin] =
                        clb_opins_used_locally[iblk][iclass].list[ipin];
            }
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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_delay,
		t_slack *	slacks,
		t_chan_width_dist	chan_width_dist,
		t_ivec **	clb_opins_used_locally,
		boolean *	Fc_clipped,
		t_direct_inf *	directs,
		int	num_directs
	)

Definition at line 220 of file route_common.c.

                                                                      {

    /* 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;
    clock_t begin, end;
    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();

    begin = clock();

    /* 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,
            directs, num_directs, FALSE,
            &tmp);

    end = clock();
#ifdef CLOCKS_PER_SEC
    vpr_printf(TIO_MESSAGE_INFO, "Build rr_graph took %g seconds.\n", (float)(end - begin) / CLOCKS_PER_SEC);
#else
    vpr_printf(TIO_MESSAGE_INFO, "Build rr_graph took %g seconds.\n", (float)(end - begin) / CLK_PER_SEC);
#endif

    /* 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) {
        vpr_printf(TIO_MESSAGE_INFO, "Confirming Router Algorithm: BREADTH_FIRST.\n");
        success = try_breadth_first_route(router_opts, clb_opins_used_locally,
                width_fac);
    } else { /* TIMING_DRIVEN route */
        vpr_printf(TIO_MESSAGE_INFO, "Confirming Router Algorithm: TIMING_DRIVEN.\n");
        assert(router_opts.route_type != GLOBAL);
        success = try_timing_driven_route(router_opts, net_delay, slacks,
            clb_opins_used_locally,timing_inf.timing_analysis_enabled);
    }

    free_rr_node_route_structs();

    return (success);
}

Here is the call graph for this function:

Here is the caller graph for this function: