SRC/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_slack, float **net_delay, t_chan_width_dist chan_width_dist, t_ivec **fb_opins_used_locally, t_mst_edge **mst, boolean *Fc_clipped)
boolean	feasible_routing (void)
t_ivec **	alloc_route_structs (t_subblock_data subblock_data)
void	free_route_structs (t_ivec **fb_opins_used_locally)
struct s_trace **	alloc_saved_routing (t_ivec **fb_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 **fb_opins_used_locally, t_ivec **saved_clb_opins_used_locally)
void	restore_routing (struct s_trace **best_routing, t_ivec **fb_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

(

t_subblock_data

subblock_data

)

Definition at line 703 of file route_common.c.

{

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

    t_ivec **fb_opins_used_locally;

    trace_head = (struct s_trace **)my_calloc(num_nets,
                                              sizeof(struct s_trace *));
    trace_tail = (struct s_trace **)my_malloc(num_nets *
                                              sizeof(struct s_trace *));

    heap_size = nx * ny;
    heap = (struct s_heap **)my_malloc(heap_size * sizeof(struct s_heap *));
    heap--;                     /* heap stores from [1..heap_size] */
    heap_tail = 1;

    route_bb = (struct s_bb *)my_malloc(num_nets * sizeof(struct s_bb));

    fb_opins_used_locally =
        alloc_and_load_clb_opins_used_locally(subblock_data);

    return (fb_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 **	fb_opins_used_locally,
		t_ivec ***	saved_clb_opins_used_locally_ptr
	)			[read]

Definition at line 730 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 =
                        fb_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 337 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

(

t_ivec **

fb_opins_used_locally

)

Definition at line 864 of file route_common.c.

{

/* Frees the temporary storage needed only during the routing.  The  *
 * final routing result is not freed.                                */
    int i;

    free(heap + 1);
    free(route_bb);

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

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

/* NB:  Should use my chunk_malloc for tptr, hptr, and mod_ptr structures. *
 * I could free everything except the tptrs at the end then.               */

}

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 891 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 210 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;
                }
        }
    printf("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 1288 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;
    char *name_type[] =
        { "SOURCE", "SINK", "IPIN", "OPIN", "CHANX", "CHANY" };
    FILE *fp;

    fp = my_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(net[inet].is_global == FALSE)
                {
                    fprintf(fp, "\n\nNet %d (%s)\n\n", inet, 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, "%6s (%d,%d) ", 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:
                                    printf
                                        ("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, net[inet].name);

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

                            node_block_pin = 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);

#ifdef CREATE_ECHO_FILES
    fp = my_fopen("mem.echo", "w");
    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);
#endif /* CREATE_ECHO_FILES */

}

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 **	fb_opins_used_locally,
		t_ivec **	saved_clb_opins_used_locally
	)

Definition at line 162 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 =
                        fb_opins_used_locally[iblk][iclass].nelem;
                    for(ipin = 0; ipin < num_local_opins; ipin++)
                        {
                            fb_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 **	fb_opins_used_locally,
		t_ivec **	saved_clb_opins_used_locally
	)

Definition at line 101 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 =
                        fb_opins_used_locally[iblk][iclass].nelem;
                    for(ipin = 0; ipin < num_local_opins; ipin++)
                        {
                            saved_clb_opins_used_locally[iblk][iclass].
                                list[ipin] =
                                fb_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_slack,
		float **	net_delay,
		t_chan_width_dist	chan_width_dist,
		t_ivec **	fb_opins_used_locally,
		t_mst_edge **	mst,
		boolean *	Fc_clipped
	)

Definition at line 249 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;
    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();

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

/* 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)
        {
            printf("Confirming Router Algorithm: BREADTH_FIRST.\n");
            success =
                try_breadth_first_route(router_opts, fb_opins_used_locally,
                                        width_fac);
        }
    else if(router_opts.router_algorithm == TIMING_DRIVEN)
        {                       /* TIMING_DRIVEN route */
            printf("Confirming Router Algorithm: TIMING_DRIVEN.\n");
            assert(router_opts.route_type != GLOBAL);
            success =
                try_timing_driven_route(router_opts, net_slack, net_delay,
                                        fb_opins_used_locally);
        }
    else
        {                       /* Directed Search Routability Driven */
            printf("Confirming Router Algorithm: DIRECTED_SEARCH.\n");
            success =
                try_directed_search_route(router_opts, fb_opins_used_locally,
                                          width_fac, mst);
        }

    free_rr_node_route_structs();

    return (success);
}

Here is the call graph for this function:

Here is the caller graph for this function: