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:

• [x] set_node_type() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1847
• [x] set_node_ptc_num() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1872
• [x] set_node_pin_num() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1872
• [x] set_node_track_num() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1872
• [x] set_node_class_num() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1872
• [x] set_node_coordinates() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1853
• [x] set_node_cost_index() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1884
• [x] set_node_rc_index() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1887
• [x] set_node_capacity() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1855
• [x] set_node_direction() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1856
• [x] add_node_side() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1889
• [x] reserve_nodes() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1905
• [x] resize_nodes() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1905
• [x] ~~add_node()~~ Removed because it is not currently used in rr_graph builder; Will think it later.
• [x] reserve_edges() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1892
• [x] emplace_back_edges() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1892
• [x] alloc_and_load_edges() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1892
• [x] count_rr_switches() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1896
• [x] remap_rr_node_switch_indices() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1897
• [x] make_edges_as_rr_switch_ids() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1902
• [x] partition_edges() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1900
• [x] init_fan_in() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1903
• [x] validate() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1899

RRGraphView API to be refactored:

• [x] node_type() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1742
• [x] node_type_string() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1873
• [x] node_rc_index() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1816
• [x] node_R() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1816
• [x] node_C() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1816
• [x] node_xlow/ylow/xhigh/yhigh() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1819
• [x] node_capacity() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1780
• [x] node_cost_index() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1843
• [x] node_direction() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1791
• [x] node_direction_string() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1791
• [x] is_node_on_specific_side() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1862
• [x] node_side_string() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1873
• [x] node_ptc_num()/node_pin_num()/node_track_num()/node_class_num() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1908
• [x] fan_in() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1799
• [x] edges()/num_edges() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1917
• [x] configurable_edges()/non_configurable_edges()/num_configurable_edges()/num_non_configurable_edges() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1917
• [x] first_edge()/last_edge() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1916
• [x] edge_sink_node()/edge_switch() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1930
• [x] nodes() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1932
• [x] rr_segments() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1910
• [x] rr_switches() https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/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 https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/7ec9f743bce637264f7cba4e13f3811df2692b5c/vpr/src/device/rr_graph_builder.h#L105-L119

https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/7ec9f743bce637264f7cba4e13f3811df2692b5c/vpr/src/device/rr_graph_view.h#L257-L269

• 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 https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/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

https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/e6c20492832f1950247c8db7b58274664d190992/vpr/src/route/rr_graph_storage.h#L345-L364

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

https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/e6c20492832f1950247c8db7b58274664d190992/vpr/src/device/rr_graph_obj.h#L227-L250

It will help you when implementing the method

https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/e6c20492832f1950247c8db7b58274664d190992/vpr/src/device/rr_graph_obj.cpp#L18-L20

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.

• [x] Add RRSwitch APIs to RRGraphBuilder #1951
• [x] Add RRSegment APIs to RRGraphBuilder #1951
• [x] Move metadata to RRGraphBuilder #1952
• [x] Clean-up DeviceContext (Remove shadowed data structure) #1962
• [x] Create LibRRGraph (If performance does not degrade) #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.