Track non-configurable edge usage to enable pruning.
Fixes #526
Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com>
diff --git a/vpr/src/route/check_route.cpp b/vpr/src/route/check_route.cpp
index f0ec889..e602ee4 100644
--- a/vpr/src/route/check_route.cpp
+++ b/vpr/src/route/check_route.cpp
@@ -13,6 +13,8 @@
#include "rr_graph.h"
#include "check_rr_graph.h"
#include "read_xml_arch_file.h"
+#include "route_tree_type.h"
+#include "route_tree_timing.h"
/******************** Subroutines local to this module **********************/
static void check_node_and_range(int inode, enum e_route_type route_type);
@@ -26,6 +28,7 @@
enum e_route_type route_type);
static bool check_non_configurable_edges(ClusterNetId net, const t_non_configurable_rr_sets& non_configurable_rr_sets);
+static void check_net_for_stubs(ClusterNetId net);
/************************ Subroutine definitions ****************************/
@@ -155,6 +158,8 @@
check_non_configurable_edges(net_id, non_configurable_rr_sets);
+ check_net_for_stubs(net_id);
+
reset_flags(net_id, connected_to_route);
} /* End for each net */
@@ -776,3 +781,90 @@
return true;
}
+
+// StubFinder traverses a net definition and find ensures that all nodes that
+// are children of a configurable node have at least one sink.
+class StubFinder {
+ public:
+ // Checks specified net for stubs, return true if at least one stub is
+ // found.
+ bool CheckNet(ClusterNetId net);
+
+ // Returns set of stub nodes.
+ const std::set<int>& stub_nodes() {
+ return stub_nodes_;
+ }
+
+ private:
+ bool RecurseTree(t_rt_node* rt_root);
+
+ // Set of stub nodes
+ // Note this is an ordered set so that node output is sorted by node
+ // id.
+ std::set<int> stub_nodes_;
+};
+
+//Cheks for stubs in a net's routing.
+//
+//Stubs (routing branches which don't connect to SINKs) serve no purpose, and only chew up wiring unecessarily.
+//The only exception are stubs required by non-configurable switches (e.g. shorts).
+//
+//We treat any configurable stubs as an error.
+void check_net_for_stubs(ClusterNetId net) {
+ auto& route_ctx = g_vpr_ctx.mutable_routing();
+
+ StubFinder stub_finder;
+
+ bool any_stubs = stub_finder.CheckNet(net);
+ if (any_stubs) {
+ auto& cluster_ctx = g_vpr_ctx.clustering();
+ std::string msg = vtr::string_fmt("Route tree for net '%s' (#%zu) contains stub branches rooted at:\n",
+ cluster_ctx.clb_nlist.net_name(net).c_str(), size_t(net));
+ for (int inode : stub_finder.stub_nodes()) {
+ msg += vtr::string_fmt(" %s\n", describe_rr_node(inode).c_str());
+ }
+
+ VPR_THROW(VPR_ERROR_ROUTE, msg.c_str());
+ }
+}
+
+bool StubFinder::CheckNet(ClusterNetId net) {
+ stub_nodes_.clear();
+
+ t_rt_node* rt_root = traceback_to_route_tree(net);
+ RecurseTree(rt_root);
+ free_route_tree(rt_root);
+
+ return !stub_nodes_.empty();
+}
+
+// Returns true if this node is a stub.
+bool StubFinder::RecurseTree(t_rt_node* rt_root) {
+ auto& device_ctx = g_vpr_ctx.device();
+
+ if (rt_root->u.child_list == nullptr) {
+ //If a leaf of the route tree is not a SINK, then it is a stub
+ if (device_ctx.rr_nodes[rt_root->inode].type() != SINK) {
+ return true; //It is the current root of this stub
+ } else {
+ return false;
+ }
+ } else {
+ bool is_stub = true;
+ for (t_linked_rt_edge* edge = rt_root->u.child_list; edge != nullptr; edge = edge->next) {
+ bool driver_switch_configurable = device_ctx.rr_switch_inf[edge->iswitch].configurable();
+
+ bool child_is_stub = RecurseTree(edge->child);
+ if (!child_is_stub) {
+ // Because the child was not a stub, this node is not a stub.
+ is_stub = false;
+ } else if (driver_switch_configurable) {
+ // This child was stub, and we drove it from a configurable
+ // edge, this is an error.
+ stub_nodes_.insert(edge->child->inode);
+ }
+ }
+
+ return is_stub;
+ }
+}
diff --git a/vpr/src/route/route_timing.cpp b/vpr/src/route/route_timing.cpp
index 5e2f358..42aa2a9 100644
--- a/vpr/src/route/route_timing.cpp
+++ b/vpr/src/route/route_timing.cpp
@@ -1539,7 +1539,9 @@
profiling::net_rebuild_start();
// convert the previous iteration's traceback into a route tree
- rt_root = traceback_to_route_tree(net_id);
+ 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);
//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));
@@ -1549,7 +1551,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);
+ rt_root = prune_route_tree(rt_root, connections_inf, &non_config_node_set_usage);
//Now that the tree has been pruned, we can free the old traceback
// NOTE: this must happen *after* pruning since it changes the
diff --git a/vpr/src/route/route_tree_timing.cpp b/vpr/src/route/route_tree_timing.cpp
index cff2126..b93aee3 100644
--- a/vpr/src/route/route_tree_timing.cpp
+++ b/vpr/src/route/route_tree_timing.cpp
@@ -53,9 +53,9 @@
bool verify_route_tree_recurr(t_rt_node* node, std::set<int>& seen_nodes);
-t_rt_node* prune_route_tree_recurr(t_rt_node* node, CBRR& connections_inf, bool congested);
+static t_rt_node* prune_route_tree_recurr(t_rt_node* node, CBRR& connections_inf, bool congested, std::vector<int>* non_config_node_set_usage);
-static t_trace* traceback_to_route_tree_branch(t_trace* trace, std::map<int, t_rt_node*>& rr_node_to_rt);
+static t_trace* traceback_to_route_tree_branch(t_trace* trace, std::map<int, t_rt_node*>& rr_node_to_rt, std::vector<int>* non_config_node_set_usage);
static std::pair<t_trace*, t_trace*> traceback_from_route_tree_recurr(t_trace* head, t_trace* tail, const t_rt_node* node);
@@ -702,12 +702,20 @@
}
/*************** Conversion between traceback and route tree *******************/
-t_rt_node* traceback_to_route_tree(ClusterNetId inet) {
+t_rt_node* traceback_to_route_tree(ClusterNetId inet, std::vector<int>* non_config_node_set_usage) {
auto& route_ctx = g_vpr_ctx.routing();
- return traceback_to_route_tree(route_ctx.trace[inet].head);
+ return traceback_to_route_tree(route_ctx.trace[inet].head, non_config_node_set_usage);
+}
+
+t_rt_node* traceback_to_route_tree(ClusterNetId inet) {
+ return traceback_to_route_tree(inet, nullptr);
}
t_rt_node* traceback_to_route_tree(t_trace* head) {
+ return traceback_to_route_tree(head, nullptr);
+}
+
+t_rt_node* traceback_to_route_tree(t_trace* head, std::vector<int>* non_config_node_set_usage) {
/* Builds a skeleton route tree from a traceback
* does not calculate R_upstream, C_downstream, or Tdel at all (left uninitialized)
* returns the root of the converted route tree
@@ -723,7 +731,7 @@
t_trace* trace = head;
while (trace) { //Each branch
- trace = traceback_to_route_tree_branch(trace, rr_node_to_rt);
+ trace = traceback_to_route_tree_branch(trace, rr_node_to_rt, non_config_node_set_usage);
}
// Due to the recursive nature of traceback_to_route_tree_branch,
// the source node is not properly configured.
@@ -740,7 +748,9 @@
//Note that R_upstream and C_downstream are initialized to NaN
//
//Returns the t_trace defining the start of the next branch
-static t_trace* traceback_to_route_tree_branch(t_trace* trace, std::map<int, t_rt_node*>& rr_node_to_rt) {
+static t_trace* traceback_to_route_tree_branch(t_trace* trace,
+ std::map<int, t_rt_node*>& rr_node_to_rt,
+ std::vector<int>* non_config_node_set_usage) {
t_trace* next = nullptr;
if (trace) {
@@ -779,8 +789,21 @@
next = trace->next;
if (iswitch != OPEN) {
+ // Keep track of non-configurable set usage by looking for
+ // configurable edges that extend out of a non-configurable set.
+ //
+ // Each configurable edges from the non-configurable set is a
+ // usage of the set.
+ auto& device_ctx = g_vpr_ctx.device();
+ auto set_itr = device_ctx.rr_node_to_non_config_node_set.find(inode);
+ if (non_config_node_set_usage != nullptr && set_itr != device_ctx.rr_node_to_non_config_node_set.end()) {
+ if (device_ctx.rr_switch_inf[iswitch].configurable()) {
+ (*non_config_node_set_usage)[set_itr->second] += 1;
+ }
+ }
+
//Recursively construct the remaining branch
- next = traceback_to_route_tree_branch(next, rr_node_to_rt);
+ next = traceback_to_route_tree_branch(next, rr_node_to_rt, non_config_node_set_usage);
//Get the created child
itr = rr_node_to_rt.find(trace->next->index);
@@ -894,7 +917,7 @@
//Prunes a route tree (recursively) based on congestion and the 'force_prune' argument
//
//Returns true if the current node was pruned
-t_rt_node* prune_route_tree_recurr(t_rt_node* node, CBRR& connections_inf, bool force_prune) {
+static t_rt_node* prune_route_tree_recurr(t_rt_node* node, CBRR& connections_inf, bool force_prune, std::vector<int>* non_config_node_set_usage) {
//Recursively traverse the route tree rooted at node and remove any congested
//sub-trees
@@ -904,6 +927,11 @@
auto& route_ctx = g_vpr_ctx.routing();
bool congested = (route_ctx.rr_node_route_inf[node->inode].occ() > device_ctx.rr_nodes[node->inode].capacity());
+ int node_set = -1;
+ auto itr = device_ctx.rr_node_to_non_config_node_set.find(node->inode);
+ if (itr != device_ctx.rr_node_to_non_config_node_set.end()) {
+ node_set = itr->second;
+ }
if (congested) {
//This connection is congested -- prune it
@@ -920,7 +948,8 @@
t_linked_rt_edge* prev_edge = nullptr;
t_linked_rt_edge* edge = node->u.child_list;
while (edge) {
- t_rt_node* child = prune_route_tree_recurr(edge->child, connections_inf, force_prune);
+ t_rt_node* child = prune_route_tree_recurr(edge->child,
+ connections_inf, force_prune, non_config_node_set_usage);
if (!child) { //Child was pruned
@@ -935,6 +964,13 @@
t_linked_rt_edge* old_edge = edge;
edge = edge->next;
+ // 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()) {
+ (*non_config_node_set_usage)[node_set] -= 1;
+ VTR_ASSERT((*non_config_node_set_usage)[node_set] >= 0);
+ }
+
free_linked_rt_edge(old_edge);
//Note prev_edge is unchanged
@@ -982,18 +1018,8 @@
// We take the corresponding actions:
// 1) Prune the node.
//
- // 2) Prune the node only if force_prune is set
- //
- // Since the node was reached non-configurably it is illegal to
- // remove it independently of any other nodes which are non-
- // configurably connected to it.
- //
- // As a result we only remove a non-configurably connected node
- // if force_prune is set.
- //
- // Note that if a node upstream of the non-configurably connected
- // nodes becomes congested, force_prune will be set and the *entire*
- // set of non-configurably connected nodes will be removed.
+ // 2) Prune the node only if the node set is unused or if force_prune
+ // is set.
//
// 3) Prune the node.
//
@@ -1005,6 +1031,12 @@
bool reached_non_configurably = false;
if (node->parent_node) {
reached_non_configurably = !device_ctx.rr_switch_inf[node->parent_switch].configurable();
+
+ 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 (reached_non_configurably && !force_prune) {
@@ -1022,7 +1054,7 @@
}
}
-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) {
/* 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.
* Returns true if the entire tree has been pruned.
@@ -1040,7 +1072,7 @@
VTR_ASSERT_MSG(route_ctx.rr_node_route_inf[rt_root->inode].occ() <= device_ctx.rr_nodes[rt_root->inode].capacity(),
"Route tree root/SOURCE should never be congested");
- return prune_route_tree_recurr(rt_root, connections_inf, false);
+ return prune_route_tree_recurr(rt_root, connections_inf, false, 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) {
diff --git a/vpr/src/route/route_tree_timing.h b/vpr/src/route/route_tree_timing.h
index 6dfc122..e998efa 100644
--- a/vpr/src/route/route_tree_timing.h
+++ b/vpr/src/route/route_tree_timing.h
@@ -49,11 +49,13 @@
void print_route_tree_inf(const t_rt_node* rt_root);
void print_route_tree_congestion(const t_rt_node* rt_root);
-t_rt_node* traceback_to_route_tree(t_trace* head);
t_rt_node* traceback_to_route_tree(ClusterNetId inet);
+t_rt_node* traceback_to_route_tree(ClusterNetId inet, std::vector<int>* non_config_node_set_usage);
+t_rt_node* traceback_to_route_tree(t_trace* head);
+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);
