Giant distance from initial placing and routing solution to a better one VTR could have found.

[WindFrank]

Hi VTR Team,

We manage to find three test cases, whose VTR solutions have giant distance from themselves to their own better solutions generated by VTR, too. The promotion percentages are respectively 47.05%, 37.47%, and 38.09%. Is there anything wrong with the program logic or algorithm strategy? The delay info is shown as follow:

case 1
worse solution delay: 2.819110
better solution delay: 1.917090

case 2
worse solution delay: 10.680300
better solution delay: 7.769120

case 3
worse solution delay: 9.998290
better solution delay: 7.240330

Expected Behaviour

Theoretically, a placing and routing solution of a netlist (.blif), which is constructed by two sub netlists having no common rr node, should be a simple addition of two solutions of sub netlists. Under the mainly purpose of delay, the rule should work.

Actually, few placing and routing systems could reach the goal because of the heuristic algorithm and ML technique. At least the system like VTR is supposed to give solutions with similar delay.

Current Behaviour

Sometimes, however, the rule proposed in Expected Behaviour is widely inconsistent when we use VTR to produce single and combining solutions and compare their delays and wire lengths.

We make sure that:
*The sub netlists have no common rr nodes.
*Use the same architecture EArch.xml and disable the power configuration in it.
*Run commands focusing on delay.

We combine two .blifs and get new large .blif, and combine their io locations to get fixed pin file .place.
And then we run the three .blif and observe their delays and wire lengths.

The command is:
run_vtr_flow.py(vpr)
program.v EArch_no_power.xml
-temp_dir
-start odin
--device fixed
(--fix_clusters combine_fixed_pin.place )
--alpha_clustering 1
--noc_placement_weighting 1
--route_chan_width 100
--noc_swap_percentage 0
--place_quench_algorithm slack_timing
--noc_latency_weighting 0
--timing_report_detail detailed
--timing_report_npaths 100000

Finally, we get test results. To get outliers, we do model residual analysis. We get three outliers like this:
Program 1
Delay: 4.323300
Wire area: 104.00000

Program 2
Delay: 7.769120
Wire area: 76.00000

Combine Netlist
Delay: 10.680300
Wire area: 225.00000

Theoretically, the delay of combine netlist should equal to the delay of program 2. However, there is great difference between the two delays. What's more, the wire area of combine netlist is also two large, which may suggest that there are instances of excessive routing. We think the situation are supposed to be taken seriously.

We hope that the cases we found could help you find bugs in VTR or optimize algorithm used in VTR.
Thank you!

Possible Solution

Maybe you should run the netlists in attachments to reproduce the results and debug the functions in VTR.

Steps to Reproduce

VTR_issue.zip

Run three .blifs in each case from attachments to reproduce the result.
You could get test report from file test.rpt.
The command is:

run_vtr_flow.py(vpr)
program.v EArch_no_power.xml
-temp_dir
-start odin
--device fixed
(--fix_clusters combine_fixed_pin.place )
--alpha_clustering 1
--noc_placement_weighting 1
--route_chan_width 100
--noc_swap_percentage 0
--place_quench_algorithm slack_timing
--noc_latency_weighting 0
--timing_report_detail detailed
--timing_report_npaths 100000

Context

We are trying to produce optimal placing and routing solution by VTR and do the software testing to find the bugs or algorithm defect in it.

Your Environment

• VTR revision used: FCCM 2023
• Operating System and version: Ubuntu 20.04
• Compiler version: g++ 9.4.0