search

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

Verilog to Routing -- Open Source CAD Flow for FPGA Research
https://verilogtorouting.org
Other
1.01k stars 391 forks source link

rr_graph reader: review unexpected channel direction edges #335

Open mcmasterg opened 6 years ago

mcmasterg commented 6 years ago

TLDR: we should either make the drawing correct or reject the rr_graph file

Conceptually an rr_graph is laid out in a two dimensional XY fashion with blocks/tracks occupying various rows and columns. While edges are expected to follow with this in mind, there is no requirement that they do so.

For example, see the attached case. I've created bi-directional edges (ie one with chanx => chany and one with chany => chanx) between the topmost CHANX and the center right CHANY. However, the CHANY is DEC_DIR, which confuses the GUI since I'm trying to connect it as a source. This resulted in the GUI assuming the source came from above and drawing a bad line.

Screenshot: screenshot from 2018-04-26 20-05-26

Sample project with this behavior: unexpected_chan_dir_edge.zip

Expected Behaviour

We should either make the drawing correct (it should appear as a bi-directional link in the sample project) or reject the rr_graph file

Current Behaviour

The graph is accepted without warning or error. Note: there are unrelated warnings for the unconnected nodes in the sample project.

Possible Solution

If the XY grid is a core concept, suggest rejecting this rr_graph

Steps to Reproduce (for bugs)

  1. Unzip attached zip
  2. cd build
  3. vpr ../arch.xml --device JOHN --timing_analysis off --sweep_dangling_blocks off --route_chan_width 2 ../wire.blif --disp on --read_rr_graph rr_graph2.xml

Context

Testing rr_graph python library. I will probably add checks on my end for now not to generate these until I have a demonstrated need for them

Your Environment

kmurray commented 6 years ago

Thanks for the detailed report and test case. I've been able to reproduce the same results.

I think there are two issues here:

  1. X/Y RR graph layout

Conceptually an rr_graph is laid out in a two dimensional XY fashion with blocks/tracks occupying various rows and columns. While edges are expected to follow with this in mind, there is no requirement that they do so.

If the XY grid is a core concept, suggest rejecting this rr_graph

I think we probably do not want to treat the XY grid layout as a core RR graph concept.

The router should be able to work on any arbitrary graph (even if it doesn't follow a strict XY layout), and I would not want to preclude supporting architectures with such RR graphs.

Hence on the basis of XY/non-XY I do not think we should reject an RR graph.

The reality is most devices generally follow an XY style of layout (at least for most of their nodes), so I would expect non-XY layouts to be the exceptions rather than the norm.

The only part of VPR which really assume an XY layout is the drawing code. I would view our top priority as supporting routing on reasonable RR graphs (whether XY or non-XY), and treat drawing them correctly as a secondary priority (you can always run with --disp off if the graphics doesn't work).

My suggestion would be to address drawing non-XY layouts (most likely just drawing a small number of non-XY rr nodes, with a larger XY graph) on an as needed basis. Making it look pretty can always follow later.

  1. What do bi-directional edges in a uni-directional RR graph mean?

I can think of two possibilities (where Node 13 is the top CHANX, Node 17 the centre right CHANY):

a. Node 17 is drives Node 13 along it's length b. Node 17 drive Node 13 at it's start-point

(a) is electrically illegal for unidir routing (there is only a single driver at the wire startpoint). (b) seems to be the only valid interpretation.

Assuming (b) then this is just a case of drawing a non-XY layout edge in an otherwise XY layout graph.

VPR does this incorrectly at the moment as shown in the screenshot above. The correct drawing for (b) would be something like this mock-up:

image

Is this what you were expecting?

mithro commented 6 years ago

@kmurray Is there any reason why there are CHANX and CHANY rather than just CHANs which just happens to run in X or Y directions? It feels like channels should just go from an arbitrary (X1, Y1) -> (X2, Y2).

It is likely we need "diagonal" channels in the future (in fact the iCE40 has connections between (X, Y) -> (X+1, Y+1) and (X, Y) -> (X-1, Y-1), etc).

kmurray commented 6 years ago

Is there any reason why there are CHANX and CHANY rather than just CHANs which just happens to run in X or Y directions?

I agree this would be more general.

That VPR uses CHANX/CHANY since that was how it was originally coded. Doing so simplifies the code since it only needs to concern itself with the horizontal/vertical cases (rather than all possible arbitrary orientations).

The actual RR node class (t_rr_node) has support for unique position coordinates (xlow, ylow, xhigh, yhigh), and so could support diagonal RR nodes.

The real dependencies on CHANX/CHANY fall within the drawing code (draws differently depending the type, since it assumes CHANX/CHANY are non-zero length nodes which are horizontally/vertically aligned).

The RR graph generator (build_rr_graph()) likely also has some similar dependencies.

So while generalizing to a non-horizontal/vertical CHAN is possible it would require updating the above code to robustly handle such cases -- a non-trivial amount of work.

It is likely we need "diagonal" channels in the future (in fact the iCE40 has connections between (X, Y) -> (X+1, Y+1) and (X, Y) -> (X-1, Y-1), etc).

I'd recommend modeling this as two RR nodes (one CHANX, one CHANY) with a non-configurable edge between them.

For example, something like:

<switch id="1" name="electrical_short" buffered="0" configurable="0">
  <timing R="0" Cin="0" Cout="0" Tdel="0"/>
</switch>
...
<node id="0" type="CHANX" direction="INC_DIR" capacity="1">
  <loc xlow="X" ylow="Y" xhigh="X+1" yhigh="Y"/>
</node>
<node id="1" type="CHANY" direction="INC_DIR" capacity="1">
  <loc xlow="X+1" ylow="Y" xhigh="X+1" yhigh="Y+1"/>
</node>
...
<edge src_node="0" sink_node="1" switch_id="1">

Since the switch is non-configurabel (configurable="0"), the router will effectively treat the above as a single RR node from (X,Y) -> (X+1, Y+1).

This L-shaped implementation is also more aligned with the physical layout, since modern process technologies do not allow arbitrary routing, but restrict you to either 1D or 2D X/Y routing.