vpr/SRC/route/route_timing.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_timing_driven_route (struct s_router_opts router_opts, float **net_slack, float **net_delay, t_ivec **clb_opins_used_locally) |
| boolean | timing_driven_route_net (int inet, float pres_fac, float max_criticality, float criticality_exp, float astar_fac, float bend_cost, float *net_slack, float *pin_criticality, int *sink_order, t_rt_node **rt_node_of_sink, float T_crit, float *net_delay) |
| void | alloc_timing_driven_route_structs (float **pin_criticality_ptr, int **sink_order_ptr, t_rt_node ***rt_node_of_sink_ptr) |
| void | free_timing_driven_route_structs (float *pin_criticality, int *sink_order, t_rt_node **rt_node_of_sink) |
Function Documentation
| void alloc_timing_driven_route_structs | ( | float ** | pin_criticality_ptr, |
| int ** | sink_order_ptr, | ||
| t_rt_node *** | rt_node_of_sink_ptr | ||
| ) |
Allocates all the structures needed only by the timing-driven router.
Definition at line 252 of file route_timing.c.
{
int max_pins_per_net;
float *pin_criticality;
int *sink_order;
t_rt_node **rt_node_of_sink;
max_pins_per_net = get_max_pins_per_net();
pin_criticality =
(float *)my_malloc((max_pins_per_net - 1) * sizeof(float));
*pin_criticality_ptr = pin_criticality - 1; /* First sink is pin #1. */
sink_order = (int *)my_malloc((max_pins_per_net - 1) * sizeof(int));
*sink_order_ptr = sink_order - 1;
rt_node_of_sink = (t_rt_node **) my_malloc((max_pins_per_net - 1) *
sizeof(t_rt_node *));
*rt_node_of_sink_ptr = rt_node_of_sink - 1;
alloc_route_tree_timing_structs();
}
Here is the call graph for this function:
Here is the caller graph for this function:
| void free_timing_driven_route_structs | ( | float * | pin_criticality, |
| int * | sink_order, | ||
| t_rt_node ** | rt_node_of_sink | ||
| ) |
Frees all the stuctures needed only by the timing-driven router.
Definition at line 280 of file route_timing.c.
{
free(pin_criticality + 1); /* Starts at index 1. */
free(sink_order + 1);
free(rt_node_of_sink + 1);
free_route_tree_timing_structs();
}
Here is the call graph for this function:
Here is the caller graph for this function:
| boolean timing_driven_route_net | ( | int | inet, |
| float | pres_fac, | ||
| float | max_criticality, | ||
| float | criticality_exp, | ||
| float | astar_fac, | ||
| float | bend_cost, | ||
| float * | net_slack, | ||
| float * | pin_criticality, | ||
| int * | sink_order, | ||
| t_rt_node ** | rt_node_of_sink, | ||
| float | T_crit, | ||
| float * | net_delay | ||
| ) |
Returns TRUE as long is found some way to hook up this net, even if that way resulted in overuse of resources (congestion). If there is no way to route this net, even ignoring congestion, it returns FALSE. In this case the rr_graph is disconnected and you can give up.
Definition at line 316 of file route_timing.c.
{
int ipin, num_sinks, itarget, target_pin, target_node, inode;
float target_criticality, old_tcost, new_tcost, largest_criticality,
pin_crit;
float old_back_cost, new_back_cost;
t_rt_node *rt_root;
struct s_heap *current;
struct s_trace *new_route_start_tptr;
int highfanout_rlim;
/* Rip-up any old routing. */
pathfinder_update_one_cost(trace_head[inet], -1, pres_fac);
free_traceback(inet);
for(ipin = 1; ipin <= clb_net[inet].num_sinks; ipin++)
{ /* For all sinks */
pin_crit = max(max_criticality - net_slack[ipin] / T_crit, 0.);
pin_crit = pow(pin_crit, criticality_exp);
pin_crit = min(pin_crit, max_criticality);
pin_criticality[ipin] = pin_crit;
}
num_sinks = clb_net[inet].num_sinks;
heapsort(sink_order, pin_criticality, num_sinks, 0);
/* Update base costs according to fanout and criticality rules */
largest_criticality = pin_criticality[sink_order[1]];
update_rr_base_costs(inet, largest_criticality);
mark_ends(inet); /* Only needed to check for multiply-connected SINKs */
rt_root = init_route_tree_to_source(inet);
for(itarget = 1; itarget <= num_sinks; itarget++)
{
target_pin = sink_order[itarget];
target_node = net_rr_terminals[inet][target_pin];
target_criticality = pin_criticality[target_pin];
highfanout_rlim = mark_node_expansion_by_bin(inet, target_node, rt_root);
add_route_tree_to_heap(rt_root, target_node, target_criticality,
astar_fac);
current = get_heap_head();
if(current == NULL)
{ /* Infeasible routing. No possible path for net. */
reset_path_costs();
free_route_tree(rt_root);
return (FALSE);
}
inode = current->index;
while(inode != target_node)
{
old_tcost = rr_node_route_inf[inode].path_cost;
new_tcost = current->cost;
if(old_tcost > 0.99 * HUGE_FLOAT) /* First time touched. */
old_back_cost = HUGE_FLOAT;
else
old_back_cost =
rr_node_route_inf[inode].backward_path_cost;
new_back_cost = current->backward_path_cost;
/* I only re-expand a node if both the "known" backward cost is lower *
* in the new expansion (this is necessary to prevent loops from *
* forming in the routing and causing havoc) *and* the expected total *
* cost to the sink is lower than the old value. Different R_upstream *
* values could make a path with lower back_path_cost less desirable *
* than one with higher cost. Test whether or not I should disallow *
* re-expansion based on a higher total cost. */
if(old_tcost > new_tcost && old_back_cost > new_back_cost)
{
rr_node_route_inf[inode].prev_node =
current->u.prev_node;
rr_node_route_inf[inode].prev_edge =
current->prev_edge;
rr_node_route_inf[inode].path_cost = new_tcost;
rr_node_route_inf[inode].backward_path_cost =
new_back_cost;
if(old_tcost > 0.99 * HUGE_FLOAT) /* First time touched. */
add_to_mod_list(&rr_node_route_inf[inode].
path_cost);
timing_driven_expand_neighbours(current, inet,
bend_cost,
target_criticality,
target_node,
astar_fac,
highfanout_rlim);
}
free_heap_data(current);
current = get_heap_head();
if(current == NULL)
{ /* Impossible routing. No path for net. */
reset_path_costs();
free_route_tree(rt_root);
return (FALSE);
}
inode = current->index;
}
/* NB: In the code below I keep two records of the partial routing: the *
* traceback and the route_tree. The route_tree enables fast recomputation *
* of the Elmore delay to each node in the partial routing. The traceback *
* lets me reuse all the routines written for breadth-first routing, which *
* all take a traceback structure as input. Before this routine exits the *
* route_tree structure is destroyed; only the traceback is needed at that *
* point. */
rr_node_route_inf[inode].target_flag--; /* Connected to this SINK. */
new_route_start_tptr = update_traceback(current, inet);
rt_node_of_sink[target_pin] = update_route_tree(current);
free_heap_data(current);
pathfinder_update_one_cost(new_route_start_tptr, 1, pres_fac);
empty_heap();
reset_path_costs();
}
/* For later timing analysis. */
update_net_delays_from_route_tree(net_delay, rt_node_of_sink, inet);
free_route_tree(rt_root);
return (TRUE);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| boolean try_timing_driven_route | ( | struct s_router_opts | router_opts, |
| float ** | net_slack, | ||
| float ** | net_delay, | ||
| t_ivec ** | clb_opins_used_locally | ||
| ) |
Definition at line 57 of file route_timing.c.
{
int itry, inet, ipin, i;
boolean success, is_routable, rip_up_local_opins;
float *pin_criticality; /* [1..max_pins_per_net-1]. */
int *sink_order; /* [1..max_pins_per_net-1]. */
t_rt_node **rt_node_of_sink; /* [1..max_pins_per_net-1]. */
float T_crit, pres_fac;
float *sinks;
int *net_index;
int bends;
int wirelength, total_wirelength, available_wirelength;
int segments;
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);
alloc_timing_driven_route_structs(&pin_criticality, &sink_order,
&rt_node_of_sink);
/* First do one routing iteration ignoring congestion and marking all sinks *
* on each net as critical to get reasonable net delay estimates. */
for(inet = 0; inet < num_nets; inet++)
{
if(clb_net[inet].is_global == FALSE)
{
for(ipin = 1; ipin <= clb_net[inet].num_sinks; ipin++)
net_slack[inet][ipin] = 0.;
}
else
{ /* Set delay of global signals to zero. */
for(ipin = 1; ipin <= clb_net[inet].num_sinks; ipin++)
net_delay[inet][ipin] = 0.;
}
}
T_crit = 1.;
pres_fac = router_opts.first_iter_pres_fac; /* Typically 0 -> ignore cong. */
for(itry = 1; itry <= router_opts.max_router_iterations; itry++)
{
for(i = 0; i < num_nets; i++)
{
inet = net_index[i];
if(clb_net[inet].is_global == FALSE)
{ /* Skip global nets. */
is_routable =
timing_driven_route_net(inet, pres_fac,
router_opts.
max_criticality,
router_opts.
criticality_exp,
router_opts.astar_fac,
router_opts.bend_cost,
net_slack[inet],
pin_criticality,
sink_order,
rt_node_of_sink,
T_crit,
net_delay[inet]);
/* Impossible to route? (disconnected rr_graph) */
if(!is_routable)
{
printf("Routing failed.\n");
free_timing_driven_route_structs
(pin_criticality, sink_order,
rt_node_of_sink);
free(net_index);
free(sinks);
return (FALSE);
}
}
}
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_timing_driven_route_structs
(pin_criticality, sink_order,
rt_node_of_sink);
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);
/* Pathfinder guys quit after finding a feasible route. I may want to keep *
* going longer, trying to improve timing. Think about this some. */
success = feasible_routing();
if(success)
{
printf
("Successfully routed after %d routing iterations.\n",
itry);
free_timing_driven_route_structs(pin_criticality,
sink_order,
rt_node_of_sink);
#ifdef DEBUG
timing_driven_check_net_delays(net_delay);
#endif
free(net_index);
free(sinks);
return (TRUE);
}
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;
/* Avoid overflow for high iteration counts, even if acc_cost is big */
pres_fac = min (pres_fac, HUGE_FLOAT / 1e5);
pathfinder_update_cost(pres_fac, router_opts.acc_fac);
}
/* Update slack values by doing another timing analysis. *
* Timing_driven_route_net updated the net delay values. */
load_timing_graph_net_delays(net_delay);
T_crit = load_net_slack(net_slack, 0);
printf("T_crit: %g.\n", T_crit);
fflush(stdout);
}
printf("Routing failed.\n");
free_timing_driven_route_structs(pin_criticality, sink_order,
rt_node_of_sink);
free(net_index);
free(sinks);
return (FALSE);
}
Here is the call graph for this function:
Here is the caller graph for this function:
