Routing failed - no possible path (even though there is one) - Binning issue

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Using the attached architecture file and blif, run vpr:

vpr k4_N10_L1_mem32768x64_MEM0_poweropt2_freq8_tech7nm_mrep20_uni.xml  
mkGmm_comp --blif_file mkGmm_comp.pre-vpr.blif  --timing_analysis on 
--timing_driven_clustering on --cluster_seed_type timing

2. Placement completes successfully.

3. Routing fails.

What is the expected output? What do you see instead?

I expect routing to succeed. Instead, I get the error message:

Using low: -1, high: -1, current: 176
Build rr_graph took 22.7307 seconds.
Confirming Router Algorithm: TIMING_DRIVEN.

Routing iteration: 1
WARNING(92): Empty heap occurred in get_heap_head.
WARNING(93): Some blocks are impossible to connect in this architecture.
Cannot route net #3990 (top^FF_NODE~229) to sink #11 -- no possible path.
Routing failed.
Using low: 176, high: -1, current: 352

The channel width is then repeatedly doubled but fails the same way at every 
step.

What version of the product are you using? On what operating system?

VTR 7.0, on Ubuntu 14.04.1 LTS

Please provide any additional information below.

I believe that the issue is in the mark_node_expansion_by_bin() function in 
vpr/SRC/route/route_timing.c, with the binning procedure.
net #3990 (top^FF_NODE~229) is a high fanout net (~160), so it goes through 
mark_node_expansion_by_bin().
If I change "#define HIGH_FANOUT_NET_LIM 64" to "#define HIGH_FANOUT_NET_LIM 
6400" vpr/SRC/base/in vpr_types.h, then routing completes successfully (the 
problematic net doesn't go through that function any more).
I couldn't pinpoint the exact cause of the problem, but I would guess that this 
is a corner case, where the sink or a routing resource is right on the edge of 
a bin, and can only get expanded from outside the bin. So even though a route 
does exist, the code doesn't see it because of the binning.

Original issue reported on code.google.com by edin.kad...@gmail.com on 22 Apr 2015 at 1:47

Attachments:

• vpr_debug3_bug_report.tar.gz

[GoogleCodeExporter]

Good debugging, thanks!  I'll forward the case to Oleg to look at.  In all 
likelihood, there is a corner case missed in the code that determines the 
bounding box for a sink of a high-fanout net.

Original comment by JasonKai...@gmail.com on 22 Apr 2015 at 3:03

[GoogleCodeExporter]

Hmm I can't reproduce this. Net 3990 routes fine for me (I'm still running the 
design to see if everything else routes too).

Edin, can you attach your generated mkGmm_comp.pre-vpr.net and 
mkGmm_comp.pre-vpr.place files?

Original comment by o.d.pete...@gmail.com on 22 Apr 2015 at 4:10

[GoogleCodeExporter]

I just tried again with a new copy of vtr_release_7.0_full.tar.gz,
attached are the generated .net and .place files.

I also just tried with the latest version in the repository, and it doesn't 
seem to break with that version. Either there were modifications that took care 
of the issue, or it just happens that the bad case is avoided with a luckier 
routing.

Original comment by edin.kad...@gmail.com on 22 Apr 2015 at 6:11

Attachments:

• net_and_place.tar.gz

[GoogleCodeExporter]

Thanks Edin. Looks like it was indeed a problem with the 
mark_node_expansion_by_bin() function. 'mark_node_expansion_by_bin' defined the 
bin size with respect to the target node xlow/ylow coordinates. On the other 
hand 'timing_driven_expand_neighbours' performed its bounding box check with 
respect to the target xhigh/yhigh coordinates. With tall function blocks like 
the multiplier sinks can span multiple 'y' coordinates which introduced an 
inconsistency between how the bounding box was initially set and how it was 
later checked. Fixed by changing 'mark_node_expansion_by_bin' calculation to be 
relative to target xhigh/yhigh coords.

Original comment by o.d.pete...@gmail.com on 23 Apr 2015 at 12:28

• Changed state: Fixed

[GoogleCodeExporter]

Thanks!

Was the fix just the two lines in 'mark_node_expansion_by_bin'?
I've tried changing it in the VPR 7.0 source (which looks a bit different from 
the latest one in svn), so I now have:

>> target_x = rr_node[target_node].xhigh;
>> target_y = rr_node[target_node].yhigh;

Instead of 'xlow' and 'ylow' previously.

That fixed the issue with that blif/arch combination (and some other 
combinations I had). However, one of them still doesn't work. I'm attaching it 
to this message.

I wonder if the fix also involves another change that I missed, or if there's 
yet another corner case in the binning code?

There are two subfolders in the attached archive. 'old' contains the error 
message, .net and .place files before applying the above fix; 'new' contains 
the error message, .net and .place files after applying the above fix.

Once again, setting "#define HIGH_FANOUT_NET_LIM 6400" makes it work.

Original comment by edin.kad...@gmail.com on 23 Apr 2015 at 2:37

Attachments:

• update.tar.gz

[GoogleCodeExporter]

Agh, good catch. Looks like I didn't account for a possible corner case in my 
fix. Since the highfanout_rlim bin dimension is calculated relative to 
xhigh/yhigh, there is no guarantee in the case of a really tall functional 
block (like in the new architecture that you attached) that the bin centered at 
xhigh/yhigh will encompass the actual sink input pin (which may be on the lower 
end of the block). As a fix I'm additionally incrementing rlim by the maximum 
x/y span of the block in question.

Original comment by o.d.pete...@gmail.com on 23 Apr 2015 at 8:37

• Changed state: Started

[GoogleCodeExporter]

Great, that fixed it. Thanks!

Original comment by edin.kad...@gmail.com on 24 Apr 2015 at 3:44

[GoogleCodeExporter]

Original comment by o.d.pete...@gmail.com on 25 Apr 2015 at 5:42

• Changed state: Fixed