support for swapping pins during routing

[jeras]

Description

While studying synthesis I noticed, for commutative operations (AND/OR reduction, cumulative sum, ...) it would be possible to reorder the input signals (any permutation, or any number of pair swaps) to reduce routing congestion.

Since explaining it would take time, here is how a similar feature works in PCB routing (I could not find such a feature documented for any professional ASIC router). https://www.altium.com/documentation/altium-designer/swapping-pins-pairs-parts?srsltid=AfmBOoqCDmp9WlcYy0lomD2lQUPnvwpyelR3OyQlglScITjzCg7ncdfA

In practice I see the following examples:

• on a small scale, an OR gate, swap two input pins to be able to remove a via,
• on a larger scale a swap might transform 2 crossing long paths into 2 non-crossing shorter paths,
• for a cumulative sum, entire integer operands can be swapped, but also just individual bits with the same weight.

If I had to give a rough estimate of how many signals would be placed into permutation groups, I would say about 10~40% (most on a small scale, some on larger scales, see examples above), but few of the swaps would actually provide an advantage. So this might result in a lot of processing with little result, also I do not know if there are any efficient algorithms able to help.

My question would be, whether pin swapping could/would provide enough routing improvement to be worth to implement.

[maliberty]

We do implement pin swapping for timing optimization but not routing congestion. Its an interesting idea, I'm not sure how much benefit it would generate without trying it. @osamahammad21 any thoughts?

[QuantamHD]

@gadfort mentioned to me that this is a well known routing technique in many tools

[QuantamHD]

We could turn the existing swap code into a library and use it in the router. https://github.com/The-OpenROAD-Project/OpenROAD/blob/9c48043f22892927d3f6b6c492be440fc8a4cdb9/src/rsz/src/RepairSetup.cc#L638

[jeras]

I am currently studying the synthesis part (yosys, abc). Could you point me (so I can look at the documentation/code) to where synthesis is telling the router (or Gate Resizer, ...) which signals could be swapped, if there is such a connection between synthesis and PnR. Otherwise, what mechanism does the router (or Gate Resizer, ...) use to decide which pins are swappable.

From what I was able to understand after a quick look at OpenROAD/src/rsz/src/RepairSetup.cc, it seems only swapping of pins on individual cells is performed. What I would like to provide are groups of signals. A typical example would be a comparator (against the val[7:0] constant or register) for a counter match = (cnt[7:0] == val[7:0]) = ~|(cnt ^ val) = ~|cmp[7:0] (cmp[7:0] = cnt ^ val). The ~| unary AND reduction operator defines a group cmp[7:0] of swappable/permutable signals. This permutability stands regardless whether the ~| reduction is implemented as a chain or as a tree.

I do not have much interest in routing itself right now, so I will not look into the details there. But on the synthesis side I have some ideas on which signals could be tagged for swapping (permutation). The purpose of my question was to decide whether to put some effort into studying this idea or not.

Maybe if you can think about a specific use case where permutability groups provided by synthesis would help PnR, could you point them out, so I can think about those too.

[maliberty]

This isn't information from synthesis. The high level operations have all been lowered to gate level and that's the level at which swapping can occur.

@gadfort I'm familiar with this in a timing context - have you seen it used in routing?

[maliberty]

@gadfort ping

[jeras]

For future reference, I found a few articles which seems to cover this under the name "Permutation Channel Routing Problem":

• https://www.researchgate.net/publication/302334533_Permutation_Channel_Routing
• https://dl.acm.org/doi/10.5555/1711932.1711942
• https://onlinelibrary.wiley.com/doi/10.1155/1994/68279

The following video mentions "bit swapability constraints" (does not seem to be the official name of the feature) in the JITX tool: https://www.youtube.com/watch?v=bw4KxhV-d8g&t=421s

[gadfort]

@maliberty yes, in routing. Usually when its trying to "untangle" a set of routes.

[maliberty]

Channel routing is quite historical but I suppose it is a similar idea. I open to someone giving this a try.

[maliberty]

@osamahammad21 FYI

[maliberty]

Note that rsz already does pin swapping as an timing optimization step but the same infrastructure could be applied here to determine which pins are swappable.