Routing Resource Graph

RRGraphView

The RRGraphView encapsulates a read-only routing resource graph as most clients (router, timing analyzer, etc.) only need to read a routing-resource graph (RRGraph).

The RRGraph models the FPGA’s programmable routing fabric as a graph consisting of nodes and edges. Each node and edge is supplemented with additional metadata, such as the physical location within the chip and electrical properties, to optimize algorithm efficiency, aid in visualizing the chip layout, and estimate signal delays.

Note that each client of rr_graph may get a frame view of the object The RRGraphView is the complete frame view of the routing resource graph

  • This helps to reduce the memory footprint for each client

  • This avoids massive changes for each client on using the APIs as each frame view provides adhoc APIs for each client

RRGraph nodes

Each node represents a routing resource, which can be:

  1. A routing track (CHANX or CHANY).

  2. An input/output of a logic block (IPIN or OPIN).

  3. A virtual source or sink node (SOURCE or SINK).

RRGraph edges

Each edge represents a switch between resources, which can be:

  1. A multiplexer.

  2. A tri-state buffer.

  3. A pass gate.

  4. A non-configurable buffer.

  5. A short (metal connection).

Note

Despite the RRGraph containing millions of edges, there are only a few switch types. Therefore, all switch details, including R and C, are stored using a flyweight pattern (rr_switch_inf) rather than being directly embedded in the edge-related data of the RRGraph. Each edge stores the ID of its associated switch for easy lookup.

Note

The RRGraphView does not own the storage. It provides a virtual read-only protocol for:

  • Placer

  • Router

  • Timing analyzer

  • GUI

class RRGraphView

Public Functions

inline vtr::StrongIdRange<RRNodeId> nodes() const

Aggregates for creating range-based loops for nodes.

To iterate over the nodes in an RRGraph, using a range-based loop is recommended.

// Strongly suggest using a read-only rr_graph object const RRGraph& rr_graph;
for (const RRNodeId& node : rr_graph.nodes()) {
    // Do something with each node
}
inline size_t num_nodes() const

Return number of routing resource nodes.

inline bool empty() const

check whether the RR graph is currently empty

inline vtr::StrongIdRange<RREdgeId> edge_range(RRNodeId id) const

Return a range of RREdgeIds that belong to a specified node.

Note

If this range is empty, then the specified node has no edges.

inline e_rr_type node_type(RRNodeId node) const

Return the type of a specified node.

inline std::optional<const std::string*> node_name(RRNodeId node) const

Return the name of a specified node.

Note

If no name is assigned, an empty optional is returned.

inline const char *node_type_string(RRNodeId node) const

Return a string indicating the type of the specified node.

inline short node_capacity(RRNodeId node) const

Return the capacity of a specified node.

inline Direction node_direction(RRNodeId node) const

Return the direction of a specified node.

Note

Direction Categories:

  • Direction::INC: Wire driver is positioned at the low-coordinate end of the wire.

  • Direction::DEC: Wire driver is positioned at the high-coordinate end of the wire.

  • Direction::BIDIR: Wire has multiple drivers, allowing signals to travel either way along the wire.

  • Direction::NONE: Node does not have a direction, such as IPIN/OPIN.

inline const std::string &node_direction_string(RRNodeId node) const

Return a string representing the direction of the specified node.

inline float node_C(RRNodeId node) const

Return the capacitance of a specified node.

inline float node_R(RRNodeId node) const

Return the resistance of a specified node.

inline int16_t node_rc_index(RRNodeId node) const

Return the rc_index of a specified node.

inline t_edge_size node_fan_in(RRNodeId node) const

Return the fan in count of a specified node.

inline short node_xlow(RRNodeId node) const

Return the minimum x-coordinate of a specified node.

inline short node_xhigh(RRNodeId node) const

Return the maximum x-coordinate of a specified node.

inline short node_ylow(RRNodeId node) const

Return the minimum y-coordinate of a specified node.

inline short node_yhigh(RRNodeId node) const

Return the maximum y-coordinate of a specified node.

inline char node_layer_high(RRNodeId node) const

Returns the highest layer where a node is located at.

inline char node_layer_low(RRNodeId node) const

Returns the lowest layer where a node is located at.

inline short node_bend_start(RRNodeId node) const

Return the bend start of a specified node.

Parameters:

node – The node id

Returns:

The bend start

inline short node_bend_end(RRNodeId node) const

Return the bend end of a specified node.

Parameters:

node – The node id

Returns:

The bend end

inline RREdgeId node_first_edge(RRNodeId node) const

Return the first outgoing edge of a specified node.

inline RREdgeId node_last_edge(RRNodeId node) const

Return the last outgoing edge of a specified node.

inline int node_length(RRNodeId node) const

Return the length (number of grid tile units spanned by the wire, including the endpoints) of a specified node.

Note

node_length() only applies to CHANX or CHANY or CHANZ and is always a positive number

inline bool node_is_initialized(RRNodeId node) const

Check if a routing resource node is initialized.

inline bool chan_nodes_are_adjacent(RRNodeId node1, RRNodeId node2) const

Check if two CHANX, CHANY, or CHANZ nodes are spatially adjacent.

Parameters:

  • node1 – First routing resource node

  • node2 – Second routing resource node

Returns:

true if the nodes are adjacent, false otherwise

inline bool node_is_inside_bounding_box(RRNodeId node, vtr::Rect<int> bounding_box) const

Check if the node is within the bounding box.

Note

To return true, the RRNode must be completely contained within the specified bounding box, with the edges of the bounding box being inclusive.

Parameters:

  • node – the id of the node.

  • bounding_box – a 2D rectangle that defines the bounding area.

inline bool x_in_node_range(int x, RRNodeId node) const

Check if x is within x-range spanned by a specified node, inclusive of its endpoints.

inline bool y_in_node_range(int y, RRNodeId node) const

Check if y is within y-range spanned by a specified node, inclusive of its endpoints.

inline const std::string node_coordinate_to_string(RRNodeId node) const

Return a string containing information about the specified node.

Note

The returned string can contain the following information: type, side, x_low, x_high, y_low, y_high, length, direction, segment_name, layer num

inline bool is_node_on_specific_side(RRNodeId node, e_side side) const

Check whether a routing resource node is on a specific side.

inline const std::vector<e_side> node_sides(RRNodeId node) const

Get the sides where the node locates on.

inline const char *node_side_string(RRNodeId node) const

Return a string representing the side of a routing resource node.

inline RRNodeId virtual_clock_network_root_idx(const char *clock_network_name) const

Return the node id of the clock network virtual sink.

inline bool is_virtual_clock_network_root(RRNodeId id) const

Checks if the specified node is a virtual sink for a clock network.

inline short edge_switch(RRNodeId id, t_edge_size iedge) const

Return the switch id that represents the iedge’th outgoing edge from a specific node.

Parameters:

  • id – the id of the node.

  • iedge – the outgoing edge index of the node.

Returns:

the id of the switch used for the specified edge.

inline short edge_switch(RREdgeId id) const

Returns the associated switch for a given edge.

inline RRNodeId edge_src_node(const RREdgeId edge_id) const

Return the source node for the specified edge.

inline RRNodeId edge_sink_node(RRNodeId id, t_edge_size iedge) const

Return the destination node for the iedge’th edge from specified RRNodeId.

Note

This method should generally not be used, and instead first_edge and last_edge should be used.

Parameters:

  • id – the id of the node

  • iedge – the iedge’th edge of the node

Returns:

destination node id of the specified edge

inline RRNodeId edge_sink_node(RREdgeId edge) const

Return the destination node for the specified edge.

Parameters:

edge – The edge id

Returns:

The destination node id

inline RRNodeId edge_source_node(RRNodeId id, t_edge_size iedge) const

Get the source node for the iedge’th edge from specified RRNodeId.

Note

This method should generally not be used, and instead first_edge and last_edge should be used.

inline bool edge_is_configurable(RRNodeId id, t_edge_size iedge) const

Check if the edge is a configurable edge.

Note

A configurable edge represents a programmable switch between routing resources, which could be

  • a multiplexer

  • a tri-state buffer

  • a pass gate

inline bool edge_is_configurable(RREdgeId edge) const

Check if the edge is a configurable edge.

Parameters:

edge – The edge id

Returns:

True if the edge is configurable, false otherwise

inline t_edge_size num_configurable_edges(RRNodeId node) const

Return the number of configurable edges.

inline t_edge_size num_non_configurable_edges(RRNodeId node) const

Return the number of non-configurable edges.

inline edge_idx_range configurable_edges(RRNodeId node) const

A configurable edge represents a programmable switch between routing resources, which could be.

  • a multiplexer

  • a tri-state buffer

  • a pass gate This API gets ID range for configurable edges. This function is inlined for runtime optimization.

inline edge_idx_range node_configurable_out_edges(RRNodeId node) const

Return ID range for configurable outgoing edges.

inline edge_idx_range non_configurable_edges(RRNodeId node) const

Return ID range for non-configurable edges.

Note

A non-configurable edge represents a hard-wired connection between routing resources, which could be

  • a non-configurable buffer that can not be turned off

  • a short metal connection that can not be turned off

inline edge_idx_range node_non_configurable_out_edges(RRNodeId node) const

Return ID range for non-configurable outgoing edges.

inline vtr::StrongIdRange<RREdgeId> all_edges() const

Returns a range of all edges in the RR Graph. This method does not depend on the edges begin correctly sorted and can be used before partition_edges is called.

inline edge_idx_range node_out_edges(RRNodeId id) const

Return ID range for outgoing edges.

std::vector<RREdgeId> find_edges(RRNodeId src_node, RRNodeId des_node) const

find the edges between two nodes

inline t_edge_size num_edges(RRNodeId node) const

Return the number of edges.

inline int node_ptc_num(RRNodeId node) const

Retrieve the ptc_num of a routing resource node.

Note

ptc_num (Pin, Track, or Class Number) allows for distinguishing overlapping routing elements that occupy the same (x, y) coordinate, ensuring they can be uniquely identified and managed without confusion. For instance, several routing wires or pins might overlap physically, but their ptc_num differentiates them.

Note

The meaning of ptc_num varies depending on the node type (relevant to VPR RRG, may not apply to custom RRGs):

  • CHANX/CHANY: Represents the track ID in routing channels.

  • OPIN/IPIN: Refers to the pin index within the logic block data structure.

  • SOURCE/SINK: Denotes the class ID of a pin, indicating logic equivalence in the logic block data structure.

Warning

This API is highly versatile and should only be used when necessary (e.g., when the node type is unknown). If the node type is known, prefer using more specific APIs such as node_pin_num(), node_track_num(), or node_class_num() based on the node type.

inline int node_pin_num(RRNodeId node) const

Return the pin num of a routing resource node.

Note

This function is intended for logic blocks and should only be used with IPIN or OPIN nodes.

inline int node_track_num(RRNodeId node) const

Return the track num of a routing resource node.

Note

This function should only be used with CHANX or CHANY nodes.

inline int node_class_num(RRNodeId node) const

Return the class num of a routing resource node.

Note

This function should only be used with SOURCE or SINK nodes.

inline RRIndexedDataId node_cost_index(RRNodeId node) const

Return the cost index of a routing resource node.

RRSegmentId node_segment(RRNodeId node) const

Get the segment id which a routing resource node represents. Only applicable to nodes whose type is CHANX or CHANY.

std::vector<RREdgeId> node_in_edges(RRNodeId node) const

Return incoming edges for a given routing resource node Requires build_in_edges() to be called first.

std::vector<RREdgeId> node_configurable_in_edges(RRNodeId node) const

Return configurable incoming edges for a given routing resource node Requires build_in_edges() to be called first.

std::vector<RREdgeId> node_non_configurable_in_edges(RRNodeId node) const

Return non-configurable incoming edges for a given routing resource node Requires build_in_edges() to be called first.

inline const t_segment_inf &rr_segments(RRSegmentId seg_id) const

Return detailed routing segment information of a specified segment.

Note

The routing segments here may not be exactly same as those defined in architecture file. They have been adapted to fit the context of routing resource graphs.

inline size_t num_rr_segments() const

Return the number of rr_segments in the routing resource graph.

inline const vtr::vector<RRSegmentId, t_segment_inf> &rr_segments() const

Return a read-only list of rr_segments for queries from client functions

inline const t_rr_switch_inf &rr_switch_inf(RRSwitchId switch_id) const

Return the switch information that is categorized in the rr_switch_inf with a given id.

Note

rr_switch_inf is created to minimize memory footprint of RRGraph class. While the RRG could contain millions (even much larger) of edges, there are only a limited number of types of switches. Hence, we use a flyweight pattern to store switch-related information that differs only for types of switches (switch type, drive strength, R, C, etc.). Each edge stores the ids of the switch that implements it so this additional information can be easily looked up.

Note

All the switch-related information, such as R, C, should be placed in rr_switch_inf but NOT directly in the edge-related data of RRGraph. If you wish to create a new data structure to represent switches between routing resources, please follow the flyweight pattern by linking your switch ids to edges only!

inline size_t num_rr_switches() const

Return the number of rr_segments in the routing resource graph.

inline const vtr::vector<RRSwitchId, t_rr_switch_inf> &rr_switch() const

Return the rr_switch_inf_ structure for queries from client functions.

inline const RRSpatialLookup &node_lookup() const

Return the fast look-up data structure for queries from client functions.

inline const t_rr_graph_storage &rr_nodes() const

Return the node-level storage structure for queries from client functions.

inline MetadataStorage<int> rr_node_metadata_data() const

Return the metadata of rr nodes.

Warning

The Metadata should stay as an independent data structure than rest of the internal data, e.g., node_lookup!

inline MetadataStorage<std::tuple<int, int, short>> rr_edge_metadata_data() const

Return the metadata of rr edges.

inline bool validate_node(RRNodeId node_id) const

Validate that edge data is partitioned correctly.

Note

This function is used to validate the correctness of the routing resource graph in terms of graph attributes. Strongly recommend to call it when you finish the building a routing resource graph. If you need more advance checks, which are related to architecture features, you should consider to use the check_rr_graph() function or build your own check_rr_graph() function.

inline bool valid_node(RRNodeId node_id) const

Check if the node id is a valid one in storage.

inline bool valid_switch(RRSwitchId switch_id) const

Check if the switch is a valid one in storage.

bool validate_in_edges() const

Validate if all the fan-in edge lists are valid. This function should be called only if build_in_edges() is called before.

size_t in_edges_count() const

Count the number of incoming edges for all the nodes. This function should be called only if build_in_edges() is called before.

RRGraphBuilder

This file defines the RRGraphBuilder data structure which allows data modification on a routing resource graph.

The builder does not own the storage but it serves a virtual protocol for

  • node_storage: store the node list

  • node_lookup: store a fast look-up for the nodes

Note

  • This is the only data structure allowed to modify a routing resource graph

class RRGraphBuilder

Public Functions

t_rr_graph_storage &rr_nodes()

Return a writable object for rr_nodes.

RRSpatialLookup &node_lookup()

Return a writable object for update the fast look-up of rr_node.

MetadataStorage<int> &rr_node_metadata()

Return a writable object for the meta data on the nodes.

Warning

The Metadata should stay as an independent data structure from the rest of the internal data, e.g., node_lookup!

MetadataStorage<std::tuple<int, int, short>> &rr_edge_metadata()

Return a writable object for the meta data on the edge.

vtr::vector<RRNodeId, std::vector<RREdgeId>> &node_in_edge_storage()

Return a writable object for the incoming edge storage.

inline size_t rr_node_metadata_size() const

Return the size for rr_node_metadata.

inline size_t rr_edge_metadata_size() const

Return the size for rr_edge_metadata.

inline vtr::flat_map<int, t_metadata_dict>::const_iterator find_rr_node_metadata(const int &lookup_key) const

Find the node in rr_node_metadata.

inline vtr::flat_map<std::tuple<int, int, short int>, t_metadata_dict>::const_iterator find_rr_edge_metadata(const std::tuple<int, int, short int> &lookup_key) const

Find the edge in rr_edge_metadata.

inline vtr::flat_map<int, t_metadata_dict>::const_iterator end_rr_node_metadata() const

Return the last node in rr_node_metadata.

inline vtr::flat_map<std::tuple<int, int, short int>, t_metadata_dict>::const_iterator end_rr_edge_metadata() const

Return the last edge in rr_edge_metadata.

inline RRSegmentId add_rr_segment(const t_segment_inf &segment_info)

Add a rr_segment to the routing resource graph. Return an valid id if successful.

  • Each rr_segment contains the detailed information of a routing track, which is denoted by a node in CHANX or CHANY type.

It is frequently used by client functions in timing and routability prediction.

inline vtr::vector<RRSegmentId, t_segment_inf> &rr_segments()

Return a writable list of all the rr_segments.

Warning

It is not recommended to use this API unless you have to. The API may be deprecated later, and future APIs will designed to return a specific data from the rr_segments.

inline RRSwitchId add_rr_switch(const t_rr_switch_inf &switch_info)

Add a rr_switch to the routing resource graph. Return an valid id if successful.

  • Each rr_switch contains the detailed information of a routing switch interconnecting two routing resource nodes.

It is frequently used by client functions in timing prediction.

inline vtr::vector<RRSwitchId, t_rr_switch_inf> &rr_switch()

Return a writable list of all the rr_switches.

Warning

It is not recommended to use this API unless you have to. The API may be deprecated later, and future APIs will designed to return a specific data from the rr_switches.

inline void set_node_type(RRNodeId id, e_rr_type type)

Set the type of a node with a given valid id.

RRNodeId create_node(int layer, int x, int y, e_rr_type type, int ptc, e_side side = NUM_2D_SIDES)

Create a new rr_node in the node storage and register it to the node look-up. Return a valid node id if succeed. Otherwise, return an invalid id. This function is currently only used when building the tileable rr_graph.

inline void set_node_name(RRNodeId id, std::string name)

Set the node name with a given valid id.

void add_node_to_all_locs(RRNodeId node)

Add an existing rr_node in the node storage to the node look-up.

The node will be added to the lookup for every side it is on (for OPINs and IPINs) and for every (x,y) location at which it exists (for wires that span more than one (x,y)).

This function requires a valid node which has already been allocated in the node storage, with

  • a valid node id

  • valid geometry information: xlow/ylow/xhigh/yhigh

  • a valid node type

  • a valid node ptc number

  • a valid side (applicable to OPIN and IPIN nodes only)

void clear()

Clear all the underlying data storage.

void reorder_nodes(e_rr_node_reorder_algorithm reorder_rr_graph_nodes_algorithm, int reorder_rr_graph_nodes_threshold, int reorder_rr_graph_nodes_seed)

reorder all the nodes Reordering the rr-graph nodes may be helpful in

  • Increasing cache locality during routing

  • Improving compile time Reorder RRNodeId’s using one of these algorithms:

  • DEGREE_BFS: Order by degree primarily, and BFS traversal order secondarily.

  • RANDOM_SHUFFLE: Shuffle using the specified seed. Great for testing. The DEGREE_BFS algorithm was selected because it had the best performance of seven existing algorithms here: https://github.com/SymbiFlow/vtr-rrgraph-reordering-tool It might be worth further research, as the DEGREE_BFS algorithm is simple and makes some arbitrary choices, such as the starting node. The re-ordering algorithm (DEGREE_BFS) does not speed up the router on most architectures vs. using the node ordering created by the rr-graph builder in VPR, so it is off by default. The other use of this algorithm is for some unit tests; by changing the order of the nodes in the rr-graph before routing we check that no code depends on the rr-graph node order Nonetheless, it does improve performance ~7% for the SymbiFlow Xilinx Artix 7 graph.

NOTE: Re-ordering will invalidate any references to rr_graph nodes, so this should generally be called before creating such references.

inline void set_node_capacity(RRNodeId id, short new_capacity)

Set capacity of this node (number of routes that can use it).

inline void set_node_coordinates(RRNodeId id, short x1, short y1, short x2, short y2)

Set the node coordinate.

inline void set_tileable(bool is_tileable)

Set the tileable flag. This function is used by tileable routing resource graph builder only since the value of this flag is set to false by default.

inline void set_node_bend_start(RRNodeId id, size_t bend_start)

Set the bend start of a node.

Parameters:

  • id – The node id

  • bend_start – The bend start

inline void set_node_bend_end(RRNodeId id, size_t bend_end)

Set the bend end of a node.

Parameters:

  • id – The node id

  • bend_end – The bend end

inline void set_node_ptc_num(RRNodeId id, int new_ptc_num)

The ptc_num carries different meanings for different node types (true in VPR RRG that is currently supported, may not be true in customized RRG) CHANX or CHANY: the track id in routing channels OPIN or IPIN: the index of pins in the logic block data structure SOURCE and SINK: the class id of a pin (indicating logic equivalence of pins) in the logic block data structure.

Note

This API is very powerful and developers should not use it unless it is necessary, e.g the node type is unknown. If the node type is known, the more specific routines, set_node_pin_num(), set_node_track_num()and set_node_class_num(), for different types of nodes should be used.

inline void set_node_layer(RRNodeId id, char layer_low, char layer_high)

Set the layer range where the given node spans.

inline void set_node_pin_num(RRNodeId id, int new_pin_num)

set_node_pin_num() is designed for logic blocks, which are IPIN and OPIN nodes

inline void set_node_track_num(RRNodeId id, int new_track_num)

set_node_track_num() is designed for routing tracks, which are CHANX and CHANY nodes

void add_node_track_num(RRNodeId node, vtr::Point<size_t> node_offset, short track_id)

Add a track id for a given node base on the offset in coordinate, applicable only to CHANX and CHANY nodes. This API is used by tileable routing resource graph generator, which requires each routing track has a different track id depending their location in FPGA fabric.

Parameters:

  • node – The node to add the track id to.

  • node_offset – Location of the portion of the node being considered. It is used to calculate the relative location from the beginning of the node.

  • track_id – The track id to add to the node.

void add_track_node_to_lookup(RRNodeId node)

Update the node_lookup for a track node. This is applicable to tileable routing graph.

inline void set_node_class_num(RRNodeId id, int new_class_num)

set_node_class_num() is designed for routing source and sinks, which are SOURCE and SINK nodes

inline void set_node_mux_num(RRNodeId id, int new_mux_num)

set_node_mux_num() is designed for routing mux nodes

void set_node_ptc_nums(RRNodeId node, const std::vector<int> &ptc_numbers)

Add a list of ptc numbers to a given node. This function is used by rr graph reader only.

bool node_contain_multiple_ptc(RRNodeId node) const

Identify if a node contains multiple ptc numbers. It is used for tileable RR Graph and mainly used by I/O reader only.

inline void set_node_direction(RRNodeId id, Direction new_direction)

Set the node direction; The node direction is only available of routing channel nodes, such as x-direction routing tracks (CHANX) and y-direction routing tracks (CHANY). For other nodes types, this value is not meaningful and should be set to NONE.

void create_edge_in_cache(RRNodeId src, RRNodeId dest, RRSwitchId edge_switch, bool remapped, std::optional<std::string> sw_template_id_ = std::nullopt)

Add a new edge to the cache of edges to be built.

Note

This will not add an edge to storage. You need to call build_edges() after all the edges are cached.

void create_edge(RRNodeId src, RRNodeId dest, RRSwitchId edge_switch, bool remapped)

Add a new edge to the cache of edges to be built.

Note

This will not add an edge to storage! You need to call build_edges() after all the edges are cached!

void build_edges(const bool &uniquify = true)

Allocate and build actual edges in storage. Once called, the cached edges will be uniquified and added to routing resource nodes, while the cache will be empty once build-up is accomplished.

void build_in_edges()

Allocate and build incoming edges for each node. By default, no incoming edges are kept in storage, to be memory efficient Currently, this function is only called when building the tileable rr_graph.

std::vector<RREdgeId> node_in_edges(RRNodeId node) const

Return incoming edges for a given routing resource node Require build_in_edges() to be called first.

inline void set_virtual_clock_network_root_idx(RRNodeId virtual_clock_network_root_idx)

Set the node id for clock network virtual sink.

inline void reserve_edges(size_t num_edges)

Reserve the lists of edges to be memory efficient. This function is mainly used to reserve memory space inside RRGraph, when adding a large number of edges in order to avoid memory fragments.

inline void emplace_back_edge(RRNodeId src, RRNodeId dest, short edge_switch, bool remapped, std::optional<std::string> sw_template_id = std::nullopt)

emplace_back_edge It adds one edge. This method is efficient if reserve_edges was called with the number of edges present in the graph.

Parameters:

remapped – If true, it means the switch id (edge_switch) corresponds to rr switch id. Thus, when the remapped function is called to remap the arch switch id to rr switch id, the edge switch id of this edge shouldn’t be changed. For example, when the intra-cluster graph is built and the rr-graph related to global resources are read from a file, this parameter is true since the intra-cluster switches are also listed in rr-graph file. So, we use that list to use the rr switch id instead of passing arch switch id for intra-cluster edges.

inline void emplace_back()

Append 1 more RR node to the RR graph.

inline void alloc_and_load_edges(const t_rr_edge_info_set *rr_edges_to_create)

alloc_and_load_edges; It adds a batch of edges.

inline void remove_edges(std::vector<RREdgeId> &rr_edges_to_remove)

Removes a given list of RREdgeIds from the RR Graph. This method does not preserve the order of edges. If you’re calling it after partition_edges has been called, you will need to call partition_edges again. This operation is O(#Edges to be removed) and should not be called frequently.

Parameters:

rr_edges_to_remove – list of RREdgeIds to be removed

inline void override_edge_switch(RREdgeId edge_id, RRSwitchId switch_id)

Overrides the associated switch for a given edge by updating the edge to use the passed in switch.

inline void set_node_cost_index(RRNodeId id, RRIndexedDataId new_cost_index)

set_node_cost_index gets the index of cost data in the list of cost_indexed_data data structure It contains the routing cost for different nodes in the RRGraph when used in evaluate different routing paths

inline void set_node_rc_index(RRNodeId id, NodeRCIndex new_rc_index)

Set the rc_index of routing resource node.

inline void add_node_side(RRNodeId id, e_side new_side)

Add the side where the node physically locates on a logic block. Mainly applicable to IPIN and OPIN nodes.

inline void remap_rr_node_switch_indices(const t_arch_switch_fanin &switch_fanin)

It maps arch_switch_inf indices to rr_switch_inf indices.

inline void mark_edges_as_rr_switch_ids()

Marks that edge switch values are rr switch indices.

inline size_t count_rr_switches(const std::vector<t_arch_switch_inf> &arch_switch_inf, t_arch_switch_fanin &arch_switch_fanins)

Counts the number of rr switches needed based on fan in to support mux size dependent switch delays.

inline void unlock_storage()

Unlock storage; required to modify an routing resource graph after edge is read.

Note

This function is used by OpenFPGA and currently doesn’t have any use in VPR code.

inline void reserve_nodes(size_t size)

Reserve the lists of nodes, edges, switches etc. to be memory efficient. This function is mainly used to reserve memory space inside RRGraph, when adding a large number of nodes/edge/switches/segments, in order to avoid memory fragments.

inline void resize_nodes(size_t size)

This function resize node storage to accommodate size RR nodes.

inline void resize_switches(size_t size)

This function resize rr_switch to accommodate size RR Switch.

inline bool validate() const

Validate that edge data is partitioned correctly. This function should be called when all edges in cache are added.

Note

This function is used to validate the correctness of the routing resource graph in terms of graph attributes. Strongly recommend to call it when you finish the building a routing resource graph. If you need more advance checks, which are related to architecture features, you should consider to use the check_rr_graph() function or build your own check_rr_graph() function.

inline void partition_edges()

Sorts edge data such that configurable edges appears before non-configurable edges.

inline void init_fan_in()

Init per node fan-in data. Should only be called after all edges have been allocated.

Note

This is an expensive, O(N), operation so it should be called once you have a complete rr-graph and not called often.

inline void reset_rr_graph_flags()

Disable the flags which would prevent adding adding extra-resources, when flat-routing is enabled, to the RR Graph.

Note

When flat-routing is enabled, intra-cluster resources are added to the RR Graph after global rosources are already added. This function disables the flags which would prevent adding extra-resources to the RR Graph

RRSpatialLookup

This RRSpatialLookup class encapsulates the node-lookup for a routing resource graph.

A data structure built to find the id of an routing resource node (rr_node) given information about its physical position and type. The data structure is mostly needed during building a routing resource graph

The data structure allows users to

  • Update the look-up with new nodes

  • Find the id of a node with given information, e.g., x, y, type etc.

class RRSpatialLookup

Public Functions

RRNodeId find_node(int layer, int x, int y, e_rr_type type, int ptc, e_side side = NUM_2D_SIDES) const

Returns the index of the specified routing resource node.

This routine also performs error checking to make sure the node in question exists.

Note

All ptcs start at 0 and are positive. Depending on what type of resource this is, ptc can be

  • the class number of a common SINK/SOURCE node of grid, starting at 0 and go up to logical_class_inf size - 1 of SOURCEs + SINKs in a grid

  • pin number of an input/output pin of a grid. They would normally start at 0 and go to the number of pins on a block at that (layer,x,y) location

  • track number of a routing wire in a channel. They would normally go from 0 to channel_width - 1 at that (layer,x,y)

Note

An invalid id will be returned if the node does not exist

Note

For segments (CHANX and CHANY) of length > 1, the segment is given an rr_index based on the (layer,x,y) location at which it starts (i.e. lowest (layer,x,y) location at which this segment exists).

Note

The ‘side’ argument only applies to IPIN/OPIN types, and specifies which side of the grid tile the node should be located on. The value is ignored for non-IPIN/OPIN types

Parameters:

  • layer – specified which FPGA die the node is located at (e.g. multi-die(3D) FPGA)

  • (x, y) – is the grid location within the FPGA

  • rr_type – specifies the type of resource,

  • ptc – gives a unique number of resources of that type (e.g. CHANX) at that (layer,x,y).

std::vector<RRNodeId> find_nodes_in_range(int layer, int xlow, int ylow, int xhigh, int yhigh, e_rr_type type, int ptc, e_side side = e_side::NUM_2D_SIDES) const

Returns unique indices of the routing resource nodes in the bounds (xlow, ylow) to (xhigh, yhigh).

Note

This function works by calling find_node() at the coordinates bounded by (xlow, ylow) to (xhigh, yhigh).

Parameters:

  • layer – specifies which FPGA die the node is located at (e.g. multi-die(3D) FPGA)

  • (xlow, ylow) – is the lower left corner of the grid location range to search within the FPGA

  • (xhigh, yhigh) – is the top right corner of the grid location range to search within the FPGA

  • type – specifies the type of resource,

  • ptc – gives a unique number of resources of that type (e.g. CHANX) at that (layer,x,y).

Returns:

nodes A vector of unique nodes within the given bounds which meet the given parameters

std::vector<RRNodeId> find_channel_nodes(int layer, int x, int y, e_rr_type type) const

Returns the indices of the specified routing resource nodes, representing routing tracks in a channel.

Note

  • Return an empty list if there are no routing channel at the given (layer,x,y) location

  • The node list returned only contain valid ids For example, if the 2nd routing track does not exist in a routing channel at (layer,x,y) location, while the 3rd routing track does exist in a routing channel at (layer,x, y) location, the node list will not contain the node for the 2nd routing track, but the 2nd element in the list will be the node for the 3rd routing track

Parameters:

  • layer – specified which FPGA die the node is located at (e.g. multi-die(3D) FPGA)

  • (x, y) – is the coordinate of the routing channel within the FPGA

  • type – specifies the type of routing channel, either x-direction or y-direction

std::vector<RRNodeId> find_nodes_at_all_sides(int layer, int x, int y, e_rr_type rr_type, int ptc) const

Like find_node() but returns all matching nodes on all the sides.

This is particularly useful for getting all instances of a specific IPIN/OPIN at a specific grid tile (layer,x,y).

std::vector<RRNodeId> find_grid_nodes_at_all_sides(int layer, int x, int y, e_rr_type rr_type) const

Returns all matching nodes on all the sides at a specific grid tile (layer,x,y) location.

As this is applicable to grid pins, the type of nodes are limited to SOURCE/SINK/IPIN/OPIN/MUX

void reserve_nodes(int layer, int x, int y, e_rr_type type, int num_nodes, e_side side = TOTAL_2D_SIDES[0])

Reserve the memory for a list of nodes at (layer, x, y) location with given type and side.

void add_node(RRNodeId node, int layer, int x, int y, e_rr_type type, int ptc, e_side side = TOTAL_2D_SIDES[0])

Register a node in the fast spatial lookup.

Note

You must have a valid node id to register the node in the lookup

Note

a node added with this call will not create a node in the rr_graph_storage node list You MUST add the node in the rr_graph_storage so that the node is valid

Parameters:

  • layer – specified which FPGA die the node is located at (e.g. multi-die(3D) FPGA)

  • (x, y) – is the coordinate of the node to be indexable in the fast spatial lookup

  • type – is the type of a node

  • ptc – is a feature number of a node, which can be

    • the class number of a common SINK/SOURCE node of grid,

    • pin index in a tile when type is OPIN/IPIN

    • track index in a routing channel when type is CHANX/CHANY

  • side – is the side of node on the tile, applicable to OPIN/IPIN; it is ignored for other types, and hence has a default set

bool remove_node(RRNodeId node, int layer, int x, int y, e_rr_type type, int ptc, e_side side = TOTAL_2D_SIDES[0])

Remove a node in the fast spatial lookup.

Parameters:

  • layer – specified which FPGA die the node is located at (e.g. multi-die(3D) FPGA)

  • (x, y) – is the coordinate of the node

  • type – is the type of a node

  • ptc – is a feature number of a node, which can be

    • the class number of a common SINK/SOURCE node of grid,

    • pin index in a tile when type is OPIN/IPIN

    • track index in a routing channel when type is CHANX/CHANY

  • side – is the side of node on the tile, applicable to OPIN/IPIN; it is ignored for other types, and hence has a default set

Returns:

success Whether the node was removed successfully. If the function returns false, the node was not in the lookup at the indices provided.

void mirror_nodes(const int layer, const vtr::Point<int> &src_coord, const vtr::Point<int> &des_coord, e_rr_type type, e_side side)

Mirror the last dimension of a look-up, i.e., a list of nodes, from a source coordinate to a destination coordinate.

This function is mostly needed by SOURCE nodes which are indexable in multiple locations. Considering a bounding box (layer, x, y)->(layer, x + width, y + height) of a multi-height and multi-width grid, SOURCE nodes are indexable in any location inside the boundary.

An example of usage:

// Create a empty lookup
RRSpatialLookup rr_lookup;
// Adding other nodes ...
// Copy the nodes whose types are SOURCE at (1, 1) to (1, 2)
rr_lookup.mirror_nodes(vtr::Point<int>(1, 1),
                       vtr::Point<int>(1, 2),
                       SOURCE,
                       TOP);

Note

currently this function only accepts SOURCE nodes. May unlock for the other types depending on needs

void resize_nodes(int layer, int x, int y, e_rr_type type, e_side side)

Resize the given 4 dimensions (layer, x, y, side) of the RRSpatialLookup data structure for the given type.

This function will keep any existing data

Note

Strongly recommend to use when the sizes of dimensions are deterministic

void reorder(const vtr::vector<RRNodeId, RRNodeId> &dest_order)

Reorder the internal look up to be more memory efficient.

void clear()

Clear all the data inside.

rr_graph_utils

This file includes the most-utilized functions that manipulate the RRGraph object.

Functions

std::vector<RRSwitchId> find_rr_graph_switches(const RRGraph &rr_graph, RRNodeId from_node, RRNodeId to_node)

Get switches in a RRGraph starting at from_node and ending at to_node.

Uses RRGraphView::find_edges(), then converts these edges to switch IDs.

Returns:

A vector of switch IDs

vtr::vector<RRNodeId, std::vector<RREdgeId>> get_fan_in_list(const RRGraphView &rr_graph)

This function generates and returns a vector indexed by RRNodeId containing a vector of fan-in edges for each node.

Note

This function is CPU expensive; complexity O(E) where E is the number of edges in rr_graph

void rr_set_sink_locs(const RRGraphView &rr_graph, RRGraphBuilder &rr_graph_builder, const DeviceGrid &grid)

This function sets better locations for SINK nodes.

build_rr_graph() sets the location of SINK nodes to span the entire tile they are in. This function sets the location of SINK nodes to be the average coordinate of the “cluster-edge” IPINs to which they are connected

int seg_index_of_cblock(const RRGraphView &rr_graph, e_rr_type from_rr_type, int to_node)

Returns the segment number (distance along the channel) of the connection box from from_rr_type (CHANX or CHANY) to to_node (IPIN).

int seg_index_of_sblock(const RRGraphView &rr_graph, int from_node, int to_node)

Returns the segment number (distance along the channel) of the switch box from from_node (CHANX or CHANY) to to_node (CHANX or CHANY).

The switch box on the left side of a CHANX segment at (i,j) has seg_index = i-1, while the switch box on the right side of that segment has seg_index = i. CHANY stuff works similarly. Hence the range of values returned is 0 to device_ctx.grid.width()-1 (if from_node is a CHANX) or 0 to device_ctx.grid.height()-1 (if from_node is a CHANY).

bool inter_layer_connections_limited_to_opin(const RRGraphView &rr_graph)

This function checks whether all inter-die connections are form OPINs. Return “true” if that is the case. Can be used for multiple purposes. For example, to determine which type of bounding box to be used to estimate the wire-length of a net.

Parameters:

rr_graph – The routing resource graph

Returns:

limited_to_opin

bool chanx_chany_nodes_are_adjacent(const RRGraphView &rr_graph, RRNodeId node1, RRNodeId node2)

Check if a CHANX and a CHANY node are adjacent, regardless of their order.

This function checks spatial adjacency between a CHANX and CHANY node without assuming any particular input order. If the node types are not one CHANX and one CHANY, an error is thrown.

Parameters:

  • rr_graph – The routing resource graph

  • node1 – One of the nodes (CHANX or CHANY)

  • node2 – The other node (CHANX or CHANY)

Returns:

true if the nodes are spatially adjacent, false otherwise

bool chanxy_chanz_adjacent(const RRGraphView &rr_graph, RRNodeId node1, RRNodeId node2)

Check if a CHANX or CHANY node is adjacent to a CHANZ node.

Note

Exactly one node must be CHANZ; the other must be CHANX or CHANY.

Parameters:

  • rr_graph – The routing resource graph

  • node1 – One of the RR nodes (CHANX, CHANY, or CHANZ)

  • node2 – The other RR node

Returns:

true if spatially adjacent, false otherwise

bool chan_same_type_are_adjacent(const RRGraphView &rr_graph, RRNodeId node1, RRNodeId node2)
std::vector<int> parse_ptc_numbers(const std::string &ptc_str)

Parse the ptc numbers string into a vector of integers.

Parameters:

ptc_str – The ptc numbers string in the format of “ptc1,ptc2,ptc3,…ptcn”.

Returns:

A vector of integers representing the ptc numbers.

std::string node_ptc_number_to_string(const RRGraphView &rr_graph, RRNodeId node)

Convert the ptc numbers of a node to a string.

Parameters:

  • rr_graph – The routing resource graph

  • node – The node id

Returns:

A string representing the ptc numbers of the node in the format of “ptc1,ptc2,ptc3,…ptcn”.