Only prune non-configurable nodes at end of routing.
Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com>
diff --git a/vpr/src/route/route_common.cpp b/vpr/src/route/route_common.cpp
index 778330c..6eb4fd0 100644
--- a/vpr/src/route/route_common.cpp
+++ b/vpr/src/route/route_common.cpp
@@ -162,10 +162,12 @@
for (auto net_id : cluster_ctx.clb_nlist.nets()) {
/* Free any current routing. */
+ pathfinder_update_path_cost(route_ctx.trace[net_id].head, -1, 0.f);
free_traceback(net_id);
/* Set the current routing to the saved one. */
route_ctx.trace[net_id].head = best_routing[net_id];
+ pathfinder_update_path_cost(route_ctx.trace[net_id].head, 1, 0.f);
best_routing[net_id] = nullptr; /* No stored routing. */
}
diff --git a/vpr/src/route/route_timing.cpp b/vpr/src/route/route_timing.cpp
index 42aa2a9..8a199f9 100644
--- a/vpr/src/route/route_timing.cpp
+++ b/vpr/src/route/route_timing.cpp
@@ -297,6 +297,8 @@
const SetupTimingInfo& timing_info,
const RoutingDelayCalculator& delay_calc);
+static void prune_unused_non_configurable_nets(CBRR& connections_inf);
+
/************************ Subroutine definitions *****************************/
bool try_timing_driven_route(const t_router_opts& router_opts,
const t_analysis_opts& analysis_opts,
@@ -727,9 +729,17 @@
VTR_LOG("Restoring best routing\n");
auto& router_ctx = g_vpr_ctx.mutable_routing();
+
+ /* Restore congestion from best route */
+ for (auto net_id : cluster_ctx.clb_nlist.nets()) {
+ pathfinder_update_path_cost(route_ctx.trace[net_id].head, -1, pres_fac);
+ pathfinder_update_path_cost(best_routing[net_id].head, 1, pres_fac);
+ }
router_ctx.trace = best_routing;
router_ctx.clb_opins_used_locally = best_clb_opins_used_locally;
+ prune_unused_non_configurable_nets(connections_inf);
+
if (timing_info) {
VTR_LOG("Critical path: %g ns\n", 1e9 * best_routing_metrics.critical_path.delay());
}
@@ -1539,9 +1549,7 @@
profiling::net_rebuild_start();
// convert the previous iteration's traceback into a route tree
- auto& device_ctx = g_vpr_ctx.device();
- std::vector<int> non_config_node_set_usage(device_ctx.rr_non_config_node_sets.size(), 0);
- rt_root = traceback_to_route_tree(net_id, &non_config_node_set_usage);
+ rt_root = traceback_to_route_tree(net_id);
//Santiy check that route tree and traceback are equivalent before pruning
VTR_ASSERT_DEBUG(verify_traceback_route_tree_equivalent(route_ctx.trace[net_id].head, rt_root));
@@ -1551,7 +1559,7 @@
VTR_ASSERT_SAFE(should_route_net(net_id, connections_inf, true));
//Prune the branches of the tree that don't legally lead to sinks
- rt_root = prune_route_tree(rt_root, connections_inf, &non_config_node_set_usage);
+ rt_root = prune_route_tree(rt_root, connections_inf);
//Now that the tree has been pruned, we can free the old traceback
// NOTE: this must happen *after* pruning since it changes the
@@ -2807,3 +2815,46 @@
timing_reporter.report_timing_setup(router_opts.first_iteration_timing_report_file, *timing_info.setup_analyzer(), analysis_opts.timing_report_npaths);
}
+
+// If a route is ripped up during routing, non-configurable sets are left
+// behind. As a result, the final routing may have stubs at
+// non-configurable sets. This function tracks non-configurable set usage,
+// and if the sets are unused, prunes them.
+static void prune_unused_non_configurable_nets(CBRR& connections_inf) {
+ auto& device_ctx = g_vpr_ctx.device();
+ auto& cluster_ctx = g_vpr_ctx.clustering();
+ auto& route_ctx = g_vpr_ctx.routing();
+
+ std::vector<int> non_config_node_set_usage(device_ctx.rr_non_config_node_sets.size(), 0);
+ for (auto net_id : cluster_ctx.clb_nlist.nets()) {
+ connections_inf.prepare_routing_for_net(net_id);
+ connections_inf.clear_force_reroute_for_net();
+
+ std::fill(non_config_node_set_usage.begin(), non_config_node_set_usage.end(), 0);
+ t_rt_node* rt_root = traceback_to_route_tree(net_id, &non_config_node_set_usage);
+ if (rt_root == nullptr) {
+ continue;
+ }
+
+ //Santiy check that route tree and traceback are equivalent before pruning
+ VTR_ASSERT(verify_traceback_route_tree_equivalent(
+ route_ctx.trace[net_id].head, rt_root));
+
+ // check for edge correctness
+ VTR_ASSERT_SAFE(is_valid_skeleton_tree(rt_root));
+
+ //Prune the branches of the tree that don't legally lead to sinks
+ rt_root = prune_route_tree(rt_root, connections_inf,
+ &non_config_node_set_usage);
+
+ // Free old traceback.
+ free_traceback(net_id);
+
+ // Update traceback with pruned tree.
+ auto& reached_rt_sinks = connections_inf.get_reached_rt_sinks();
+ traceback_from_route_tree(net_id, rt_root, reached_rt_sinks.size());
+ VTR_ASSERT(verify_traceback_route_tree_equivalent(route_ctx.trace[net_id].head, rt_root));
+
+ free_route_tree(rt_root);
+ }
+}
diff --git a/vpr/src/route/route_tree_timing.cpp b/vpr/src/route/route_tree_timing.cpp
index 0b9bc78..d51aa5d 100644
--- a/vpr/src/route/route_tree_timing.cpp
+++ b/vpr/src/route/route_tree_timing.cpp
@@ -977,7 +977,7 @@
// After removing an edge, check if non_config_node_set_usage
// needs an update.
- if (node_set != -1 && device_ctx.rr_switch_inf[old_edge->iswitch].configurable()) {
+ if (non_config_node_set_usage != nullptr && node_set != -1 && device_ctx.rr_switch_inf[old_edge->iswitch].configurable()) {
(*non_config_node_set_usage)[node_set] -= 1;
VTR_ASSERT((*non_config_node_set_usage)[node_set] >= 0);
}
@@ -1046,7 +1046,9 @@
if (reached_non_configurably) {
// Check if this non-configurable node set is in use.
VTR_ASSERT(node_set != -1);
- force_prune = force_prune || (*non_config_node_set_usage)[node_set] == 0;
+ if (non_config_node_set_usage != nullptr && (*non_config_node_set_usage)[node_set] == 0) {
+ force_prune = true;
+ }
}
}
@@ -1068,7 +1070,7 @@
// 3. The node set is not active
//
// Then prune this node.
- if (node_set != -1 && device_ctx.rr_switch_inf[node->parent_switch].configurable() && (*non_config_node_set_usage)[node_set] == 0) {
+ if (non_config_node_set_usage != nullptr && node_set != -1 && device_ctx.rr_switch_inf[node->parent_switch].configurable() && (*non_config_node_set_usage)[node_set] == 0) {
// This node should be pruned, re-prune edges once more.
return prune_route_tree_recurr(node, connections_inf, /*force_prune=*/false, non_config_node_set_usage);
}
@@ -1080,6 +1082,10 @@
}
}
+t_rt_node* prune_route_tree(t_rt_node* rt_root, CBRR& connections_inf) {
+ return prune_route_tree(rt_root, connections_inf, nullptr);
+}
+
t_rt_node* prune_route_tree(t_rt_node* rt_root, CBRR& connections_inf, std::vector<int>* non_config_node_set_usage) {
/* Prune a skeleton route tree of illegal branches - when there is at least 1 congested node on the path to a sink
* This is the top level function to be called with the SOURCE node as root.
diff --git a/vpr/src/route/route_tree_timing.h b/vpr/src/route/route_tree_timing.h
index e998efa..ae67a15 100644
--- a/vpr/src/route/route_tree_timing.h
+++ b/vpr/src/route/route_tree_timing.h
@@ -55,6 +55,7 @@
t_rt_node* traceback_to_route_tree(t_trace* head, std::vector<int>* non_config_node_set_usage);
t_trace* traceback_from_route_tree(ClusterNetId inet, const t_rt_node* root, int num_remaining_sinks);
+t_rt_node* prune_route_tree(t_rt_node* rt_root, CBRR& connections_inf);
t_rt_node* prune_route_tree(t_rt_node* rt_root, CBRR& connections_inf, std::vector<int>* non_config_node_set_usage);
void pathfinder_update_cost_from_route_tree(const t_rt_node* rt_root, int add_or_sub, float pres_fac);
