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