Unable to Describe Diagonal Wires with Current VPR architecture description

[WhiteNinjaZ]

Current Behaviour

Several current FPGA's utilize diagonal routing in their architectures (specifically Xilinx parts). Currently, VPR has no way to implement this functionality. The proposal has been made that diagonal wires could be implemented by using a combination of shorted segments and custom switch blocks. However, there is a major issue with this:
The issue is that switchpoints in vtr are currently referenced as 0->1->2->...->0 (i.e. both ends have a 0 index). Custom SB allow for unique specification of interconnect for each switch-point, but because both ends are specified with a zero index there is no way to uniquely specify an interconnect for the two ends. To demonstrate why this is an issue, lets assume we want to create a diagonal wire that goes up/down 4 and over 2 (i.e. vertical length 4 wires and horizontal length 2 wires). The desired functionality would be to have each end of vertical L4 wires connect to each begining of horizontal L2 wires via a short and for the beginning of the L4 wire and the end of the L2 wire to have "normal" interconnect (i.e. able to connect to other wire types), as shown in the drawing bellow:

However, with the current iteration of VTR it is impossible to differentiate between the start and end of each wire segment in the architecture description since both the start and end are only accessible via their switch-points at the 0th index. The most you can do with the current architecture description is to short multiple diagonal segments together.

Possible Solution

This problem could be remedied by just changing how wire segments are represented (i.e. for a length y wire the start switchpoint has index 0 and the end switch point has index y), however, the assumption that both wire ends have index 0 is pretty deeply ingrained in the code used to build switch blocks and parse wire segments as well as in previously created architecture descriptions. The use case is also unique enough that I wonder if it would just be better to create a new diagonal segment type. I am currently going through the code base to determine the best way to implement diagonal wires and will post here once I have a better understanding of a good approach. The main purpose for this issue is to provide a place to discuss ideas for how diagonal wires should be implemented and how they should be represented in the xml if we go that route.

Update: after thinking about diagonal wires for a while and working through some proofs using set theory, it appears that there is actually a way to build a rough approximation for diagonal wires using only custom SBs and a very small change to the code base (I believe the issue stated above was an error on my part and also due to me trying to implement diagonal wires in a bi-directional architecture). In the case of unidirectional architectures at least, all that is needed is to specify that the wires being driven by the vertical component of a diagonal segment have a arch_wire_switch that is of type "short" (i.e. in a L4->L2 diagonal wire, the L2 wire wire switch is overridden to be a short). However, this technique for specifying a diagonal wire in all four Intercardinal directions (NE,NW,SE,SW) requires a high level of verbosity. At least eight segments are needed and four custom switch blocks to specify a single diagonal wire. Additionally, there are certain aspects of diagonal wires that make their routing and interconnection unique and difficult or impossible to describe in the current architecture description. In light of this, I still think it would be a good idea to create a special way to describe diagonal wires in the architecture.

[WhiteNinjaZ]

A major consideration when thinking about how to represent diagonal wires in the xml is that a diagonal wire does not necessarily have the same contribution to the horizontal/vertical channels of an architecture. Consider, for example, an architecture with 24 wires in the vertical and horizontal directions and that we want to create a diagonal wire with a vertical component of length 3 and a horizontal component of length one. Also assume that only one wire terminates/starts at each destination/source. The result can be seen in the image bellow:

Here we can see that the diagonal wires contribute 6 segments to each vertical channel (25% of all vertical wires) and 2 segments to each horizontal channel (8.3% of all horizontal wires).
This is important because the calculations for these different contributions need to either (a) be done by the end user and specified in the xml or (b) done in the code that generates the rr_graph. I believe that doing option (a) would be better because it would simplify the changes that would have to be made to the code base. That being said the following comment gives a few ideas for how to implement diagonal wires in the xml:

[WhiteNinjaZ]

The following gives some examples of how diagonal wires might be represented in the xml along with the pros and cons of each. Options are listed from most to least favorable. In all cases the examples given are of diagonal wires with vertical length 4 and horizontal length 2:

Option 1: create a diagonal "wrapper" for two segment types

Description: Diagonal wires could be represented by wrapping exactly 2 segments in a <diagonal_interconnect> tag within the segmentlist. I believe this would be relatively simple to implement and would provide the user with a large degree of flexibility.
Example:

...
<segmentlist>
  
  ...
  <!-- start of diagonal wrapper  -->
  <diagonal_interconnect>

  <!-- specify horizontal component  -->
  <segment axis="x" freq="0.5161290" name="diagonal_xComp" length="2" type="unidir" Rmetal="101" Cmetal="22.5e-15">
    <mux name="mux"/>
    <sb type="pattern">1 0 1</sb>
    <cb type="pattern">1 1</cb>
  </segment>

  <!-- specify vertical component  -->
  <segment axis="y" freq="0.2580645" name="diagonal_yComp" length="4" type="unidir" Rmetal="101" Cmetal="22.5e-15">
    <mux name="mux"/>
    <sb type="pattern">1 0 0 0 1</sb>
    <cb type="pattern">1 0 1 1</cb>
  </segment>

</diagonal_interconnect>
  <!-- end of diagonal wrapper  -->
  ... 

</segmentlist>
...

Pros:

• Gives the user a decent amount of flexibility (i.e. separate sb/cb patterns can be specified for the vertical/ horizontal segments).
• relatively simple to implement in the code base
• breaks up the description of diagonal wires between multiple segments
• intuitive

Cons:

• specific directions (i.e. NE, SE) cannot be declared on their own, at least not in the way I have it here. Note that this is not really a problem if perfect symmetry is assumed (in the case of the xilinx arch this is a very good approximation)
• Option 2 (from what I can tell) would be easier to implement in the code base. This option requires new functionality to be added to both custom and default switchblock types.

Option 2: Create a diagonal interconnect inside of the custom switchblocklist

Description: Another option would be to specify a special type of switchblock within the switchblocklist for custom SB's. I think this route would be the simplest to implement in code and could potentially give the user the most amount of flexibility in how diagonal wires are defined. The following is just one possible implementation.
Example:

...

<switchblocklist>

  <!-- diagonal switchblock begins-->
 
  <switchblock name="diagonal_interconnect" type="diagonal_connection">
    <switchblock_location type="EVERYWHERE"/>
    <switchfuncs>
      <!-- NW turn -->
      <func type="tl" formula="W-t"/>
      <!-- SW turn -->
      <func type="tl" formula="t+1"/>
      <!-- NE turn -->
      <func type="br" formula="2*W-2-t"/>
      <!-- SE turn -->
      <func type="bl" formula="t+1"/>
    </switchfuncs>

    <!-- The wirecon specifies which segments are connected diagonally with a short ONLY between them. 
    Note that the num_conns as well as to/from_switchpoint details don't really make to much sense here
    since there is only one connection between two wires at the two segments intersection -->
    <wireconn from_type="diagonal_yComp" to_type="diagonal_xComp"/>

    <!-- Note: the different H/V frequencies would be defined for each wire segment in the segment list-->

  </switchblock>
  <!-- diagonal switchblock ends-->
  
  ...
</switchblocklist>
...

Pros:

• This would be by far the easiest to implement in the code base as the functionality of picking unique segments and interconnecting them is already a part of the custom sb's.
• This method could potentially allow a user to specify diagonal wires that only go in a certain direction (i.e. NE wires could be implemented by only allowing for bottom->right connections to occur). Using this method might also allow for T shaped wires (i.e. specifying that three segments connect via short at there intersection points)
• Gives the user the highest degree of flexibility in specifying diagonal interconnect.

Cons:

• Not very intuitive
• In order to use diagonal wires a user would have to use custom SB's. There wouldn't be a way to do diagonal wires with the default SB types.

Option 3: create a new diagonal segment type

Description: I believe this method would be the most difficult to implement in the code base. It would be similar to option 1 above in that it would exist in the segmentlist, however, an entirely new segment description would need to be created.
Example:

...

<segmentlist>
  
  ...
  <!-- start of diagonal segment discription  -->
<diagonal_segment name="verticle4_horizontal2" y_freq="0.5161290" x_freq="0.2580645" length_y="4" length_x="2" type="unidir" Rmetal="101" Cmetal="22.5e-15"> 
    <mux name="mux"/> <!-- Note that this mux would only be used on the ends of the diagonal wire-->

    <!-- the following shows how diffrent sb/cb interconnect patterns could be implemented along the horizontal/verticle lengths
    of the segment. Note that this is optional, one could just not give the user the option of specifying cb/sb interconnect -->
    <y_sb type="pattern">1 0 0 0 1</y_sb>
    <y_cb type="pattern">1 1 1 1</y_cb>

    <x_sb type="pattern">1 0 1</x_sb>
    <x_cb type="pattern">1 1</x_cb>
  </diagonal_segment>
  ... 

</segmentlist>

Pros:

• intuitive

Cons:

• Long xml description
• difficult to implement, would have to basically create from scratch
• depending on what options are given, this method could potentially be the most restrictive to a user.

Conclusion

I think Options 1 or 2 are the best choices for implementing diagonals in the xml. Option 1 is more intuitive in my opinion and has a good balance of user friendliness and flexibility. On the other hand Option 2 is likely much easier to implement and gives the user the maximum amount of flexibility. @jgoeders @vaughnbetz @ArashAhmadian I would love to get your feedback on these ideas. Which option is preferable and/or is there a better way to represent diagonal wires in the xml that you can see?

[WhiteNinjaZ]

I have found that a rough approximation of diagonal interconnect can be created using a very simple change to the architecture description and custom switch blocks. If a switch override tag is added to the wireconn of a switchblock like so:

<wireconn num_conns="min(from,to)" from_type="len4_diag_y" from_switchpoint="0" to_type="len2_diag_x" 
to_switchpoint="0" switch_override="short"/>

the wire_switch of the wire in the to set (len2_diag_x in this case) can be overridden to a short, essentially creating a diagonal wire. However, two issues still remain:

1. In order to keep unwanted unions between switchblocks from happening (i.e. accidentally shorting 2+ diagonal wires together) a lot of redundancy is required in the xml description. I had to use eight different segment types who's only difference between each other was their names in order to specify one diagonal wire that went NE, NW, SE, and SW. The only way I can see to fix this would be to create a new way to specify diagonals in the xml (see last post for examples).
2. On the perimeter of the FPGA there are horizontal or vertical components of a diagonal wire have no counterpart to connect too, essentially creating dangling wires in the architecture (for example, wires that go down 4 and to the right 2 have no horizontal component on the bottom right edge of the FPGA). Possible solutions to this might be to 1) replace unconnected diagonal wires with normal wires from the architecture randomly, or 2) somehow create a way to force every horizontal and vertical component of a diagonal wire to be routed together (possibly by moving them around in the architecture until they fit). @vaughnbetz @jgoeders would love to get your opinion/alternative solutions.

[vaughnbetz]

I tend to like the lower effort ones, so option 2 and the new option (which I think is close to option 2) seem worth trying, as they have the least code changes.
The switch_override tag seems like a generally useful addition; can be used not just to specify shorts for diagonal routing but also more complex switch blocks.

Issue 0: (index 0 means both start and end of a wire): I suspect this isn't really a problem for unidirectional architectures (which are dominant) since we always connect to the start of the receiving wire, and I don't think we ever switch from the start of the sending wire. Hence (for example) a connection from horiz wire at index 0 -> vert wire at index 0 would (I think) always be an H->V diagonal connection, which is what we'd want.

Issue 1 (redundancy): Specifying 8 segments is a bit of a pain if the architecture is symmetric. I think you're saying if we have four different types of diagonal wire (up->right, up->left, down->right, down->left) we'd need 8 segment types to specify the 4 types of diagonal connections. Option 3 gets rid of this redundancy by specifying the two pieces of the diagonal wire in one segment (shorter than 2 current segment descriptions, but longer than 1) and assuming symmetry in all four directions I think. I think the redundancy is an OK price to pay for the easier implementation and the more flexibility to specify some diagonals but not all.

Issue 2 (edge effects): these are real, and it is OK to leave dangling wires there. Switch patterns get strange near the edges of FPGAs as wires get chopped off by the edge etc.
Detailed example (skip if you're tired of reading!) In Stratix, we left the wires dangling, exactly as you say the code would currently do. In Stratix II and later we added some shorts at the edges to short cut off wires to each other with a "u turn". E.g two length 4 wires that were cut off (one with length 3 going left to the left edge, and one with length 1 going right from the left edge would be shorted from the length 3 left-going wire to the length 1 right-going wire. That makes the right-going wire at least a bit usuable, as without the metal short it is undriven in a directional architecture (it's usual mux is outside the left boundary of the chip). But it is not a big deal.