Route Tree¶

RouteTree¶

Overview¶

A RouteTree holds a root RouteTreeNode and exposes top level operations on the tree, such as RouteTree::update_from_heap() and RouteTree::prune().

Routing itself is not done using this representation. The route tree is pushed to the heap with ConnectionRouterInterface::timing_driven_route_connection_from_route_tree() and the newly found path is committed via RouteTree::update_from_heap(). The timing data is updated with RouteTree::reload_timing() where required.

Each net in the netlist given to the router has a single RouteTree, which is kept in RoutingContext::route_trees.

Usage¶

A RouteTree either requires a RRNodeId or a ParentNetId (as the source node) to construct:

 RouteTree tree(inet);
 // ...

RouteTrees cannot be manually updated. The only way to extend them is to first route a connection and then update from the resulting heap.

 std::tie(found_path, cheapest) = router.timing_driven_route_connection_from_route_tree(tree.root(), ...);
 if (found_path)
      std::tie(std::ignore, rt_node_of_sink) = tree.update_from_heap(&cheapest, ...);

Congested paths in a tree can be pruned using RouteTree::prune(). This is done between iterations to keep only the legally routed section. Note that updates to a tree require an update to the global occupancy state via pathfinder_update_cost_from_route_tree(). RouteTree::prune() depends on this global data to find congestions, so the flow to prune a tree is somewhat convoluted:

 RouteTree tree2 = tree;
 // Prune the copy (using congestion data before subtraction)
 vtr::optional<RouteTree&> pruned_tree2 = tree2.prune(connections_inf);

 // Subtract congestion using the non-pruned original
 pathfinder_update_cost_from_route_tree(tree.root(), -1);

 if (pruned_tree2) {  // Partially pruned
     // Add back congestion for the pruned route tree
     pathfinder_update_cost_from_route_tree(pruned_tree2.value().root(), 1);
     ...
 } else {  // Fully destroyed
     ...

Most usage of RouteTree outside of the router requires iterating through existing routing. Both RouteTree and RouteTreeNode exposes functions to traverse the tree.

To iterate over all nodes in the tree:

 RouteTree& tree = route_ctx.route_trees[inet].value();

 for (auto& node: tree.all_nodes()) {
     // ...
 }

This will walk the tree in depth-first order. Breadth-first traversal would require recursion:

 const RouteTreeNode& root = tree.root();

 for (auto& child: root.child_nodes()) {
     // recurse...
 }

To walk a node’s subtree in depth-first order:

 for (auto& node: root.all_nodes()) {  // doesn't include root!
     // ...   
 }

RouteTree::find_by_rr_id() finds the RouteTreeNode for a given RRNodeId. Note that RRNodeId isn’t a unique key for SINK nodes and therefore an external lookup (generated from sink nodes returned by RouteTree::update_from_heap()) or a search may be required to find a certain SINK.

When the occupancy and timing data is up to date, a tree can be sanity checked using RouteTree::is_valid().

class RouteTree¶

Top level route tree used in timing analysis and keeping routing state.

Contains the root node and a lookup from RRNodeIds to RouteTreeNode&s in the tree.

Public Functions

RouteTree(RRNodeId inode)¶: Return a RouteTree initialized to inode. Note that prune() won’t work on a RouteTree initialized this way (see _net_id comments)

RouteTree(ParentNetId inet)¶: Return a RouteTree initialized to the source of nets[inet]. Use this constructor where possible (needed for prune() to work)

std::tuple<vtr::optional<const RouteTreeNode&>, vtr::optional<const RouteTreeNode&>> update_from_heap(RTExploredNode *hptr, int target_net_pin_index, SpatialRouteTreeLookup *spatial_rt_lookup, bool is_flat)¶

Add the most recently finished wire segment to the routing tree, and update the Tdel, etc. numbers for the rest of the routing tree. hptr is the heap pointer of the SINK that was reached, and target_net_pin_index is the net pin index corresponding to the SINK that was reached. This routine returns a tuple: RouteTreeNode of the branch it adds to the route tree and RouteTreeNode of the SINK it adds to the routing. Locking operation: only one thread can update_from_heap() a RouteTree at a time.

Add the most recently finished wire segment to the routing tree, and update the Tdel, etc. numbers for the rest of the routing tree. hptr is the pointer of the SINK that was reached/explored, and target_net_pin_index is the net pin index corresponding to the SINK that was reached. Usually target_net_pin_index is a non-negative integer indicating the netlist connection being routed, but it can be OPEN (-1) to indicate this is a routing path to a virtual sink which we use when routing to the source of dedicated clock networks. This routine returns a tuple: RouteTreeNode of the branch it adds to the route tree and RouteTreeNode of the SINK it adds to the routing.

void reload_timing(vtr::optional<RouteTreeNode&> from_node = vtr::nullopt)¶

Reload timing values (R_upstream, C_downstream, Tdel). Can take a RouteTreeNode& to do an incremental update. Note that update_from_heap already does this, but prune() doesn’t. Locking operation: only one thread can reload_timing() for a RouteTree at a time.

Reload timing values (R_upstream, C_downstream, Tdel). Can take a RouteTreeNode& to do an incremental update. Note that update_from_heap already calls this.

vtr::optional<const RouteTreeNode&> find_by_rr_id(RRNodeId rr_node) const¶: Get the RouteTreeNode corresponding to the RRNodeId. Returns nullopt if not found. SINK nodes may be added to the tree multiple times. In that case, this will return the last one added. Use find_by_isink for a more accurate lookup.

inline vtr::optional<const RouteTreeNode&> find_by_isink(int isink) const¶: Get the sink RouteTreeNode associated with the isink. Will probably segfault if the tree is not constructed with a ParentNetId.

inline constexpr size_t num_sinks(void) const¶: Get the number of sinks in associated net.

bool is_valid(void) const¶

Check the consistency of this route tree. Looks for:

invalid parent-child links
invalid timing values
congested SINKs Returns true if OK.

bool is_uncongested(void) const¶

Check if the tree has any overused nodes (-> the tree is congested). Returns true if not congested.

Check if the tree has any overused nodes (-> the tree is congested). Returns true if not congested

void print(void) const¶: Print information about this route tree to stdout.

vtr::optional<RouteTree&> prune(CBRR &connections_inf, std::vector<int> *non_config_node_set_usage = nullptr)¶

Prune overused nodes from the tree. Also prune unused non-configurable nodes if non_config_node_set_usage is provided (see get_non_config_node_set_usage) Returns nullopt if the entire tree is pruned. Locking operation: only one thread can prune() a RouteTree at a time.

Prune a route tree of illegal branches - when there is at least 1 congested node on the path to a sink Returns nullopt if the entire tree has been pruned. Updates “is_isink_reached” lookup! After prune(), if a sink is marked as reached in the lookup, it is reached legally.

Note: does not update R_upstream/C_downstream

void freeze(void)¶

Remove all sinks and mark the remaining nodes as un-expandable. This is used after routing a clock net. TODO: is this function doing anything? Try running without it Locking operation: only one thread can freeze() a RouteTree at a time.

Remove all sinks and mark the remaining nodes as un-expandable. This is used after routing a clock net. TODO: is this function doing anything? Try running without it

std::vector<int> get_non_config_node_set_usage(void) const¶: Count configurable edges to non-configurable node sets. (rr_nonconf_node_sets index -> int) Required when using prune() to remove non-configurable nodes.

inline constexpr iterable all_nodes(void) const¶: Get an iterable for all nodes in this RouteTree.

inline constexpr const RouteTreeNode &root(void) const¶: Get a reference to the root RouteTreeNode.

inline constexpr const vtr::dynamic_bitset &get_is_isink_reached(void) const¶: Get a lookup which contains the “isink reached state”. It’s a 1-indexed! bitset of “pin indices”. True if the nth sink has been reached, false otherwise. If you call it before prune() and after routing, there’s no guarantee on whether the reached sinks are reached legally. Another catch is that vtr::dynamic_bitsets don’t know their size, so keep tree.num_sinks()+1 as a limit when iterating over this.

inline constexpr reached_isink_range get_reached_isinks(void) const¶: Get reached isinks: 1-indexed pin indices enumerating the sinks in this net. “Reached” means “reached legally” if you call this after prune() and not before any routing. Otherwise it doesn’t guarantee legality. Builds and returns a value: use get_is_isink_reached directly if you want speed.

inline constexpr remaining_isink_range get_remaining_isinks(void) const¶: Get remaining (not routed (legally?)) isinks: 1-indexed pin indices enumerating the sinks in this net. Caveats in get_reached_isinks() apply.

template<bool sink_state> class IsinkIterator¶: Iterator implementation for remaining or reached isinks. Goes over [1..num_sinks] and only returns a value when the sink state is right

RouteTreeNode¶

class RouteTreeNode¶

A single route tree node.

Structure describing one node in a RouteTree.

Public Functions

RouteTreeNode(RRNodeId inode, RRSwitchId parent_switch, RouteTreeNode *parent)¶: This struct makes little sense outside the context of a RouteTree. This constructor is only public for compatibility purposes.

inline constexpr iterable<const RouteTreeNode&> child_nodes(void) const¶: Traverse child nodes.

inline constexpr vtr::optional<const RouteTreeNode&> parent(void) const¶: Get parent node if exists. (nullopt if not)

inline constexpr rec_iterable<const RouteTreeNode&> all_nodes(void) const¶: Traverse the subtree under this node in depth-first order. Doesn’t include this node.

void print(void) const¶: Print information about this subtree to stdout.

inline constexpr bool is_leaf(void) const¶

Is this node a leaf?

True if the next node after this is not its child (we jumped up to the next branch) or if it’s null. The RouteTree functions keep the books for this.

Public Members

RRNodeId inode¶: ID of the rr_node that corresponds to this node.

RRSwitchId parent_switch¶: Switch type driving this node (by its parent).

bool re_expand¶: Should this node be put on the heap as part of the partial routing to act as a source for subsequent connections?

float Tdel¶: Time delay for the signal to get from the net source to this node. Includes the time to go through this node.

float R_upstream¶: Total upstream resistance from this node to the net source, including any device_ctx.rr_nodes[].R of this node.

float C_downstream¶: Total downstream capacitance from this node. That is, the total C of the subtree rooted at the current node, including the C of the current node.

int net_pin_index¶: Net pin index associated with the node. This value ranges from 1 to fanout [1..num_pins-1]. For cases when different speed paths are taken to the same SINK for different pins, inode cannot uniquely identify each SINK, so the net pin index guarantees an unique identification for each SINK node. For non-SINK nodes and for SINK nodes with no associated net pin index, (i.e. special SINKs like the source of a clock tree which do not correspond to an actual netlist connection), the value for this member should be set to OPEN (-1).

Friends

inline friend bool operator==(const RouteTreeNode &lhs, const RouteTreeNode &rhs)¶: Equality operator. For now, just compare the addresses

template<class Iterator> class Iterable¶: Provide begin and end fns when iterating on this tree. .child_nodes() returns Iterable<RTIterator> while .all_nodes() returns Iterable<RTRecIterator>

template<class ref> class RTIterator¶: Iterator implementation for child_nodes(). Walks using _next_sibling ptrs. At the end of the child list, the ptr points up to where the parent’s subtree ends, so we know where to stop

template<class ref> class RTRecIterator¶: Recursive iterator implementation for a RouteTreeNode. This walks over all child nodes of a given node without a stack or recursion: we keep the nodes in depth-first order in the linked list managed by RouteTree. Nodes know where their subtree ends, so we can just walk the _next ptrs until we find that

RTExploredNode¶

class RTExploredNode¶

Each RTExploredNode element stores the node states for the connection router and represents a partial route.

Note

Only index, prev_edge, and rcv_path_backward_delay fields are used as the return value outside the connection router.

Public Members

float total_cost = std::numeric_limits<float>::infinity()¶: The cost used to sort heap. For the timing-driven router this is the backward_path_cost plus the expected cost to the target.

float backward_path_cost = std::numeric_limits<float>::infinity()¶: The “known” cost of the path up to and including this node.

float R_upstream = std::numeric_limits<float>::infinity()¶: Stores the upstream resistance to ground from this node in the path search (connection routing), including the resistance of the node itself (device_ctx.rr_nodes[index].R).

t_heap_path *path_data = nullptr¶: Structure to handle extra RCV structures. Managed by PathManager class.

RRNodeId index = RRNodeId::INVALID()¶: The RR node index associated with the costs/R_upstream values. Outside the connection router, this field is mainly used in RouteTree::update_from_heap and RouteTree::add_subtree_from_heap. Inside the connection router, this is used as part of the node info passed as a parameter of some member functions.

RREdgeId prev_edge = RREdgeId::INVALID()¶: The edge from the previous node used to reach the current. Same usage as the index field described above.

float rcv_path_backward_delay = std::numeric_limits<float>::infinity()¶: The delay of the partial path plus the path from route tree to source. Needed by RCV. Set to infinity if RCV is disabled. This field is used as part of the return value of the route routine, derived from the path_data pointer (but not using path_data for returning to avoid issues with dynamic memory management).