ClockRRGraphBuilder uses bad allocation strategies and duplicates work

[litghost]

Expected Behaviour

Per the comment here, memory fragmentation should be avoided when creating the rr graph for performance reasons. The new ClockRRGraphBuilder should avoid incremental allocation patterns, and instead batch edge insertion.

In addition ClockRRGraphBuilder::create_and_append_clock_rr_graph should be invoked at a point in the rr graph construction flow where work is not duplicated.

Current Behaviour

ClockRRGraphBuilder and its classes use only incremental allocation patterns (e.g. they only called add_edge and never preallocate memory). In addition ClockRRGraphBuilder::create_and_append_clock_rr_graph is called after partition_rr_graph_edges, init_fan_in, alloc_and_load_rr_indexed_data are already called, so ClockRRGraphBuilder::create_and_append_clock_rr_graph ends up calling them again! See https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/master/vpr/src/route/rr_graph_clock.cpp#L33-L43

ClockRRGraphBuilder does 3 forms of incremental allocation:

• t_rr_node::add_edge
• rr_nodes.emplace_back();
• segment_inf.emplace_back();

The rr node and edge incremental allocation are probably worth fixing. The segment emplace back is possible fine?

Possible Solution

Related issues

#1079

[litghost]

@kmurray / @vaughnbetz This likely needs to be fixed before working on #1079, as the original plan for #1079 requires a boundry between writing and reading, and because ClockRRGraphBuilder violates that, either the design in #1079 needs to be changed or ClockRRGraphBuilder needs to change.

IMO, the current implementation of ClockRRGraphBuilder is incorrect, and should be fixed.

[litghost]

I just noticed that ClockRRGraphBuilder::create_and_append_clock_rr_graph is called after check_rr_graph (which is located within build_rr_graph)!!! So the invocation point of ClockRRGraphBuilder from my perspective is simply wrong.

[litghost]

As far as I can tell add_rr_switches_and_map_to_nodes should simply not exist. In generally the ClockRRGraphBuilder code seems to not properly distinguish between arch_switch_idx and rr_switch_idx, and intermixes them improperly.

For example:
https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/master/vpr/src/route/clock_connection_builders.h#L49 is clearly supposed to be an rr_switch_idx, but here https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/master/vpr/src/base/setup_clocks.cpp#L143 clearly sets a arch_switch_idx.

[litghost]

As far as I can tell add_rr_switches_and_map_to_nodes should simply not exist. In generally the ClockRRGraphBuilder code seems to not properly distinguish between arch_switch_idx and rr_switch_idx, and intermixes them improperly.

For example:
https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/master/vpr/src/route/clock_connection_builders.h#L49 is clearly supposed to be an rr_switch_idx, but here https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/master/vpr/src/base/setup_clocks.cpp#L143 clearly sets a arch_switch_idx.

For clarity, the mismatch between arch_switch_idx and rr_switch_idx means that it is relatively trival to create an architecture XML that will segfault VPR. In particular, if the clock connection arch switch index is greater than the rr graph switch count, it will cause memory violations.

[litghost]

I think I see what should've happened.

ClockRRGraphBuilder::create_and_append_clock_rr_graph really needed to be inserted into the flow at the "right" place. It looks like remap_rr_node_switch_indices is the place where arch_switch_idx become rr_switch_idx, but because ClockRRGraphBuilder::create_and_append_clock_rr_graph is trying to run after remap_rr_node_switch_indices has been called, it cannot just rely on it to do the fixup.

The solution seems to be to have clock_graph.create_clock_networks_wires and clock_graph.create_clock_networks_switches be called here https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/master/vpr/src/route/rr_graph.cpp#L1297, and let the original code handle the fixup.

This solves the work duplication, because https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/master/vpr/src/route/rr_graph.cpp#L1297 is before init_fan_in is called, which then gets used in alloc_and_load_rr_switch_inf, followed by partition_rr_graph_edges.

[vaughnbetz]

Adding Mustafa so he can comment. @mustafabbas
I haven't traced all the code paths, but your analysis looks correct to me Keith. The idea was to insert the clock part of the rr-graph without disturbing the already complex main rr-graph building from an arch file (for the regular routing channels). The clock rr-graph should therefore be inserted before check_rr_graph, before any clean up / partitioning of edge arrays etc. so that all those changes occur after all the edges for the whole rr-graph are in place. [Hopefully there is no strange dependency in clock_rr_graph that breaks that, but if so, it was not intended and isn't desirable].

For reading in an rr-graph from xml: in that case all the nodes and edges should be in the xml (or other file), so we shouldn't have to call a clock graph creator as a separate step. The rr_graph on disk should have all the nodes and edges, which should just be read in and allocated.

@mustafabbas can you comment? If my analysis is correct, I think someone (ideally Mustafa, but Keith if Mustafa can't do it) should try moving the call point of create_and_append_clock_rr_graph.

[litghost]

I've taken a shot at fixing this in #1081. I'm not totally confident how to verify I haven't broken anything. @mustafabbas / @kmurray Were tests added to vtr_reg_strong for the clock network?

[litghost]

For reading in an rr-graph from xml: in that case all the nodes and edges should be in the xml (or other file), so we shouldn't have to call a clock graph creator as a separate step. The rr_graph on disk should have all the nodes and edges, which should just be read in and allocated.

Yes and no. In particular the mutation of device_ctx.virtual_clock_network_root_idx here is not something the rr graph writer/reader preserves. On that particular front, I would wait until we've merged #1060, and then fixing that specific issue is relatively straight forward.

[mustafabbas]

Hi Keith, there is a vtr strong test in
vtr_flow/tasks/regression_tests/vtr_reg_strong/strong_dedicated_clock/config/config.txt
The test checks that when using an architecture where the fc from clock pins (of logic blocks, RAMs, ...) to local routing is zero and instead clock pins connect to just the dedicated clock network an additional net is routed (the clock net) successfully.
This architecture is timing/k6_frac_N10_frac_chain_mem32K_htree0_40nm.xml

The test does the same with an architecture where the fc from clock pins to local routing is greater than zero timing/k6_frac_N10_frac_chain_mem32K_htree0_routedCLK_40nm.xml just to exercise both saved architecture files.

For an additional level of sanity checking, it may be worth it to run vpr using one of the above mentioned architecture files. Then diffing the generated rr_graph before and after the change. An example command:
vpr vtr_flow/arch/timing/k6_frac_N10_frac_chain_mem32K_htree0_40nm.xml stereovision3.pre-vpr.blif --clock_modeling dedicated_network --write_rr_graph rr_graph.xml