vpr/SRC/route/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 **clb_opins_used_locally, t_mst_edge **mst, boolean *Fc_clipped) |
| boolean | feasible_routing (void) |
| t_ivec ** | alloc_route_structs () |
| void | free_route_structs (t_ivec **clb_opins_used_locally) |
| 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 | ( | ) |
Allocates the data structures needed for routing.
Definition at line 704 of file route_common.c.
{
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 | ||
| ) | [read] |
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).
Definition at line 734 of file route_common.c.
{
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 | ) |
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.
Definition at line 349 of file route_common.c.
{
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 ** | clb_opins_used_locally | ) |
Frees the temporary storage needed only during the routing. The final routing result is not freed.
Definition at line 858 of file route_common.c.
{
int i;
free(heap + 1);
free(route_bb);
heap = NULL; /* Defensive coding: crash hard if I use these. */
route_bb = NULL;
if(clb_opins_used_locally != NULL) {
for(i = 0; i < num_blocks; i++)
{
free_ivec_vector(clb_opins_used_locally[i], 0,
block[i].type->num_class - 1);
}
free(clb_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:
Frees the data structures needed to save a routing.
Definition at line 886 of file route_common.c.
{
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 | ) |
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.
Definition at line 212 of file route_common.c.
{
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 * | route_file | ) |
Prints out the routing to file route_file.
Definition at line 1293 of file route_common.c.
{
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", "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\n Used 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, "%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, 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);
#ifdef CREATE_ECHO_FILES
fp = my_fopen("mem.echo", "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);
#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 ** | clb_opins_used_locally, | ||
| t_ivec ** | saved_clb_opins_used_locally | ||
| ) |
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.
Definition at line 168 of file route_common.c.
{
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 | ||
| ) |
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.
Definition at line 109 of file route_common.c.
{
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_slack, | ||
| float ** | net_delay, | ||
| t_chan_width_dist | chan_width_dist, | ||
| t_ivec ** | clb_opins_used_locally, | ||
| t_mst_edge ** | mst, | ||
| boolean * | Fc_clipped | ||
| ) |
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.
Definition at line 253 of file route_common.c.
{
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, &tmp);
end = clock();
#ifdef CLOCKS_PER_SEC
printf("build rr_graph took %g seconds\n", (float)(end - begin) / CLOCKS_PER_SEC);
#else
printf("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)
{
printf("Confirming Router Algorithm: BREADTH_FIRST.\n");
success =
try_breadth_first_route(router_opts, clb_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,
clb_opins_used_locally);
}
else
{ /* Directed Search Routability Driven */
printf("Confirming Router Algorithm: DIRECTED_SEARCH.\n");
success =
try_directed_search_route(router_opts, clb_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:
