Routing Resource Graph

RRGraphView

class RRGraphView

Public Functions

inline size_t num_nodes() const

Return number of nodes. This function is inlined for runtime optimization.

inline bool empty() const

Is the RR graph currently empty?

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

Returns a range of RREdgeId’s belonging to RRNodeId id. If this range is empty, then RRNodeId id has no edges.

inline t_rr_type node_type(RRNodeId node) const

Get the type of a routing resource node. This function is inlined for runtime optimization.

inline const char *node_type_string(RRNodeId node) const

Get the type string of a routing resource node. This function is inlined for runtime optimization.

inline short node_capacity(RRNodeId node) const

Get the capacity of a routing resource node. This function is inlined for runtime optimization.

inline Direction node_direction(RRNodeId node) const

Get the direction of a routing resource node. This function is inlined for runtime optimization. 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, so signals can 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

Get the direction string of a routing resource node. This function is inlined for runtime optimization.

inline float node_C(RRNodeId node) const

Get the capacitance of a routing resource node. This function is inlined for runtime optimization.

inline float node_R(RRNodeId node) const

Get the resistance of a routing resource node. This function is inlined for runtime optimization.

inline int16_t node_rc_index(RRNodeId node) const

Get the rc_index of a routing resource node. This function is inlined for runtime optimization.

inline t_edge_size node_fan_in(RRNodeId node) const

Get the fan in of a routing resource node. This function is inlined for runtime optimization.

inline short node_xlow(RRNodeId node) const

Get the minimum x-coordinate of a routing resource node. This function is inlined for runtime optimization.

inline short node_xhigh(RRNodeId node) const

Get the maximum x-coordinate of a routing resource node. This function is inlined for runtime optimization.

inline short node_ylow(RRNodeId node) const

Get the minimum y-coordinate of a routing resource node. This function is inlined for runtime optimization.

inline short node_yhigh(RRNodeId node) const

Get the maximum y-coordinate of a routing resource node. This function is inlined for runtime optimization.

inline RREdgeId node_first_edge(RRNodeId node) const

Get the first out coming edge of resource node. This function is inlined for runtime optimization.

inline RREdgeId node_last_edge(RRNodeId node) const

Get the last out coming edge of resource node. This function is inlined for runtime optimization.

inline int node_length(RRNodeId node) const

Get the length (number of grid tile units spanned by the wire, including the endpoints) of a routing resource node. node_length() only applies to CHANX or CHANY and is always a positive number This function is inlined for runtime optimization.

inline bool node_is_initialized(RRNodeId node) const

Check if routing resource node is initialized. This function is inlined for runtime optimization.

inline bool nodes_are_adjacent(RRNodeId chanx_node, RRNodeId chany_node) const

Check if two routing resource nodes are adjacent (must be a CHANX and a CHANY). This function is used for error checking; it checks if two nodes are physically adjacent (could be connected) based on their geometry. It does not check the routing edges to see if they are, in fact, possible to connect in the current routing graph. This function is inlined for runtime optimization.

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

Check if node is within bounding box. To return true, the RRNode must be completely contained within the specified bounding box, with the edges of the bounding box being inclusive. This function is inlined for runtime optimization.

inline bool x_in_node_range(int x, RRNodeId node) const

Check if x is within x-range spanned by the node, inclusive of its endpoints. This function is inlined for runtime optimization.

inline bool y_in_node_range(int y, RRNodeId node) const

Check if y is within y-range spanned by the node, inclusive of its endpoints. This function is inlined for runtime optimization.

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

Get string of information about routing resource node. The string will contain the following information. type, side, x_low, x_high, y_low, y_high, length, direction, segment_name This function is inlined for runtime optimization.

inline bool is_node_on_specific_side(RRNodeId node, e_side side) const

Check whether a routing node is on a specific side. This function is inlined for runtime optimization.

inline const char *node_side_string(RRNodeId node) const

Get the side string of a routing resource node. This function is inlined for runtime optimization.

inline short edge_switch(RRNodeId id, t_edge_size iedge) const

Get the switch id that represents the iedge’th outgoing edge from a specific node TODO: We may need to revisit this API and think about higher level APIs, like switch_delay()

inline RRNodeId edge_sink_node(RRNodeId id, t_edge_size iedge) const

Get the destination node for the iedge’th edge from specified RRNodeId. 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

Detect if the edge is a configurable edge (controlled by a programmable routing multipler or a tri-state switch).

inline t_edge_size num_configurable_edges(RRNodeId node) const

Get the number of configurable edges. This function is inlined for runtime optimization.

inline t_edge_size num_non_configurable_edges(RRNodeId node) const

Get the number of non-configurable edges. This function is inlined for runtime optimization.

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 non_configurable_edges(RRNodeId node) const

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 This API gets ID range for non-configurable edges. This function is inlined for runtime optimization.

inline edge_idx_range edges(const RRNodeId &id) const

Get outgoing edges for a node. This API is designed to enable range-based loop to walk through the outgoing edges of a node Example: RRGraphView rr_graph; // A dummny rr_graph for a short example RRNodeId node; // A dummy node for a short example for (RREdgeId edge : rr_graph.edges(node)) { // Do something with the edge }.

inline t_edge_size num_edges(RRNodeId node) const

Get the number of edges. This function is inlined for runtime optimization.

inline short node_ptc_num(RRNodeId node) const

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, node_pin_num(), node_track_num()and node_class_num(), for different types of nodes should be used.

inline short node_pin_num(RRNodeId node) const

Get the pin num of a routing resource node. This is designed for logic blocks, which are IPIN and OPIN nodes. This function is inlined for runtime optimization.

inline short node_track_num(RRNodeId node) const

Get the track num of a routing resource node. This is designed for routing tracks, which are CHANX and CHANY nodes. This function is inlined for runtime optimization.

inline short node_class_num(RRNodeId node) const

Get the class num of a routing resource node. This is designed for routing source and sinks, which are SOURCE and SINK nodes. This function is inlined for runtime optimization.

inline RRIndexedDataId node_cost_index(RRNodeId node) const

Get the cost index of a routing resource node. This function is inlined for runtime optimization.

inline const t_segment_inf &rr_segments(RRSegmentId seg_id) const

Return detailed routing segment information with a given id*.

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 rr_switch_inf is created to minimize memory footprint of RRGraph classs 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

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

inline bool validate_node(RRNodeId node_id) const

brief 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.

RRGraphBuilder

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 than 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.

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.

TODO

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.

TODO

inline void set_node_type(RRNodeId id, t_rr_type type)

Set the type of a node 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_node_ptc_num(RRNodeId id, short 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_pin_num(RRNodeId id, short 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, short new_track_num)

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

inline void set_node_class_num(RRNodeId id, short new_class_num)

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

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.

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 fragements.

inline void emplace_back_edge(RRNodeId src, RRNodeId dest, short edge_switch)

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

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 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 indicies to rr_switch_inf indicies.

inline void mark_edges_as_rr_switch_ids()

Marks that edge switch values are rr switch indicies.

inline size_t count_rr_switches(size_t num_arch_switches, 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 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 fragements.

inline void resize_nodes(size_t size)

This function resize node storage to accomidate size RR nodes.

inline void resize_switches(size_t size)

This function resize rr_switch to accomidate size RR Switch.

inline bool validate() 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 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.

RRSpatialLookup

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 x, int y, t_rr_type type, int ptc, e_side side = NUM_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 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 (x, y) location

  • track number of a routing wire in a channel. They would normally go from 0 to channel_width - 1 at that (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 (x,y) location at which it starts (i.e. lowest (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
  • (x, y) – are 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 (x,y).

std::vector<RRNodeId> find_channel_nodes(int x, int y, t_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 (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 (x, y) location, while the 3rd routing track does exist in a routing channel at (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
  • (x, y) – are the coordinate of the routing channel within the FPGA

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

std::vector<RRNodeId> find_nodes_at_all_sides(int x, int y, t_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 (x,y) location.

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

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

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

void reserve_nodes(int x, int y, t_rr_type type, int num_nodes, e_side side = SIDES[0])

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

void add_node(RRNodeId node, int x, int y, t_rr_type type, int ptc, e_side side = SIDES[0])

Register a node in the fast look-up.

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
  • (x, y) – are the coordinate of the node to be indexable in the fast look-up

  • 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

void mirror_nodes(const vtr::Point<int> &src_coord, const vtr::Point<int> &des_coord, t_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 need by SOURCE and SINK nodes which are indexable in multiple locations. Considering a bounding box (x, y)->(x + width, y + height) of a multi-height and multi-width grid, SOURCE and SINK nodes are indexable in any location inside the boundry.

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/SINK nodes. May unlock for the other types depending on needs

void resize_nodes(int x, int y, t_rr_type type, e_side side)

Resize the given 3 dimensions (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.