vpr: Add fast node look-up support to RRGraph
diff --git a/vpr/src/route/rr_graph.cpp b/vpr/src/route/rr_graph.cpp
index 33e3d45..d7768e4 100644
--- a/vpr/src/route/rr_graph.cpp
+++ b/vpr/src/route/rr_graph.cpp
@@ -138,6 +138,36 @@
return RREdgeId::INVALID();
}
+RRNodeId RRGraph::find_node(short x, short y, t_rr_type type, int ptc, e_side side) const {
+ if (!valid_fast_node_lookup()) {
+ build_fast_node_lookup();
+ }
+ size_t itype = type;
+ size_t iside = side;
+ return node_lookup_[x][y][itype][ptc][iside];
+}
+
+RRGraph::node_range RRGraph::find_nodes(short x, short y, t_rr_type type, int ptc) const {
+ if (!valid_fast_node_lookup()) {
+ build_fast_node_lookup();
+ }
+
+ const auto& matching_nodes = node_lookup_[x][y][type][ptc];
+
+ return vtr::make_range(matching_nodes.begin(), matching_nodes.end());
+}
+
+bool RRGraph::is_dirty() const {
+ return dirty_;
+}
+
+void RRGraph::set_dirty() {
+ dirty_ = true;
+}
+
+void RRGraph::clear_dirty() {
+ dirty_ = false;
+}
//Mutators
RRNodeId RRGraph::create_node(t_rr_type type) {
@@ -161,6 +191,8 @@
node_in_edges_.emplace_back(); //Initially empty
node_out_edges_.emplace_back(); //Initially empty
+ invalidate_fast_node_lookup();
+
VTR_ASSERT(validate_sizes());
return node_id;
@@ -212,7 +244,10 @@
//Mark node invalid
node_ids_[node] = RRNodeId::INVALID();
- dirty_ = true;
+ //Invalidate the node look-up
+ invalidate_fast_node_lookup();
+
+ set_dirty();
}
void RRGraph::remove_edge(RREdgeId edge) {
@@ -237,7 +272,7 @@
//Mark edge invalid
edge_ids_[edge] = RREdgeId::INVALID();
- dirty_ = true;
+ set_dirty();
}
void RRGraph::set_node_xlow(RRNodeId node, short xlow) {
@@ -340,6 +375,54 @@
node_Cs_[node] = C;
}
+void RRGraph::build_fast_node_lookup() const {
+ invalidate_fast_node_lookup();
+
+ for (auto node : nodes()) {
+ size_t x = node_xlow(node);
+ if (x < node_lookup_.size()) {
+ node_lookup_.resize(x + 1);
+ }
+
+ size_t y = node_ylow(node);
+ if (y < node_lookup_[x].size()) {
+ node_lookup_[x].resize(y + 1);
+ }
+
+ size_t itype = node_type(node);
+ if (itype < node_lookup_[x][y].size()) {
+ node_lookup_[x][y].resize(itype + 1);
+ }
+
+ size_t ptc = node_ptc_num(node);
+ if (ptc < node_lookup_[x][y][itype].size()) {
+ node_lookup_[x][y][itype].resize(ptc + 1);
+ }
+
+ size_t iside = -1;
+ if (node_type(node) == OPIN || node_type(node) == IPIN) {
+ iside = node_side(node);
+ } else {
+ iside = NUM_SIDES;
+ }
+
+ if (iside < node_lookup_[x][y][itype][ptc].size()) {
+ node_lookup_[x][y][itype][ptc].resize(iside + 1);
+ }
+
+ //Save node in lookup
+ node_lookup_[x][y][itype][ptc][iside] = node;
+ }
+}
+
+void RRGraph::invalidate_fast_node_lookup() const {
+ node_lookup_.clear();
+}
+
+bool RRGraph::valid_fast_node_lookup() const {
+ return !node_lookup_.empty();
+}
+
bool RRGraph::validate() {
bool success = true;
success &= validate_sizes();
@@ -495,7 +578,9 @@
rebuild_node_refs(edge_id_map);
- dirty_ = false;
+ invalidate_fast_node_lookup();
+
+ clear_dirty();
}
void RRGraph::build_id_maps(vtr::vector<RRNodeId,RRNodeId>& node_id_map,
diff --git a/vpr/src/route/rr_graph.h b/vpr/src/route/rr_graph.h
index 1ef8c89..0dcf779 100644
--- a/vpr/src/route/rr_graph.h
+++ b/vpr/src/route/rr_graph.h
@@ -60,6 +60,9 @@
//Utilities
RREdgeId find_edge(RRNodeId src_node, RRNodeId sink_node) const;
+ RRNodeId find_node(short x, short y, t_rr_type type, int ptc, e_side side=NUM_SIDES) const;
+ node_range find_nodes(short x, short y, t_rr_type type, int ptc) const;
+ bool is_dirty() const;
public: //Mutators
RRNodeId create_node(t_rr_type type);
RREdgeId create_edge(RRNodeId source, RRNodeId sink, RRSwitchId switch_id);
@@ -90,6 +93,14 @@
void compress();
bool validate();
private: //Internal
+ void set_dirty();
+ void clear_dirty();
+
+ //Fast look-up
+ void build_fast_node_lookup() const;
+ void invalidate_fast_node_lookup() const;
+ bool valid_fast_node_lookup() const;
+
//Validation
bool valid_node_id(RRNodeId node) const;
bool valid_edge_id(RREdgeId edge) const;
@@ -143,6 +154,10 @@
//Misc.
bool dirty_ = false;
+
+ //Fast look-up
+ typedef std::vector<std::vector<std::vector<std::vector<std::vector<RRNodeId>>>>> NodeLookup;
+ mutable NodeLookup node_lookup_; //[0..xmax][0..ymax][0..NUM_TYPES-1][0..ptc_max][0..NUM_SIDES-1]
};
#endif
