vpr: added set to heap node data structure which keeps track of path excluding the starting point from the route tree to the route tree node being added
diff --git a/vpr/src/route/route_budgets.cpp b/vpr/src/route/route_budgets.cpp
index a2387b5..fd1366c 100644
--- a/vpr/src/route/route_budgets.cpp
+++ b/vpr/src/route/route_budgets.cpp
@@ -140,9 +140,9 @@
for (auto net_id : cluster_ctx.clb_nlist.nets()) {
for (auto pin_id : cluster_ctx.clb_nlist.net_sinks(net_id)) {
int ipin = cluster_ctx.clb_nlist.pin_net_index(pin_id);
- //cap max budget to be bigger or equal than min budget
- if (delay_max_budget[net_id][ipin] < delay_min_budget[net_id][ipin])
- delay_max_budget[net_id][ipin] = delay_min_budget[net_id][ipin];
+ //cap max budget to be bigger or equal than min budget
+ if (delay_max_budget[net_id][ipin] < delay_min_budget[net_id][ipin])
+ delay_max_budget[net_id][ipin] = delay_min_budget[net_id][ipin];
calculate_delay_targets(net_id, pin_id);
}
}
@@ -171,8 +171,8 @@
/*Preprocessing algorithm in order to consider short paths when setting initial maximum budgets.
* Not necessary unless budgets are really hard to meet*/
- if ( negative_hold_slack ) {
- process_negative_slack_using_minimax(net_delay, netlist_pin_lookup);
+ if (negative_hold_slack) {
+ process_negative_slack_using_minimax(net_delay, netlist_pin_lookup);
}
iteration = 0;
max_budget_change = 900e-12;
@@ -200,14 +200,14 @@
max_budget_change = 900e-12;
/*Allocate the short path slack to decrease the budgets accordingly*/
- while ((iteration > 3 && max_budget_change > 5e-12) || iteration <= 3) {
+ while ((iteration > 3 && max_budget_change > 5e-12) || iteration <= 3) {
max_budget_change = minimax_PERT(original_timing_info, timing_info_min, delay_min_budget, net_delay, netlist_pin_lookup, HOLD, true, POSITIVE);
timing_info_min = perform_sta(delay_min_budget);
iteration++;
if (iteration > 20)
break;
- }
+ }
/*Post basic algorithm processing
*This prevents wasting resources by allowing the minimum budgets to go below
@@ -244,12 +244,10 @@
float second_max_budget_change = 900e-12;
original_timing_info = perform_sta(net_delay);
-
while (iteration < 20 && max_budget_change > 5e-12) {
if (iteration == 0) {
max_budget_change = minimax_PERT(original_timing_info, original_timing_info, delay_max_budget, net_delay, netlist_pin_lookup, HOLD, true, NEGATIVE);
timing_info = perform_sta(delay_max_budget);
-
} else {
max_budget_change = minimax_PERT(original_timing_info, timing_info, delay_max_budget, net_delay, netlist_pin_lookup, HOLD, true, NEGATIVE);
@@ -314,9 +312,7 @@
}
}
-float route_budgets::minimax_PERT(std::shared_ptr<SetupHoldTimingInfo> orig_timing_info, std::shared_ptr<SetupHoldTimingInfo> timing_info, vtr::vector<ClusterNetId, float *> &temp_budgets,
- vtr::vector<ClusterNetId, float *> &net_delay, const ClusteredPinAtomPinsLookup& netlist_pin_lookup, analysis_type analysis_type,
- bool keep_in_bounds, slack_allocated_type slack_type) {
+float route_budgets::minimax_PERT(std::shared_ptr<SetupHoldTimingInfo> orig_timing_info, std::shared_ptr<SetupHoldTimingInfo> timing_info, vtr::vector<ClusterNetId, float*>& temp_budgets, vtr::vector<ClusterNetId, float*>& net_delay, const ClusteredPinAtomPinsLookup& netlist_pin_lookup, analysis_type analysis_type, bool keep_in_bounds, slack_allocated_type slack_type) {
/*This function uses weights to calculate how much slack to allocate to a connection.
* The weights are deteremined by how much delay of the whole path is present in this connection*/
@@ -325,7 +321,6 @@
auto& device_ctx = g_vpr_ctx.device();
std::shared_ptr<const tatum::SetupHoldTimingAnalyzer> timing_analyzer = orig_timing_info->setup_hold_analyzer();
-
float total_path_delay = 0;
float path_slack;
@@ -340,19 +335,19 @@
if (analysis_type == HOLD) {
path_slack = calculate_clb_pin_slack(net_id, ipin, timing_info, netlist_pin_lookup, HOLD, atom_pin);
if (path_slack > 0) {
- path_slack = path_slack *0.90 - 300e-12;
+ path_slack = path_slack * 0.90 - 300e-12;
} else {
- path_slack = path_slack - 100e-12;
- }
+ path_slack = path_slack - 100e-12;
+ }
hold_path_slack = path_slack;
} else {
path_slack = calculate_clb_pin_slack(net_id, ipin, timing_info, netlist_pin_lookup, SETUP, atom_pin);
hold_path_slack = calculate_clb_pin_slack(net_id, ipin, orig_timing_info, netlist_pin_lookup, HOLD, atom_pin);
- if (hold_path_slack > 0) {
- hold_path_slack = hold_path_slack *0.90 - 300e-12;
+ if (hold_path_slack > 0) {
+ hold_path_slack = hold_path_slack * 0.90 - 300e-12;
} else {
- hold_path_slack = hold_path_slack - 100e-12;
- }
+ hold_path_slack = hold_path_slack - 100e-12;
+ }
}
tatum::NodeId timing_node = atom_ctx.lookup.atom_pin_tnode(atom_pin);
@@ -365,13 +360,13 @@
/*During hold analysis, increase the budgets when there is negative slack.
* During setup analysis, decrease the budgets when there is negative slack*/
if ((slack_type == NEGATIVE && path_slack < 0) || (slack_type == POSITIVE && path_slack > 0) || slack_type == BOTH) {
- if (analysis_type == HOLD ) {
+ if (analysis_type == HOLD) {
temp_budgets[net_id][ipin] += -1 * net_delay[net_id][ipin] * (path_slack) / total_path_delay;
max_budget_change = max(max_budget_change, (float)abs(net_delay[net_id][ipin] * (path_slack) / total_path_delay));
} else {
if ((slack_type == POSITIVE) || (hold_path_slack > 0)) {
/* prevents oscillation behaviour when allocating both negative hold and setup slack on the same net */
- temp_budgets[net_id][ipin] += net_delay[net_id][ipin] * (path_slack) / total_path_delay;
+ temp_budgets[net_id][ipin] += net_delay[net_id][ipin] * (path_slack) / total_path_delay;
max_budget_change = max(max_budget_change, (float)abs(net_delay[net_id][ipin] * (path_slack / total_path_delay)));
}
}
@@ -382,11 +377,9 @@
keep_budget_in_bounds(temp_budgets, net_id, pin_id);
}
-
if (slack_type == NEGATIVE && path_slack < 0 && analysis_type == HOLD || hold_path_slack < 0) {
should_reroute_for_hold[net_id] = true;
}
-
}
}
return max_budget_change;
@@ -750,7 +743,6 @@
return (set && should_reroute_for_hold[net_id]);
}
-
void route_budgets::set_should_reroute(ClusterNetId net_id, bool value) {
/*Returns if the budgets have been loaded yet*/
if (set) {
diff --git a/vpr/src/route/route_budgets.h b/vpr/src/route/route_budgets.h
index a3cd44c..a119b8a 100644
--- a/vpr/src/route/route_budgets.h
+++ b/vpr/src/route/route_budgets.h
@@ -51,10 +51,10 @@
void lower_budgets(float delay_decrement);
void not_congested_this_iteration(ClusterNetId net_id);
- bool get_should_reroute(ClusterNetId net_id) ;
+ bool get_should_reroute(ClusterNetId net_id);
void set_should_reroute(ClusterNetId net_id, bool value);
- int get_hold_fac(ClusterNetId net_id) ;
- void set_hold_fac(ClusterNetId net_id, int value) ;
+ int get_hold_fac(ClusterNetId net_id);
+ void set_hold_fac(ClusterNetId net_id, int value);
private:
/*For allocating and freeing memory*/
@@ -70,10 +70,8 @@
void allocate_slack_using_weights(vtr::vector<ClusterNetId, float*>& net_delay, const ClusteredPinAtomPinsLookup& netlist_pin_lookup, bool negative_hold_slack);
/*Sometimes want to allocate only positive or negative slack.
* By default, allocate both*/
-
- float minimax_PERT(std::shared_ptr<SetupHoldTimingInfo> orig_timing_info, std::shared_ptr<SetupHoldTimingInfo> timing_info, vtr::vector<ClusterNetId, float *> &temp_budgets,
- vtr::vector<ClusterNetId, float *> &net_delay, const ClusteredPinAtomPinsLookup& netlist_pin_lookup, analysis_type analysis_type,
- bool keep_in_bounds, slack_allocated_type slack_type = BOTH);
+
+ float minimax_PERT(std::shared_ptr<SetupHoldTimingInfo> orig_timing_info, std::shared_ptr<SetupHoldTimingInfo> timing_info, vtr::vector<ClusterNetId, float*>& temp_budgets, vtr::vector<ClusterNetId, float*>& net_delay, const ClusteredPinAtomPinsLookup& netlist_pin_lookup, analysis_type analysis_type, bool keep_in_bounds, slack_allocated_type slack_type = BOTH);
void process_negative_slack_using_minimax(vtr::vector<ClusterNetId, float*>& net_delay, const ClusteredPinAtomPinsLookup& netlist_pin_lookup);
/*Perform static timing analysis*/
diff --git a/vpr/src/route/route_common.cpp b/vpr/src/route/route_common.cpp
index 917c0dc..d57fc8e 100644
--- a/vpr/src/route/route_common.cpp
+++ b/vpr/src/route/route_common.cpp
@@ -1264,13 +1264,10 @@
hptr->R_upstream = R_upstream;
push_back(hptr);
}
-
-void push_back_node_with_info(int inode, float total_cost, int prev_node, int prev_edge,
- float backward_path_cost, float R_upstream, float backward_path_delay, std::vector<int> path, std::set<int> net_rr) {
-
+void push_back_node_with_info(int inode, float total_cost, int prev_node, int prev_edge, float backward_path_cost, float R_upstream, float backward_path_delay, std::set<int> net_rr) {
/* Puts an rr_node on the heap with the same condition as node_to_heap,
- but do not fix heap property yet as that is more efficiently done from
- bottom up with build_heap. Certain information is also added */
+ * but do not fix heap property yet as that is more efficiently done from
+ * bottom up with build_heap. Certain information is also added */
auto& route_ctx = g_vpr_ctx.routing();
if (total_cost >= route_ctx.rr_node_route_inf[inode].path_cost)
@@ -1285,7 +1282,7 @@
hptr->edge.clear();
hptr->net_rr = net_rr;
hptr->backward_delay = backward_path_delay;
- hptr->backward_cong = 0;
+ hptr->backward_cong = 0;
push_back(hptr);
}
@@ -1410,8 +1407,9 @@
temp_ptr->R_upstream = 0.;
temp_ptr->index = OPEN;
temp_ptr->path_rr.clear();
- temp_ptr->net_rr.clear();
temp_ptr->edge.clear();
+ temp_ptr->net_rr.clear();
+ temp_ptr->partial_path_nodes.clear();
temp_ptr->u.prev.node = NO_PREVIOUS;
temp_ptr->u.prev.edge = NO_PREVIOUS;
return (temp_ptr);
@@ -1594,14 +1592,14 @@
route_ctx.routing_id = vtr::secure_digest_file(route_file);
}
-//To ensure the router can only swaps pin which are actually logically equivalent some block output pins must be
+//To ensure the router can only swap pins which are actually logically equivalent, some block output pins must be
//reserved in certain cases.
//
// In the RR graph, output pin equivalence is modelled by a single SRC node connected to (multiple) OPINs, modelling
// that each of the OPINs is logcially equivalent (i.e. it doesn't matter through which the router routes a signal,
// so long as it is from the appropriate SRC).
//
-// This correctly models 'full' equivalence (e.g. if there is a full crossbar between the outputs), but is to
+// This correctly models 'full' equivalence (e.g. if there is a full crossbar between the outputs), but is too
// optimistic for 'instance' equivalence (which typcially models the pin equivalence possible by swapping sub-block
// instances like BLEs). In particular, for the 'instance' equivalence case, some of the 'equivalent' block outputs
// may be used by internal signals which are routed entirely *within* the block (i.e. the signals which never leave
@@ -1648,7 +1646,7 @@
VTR_ASSERT(type->class_inf[iclass].equivalence == PortEquivalence::INSTANCE);
//From the SRC node we walk through it's out going edges to collect the
- //OPIN nodes. We then push them onto a heap so the the OPINs with lower
+ //OPIN nodes. We then push them onto a heap so the OPINs with lower
//congestion cost are popped-off/reserved first. (Intuitively, we want
//the reserved OPINs to move out of the way of congestion, by preferring
//to reserve OPINs with lower congestion costs).
diff --git a/vpr/src/route/route_common.h b/vpr/src/route/route_common.h
index 80f54d4..d96df08 100644
--- a/vpr/src/route/route_common.h
+++ b/vpr/src/route/route_common.h
@@ -36,6 +36,8 @@
* edge: A list of edges from each node in the partial path to reach the next node
*
* net_rr: The entire route tree
+ *
+ * partial_path_nodes: The entire partial path up until the route tree, stored as a set.
*
* backward_delay: The delay of the partial path plus the path from route tree to source
*
@@ -47,11 +49,12 @@
float R_upstream = 0.;
int index = OPEN;
- std::vector<int> path_rr;
- std::vector<int> edge;
- std::set<int> net_rr;
- float backward_delay = 0.;
- float backward_cong = 0.;
+ std::vector<int> path_rr;
+ std::vector<int> edge;
+ std::set<int> net_rr;
+ std::set<int> partial_path_nodes;
+ float backward_delay = 0.;
+ float backward_cong = 0.;
struct t_prev {
int node;
@@ -103,7 +106,7 @@
void sift_up(size_t tail, t_heap* const hptr);
void push_back(t_heap* const hptr);
void push_back_node(int inode, float total_cost, int prev_node, int prev_edge, float backward_path_cost, float R_upstream);
-void push_back_node_with_info(int inode, float total_cost, int prev_node, int prev_edge, float backward_path_cost, float R_upstream, float backward_path_delay, std::vector<int> path, std::set<int> net_rr);
+void push_back_node_with_info(int inode, float total_cost, int prev_node, int prev_edge, float backward_path_cost, float R_upstream, float backward_path_delay, std::set<int> net_rr);
bool is_valid();
void pop_heap();
void print_heap();
diff --git a/vpr/src/route/route_timing.cpp b/vpr/src/route/route_timing.cpp
index 6a74148..441c8c9 100644
--- a/vpr/src/route/route_timing.cpp
+++ b/vpr/src/route/route_timing.cpp
@@ -146,7 +146,7 @@
const RouterLookahead& router_lookahead,
SpatialRouteTreeLookup& spatial_rt_lookup,
RouterStats& router_stats,
- route_budgets &budgeting_inf,
+ route_budgets& budgeting_inf,
std::set<int>& route_tree_nodes);
static t_heap* timing_driven_route_connection_from_route_tree_high_fanout(t_rt_node* rt_root,
@@ -289,8 +289,7 @@
static void enable_router_debug(const t_router_opts& router_opts, ClusterNetId net, int sink_rr);
-static bool is_iteration_complete(bool routing_is_feasible, const t_router_opts& router_opts,
- int itry, std::shared_ptr<const SetupHoldTimingInfo> timing_info);
+static bool is_iteration_complete(bool routing_is_feasible, const t_router_opts& router_opts, int itry, std::shared_ptr<const SetupHoldTimingInfo> timing_info);
static bool should_setup_lower_bound_connection_delays(int itry, const t_router_opts& router_opts);
@@ -659,7 +658,7 @@
++itry_conflicted_mode;
}
if (timing_info) {
- if (should_setup_lower_bound_connection_delays(itry,router_opts)) {
+ if (should_setup_lower_bound_connection_delays(itry, router_opts)) {
// first iteration sets up the lower bound connection delays since only timing is optimized for
connections_inf.set_stable_critical_path_delay(critical_path.delay());
connections_inf.set_lower_bound_connection_delays(net_delay);
@@ -768,7 +767,7 @@
is_routed = true;
} else if (cluster_ctx.clb_nlist.net_is_ignored(net_id)) { /* Skip ignored nets. */
is_routed = true;
- } else if ( budgeting_inf.get_should_reroute(net_id) ) { /* if there is a hold violation and this net is involved, reroute */
+ } else if (budgeting_inf.get_should_reroute(net_id)) { /* if there is a hold violation and this net is involved, reroute */
// track time spent vs fanout
profiling::net_fanout_start();
@@ -790,12 +789,11 @@
/* Impossible to route? (disconnected rr_graph) */
if (is_routed) {
- route_ctx.net_status[net_id].is_routed = true;
+ route_ctx.net_status[net_id].is_routed = true;
} else {
VTR_LOG("Routing failed.\n");
}
-
} else if (should_route_net(net_id, connections_inf, true) == false) {
is_routed = true;
} else {
@@ -952,10 +950,10 @@
VTR_LOGV_DEBUG(f_router_debug, "Routing Net %zu (%zu sinks)\n", size_t(net_id), num_sinks);
- t_rt_node* rt_root = setup_routing_resources(itry, net_id, num_sinks, pres_fac, router_opts.min_incremental_reroute_fanout, connections_inf, rt_node_of_sink, check_hold(router_opts,timing_info));
+ t_rt_node* rt_root = setup_routing_resources(itry, net_id, num_sinks, pres_fac, router_opts.min_incremental_reroute_fanout, connections_inf, rt_node_of_sink, check_hold(router_opts, timing_info));
bool high_fanout = is_high_fanout(num_sinks, router_opts.high_fanout_threshold);
-
+
std::set<int> route_tree_nodes;
SpatialRouteTreeLookup spatial_route_tree_lookup;
@@ -1080,7 +1078,7 @@
const RouterLookahead& router_lookahead,
SpatialRouteTreeLookup& spatial_rt_lookup,
RouterStats& router_stats,
- route_budgets &budgeting_inf,
+ route_budgets& budgeting_inf,
std::set<int>& route_tree_nodes) {
/* Build a path from the existing route tree rooted at rt_root to the target_node
* add this branch to the existing route tree and update pathfinder costs and rr_node_route_inf to reflect this */
@@ -1170,7 +1168,7 @@
update_screen(ScreenUpdatePriority::MAJOR, "Routed connection successfully", ROUTING, nullptr);
}
- if (budgeting_inf.if_set() && cheapest->backward_delay < cost_params.delay_budget->min_delay ) {
+ if (budgeting_inf.if_set() && cheapest->backward_delay < cost_params.delay_budget->min_delay) {
budgeting_inf.set_should_reroute(net_id, true);
}
@@ -1358,7 +1356,6 @@
const RouterLookahead& router_lookahead,
std::vector<int>& modified_rr_node_inf,
RouterStats& router_stats) {
-
auto& route_ctx = g_vpr_ctx.mutable_routing();
VTR_ASSERT_SAFE(heap_::is_valid());
@@ -1378,13 +1375,13 @@
//Have we found the target?
if (inode == sink_node) {
if (cost_params.delay_budget && cost_params.delay_budget->routing_budgets_algorithm == YOYO) {
- for (unsigned i = 1; i < cheapest->edge.size() - 1; i++ ) {
+ for (unsigned i = 1; i < cheapest->edge.size() - 1; i++) {
int node_2 = cheapest->path_rr[i];
- int edge = cheapest->edge[i-1];
- route_ctx.rr_node_route_inf[node_2].prev_node = cheapest->path_rr[i-1];
- route_ctx.rr_node_route_inf[node_2].prev_edge = edge;
- route_ctx.rr_node_route_inf[node_2].path_cost = cheapest->cost;
- route_ctx.rr_node_route_inf[node_2].backward_path_cost = cheapest->backward_path_cost;
+ int edge = cheapest->edge[i - 1];
+ route_ctx.rr_node_route_inf[node_2].prev_node = cheapest->path_rr[i - 1];
+ route_ctx.rr_node_route_inf[node_2].prev_edge = edge;
+ route_ctx.rr_node_route_inf[node_2].path_cost = cheapest->cost;
+ route_ctx.rr_node_route_inf[node_2].backward_path_cost = cheapest->backward_path_cost;
}
}
@@ -1515,7 +1512,7 @@
if (old_total_cost > new_total_cost && (old_back_cost > new_back_cost || (cost_params.delay_budget && cost_params.delay_budget->routing_budgets_algorithm == YOYO))) {
VTR_LOGV_DEBUG(f_router_debug, " Better cost to %d\n", inode);
-
+
VTR_LOGV_DEBUG(f_router_debug, " Setting path costs for assicated node %d (from %d edge %d)\n", cheapest->index, cheapest->u.prev.node, cheapest->u.prev.edge);
add_to_mod_list(cheapest->index, modified_rr_node_inf);
@@ -1816,7 +1813,7 @@
std::set<int> net_rr) {
int inode = rt_node->inode;
float backward_path_cost = cost_params.criticality * rt_node->Tdel; //+ (1. - cost_params.criticality) * get_rr_cong_cost(inode);
-
+
float R_upstream = rt_node->R_upstream;
float tot_cost = backward_path_cost
+ cost_params.astar_fac
@@ -1829,31 +1826,30 @@
const t_conn_delay_budget* delay_budget = cost_params.delay_budget;
float expected_cost = router_lookahead.get_expected_cost(inode, target_node, cost_params, R_upstream);
- std::vector<int> path;
- if (delay_budget && delay_budget->routing_budgets_algorithm == YOYO ) {
+ if (delay_budget && delay_budget->routing_budgets_algorithm == YOYO) {
float expected_total_cost;
float expected_delay = router_lookahead.get_expected_delay(inode, target_node, cost_params, R_upstream);
float expected_cong = router_lookahead.get_expected_cong(inode, target_node, cost_params, R_upstream);
-
- float expected_total_delay_cost;// = new_costs.backward_cost + cost_params.astar_fac * expected_cost;
- float expected_total_cong = expected_cong + get_rr_cong_cost(inode);
+
+ float expected_total_delay_cost; // = new_costs.backward_cost + cost_params.astar_fac * expected_cost;
+ float expected_total_cong = expected_cong + get_rr_cong_cost(inode);
float expected_total_delay = expected_delay * cost_params.astar_fac + rt_node->Tdel;
-
+
expected_total_delay_cost = cost_params.criticality * expected_total_delay;
- expected_total_delay_cost += (delay_budget->short_path_criticality + cost_params.criticality) * max(0.f, delay_budget->target_delay - expected_total_delay);
- expected_total_delay_cost += pow(max(0.f, expected_total_delay- delay_budget->max_delay), 2) / 100e-12;
+ expected_total_delay_cost += (delay_budget->short_path_criticality + cost_params.criticality) * max(0.f, delay_budget->target_delay - expected_total_delay);
+ expected_total_delay_cost += pow(max(0.f, expected_total_delay - delay_budget->max_delay), 2) / 100e-12;
expected_total_delay_cost += pow(max(0.f, delay_budget->min_delay - expected_total_delay), 2) / 100e-12;
expected_total_cost = expected_total_delay_cost + expected_cong;
-
+
heap_::push_back_node_with_info(inode, expected_total_cost, NO_PREVIOUS, NO_PREVIOUS,
- backward_path_cost, R_upstream, rt_node->Tdel, path, net_rr);
- }else {
- // tot_cost = backward_path_cost + cost_params.astar_fac * expected_cost;
+ backward_path_cost, R_upstream, rt_node->Tdel, net_rr);
+ } else {
+ // tot_cost = backward_path_cost + cost_params.astar_fac * expected_cost;
VTR_LOGV_DEBUG(f_router_debug, " Adding node %8d to heap from init route tree with cost %g (%s)\n", inode, tot_cost, describe_rr_node(inode).c_str());
heap_::push_back_node(inode, tot_cost, NO_PREVIOUS, NO_PREVIOUS,
- backward_path_cost, R_upstream);
+ backward_path_cost, R_upstream);
}
++router_stats.heap_pushes;
@@ -1913,10 +1909,11 @@
int to_xhigh = device_ctx.rr_nodes[to_node].xhigh();
int to_yhigh = device_ctx.rr_nodes[to_node].yhigh();
- if ((to_xhigh < bounding_box.xmin //Strictly left of BB left-edge
- || to_xlow > bounding_box.xmax //Strictly right of BB right-edge
- || to_yhigh < bounding_box.ymin //Strictly below BB bottom-edge
- || to_ylow > bounding_box.ymax) && !(cost_params.delay_budget && cost_params.delay_budget->routing_budgets_algorithm == YOYO)) { //Strictly above BB top-edge
+ if ((to_xhigh < bounding_box.xmin //Strictly left of BB left-edge
+ || to_xlow > bounding_box.xmax //Strictly right of BB right-edge
+ || to_yhigh < bounding_box.ymin //Strictly below BB bottom-edge
+ || to_ylow > bounding_box.ymax)
+ && !(cost_params.delay_budget && cost_params.delay_budget->routing_budgets_algorithm == YOYO)) { //Strictly above BB top-edge
VTR_LOGV_DEBUG(f_router_debug,
" Pruned expansion of node %d edge %d -> %d"
" (to node location %d,%dx%d,%d outside of expanded"
@@ -1957,8 +1954,8 @@
if (!cost_params.delay_budget || (cost_params.delay_budget && cost_params.delay_budget->routing_budgets_algorithm != YOYO) || (current->net_rr.find(to_node) == current->net_rr.end())) {
timing_driven_add_to_heap(cost_params,
- router_lookahead,
- current, from_node, to_node, from_edge, target_node, router_stats);
+ router_lookahead,
+ current, from_node, to_node, from_edge, target_node, router_stats);
}
}
@@ -1982,6 +1979,7 @@
next->R_upstream = current->R_upstream;
next->path_rr = current->path_rr;
next->net_rr = current->net_rr;
+ next->partial_path_nodes = current->partial_path_nodes;
next->edge = current->edge;
auto& route_ctx = g_vpr_ctx.routing();
@@ -1996,7 +1994,7 @@
add_to_heap(next);
++router_stats.heap_pushes;
} else {
- free_heap_data(next);
+ free_heap_data(next);
}
}
@@ -2021,6 +2019,7 @@
current->u.prev.node = from_node;
current->path_rr.emplace_back(from_node);
current->net_rr.emplace(from_node);
+ current->partial_path_nodes.emplace(from_node);
current->edge.emplace_back(iconn);
}
@@ -2073,7 +2072,6 @@
to->backward_delay += Tdel;
to->backward_cong += get_rr_cong_cost(to_node);
-
// to->backward_delay += Tdel;
// to->backward_cong += get_rr_cong_cost(to_node);
if (cost_params.bend_cost != 0.) {
@@ -2087,14 +2085,14 @@
float total_cost = 0.;
const t_conn_delay_budget* delay_budget = cost_params.delay_budget;
- float expected_delay = router_lookahead.get_expected_delay(to_node, target_node, cost_params, to->R_upstream );
- float expected_cong = router_lookahead.get_expected_cong(to_node, target_node, cost_params, to->R_upstream );
+ float expected_delay = router_lookahead.get_expected_delay(to_node, target_node, cost_params, to->R_upstream);
+ float expected_cong = router_lookahead.get_expected_cong(to_node, target_node, cost_params, to->R_upstream);
if (delay_budget && delay_budget->routing_budgets_algorithm == YOYO) {
- float expected_total_delay_cost;// = new_costs.backward_cost + cost_params.astar_fac * expected_cost;
+ float expected_total_delay_cost; // = new_costs.backward_cost + cost_params.astar_fac * expected_cost;
float expected_total_cong_cost;
-
- float expected_total_cong =expected_cong + to->backward_cong;
- float expected_total_delay =cost_params.astar_fac * expected_delay + to->backward_delay;
+
+ float expected_total_cong = expected_cong + to->backward_cong;
+ float expected_total_delay = cost_params.astar_fac * expected_delay + to->backward_delay;
//If budgets specified calculate cost as described by RCV paper:
// R. Fung, V. Betz and W. Chow, "Slack Allocation and Routing to Improve FPGA Timing While
// Repairing Short-Path Violations," in IEEE Transactions on Computer-Aided Design of
@@ -2102,17 +2100,17 @@
//TODO: Since these targets are delays, shouldn't we be using Tdel instead of new_costs.total_cost on RHS?
expected_total_delay_cost = cost_params.criticality * expected_total_delay;
- expected_total_delay_cost += (delay_budget->short_path_criticality + cost_params.criticality) * max(0.f, delay_budget->target_delay - expected_total_delay);
- expected_total_delay_cost += pow(max(0.f, expected_total_delay- delay_budget->max_delay), 2) / 100e-12;
+ expected_total_delay_cost += (delay_budget->short_path_criticality + cost_params.criticality) * max(0.f, delay_budget->target_delay - expected_total_delay);
+ expected_total_delay_cost += pow(max(0.f, expected_total_delay - delay_budget->max_delay), 2) / 100e-12;
expected_total_delay_cost += pow(max(0.f, delay_budget->min_delay - expected_total_delay), 2) / 100e-12;
- expected_total_cong_cost = (1. - cost_params.criticality) * expected_total_cong;
+ expected_total_cong_cost = (1. - cost_params.criticality) * expected_total_cong;
total_cost = expected_total_delay_cost + expected_total_cong;
- }
- else {
+ } else {
//Update total cost
float expected_cost = router_lookahead.get_expected_cost(to_node, target_node, cost_params, to->R_upstream);
total_cost = to->backward_path_cost + cost_params.astar_fac * expected_cost;
- } to->cost = total_cost;
+ }
+ to->cost = total_cost;
}
void update_rr_base_costs(int fanout) {
@@ -2231,8 +2229,7 @@
static bool check_hold(const t_router_opts& router_opts, std::shared_ptr<const SetupHoldTimingInfo> timing_info) {
if (router_opts.routing_budgets_algorithm != YOYO) {
return false;
- }
- else if (timing_info->hold_worst_negative_slack() == 0) {
+ } else if (timing_info->hold_worst_negative_slack() == 0) {
return true;
}
return false;
@@ -2779,18 +2776,16 @@
#endif
}
-static bool is_iteration_complete(bool routing_is_feasible, const t_router_opts& router_opts,
- int itry, std::shared_ptr<const SetupHoldTimingInfo> timing_info) {
- //This function checks if a routing iteration has completed.
+static bool is_iteration_complete(bool routing_is_feasible, const t_router_opts& router_opts, int itry, std::shared_ptr<const SetupHoldTimingInfo> timing_info) {
+ //This function checks if a routing iteration has completed.
//When VPR is run normally, we check if routing_budgets_algorithm is disabled, and if the routing is legal
- //With the introduction of yoyo budgeting algorithm, we must check if there are no hold violations
+ //With the introduction of yoyo budgeting algorithm, we must check if there are no hold violations
//in addition to routing being legal and the correct budgeting algorithm being set.
if (routing_is_feasible) {
if (router_opts.routing_budgets_algorithm != YOYO) {
return true;
- }
- else if (router_opts.routing_budgets_algorithm == YOYO && (itry == 1) && timing_info->hold_worst_negative_slack() == 0) {
+ } else if (router_opts.routing_budgets_algorithm == YOYO && (itry == 1) && timing_info->hold_worst_negative_slack() == 0) {
return true;
}
}
@@ -2803,8 +2798,7 @@
//However, with the yoyo algorithm, the lower bound is set every after every 5 iterations, so long as it is below 25.
if (router_opts.routing_budgets_algorithm != YOYO && itry == 1) {
return true;
- }
- else if (router_opts.routing_budgets_algorithm == YOYO && itry % 5 == 1 && itry < 25) {
+ } else if (router_opts.routing_budgets_algorithm == YOYO && itry % 5 == 1 && itry < 25) {
return true;
}
return false;
diff --git a/vpr/src/route/route_tree_timing.cpp b/vpr/src/route/route_tree_timing.cpp
index 5074631..d432805 100644
--- a/vpr/src/route/route_tree_timing.cpp
+++ b/vpr/src/route/route_tree_timing.cpp
@@ -3,7 +3,6 @@
#include <vector>
using namespace std;
-
#include "vtr_assert.h"
#include "vtr_log.h"
#include "vtr_memory.h"
@@ -51,7 +50,8 @@
static void free_linked_rt_edge(t_linked_rt_edge* rt_edge);
static t_rt_node* add_subtree_to_route_tree(t_heap* hptr,
- t_rt_node** sink_rt_node_ptr,std::set<int>& route_tree_nodes);
+ t_rt_node** sink_rt_node_ptr,
+ std::set<int>& route_tree_nodes);
static t_rt_node* add_non_configurable_to_route_tree(const int rr_node, const bool reached_by_non_configurable_edge, std::unordered_set<int>& visited, std::set<int>& route_tree_nodes);
@@ -213,7 +213,7 @@
auto& device_ctx = g_vpr_ctx.device();
//Create a new subtree from the target in hptr to existing routing
- start_of_new_subtree_rt_node = add_subtree_to_route_tree(hptr, &sink_rt_node,route_tree_nodes);
+ start_of_new_subtree_rt_node = add_subtree_to_route_tree(hptr, &sink_rt_node, route_tree_nodes);
//Propagate R_upstream down into the new subtree
load_new_subtree_R_upstream(start_of_new_subtree_rt_node);
diff --git a/vpr/src/route/router_delay_profiling.cpp b/vpr/src/route/router_delay_profiling.cpp
index 6f7770a..fa91996 100644
--- a/vpr/src/route/router_delay_profiling.cpp
+++ b/vpr/src/route/router_delay_profiling.cpp
@@ -73,7 +73,7 @@
std::vector<float> path_delays_to(device_ctx.rr_nodes.size(), std::numeric_limits<float>::quiet_NaN());
t_rt_node* rt_root = setup_routing_resources_no_net(src_rr_node);
-
+
std::set<int> dummy_route_tree_nodes; // dummy set that will not be used for any purpose.
t_bb bounding_box;
diff --git a/vpr/src/route/router_lookahead.cpp b/vpr/src/route/router_lookahead.cpp
index 40bbcf9..0c7e19f 100644
--- a/vpr/src/route/router_lookahead.cpp
+++ b/vpr/src/route/router_lookahead.cpp
@@ -73,7 +73,6 @@
t_rr_type rr_type = device_ctx.rr_nodes[inode].type();
if (rr_type == CHANX || rr_type == CHANY) {
-
VTR_ASSERT_SAFE(device_ctx.rr_nodes[inode].type() == CHANX || device_ctx.rr_nodes[inode].type() == CHANY);
int num_segs_ortho_dir = 0;
@@ -87,18 +86,17 @@
const auto& ipin_data = device_ctx.rr_indexed_data[IPIN_COST_INDEX];
const auto& sink_data = device_ctx.rr_indexed_data[SINK_COST_INDEX];
- float Tdel = num_segs_same_dir * same_data.T_linear
- + num_segs_ortho_dir * ortho_data.T_linear
- + num_segs_same_dir * num_segs_same_dir * same_data.T_quadratic
- + num_segs_ortho_dir * num_segs_ortho_dir * ortho_data.T_quadratic
- + R_upstream * ( num_segs_same_dir * same_data.C_load
- + num_segs_ortho_dir * ortho_data.C_load);
- + ipin_data.T_linear;
+ float Tdel = num_segs_same_dir * same_data.T_linear
+ + num_segs_ortho_dir * ortho_data.T_linear
+ + num_segs_same_dir * num_segs_same_dir * same_data.T_quadratic
+ + num_segs_ortho_dir * num_segs_ortho_dir * ortho_data.T_quadratic
+ + R_upstream * (num_segs_same_dir * same_data.C_load + num_segs_ortho_dir * ortho_data.C_load);
+ +ipin_data.T_linear;
return (Tdel);
} else if (rr_type == IPIN) { /* Change if you're allowing route-throughs */
return (device_ctx.rr_indexed_data[SINK_COST_INDEX].base_cost);
-
+
} else { /* Change this if you want to investigate route-throughs */
return (0.);
}
@@ -110,7 +108,6 @@
t_rr_type rr_type = device_ctx.rr_nodes[inode].type();
if (rr_type == CHANX || rr_type == CHANY) {
-
int num_segs_ortho_dir = 0;
int num_segs_same_dir = get_expected_segs_to_target(inode, target_node, &num_segs_ortho_dir);
@@ -122,19 +119,19 @@
const auto& ipin_data = device_ctx.rr_indexed_data[IPIN_COST_INDEX];
const auto& sink_data = device_ctx.rr_indexed_data[SINK_COST_INDEX];
- float cong_cost = num_segs_same_dir * same_data.base_cost
- + num_segs_ortho_dir * ortho_data.base_cost
- + ipin_data.base_cost
- + sink_data.base_cost;
+ float cong_cost = num_segs_same_dir * same_data.base_cost
+ + num_segs_ortho_dir * ortho_data.base_cost
+ + ipin_data.base_cost
+ + sink_data.base_cost;
return (1. - params.criticality) * cong_cost;
- //} else if (rr_type == IPIN) {
+ //} else if (rr_type == IPIN) {
- //const auto& ipin_data = device_ctx.rr_indexed_data[IPIN_COST_INDEX];
- //const auto& sink_data = device_ctx.rr_indexed_data[SINK_COST_INDEX];
- //
- //float cong_cost = ipin_data.base_cost
- // + sink_data.base_cost;
+ //const auto& ipin_data = device_ctx.rr_indexed_data[IPIN_COST_INDEX];
+ //const auto& sink_data = device_ctx.rr_indexed_data[SINK_COST_INDEX];
+ //
+ //float cong_cost = ipin_data.base_cost
+ // + sink_data.base_cost;
} else {
return (0.);
}
@@ -154,8 +151,6 @@
}
}
-
-
float MapLookahead::get_expected_delay(int inode, int target_node, const t_conn_cost_params& params, float R_upstream) const {
return 0.;
}
diff --git a/vpr/src/route/router_lookahead.h b/vpr/src/route/router_lookahead.h
index d67a499..bc41c2a 100644
--- a/vpr/src/route/router_lookahead.h
+++ b/vpr/src/route/router_lookahead.h
@@ -11,7 +11,6 @@
virtual float get_expected_delay(int node, int target_node, const t_conn_cost_params& params, float R_upstream) const = 0;
virtual float get_expected_cong(int node, int target_node, const t_conn_cost_params& params, float R_upstream) const = 0;
-
virtual ~RouterLookahead() {}
};
