Skip to content

Routing failure on global channel structure #520

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
litghost opened this issue Mar 28, 2019 · 6 comments
Closed

Routing failure on global channel structure #520

litghost opened this issue Mar 28, 2019 · 6 comments

Comments

@litghost
Copy link
Collaborator

Expected Behavior

The router should successfully find a path from source to sink.

Current Behavior

The router fails to find a path from source to sink in 3 of the 4 cases tests.

Possible Solution

Using a high bb_factor and mux's instead of shorts for connecting the channels appears to enable the router to find a path. The channel design could also be changed to suit the router better, but it is not completely clear how much of this is a router bug versus a rrgraph bug.

Steps to Reproduce

  1. vtr_bug.zip contains an example blif, and two versions of the arch/rrgraph. The version in the mux folder uses muxes to connect the global constant network together, the version in the short folder uses shorts to connect the global constant network.
  2. After extracting the zip run the following command in either the mux or short directory:
vpr \
  arch.unique_pack.xml \
  ../top.eblif \
  --device 10x10 \
  --read_rr_graph rr_graph_10x10_dummy.rr_graph.real.xml \
  --min_route_chan_width_hint 100 --max_criticality 0.0 \
  --max_router_iterations 500 --routing_failure_predictor off \
  --router_high_fanout_threshold -1 --constant_net_method route \
  --route_chan_width 100

This fails to complete successfully on both the mux and short versions.

  1. Attempting to increase the bb_factor results in the mux version finding a route, but not the short version:
vpr \
  arch.unique_pack.xml \
  ../top.eblif \
  --device 10x10 \
  --read_rr_graph rr_graph_10x10_dummy.rr_graph.real.xml \
  --min_route_chan_width_hint 100 --max_criticality 0.0 \
  --max_router_iterations 500 --routing_failure_predictor off \
  --router_high_fanout_threshold -1 --constant_net_method route \
  --route_chan_width 100
  --bb_factor 1000

Context

As part of exploring how to route constants in VPR (#163), I attempted to create a global network for the VCC and GND signal, and modified my synthesis tool to emit the $true (e.g. VCC) and $false (e.g. GND) signals connected to these sources. Generating the new rrgraph was not to complicated, however when I went to test it, the router failed to find a path between the constant source and the pin sink.

The shape of the global constant network is a set of CHANY (which span the entire height) with one CHANX spanning the entire width, which are all connected to each other with shorts.

Your Environment

VPR built from litghost@1077383
@litghost
Copy link
Collaborator Author

Visualization of issue https://docs.google.com/drawings/d/1P-_r5eF1d5eXGhshIwqI-EtSzA3WNNMAUDndIsNwi3M/edit

@kmurray
Copy link
Contributor

kmurray commented Mar 29, 2019

Thanks for the report, and the helpful visualizations.

1. Bounding Box for nets on dedicated global networks

As you noted to use a global network fully the router's bounding box must include all the networks resources (otherwise the router won't explore it fully and you can end up with disconnected resource as you found).

I think the long term fix is to handle nets which are expected to route on global resources specially.

@mustafabbas is looking at a two-stage approach for routing signals on dedicated global networks (primarily motivated by clocks):

  • Stage 1: Route from input pin to clock driver
  • Stage 2: Route from clock driver to sinks

The same method could be applied to your vcc/gnd use case. For the stage 2 routing it would make sense to use a bounding box which matches the dimensions of the global network (rather than the driver/sink location) which would avoid the issue you are seeing.

2. Shorted Connections

I've been able to reproduce the issue with shorted connections. This looks like a limitation of the router's handling of shorted connections.

With VTR_ENABLE_DEBUG_LOGGING on, and --router_debug_net 6 I get:

---- ------ ------- ---- ------- ------- ------- ----------------- --------------- -------- ---------- ---------- ---------- ---------- --------
Iter   Time    pres  BBs    Heap  Re-Rtd  Re-Rtd Overused RR Nodes      Wirelength      CPD       sTNS       sWNS       hTNS       hWNS Est Succ
      (sec)     fac Updt    push    Nets   Conns                                       (ns)       (ns)       (ns)       (ns)       (ns)     Iter
---- ------ ------- ---- ------- ------- ------- ----------------- --------------- -------- ---------- ---------- ---------- ---------- --------
Net 6 Target 0 (RR node: 518 type: SINK location: (4,14) class: 0)
  Adding node       28 to heap from init route tree with cost 0 (RR node: 28 type: SOURCE location: (1,14) class: 0)
  Routing to 518 as normal net (BB: 0,0 x 15,15)
  Popping node 28
    Better cost to 28
      Setting path costs for assicated node 28 (from -1 edge -1)
      Expanding to node 29 (RR node: 29 type: OPIN location: (1,14) pin: 0 pin_name: BLK_TI-VCC.VCC[0])
        Force Expanding to node 3100 (RR node: 3100 type: CHANY location: (1,1) <-> (1,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3118 (RR node: 3118 type: CHANX location: (1,5) <-> (14,5) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3114 (RR node: 3114 type: CHANX location: (1,1) <-> (14,1) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3104 (RR node: 3104 type: CHANY location: (5,1) <-> (5,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3113 (RR node: 3113 type: CHANY location: (14,1) <-> (14,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3109 (RR node: 3109 type: CHANY location: (10,1) <-> (10,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3105 (RR node: 3105 type: CHANY location: (6,1) <-> (6,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3101 (RR node: 3101 type: CHANY location: (2,1) <-> (2,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3110 (RR node: 3110 type: CHANY location: (11,1) <-> (11,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3106 (RR node: 3106 type: CHANY location: (7,1) <-> (7,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3102 (RR node: 3102 type: CHANY location: (3,1) <-> (3,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3111 (RR node: 3111 type: CHANY location: (12,1) <-> (12,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3107 (RR node: 3107 type: CHANY location: (8,1) <-> (8,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3112 (RR node: 3112 type: CHANY location: (13,1) <-> (13,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3103 (RR node: 3103 type: CHANY location: (4,1) <-> (4,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3108 (RR node: 3108 type: CHANY location: (9,1) <-> (9,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3119 (RR node: 3119 type: CHANX location: (1,6) <-> (14,6) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3124 (RR node: 3124 type: CHANX location: (1,11) <-> (14,11) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3115 (RR node: 3115 type: CHANX location: (1,2) <-> (14,2) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3120 (RR node: 3120 type: CHANX location: (1,7) <-> (14,7) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3125 (RR node: 3125 type: CHANX location: (1,12) <-> (14,12) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3121 (RR node: 3121 type: CHANX location: (1,8) <-> (14,8) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3126 (RR node: 3126 type: CHANX location: (1,13) <-> (14,13) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3116 (RR node: 3116 type: CHANX location: (1,3) <-> (14,3) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3122 (RR node: 3122 type: CHANX location: (1,9) <-> (14,9) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3127 (RR node: 3127 type: CHANX location: (1,14) <-> (14,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3117 (RR node: 3117 type: CHANX location: (1,4) <-> (14,4) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3123 (RR node: 3123 type: CHANX location: (1,10) <-> (14,10) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
  Popping node 29
    Better cost to 29
      Setting path costs for assicated node 29 (from 28 edge 0)
      Setting path costs for assicated node 3100 (from 29 edge 0)
      Setting path costs for assicated node 3118 (from 3100 edge 0)
      Setting path costs for assicated node 3114 (from 3100 edge 1)
      Setting path costs for assicated node 3104 (from 3114 edge 0)
      Setting path costs for assicated node 3113 (from 3114 edge 1)
      Setting path costs for assicated node 3109 (from 3114 edge 3)
      Setting path costs for assicated node 3105 (from 3114 edge 4)
      Setting path costs for assicated node 3101 (from 3114 edge 5)
      Setting path costs for assicated node 3110 (from 3114 edge 6)
      Setting path costs for assicated node 3106 (from 3114 edge 7)
      Setting path costs for assicated node 3102 (from 3114 edge 8)
      Setting path costs for assicated node 3111 (from 3114 edge 9)
      Setting path costs for assicated node 3107 (from 3114 edge 10)
      Setting path costs for assicated node 3112 (from 3114 edge 11)
      Setting path costs for assicated node 3103 (from 3114 edge 12)
      Setting path costs for assicated node 3108 (from 3114 edge 13)
      Setting path costs for assicated node 3119 (from 3100 edge 2)
      Setting path costs for assicated node 3124 (from 3100 edge 3)
      Setting path costs for assicated node 3115 (from 3100 edge 4)
      Setting path costs for assicated node 3120 (from 3100 edge 5)
      Setting path costs for assicated node 3125 (from 3100 edge 6)
      Setting path costs for assicated node 3121 (from 3100 edge 7)
      Setting path costs for assicated node 3126 (from 3100 edge 8)
      Setting path costs for assicated node 3116 (from 3100 edge 9)
      Setting path costs for assicated node 3122 (from 3100 edge 10)
      Setting path costs for assicated node 3127 (from 3100 edge 11)
      Setting path costs for assicated node 3117 (from 3100 edge 12)
      Setting path costs for assicated node 3123 (from 3100 edge 13)
        Force Expanding to node 3100 (RR node: 3100 type: CHANY location: (1,1) <-> (1,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3118 (RR node: 3118 type: CHANX location: (1,5) <-> (14,5) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3114 (RR node: 3114 type: CHANX location: (1,1) <-> (14,1) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3104 (RR node: 3104 type: CHANY location: (5,1) <-> (5,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3113 (RR node: 3113 type: CHANY location: (14,1) <-> (14,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3109 (RR node: 3109 type: CHANY location: (10,1) <-> (10,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3105 (RR node: 3105 type: CHANY location: (6,1) <-> (6,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3101 (RR node: 3101 type: CHANY location: (2,1) <-> (2,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3110 (RR node: 3110 type: CHANY location: (11,1) <-> (11,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3106 (RR node: 3106 type: CHANY location: (7,1) <-> (7,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3102 (RR node: 3102 type: CHANY location: (3,1) <-> (3,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3111 (RR node: 3111 type: CHANY location: (12,1) <-> (12,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3107 (RR node: 3107 type: CHANY location: (8,1) <-> (8,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3112 (RR node: 3112 type: CHANY location: (13,1) <-> (13,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3103 (RR node: 3103 type: CHANY location: (4,1) <-> (4,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3108 (RR node: 3108 type: CHANY location: (9,1) <-> (9,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3119 (RR node: 3119 type: CHANX location: (1,6) <-> (14,6) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3124 (RR node: 3124 type: CHANX location: (1,11) <-> (14,11) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3115 (RR node: 3115 type: CHANX location: (1,2) <-> (14,2) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3120 (RR node: 3120 type: CHANX location: (1,7) <-> (14,7) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3125 (RR node: 3125 type: CHANX location: (1,12) <-> (14,12) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3121 (RR node: 3121 type: CHANX location: (1,8) <-> (14,8) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3126 (RR node: 3126 type: CHANX location: (1,13) <-> (14,13) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3116 (RR node: 3116 type: CHANX location: (1,3) <-> (14,3) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3122 (RR node: 3122 type: CHANX location: (1,9) <-> (14,9) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3127 (RR node: 3127 type: CHANX location: (1,14) <-> (14,14) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3117 (RR node: 3117 type: CHANX location: (1,4) <-> (14,4) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
        Force Expanding to node 3123 (RR node: 3123 type: CHANX location: (1,10) <-> (14,10) track: 1 len: 13 longline: 0 seg_type: span dir: BI_DIR)
  Popping node 3102
  Empty heap (no path found)
Cannot route from BLK_TI-VCC.VCC[0] (RR node: 28 type: SOURCE location: (1,14) class: 0) to BLK_IG-OBUF.O[0] (RR node: 518 type: SINK location: (4,14) class: 0) -- no possible path
Failed to route connection from '$true' to 'out:D5' for net 'D5' (#6)

Which shows the router followed the OPIN (29) and identified all the shorted-together span wire nodes (31xx's) forming the dedicated global network.

However the limitation is the router does not correctly explore the pins reachable from all the 31xx span nodes. It only tries to expand 3102 (likely because it is expected to have the lowest cost to the target pin), but it turns out to not connect to the target block, so any connected IPINs are not explored (i.e. pruned by https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/master/vpr/src/route/route_timing.cpp#L1761-L1768).

The fix is to have the router expand from all the 31xx nodes so that it will find the IPIN it's trying to connect to. I'm looking into how to do this cleanly.

@litghost
Copy link
Collaborator Author

@mustafabbas is looking at a two-stage approach for routing signals on dedicated global networks (primarily motivated by clocks):

  • Stage 1: Route from input pin to clock driver
  • Stage 2: Route from clock driver to sinks

We are interested in this as well. Do you have a issue tracking this work?

@kmurray kmurray mentioned this issue Mar 29, 2019
Closed
@kmurray
Copy link
Contributor

kmurray commented Mar 29, 2019

We are interested in this as well. Do you have a issue tracking this work?

Filed as #521

@kmurray
Copy link
Contributor

kmurray commented Mar 29, 2019

The fix is to have the router expand from all the 31xx nodes so that it will find the IPIN it's trying to connect to. I'm looking into how to do this cleanly.

I believe this is fixed as of 08b8a0f.

I had to make one change to your shorted RR graph to make this work. Currently in your RR graph the OPIN's driving the dedicated vcc/gnd network are also 'short'-type switches. This causes issues with the routing legality checker since 'short' type switch expect there to be two edges (bi-directional) between shorted nodes -- but you only have the forward edge leaving the OPIN.

The fix is to just convert the OPIN edge to use a regular configurable switch:

<     <edge sink_node="3128" src_node="7" switch_id="2"/>
<     <edge sink_node="3100" src_node="29" switch_id="2"/>
---
>     <edge sink_node="3128" src_node="7" switch_id="1"/>
>     <edge sink_node="3100" src_node="29" switch_id="1"/>

@litghost litghost mentioned this issue Mar 29, 2019
Merged
@litghost
Copy link
Collaborator Author

The fix in 08b8a0f looks good. Given that #521 is filled and with address the mux case with default bb_factor, and the short case is now working, I think we can close this.

@mkurc-ant mkurc-ant mentioned this issue Apr 12, 2019
Closed
@mustafabbas mustafabbas mentioned this issue Aug 16, 2019
Merged
4 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@litghost @kmurray