Dashboard for RRGraph API refactoring status

[tangxifan]

Motivation of Refactoring effort

A detailed technical plan can be found at link

The overall refactoring effort aims to

• create a unified data structure RRGraphView as a centralized storage for all the routing resource graph -related information. See Fig. 1
• create a set of frame view object from the centralized storage RRGraph for client functions, which are suitable for rr_graph builder, placer, router, GUI, timing analyzer etc. See Fig. 2.
• This is to avoid massive updates to the codes of client functions when there is a change on the unified data structure.
• Also it avoid large memory footprint for client functions, since each client function may only use a small portion (typically <50%) APIs of the unified object.

Fig. 1 Illustration of the relationship between data structures

Fig. 2 Different levels of frame views of routing resource graphs to satisfy various needs from client functions.

The result/benefits of the refactoring efforts is

• The routing resource graph can be decoupled from VPR's core engine as a library. Unit tests can be enabled
• It is much easier for developers to develop custom routing resource graph builders thanks to the APIs of the unified data structure RRGraph. A routing resource graph builder can be a library, decoupled from VPR's core engine. Many checking codes can be efficiently merged into the data structure and developers can save a lot of efforts in writing the atom-level sanity checks.
• Ensure that each client functions have a clean view of the routing resource graph, i.e. RRGraphView. In other words, routing resource graph will be read-only and only accessors are exposed to client functions. Developers have no worries on developing their own placer/router etc.

Checklist

RRGraphBuilder API to be refactored:

• set_node_type() Add a new API set_node_type() to RRGraphBuilder #1847
• set_node_ptc_num() Add a new API set_node_x_num() to RRGraphBuilder #1872
• set_node_pin_num() Add a new API set_node_x_num() to RRGraphBuilder #1872
• set_node_track_num() Add a new API set_node_x_num() to RRGraphBuilder #1872
• set_node_class_num() Add a new API set_node_x_num() to RRGraphBuilder #1872
• set_node_coordinates() Add a new API set_node_coordinates() to RRGraphBuilder #1853
• set_node_cost_index() Add a new API set_node_cost_index() to RRGraphBuilder #1884
• set_node_rc_index() Add a new API set_node_rc_index() to RRGraphBuilder  #1887
• set_node_capacity() Add a new API set_node_capacity() to RRGraphBuilder #1855
• set_node_direction() Add a new API set_node_direction() to RRGraphBuilder #1856
• add_node_side() Add a new API add_node_side() to RRGraphBuilder #1889
• reserve_nodes() Add a new APIs reserve_nodes() and resize_nodes to RRGraphBuilder #1905
• resize_nodes() Add a new APIs reserve_nodes() and resize_nodes to RRGraphBuilder #1905
• add_node() Removed because it is not currently used in rr_graph builder; Will think it later.
• reserve_edges() Add a new APIs reserve_edges(), emplace_back_edges() and alloc_and_load_edges() to RRGraphBuilder #1892
• emplace_back_edges() Add a new APIs reserve_edges(), emplace_back_edges() and alloc_and_load_edges() to RRGraphBuilder #1892
• alloc_and_load_edges() Add a new APIs reserve_edges(), emplace_back_edges() and alloc_and_load_edges() to RRGraphBuilder #1892
• count_rr_switches() Add a new API count_rr_switches() to RRGraphBuilder #1896
• remap_rr_node_switch_indices() Add a new API remap_rr_node_switch_indices() to RRGraphBuilder #1897
• make_edges_as_rr_switch_ids() Add a new API make_edges_as_rr_switch_ids() to RRGraphBuilder #1902
• partition_edges() Add a new API partition_edges() to RRGraphBuilder #1900
• init_fan_in() Add a new API init_fan_in() to RRGraphBuilder #1903
• validate() Add a new API validate() to RRGraphBuilder #1899

RRGraphView API to be refactored:

• node_type() RRGraphView::node_type() Implementation #1742
• node_type_string() RRGraphView node_type_string(), node_side_string() Implementation #1873
• node_rc_index() RRGraphView node_R(), node_C(), node_rc_index() Implementation #1816
• node_R() RRGraphView node_R(), node_C(), node_rc_index() Implementation #1816
• node_C() RRGraphView node_R(), node_C(), node_rc_index() Implementation #1816
• node_xlow/ylow/xhigh/yhigh() RRGraphView node_xlow(), node_xhigh(), node_ylow(), node_yhigh() Implementation #1819
• node_capacity() RRGraphView::node_capacity() Implementation #1780
• node_cost_index() RRGraphView node_cost_index() Implementation #1843
• node_direction() RRGraphView::node_direction() Implementation #1791
• node_direction_string() RRGraphView::node_direction() Implementation #1791
• is_node_on_specific_side() RRGraphView is_node_on_specific_side() Implementation #1862
• node_side_string() RRGraphView node_type_string(), node_side_string() Implementation #1873
• node_ptc_num()/node_pin_num()/node_track_num()/node_class_num() RRGraphView node_ptc_num(), node_pin_num(), node_class_num(), node_track_num() Implementation #1908
• fan_in() RRGraphView::node_fan_in() Implementation #1799
• edges()/num_edges() RRGraphView edges(), num_edges(), configurable_edges(), non_configurable_edges(), num_configurable_edges(), num_non_configurable_edges() Implementation #1917
• configurable_edges()/non_configurable_edges()/num_configurable_edges()/num_non_configurable_edges() RRGraphView edges(), num_edges(), configurable_edges(), non_configurable_edges(), num_configurable_edges(), num_non_configurable_edges() Implementation #1917
• first_edge()/last_edge() RRGraphView::node_first_edge() Implementation #1916
• edge_sink_node()/edge_switch() RRGraphView edge_sink_node()/edge_switch() Implementation #1930
• nodes() RRGraphView nodes() Implementation #1932
• rr_segments() RRGraphView rr_segments() Implementation #1910
• rr_switches() RRGraphView rr_switches() Implementation #1945

[tangxifan]

@ethanroj23 @hariszafar-lm @hamzakhan-rs
I summarized our ongoing refactoring effort here and created a checklist.
The idea is to keep a memo for all of us on the progress bar, so that we all know where we are and how far we are to reach the destination.

[baberali-rs]

@tangxifan There are some new APIs which do not exist in rr_node.h or anywhere you mentioned above and we will implement them in RRGraphView or RRGraphBuilder, right?
@ethanroj23 Can you please tell me which APIs you are currently working on? So that we can work on others.

[ethanroj23]

@baberali-rs I am currently working on node_type(), node_type_string(), and node_side_string() in RRGraphView.

[tangxifan]

@ethanroj23 Thanks for the update. While are you working these APIs, would you mind the Rapidsilicon team working on merging the rr_segment into RRGraphView? We will be active in resolving any merging conflicts.

[ethanroj23]

@tangxifan I would not mind. That would be very helpful, thanks!

[tangxifan]

@baberali-rs Yes. I have discussed with @vaughnbetz and @kmurray. We agree to

• Force the use of strong ids for the rr_index_data, rr_switch and rr_segment. For any node/edge-level data query API in RRGraphBuilder and RRGraphView, it should return the strong id rather than an int as the unique index.
• Merge the rr_index_data, rr_switch and rr_segment into RRGraphBuilder and RRGraphView as an internal storage. It will be part of the internal data at
  

  vtr-verilog-to-routing/vpr/src/device/rr_graph_builder.h

  Lines 105 to 119 in 7ec9f74

  	/* -- Internal data storage -- */
  	private:
  	/* TODO: When the refactoring effort finishes,
  	* the builder data structure will be the owner of the data storages.
  	* That is why the reference to storage/lookup is used here.
  	* It can avoid a lot of code changes once the refactoring is finished
  	* (there is no function get data directly through the node_storage in DeviceContext).
  	* If pointers are used, it may cause many codes in client functions
  	* or inside the data structures to be changed later.
  	* That explains why the reference is used here temporarily
  	*/
  	/* node-level storage including edge storages */
  	t_rr_graph_storage& node_storage_;
  	/* Fast look-up for rr nodes */
  	RRSpatialLookup node_lookup_;

vtr-verilog-to-routing/vpr/src/device/rr_graph_view.h

Lines 257 to 269 in 7ec9f74

	/* -- Internal data storage -- */
	/* Note: only read-only object or data structures are allowed!!! */
	private:
	/* node-level storage including edge storages */
	const t_rr_graph_storage& node_storage_;
	/* Fast look-up for rr nodes */
	const RRSpatialLookup& node_lookup_;
	/* rr_indexed_data_ and rr_segments_ are needed to lookup the segment information in node_coordinate_to_string() */
	const vtr::vector<RRIndexedDataId, t_rr_indexed_data>& rr_indexed_data_;
	/* Segment info for rr nodes */
	const std::vector<t_segment_inf>& rr_segments_;

• Evaluate if we should directly return the data of rr_index_data, rr_switch and rr_segment, e.g., seg_type(RRNodeId) with a given node id, rather than a two-step process (get RRSegmentId first and then get the data from rr_segments). @vaughnbetz mentioned it may cause some CPU penalties. But we do not know if it is going to be trivial or huge. If trivial, I believe it is worthy.

See details in #1843

I believe you and your team can start developing the step 1 & 2 in the checklist and create pull requests.

Let me know if you have any questions.

[tangxifan]

As discussed with @vaughnbetz, once the API refactoring is done. We should do the follow-up refactoring

• Extract the rr_graph -related data structure to a separated library librrgraph. Then VPR will use linker to access the data structures
  • This library will include RRGraphBuilder, RRGraphView and RRGraphReader and RRGraphWriter
  • **Caution: We have to run QoR tests for this effort and carefully check any QoR degradation. @vaughnbetz mentioned the problem on inline functions. Once we move to a separated library, the linker may be challenged. It may cause a serious performance degradation on router (could be 50%). We should be very careful on this effort
• Apply unit tests for RRGraph to test it efficiency, especially on the runtime and peak memory usage
• Rework internal data storage for these APIs to accelerate runtime and reduce peak memory usage.

[tangxifan]

@vaughnbetz If I misunderstood your message, feel free to comment. I will formulate the problem.

[tangxifan]

As discussed with @ethanroj23 , some of the remaining tasks on the APIs will be assigned to Rapidsilicon team

• node_ptc_num()/node_pin_num()/node_track_num()/node_class_num() -> @ethanroj23
• edges()/num_edges() -> Rapidsilicon team
• configurable_edges()/non_configurable_edges()/num_configurable_edges()/num_non_configurable_edges() -> Rapidsilicon team
• first_edge()/last_edge() -> Rapidsilicon team
• edge_sink_node()/edge_switch() -> Rapidsilicon team
• nodes() -> @ethanroj23
• rr_switches() -> @ethanroj23

[vaughnbetz]

Thanks @tangxifan. You captured my thoughts well. Basically refactoring into a separate library may not be desirable with a low-level function interface (which is what we have) as we may need inlining for acceptable performance, and that will be left the linker and may not be possible or reliable.

[ethanroj23]

@tangxifan which API are you referencing above called nodes()? I could only find usages of a function called nodes() for the TimingGraph. The same is true for rr_switches(). Are these meant to be brand new APIs? If so, what would be your desired functionality for each?

[tangxifan]

@ethanroj23 You are right.

• nodes() should be a new API in place of the current methods that are used to walk through all the nodes

vtr-verilog-to-routing/vpr/src/route/rr_graph_storage.h

Lines 345 to 364 in e6c2049

	/*
	* Node proxy methods
	*
	* The following methods implement an interface that appears to be
	* equivalent to the interface exposed by std::vector<t_rr_node>.
	* This was done for backwards compability. See t_rr_node for more details.
	*
	* Proxy methods:
	*
	* - begin()
	* - end()
	* - operator[]
	* - at()
	* - front
	* - back
	*
	* These methods should not be used by new VPR code, and instead access
	* methods that use RRNodeId and RREdgeId should be used.
	*
	**********************/

It is designed when we consider the context of t_rr_node (there are only nodes and we can access a node using rr_node[i])
However, now, this is a graph. The accessor API should be more precise. For example,

• We should support range-based loop which is enabled by nodes()

  for (const RRNodeId& node : rr_graph.nodes()) {
     // Use node as the id to get more attributes
  }

You can refer to my implementation at

vtr-verilog-to-routing/vpr/src/device/rr_graph_obj.h

Lines 227 to 250 in e6c2049

	/* Aggregates: create range-based loops for nodes/edges/switches/segments
	* To iterate over the nodes/edges/switches/segments in a RRGraph,
	* using a range-based loop is suggested.
	* -----------------------------------------------------------------
	* Example: iterate over all the nodes
	* // Strongly suggest to use a read-only rr_graph object
	* const RRGraph& rr_graph;
	* for (const RRNodeId& node : rr_graph.nodes()) {
	* // Do something with each node
	* }
	*
	* for (const RREdgeId& edge : rr_graph.edges()) {
	* // Do something with each edge
	* }
	*
	* for (const RRSwitchId& switch : rr_graph.switches()) {
	* // Do something with each switch
	* }
	*
	* for (const RRSegmentId& segment : rr_graph.segments()) {
	* // Do something with each segment
	* }
	*/
	node_range nodes() const;

It will help you when implementing the method

vtr-verilog-to-routing/vpr/src/device/rr_graph_obj.cpp

Lines 18 to 20 in e6c2049

	RRGraph::node_range RRGraph::nodes() const {
	return vtr::make_range(node_ids_.begin(), node_ids_.end());
	}

For other APIs, we may consider to deprecate them. Since current APIs always relay on an id to get the information you want, we no long return a data structure t_rr_node anymore. However, it is safer to double check. I am open to add other APIs if necessary.

For rr_switches(), it is brand new APIs. It is a similar story than merging the rr_segments into RRGraphView. Can you look into the PR #1910 ? After that, if you are still confused, we can talk.

Let me know what you think.

[ethanroj23]

@tangxifan Thank you for the explanation, this makes more sense now! I will begin implementation of this new API and look for feedback once I have done enough for a WIP PR.

[tangxifan]

Hi @ethanroj23   I believe you can try the ``vtr::make_range(begin(), end())``, since the existing APIs ``begin()`` and ``end()`` are already there.  You can refer to the ``rr_graph_ohj.h``     https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/e6c20492832f1950247c8db7b58274664d190992/vpr/src/device/rr_graph_obj.h#L215-L224   The ``begin()`` and ``end()`` are actually iterators. Just need to find a way to use the ``make_range()`` function  

[tangxifan]

@behzadmehmood-rs @umariqbal-rs
Thank you very much on the good work. We have accomplished all the major tasks in this refactoring effort.
We are approaching the final destination! I have listed the last few steps before we can extract the routing resource graph data structure as library.

• Add RRSwitch APIs to RRGraphBuilder Add APIs rr_switch and rr_segment() to RRGraphBuilder #1951
• Add RRSegment APIs to RRGraphBuilder Add APIs rr_switch and rr_segment() to RRGraphBuilder #1951
• Move metadata to RRGraphBuilder Data structure rr_node_metadata/rr_edge_metadata owner change #1952
• Clean-up DeviceContext (Remove shadowed data structure) Clean-up DeviceContext (Remove shadowed data structure) #1962
• Create LibRRGraph (If performance does not degrade) Now rr_graph -related source files are placed in a separated library librrgraph #1972
• Develop Unit tests for RRGraph objects

Please let me know which step you want to take the ownership.

[behzadmehmood-rs]

@tangxifan Thank you for your support. We are ready to own the first four tasks.

[vaughnbetz]

@tangxifan : I think this can be closed. Agreed?

[vaughnbetz]

Or maybe it's waiting for the last item: unit tests?

[tangxifan]

@vaughnbetz The unit tests have been built in #2150 but not yet merged. Feel sorry for the delayed review. I will catch that this summer. I am o.k. to close the PR and create a new one on the unit tests.