Routing Resource Graph

RRGraphView

class RRGraphView

Public Functions

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 const t_segment_inf &rr_segments(RRSegmentId seg_id) 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. 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 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 RRSpatialLookup &node_lookup() const

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

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 &node_storage()

Return a writable object for rr_nodes.

RRSpatialLookup &node_lookup()

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

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.

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 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)

This function reserve storage for RR nodes.

inline void resize_nodes(size_t size)

This function resize node storage to accomidate size RR nodes.

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

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.