Unroutable connection on SymbiFlow tests

acomodi commented 4 years ago

Expected Behaviour

Routing passes correctly.

Current Behaviour

Routing fails to find a connection between SOURCE and SINK.

## Initializing router criticalities took 0.02 seconds (max_rss 654.6 MiB, delta_rss +0.0 MiB)
---- ------ ------- ---- ------- ------- ------- ----------------- --------------- -------- ---------- ---------- ---------- ---------- --------
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
---- ------ ------- ---- ------- ------- ------- ----------------- --------------- -------- ---------- ---------- ---------- ---------- --------
Warning 62: No routing path for connection to sink_rr 255038, retrying with full device bounding box
Warning 63: No routing path for connection to sink_rr 189168, retrying with full device bounding box
Cannot route from SYN-GND[0].GND[0] (RR node: 103354 type: SOURCE location: (30,27) class: 0 capacity: 1 fan-in: 0 fan-out: 1) to BLK-TL-BRAM_L[0].BRAM_FIFO18_DIADI5[0] (RR node: 189168 type: SINK location: (20,53) class: 43 capacity: 1 fan-in: 1 fan-out: 0) -- no possible path
Failed to route connection from '$false' to 'murax.system_ram.ram_symbol1.0.0.0' for net '$false' (#0)
Routing failed for net 0
# Routing took 2.48 seconds (max_rss 654.6 MiB, delta_rss +0.0 MiB)
Circuit is unroutable with a channel width factor of 500.
For a detailed report on the RR node overuse information (report_overused_nodes.rpt), specify --generate_rr_node_overuse_report on.

Possible Solution

I have tracked down the source of this error being in this piece of code: https://github.com/verilog-to-routing/vtr-verilog-to-routing/blob/489eb5b0aeb80873eb72f4e8a46da45d8c593dbe/vpr/src/route/rr_graph2.cpp#L1139-L1181

More specifically, the issue seems to be due to the one time increase of the index pointer whenever a pin is assigned to an RR node. Previously, the pin could be associated with multiple nodes depending on the four possible sides of the tile.

The flow to generate the RR graph in SymbiFlow is the following:

Generate a "virtual" RR graph
Fill the RR graph with all the CHANX/CHANY information with external scripts
Validate the RR graph and re-generate a real RR graph through VPR.

The issue, I believe, is the fact that the "virtual" RR graph might not contain all the necessary nodes to patch it correctly, ending up in a situation where some of the connections required are now missing, causing the unroutability issue reported above. This because, instead of increasing the index counter and, as far as I understood, creating a single node for each tile pin's sides, only one node is generated.

By re-allowing the increase of the index for each side of the pin within the tile solved the issue.

Steps to Reproduce

Working on trying to pack a reproducible test.

Your Environment

VTR revision used: https://github.com/verilog-to-routing/vtr-verilog-to-routing/pull/1568
Operating System and version:
Compiler version:

acomodi commented 4 years ago

@litghost @vaughnbetz FYI.

@tangxifan tagging also you as I see these changes were included in the RR graph fixup PR. Maybe you can have some additional insights on this.

vaughnbetz commented 4 years ago

The prior code wasn't correct for pins that could occur on multiple sides/locations; they were each given their own rr-node rather than having one rr-node with more switches. If symbiflow was relying on the same pin number on different sides / locations on a block being different rr-nodes, the right fix would be to make two different pins for the two distinct inputs. I'm not sure of exactly how symbiflow finds the rr-nodes to which it wants to add connections; perhaps there is a fragility there where it is getting the rr-node index to add connections to in a way that had some implicit assumptions, and hence is not working with the new rr-graph.

acomodi commented 4 years ago

@vaughnbetz Thanks for the insight.

I think I have solved the issue on the symbiflow side, as suggested. Basically, with the local fix in symbiflow, now multiple switches are generated for the same node that is related to a pin that can occur on multiple sides.

I'll need to further test this and make sure that everything is working as supposed.

verilog-to-routing / vtr-verilog-to-routing