Connection Router

ConnectionRouter

This file defines the ConnectionRouter class.

Overview

The ConnectionRouter represents the timing-driven connection routers, which route from some initial set of sources (via the input rt tree) to a particular sink. VPR supports two timing-driven connection routers, including the serial connection router and the MultiQueue-based parallel connection router. This class defines the interface for the two connection routers and encapsulates the common member variables and helper functions for them.

Note

When the ConnectionRouter is used, it mutates the provided rr_node_route_inf. The routed path can be found by tracing from the sink node (which is returned) through the rr_node_route_inf. See update_traceback as an example of this tracing.

template<typename HeapImplementation>
class ConnectionRouter : public ConnectionRouterInterface
#include <connection_router.h>

interface for the serial and parallel connection routers and encapsulates the common variables and helper functions for the two routers

Subclassed by SerialConnectionRouter< DAryHeap >, SerialConnectionRouter< HeapImplementation >

Public Functions

inline ConnectionRouter(const DeviceGrid &grid, const RouterLookahead &router_lookahead, const t_rr_graph_storage &rr_nodes, const RRGraphView *rr_graph, const std::vector<t_rr_rc_data> &rr_rc_data, const vtr::vector<RRSwitchId, t_rr_switch_inf> &rr_switch_inf, vtr::vector<RRNodeId, t_rr_node_route_inf> &rr_node_route_inf, bool is_flat, int route_verbosity)
inline virtual ~ConnectionRouter()
virtual void clear_modified_rr_node_info() = 0

Clears the modified list.

Note

Should be called after reset_path_costs have been called

virtual void reset_path_costs() = 0

Resets modified data in rr_node_route_inf based on modified_rr_node_inf.

virtual std::tuple<bool, bool, RTExploredNode> timing_driven_route_connection_from_route_tree(const RouteTreeNode &rt_root, RRNodeId sink_node, const t_conn_cost_params &cost_params, const t_bb &bounding_box, RouterStats &router_stats, const ConnectionParameters &conn_params) final

Finds a path from the route tree rooted at rt_root to sink_node.

Note

This is used when you want to allow previous routing of the same net to serve as valid start locations for the current connection.

Parameters:

  • rt_root – RouteTreeNode describing the current routing state

  • sink_node – Sink node ID to route to

  • cost_params – Cost function parameters

  • bounding_box – Keep search confined to this bounding box

  • router_stats – Update router statistics

  • conn_params – Parameters to guide the routing of the given connection

Returns:

A tuple of:

  • bool: path exists? (hard failure, rr graph disconnected)

  • bool: should retry with full bounding box? (only used in parallel routing)

  • RTExploredNode: the explored sink node, from which the cheapest path can be found via back-tracing

virtual std::tuple<bool, bool, RTExploredNode> timing_driven_route_connection_from_route_tree_high_fanout(const RouteTreeNode &rt_root, RRNodeId sink_node, const t_conn_cost_params &cost_params, const t_bb &net_bounding_box, const SpatialRouteTreeLookup &spatial_rt_lookup, RouterStats &router_stats, const ConnectionParameters &conn_params) final

Finds a path from the route tree rooted at rt_root to sink_node for a high fanout net.

Note

Unlike timing_driven_route_connection_from_route_tree(), only part of the route tree which is spatially close to the sink is added to the heap.

Parameters:

  • rt_root – RouteTreeNode describing the current routing state

  • sink_node – Sink node ID to route to

  • cost_params – Cost function parameters

  • net_bounding_box – Keep search confined to this bounding box

  • spatial_rt_lookup – Route tree spatial lookup

  • router_stats – Update router statistics

  • conn_params – Parameters to guide the routing of the given connection

Returns:

A tuple of:

  • bool: path exists? (hard failure, rr graph disconnected)

  • bool: should retry with full bounding box? (only used in parallel routing)

  • RTExploredNode: the explored sink node, from which the cheapest path can be found via back-tracing

virtual vtr::vector<RRNodeId, RTExploredNode> timing_driven_find_all_shortest_paths_from_route_tree(const RouteTreeNode &rt_root, const t_conn_cost_params &cost_params, const t_bb &bounding_box, RouterStats &router_stats, const ConnectionParameters &conn_params) = 0

Finds shortest paths from the route tree rooted at rt_root to all sinks available.

Note

Unlike timing_driven_route_connection_from_route_tree(), only part of the route tree which is spatially close to the sink is added to the heap.

Note

If cost_params.astar_fac is set to 0, this effectively becomes Dijkstra’s algorithm with a modified exit condition (runs until heap is empty). When using cost_params.astar_fac = 0, for efficiency the RouterLookahead used should be the NoOpLookahead.

Note

This routine is currently used only to generate information that may be helpful in debugging an architecture.

Parameters:

  • rt_root – RouteTreeNode describing the current routing state

  • cost_params – Cost function parameters

  • bounding_box – Keep search confined to this bounding box

  • router_stats – Update router statistics

  • conn_params – Parameters to guide the routing of the given connection

Returns:

A vector where each element is a reachable sink

inline virtual void set_router_debug(bool router_debug) final

Sets router debug option.

Parameters:

router_debug – Router debug option

inline virtual void empty_rcv_route_tree_set() final

Empties the route tree set used for RCV node detection.

Note

Will immediately return if RCV is disabled. Called after each net is finished routing to flush the set.

virtual void set_rcv_enabled(bool enable) = 0

Enables or disables RCV in connection router.

Note

Enabling this will utilize extra path structures, as well as the RCV cost function. Ensure route budgets have been calculated before enabling this.

Parameters:

enable – Whether enabling RCV or not

Protected Functions

bool timing_driven_route_connection_common_setup(const RouteTreeNode &rt_root, RRNodeId sink_node, const t_conn_cost_params &cost_params, const t_bb &bounding_box)

Common logic from timing_driven_route_connection_from_route_tree and timing_driven_route_connection_from_route_tree_high_fanout for running the connection router.

Parameters:

  • rt_root – RouteTreeNode describing the current routing state

  • sink_node – Sink node ID to route to

  • cost_params – Cost function parameters

  • bounding_box – Keep search confined to this bounding box

Returns:

bool signal to retry this connection with a full-device bounding box

void timing_driven_route_connection_from_heap(RRNodeId sink_node, const t_conn_cost_params &cost_params, const t_bb &bounding_box)

Finds a path to sink_node, starting from the elements currently in the heap.

Note

If the path is not found, which means that the path_cost of sink_node in RR node route info has never been updated, rr_node_route_inf_[sink_node].path_cost will be the initial value (i.e., float infinity). This case can be detected by std::isinf(rr_node_route_inf_[sink_node].path_cost).

Note

This is the core maze routing routine. For understanding the connection router, start here.

Parameters:

  • sink_node – Sink node ID to route to

  • cost_params – Cost function parameters

  • bounding_box – Keep search confined to this bounding box

virtual void timing_driven_find_single_shortest_path_from_heap(RRNodeId sink_node, const t_conn_cost_params &cost_params, const t_bb &bounding_box, const t_bb &target_bb) = 0

Finds the single shortest path from current heap to the sink node in the RR graph.

Parameters:

  • sink_node – Sink node ID to route to

  • cost_params – Cost function parameters

  • bounding_box – Keep search confined to this bounding box

  • target_bb – Prune IPINs that lead to blocks other than the target block

virtual vtr::vector<RRNodeId, RTExploredNode> timing_driven_find_all_shortest_paths_from_heap(const t_conn_cost_params &cost_params, const t_bb &bounding_box) = 0

Finds shortest paths from current heap to all nodes in the RR graph.

Parameters:

  • cost_params – Cost function parameters

  • bounding_box – Keep search confined to this bounding box

Returns:

A vector where each element contains the shortest route to a specific sink node

virtual void add_route_tree_node_to_heap(const RouteTreeNode &rt_node, RRNodeId target_node, const t_conn_cost_params &cost_params, const t_bb &net_bb) = 0

Unconditionally adds rt_node to the heap.

Todo:

Consider moving this function into the ConnectionRouter class after checking the different prune functions of the serial and parallel connection routers.

Note

If you want to respect rt_node->re_expand that is the caller’s responsibility.

Parameters:

  • rt_node – RouteTreeNode to be added to the heap

  • target_node – Target node ID to route to

  • cost_params – Cost function parameters

  • net_bb – Do not push to heap if not in bounding box

void evaluate_timing_driven_node_costs(RTExploredNode *to, const t_conn_cost_params &cost_params, RRNodeId from_node, RRNodeId target_node)

Calculates the cost of reaching to_node.

Parameters:

  • to – Neighbor node to calculate costs before being expanded

  • cost_params – Cost function parameters

  • from_node – Current node ID being explored

  • target_node – Target node ID to route to

float compute_node_cost_using_rcv(const t_conn_cost_params cost_params, RRNodeId to_node, RRNodeId target_node, float backwards_delay, float backwards_cong, float R_upstream)

Evaluate node costs using the RCV algorithm.

Parameters:

  • cost_params – Cost function parameters

  • to_node – Neighbor node to calculate costs before being expanded

  • target_node – Target node ID to route to

  • backwards_delay – “Known” delay up to and including to_node

  • backwards_cong – “Known” congestion up to and including to_node

  • R_upstream – Upstream resistance to ground from to_node

Returns:

Node cost using RCV

void add_route_tree_to_heap(const RouteTreeNode &rt_node, RRNodeId target_node, const t_conn_cost_params &cost_params, const t_bb &net_bb)

Adds the route tree rooted at rt_node to the heap, preparing it to be used as branch-points for further routing.

Parameters:

  • rt_node – RouteTreeNode to be added to the heap

  • target_node – Target node ID to route to

  • cost_params – Cost function parameters

  • net_bb – Do not push to heap if not in bounding box

t_bb add_high_fanout_route_tree_to_heap(const RouteTreeNode &rt_root, RRNodeId target_node, const t_conn_cost_params &cost_params, const SpatialRouteTreeLookup &spatial_route_tree_lookup, const t_bb &net_bounding_box)

For high fanout nets, adds only route tree nodes which are spatially close to the sink.

Parameters:

  • rt_root – RouteTreeNode to be added to the heap

  • target_node – Target node ID to route to

  • cost_params – Cost function parameters

  • spatial_route_tree_lookup – Route tree spatial lookup

  • net_bounding_box – Do not push to heap if not in bounding box

Protected Attributes

const DeviceGrid &grid_

Device grid

const RouterLookahead &router_lookahead_

Router lookahead

const t_rr_graph_view rr_nodes_

RR node data

const RRGraphView *rr_graph_

RR graph

vtr::array_view<const t_rr_rc_data> rr_rc_data_

RR node resistance/capacitance data

vtr::array_view<const t_rr_switch_inf> rr_switch_inf_

RR switch data

const vtr::vector<ParentNetId, std::vector<std::vector<int>>> &net_terminal_groups

Net terminal groups

const vtr::vector<ParentNetId, std::vector<int>> &net_terminal_group_num
vtr::vector<RRNodeId, t_rr_node_route_inf> &rr_node_route_inf_

RR node extra information needed during routing

bool is_flat_

Is flat router enabled or not?

int route_verbosity_

The verbosity of log messages in the router.

RouterStats *router_stats_

Router statistics (e.g., heap push/pop counts)

const ConnectionParameters *conn_params_

Parameters to guide the routing of the given connection

HeapImplementation heap_

Templated heap instance (e.g., binary heap, 4-ary heap, MultiQueue-based parallel heap)

bool router_debug_

Router debug option

std::chrono::microseconds path_search_cumulative_time

Cumulative time spent in the path search part of the connection router

PathManager rcv_path_manager

The path manager for RCV, keeps track of the route tree as a set, also manages the allocation of rcv_path_data.

vtr::vector<RRNodeId, t_heap_path*> rcv_path_data

SerialConnectionRouter

template<typename HeapImplementation>
class SerialConnectionRouter : public ConnectionRouter<HeapImplementation>

AIR’s serial timing-driven connection router

This class routes from some initial set of sources (via the input rt tree) to a particular sink using single thread.

ParallelConnectionRouter

template<typename HeapImplementation>
class ParallelConnectionRouter : public ConnectionRouter<MultiQueueDAryHeap<HeapImplementation::arg_D>>

MultiQueue-based parallel connection router (FPT’24) based on the ConnectionRouter interface.

The details of the algorithm can be found from the conference paper: A. Singer, H. Yan, G. Zhang, M. Jeffrey, M. Stojilovic and V. Betz, “MultiQueue-Based FPGA Routing:

Relaxed A* Priority Ordering for Improved Parallelism,” Int. Conf. on Field-Programmable Technology, Dec. 2024.