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

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 set_node_coordinates(RRNodeId id, short x1, short y1, short x2, short y2)

Set the node coordinate.

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.